Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling

John DuchiAlekh AgarwalMartin Wainwright

article2010IEEE Transactions on Automatic Control1,326 citationsBest Paper Award

Develops distributed dual averaging algorithms for decentralized convex optimization, providing sharp convergence rates that explicitly decouple algorithmic progress from network topology via the graph spectral gap.

Listen

Modern large-scale engineering and data systems—ranging from wireless sensor networks to distributed machine learning clusters—frequently need to solve complex optimization problems without relying on a centralized coordinator. In these environments, individual computing nodes hold only a fraction of the overall data or cost function and can communicate solely with immediate neighbors. Prior decentralized optimization methods often suffered from theoretical convergence guarantees that degraded exponentially or polynomially with the network size, failing to show how network connectivity truly influences performance.

The article develops and evaluates a distributed dual averaging algorithm for constrained convex optimization over networks. Its primary objective is to establish sharp mathematical bounds and demonstrate empirically how convergence speed depends directly on the network size and communication topology.

The authors analyze an algorithm where each node maintains local parameter estimates, tracks a weighted running average of gradients received from neighbors, and applies a regularized projection step. The analytical framework separates standard optimization error from network communication delays using spectral graph theory and Markov chain mixing analysis. The evaluation validates these theoretical bounds through numerical simulations on distributed support vector machine classification tasks across varying network structures containing up to 900 nodes.

The analysis reveals that the number of iterations required to reach a target accuracy scales inversely with the network's spectral gap—a measure of how rapidly information diffuses across the graph. Specifically, as network size grows, well-connected expander graphs achieve target accuracy in a constant number of iterations regardless of size. In contrast, two-dimensional grid networks require iterations that scale linearly with network size, and poorly connected single-cycle networks scale quadratically. The authors prove that this inverse spectral gap scaling is tight and cannot be improved. Furthermore, the algorithm extends robustly to environments with randomized communication links, temporary network link failures, and noisy or stochastic gradient measurements.

These findings provide clear guidance for designing large-scale computational infrastructure and distributed sensor systems. Communication delays and topology structure, rather than local processing limitations, dominate convergence time. By adopting topologies with high spectral connectivity, organizations can scale processing clusters to massive node counts without sacrificing convergence speed. Conversely, deploying optimization routines over poorly connected topologies introduces severe runtime and communication bottlenecks.

System designers and engineering leaders should prioritize high-connectivity communication topologies, such as expander-like routing graphs, when deploying distributed learning and optimization frameworks. When hardware or bandwidth constraints prevent full communication at every step, practitioners can safely use randomized gossip protocols or sub-sampled communication, adjusting step sizes according to the expected network spectral gap. Future work should explore extending these dual averaging principles to non-convex objectives and broader asymmetric or directed communication networks.

The theoretical guarantees assume convex local objective functions with bounded gradients and doubly stochastic communication matrices. While the analytical and empirical results provide high confidence for convex settings, performance in highly irregular or non-convex optimization problems will require additional empirical validation.

University of California Berkeley communication constraints deterministic distributed algorithm dual averaging distributed optimization network scaling

arXiv: 1005.2012

Paper: Online Convex Programming and Generalized Infinitesimal Gradient Ascent, Martin A. Zinkevich (2003). Introduces online convex programming and basic projected gradient updates, providing foundational concepts essential for understanding dual averaging and regret-based distributed optimization.
Paper: Efficient projections onto the l1-ball for learning in high dimensions, John C. Duchi et al. (2008). Presents foundational projection and proximal operators for high-dimensional subgradient and dual methods built upon in distributed convex settings.
Paper: Logarithmic regret algorithms for online convex optimization, Elad Hazan et al. (2006). Establishes regret bounds and online optimization dynamics that underlie the convergence analysis of subgradient and dual averaging procedures.
Paper: A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers, Sahand N. Negahban et al. (2009). Provides the foundational theoretical framework for regularized convex M-estimators that dual averaging techniques aim to solve across distributed networks.

Paper: Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent, Xiangru Lian et al. (2017). Extends decentralized optimization principles over network topologies to stochastic gradient descent in deep learning, comparing communication efficiency directly against centralized baselines.
Paper: Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, John Duchi et al. (2011). Builds on subgradient methods and dual averaging concepts to introduce adaptive per-coordinate learning rates for online and stochastic optimization.
Paper: QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding, Dan Alistarh et al. (2016). Addresses network communication bottlenecks in distributed optimization by introducing quantized stochastic gradient schemes with provable convergence guarantees.
Paper: signSGD: compressed optimisation for non-convex problems, Jeremy Bernstein et al. (2018). Applies communication-efficient gradient compression techniques to distributed optimization in non-convex settings.
Paper: Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training, Yujun Lin et al. (2018). Further advances communication reduction in distributed gradient methods using extreme sparsification and momentum correction.
Paper: Federated Optimization: Distributed Machine Learning for On-Device Intelligence, Jakub Konečný et al. (2016). Generalizes distributed optimization concepts to federated learning environments characterized by high communication latency and non-IID local datasets.
Paper: Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates, Dong Yin et al. (2018). Expands distributed optimization frameworks to be resilient against adversarial and Byzantine failures during worker aggregation.
Paper: Minimizing finite sums with the stochastic average gradient, Mark Schmidt et al. (2013). Investigates variance reduction in finite-sum optimization, accelerating the convergence rates of stochastic gradient updates.
Paper: On the Convergence of FedAvg on Non-IID Data, Xiang Li et al. (2019). Analyzes the convergence behavior of distributed local averaging schemes on heterogeneous data, extending the study of network-induced consensus error.

Cover for Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling

Abstract

The goal of decentralized optimization over a network is to optimize a global objective formed by a sum of local (possibly nonsmooth) convex functions using only local computation and communication. It arises in various application domains, including distributed tracking and localization, multi-agent co-ordination, estimation in sensor networks, and large-scale optimization in machine learning. We develop and analyze distributed algorithms based on dual averaging of subgradients, and we provide sharp bounds on their convergence rates as a function of the network size and topology. Our method of analysis allows for a clear separation between the convergence of the optimization algorithm itself and the effects of communication constraints arising from the network structure. In particular, we show that the number of iterations required by our algorithm scales inversely in the spectral gap of the network. The sharpness of this prediction is confirmed both by theoretical lower bounds and simulations for various networks. Our approach includes both the cases of deterministic optimization and communication, as well as problems with stochastic optimization and/or communication.

Topics

communication constraints deterministic distributed algorithm machine learning multi-agent optimization optimization problems sensor networks stochastic optimization topology

Keywords

dual averaging distributed optimization network scaling stochastic optimization convex optimization gossip algorithms convergence analysis subgradient methods random geometric graphs

1 Introduction
2 Problem set-up and algorithm
2.1 Distributed minimization
2.2 Standard dual averaging
2.3 Distributed dual averaging
3 Main results and consequences
3.1 Convergence of distributed dual averaging
3.2 Convergence rates and network topology
3.3 Extensions to stochastic communication links
3.4 Results for stochastic gradient algorithms
4 Related Work
5 Basic convergence analysis for distributed dual averaging
5.1 Setting up the analysis
5.2 Proof of Theorem
6 Convergence rates, spectral gap, and network topology
6.1 Proof of Theorem
6.2 Proof of Corollary
6.3 Proof of Proposition
7 Convergence rates for stochastic communication
7.1 Basic convergence analysis
7.1.1 Markov chain mixing for stochastic communication
7.1.2 Proof of Theorem
7.2 Gossip-like protocols
7.2.1 Partially asynchronous gossip protocols
7.2.2 Totally asynchronous gossip protocol
7.3 Random edge inclusion and failure
8 Stochastic Gradient Optimization
8.1 Proof of Theorem
9 Simulations
10 Conclusions and Discussion
A The Dual Averaging Algorithm
A.1 Proof of Lemma
A.2 Proof of Lemma
A.3 Lipschitz continuity of projections
B Background on stochastic matrices
C Eigenvalues of paths
D Composite Objectives
References

Knowls

Knowl 1 — Distributed Dual Averaging Algorithm
algorithm
The distributed dual averaging algorithm minimizes a distributed convex objective $f(x) = \frac{1}{n} \sum_{i=1}^n f_i(x)$ over a closed convex set $\mathcal{X} \subset \mathbb{R}^d$ across an undirected network graph $G = (V, E)$ with $n = |V|$ nodes, where each node $i$ only has access to its local convex $L$ -Lipschitz function $f_i$ and can communicate only with its immediate neighbors $\mathcal{N}(i) = \{j \in V \mid (i,j) \in E\}$ .

The algorithm employs a 1-strongly convex proximal function $\psi: \mathbb{R}^d \to \mathbb{R}$ with respect to a norm $\|\cdot\|$ satisfying $\psi(x) \ge 0$ for all $x \in \mathcal{X}$ and $\psi(0) = 0$ , a non-increasing positive stepsize sequence $\{\alpha(t)\}_{t=0}^\infty$ , and a symmetric doubly stochastic weight matrix $P \in \mathbb{R}^{n \times n}$ conforming to $G$ .
Input: Convex constraint set $\mathcal{X}$ , proximal function $\psi$ , stepsize sequence $\{\alpha(t)\}_{t=0}^\infty$ , doubly stochastic matrix $P$ , iterations $T$
Initialize $z_i(1) = 0 \in \mathbb{R}^d$ for each node $i \in \{1, \ldots, n\}$
for $t = 1$ to $T$ do
    for each node $i \in \{1, \ldots, n\}$ in parallel do
        Compute subgradient $g_i(t) \in \partial f_i(x_i(t))$
        Transmit $z_i(t)$ to neighbors $j \in \mathcal{N}(i)$ and receive $z_j(t)$
         $z_i(t+1) = \sum_{j \in \mathcal{N}(i)} P_{ij} z_j(t) + g_i(t)$
         $x_i(t+1) = \operatorname{argmin}_{x \in \mathcal{X}} \left\{ \langle z_i(t+1), x \rangle + \frac{1}{\alpha(t)} \psi(x) \right\}$
    end for
end for
Output: Local temporal average $\widehat{x}_i(T) = \frac{1}{T} \sum_{t=1}^T x_i(t)$ at each node $i$
Knowl 2 — Basic Error Decomposition for Distributed Dual Averaging
theoretical result
Let the sequence of primal and dual iterates $\{x_i(t)\}_{t=1}^\infty$ and $\{z_i(t)\}_{t=0}^\infty$ be generated by distributed dual averaging across $n$ nodes on an undirected graph $G = (V,E)$ , where each node $i \in V$ holds an $L$ -Lipschitz convex objective $f_i$ with respect to a norm $\|\cdot\|$ . Let $f(x) = \frac{1}{n} \sum_{i=1}^n f_i(x)$ , $\bar{z}(t) = \frac{1}{n} \sum_{i=1}^n z_i(t)$ denote the network average of the dual vectors, and $\widehat{x}_i(T) = \frac{1}{T} \sum_{t=1}^T x_i(t)$ denote the local time average at node $i$ .

For any reference point $x^* \in \mathcal{X}$ and every node $i \in V$ , the error decomposes into optimization and network consensus deviation terms as:

$f(\widehat{x}_i(T)) - f(x^*) \le \frac{\psi(x^*)}{T \alpha(T)} + \frac{L^2}{2T} \sum_{t=1}^T \alpha(t-1) + \frac{2L}{nT} \sum_{t=1}^T \sum_{j=1}^n \alpha(t) \|\bar{z}(t) - z_j(t)\|_* + \frac{L}{T} \sum_{t=1}^T \alpha(t) \|\bar{z}(t) - z_i(t)\|_*$

where $\|\cdot\|_*$ is the dual norm of $\|\cdot\|$ .
Knowl 3 — Convergence Rate Governed by Network Spectral Gap
theoretical result
Let $P \in \mathbb{R}^{n \times n}$ be a symmetric doubly stochastic communication matrix conforming to graph $G$ with second singular value $\sigma_2(P) < 1$ . Suppose each $f_i$ is $L$ -Lipschitz with respect to $\|\cdot\|$ and $\psi(x^*) \le R^2$ for an optimal solution $x^* \in \mathcal{X}$ .

When distributed dual averaging is executed with the stepsize sequence

$\alpha(t) = \frac{R \sqrt{1 - \sigma_2(P)}}{4 L \sqrt{t}}$

for $t \ge 1$ , the running local average $\widehat{x}_i(T) = \frac{1}{T} \sum_{t=1}^T x_i(t)$ at every node $i \in \{1, \ldots, n\}$ satisfies:

$f(\widehat{x}_i(T)) - f(x^*) \le \frac{8 R L}{\sqrt{T}} \frac{\log(T \sqrt{n})}{\sqrt{1 - \sigma_2(P)}}$

Consequently, the iteration complexity to achieve an $\epsilon$ -accurate solution scales as $\mathcal{O}\left( \frac{1}{\epsilon^2 (1 - \sigma_2(P))} \right)$ up to logarithmic factors.
Knowl 4 — Network Topology Dependent Convergence Rates and Iteration Complexity
theoretical result
For a network of $n$ nodes using the doubly stochastic matrix $P_n(G) = I - \frac{1}{\delta_{\max}+1}(D - A)$ (with degree matrix $D$ , adjacency matrix $A$ , and maximum degree $\delta_{\max}$ ) and optimal stepsize $\alpha(t) \propto R \sqrt{1-\sigma_2(P_n(G))} / (L\sqrt{t})$ , the convergence rate $f(\widehat{x}_i(T)) - f(x^*)$ and iteration complexity $T_G(\epsilon; n)$ to reach an $\epsilon$ -suboptimal solution vary with network topology as:
1. $k$ -Connected Paths and Cycles ( $k \le \sqrt{n}$ ): $f(\widehat{x}_i(T)) - f(x^*) = \mathcal{O}\left( \frac{RL}{\sqrt{T}} \frac{n \log(Tn)}{k} \right), \quad T_{\text{cycle}}(\epsilon; n) = \mathcal{O}\left( \frac{n^2}{k^2 \epsilon^2} \right)$
2. $k$ -Connected $\sqrt{n} \times \sqrt{n}$ Grids ( $k \le n^{1/4}$ ): $f(\widehat{x}_i(T)) - f(x^*) = \mathcal{O}\left( \frac{RL}{\sqrt{T}} \frac{\sqrt{n} \log(Tn)}{k} \right), \quad T_{\text{grid}}(\epsilon; n) = \mathcal{O}\left( \frac{n}{k^2 \epsilon^2} \right)$
3. Random Geometric Graphs (connectivity radius $r = \Omega(\sqrt{\log^{1+\epsilon_0} n / n})$ for $\epsilon_0 > 0$ ): $f(\widehat{x}_i(T)) - f(x^*) = \mathcal{O}\left( \frac{RL}{\sqrt{T}} \sqrt{\frac{n}{\log n}} \log(Tn) \right), \quad T_{\text{RGG}}(\epsilon; n) = \mathcal{O}\left( \frac{n}{\log n \cdot \epsilon^2} \right) \quad \text{with high probability}$
4. Bounded-Degree Expander Graphs: $f(\widehat{x}_i(T)) - f(x^*) = \mathcal{O}\left( \frac{RL}{\sqrt{T}} \log(Tn) \right), \quad T_{\text{exp}}(\epsilon; n) = \mathcal{O}\left( \frac{1}{\epsilon^2} \right)$
Knowl 5 — Lower Bound on Network Scaling for Distributed Dual Averaging
theoretical result
For distributed dual averaging with a quadratic proximal function $\psi(x) = \frac{1}{2}\|x\|_2^2$ and communication matrix $P_n(G) = I - \frac{1}{\delta_{\max}+1}(D - A)$ , the inverse spectral gap dependence is unimprovable. For any graph $G$ with $n$ nodes, there exist $(c+1)$ -Lipschitz univariate linear objectives $f_i(x) = (c + w_i)x$ defined on $\mathcal{X} = [-1, 1]$ (where $w$ is the normalized second eigenvector of $P_n(G)$ such that $\sum_{i=1}^n w_i = 0$ and $\|w\|_\infty = 1$ , and $0 < c \le 1/3$ ) such that achieving a fixed error $f(\widehat{x}_i(T)) - f(x^*) \le c$ requires at least

$T_G(c; n) = \Omega\left( \frac{1}{1 - \sigma_2(P_n(G))} \right)$

iterations at node 1 (where $w_1 = -1$ ).
Knowl 6 — Distributed Dual Averaging with Stochastic Communication
theoretical result
Let $\{P(t)\}_{t=0}^\infty$ be an i.i.d. sequence of doubly stochastic communication matrices conforming to graph $G$ , and let $\lambda_2(G) = \lambda_2(\mathbb{E}[P(t)^\top P(t)])$ . Under the distributed dual averaging updates with time-varying communication weights $P_{ij}(t)$ and stepsize sequence $\{\alpha(t)\}_{t=0}^\infty$ , for any $x^* \in \mathcal{X}$ and each node $i \in V$ , with probability at least $1 - 1/T$ :

$f(\widehat{x}_i(T)) - f(x^*) \le \frac{\psi(x^*)}{T \alpha(T)} + \frac{L^2}{2T} \sum_{t=1}^T \alpha(t-1) + \frac{3L^2}{T} \left( \frac{6 \log(T^2 n)}{1 - \lambda_2(G)} + \frac{1}{T\sqrt{n}} + 2 \right) \sum_{t=1}^T \alpha(t)$

Setting $\alpha(t) \propto \frac{R\sqrt{1 - \lambda_2(G)}}{L\sqrt{t}}$ yields the high-probability convergence bound:

$f(\widehat{x}_i(T)) - f(x^*) \le C \frac{R L}{\sqrt{T}} \frac{\log(T n)}{\sqrt{1 - \lambda_2(\mathbb{E}[P(t)^\top P(t)])}}$

for a universal constant $C > 0$ , where $R^2 \ge \psi(x^*)$ .
Knowl 7 — Distributed Dual Averaging with Stochastic Subgradients
theoretical result
Let $\mathcal{F}_{t-1}$ denote the history of the algorithm up to step $t-1$ . Suppose each agent $i$ receives a noisy subgradient estimate $\widehat{g}_i(t)$ satisfying $\mathbb{E}[\widehat{g}_i(t) \mid \mathcal{F}_{t-1}] \in \partial f_i(x_i(t))$ and $\mathbb{E}[\|\widehat{g}_i(t)\|_*^2 \mid \mathcal{F}_{t-1}] \le L^2$ .
1. Expected Convergence: For each node $i \in V$ : $\mathbb{E}[f(\widehat{x}_i(T))] - f(x^*) \le \frac{\psi(x^*)}{T\alpha(T)} + \frac{8L^2}{T} \sum_{t=1}^T \alpha(t-1) + \frac{3L^2 \log(T\sqrt{n})}{T(1 - \sigma_2(P))} \sum_{t=1}^T \alpha(t)$
2. High-Probability Bound: If $\mathcal{X}$ has finite radius $R = \sup_{x \in \mathcal{X}} \|x - x^*\|$ and $\|\widehat{g}_i(t)\|_* \le L$ , then with probability at least $1 - \delta$ : $f(\widehat{x}_i(T)) - f(x^*) \le \frac{\psi(x^*)}{T\alpha(T)} + \frac{8L^2}{T} \sum_{t=1}^T \alpha(t-1) + \frac{3L^2 \log(T\sqrt{n})}{T(1 - \sigma_2(P))} \sum_{t=1}^T \alpha(t) + 8LR \sqrt{\frac{\log(1/\delta)}{T}}$
3. Uncorrelated Gradient Noise: If the gradient estimates across nodes are conditionally uncorrelated given $\mathcal{F}_{t-1}$ , the concentration penalty improves to $\frac{3LR\log(1/\delta)}{T} + 4LR\sqrt{\frac{\log(1/\delta)}{nT}}$ .
Knowl 8 — Doubly Stochastic Weight Matrix Design via the Normalized Graph Laplacian
theoretical result
For an undirected connected graph $G = (V, E)$ with adjacency matrix $A$ , degree matrix $D = \operatorname{diag}(\delta_1, \ldots, \delta_n)$ , maximum degree $\delta_{\max}$ , minimum degree $\delta_{\min}$ , and normalized Laplacian $\mathcal{L}(G) = I - D^{-1/2} A D^{-1/2}$ , the symmetric matrix

$P_n(G) = I - \frac{1}{\delta_{\max} + 1}(D - A) = I - \frac{1}{\delta_{\max} + 1} D^{1/2} \mathcal{L}(G) D^{1/2}$

is doubly stochastic and satisfies:

$\sigma_2(P_n(G)) \le \max \left\{ 1 - \frac{\delta_{\min}}{\delta_{\max}+1} \lambda_{n-1}(\mathcal{L}(G)), \; \frac{\delta_{\max}}{\delta_{\max}+1} \lambda_1(\mathcal{L}(G)) - 1 \right\}$

For a lazy random walk $P_{\text{lazy}} = \frac{1}{2}(I + P_n(G))$ , the singular value bound simplifies strictly in terms of the algebraic connectivity $\lambda_{n-1}(\mathcal{L}(G))$ :

$\sigma_2(P_{\text{lazy}}) = \lambda_2(P_{\text{lazy}}) \le 1 - \frac{\delta_{\min}}{2(\delta_{\max}+1)} \lambda_{n-1}(\mathcal{L}(G))$

which directly upper bounds the distributed dual averaging convergence rate by $\mathcal{O}\left( \frac{RL}{\sqrt{T}} \frac{\log(Tn)}{\sqrt{\lambda_{n-1}(\mathcal{L}(G))}} \right)$ .
Knowl 9 — Extension to Distributed Composite and Regularized Objectives
theoretical result
Distributed dual averaging extends to composite optimization problems of the form $\min_{x \in \mathcal{X}} \{ \frac{1}{n} \sum_{i=1}^n f_i(x) + \phi(x) \}$ , where $\phi$ is a known non-negative closed convex regularizer, by modifying the local primal update to the composite projection:

$x_i(t+1) = \Pi_{\mathcal{X}}^t(-z_i(t+1)) = \operatorname{argmin}_{x \in \mathcal{X}} \left\{ \langle z_i(t+1), x \rangle + t \phi(x) + \frac{1}{\alpha(t)} \psi(x) \right\}$

with dual updates $z_i(t+1) = \sum_{j=1}^n P_{ij}(t) z_j(t) + g_i(t)$ , where $\mathbb{E}[g_i(t) \mid \mathcal{F}_{t-1}] \in \partial f_i(x_i(t))$ .

For $y(t) = \Pi_{\mathcal{X}}^t(-\bar{z}(t))$ where $\bar{z}(t) = \frac{1}{n} \sum_{i=1}^n z_i(t)$ , the running average satisfies:

$\sum_{t=1}^T \left( f(y(t)) + \phi(y(t)) - f(x^*) - \phi(x^*) \right) \le \frac{\psi(x^*)}{\alpha(T)} + \frac{L^2}{2} \sum_{t=1}^T \alpha(t-1) + \frac{2L}{n} \sum_{t=1}^T \alpha(t) \sum_{i=1}^n \|\bar{z}(t) - z_i(t)\|_*$

retaining the exact same network scaling properties with respect to the spectral gap as standard distributed dual averaging.
Knowl 10 — Spectral Scaling for Partially Asynchronous Gossip and Random Edge Failures
theoretical result
In stochastic communication frameworks with time-varying matrices $P(t)$ :
1. Partially Asynchronous Gossip: In each round $t$ , a single edge $(i, j) \in E$ is sampled with probability $1 / \langle \mathbf{1}, A\mathbf{1} \rangle$ and updates use $P(t) = I - \frac{1}{2}(e_i - e_j)(e_i - e_j)^\top$ . Since $P(t)^\top P(t) = P(t)$ , the expected transition matrix is $\mathbb{E}[P(t)] = I - \frac{1}{\langle \mathbf{1}, A\mathbf{1} \rangle} D^{1/2} \mathcal{L}(G) D^{1/2}$ , yielding: $\lambda_2(\mathbb{E}[P(t)]) \le 1 - \frac{\min_i \delta_i}{\langle \mathbf{1}, A\mathbf{1} \rangle} \lambda_{n-1}(\mathcal{L}(G))$ For regular graphs, this reduces per-round communication from $\Theta(n \delta_{\max})$ edges to 1 at the cost of a factor of roughly $1/n$ in convergence rate.
2. Independent Edge Failures: When each edge fails independently with probability $\rho \in (0, 1)$ at each round, the expected communication matrix becomes $\mathbb{E}[P(t)] = \rho I + (1 - \rho)P$ , where $P$ is the static doubly stochastic matrix. The second eigenvalue satisfies: $\lambda_2(\mathbb{E}[P(t)]) = \rho + (1 - \rho)\lambda_2(P)$ which scales the convergence rate bound by at most a factor of $\sqrt{1 - \rho}$ .
Knowl 11 — Empirical Network Scaling on Distributed Support Vector Machines
empirical result
Numerical evaluations of distributed dual averaging on distributed linear SVM classification minimizing $f(x) = \frac{1}{n} \sum_{i=1}^n [1 - y_i \langle b_i, x \rangle]_+$ subject to $\|x\|_2 \le 5$ (with $L = \max_i \|b_i\|_2 = 1$ ) over networks ranging from $n = 100$ to $n = 900$ nodes confirm the theoretical scaling laws:
- Single Cycle Graphs: The number of iterations $T_{\text{cycle}}(\epsilon; n)$ to reach a fixed suboptimality error $\epsilon = 0.1$ grows quadratically as $\Theta(n^2)$ .
- Two-Dimensional Grids: The iteration count $T_{\text{grid}}(\epsilon; n)$ grows linearly as $\Theta(n)$ .
- Random 5-Regular Expanders: The iteration count $T_{\text{exp}}(\epsilon; n)$ remains constant regardless of network size $n$ .
Comparing distributed dual averaging (DDA) against Markov incremental gradient descent (MIGD) shows DDA scales substantially better: on expanders, DDA requires a constant number of iterations $\mathcal{O}(1/\epsilon^2)$ whereas MIGD requires $\mathcal{O}(n/\epsilon^2)$ iterations.

Coverage note — None was omitted; all key theoretical bounds, algorithm definitions, spectral graph analyses, stochastic extensions, composite objectives, and empirical evaluations are represented.

References

1.N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), 83–96.
2.K. Azuma, Weighted sums of certain dependent random variables, Tohoku Mathematical Journal 68 (1967), 357–367.
3.F. Bénézit, A. Dimakis, P. Thiran, and M. Vetterli, Order-optimal consensus through randomized path averaging, IEEE Transactions on Information Theory 56 (2010), no. 10, 5150–5167.
4.D.P. Bertsekas, Nonlinear programming, Athena Scientific, 1999.
5.S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, Randomized gossip algorithms, IEEE Transactions on Information Theory 52 (2006), no. 6, 2508–2530.
6.D. P. Bertsekas and J. N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., 1989.
7.F.R.K. Chung, Spectral graph theory, AMS, 1998.
8.C. Cortes and V. Vapnik, Support-vector networks, Machine Learning 20 (1995), no. 3, 273–297.
9.P. Diaconis and D. Stroock, Geometric bounds for eigenvalues of Markov chains, The Annals of Probability 1 (1991), no. 1, 36–61.
10.A. G. Dimakis, A. Sarwate, and M. J. Wainwright, Geographic gossip: Efficient averaging for sensor networks, IEEE Transactions on Signal Processing 53 (2008), 1205–1216.
11.G. B. Dantzig and P. Wolfe, Decomposition principle for linear programs, Operations Research 8 (1960), 101–111.
12.J. Friedman, J. Kahn, and E. Szemerédi, On the second eigenvalue of random regular graphs, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, ACM, 1989, pp. 587–598.
13.D. A. Freedman, On tail probabilities for martingales, The Annals of Probability 3 (1975), no. 1, 100–118.
14.P. Gupta and P. Kumar, The capacity of wireless networks, IEEE Transactions on Information Theory 46 (2000), no. 2, 388–404.
15.R. Gray, Toeplitz and circulant matrices: A review, Foundations and Trends in Communications and Information Theory 2 (2006), no. 3, 155–239.
16.R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 1985.
17.J. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms I, Springer, 1996.
18.———, Convex Analysis and Minimization Algorithms II, Springer, 1996.
19.B. Johansson, M. Rabi, and M. Johansson, A randomized incremental subgradient method for distributed optimization in networked systems, SIAM Journal on Optimization 20 (2009), no. 3, 1157–1170.
20.A. Kalai and S. Vempala, Efficient algorithms for online decision problems, Journal of Computer and System Sciences 71 (2005), no. 3, 291–307.
21.I. Lobel and A. Ozdaglar, Distributed subgradient methods over random networks, Tech. Report 2800, MIT LIDS, 2009.
22.V. Lesser, C. Ortiz, and M. Tambe (eds.), Distributed Sensor Networks: A Multiagent Perspective, vol. 9, Kluwer Academic Publishers, 2003.
23.D. Levin, Y. Peres, and E. Wilmer, Markov Chains and Mixing Times, American Mathematical Society, 2008.
24.D. Li, K. Wong, Y. Hu, and A. Sayeed, Detection, classification and tracking of targets in distributed sensor networks, IEEE Signal Processing Magazine, 2002, pp. 17–29.
25.D. Mosk-Aoyama, T. Roughgarden, and D. Shah, Fully distributed algorithms for convex optimization problems, SIAM Journal on Optimization 20 (2010), no. 6, 3260–3279.
26.R. McDonald, K. Hall, and G. Mann, Distributed training strategies for the structured perceptron, North American Chapter of the Association for Computational Linguistics (NAACL), 2010.
27.A. Nedic and D. P. Bertsekas, Incremental subgradient methods for nondifferentiable optimization, SIAM Journal on Optimization 12 (2001), no. 1, 109–138.
28.Y. Nesterov, Introductory lectures on convex optimization, Kluwer Academic Publishers, 2004.
29.———, Primal-dual subgradient methods for convex problems, Mathematical Programming A 120 (2009), no. 1, 261–283.
30.A. Nedić and A. Ozdaglar, Distributed subgradient methods for multi-agent optimization, IEEE Transactions on Automatic Control 54 (2009), 48–61.
31.A. Nedić, A. Olshevsky, A. Ozdaglar, and J. N. Tsitsiklis, On distributed averaging algorithms and quantization effects, IEEE Transactions on Automatic Control 54 (2009), no. 11, 2506 –2517.
32.A. Nemirovski and D. Yudin, Problem complexity and method efficiency in optimization, Wiley, New York, 1983.
33.M. Penrose, Random Geometric Graphs, Oxford University Press, 2003.
34.M. Rabbat and R. Nowak, Distributed optimization in sensor networks, The 3rd International Symposium on Information Processing in Sensor Networks, 2004, pp. 20–27.
35.S. S. Ram, A. Nedić, and V. V. Veeravalli, Distributed stochastic subgradient projection algorithms for convex optimization, Journal of Optimization Theory and Applications 147 (2010), no. 3, 516–545.
36.J. N. Tsitsiklis, D. P. Bertsekas, and M. Athans, Distributed asynchronous deterministic and stochastic gradient optimization algorithms, IEEE Transactions on Automatic Control 31 (1986), 803–812.
37.J. Tsitsiklis, Problems in decentralized decision making and computation, Ph.D. thesis, Massachusetts Institute of Technology, 1984.
38.U. von Luxburg, A. Radl, and M. Hein, Hitting times, commute distances, and the spectral gap for large random geometric graphs, 2010.
39.L. Xiao, S. Boyd, and S. J. Kim, Distributed average consensus with least-mean-square deviation, Journal of Parallel and Distributed Computing 67 (2007), no. 1, 33–46.
40.L. Xiao, Dual averaging methods for regularized stochastic learning and online optimization, Journal of Machine Learning Research 11 (2010), 2543–2596.

Citation

MLA

Duchi, J. C., et al. “Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling”. IEEE Transactions on Automatic Control, vol. 57, no. 3, 2012, pp. 592–606, https://doi.org/10.1109/TAC.2011.2161027.

APA

Duchi, J. C., Agarwal, A., & Wainwright, M. J. (2012). Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling. IEEE Transactions on Automatic Control, 57(3), 592–606. https://doi.org/10.1109/TAC.2011.2161027

Chicago

Duchi, J. C., A. Agarwal, and M. J. Wainwright. 2012. “Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling”. IEEE Transactions on Automatic Control 57 (3): 592–606. https://doi.org/10.1109/TAC.2011.2161027.

Harvard

Duchi, J.C., Agarwal, A. and Wainwright, M.J. (2012) “Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling”, IEEE Transactions on Automatic Control, 57(3), pp. 592–606. Available at: https://doi.org/10.1109/TAC.2011.2161027.

Vancouver

1. Duchi JC, Agarwal A, Wainwright MJ (2012) Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling. IEEE Transactions on Automatic Control 57:592–606

BibTeX

@article{Duchi_2012, title={Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling}, volume={57}, ISSN={1558-2523}, url={http://dx.doi.org/10.1109/TAC.2011.2161027}, DOI={10.1109/tac.2011.2161027}, number={3}, journal={IEEE Transactions on Automatic Control}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Duchi, J. C. and Agarwal, A. and Wainwright, M. J.}, year={2012}, month=Mar, pages={592–606} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Distributed Dual Averaging Algorithm

Knowl 2 — Basic Error Decomposition for Distributed Dual Averaging

Knowl 3 — Convergence Rate Governed by Network Spectral Gap

Knowl 4 — Network Topology Dependent Convergence Rates and Iteration Complexity

Knowl 5 — Lower Bound on Network Scaling for Distributed Dual Averaging

Knowl 6 — Distributed Dual Averaging with Stochastic Communication

Knowl 7 — Distributed Dual Averaging with Stochastic Subgradients

Knowl 8 — Doubly Stochastic Weight Matrix Design via the Normalized Graph Laplacian

Knowl 9 — Extension to Distributed Composite and Regularized Objectives

Knowl 10 — Spectral Scaling for Partially Asynchronous Gossip and Random Edge Failures

Knowl 11 — Empirical Network Scaling on Distributed Support Vector Machines

References

Citation

BibTeX

Access the Paper