skip to main content
Language:
Search Limited to: Search Limited to: Resource type Show Results with: Show Results with: Search type Index

Convergence of constant step stochastic gradient descent for non-smooth non-convex functions

Set-valued and variational analysis, 2022-09, Vol.30 (3), p.1117-1147 [Peer Reviewed Journal]

Distributed under a Creative Commons Attribution 4.0 International License ;ISSN: 1877-0533 ;EISSN: 1877-0541 ;DOI: 10.1007/s11228-022-00638-z

Digital Resources/Online E-Resources

Citations Cited by
  • Title:
    Convergence of constant step stochastic gradient descent for non-smooth non-convex functions
  • Author: Bianchi, Pascal ; Hachem, Walid ; Schechtman, Sholom
  • Subjects: Mathematics ; Numerical Analysis ; Optimization and Control
  • Is Part Of: Set-valued and variational analysis, 2022-09, Vol.30 (3), p.1117-1147
  • Description: This paper studies the asymptotic behavior of the constant step Stochastic Gradient Descent for the minimization of an unknown function F , defined as the expectation of a non convex, non smooth, locally Lipschitz random function. As the gradient may not exist, it is replaced by a certain operator: a reasonable choice is to use an element of the Clarke subdifferential of the random function; an other choice is the output of the celebrated backpropagation algorithm, which is popular amongst practionners, and whose properties have recently been studied by Bolte and Pauwels [7]. Since the expectation of the chosen operator is not in general an element of the Clarke subdifferential BF of the mean function, it has been assumed in the literature that an oracle of BF is available. As a first result, it is shown in this paper that such an oracle is not needed for almost all initialization points of the algorithm. Next, in the small step size regime, it is shown that the interpolated trajectory of the algorithm converges in probability (in the compact convergence sense) towards the set of solutions of the differential inclusion. Finally, viewing the iterates as a Markov chain whose transition kernel is indexed by the step size, it is shown that the invariant distribution of the kernel converge weakly to the set of invariant distribution of this differential inclusion as the step size tends to zero. These results show that when the step size is small, with large probability, the iterates eventually lie in a neighborhood of the critical points of the mean function F .
  • Publisher: Springer
  • Language: English
  • Identifier: ISSN: 1877-0533
    EISSN: 1877-0541
    DOI: 10.1007/s11228-022-00638-z
  • Source: Hyper Article en Ligne (HAL) (Open Access)
Back to results list
INSPIRE LIBRARY - TON DUC THANG UNIVERSITY (84-028) 37 755 057 Feedback
19 Nguyen Huu Tho St. Dist.7, HCM thuvien@tdtu.edu.vn

Copyright © 2017 INSPIRE LIBRARY - TON DUC THANG UNIVERSITY

Searching Remote Databases, Please Wait