全批量梯度下降在单指数模型中仅需约d个样本即可高效学习，优于仅遍历一次的数据的随机梯度下降。
Full-Batch Gradient Descent Outperforms One-Pass SGD: Sample Complexity Separation in Single-Index Learning
- 通过截断激活函数，全批量梯度下降在n≈d时优化景观更优。
- 全批量梯度下降在n≳d样本下实现精确恢复，而一阶段SGD需n≳d log d。
- 适合关注非凸优化样本效率的研究者，尤其是深度学习理论方向。
在学习一个具有二次激活函数的d维单指数模型时，已知一阶段随机梯度下降（online SGD）需要n≳d log d个样本才能实现弱恢复。本文首先证明，对相关损失使用全批量球形梯度下降（spherical GD），该log d因子依然存在；但通过简单截断激活函数，全批量GD在n≈d样本时展现出有利的优化景观，从而在统计效率上超越使用相同激活函数的一阶段SGD。此外，通过对小初始化下的平方损失进行轨迹分析，表明n≳d样本和T≳log d次梯度步数足以实现强（精确）恢复。
原文摘要 · Abstract (English)
It is folklore that reusing training data more than once can improve the statistical efficiency of gradient-based learning. While this phenomenon has been extensively studied in linear regression, the benefit of multi-pass gradient descent (GD, which reuses all the data) over one-pass stochastic gradient descent (online SGD, which uses each data point only once) is not well-understood in nonlinear and non-convex settings, except for a loss modification mechanism achieved by the first two passes on the data. In this work, we consider learning a $d$-dimensional single-index model with a quadratic activation, for which it is known that one-pass SGD requires $n\gtrsim d\log d$ samples to achieve weak recovery. We first show that this $\log d$ factor in the sample complexity persists for full-batch spherical GD on the correlation loss; however, by simply truncating the activation, full-batch GD exhibits a favorable optimization landscape at $n \simeq d$ samples, thereby outperforming one-pass SGD (with the same activation) in statistical efficiency. We complement this result with a trajectory analysis of full-batch GD on the squared loss from small initialization, showing that $n \gtrsim d$ samples and $T \gtrsim\log d$ gradient steps suffice to achieve strong (exact) recovery.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。