随机特征组合可逼近无分布假设下的神经网络训练结果
The Power of Random Features and the Limits of Distribution-Free Gradient Descent
- 用随机特征线性组合模拟梯度下降过程，无需数据分布假设
- 训练步数和精度决定所需特征组合的大小，呈多项式关系
- 揭示了无分布假设下学习的局限性，适合理论研究者参考
我们研究参数化模型（如神经网络）的梯度优化与随机特征线性组合优化之间的关系。核心结论表明：若某参数化模型可在不假设数据分布的前提下通过小批量随机梯度下降（bSGD）学习，则以高概率可由一个多项式规模的随机特征组合近似目标函数。该组合规模取决于bSGD过程中的梯度步数和数值精度。这一发现揭示了在梯度下降训练的神经网络中，无分布假设学习的根本局限性，说明实践中假设数据分布往往至关重要。此外，我们引入了一种新理论框架——平均概率维复杂度（adc），它扩展了Kamath等人（2020）提出的概率维复杂度。我们证明adc与统计查询维复杂度存在多项式关系，并据此展示了adc与标准维复杂度之间的无限差距。
原文摘要 · Abstract (English)
We study the relationship between gradient-based optimization of parametric models (e.g., neural networks) and optimization of linear combinations of random features. Our main result shows that if a parametric model can be learned using mini-batch stochastic gradient descent (bSGD) without making assumptions about the data distribution, then with high probability, the target function can also be approximated using a polynomial-sized combination of random features. The size of this combination depends on the number of gradient steps and numerical precision used in the bSGD process. This finding reveals fundamental limitations of distribution-free learning in neural networks trained by gradient descent, highlighting why making assumptions about data distributions is often crucial in practice. Along the way, we also introduce a new theoretical framework called average probabilistic dimension complexity (adc), which extends the probabilistic dimension complexity developed by Kamath et al. (2020). We prove that adc has a polynomial relationship with statistical query dimension, and use this relationship to demonstrate an infinite separation between adc and standard dimension complexity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。