Littlestone 类的近线性私有学习

arXiv:2610.23160v1 公告类型：新摘要：差分隐私学习旨在保护个体训练样本的同时从数据中进行学习。对于二元分类，有限的 Littlestone 维刻画了近似私有 PAC 可学习性（Alon et al., JACM 2022）。理解这一维度如何控制私有样本复杂度，仍是一个核心问题。对于 Littlestone 维为 $d$ 的类，第一个一般性上界关于 $d$ 是双指数的（Bun, Livni, and Moran, FOCS 2020）。后续工作将其改进为 $\widetilde O(d^6)$（Ghazi et al., STOC 2021），再改进为 $\widetilde O(d^5)$（Lyu, STOC 2026）。我们证明了一个近线性的 $O(d\log d)$ 上界。我们的主要算法贡献是：针对配备满足适当稳定性条件的秩的数据依赖候选集，构造一种结构化指数机制。对于子空间指示函数等自然的 Littlestone 类，该秩具有简单的几何解释：它就是余维数。由此，我们为任意域上维数至多为 $d$ 的子空间构造了一个私有 PAC 学习器，其对 $d$ 具有紧的线性依赖，且与环境维数无关，从而改进了 Kaplan et al.（STOC 2025）中的二次依赖。我们的第二项贡献是组合性的：借鉴模型论思想，我们为一般的 Littlestone 类构造了一个合适的秩，并建立了该机制所需的计数界。