Search

Gradient tracking (GT) is an algorithm designed for solving decentralized optimization problems over a network (such as training a machine learning model). A key feature of GT is a tracking mechanism that allows us to overcome data heterogeneity between nodes. We develop a novel decentralized tracking mechanism, K-GT, which enables communication-efficient local updates in GT while inheriting the data-independence property of GT. We prove a convergence rate for K-GT on smooth non-convex functions and prove that it reduces the communication overhead asymptotically by a linear factor K, where K denotes the number of local steps. We illustrate the robustness and effectiveness of this heterogeneity correction on convex and non-convex benchmark problems and a non-convex neural network training task with the MNIST dataset. [ABSTRACT FROM AUTHOR]

Chemotaxis is a directed cell movement in response to external chemical stimuli. In this paper, we propose a simple model for the origin of chemotaxis – namely how a directed movement in response to an external chemical signal may occur based on purely reaction–diffusion equations reflecting inner working of the cells. The model is inspired by the well-studied role of the rho-GTPase Cdc42 regulator of cell polarity, in particular in yeast cells. We analyse several versions of the model to better understand its analytic properties and prove global regularity in one and two dimensions. Using computer simulations, we demonstrate that in the framework of this model, at least in certain parameter regimes, the speed of the directed movement appears to be proportional to the size of the gradient of signalling chemical. This coincides with the form of the chemical drift in the most studied mean field model of chemotaxis, the Keller–Segel equation. [ABSTRACT FROM AUTHOR]

In this paper, we study the distributed optimization problem for a system of agents embedded in time-varying directed communication networks. Each agent has its own cost function and agents cooperate to determine the global decision that minimizes the summation of all individual cost functions. We consider the so-called push-pull gradient-based algorithm (termed as AB/Push-Pull) which employs both row- and column-stochastic weights simultaneously to track the optimal decision and the gradient of the global cost while ensuring consensus and optimality. We show that the algorithm converges linearly to the optimal solution over a time-varying directed network for a constant stepsize when the agent's cost function is smooth and strongly convex. The linear convergence of the method has been shown in [F. Saadatniaki, R. Xin, and U.A. Khan, Decentralized optimization over time-varying directed graphs with row and column-stochastic matrices, IEEE Trans. Autom. Control 65(11) (2020), pp. 4769–4780], where the multi-step consensus contraction parameters for row- and column-stochastic mixing matrices are not directly related to the underlying graph structure, and the explicit range for the stepsize value is not provided. With respect to [F. Saadatniaki, R. Xin, and U.A. Khan, Decentralized optimization over time-varying directed graphs with row and column-stochastic matrices, IEEE Trans. Autom. Control 65(11) (2020), pp. 4769–4780], the novelty of this work is twofold: (1) we establish the one-step consensus contraction for both row- and column-stochastic mixing matrices with the contraction parameters given explicitly in terms of the graph diameter and other graph properties; and (2) we provide explicit upper bounds for the stepsize value in terms of the properties of the cost functions, the mixing matrices, and the graph connectivity structure. [ABSTRACT FROM AUTHOR]

This paper considers the decentralized convex optimization problem, which has a wide range of applications in large-scale machine learning, sensor networks, and control theory. We propose novel algorithms that achieve optimal computation complexity and near optimal communication complexity. Our theoretical results give affirmative answers to the open problem on whether there exists an algorithm that can achieve a communication complexity (nearly) matching the lower bound depending on the global condition number instead of the local one. Furthermore, the linear convergence of our algorithms only depends on the strong convexity of global objective and it does not require the local functions to be convex. The design of our methods relies on a novel integration of well-known techniques including Nesterov's acceleration, multi-consensus and gradient-tracking. Empirical studies show the outperformance of our methods for machine learning applications. [ABSTRACT FROM AUTHOR]

In this paper, we consider distributed quantile regression over a decentralized network, which is an example of a popularly used non-smooth statistical model. Somewhat different from the viewpoint of the optimization literature, we jointly consider numerical convergence and statistical convergence when the objective function is the loss function constructed from i.i.d. data, and the convergence to the true population parameter (instead of the minimizer of the empirical risk) is emphasized. Distributed sub-gradient methods with and without gradient tracking are considered, with an emphasis on the former. With gradient tracking, the estimate linearly converges to the true parameter up to the statistical precision based on all data, when the local sample size is sufficiently large. The distinction of our result compared to the existing optimization literature is that linear convergence can be established despite the fact that the function is not strongly convex. Numerical illustrations are given to compare with distributed descent algorithm without gradient tracking, and compare the ATC (adapt-then-combine) version with the non-ATC one. • Establish linear convergence of decentralized estimation for nonsmooth quantile regression. • Several variants of decentralized gradients methods are compared. • Numerical demonstrate the performance in comparison with ADMM approach. [ABSTRACT FROM AUTHOR]

Emerging distributed applications recently boosted the development of decentralized machine learning, especially in IoT and edge computing fields. In real-world scenarios, the common problems of non-convexity and data heterogeneity result in inefficiency, performance degradation, and development stagnation. The bulk of studies concentrate on one of the issues mentioned above without having a more general framework that has been proven optimal. To this end, we propose a unified paradigm called UMP, which comprises two algorithms D-SUM and GT-DSUM based on the momentum technique with decentralized stochastic gradient descent (SGD). The former provides a convergence guarantee for general non-convex objectives, while the latter is extended by introducing gradient tracking, which estimates the global optimization direction to mitigate data heterogeneity (i.e. , distribution drift). We can cover most momentum-based variants based on the classical heavy ball or Nesterov's acceleration with different parameters in UMP. In theory, we rigorously provide the convergence analysis of these two approaches for non-convex objectives and conduct extensive experiments, demonstrating a significant improvement in model accuracy up to 57.6% compared to other methods in practice. [ABSTRACT FROM AUTHOR]

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]

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]

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]

This article considers a problem of solving the optimal solution of the sum of locally convex cost functions over an undirected network. Each local convex cost function in the network is accessed only by each unit. To be able to reduce the amount of computation and get the desired result in an accelerated way, we put forward a fresh accelerated decentralized event-triggered algorithm, named as A-DETA, for the optimization problem. A-DETA combines gradient tracking and two momentum accelerated terms, adopts nonuniform step-sizes and emphasizes that each unit interacts with neighboring units independently only at the sampling time triggered by the event. On the premise of assuming the smoothness and strong convexity of the cost function, it is proved that A-DETA can obtain the exact optimal solution linearly in the event of sufficiently small positive step-size and momentum coefficient. Moreover, an explicit linear convergence speed is definitely shown. Finally, extensive simulation example validates the usability of A-DETA. [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]

There is growing interest in large-scale machine learning and optimization over decentralized networks, e.g. in the context of multi-agent learning and federated learning. Due to the imminent need to alleviate the communication burden, the investigation of communication- efficient distributed optimization algorithms -- particularly for empirical risk minimization -- has flourished in recent years. A large fraction of these algorithms have been developed for the master/slave setting, relying on the presence of a central parameter server that can communicate with all agents. This paper focuses on distributed optimization over networks, or decentralized optimization, where each agent is only allowed to aggregate information from its neighbors over a network (namely, no centralized coordination is present). By properly adjusting the global gradient estimate via local averaging in conjunction with proper correction, we develop a communication-efficient approximate Newton-type method, called Network-DANE, which generalizes DANE to accommodate decentralized scenarios. Our key ideas can be applied, in a systematic manner, to obtain decentralized versions of other master/slave distributed algorithms. A notable development is Network-SVRG/SARAH, which employs variance reduction at each agent to further accelerate local computation. We establish linear convergence of Network-DANE and Network-SVRG for strongly convex losses, and Network-SARAH for quadratic losses, which shed light on the impacts of data homogeneity, network connectivity, and local averaging upon the rate of convergence. We further extend Network-DANE to composite optimization by allowing a nonsmooth penalty term. Numerical evidence is provided to demonstrate the appealing performance of our algorithms over competitive baselines, in terms of both communication and computation efficiency. Our work suggests that by performing a judiciously chosen amount of local communication and computation per iteration, the overall efficiency can be substantially improved. [ABSTRACT FROM AUTHOR]

Privacy protection has become an increasingly pressing requirement in distributed optimization. However, equipping distributed optimization with differential privacy, the state-of-the-art privacy protection mechanism, will unavoidably compromise optimization accuracy. In this paper, we propose an algorithm to achieve rigorous ϵ -differential privacy in gradient-tracking based distributed optimization with enhanced optimization accuracy. More specifically, to suppress the influence of differential-privacy noise, we propose a new robust gradient-tracking based distributed optimization algorithm that allows both stepsize and the variance of injected noise to vary with time. Then, we establish a new analyzing approach that can characterize the convergence of the gradient-tracking based algorithm under both constant and time-varying stepsizes. To our knowledge, this is the first analyzing framework that can treat gradient-tracking based distributed optimization under both constant and time-varying stepsizes in a unified manner. More importantly, the new analyzing approach gives a much less conservative analytical bound on the stepsize compared with existing proof techniques for gradient-tracking based distributed optimization. We also theoretically characterize the influence of differential-privacy design on the accuracy of distributed optimization, which reveals that inter-agent interaction has a significant impact on the final optimization accuracy. Numerical simulation results confirm the theoretical predictions. [ABSTRACT FROM AUTHOR]

The problem of homing a mobile robot to a given reference location under unknown relative and absolute positions is addressed in this paper. This problem is easy to solve when all the positions and kinematic variables are known or are observable, but remains a challenge when only range is measured. Its complexity further increases when variable and unknown drifts are added to the motion, which is typical for marine vehicles. Based on the range measurements, it is possible to drive the robot arbitrarily close to the reference. This paper presents a complete solution and demonstrates the validity of the approach based on the Lyapunov theory. The use of models, which are often affected by uncertainties and/or unmodeled terms, is intended to be minimal and only some constraints are imposed on the speed of the robot. We derive a control law that makes the robot converge asymptotically to the reference and prove its stability theoretically. Nevertheless, as it is well known, practical limitations on the actuation can weaken some properties of convergence, namely when the system dynamics require increasing actuation along the approach trajectory. We will demonstrate that the robot reaches a positively invariant set around the reference whose upper bound is determined. Finally, we conclude our work by presenting simulation and experimental data and by demonstrating the validity and the robustness of the method. [ABSTRACT FROM AUTHOR]