Timezone: »
Poster
Littlestone Classes are Privately Online Learnable
Noah Golowich · Roi Livni
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$ a hypothesis $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 hypothesis class $\mathcal{H}$. We require that the algorithm satisfies the following privacy constraint: the sequence $h_1, \ldots, h_T$ of hypotheses output by the algorithm needs to be an $(\epsilon, \delta)$differentially private function of the whole input sequence $(x_1, y_1), \ldots, (x_T, y_T)$.We provide the first nontrivial regret bound for the realizable setting. Specifically, we show that if the class $\mathcal{H}$ has constant Littlestone dimension then, given an oblivious sequence of labelled examples, there is a private learner that makes in expectation at most $O(\log T)$ mistakes  comparable to the optimal mistake bound in the nonprivate case, up to a logarithmic factor. Moreover, for general values of the Littlestone dimension $d$, the same mistake bound holds but with a doublyexponential in $d$ factor. A recent line of work has demonstrated a strong connection between classes that are online learnable and those that are differentiallyprivate learnable. Our results strengthen this connection and show that an online learning algorithm can in fact be directly privatized (in the realizable setting).We also discuss an adaptive setting and provide a sublinear regret bound of $O(\sqrt{T})$.
Author Information
Noah Golowich (MIT)
Roi Livni (Tel Aviv University)
Related Events (a corresponding poster, oral, or spotlight)

2021 Spotlight: Littlestone Classes are Privately Online Learnable »
Dates n/a. Room
More from the Same Authors

2021 : NearOptimal NoRegret Learning in General Games »
Constantinos Daskalakis · Maxwell Fishelson · Noah Golowich 
2021 : NearOptimal NoRegret Learning in General Games »
Constantinos Daskalakis · Maxwell Fishelson · Noah Golowich 
2021 Poster: Deep Learning with Label Differential Privacy »
Badih Ghazi · Noah Golowich · Ravi Kumar · Pasin Manurangsi · Chiyuan Zhang 
2021 Poster: Never Go Full Batch (in Stochastic Convex Optimization) »
Idan Amir · Yair Carmon · Tomer Koren · Roi Livni 
2021 Poster: NearOptimal NoRegret Learning in General Games »
Constantinos Daskalakis · Maxwell Fishelson · Noah Golowich 
2021 Oral: NearOptimal NoRegret Learning in General Games »
Constantinos Daskalakis · Maxwell Fishelson · Noah Golowich 
2020 Poster: Can Implicit Bias Explain Generalization? Stochastic Convex Optimization as a Case Study »
Assaf Dauber · Meir Feder · Tomer Koren · Roi Livni 
2017 Poster: AffineInvariant Online Optimization and the Lowrank Experts Problem »
Tomer Koren · Roi Livni 
2017 Poster: MultiArmed Bandits with Metric Movement Costs »
Tomer Koren · Roi Livni · Yishay Mansour