首个针对VC维为1概念类的近最优差分隐私学习算法

An $\tilde{O}$ptimal Differentially Private Learner for Concept Classes with VC Dimension 1

• 设计了基于差分隐私的近最优学习算法
• 样本复杂度达到约 log* d，逼近理论下限
• 适合研究隐私保护学习与小维度概念类的学者

我们提出了首个针对任意VC维为1、Littlestone维数为d的概念类的近最优差分隐私PAC学习算法。该算法实现的样本复杂度为$ ilde{O}_{ε,δ,α,δ}("log^* d)$，几乎匹配Alon等人在STOC19中证明的$Ω("log^* d)$理论下界。此前最佳结果为Ghazi等人在STOC21中给出的$ ilde{O}(VC\cdot d^5)$，适用于一般VC类。

原文摘要 · Abstract (English)

We present the first nearly optimal differentially private PAC learner for any concept class with VC dimension 1 and Littlestone dimension $d$. Our algorithm achieves the sample complexity of $\tilde{O}_{\varepsilon,δ,α,δ}(\log^* d)$, nearly matching the lower bound of $Ω(\log^* d)$ proved by Alon et al. [STOC19]. Prior to our work, the best known upper bound is $\tilde{O}(VC\cdot d^5)$ for general VC classes, as shown by Ghazi et al. [STOC21].

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。