Analysis of nonsmooth stochastic approximation: the differential inclusion approach

By Szymon Majewski, Blazej Miasojedow, Eric Moulines. 2018

52 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/631776e0b393aee32181908521cd0e49c942ae0d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Stochastic Subgradient Method Converges on Tame Functions (2018, background): “2 Concurrent to this work, the independent preprint [29] also provides convergence guarantees for the stochastic projected subgradient method, under the assumption that the objective function is “subdifferentially regular” and the constraint set is convex.”