Source-linked AI summary
Optimal Distributed Stochastic Mirror Descent for Strongly Convex Optimization
Deming Yuan, Yiguang Hong, Daniel W. C. Ho, Guoping Jiang
TL;DR
The paper asks how to obtain fast convergence for constrained, possibly nonsmooth strongly convex stochastic optimization over distributed networks when Euclidean projections can be difficult. It develops distributed stochastic mirror descent using Bregman divergence, plus an epoch variant. DSMD recovers O(ln(T)/T), while Epoch-DSMD attains O(1/T); the epoch result assumes a finite-radius constraint set.
Problem
The paper addresses convergence rates for constrained, possibly nonsmooth strongly convex objectives over distributed networks when nodes have only stochastic subgradients and Euclidean projections may be challenging.
Source: §1 · pp. 1–2Method
The paper proposes distributed stochastic mirror descent using Bregman divergence and an epoch variant combining DSMD with epoch gradient descent.
Source: §1 · p. 2Results
Takeaways & Limitations
Choosing Bregman divergence lets the algorithms use non-Euclidean geometry, and the epoch variant attains the optimal rate stated for the distributed problem.
Source: §1 · p. 2The Epoch-DSMD convergence results assume the constraint set has finite radius.
Source: §4 · p. 5
Abstract
from arXiv · showhide
In this paper we consider convergence rate problems for stochastic strongly-convex optimization in the non-Euclidean sense with a constraint set over a time-varying multi-agent network. We propose two efficient non-Euclidean stochastic subgradient descent algorithms based on the Bregman divergence as distance-measuring function rather than the Euclidean distances that were employed by the standard distributed stochastic projected subgradient algorithms. For distributed optimization of nonsmooth and strongly convex functions whose only stochastic subgradients are available, the first algorithm recovers the best previous known rate of O(ln(T)/T) (where T is the total number of iterations). The second algorithm is an epoch variant of the first algorithm that attains the optimal convergence rate of O(1/T), matching that of the best previously known centralized stochastic subgradient algorithm. Finally, we report some simulation results to illustrate the proposed algorithms.
1 Introduction
The introduction motivates distributed methods for strongly convex stochastic optimization by the limits of Euclidean projections and asks whether non-Euclidean methods can attain strong convergence rates. It proposes DSMD and an epoch variant to address those questions.
1 Introduction
- Distributed subgradient methods have drawn interest partly because network optimization has applications including sensor networks and smart grids.The introduction also notes strongly convex objectives in engineering and regularization settings.Source: §1 · p. 1
- Euclidean distributed methods can make efficient projections challenging or infeasible for some objectives and constraint sets, motivating mirror descent with Bregman divergence.Bregman divergences include Euclidean distance and KL divergence as special cases.Source: §1 · pp. 1–2
- The paper focuses on constrained, possibly nonsmooth functions that are strongly convex in the non-Euclidean sense, with nodes receiving noisy subgradients.It asks whether a distributed method can recover O(ln(T)/T) and whether a variant can attain O(1/T).Source: §1 · p. 2
- The paper proposes DSMD with an O(ln(T)/T) rate and Epoch-DSMD with an optimal O(1/T) rate for distributed stochastic optimization using only stochastic subgradients.The epoch method combines epoch gradient descent with DSMD.Source: §1 · p. 2
2 Problem Setting and Assumptions
The problem setting uses stochastic local subgradients over a time-varying multi-agent network and expresses non-Euclidean geometry through a Bregman divergence. Its assumptions constrain network communication, objective curvature, and the stochastic oracle.
2 Problem Setting and Assumptions
- The network assumption requires positive self-weights and active-edge weights, a doubly stochastic communication matrix, and connectivity over a bounded time window.The graph and communication matrix may vary over time.Source: §2 · pp. 2–3
- The Bregman divergence is induced by a strongly convex differentiable distance-generating function and is convex in its second argument for fixed first argument.The paper introduces this divergence as central to constructing the algorithms.Source: §2 · p. 3
- The setup assumes non-Euclidean strong convexity for the local objectives relative to the generating function's divergence.The cited remark says smoothness of the generating function can imply Euclidean strong convexity under the stated assumption.Source: §2 · p. 3
- Stochastic subgradients model noisy information that may be easier to calculate and can reduce cost by using one sample among multiple samples.The paper states that the stochastic-subgradient assumption is widely used.Source: §2 · p. 3
3 Distributed Stochastic Mirror Descent
The DSMD section presents a distributed stochastic mirror-descent algorithm and establishes an explicit convergence rate. Its Bregman-based update supports different geometries, including Euclidean and simplex settings.
3 Distributed Stochastic Mirror Descent
- The DSMD section establishes an explicit convergence rate for the proposed distributed stochastic mirror-descent algorithm.The theorem is stated under Assumptions 1–3, with conditions including the step-size schedule and a constrained optimizer.Source: §3 · p. 3
- The update uses stochastic subgradients and Bregman divergence, and the Euclidean setup reduces DSMD to a stochastic distributed projected-subgradient method.For the simplex setup, the divergence is KL and the update becomes distributed stochastic entropic descent.Source: §3 · p. 3
- Unlike standard distributed projected subgradient descent, the simplex update can avoid solving a d-dimensional nonlinear equation at every step.The comparison concerns the Euclidean projection required by the standard method and the DSMD update.Source: §3 · pp. 3–4
- A lemma bounds differences among node estimates, supplying a consensus-related bound used in the theorem proof.The proof combines this lemma with stochastic-subgradient and convexity bounds.Source: §3 · p. 4
4 The Epoch-based Optimal Algorithm
Epoch-DSMD is introduced to improve on the preceding O(ln(T)/T) distributed mirror-descent rate. It attains O(1/T), matching the best previously known centralized stochastic subgradient rate.
4 The Epoch-based Optimal Algorithm
- The convergence analysis assumes that the constraint set W has finite Euclidean radius and finite Φ-diameter.Source: §4 · p. 5
- Epoch lengths double while step sizes halve across successive epochs.Source: §4 · p. 6
- O(1/T) convergence improves on the preceding O(ln(T)/T) rate and matches the best previously known centralized stochastic subgradient rate, without smoothness assumptions.Source: §4 · pp. 5–6
- Epoch-DSMD keeps the step size constant within each epoch, requiring only O(ln(T)) step-size coordinations among nodes.Source: §4 · p. 6
5 Simulation Results
The simulations compare Epoch-DSMD with distributed stochastic methods under simplex and box constraints; Epoch-DSMD converges faster in both reported comparisons.
5 Simulation Results
- Experiments use a time-varying 40-node ring, dimension d = 10, normally distributed i.i.d. subgradient noise, and averages over 50 realizations.At each time instant, half the links are activated randomly.Source: §5 · pp. 6–7
- For the unit simplex, Epoch-DSMD converges faster than MAMD at σ = 0.25 and σ = 0.5.The plots show average error on a log scale versus iterations for three randomly selected nodes.Source: Figure 1 · p. 7, Figure 2 · p. 7, §5 · p. 7
- For the box constraint, Epoch-DSMD converges much faster than the standard distributed stochastic projected subgradient algorithm at σ = 0.25 and σ = 0.5.The box bounds are l_i = −1 and u_i = 1 for all i; the plots show average error on a log scale versus iterations for three randomly selected nodes.Source: Figure 3 · p. 7, Figure 4 · p. 7, §5 · p. 7
6 Conclusion
The paper studies distributed optimization of nonsmooth, strongly convex functions and proposes two non-Euclidean mirror-descent algorithms with distinct convergence-rate guarantees.
6 Conclusion
- The work addresses distributed optimization of nonsmooth, strongly convex functions.Source: §6 · p. 7
- The first proposed algorithm recovers the best previously known rate, while the second attains the optimal convergence rate.Source: §6 · p. 7
- Future directions include asynchronous variants, removing the doubly stochasticity assumption, and adapting accelerated subgradient schemes.Source: §6 · p. 7
A Proof of Lemma 1
The proof applies the update's first-order optimality condition, derives recursive relations for decisions and their average, then sums inequalities to obtain the bound.
A Proof of Lemma 1
- The update's first-order optimality condition, combined with strong convexity of Φ, yields a bound for all v in W.Source: A Proof of Lemma 1 · pp. 7–8
- Doubly stochastic weights give the average-decision evolution; combining it with the decision recursion and transition-matrix convergence yields a relation for t ≥ 2.Source: A Proof of Lemma 1 · p. 8
- Summing the preceding inequalities over t = 1, …, T and all nodes, then using algebra, gives the desired bound.Source: A Proof of Lemma 1 · p. 8