自适应回溯加速优化
本文研究了变量排序和局部一致性对冲突-directed backjumping算法的影响。实验证明,增强前瞻技术有时对回溯算法的后跳技术产生反作用。理论分析表明,在回溯搜索中保持的局部一致性水平越高,后跳的改进效果就越小。
Jun, 2011
本文提供一个简明的证明,只需遵循两个规则即可自动化梯度下降:1)不要过快增加步长,2)不要超出局部曲率;通过遵循这些规则,可以得到对局部几何条件自适应的方法,收敛保证只取决于解的附近的平滑度,因此收敛于任何凸问题中,包括可以最小化任意连续两次可微的凸函数的问题,本文将探讨该方法在一系列凸和非凸问题上的性能。
Oct, 2019
本文提出了一种新的加速梯度下降方法(AC-FGM),可以在没有给定全局Lipschitz常数或使用线性搜索过程的情况下,实现平滑凸优化的最优收敛速率,并将AC-FGM扩展到具有Hölder连续梯度的凸优化问题,自动实现所有问题类别的最优收敛速率,并在凸优化中演示了AC-FGM相对于以前开发的无参数方法的优势。
Oct, 2023
该研究提出了一种新颖的自适应步长方法来解决随机梯度下降(SGD)中的问题,通过利用我们识别出的可追踪的量(梯度的 Lipschitz 常数和搜索方向的局部方差的概念),我们的发现为随机优化提供了几乎无需调参的算法,该算法在应用于二次问题时具有可证明的收敛性质,并在经典图像分类任务中展现出真正的问题自适应行为。我们的框架还可以包含预处理器,从而实现对随机二阶优化方法的自适应步长的实现。
Nov, 2023
基于最近的无线搜索自适应近端梯度方法,本文提出了AdaPG^rπ框架,通过提供更大的步长策略和改进的下界,统一和扩展了现有的结果。讨论了参数π和r的不同选择,并通过数值模拟证明了所得方法的有效性。为了更好地理解基本理论,还建立了一个允许时变参数的更一般的收敛性设置。最后,通过探索对偶设置,提出了一种自适应交替最小化算法。这种算法不仅包含了额外的适应性,而且扩展了其适用性,超出了标准强凸设置。
Nov, 2023
我们开发了一种梯度下降法的新次优性边界,该边界依赖于优化路径中的目标条件,而不是全局最坏情况下的常数。我们的证明关键在于方向平滑性,这是一种梯度变化的度量,我们用它来开发上界约束。通过求解隐式方程来最小化这些上界约束,我们展示了这些方程对于凸二次函数是容易解决的,并为两种传统步长提供了新的保证。对于一般函数,我们证明了Polyak步长和归一化梯度下降法尽管不使用方向平滑性的任何知识,但能够获得快速的路径相关性。逻辑回归上的实验证明,我们的收敛保证比基于L平滑性的传统理论更紧致。
Mar, 2024
通过对于凸最小化问题的自适应方法的最新进展的利用,本文提供了一种无需线搜索的近端梯度下降框架,用于全局化收敛于流行的步长选择,如Barzilai-Borwein和一维Anderson加速。该框架可以处理梯度可微函数只具有局部Holder连续性的问题。我们的分析不仅包含但也改进了现有结果,并以数值证据来证明快速步长选择和自适应方法之间的协同作用。
Apr, 2024
我们提出了自适应的、无需线搜索的二阶方法,以最优收敛速度解决凸凹最大最小问题,通过自适应步长,我们的算法采用简单的更新规则,每次迭代仅需解一个线性系统,消除了线搜索和回溯机制的需求,具体而言,我们基于乐观法则并将其与二阶信息合理地结合,与常见的自适应方案不同的是,我们递归地将步长定义为梯度范数和乐观更新中的预测误差的函数,我们首先分析了一种方案,其中步长需要知道Hessian的Lipschitz常数,在额外假设梯度连续Lipschitz的情况下,我们通过局部跟踪Hessian的Lipschitz常数并确保迭代保持有界,进一步设计了一个无需参数的版本,我们还通过将其与现有的二阶算法进行比较来评估我们算法的实际性能。
Jun, 2024