Analysis of nonsmooth stochastic approximation: the differential inclusion approach

Abstract

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.

References in corpus (3)

• On the ergodicity properties of some adaptive MCMC algorithms
• Variance Reduction for Faster Non-Convex Optimization
• On the ergodicity of the adaptive Metropolis algorithm on unbounded domains

Cited by in corpus (12)

• Unbalanced minibatch Optimal Transport; applications to Domain Adaptation
• Minibatch optimal transport distances; analysis and applications
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions
• On Correctness of Automatic Differentiation for Non-Differentiable Functions
• Simple Stochastic Gradient Methods for Non-Smooth Non-Convex Regularized Optimization
• Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex Functions?
• Stochastic proximal subgradient descent oscillates in the vicinity of its accumulation set
• Oracle Complexity in Nonsmooth Nonconvex Optimization
• Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning
• A Stochastic Subgradient Method for Distributionally Robust Non-Convex Learning
• Asynchronous Optimization Methods for Efficient Training of Deep Neural Networks with Guarantees
• Stochastic Subgradient Descent on a Generic Definable Function Converges to a Minimizer