优化中的可重复性:理论框架与限制
本文研究了利用随机一阶预测器在凸集上最小化凸函数的问题,证明了函数在最小值点$x_{f, S}^*$附近增长的速率是最优学习率的决定因素,并得到了关于学习率和复杂度的结论结果。
Jul, 2012
我们开发了一个新的框架来研究光滑和强凸优化算法,特别是针对二次函数,我们能够将优化算法作为线性运算的递归应用程序来检查,这揭示了一种强大的联系,即一类优化算法与多项式的分析理论之间的联系,从而导出了新的下界和上界,同时我们还以多项式相关的最优解的形式表达它,从而对Nesterov著名的加速梯度下降方法进行了新的系统推导。
Mar, 2015
本文探讨了在随机凸优化问题中寻找近似驻点的 oracle 复杂度问题和其和全局 oracle 模型的关系,并提出了一种扩展的递归正则化算法以实现接近最优率,并揭示了 stochastic optimization 和 learning 的复杂度之间的一些惊人区别。
Feb, 2019
本文研究了梯度下降算法在非凸优化问题中的性能保证,发现梯度噪声对逃脱鞍点和到达二阶稳定点的效率起到了关键作用,提出了一个基于均方方法的替代方案来保证梯度噪声的相对方差较小就足以确保逃脱鞍点,而不需要注入其他噪声或采用全局分散噪声假设。
Aug, 2019
该论文研究贝叶斯学习中常见的最大后验估计和后验分布采样的计算任务,证明在非凸情况下后验分布采样有时比优化更快,并展示两者在计算复杂性上的不可比较性,呈现出计算复杂度的急剧相变。
Nov, 2019
通过改变训练过程中的微小变化以度量算法的可重现性,我们挑战了之前的观点,并证明在各种有错误的预测设置下,对于平滑凸优化和平滑凸凹极小极大问题,可以实现最佳的可重现性和接近最优的收敛保证。
Oct, 2023
研究表明,强化学习中存在噪音和随机性,现有的评估程序仅使用期望回报评估政策,限制其在比较政策和选择最佳权衡值方面的有效性。本研究通过推荐使用贝叶斯优化中的置信下界指标,为用户提供选择所需性能与重复性权衡的参数,并通过大量实验验证了这些指标的益处。
Dec, 2023
使用定期化的最小化增量替代优化算法 (MISO),基于常规的重复采样方案,在非凸、可能非光滑的目标函数上,期望的最优性差随着数据点数量的增加以最佳速率 O(n^{-1/2}) 收敛。更进一步,暗示常数明确取决于“重复速度”,通过对预期访问给定数据点的时间进行平均(“目标时间”)或最大化(“击中时间”)测量。我们的研究理论上和实证上证明,通过选择最有效地覆盖数据集的采样算法,可以加速收敛速度。我们还讨论了该通用框架在分散优化和分布式非负矩阵分解方面的应用。
Jan, 2024
双层优化是一种针对依赖于内部优化问题解的外部目标函数进行优化的方法,在机器学习中广泛应用于超参数调整。本研究通过研究隐藏变量方法的误差,分析了两种减小误差的策略:预处理隐藏变量公式和重新参数化内部问题。我们详细说明了这两种修改对误差的影响,并强调了涉及的功能的高阶导数所起的作用。我们的理论发现解释了何时可以实现超级效率,即使得超梯度的误差与内部问题的误差二次相关,并在这种情况下比较了两种方法。对回归问题的超参数调整的数值评估验证了我们的理论发现。
Feb, 2024
我们分析了非光滑随机凸优化中全批量梯度下降(GD)的样本复杂性,表明GD的泛化误差与最优超参数选择的样本复杂性匹配,可以表示为Θ(d/m + 1/√m),其中d为维度,m为样本大小,这与最坏情况下的经验风险最小化器相符,这意味着与其他算法相比,GD没有优势。我们的界限来自一个新的泛化界限,它取决于维度、学习速率和迭代次数。对于一般的超参数,当维度严格大于样本数量时,需要Ω(1/ε^4)次迭代才能避免过拟合,这解决了schliserman2024dimension和amir2021sgd提出的一个开放问题,并改进了先前的下界,前者证明了样本大小至少必须为维度的平方根。
Apr, 2024