Polynomial escape-time from saddle points in distributed non-convex optimization
File(s)nonconvex_camsap_v2.pdf (534.02 KB)
Accepted version
Author(s)
Vlaski, Stefan
Sayed, Ali H
Type
Conference Paper
Abstract
The diffusion strategy for distributed learning from streaming data employs local stochastic gradient updates along with exchange of iterates over neighborhoods. In this work we establish that agents cluster around a network centroid in the mean-fourth sense and proceeded to study the dynamics of this point. We establish expected descent in non-convex environments in the large-gradient regime and introduce a short-term model to examine the dynamics over finite-time horizons. Using this model, we establish that the diffusion strategy is able to escape from strict saddle-points in O(1/μ) iterations, where μ denotes the step-size; it is also able to return approximately second-order stationary points in a polynomial number of iterations. Relative to prior works on the polynomial escape from saddle-points, most of which focus on centralized perturbed or stochastic gradient descent, our approach requires less restrictive conditions on the gradient noise process.
Date Issued
2020-03-05
Date Acceptance
2019-12-01
Citation
2019 IEEE 8TH INTERNATIONAL WORKSHOP ON COMPUTATIONAL ADVANCES IN MULTI-SENSOR ADAPTIVE PROCESSING (CAMSAP 2019), 2020, pp.171-175
Publisher
IEEE
Start Page
171
End Page
175
Journal / Book Title
2019 IEEE 8TH INTERNATIONAL WORKSHOP ON COMPUTATIONAL ADVANCES IN MULTI-SENSOR ADAPTIVE PROCESSING (CAMSAP 2019)
Copyright Statement
Copyright © 2020 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://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000556233000033&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=a2bf6146997ec60c407a63945d4e92bb
Source
8th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)
Subjects
adaptation
Computer Science
Computer Science, Hardware & Architecture
DIFFUSION
diffusion learning
distributed optimization
Engineering
Engineering, Electrical & Electronic
escape time
gradient noise
NETWORKS
non-convex costs
saddle point
Science & Technology
stationary points
Stochastic optimization
Technology
Publication Status
Published
Start Date
2019-12-15
Finish Date
2019-12-18
Coverage Spatial
Guadeloupe, France