我们提出了一个利用非线性系统理论填补演进中算法收敛性和鲁棒性分析的理论框架,可以自动化地优化学习到的算法,保证其设计上的收敛性。
Mar, 2024
分析迭代算法的收敛速度与稳定性之间的平衡问题,得出迭代算法总体表现是由最小二乘统计误差下界和稳定性共同决定的结论。以几种收敛速度较快的迭代算法为例,讨论了它们的稳定性上界和下界,并提出一些问题,说明改进收敛速度需要牺牲稳定性的平衡关系。
Apr, 2018
我们开发了一个新的框架来研究光滑和强凸优化算法,特别是针对二次函数,我们能够将优化算法作为线性运算的递归应用程序来检查,这揭示了一种强大的联系,即一类优化算法与多项式的分析理论之间的联系,从而导出了新的下界和上界,同时我们还以多项式相关的最优解的形式表达它,从而对 Nesterov 著名的加速梯度下降方法进行了新的系统推导。
Mar, 2015
该研究探讨了基于梯度的优化算法在机器学习应用中的收敛速度、遗憾界限等指标以及其与稳定性保证之间的关系,并提供了更为通用的稳定性保证,以促进实时学习应用的安全可靠部署。
May, 2024
本文提出了一种新颖的方法来生成 Lyapunov 函数,以证明一阶优化方法的线性收敛率,该方法能够获得可以由二次 Lyapunov 函数进行验证的最快线性收敛率,并且仅仅依赖于解决大小适中的半定规划问题,该方法结合了性能估算问题和积分二次约束的优点,并依赖于凸插值。
Mar, 2018
我们提出了一种随机梯度框架,用于解决具有(可能)无限数量的线性包含约束条件的随机复合凸优化问题,而这些约束条件需要几乎确定。我们使用平滑和同伦技术处理约束条件,无需矩阵投影,并且通过数值实验表明,我们的算法实现了最先进的实用性能。
Jan, 2019
本文提供了一种新颖的计算机辅助技术,用于系统地分析面向优化的一阶方法,并且与以往的工作相比,该方法特别适用于处理次线性收敛率和随机预言机。该技术依赖于半定规划和潜力函数,并允许同时获得算法行为的最坏情况保证,并帮助选择适当的参数以调整其最坏情况表现。
Feb, 2019
研究用于找到凸凹函数鞍点的随机一阶方法的性能。我们提出了一种简单有效的正则化技术,稳定迭代并提供有意义的性能保证,即使域和梯度噪声与迭代的大小成线性关系(可能是无界的)。此外,我们还将算法应用于强化学习中的特定问题,在无偏扩展的平均奖励 MDP 中,即使没有先验知识,也能找到接近最优策略的性能保证。
Feb, 2024
本文提供了用于计算强凸光滑函数的梯度(或 Cauchy 梯度下降)方法和自准共轭函数的 Newton 方法(包括不准确搜索方向的情况)的最坏情况性能分析的新工具,并通过半定规程性能评估分析扩展了最近 2017 年 Optimization Letters 论文中作者对 Cauchy 方法的性能评估结果,然后通过使用这些工具以一种创新的方式对使用不准确搜索方向的短步长内点法的复杂性进行了演示。作为此框架中的示例,我们概述了如何通过 Abernethy 和 Hazan 在 2016 年的 PMLR 论文中的最近内点法的最坏情况复杂性的严格分析。
Sep, 2017
本文研究了最速下降法在具有 Lipschitz 连续梯度的强凸函数中的精确线性搜索,并确定了该方案的最差收敛速度,证明了某些凸二次函数展示的最差行为。我们还给出了一种噪声变体的最差复杂性边界,通过改变搜索方向,该方向与负梯度的值之差最多只有一个预定的相对容差,并借助于半定规划性能估计问题的解决方法进行了计算机辅助证明
Jun, 2016