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

Feb, 2018

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

Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions

Damek Davis, Dmitriy Drusvyatskiy

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

Abstract

We prove that the proximal stochastic subgradient method, applied to a weakly convex problem, drives the gradient of the moreau envelope to zero at the rate $O(k^{-1/4})$. As a consequence, we resolve an open que

proximal stochastic subgradient method moreau envelope weakly convex problem convergence rate smooth nonconvex function

发现论文，激发创造

基于随机模型的弱凸函数最小化

本文提出一族算法通过简单的随机模型样本和优化方法，成功的减少了目标函数。我们展示出，合理的近似质量和模型的正则性下，此类算法将自然的稳定度衡量推向 0，该衰减速度为 O (k^(-1/4))，基于此原理，我们为随机的近端子梯度法，近端次梯度法以及规则化的高斯牛顿法等提供了第一个复杂性保证。

Mar, 2018

重新审视亚梯度法：超越 Lipschitz 连续性的复杂度和收敛性

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

May, 2023

随机近端梯度算法的收敛性

本文基于凸优化中函数是光滑和非光滑组合的形式，证明了一种适用于大类凸优化问题的随机近端梯度算法收敛性质，其避免了平均化和理论研究中常见但实际中不一定满足的有界性假设，证明了一系列强、弱收敛性结果，并得到了期望意义下的 $O (1/n)$ 的有界性结果。

Mar, 2014

非光滑、非凸问题的近距离引导随机次梯度方法

本文介绍了一种基于随机投影次梯度方法的弱凸（即均匀逼近正则）非光滑非凸函数的算法，并通过简单证明证明这种方法与用于光滑非凸问题的随机梯度方法具有相同的收敛速度；这似乎是第一个针对弱凸函数类的随机次（或确定性）梯度法的收敛速度分析。

Jul, 2017

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

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

Aug, 2023

复合凸极小化的近端梯度法的最恶情况收敛速率

本文研究了求解由平滑强凸函数和可得到其 Proximal 算子的非光滑凸函数组成的函数和的最优收敛速度，并利用半定规划等工具，建立了 Proximal 梯度算法的准确最坏情况收敛速度，同时提出可将强凸性等条件放宽以保证相应的收敛速度，得到了三种性能度量的同一步长最优的证明。

May, 2017

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

通过对 Shor 子梯度分析的推广，我们将子梯度方法的经典收敛速度理论扩展到可适用于非 Lipschitz 函数。我们证明了在任何具有局部 Lipschitz 性的凸函数中，确定性投影子梯度算法的全局 O（1/√T）收敛速度。我们还表明，对于具有最多二次增长的凸函数，随机投影子梯度方法的收敛速度为 O（1/√T），在强凸性或较弱的二次下限条件下，该速度可进一步提高至 O (1/T)。

Dec, 2017

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

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

Jun, 2013

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

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

Jan, 2024

Polyak 学习率的随机梯度下降

本文提出将 Subgradient 方法中的 Polyak 步长推广到随机梯度下降中，并证明了该算法可以在非渐进情况下以更好的速率收敛于优化解，该算法在训练深度神经网络等问题上表现良好。

Mar, 2019