15 July 2020 in IEEE Transactions on Automatic Control
This work studies a class of non-smooth decentralized multi-agent optimization problems where the agents aim at minimizing a sum of local strongly-convex smooth components plus a common non-smooth term. We propose a general primal-dual algorithmic framework that captures many existing state-of-the-art algorithms including the adapt-then-combine gradient-tracking methods for smooth costs. We then prove linear convergence of the proposed method (to the exact minimizer) in the presence of the non-smooth term. Moreover, for the more general class of problems with agent specific non-smooth terms, we show that linear convergence cannot be achieved (in the worst case) for the class of algorithms that uses the gradients and the proximal mappings of the smooth and non-smooth parts, respectively. We further provide a numerical counterexample that shows some state-of-the-art algorithms fail to converge linearly for strongly-convex objectives and different local non-smooth terms.
21 June 2022 in IEEE Transactions on Signal Processing
We study the consensus decentralized optimization problem where the objective function is the average of $n$ agents private non-convex cost functions; moreover, the agents can only communicate to their neighbors on a given network topology. The stochastic learning setting is considered in this paper where each agent can only access a noisy estimate of its gradient. Many decentralized methods can solve such problem including EXTRA, Exact-Diffusion/D$^{2}$, and gradient-tracking. Unlike the famed Dsgd algorithm, these methods have been shown to be robust to the heterogeneity across the local cost functions. However, the established convergence rates for these methods indicate that their sensitivity to the network topology is worse than Dsgd. Such theoretical results imply that these methods can perform much worse than Dsgd over sparse networks, which, however, contradicts empirical experiments where Dsgd is observed to be more sensitive to the network topology. In this work, we study a general stochastic unified decentralized algorithm (SUDA) that includes the above methods as special cases. We establish the convergence of SUDA under both non-convex and the Polyak-Łojasiewicz condition settings. Our results provide improved network topology dependent bounds for these methods (such as Exact-Diffusion/D$^{2}$ and gradient-tracking) compared with existing literature. Moreover, our results show that these methods are often less sensitive to the network topology compared to Dsgd, which agrees with numerical experiments.
13 July 2020 in IEEE Transactions on Signal Processing
Various bias-correction methods such as EXTRA, gradient tracking methods, and exact diffusion have been proposed recently to solve distributed deterministic optimization problems. These methods employ constant step-sizes and converge linearly to the exact solution under proper conditions. However, their performance under stochastic and adaptive settings is less explored. It is still unknown whether, when and why these bias-correction methods can outperform their traditional counterparts (such as consensus and diffusion) with noisy gradient and constant step-sizes. This work studies the performance of exact diffusion under the stochastic and adaptive setting, and provides conditions under which exact diffusion has superior steady-state mean-square deviation (MSD) performance than traditional algorithms without bias-correction. In particular, it is proven that this superiority is more evident over sparsely-connected network topologies such as lines, cycles, or grids. Conditions are also provided under which exact diffusion method match or may even degrade the performance of traditional methods. Simulations are provided to validate the theoretical findings.
27 March 2019 in IEEE Transactions on Automatic Control
This paper develops an effective distributed strategy for the solution of constrained multiagent stochastic optimization problems with coupled parameters across the agents. In this formulation, each agent is influenced by only a subset of the entries of a global parameter vector or model, and is subject to convex constraints that are only known locally. Problems of this type arise in several applications, most notably in disease propagation models, minimum-cost flow problems, distributed control formulations, and distributed power system monitoring. This paper focuses on stochastic settings, where a stochastic risk function is associated with each agent and the objective is to seek the minimizer of the aggregate sum of all risks subject to a set of constraints. Agents are not aware of the statistical distribution of the data and, therefore, can only rely on stochastic approximations in their learning strategies. We derive an effective distributed learning strategy that is able to track drifts in the underlying parameter model. A detailed performance and stability analysis is carried out showing that the resulting coupled diffusion strategy converges at a linear rate to an $O(\mu)$ neighborhood of the true penalized optimizer.
17 December 2019 in IEEE Transactions on Automatic Control
This article develops a proximal primal–dual decentralized strategy for multiagent optimization problems that involve multiple coupled affine constraints, where each constraint may involve only a subset of the agents. The constraints are generally sparse, meaning that only a small subset of the agents are involved in them. This scenario arises in many applications, including decentralized control formulations, resource allocation problems, and smart grids. Traditional decentralized solutions tend to ignore the structure of the constraints and lead to degraded performance. We instead develop a decentralized solution that exploits the sparsity structure. Under constant step-size learning, the asymptotic convergence of the proposed algorithm is established in the presence of nonsmooth terms, and it occurs at a linear rate in the smooth case. We also examine how the performance of the algorithm is influenced by the sparsity of the constraints. Simulations illustrate the superior performance of the proposed strategy.
1 April 2024 in IEEE Transactions on Automatic Control
Distributed optimization methods with local updates have recently attracted a lot of attention due to their potential to reduce the communication cost of distributed methods. In these algorithms, a collection of nodes performs several local updates based on their local data, and then, they communicate with each other to exchange estimate information. While there have been many studies on distributed local methods with centralized network connections, there has been less work on decentralized networks. In this work, we propose and investigate a locally updated decentralized method called local exact-diffusion (LED). We establish the convergence of LED in both convex and nonconvex settings for the stochastic online setting. Our convergence rate improves over the rate of existing decentralized methods. When we specialize the network to the centralized case, we recover the state-of-the-art bound for centralized methods. We also link LED to several other independently studied distributed methods, including Scaffnew, FedGate, and VRL-SGD. In addition, we numerically investigate the benefits of local updates for decentralized networks and demonstrate the effectiveness of the proposed method.