随机偏置让复杂函数学习变简单，小扰动即有效
Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions
- 用随机均值偏移改变数据分布，简化学习任务
- 高维单指数模型经扰动后学习复杂度等同线性函数
- 结果适用于稀疏布尔函数，适合关注泛化效率的研究者
单指数与多指数模型的学习问题在高维统计中备受关注。近期研究多聚焦于梯度方法在各向同性分布下的表现，揭示了目标函数的跳跃性、信息量与生成指数等分析性质对算法样本复杂度的决定作用，量化区分了低复杂度与高复杂度学习任务。本文证明：高复杂度情形极为罕见。具体而言，仅通过在数据分布的一阶矩上引入微小随机扰动（如随机平移），即可使任意高斯单指数模型的学习难度降至与线性函数相当。该结论进一步拓展至一类多指数模型——稀疏布尔函数（即朱诺斯函数），表明随机偏置能普遍降低复杂函数的学习门槛。
原文摘要 · Abstract (English)
The problem of learning single index and multi index models has gained significant interest as a fundamental task in high-dimensional statistics. Many recent works have analysed gradient-based methods, particularly in the setting of isotropic data distributions, often in the context of neural network training. Such studies have uncovered precise characterisations of algorithmic sample complexity in terms of certain analytic properties of the target function, such as the leap, information, and generative exponents. These properties establish a quantitative separation between low and high complexity learning tasks. In this work, we show that high complexity cases are rare. Specifically, we prove that introducing a small random perturbation to the data distribution--via a random shift in the first moment--renders any Gaussian single index model as easy to learn as a linear function. We further extend this result to a class of multi index models, namely sparse Boolean functions, also known as Juntas.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。