Search

We study distributed multiagent optimization over graphs. We consider the minimization of F + G subject to convex constraints, where F is the smooth strongly convex sum of the agent's losses and G is a nonsmooth convex function. We build on the SONATA algorithm: the algorithm employs the use of surrogate objective functions in the agents' subproblems (thus going beyond linearization, such as proximal-gradient) coupled with a perturbed consensus mechanism that aims to locally track the gradient of F. SONATA achieves precision ε > 0 on the objective value in O(Κg log (1/ε)) gradient computations at each node and O(Κ9(1 -- ρ)-1/2 log (1/&#949)) communication steps, where Κg is the condition number of F and ρ characterizes the connectivity of the network. This is the first linear rate result for distributed composite optimization; it also improves on existing (nonaccelerated) schemes just minimizing F, whose rate depends on much larger quantities than Κg. When the loss functions of the agents are similar, due to statistical data similarity or otherwise, SONATA employing high-order surrogates achieves precision ε > O((β/µ) log (1/ε)) iterations and O((β/µ)(1 -- ρ)-1/2 log (1ε)) communication steps, where β measures the degree of similarity of agents' losses and µ is the strong convexity constant of F. Therefore, when β/µ < Κg, the use of high-order surrogates yields provably faster rates than those achievable by first-order models; this is without exchanging any Hessian matrix over the network. [ABSTRACT FROM AUTHOR]

This paper considers decentralized minimization of N := nm smooth nonconvex cost functions equally divided over a directed network of n nodes. Specifically, we describe a stochastic first-order gradient method, called GT-SARAH, that employs a SARAH-type variance reduction technique and gradient tracking (GT) to address the stochastic and decentralized nature of the problem. We show that GT-SARAH, with appropriate algorithmic parameters, finds an ϵ-accurate first-order stationary point with O(max{N1/2, n(1 - λ)-2, n2/3m1/3(1 - λ)-1} Lϵ-2 gradient complexity, where (1 λ) ∈ (0, 1] is the spectral gap of the network weight matrix and L is the smoothness parameter of the cost functions. This gradient complexity outperforms that of the existing decentralized stochastic gradient methods. In particular, in a big-data regime such that n = O(N1/2(1 - λ)³), this gradient complexity furthers reduces to O(N1/2Lϵ-2), independent of the network topology, and matches that of the centralized near-optimal variance-reduced methods. Moreover, in this regime GT-SARAH achieves a nonasymptotic linear speedup in that the total number of gradient computations at each node is reduced by a factor of 1/n compared to the centralized near-optimal algorithms that perform all gradient computations at a single node. To the best of our knowledge, GT-SARAH is the first algorithm that achieves this property. In addition, we show that appropriate choices of local minibatch size balance the trade-offs between the gradient and communication complexity of GT-SARAH. Over infinite time horizon, we establish that all nodes in GT-SARAH asymptotically achieve consensus and converge to a first-order stationary point in the almost sure and mean-squared sense. [ABSTRACT FROM AUTHOR]

We consider distributed smooth nonconvex unconstrained optimization over networks, modeled as a connected graph. We examine the behavior of distributed gradient-based algorithms near strict saddle points. Specifically, we establish that (i) the renowned distributed gradient descent algorithm likely converges to a neighborhood of a second-order stationary (SoS) solution; and (ii) the more recent class of distributed algorithms based on gradient tracking--implementable also over digraphs-likely converges to exact SoS solutions, thus avoiding (strict) saddle points. Furthermore, new convergence rate results for first-order critical points is established for the latter class of algorithms. [ABSTRACT FROM AUTHOR]