English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present a provably optimal differentially private algorithm for thestochastic multi-arm bandit problem, as opposed to the private analogue of theUCB-algorithm [Mishra and Thakurta, 2015; Tossou and Dimitrakakis, 2016] whichdoesn't meet the recently discovered lower-bound of $\Omega\left(\frac{K\log(T)}{\epsilon} \right)$ [Shariff and Sheffet, 2018]. Ourconstruction is based on a different algorithm, Successive Elimination[Even-Dar et al. 2002], that repeatedly pulls all remaining arms until an armis found to be suboptimal and is then eliminated. In order to devise a privateanalogue of Successive Elimination we visit the problem of private stoppingrule, that takes as input a stream of i.i.d samples from an unknowndistribution and returns a multiplicative $(1 \pm \alpha)$-approximation of thedistribution's mean, and prove the optimality of our private stopping rule. Wethen present the private Successive Elimination algorithm which meets both thenon-private lower bound [Lai and Robbins, 1985] and the above-mentioned privatelower bound. We also compare empirically the performance of our algorithm withthe private UCB algorithm.

An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rule