Search

This paper studies a distributed aggregative optimization problem over a directed graph with the row-stochastic weighted matrix. Different from the existing work on distributed optimization, the local cost function of each agent depends both on its local decision variable and on the sum of all functions formed by the decision variables of all agents. Inspired by the distributed dynamic average consensus protocol, heavy-ball strategy, and Nesterov gradient descent method, a momentum-based distributed gradient tracking algorithm with a fixed step size is proposed to solve such a problem. Further, it is shown that the proposed algorithm has a linear convergence rate if the global cost function is strongly convex with the Lipschitz-continuous gradient. The upper bounds of the fixed step size and the momentum parameter are restricted by a sufficiently small positive constant, respectively. Finally, a numerical example is provided to verify the effectiveness of the findings. [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]

In this article, we concentrate on dealing with the distributed optimization problem over a directed network, where each unit possesses its own convex cost function and the principal target is to minimize a global cost function (formulated by the average of all local cost functions) while obeying the network connectivity structure. Most of the existing methods, such as push-sum strategy, have eliminated the unbalancedness induced by the directed network via utilizing column-stochastic weights, which may be infeasible if the distributed implementation requires each unit to gain access to (at least) its out-degree information. In contrast, to be suitable for the directed networks with row-stochastic weights, we propose a new directed distributed Nesterov-like gradient tracking algorithm, named as D-DNGT, that incorporates the gradient tracking into the distributed Nesterov method with momentum terms and employs nonuniform step-sizes. D-DNGT extends a number of outstanding consensus algorithms over strongly connected directed networks. The implementation of D-DNGT is straightforward if each unit locally chooses a suitable step-size and privately regulates the weights on information that acquires from in-neighbors. If the largest step-size and the maximum momentum coefficient are positive and small sufficiently, we can prove that D-DNGT converges linearly to the optimal solution provided that the cost functions are smooth and strongly convex. We provide numerical experiments to confirm the findings in this article and contrast D-DNGT with recently proposed distributed optimization approaches. [ABSTRACT FROM AUTHOR]