研究噪声和对抗扰动下可压缩分布的鲁棒学习性,解决两个开放问题。
Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbations
- 提出扰动-量化框架,结合压缩机制实现鲁棒学习
- 在噪声和对抗攻击下仍保持可学习性,样本复杂度随扰动水平平滑增长
- 首次解决高维均匀混合模型与高斯混合模型在对抗样本下的学习复杂度问题
在无监督学习与统计学中,学习定义在ℝ^d上的分布族是基础问题。核心问题是:给定分布族是否具有足够结构以实现信息论意义上的可学习?若可学习,其样本复杂度如何?2018年,Ashtiani等将样本压缩(sample compressibility)重新定义为分布类的结构性质,证明其保证PAC可学习性,推动了多个高维开放问题的近似紧致样本复杂度界研究。已有猜想认为所有可学习类均存在紧致样本压缩方案。本文证明:在满足必要充分条件时,可压缩分布族在扰动样本下依然可学习。分析两种数据扰动模型:(i) 加性独立噪声模型;(ii) 对抗污染模型,其中对手操控未知的有限样本子集。结果具一般性,假设极小。我们构建扰动-量化框架,自然对接压缩方案,导出样本复杂度随噪声水平与污染预算平稳增长的界。具体应用包括:在噪声与对抗扰动下,对高维均匀分布有限混合模型,以及从对抗污染样本中学习高斯混合模型,首次建立新样本复杂度界,解决了文献中的两个开放问题。
原文摘要 · Abstract (English)
Learning distribution families over $\mathbb{R}^d$ is a fundamental problem in unsupervised learning and statistics. A central question in this setting is whether a given family of distributions possesses sufficient structure to be (at least) information-theoretically learnable and, if so, to characterize its sample complexity. In 2018, Ashtiani et al. reframed \emph{sample compressibility}, originally due to Littlestone and Warmuth (1986), as a structural property of distribution classes, proving that it guarantees PAC-learnability. This discovery subsequently enabled a series of recent advancements in deriving nearly tight sample complexity bounds for various high-dimensional open problems. It has been further conjectured that the converse also holds: every learnable class admits a tight sample compression scheme. In this work, we establish that sample compressible families remain learnable even from perturbed samples, subject to a set of necessary and sufficient conditions. We analyze two models of data perturbation: (i) an additive independent noise model, and (ii) an adversarial corruption model, where an adversary manipulates a limited subset of the samples unknown to the learner. Our results are general and rely on as minimal assumptions as possible. We develop a perturbation-quantization framework that interfaces naturally with the compression scheme and leads to sample complexity bounds that scale gracefully with the noise level and corruption budget. As concrete applications, we establish new sample complexity bounds for learning finite mixtures of high-dimensional uniform distributions under both noise and adversarial perturbations, as well as for learning Gaussian mixture models from adversarially corrupted samples, resolving two open problems in the literature.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。