In this paper we address the convergence of stochastic approximation when the
functions to be minimized are not convex and nonsmooth. We show that the
"mean-limit" approach to the convergence which leads, for smooth problems, to
the ODE approach can be adapted to the non-smooth case. The limiting dynamical
system may be shown to be, under appropriate assumption, a differential
inclusion. Our results expand earlier works in this direction by Benaim et al.
(2005) and provide a general framework for proving convergence for
unconstrained and constrained stochastic approximation problems, with either
explicit or implicit updates. In particular, our results allow us to establish
the convergence of stochastic subgradient and proximal stochastic gradient
descent algorithms arising in a large class of deep learning and
high-dimensional statistical inference with sparsity inducing penalties.

本文研究了非凸、非光滑情况下随机逼近的收敛性，提出了一种基于极限均值的收敛方法并推导了相应的微分包含形式，为证明无约束和约束随机逼近问题的收敛性提供了一般框架，尤其适合于深度学习和低维度高稀疏性统计推断中随机次梯度算法的收敛性分析。

非光滑随机逼近分析：微分包含方法

Analysis of nonsmooth stochastic approximation: the differential  inclusion approach

In 1963, Polyak proposed a simple condition that is sufficient to show a
global linear convergence rate for gradient descent. This condition is a
special case of the \L{}ojasiewicz inequality proposed in the same year, and it
does not require strong convexity (or even convexity). In this work, we show
that this much-older Polyak-\L{}ojasiewicz (PL) inequality is actually weaker
than the main conditions that have been explored to show linear convergence
rates without strong convexity over the last 25 years. We also use the PL
inequality to give new analyses of randomized and greedy coordinate descent
methods, sign-based gradient descent methods, and stochastic gradient methods
in the classic setting (with decreasing or constant step-sizes) as well as the
variance-reduced setting. We further propose a generalization that applies to
proximal-gradient methods for non-smooth optimization, leading to simple proofs
of linear convergence of these methods. Along the way, we give simple
convergence results for a wide variety of problems in machine learning: least
squares, logistic regression, boosting, resilient backpropagation,
L1-regularization, support vector machines, stochastic dual coordinate ascent,
and stochastic variance-reduced gradient methods.

介绍了一种不需要强凸性条件的梯度下降算法，并针对机器学习中的各种问题提供了新的分析方法和收敛证明。

梯度和近端梯度法在 Polyak-Łojasiewicz 条件下的线性收敛

Linear Convergence of Gradient and Proximal-Gradient Methods Under the  Polyak-Łojasiewicz Condition

We propose a new majorization-minimization (MM) method for non-smooth and
non-convex programs, which is general enough to include the existing MM
methods. Besides the local majorization condition, we only require that the
difference between the directional derivatives of the objective function and
its surrogate function vanishes when the number of iterations approaches
infinity, which is a very weak condition. So our method can use a surrogate
function that directly approximates the non-smooth objective function. In
comparison, all the existing MM methods construct the surrogate function by
approximating the smooth component of the objective function. We apply our
relaxed MM methods to the robust matrix factorization (RMF) problem with
different regularizations, where our locally majorant algorithm shows
advantages over the state-of-the-art approaches for RMF. This is the first
algorithm for RMF ensuring, without extra assumptions, that any limit point of
the iterates is a stationary point.

本文提出了一种新的主化 - 最小化（MM）方法，适用于非光滑和非凸规划，其广泛性足以涵盖现有的 MM 方法。与现有的 MM 方法相比，该方法构建替代函数的方式更优越，相应的算法在抗干扰矩阵分解问题（RMF）中得到应用，并非仅仅基于平滑部分逼近的代理函数，而是直接逼近非平滑目标函数。