Jan, 2024
用梯度实现的维度冲击：随机凸优化中的梯度方法的泛化
The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization
Matan Schliserman, Uri Sherman, Tomer Koren
TL;DR研究了梯度方法在基础随机凸优化条件下的泛化性能，并关注其与维数的依赖关系。针对全批量梯度下降（GD），通过构建学习问题，在维数为 $ d = O（n^2）$ 的情况下，可以证明经过调整以达到经验风险最优表现的典型 GD（使用 n 个训练样本）在具有常数概率的情况下，收敛为近似经验风险最小化器，且其相对于总体风险具有 Ω（1）的过量风险。这个界限对于标准 GD 需要达到非平凡测试误差的训练样本数量有一个下界 Ω（√d），回答了 Feldman（2016）和 Amir，Koren 和 Livni（2021b）提出的一个开放问题，表明非平凡的维数依赖性是不可避免的。此外，针对标准的一次遍历随机梯度下降（SGD），我们证明了同样的构建技术在样本复杂度上提供了类似的 Ω（√d）下界，以达到非平凡的经验误差，尽管它可以实现最优的测试性能。与之前的工作（Koren，Livni，Mansour 和 Sherman，2022）相比，这提供了维数依赖性的指数级改进，解决了其中的一个开放问题。