Second-Order Optimality in Non-Convex Decentralized Optimization via Perturbed Gradient Tracking
Second-Order Optimality in Non-Convex Decentralized Optimization via Perturbed Gradient Tracking
复制标题
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Isidoros Tziotis;C. Caramanis;Aryan Mokhtari
中科院分区：
文献类型：
--
作者：
Isidoros Tziotis;C. Caramanis;Aryan Mokhtari
在这篇文章中，我们研究了在分散的环境下，一组智能体合作最小化他们的总目标函数的情况下摆脱鞍点并实现二阶最优的问题。我们给出了一个非渐近(有限时间)分析，并证明了遵循摄动梯度下降的思想，可以在若干次迭代中收敛到一个二阶驻点，该迭代线性地依赖于维度，并以多项式的方式依赖于二阶驻点的精度。要以通信高效的方式做到这一点，需要克服几个挑战，从以分布式方式识别(一阶)平稳点，到在没有令人望而却步的通信复杂性的情况下适应扰动的梯度框架。我们提出的扰动分散梯度跟踪(PDGT)方法包括两个主要阶段：(I)基于梯度的一阶平稳点的寻找步骤和(Ii)一阶平稳点的扰动梯度下降步骤，如果一阶平稳点是具有足够曲率的鞍点，则扰动梯度下降步骤。作为我们结果的另一个好处，在所有鞍点都是非退化(严格)的情况下，所提出的PDGT方法在有限次迭代中找到所考虑的分散优化问题的局部最小值。
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 gradientbased 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.