Timezone: »

 
Poster
Second Order Optimality in Decentralized Non-Convex Optimization via Perturbed Gradient Tracking
Isidoros Tziotis · Constantine Caramanis · Aryan Mokhtari

Wed Dec 09 09:00 AM -- 11:00 AM (PST) @ Poster Session 3 #1133
in Poster Session 4 »

In this paper we study the problem of escaping from saddle points and achieving second-order optimality in a decentralized setting where a group of agents collaborate to minimize their aggregate objective function. We provide a non-asymptotic (finite-time) analysis and show that by following the idea of perturbed gradient descent, it is possible to converge to a second-order stationary point in a number of iterations which depends linearly on dimension and polynomially on the accuracy of second-order stationary point. Doing this in a communication-efficient manner requires overcoming several challenges, from identifying (first order) stationary points in a distributed manner, to adapting the perturbed gradient framework without prohibitive communication complexity. Our proposed Perturbed Decentralized Gradient Tracking (PDGT) method consists of two major stages: (i) a gradient-based step to find a first-order stationary point and (ii) a perturbed gradient descent step to escape from a first-order stationary point, if it is a saddle point with sufficient curvature. As a side benefit of our result, in the case that all saddle points are non-degenerate (strict), the proposed PDGT method finds a local minimum of the considered decentralized optimization problem in a finite number of iterations.

Keywords: Applications · Generative Models; Probabilistic Methods · Applications -> Computer Vision; Deep Learning -> Deep Autoencoders; Deep Learning

Author Information

Isidoros Tziotis (UT Austin)
Constantine Caramanis (UT Austin)
Aryan Mokhtari (UT Austin)

More from the Same Authors