Source-linked AI summary
Optimal Algorithms for Non-Smooth Distributed Optimization in Networks
Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, Laurent Massoulié
TL;DR
The paper asks how to obtain optimal distributed algorithms and convergence rates for non-smooth convex optimization under global or local Lipschitz assumptions. It develops MSPD for local regularity and DRS for global regularity, showing optimality for the former and near-optimal communication convergence for the latter. Under local regularity, communication contributes a faster O(1/t) term alongside dominant O(1/√t) optimization error.
Problem
The paper studies optimal convergence rates and algorithms for non-smooth convex optimization distributed across a network under global or local Lipschitz regularity.
Method
It develops MSPD for local regularity and adapts randomized smoothing into DRS for global regularity, using decentralized communication and computation schemes.
Results
MSPD is optimal under local regularity, while DRS is within a d^1/4 multiplicative factor of the optimal convergence rate under global regularity.
Takeaways & Limitations
Under local regularity, communication error decreases at O(1/t), faster than the dominant O(1/√t) non-smooth optimization error.
Takeaways & Limitations
Finding an optimal algorithm under global regularity remains an open problem.
Abstract
from arXiv · showhide
In this work, we consider the distributed optimization of non-smooth convex functions using a network of computing units. We investigate this problem under two regularity assumptions: (1) the Lipschitz continuity of the global objective function, and (2) the Lipschitz continuity of local individual functions. Under the local regularity assumption, we provide the first optimal first-order decentralized algorithm called multi-step primal-dual (MSPD) and its corresponding optimal convergence rate. A notable aspect of this result is that, for non-smooth functions, while the dominant term of the error is in $O(1/\sqrt{t})$, the structure of the communication network only impacts a second-order term in $O(1/t)$, where $t$ is time. In other words, the error due to limits in communication resources decreases at a fast rate even in the case of non-strongly-convex objective functions. Under the global regularity assumption, we provide a simple yet efficient algorithm called distributed randomized smoothing (DRS) based on a local smoothing of the objective function, and show that DRS is within a $d^{1/4}$ multiplicative factor of the optimal convergence rate, where $d$ is the underlying dimension.
1 Introduction
The paper extends optimal convergence analysis for distributed optimization from smooth, strongly convex problems to non-smooth convex objectives under global and local Lipschitz assumptions. It introduces MSPD and DRS, while showing that communication error can decrease at a faster rate than optimization error under local regularity.
- Non-smooth distributed optimization is studied under Lipschitz continuity of either the global objective or the local functions.These are the paper’s two regularity assumptions for deriving convergence rates and algorithms.
- MSPD provides the first optimal algorithm for non-smooth decentralized optimization under local regularity.The result includes matching upper and lower complexity bounds in the gossip communication setting.
- DRS matches the global-regularity lower bound within a d^1/4 multiplicative factor, where d is the problem dimension.It distributes a randomized smoothing approach to obtain fast communication convergence.
- Communication limitations contribute an O(1/t) error term, while the dominant non-smooth optimization error is O(1/√t).The analysis models communication through a smooth saddle-point term and local optimization through a non-smooth term.
- The paper addresses a gap left by prior non-smooth decentralized methods, which lacked precise optimal convergence rates.Earlier work had developed fast communication schemes but had not established exact optimal rates.
2 Distributed optimization setting
The setting consists of computing units on a strongly connected directed network, each holding a convex local function and communicating or computing asynchronously. The analysis distinguishes global from local Lipschitz regularity, with matching bounds available only under the local assumption.
- Optimization problem: The optimization problem minimizes the average of convex local functions held separately by n computing units on a strongly connected directed graph.Each function is defined over a convex set K, and the network has diameter Δ.
- Distributed setting: Each node computes subgradients of its local function and communicates vectors to neighboring nodes, with direct communication taking time τ.Computations and communications may proceed asynchronously and in parallel, while each node maintains a local parameter.
- Regularity assumptions: Global regularity assumes that the global objective is Lg-Lipschitz, whereas local regularity assumes each local function is Li-Lipschitz.The local assumption is summarized using the ℓ2-average of the local Lipschitz constants.
- Regularity assumptions: A1 is weaker than A2 because Lg ≤ Lℓ, and global regularity can hold even when local Lipschitz constants are arbitrarily large.The paper obtains matching upper and lower bounds under local regularity but only a d^1/4 competitive ratio under global regularity.
- Assumptions: The feasible region K is assumed convex and bounded, with R denoting the radius of a ball containing it.
- Black-box procedure: The black-box model permits local memory, subgradient computation, neighbor communication, and a per-node output value.The analysis requires all local outputs to converge to the optimal parameter.
3 Distributed optimization under global regularity
Under global regularity, the paper develops distributed randomized smoothing (DRS) and analyzes its computation and communication rates against lower bounds. DRS uses local Gaussian smoothing and shared randomness to obtain fast communication convergence, with performance within a d^1/4 factor of optimal communication convergence.
- 3.1 A simple algorithm with fast communication rates: The DRS procedure computes a spanning tree, distributes a random seed, broadcasts iterates, and assigns smoothed-gradient computations to the computing units.Most optimization steps run at the spanning-tree root while other units compute the smoothed gradient.
- 3.1 A simple algorithm with fast communication rates: Gaussian smoothing makes the objective smooth and enables accelerated optimization, but each smoothed-gradient computation requires sampling subgradients at perturbed points.The shared seed lets computing units reproduce the same random variables without communicating every sample.
- 3.1 A simple algorithm with fast communication rates: DRS distributes randomized smoothing of the global objective to obtain fast convergence with respect to communication time.Nodes share one random seed to generate identical Gaussian samples, avoiding communication of each sampled vector.
- 3.1 A simple algorithm with fast communication rates: DRS improves on the standard distributed method when the dimension is not too large, with d^1/4 remaining about 6 when d = 1000.For R and Lg around 1, the stated condition is already met when ε ≤ 10^-2 and d ≤ 10^8.
- 3.1 A simple algorithm with fast communication rates: A lower bound shows that DRS is optimal in computation time and within a d^1/4 multiplicative factor of the optimal communication convergence rate.The lower bound applies to black-box procedures under the global regularity assumption and is constructed from separate worst-case computation and communication functions.
4 Decentralized optimization under local regularity
Under local regularity, decentralized optimization is analyzed with gossip communication, yielding matching lower bounds and the optimal MSPD algorithm. MSPD combines primal-dual updates with accelerated gossip to attain the lower complexity bound.
- Communication model: The decentralized model uses local averaging through a symmetric positive-semidefinite gossip matrix supported on network edges.Its kernel is the space of constant vectors, ensuring consensus across nodes.
- Optimal convergence rate: The lower bound depends on the normalized eigengap γ(W), which replaces network diameter as the communication-connectivity parameter.The eigengap is γ(W) = λn−1(W)/λ1(W).
- Optimal decentralized algorithm: The proposed MSPD algorithm modifies a primal-dual method with Chebyshev-accelerated gossip for decentralized optimization under local regularity.Its updates are implemented locally using the gossip matrix and approximate proximal steps based on multiple subgradient iterations.
- Optimal decentralized algorithm: MSPD achieves the optimal convergence rate under the local regularity assumption, matching the lower complexity bound.The algorithm uses accelerated communication and M subgradient steps per iteration to control approximation error.
- Optimal decentralized algorithm: The iterative variant has an optimal communication term, but its local-computation term does not match the lower bound until additional communication acceleration is used.Chebyshev acceleration with an increased number of communication steps closes this gap.
5 Conclusion
The paper establishes optimal convergence rates for non-smooth convex distributed optimization under global and local Lipschitz assumptions. MSPD is optimal locally, while DRS is within a d^1/4 factor globally, and communication error decreases faster than computation error.
- Contributions: The paper studies two regularity settings: Lipschitz continuity of the global objective and Lipschitz continuity of local functions.Under local regularity, rates depend on the ℓ2-average of local Lipschitz constants and the gossip eigengap.
- Contributions: MSPD is the first optimal decentralized algorithm for non-smooth optimization under local regularity.Its convergence rate matches the corresponding lower complexity bound.
- Contributions: DRS is within a d^1/4 multiplicative factor of the optimal convergence rate under global regularity.The paper also provides a lower complexity bound for this setting.
- Open problems: Finding an optimal algorithm under global regularity remains an open problem despite DRS's efficiency.The analysis also points to extensions involving time-varying networks, asynchronous algorithms, stochastic settings, and unequal compute speeds.
A Proof of the convergence rate of DRS (Theorem 1)
This proof derives a time bound for DRS by selecting the gradient step and smoothing parameters appropriately, then translating the resulting precision requirement into total time.
- Parameter choice: Choosing ηt and γt according to Corollary 2.4 gives the DRS convergence bound.The parameter choice controls both the gradient iteration and local smoothing contributions.
- Precision target: To reach precision ε, the proof selects an iteration count T based on the resulting error inequality.This converts the convergence estimate into an explicit complexity requirement.
- Time complexity: The total time bound is Tε = T(2∆τ + K), combining communication time with the per-iteration computational cost.The expression captures the time needed to reach the desired precision.
B Proof of the lower bound under global regularity (Theorem 2)
The global-regularity lower-bound proof combines a single-machine hard function with a communication-hard function split across distant nodes. Coordinate-activation constraints then limit how quickly distributed subgradient methods can reduce the error.
- Hard-instance construction: The construction starts from a hard Lipschitz bounded-function instance used to establish single-machine oracle complexity.This supplies the local-computation component of the lower bound.
- Hard-instance construction: The hard function is split across two extremal nodes so communication between distant parts of the network is necessary.The resulting objective combines local optimization difficulty with network-dependent communication difficulty.
- Optimizer structure: Reordering coordinates decreases the objective, so an optimum can be taken to satisfy the corresponding decreasing-order constraint.This structural property simplifies characterization of the worst-case optimizer.
- Optimizer structure: At the optimum, coordinate blocks are constant and coordinates after the final active block are zero.The proof uses this block structure to analyze the objective value.
- Information-propagation lower bound: Before enough subgradient and communication steps occur, newly activated coordinates remain zero, preventing the method from reaching the optimum quickly.For the stated time range, information cannot propagate across all required coordinates and distant nodes.
C Proof of the lower bound under local regularity (Theorem 3)
The lower-bound construction realizes prescribed network eigengaps using connected three-node or weighted linear graphs, then separates function supports across distant node sets. This preserves the average objective while imposing communication delay that yields the lower-bound behavior.
- Graph construction: For γ ≥ 1/3, the construction uses a totally connected graph with n_γ = 3 nodes and adjusts one edge weight to realize γ.Continuity of the Laplacian eigenvalues provides an edge weight a ∈ [0, 1] with γ(W_a) = γ.
- Graph construction: For γ < 1/3, a weighted linear graph is chosen so its size n_γ and edge weighting realize the prescribed eigengap γ.The construction uses x_n = 1 − cos(π/n), selecting n_γ with x_nγ ≥ γ > x_nγ+1, then continuously varying one edge weight.
- Function placement: The proof splits local functions across two endpoint sets I_0 and I_1 of the constructed graph.The sets are defined near opposite ends of the linear graph, with m = ⌊(n_γ + 1)/3⌋.
- Communication delay: The average function remains unchanged, but communicating between the two sets takes at least d(I_0, I_1)τ time.This lets the lower-bound argument retain the structure of Theorem 2 with Δ = d(I_0, I_1).
- Conclusion: The resulting bounds from Eqs. (46), (48), and (49) establish the desired lower-bound result.
D Proof of the convergence rate of MSPD (Theorem 4 and Theorem 5)
The convergence proof analyzes exact and approximate proximal steps in a primal-dual method, then accelerates gossip because the communication-dependent term is not optimal. The resulting construction reaches an ε-minimizer after balancing communication and subgradient computation costs.
- Exact proximal steps: Under τσλ_1(W) < 1, the exact proximal-step algorithm yields a restricted primal-dual gap.
- Approximate proximal steps: The proof replaces unavailable exact proximal operators with approximate solves whose individual gaps δ_i add to the overall gap.
- Approximate proximal steps: M subgradient steps produce an associated approximation gap governed by the standard strongly-convex subgradient bound.
- Time accounting: After T communication steps and MT subgradient evaluations, the total error combines communication time Tτ with computation time MT.
- Acceleration: The proof identifies the first error term as non-optimal while the second is optimal, motivating accelerated gossip instead of plain gossip.
- Final convergence guarantee: γ(P_K(W)) ≥ 1/4, and the resulting overall time obtains error below ε before yielding an ε-minimizer of the original problem.