Perturbed Iterate SGD for Lipschitz Continuous Loss Functions

Michael R. Metel () and Akiko Takeda ()
Additional contact information
Michael R. Metel: Huawei Noah’s Ark Lab
Akiko Takeda: The University of Tokyo

Journal of Optimization Theory and Applications, 2022, vol. 195, issue 2, No 6, 504-547

Abstract: 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éodory 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.

Keywords: Stochastic optimization; Lipschitz continuity; First-order method; Non-asymptotic convergence; 62L20; 68Q25; 90C15; 90C26 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-022-02093-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:195:y:2022:i:2:d:10.1007_s10957-022-02093-0

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-022-02093-0

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().