Distributed Dual Averaging In Networks

John C. Duchi, Alekh Agarwal, Martin J. WainwrightNeurIPS 2010 · OpenReview

The Challenge of Decentralized Optimization

In the era of "Big Data," datasets are often too massive to fit on a single machine. To solve optimization problems—such as training a machine learning model—data must be distributed across a network of processors.

The primary challenge in this setting is decentralized optimization: how can these processors work together to minimize a global objective function when each node only knows its own local data and can only communicate with its immediate neighbors? Previous methods often suffered from convergence rates that scaled poorly with the number of nodes ($n$), sometimes even exponentially. This paper introduces an algorithm where the convergence rate is "sharp," meaning it accurately reflects how the network's physical shape (topology) affects its overall performance.

Distributed Dual Averaging

To address these communication constraints, the authors propose a Distributed Dual Averaging subgradient method. The algorithm operates through four main steps:

  1. Local Subgradients: Each node computes a subgradient (a generalized derivative) of its local cost function based on its own data.
  2. Dual Averaging: Instead of simply updating a local parameter, each node maintains a running weighted average of the subgradients it has computed, alongside those it has received from its neighbors.
  3. Communication: Nodes communicate using a "doubly stochastic" weight matrix ($P$), ensuring that information eventually spreads evenly across the entire network.
  4. Projection: To generate the next estimate, nodes perform a "proximal projection," which maps the accumulated gradient information back into the space of feasible solutions.

Unlike previous "primal" subgradient methods, this "dual" approach allows the authors to cleanly separate the error originating from the optimization process itself from the error caused by network communication constraints.

Network Topologies and the Spectral Gap

The researchers validated their theory using a synthetic SVM problem (distributed minimization of hinge losses) across four distinct network structures:

Four network topologies tested: (a) cycle, (b) grid, (c) random geometric, and (d) expander graph.
  • Single Cycles/Paths: Poorly connected networks.
  • 2D Grids: Moderately connected networks.
  • Random Geometric Graphs: Models typical of wireless sensor networks.
  • Expander Graphs: Highly connected, sparse graphs.

The most significant insight from the paper is that the number of iterations required to reach an $\epsilon$-optimal solution scales inversely with the spectral gap ($1 - \sigma_2(P)$) of the network. The theory predicts that "well-connected" networks like expander graphs will converge much faster than "stringy" networks like cycles. Furthermore, the authors provide a lower bound proving that their algorithm’s dependence on network topology is essentially optimal for this class of methods.

Key Results and Scaling Laws

The paper provides explicit scaling laws for the number of iterations ($T$) needed to reach a specific accuracy ($\epsilon$), which are strongly supported by experimental simulations:

Scaling of steps required to reach an $\epsilon$-optimal solution across different network sizes and topologies.
  • Cycles/Paths: $T \approx O(n^2/\epsilon^2)$. The time required grows quadratically with the number of nodes.
  • 2D Grids: $T \approx O(n/\epsilon^2)$. The time grows linearly with the number of nodes.
  • Expander Graphs: $T \approx O(1/\epsilon^2)$. Remarkably, for these well-connected graphs, the time to converge is independent of the number of nodes in the network.

Because of the algorithm's design, every node maintains a "good" estimate of the optimum at all times, which is critical for real-time or streaming applications.

Limitations and Future Work

While the theoretical bounds are sharp, the study has a few limitations. The primary analysis assumes a static network topology with a constant weight matrix $P$, though extensions to changing networks are briefly noted. Additionally, the algorithm relies on synchronous updates, whereas asynchronous updates are often more practical in massive, real-world systems. Finally, the method is designed strictly for convex functions; extending these sharp topological bounds to non-convex landscapes (like deep neural networks) remains a significant challenge for future research.

Summary updated

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. 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 analysis clearly separates the convergence of the optimization algorithm itself from the effects of communication constraints arising from the network structure. 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.
BibTeX
@inproceedings{duchi2010distributed,
  author = {John C. Duchi and Alekh Agarwal and Martin J. Wainwright},
  title = {{Distributed Dual Averaging In Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=H1W2XPW_Wr},
}
Figure