提出更高效的隐私保护在线学习算法，显著降低错误次数。
Private Learning of Littlestone Classes, Revisited
- 采用改进的不可约性技术与私有稀疏选择机制
- 在线学习错误数降至 $\tilde{O}(d^{9.5} \log T)$，比之前快两倍指数级
- 适合关注隐私保护与高效学习的算法研究者
我们研究在近似差分隐私约束下对 Littlestone 类的在线学习和 PAC 学习。主要成果是设计了一个私有学习器，在可实现情况下以 $\tilde{O}(d^{9.5} \cdot \log T)$ 的错误率在线学习 Littlestone 维度为 $d$ 的类别，其中 $T$ 为时间范围。该结果相比现有最优 [GL'21] 实现了双重指数级提升，并逼近该任务的理论下界。改进得益于对 [GGKM'21] 中不可约性技术的全新解读，使我们能优化其 PAC 学习器，获得样本复杂度上界 $\widetilde{O}\left(\frac{d^5 \log(1/δβ)}{\varepsilon α}\right)$，其中 $α$ 和 $β$ 分别表示精度和置信度，较 [GGKM'21] 提升 $\frac{d}{α}$ 因子并达到 $α$ 的最优依赖。算法使用私有稀疏选择从高度依赖输入的候选池中采样，但不同于以往仅关注输出效用的做法，需精确理解并控制采样分布。证明中引入 [GKM'21] 的稀疏化指数机制，具有良好性质，便于简化效用分析。
原文摘要 · Abstract (English)
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/δβ)}{\varepsilon α})$ where $α$ and $β$ denote the accuracy and confidence of the PAC learner, respectively. This improves over [GGKM'21] by factors of $\frac{d}α$ and attains an optimal dependence on $α$. 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。