Littlestone Classes are Privately Online Learnable
Littlestone Classes are Privately Online Learnable
复制标题
Littlestone 课程可私下在线学习
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Roi Livni
中科院分区：
文献类型：
--
作者：
Noah Golowich;Roi Livni
我们考虑隐私约束下的在线分类问题。在这种设置中，学习器顺序观察标记的示例$（x_t，y_t）$的流，对于$1 \leq t \leq T$，并在每次迭代$t$返回用于预测每个新示例$x_t$的标签的假设$h_t$。学习者的表现是衡量她对一个已知的假设类$\mathcal{H}$的遗憾。我们要求算法满足以下隐私约束：算法输出的假设序列$h_1，\ldots，h_T$需要是整个输入序列$（x_1，y_1），\ldots，（x_T，y_T）$的$（\delta，\delta）$-差分隐私函数。我们提供了第一个非平凡的遗憾的可实现的设置。具体来说，我们表明，如果类$\mathcal{H}$具有恒定的Littlestone维数，那么，给定一个不经意的序列标记的例子，有一个私人学习者，使在预期中最多$O（\log T）$错误-在非私人的情况下，最佳的错误界相比，对数因子。此外，对于Littlestone维数d的一般值，同样的错误界成立，但具有双指数的d因子。最近的一项工作表明，在线学习的课程和差异化私人学习的课程之间存在着很强的联系。我们的研究结果加强了这种联系，并表明在线学习算法实际上可以直接私有化（在可实现的设置中）。我们还讨论了一个自适应设置，并提供了一个次线性遗憾界为O（\sqrt{T}）$。
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 non-trivial 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 non-private case, up to a logarithmic factor. Moreover, for general values of the Littlestone dimension $d$, the same mistake bound holds but with a doubly-exponential in $d$ factor. A recent line of work has demonstrated a strong connection between classes that are online learnable and those that are differentially-private 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})$.
DOI：
10.1145/3188745.3188946
发表时间：
2018-06
期刊：
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Mark Bun;C. Dwork;G. Rothblum;T. Steinke
通讯作者：
Mark Bun;C. Dwork;G. Rothblum;T. Steinke
具有隐私保证的无投影强盗优化
DOI：
--
发表时间：
2021
期刊：
Proceedings of the AAAI Conference on Artificial Intelligence
影响因子：
--
作者：
Ene, Alina;Nguyen, Huy L;Vladu, Adrian
通讯作者：
Vladu, Adrian
私有中心点和半空间学习
DOI：
--
发表时间：
2020
期刊：
COLT 2019
影响因子：
--
作者：
Amos Beimel, Shay Moran
通讯作者：
Amos Beimel, Shay Moran