Second-order guarantees of stochastic gradient descent in non-convex optimization
File(s)
Accepted version
Author(s)
Vlaski, Stefan
Sayed, Ali H
Type
Journal Article
Abstract
Recent years have seen increased interest in performance guarantees of gradient descent algorithms for non-convex optimization. A number of works have uncovered that gradient noise plays a critical role in the ability of gradient descent recursions to efficiently escape saddle-points and reach second-order stationary points. Most available works limit the gradient noise component to be bounded with probability one or sub-Gaussian and leverage concentration inequalities to arrive at high-probability results. We present an alternate approach, relying primarily on mean-square arguments and show that a more relaxed relative bound on the gradient noise variance is sufficient to ensure efficient escape from saddle-points without the need to inject additional noise, employ alternating step-sizes or rely on a global dispersive noise assumption, as long as a gradient noise component is present in a descent direction for every saddle-point.
Date Issued
2022-12-01
Date Acceptance
2021-12-01
Citation
IEEE Transactions on Automatic Control, 2022, 67 (12), pp.6489-6504
ISSN
0018-9286
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Start Page
6489
End Page
6504
Journal / Book Title
IEEE Transactions on Automatic Control
Volume
67
Issue
12
Copyright Statement
© 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Identifier
https://ieeexplore.ieee.org/document/9632425
Publication Status
Published
Date Publish Online
2021-12-01