本文研究了一类增量方法,用于解决微弱凸优化问题,并证明了这三种增量方法可以使自然稳定性测量值小于给定的极值下界,同时,当微弱凸函数满足锐化条件时,经过适当的初始化和几何递减的步长,三种增量方法可以实现局部线性收敛速度,最后在鲁棒矩阵感知问题上进行了数值实验。
Jul, 2019
该篇研究综述了一系列针对包含大量凸组件函数的最小化求和问题的方法,这些方法通常采用单个组件的迭代,并分析了这些方法的收敛性和收敛速度。 此外,作者还探讨了这些方法在推理 / 机器学习、信号处理和大规模 / 分布式优化等方面的应用。
Jul, 2015
通过分析,我们展示了对于凸问题,自适应的近端梯度方法不受传统的 Lipschitzian 假设的限制。我们的分析揭示了一类无需线搜索的方法仍然在纯粹的局部 Hölder 梯度连续性下收敛,特别是连续可微分的半代数函数。为了解决局部 Lipschitz 连续性的缺失,流行的方法围绕着 ε- 预测器和 / 或线搜索程序。相反,我们利用 Hölder 不等式,而不需要任何近似,同时保持自适应方案的无需线搜索的特性。此外,我们在先验地不了解局部 Hölder 常数和 Hölder 连续性的阶的情况下,证明了完全序列的收敛性。在数值实验中,我们将其与基准方法在涵盖局部和全局 Hölder 设置的各种机器学习任务中进行比较。
Feb, 2024
研究证明了随机梯度下降法的最终迭代在各种条件下都能以最优的收敛速度收敛,包括期望和高概率收敛,在紧致域、非平滑问题和组合优化中都能适用。
Dec, 2023
本论文研究了用于函数最小化的二次逼近方法,重点考虑迭代复杂度以及该方法的充分性和必要性证明。我们证明了在实现精度范围内的非精确解决方案足以保证收敛速度与精确方案相同,本文揭示了这个在早期阶段是线性的,而总比例为 $O (1 /k)$。此外,我们还证明了此方法在一些凸问题上具有全局收敛性。
Mar, 2018
本文探讨了使用近端梯度法优化平滑凸函数和非平滑凸函数的和时,如果在计算平滑项的梯度或非平滑项的邻近算子时存在误差,基本的近端梯度法和加速近端梯度法可以实现与没有错误的情况下相同的收敛率,前提是错误以适当的速度减小。使用这些速度,在一组结构稀疏性问题上,我们的表现与精心选择的固定误差级别相当或更好。
Sep, 2011
本文探讨了凸优化中的两个基本一阶算法,梯度下降法(GD)和近端梯度法(ProxGD)。我们着重于通过利用光滑函数的局部曲率信息,使这些算法完全自适应。我们提出了基于观察到的梯度差异的 GD 和 ProxGD 的自适应版本,因此没有额外的计算成本。此外,我们证明了方法的收敛性,仅需假设梯度在局部利普希茨连续。此外,所提出的版本允许使用比 [MM20] 最初建议的更大的步长。
Aug, 2023
本文介绍了一种利用步长乘以线性误差边界的方法来实现凸函数最小化的近端梯度算法;通过证明将误差边界与一种自然二次生长条件的等价性,直观地解释了观察到的线性收敛现象;我们的方法将推广到用于最小化由光滑映射组成的非光滑函数的近端方法,同时观察到算法中的短步长暗示了接近稳定状态,建议作为可靠的终止准则。
Feb, 2016
本文提出了增量 Newton 方法和梯度增长条件,通过实例研究,发现增量 Newton 方法需要满足梯度增长条件才能达到线性收敛率,进而得到了分布式优化方法的线性收敛率结果。
Oct, 2014
提出了两个针对非凸情况的数值算法,用于快速解决优化问题。该算法基于可变度量介绍了近端项,这使得我们能够针对非凸结构优化问题构建新的近端分裂算法。在变量度量序列条件温和并且假设相关增广拉格朗日函数具有 Kurdyka-Lojasiewicz 性质的情况下,证明了该算法迭代可以收敛到 KKT 点,并获得了增广拉格朗日函数和迭代的收敛速度。
Jan, 2018