随机凸优化中不要使用完整批次
本文研究了随机梯度下降和全样本梯度下降在随机凸优化模型中泛化性能的分离问题,发现经典的全样本梯度下降算法在步数相同的情况下会出现过拟合且通常需要更多的步数才能与随机梯度下降算法获得类似的泛化性能。同时本文还探讨了正则化、稳定性和隐含偏差等概念在泛化中的作用。
Feb, 2021
研究了梯度方法在基础随机凸优化条件下的泛化性能,并关注其与维数的依赖关系。针对全批量梯度下降(GD),通过构建学习问题,在维数为 $ d = O(n^2)$ 的情况下,可以证明经过调整以达到经验风险最优表现的典型 GD(使用 n 个训练样本)在具有常数概率的情况下,收敛为近似经验风险最小化器,且其相对于总体风险具有 Ω(1)的过量风险。这个界限对于标准 GD 需要达到非平凡测试误差的训练样本数量有一个下界 Ω(√d),回答了 Feldman(2016)和 Amir,Koren 和 Livni(2021b)提出的一个开放问题,表明非平凡的维数依赖性是不可避免的。此外,针对标准的一次遍历随机梯度下降(SGD),我们证明了同样的构建技术在样本复杂度上提供了类似的 Ω(√d)下界,以达到非平凡的经验误差,尽管它可以实现最优的测试性能。与之前的工作(Koren,Livni,Mansour 和 Sherman,2022)相比,这提供了维数依赖性的指数级改进,解决了其中的一个开放问题。
Jan, 2024
我们分析了非光滑随机凸优化中全批量梯度下降(GD)的样本复杂性,表明 GD 的泛化误差与最优超参数选择的样本复杂性匹配,可以表示为 Θ(d/m + 1/√m),其中 d 为维度,m 为样本大小,这与最坏情况下的经验风险最小化器相符,这意味着与其他算法相比,GD 没有优势。我们的界限来自一个新的泛化界限,它取决于维度、学习速率和迭代次数。对于一般的超参数,当维度严格大于样本数量时,需要 Ω(1/ε^4) 次迭代才能避免过拟合,这解决了 schliserman2024dimension 和 amir2021sgd 提出的一个开放问题,并改进了先前的下界,前者证明了样本大小至少必须为维度的平方根。
Apr, 2024
我们研究了在紧致集合上的光滑凸函数中使用随机梯度下降的泛化误差,并展示了当迭代次数 T 和数据集大小 n 以任意速率趋近于零时,我们第一次得到了一个消失的泛化误差界,该界与步长 αt=1/√t 成比例,泛化能力不需要强凸性。
Jan, 2024
本篇论文研究了关于随机逼近问题的现有算法,提出了两种新型随机梯度算法,并在回归和逻辑分类两种经典的监督学习问题上进行了测试,得到了较好的优化效果。
Jun, 2013
通过加速梯度方法,改进小批量算法加速随机凸优化问题,提供新颖分析证明标准梯度法有时不足以获取大幅加速,提出一种新的加速梯度算法,解决了这个缺点,并在实践中表现良好。
Jun, 2011
本文证明使用随机梯度方法训练的参数模型少迭代次数即可实现消失的泛化误差,提供了新的对于随机梯度方法多周期泛化性能好的解释,对于神经网络的训练也有新的稳定性解释。
Sep, 2015
随机梯度下降是最简单的深度学习优化器之一,该论文通过蒙特卡洛方法对其进行了收敛性分析,并证明了使用 Armijo 线搜索的随机梯度下降在非凸优化中的性能优于其他深度学习优化器,同时还发现了批量大小对训练的影响,批量大小越大,需要的步数越少,但在成本和梯度计算的角度,存在一个临界批量大小最能降低成本。
Jul, 2023