Perturbed Iterate SGD for Lipschitz Continuous Loss Functions

DOI10.1007/S10957-022-02093-0arXiv2003.07606MaRDI QIDQ6336888

Akiko Takeda, Michael R. Metel

Publication date: 17 March 2020

Abstract: This paper presents an extension of stochastic gradient descent for the minimization of Lipschitz continuous loss functions. Our motivation is for use in non-smooth non-convex stochastic optimization problems, which are frequently encountered in applications such as machine learning. Using the Clarke $epsilon$-subdifferential, we prove the non-asymptotic convergence to an approximate stationary point in expectation for the proposed method. From this result, a method with non-asymptotic convergence with high probability, as well as a method with asymptotic convergence to a Clarke stationary point almost surely are developed. Our results hold under the assumption that the stochastic loss function is a Carath'eodory function which is almost everywhere Lipschitz continuous in the decision variables. To the best of our knowledge this is the first non-asymptotic convergence analysis under these minimal assumptions.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonconvex programming, global optimization (90C26) Stochastic programming (90C15) Stochastic approximation (62L20)

This page was built for publication: Perturbed Iterate SGD for Lipschitz Continuous Loss Functions