ESCAPING STRICT SADDLE POINTS OF THE MOREAU ENVELOPE IN NONSMOOTH OPTIMIZATION
ESCAPING STRICT SADDLE POINTS OF THE MOREAU ENVELOPE IN NONSMOOTH OPTIMIZATION
复制标题
DOI：
10.1137/21m1430868
复制
发表时间：
2022-01-01
影响因子：
3.1
通讯作者：
Drusvyatskiy, Dmitriy
中科院分区：
文献类型：
--
作者：
Davis, Damek;Diaz, Mateo;Drusvyatskiy, Dmitriy
最近的工作表明，随机摄动梯度法可以有效地避开光滑函数的严格鞍点。通过分析应用于Moreau包络的随机扰动梯度法的不精确模拟，我们将这一工作扩展到非光滑优化。主要结论是，各种非光滑优化算法都能以受控的速度避开Moreau包络的严格鞍点。主要的技术见解是，许多应用于近似子问题的算法产生的方向近似于Moreau包络的梯度。
Recent work has shown that stochastically perturbed gradient methods can efficiently escape strict saddle points of smooth functions. We extend this body of work to nonsmooth optimization, by analyzing an inexact analogue of a stochastically perturbed gradient method applied to the Moreau envelope. The main conclusion is that a variety of algorithms for nonsmooth optimization can escape strict saddle points of the Moreau envelope at a controlled rate. The main technical insight is that many algorithms applied to the proximal subproblem yield directions that approximate the gradient of the Moreau envelope.