使用多维回溯搜索最优单坐标步长
本文考虑使用随机块坐标下降方法来最小化一个凸函数,其中关键步骤是更新变量块。现有算法假定为计算更新需要完全解决一个特定子问题。作者在本研究中放宽了这个要求,允许子问题被部分解决,导致一种不完全的块坐标下降方法。本方法将精确更新的最佳结果作为特例,并使用迭代技术和预处理进行进一步的加速。
Apr, 2013
这篇论文提出了基于近期的数据草图(sketching)与优化发展的快速方法,结合(加速的) mini-batch SGD 与一个叫做两步预处理的新方法,以比当前低精度情况下最先进技术所需的时间复杂度更低的近似解。这个方法也可以扩展到高精度情况,提供一个具有显著时间复杂度改进的 Iterative Hessian Sketch (IHS) 方法的替代实现。基准和合成数据集上的实验表明,我们的方法确实在低精度和高精度情况下都明显优于现有方法。
Feb, 2018
提出了一种混合条件梯度方法,可用于在多面体P上最小化平滑凸函数,该方法结合了Frank-Wolfe算法和基于梯度的步骤,并通过保持迭代点为P的极端点的有限数量的稀疏凸组合,避免了向P投影的优点,实现了强凸函数的线性收敛。
May, 2018
本文提出一种针对一类非光滑复合问题的贪心更新规则,其中包括$L1$-正则化问题,SVM等应用程序。我们提供了独立于$n$的首个线性收敛速度,并且证明了我们的贪心更新规则提供了类似于光滑情况下所获得的速度提升。此外,我们还展示了我们的新选择规则可以映射到最大内积搜索实例中,从而利用标准最近邻算法来加速实现。通过广泛的数值实验证明了该方法的有效性。
Oct, 2018
本文提出一种新的自动求导方法——一步法微分(Jacobian-free backpropagation),其性能可与隐式微分方法相媲美,并为快速算法(如超线性优化方法)提供了解决方案。其中使用特定的例子(如牛顿法和梯度下降法)对其进行全面的理论近似分析,并揭示了其在双层优化中的应用。通过多个数值示例,证明了这种一步估计器的正确性。
May, 2023
本文提出了一种新的加速梯度下降方法(AC-FGM),可以在没有给定全局Lipschitz常数或使用线性搜索过程的情况下,实现平滑凸优化的最优收敛速率,并将AC-FGM扩展到具有Hölder连续梯度的凸优化问题,自动实现所有问题类别的最优收敛速率,并在凸优化中演示了AC-FGM相对于以前开发的无参数方法的优势。
Oct, 2023
该研究提出了一种新颖的自适应步长方法来解决随机梯度下降(SGD)中的问题,通过利用我们识别出的可追踪的量(梯度的 Lipschitz 常数和搜索方向的局部方差的概念),我们的发现为随机优化提供了几乎无需调参的算法,该算法在应用于二次问题时具有可证明的收敛性质,并在经典图像分类任务中展现出真正的问题自适应行为。我们的框架还可以包含预处理器,从而实现对随机二阶优化方法的自适应步长的实现。
Nov, 2023
我们提出了自适应的、无需线搜索的二阶方法,以最优收敛速度解决凸凹最大最小问题,通过自适应步长,我们的算法采用简单的更新规则,每次迭代仅需解一个线性系统,消除了线搜索和回溯机制的需求,具体而言,我们基于乐观法则并将其与二阶信息合理地结合,与常见的自适应方案不同的是,我们递归地将步长定义为梯度范数和乐观更新中的预测误差的函数,我们首先分析了一种方案,其中步长需要知道Hessian的Lipschitz常数,在额外假设梯度连续Lipschitz的情况下,我们通过局部跟踪Hessian的Lipschitz常数并确保迭代保持有界,进一步设计了一个无需参数的版本,我们还通过将其与现有的二阶算法进行比较来评估我们算法的实际性能。
Jun, 2024
本研究解决了传统回溯线搜索在数值优化中调整步长效率低的问题。提出了一种新方法,通过考虑所选标准的违反程度来调整步长,避免了额外的计算负担。实验结果表明,自适应回溯能够在实际应用中显著加快优化速度,尤其在使用阿米霍条件和下降引理时具有更高的效率。
Aug, 2024