随机次梯度法在弱凸函数上以 $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 projected 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})$.