Distributed subgradient methods and quantization effects

By Angelia Nedić, Alexander Olshevsky, Asuman E. Ozdaglar, John N. Tsitsiklis. 2008

205 citations recorded by the source corpus.

We consider a convex unconstrained optimization problem that arises in a network of agents whose goal is to cooperatively optimize the sum of the individual agent objective functions through local computations and communications. For this problem, we use averaging algorithms to develop distributed subgradient methods that can operate over a time-varying topology. Our focus is on the convergence rate of these methods and the degradation in performance when only quantized information is available. Based on our recent results on the convergence time of distributed averaging algorithms, we derive improved upper bounds on the convergence rate of the unquantized subgradient method. We then propose a distributed subgradient method under the additional constraint that agents can only store and communicate quantized information, and we provide bounds on its convergence rate that highlight the dependence on the number of quantization levels.

Subfields: Artificial Intelligence, Computer Networks and Communications, Optimization & Training, Federated & Distributed Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Optimization & Training

In Federated & Distributed Learning

Citations in the corpus

Distributed Fixed Point Methods with Compressed Iterates (2019, methodology): “Among inexact methods, some provide algorithms that compute (sub)gradients at compressed iterates: [23, 24].”
Robust and Communication-Efficient Collaborative Learning (2019, methodology): “In the decentralized setting, quantization methods were proposed in different convex optimization contexts with nonvanishing errors (Yuksel and Basar, 2003; Rabbat and Nowak, 2005; Kashyap et al., 2006; El Chamie et al., 2016; Aysal et al., 2007; Nedic et al., 2008).”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, background): “It has been observed that gossip averaging can diverge (or not converge to the correct solution) in the presence of quantization noise (Xiao et al., 2005; Carli et al., 2007; Nedić et al., 2008; Dimakis et al., 2010; Carli et al., 2010b; Yuan et al., 2012).”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, methodology): “The proposed schemes in (Carli et al., 2007; Nedi´c et al., 2008; Aysal et al., 2008; Carli et al., 2010b; Yuan et al., 2012) do only converge to a neighborhood (whose size depends on the compression accuracy) of the solution.”
Improving the Privacy and Accuracy of ADMM-Based Distributed Algorithms (2018, methodology): “Existing approaches to decentralizing an optimization problem primarily consist of subgradientbased algorithms (Nedic et al., 2008; Nedic & Ozdaglar, 2009; Lobel & Ozdaglar, 2011), ADMM-based algorithms (Wei & Ozdaglar, 2012; Ling & Ribeiro, 2014; Shi et al.”
Convergence Analysis of Quantized Primal-Dual Algorithms in Network Utility Maximization Problems (2016, background): “[3] considered a convex optimization problem, in which a set of agents collaboratively minimize a sum of individual objective functions.”
Fast Convergence Rates of Distributed Subgradient Methods With Adaptive Quantization (2018, background): “In [11] and [12], the authors only show the convergence to a neighborhood around the optimal of the problem, while an exact convergence has been studied in [14]; however, a condition on the growing communication bandwidth is assumed in the latter work.”
A gossip algorithm for convex consensus optimization over networks (2010, background): “Furthermore, the algorithms mostly assume delay- and error-free communications with no quantization over directed graphs, although there are a few exceptions: [18] allowed the presence of bounded time delays, [28] considered random additive errors in subgradient evaluations, [20], [26] studied the e”
DP-ADMM: ADMM-Based Distributed Learning With Differential Privacy (2018, background): “As pointed out in recent studies [1], [2], existing approaches to decentralizing an optimization problem mainly consist of subgradient-based algorithms [3], [4], alternating direction method of multipliers (ADMM) based algorithms [5]–[8], and composite of sub-gradient descent and ADMM [9].”
Quantized consensus ADMM for multi-agent distributed optimization (2015, background): “Anotherexample is the large scale machine learning where a computation task may be executed by collaborative microprocessors with individual memories and storage spaces 2 [6], [7].”
Distributed dual averaging method for multi-agent optimization with quantized communication (2012, methodology): “However, to the best of our knowledge, only the authors in [5] have considered the quantization effects on the multi-agent optimization problem; their proposed method is different from ours.”