标题： 小石类的私有学习，再审视 显示英文标题

标题： Private Learning of Littlestone Classes, Revisited

摘要： 我们考虑在近似差分隐私约束下的Littlestone类的在线学习和PAC学习。 我们的主要结果是一个私有学习者，在可实现情况下，可以以错误界为$\tilde{O}(d^{9.5}\cdot \log(T))$在线学习一个Littlestone类，其中$d$表示Littlestone维数，$T$表示时间范围。 这比最新的成果[GL'21]有了双重指数级的改进，并且与该任务的下限多项式接近。 这一进展得益于几个关键要素。 第一个是对于最新私有PAC学习者中“不可约性”技术的清晰且精炼的解释[GGKM'21]。 我们的新视角也使我们能够改进[GGKM'21]中的PAC学习者，并给出样本复杂度上界为$\widetilde{O}(\frac{d^5 \log(1/\delta\beta)}{\varepsilon \alpha})$，其中$\alpha$和$\beta$分别表示PAC学习者的准确性和置信度。 这比[GGKM'21]提高了$\frac{d}{\alpha}$倍，并实现了与$\alpha$的最优依赖关系。 我们的算法使用了一种私有稀疏选择算法，从一组强输入依赖的候选者中进行\emph{样本}。 然而，与大多数之前使用稀疏选择算法的情况不同，我们只关注输出的效用，我们的算法需要理解和操作输出所来自的实际分布。 在证明中，我们使用了[GKM'21]中的一种稀疏版本的指数机制，它在我们的框架下表现良好，并且易于进行效用证明。 显示英文摘要

摘要： We consider online and PAC learning of Littlestone classes subject to the constraint of approximate differential privacy. Our main result is a private learner to online-learn a Littlestone class with a mistake bound of $\tilde{O}(d^{9.5}\cdot \log(T))$ in the realizable case, where $d$ denotes the Littlestone dimension and $T$ the time horizon. This is a doubly-exponential improvement over the state-of-the-art [GL'21] and comes polynomially close to the lower bound for this task. The advancement is made possible by a couple of ingredients. The first is a clean and refined interpretation of the ``irreducibility'' technique from the state-of-the-art private PAC-learner for Littlestone classes [GGKM'21]. Our new perspective also allows us to improve the PAC-learner of [GGKM'21] and give a sample complexity upper bound of $\widetilde{O}(\frac{d^5 \log(1/\delta\beta)}{\varepsilon \alpha})$ where $\alpha$ and $\beta$ denote the accuracy and confidence of the PAC learner, respectively. This improves over [GGKM'21] by factors of $\frac{d}{\alpha}$ and attains an optimal dependence on $\alpha$. Our algorithm uses a private sparse selection algorithm to \emph{sample} from a pool of strongly input-dependent candidates. However, unlike most previous uses of sparse selection algorithms, where one only cares about the utility of output, our algorithm requires understanding and manipulating the actual distribution from which an output is drawn. In the proof, we use a sparse version of the Exponential Mechanism from [GKM'21] which behaves nicely under our framework and is amenable to a very easy utility proof.