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 consider the problem of online classification under a privacy constraint.In this setting a learner observes sequentially a stream of labelled examples$(x_t, y_t)$, for $1 \leq t \leq T$, and returns at each iteration $t$ ahypothesis $h_t$ which is used to predict the label of each new example $x_t$.The learner's performance is measured by her regret against a known hypothesisclass $\mathcal{H}$. We require that the algorithm satisfies the followingprivacy constraint: the sequence $h_1, \ldots, h_T$ of hypotheses output by thealgorithm needs to be an $(\epsilon, \delta)$-differentially private functionof the whole input sequence $(x_1, y_1), \ldots, (x_T, y_T)$. We provide thefirst non-trivial regret bound for the realizable setting. Specifically, weshow that if the class $\mathcal{H}$ has constant Littlestone dimension then,given an oblivious sequence of labelled examples, there is a private learnerthat makes in expectation at most $O(\log T)$ mistakes -- comparable to theoptimal mistake bound in the non-private case, up to a logarithmic factor.Moreover, for general values of the Littlestone dimension $d$, the same mistakebound holds but with a doubly-exponential in $d$ factor. A recent line of workhas demonstrated a strong connection between classes that are online learnableand those that are differentially-private learnable. Our results strengthenthis connection and show that an online learning algorithm can in fact bedirectly privatized (in the realizable setting). We also discuss an adaptivesetting and provide a sublinear regret bound of $O(\sqrt{T})$.

Littlestone Classes are Privately Online Learnable