Dec, 2017

非 Lipschitz 连续情况下的确定性与随机次梯度方法的收敛速度

PDF
TL;DR通过对 Shor 子梯度分析的推广，我们将子梯度方法的经典收敛速度理论扩展到可适用于非 Lipschitz 函数。我们证明了在任何具有局部 Lipschitz 性的凸函数中，确定性投影子梯度算法的全局 O（1/√T）收敛速度。我们还表明，对于具有最多二次增长的凸函数，随机投影子梯度方法的收敛速度为 O（1/√T），在强凸性或较弱的二次下限条件下，该速度可进一步提高至 O (1/T)。
subgradient methodsconvergence rate theorydeterministic projected subgradient methodstochastic projected subgradient methodquadratic growth
发现论文，激发创造
  • 重新审视亚梯度法：超越 Lipschitz 连续性的复杂度和收敛性

    本文研究了基于次梯度方法的非光滑优化问题，针对具有凸性和弱凸性的目标函数，推导了次梯度方法的收敛性和复杂度界限，证明了步长的选取可以控制其移动轨迹，从而保证算法的收敛性。同时，还将该方法拓展到了截断型、随机型、增量型等非 Lipschitz 函数的问题上。

    May, 2023

  • 超过 Lipschitz 连续性的随机弱凸优化

    本研究考虑在没有标准 Lipschitz 连续性假设的随机弱凸优化问题中，基于新的自适应正则化（步长）策略，我们展示了一类广泛的随机算法包括随机次梯度法在具有恒定错误率的情况下保持 O (1/√K) 的收敛速率。我们的分析基于弱假设：Lipschitz 参数可以由 ||x|| 的一般增长函数界定，或通过独立随机样本进行局部估计。

    Jan, 2024

  • 随机次梯度法收敛于温顺函数

    通过研究随机子梯度方法在无光滑性和凸性情况下的收敛性，证明了在任何半代数局部 Lipschitz 函数中，随机子梯度方法产生的极限点都是一阶稳定的，特别地，这项工作为随机子梯度方法及其近端扩展在数据科学中应用的各种问题，包括所有流行的深度学习框架，提供了严格的收敛性保证。

    Apr, 2018

  • 针对最小化复合非凸、非光滑和非 Lipschitz 函数的次梯度方法的统一分析

    本文提出了一种用于解决非凸、非光滑优化问题的近端次梯度方法（Prox-SubGrad），并通过建立一些子梯度上界及其关系，简化和统一了收敛速度的证明方案，同时还提出了一些新的随机子梯度上界条件，并为随机子梯度方法（Sto-SubGrad）建立了收敛和迭代复杂度。

    Aug, 2023

  • 随机次梯度法在弱凸函数上以 $O (k^{-1/4})$ 收敛

    本文证明了应用于弱凸问题的近端随机亚梯度法能将 Moreau 包络的梯度速率推向零点，因此我们实现了关于最小化光滑非凸函数和凸可靠函数之和的近端随机梯度下降法的收敛速率的一个开放性问题。

    Feb, 2018

  • 利用局部增长条件加速随机子梯度方法

    本文提出了一种新的局部增长速度理论，通过采用两种不同的加速随机次梯度下降方法解决了 随机凸优 程序，在不知道增长常数和增长率 θ 的情况下，证明了算法比传统随机次梯度下降法具有更快的全局收敛速度。

    Jul, 2016

  • MixedGrad: 一种 O (1/T) 收敛率算法用于随机平滑优化

    本文将提出一种新的混合优化方法用于平滑函数优化的同时，考虑了随机预测和完整梯度的优化，通过最多使用 O (lnT) 次完整梯度 oracle 和 O (T) 次随机 oracle，可以实现 O (1/T) 的优化误差。

    Jul, 2013

  • 非光滑随机梯度下降的严格分析

    使用随机梯度下降来最小化 Lipschitz 函数和强凸函数但不一定可微的问题，证明了在 T 步随机梯度下降后，最终迭代的误差高概率为 O (log (T)/T)；同时构造了一个函数，证明了在确定性梯度下降中，最终迭代的误差为 Ω(log (T)/T)；然后证明了在采用后缀平均法的情形下，它的高概率误差界是优化函数相关类别中的最优界（O (1/T)）；最后证明了对于 Lipschitz 和凸函数 class，使用随机梯度下降解决此问题后，最终迭代的误差高概率为 O (log (T)/sqrt (T))

    Dec, 2018

  • 随机梯度下降法在非凸目标函数中的收敛速率

    本文研究了随机梯度下降法在非全局凸函数的情况下，实现局部收敛和收敛速率的估计，尤其适用于机器学习中的简单目标函数。

    Apr, 2019

  • 非强凸平稳随机逼近，收敛速率 O (1/n)

    本篇论文研究了关于随机逼近问题的现有算法，提出了两种新型随机梯度算法，并在回归和逻辑分类两种经典的监督学习问题上进行了测试，得到了较好的优化效果。

    Jun, 2013