Asymptotic Network Independence and Step-Size for A Distributed Subgradient Method

Alex OlshevskyarXiv 2020 · OpenReview

TL;DR

This paper investigates whether distributed optimization methods can achieve a linear speedup over their centralized counterparts. The authors demonstrate that a linear speedup is possible with specific step-size choices ($1/t^\beta$ with $\beta \in (1/2, 1)$), leading to network-independent performance after a transient phase. However, they also show that the optimal step-size ($1/\sqrt{t}$) can prevent this speedup, highlighting a crucial interplay between step-size selection and network topology.

What Problem Does This Paper Address?

The core question this paper tackles is whether distributing an optimization problem across multiple nodes in a network can lead to a faster solution compared to a single, centralized node. Intuitively, if $n$ nodes can compute $n$ subgradients in parallel, one might expect an $n$-times speedup. However, existing theoretical bounds for distributed optimization methods often suggest a slowdown or, at best, no significant speedup. This paper aims to clarify the conditions under which a true linear speedup is achievable and when it is not, particularly focusing on the role of the step-size in the subgradient method.

Methods

The paper analyzes a distributed subgradient method, specifically a variation of the standard projected subgradient method adapted for a network setting. The core of their analysis involves:

  • Theoretical Analysis of Convergence Rates: The authors derive convergence bounds for both centralized and distributed subgradient methods. They meticulously track how factors like network topology (represented by the spectral gap, $1-\sigma$) and the number of nodes ($n$) influence these bounds.
  • Step-Size Analysis: A significant portion of the work is dedicated to understanding the impact of different step-size decay rates. They distinguish between:
  • Square-summable-but-not-summable step-sizes: Specifically, $a(t) = 1/t^\beta$ where $\beta \in (1/2, 1)$.
  • Optimally decaying step-size: $a(t) = 1/\sqrt{t}$.
  • Counterexample Construction: To demonstrate the limitations of certain step-sizes, they construct a specific graph topology and a set of non-smooth functions where the distributed method fails to achieve network independence, even with a large number of iterations.
  • Mathematical Tools: The proofs rely on standard techniques in convex optimization, including telescoping sums, analysis of recurrence relations, and properties of doubly stochastic matrices.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses synthetic problem instances for simulation rather than real-world datasets.

Key Insights and Ideas

  • Step-Size is Crucial for Speedup: The choice of step-size is not merely a tuning parameter; it fundamentally dictates whether a distributed method can achieve asymptotic network independence and a linear speedup.
  • "Network Independence" is Achievable (with the Right Step-Size): For step-sizes like $1/t^\beta$ with $\beta \in (1/2, 1)$, the convergence rate eventually becomes independent of the network's spectral gap and the number of nodes, implying a true linear speedup. This means that after an initial "transient" period, the performance is solely determined by the problem's inherent difficulty, not the network's structure.
  • The "Optimal" Step-Size Can Be Detrimental: Counter-intuitively, the standard, theoretically optimal step-size for centralized methods, $1/\sqrt{t}$, can prevent network independence in distributed settings. This is because the error introduced by network disagreement might not decay fast enough relative to the $1/\sqrt{t}$ step-size, leading to a persistent dependence on network parameters.
  • Transient Period Matters: While network independence is achieved asymptotically, the size of the transient period before this independence kicks in can depend on the network's spectral gap. This means that for practical, finite-time convergence, the network structure can still play a role.
  • "Step-Size Inversion" Phenomenon: The paper hints at a phenomenon where a slower-decaying step-size (larger $\beta$) might be worse for centralized methods but better for distributed ones, especially in non-smooth problems. This suggests that the optimal step-size choice might differ significantly between centralized and distributed optimization.

Key Results

  • Theorem 2: Proves that for step-sizes $a(t) = 1/t^\beta$ with $\beta \in (1/2, 1)$, a distributed subgradient method achieves asymptotic network independence and a linear speedup over a single-node rate. The performance guarantee becomes independent of the network's spectral gap and the number of nodes after a transient period.
  • Theorem 3: Demonstrates that for the step-size $a(t) = 1/\sqrt{t}$, asymptotic network independence is not achieved. A counterexample is constructed where the convergence rate remains dependent on the network's spectral gap, even for large numbers of iterations.
  • Quantitative Bounds: The paper provides explicit bounds on the error $F(\bar{x}(t)) - F^*$ (where $\bar{x}(t)$ is the average iterate and $F^*$ is the optimal value), showing how these bounds depend on network parameters (like $1-\sigma$) for $1/\sqrt{t}$ step-sizes, but not for $1/t^\beta$ with $\beta \in (1/2, 1)$ after the transient.
  • Simulation Results (Figure 1): Numerical simulations visually confirm the theoretical findings, showing that for $a(t) = 1/\sqrt{t}$, the performance scales with $n$ (or related network parameters), while for $a(t) = 1/t^{3/4}$, the curves converge to a common bound, indicating network independence.

Limitations and Future Work

  • Non-Smoothness Assumption: The analysis for the $1/\sqrt{t}$ step-size counterexample relies on non-smooth functions. The authors note that their results for $1/t^\beta$ with $\beta \in (1/2, 1)$ hold for convex functions, but the specific counterexample for $1/\sqrt{t}$ is constructed for non-smoothness.
  • Transient Period Dependence: While asymptotic network independence is shown for certain step-sizes, the size of the transient period can still depend on the network's spectral gap.
  • Practical Implications of Step-Size Inversion: The paper identifies a "step-size inversion" phenomenon where a slower-decaying step-size might be better for distributed methods in practice, even if worse for centralized ones. However, this is based on simulations and a specific class of problems, and a theoretical explanation is lacking.
  • Future Work:
    • Developing a theoretical explanation for the observed step-size inversion phenomenon.
  • Investigating whether a linear speedup can be obtained for the $1/\sqrt{t}$ step-size using a different algorithm or a modified standard model of distributed optimization.
  • Conducting larger-scale computational studies to see if step-size inversion is a widespread phenomenon.
  • Exploring if linear speedup is achievable for $\beta = 1/2$ with alternative algorithms.

Summary updated

Abstract

We consider whether distributed subgradient methods can achieve a linear speedup over a centralized subgradient method. While it might be hoped that distributed network of $n$ nodes that can compute $n$ times more subgradients in parallel compared to a single node might, as a result, be $n$ times faster, existing bounds for distributed optimization methods are often consistent with a slowdown rather than speedup compared to a single node. We show that a distributed subgradient method has this "linear speedup" property when using a class of square-summable-but-not-summable step-sizes which include $1/t^{\beta}$ when $\beta \in (1/2,1)$; for such step-sizes, we show that after a transient period whose size depends on the spectral gap of the network, the method achieves a performance guarantee that does not depend on the network or the number of nodes. We also show that the same method can fail to have this "asymptotic network independence" property under the optimally decaying step-size $1/\sqrt{t}$ and, as a consequence, can fail to provide a linear speedup compared to a single node with $1/\sqrt{t}$ step-size.
BibTeX
@misc{olshevsky2020asymptotic,
  author = {Alex Olshevsky},
  title = {{Asymptotic Network Independence and Step-Size for A Distributed Subgradient Method}},
  year = {2020},
  eprint = {2003.06739},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2003.06739},
}
Figure