Source-linked AI summary
Distributed stochastic optimization with gradient tracking over strongly-connected networks
Ran Xin, Anit Kumar Sahu, Usman A. Khan, Soummya Kar
TL;DR
Distributed stochastic optimization over directed networks must handle inexact data and communication that need not be bidirectional. The paper proposes S-AB, using row- and column-stochastic weights, and shows linear convergence to a neighborhood of the global minimizer for a sufficiently small constant step-size.
Problem
The paper studies distributed optimization when data is inexact and inter-agent communication takes place over directed graphs.
Source: §I · p. 1Method
S-AB combines row- and column-stochastic weights in a distributed stochastic optimization method.
Source: §I · p. 2, §VI · p. 11Results
With a sufficiently small constant step-size, S-AB converges linearly to a neighborhood of the global minimizer.
Source: §I · p. 2, §VI · p. 11Takeaways & Limitations
S-AB is designed for strongly-connected directed graphs without requiring doubly-stochastic weights.
Source: §VI · pp. 10–11
Abstract
from arXiv · showhide
In this paper, we study distributed stochastic optimization to minimize a sum of smooth and strongly-convex local cost functions over a network of agents, communicating over a strongly-connected graph. Assuming that each agent has access to a stochastic first-order oracle ($\mathcal{SFO}$), we propose a novel distributed method, called $\mathcal{S}$-$\mathcal{AB}$, where each agent uses an auxiliary variable to asymptotically track the gradient of the global cost in expectation. The $\mathcal{S}$-$\mathcal{AB}$ algorithm employs row- and column-stochastic weights simultaneously to ensure both consensus and optimality. Since doubly-stochastic weights are not used, $\mathcal{S}$-$\mathcal{AB}$ is applicable to arbitrary strongly-connected graphs. We show that under a sufficiently small constant step-size, $\mathcal{S}$-$\mathcal{AB}$ converges linearly (in expected mean-square sense) to a neighborhood of the global minimizer. We present numerical simulations based on real-world data sets to illustrate the theoretical results.
I. INTRODUCTION
The paper proposes S-AB for stochastic distributed optimization over directed graphs, combining row- and column-stochastic weights without requiring doubly-stochastic weights. Under stated assumptions and a sufficiently small constant step-size, it converges linearly to a neighborhood of the global minimizer.
I. INTRODUCTION
- S-AB addresses distributed stochastic optimization over directed graphs, where data may be inexact and communication need not be bidirectional.The paper frames distributed methods as relevant when data storage and processing exceed a single device's capacity.Source: §I · pp. 1–2
- S-AB uses row-stochastic weights for solution estimates and column-stochastic weights for gradient estimates, without doubly-stochastic weights, making it applicable to arbitrary strongly-connected graphs.Each agent incorporates its local gradient estimate while tracking the global gradient.Source: §I · p. 2
- S-AB converges linearly to a neighborhood of the global minimizer with a sufficiently small constant step-size under the stated smoothness, strong-convexity, and oracle assumptions.The analysis assumes zero-mean, bounded-variance gradient noise.Source: §I · p. 2
- The paper provides explicit norms under which row- and column-stochastic weight matrices contract, then uses them to develop sharp, explicit convergence arguments.The introduction contrasts this analysis with prior work whose arbitrary norms yielded non-sharp convergence bounds.Source: §I · p. 2
- The paper situates its contribution among distributed deterministic and stochastic optimization and gradient-tracking methods for directed graphs.It notes that earlier directed-graph gradient-tracking methods relied on separate eigenvector-estimation iterations, later removed by approaches using both row- and column-stochastic weights.Source: §I · p. 2
II. PROBLEM FORMULATION AND AUXILIARY RESULTS
The problem formulation places agents on a directed graph and assigns each agent a local objective. Strong connectivity and assumptions on the local objectives and stochastic first-order oracle underpin the optimization setup.
II. PROBLEM FORMULATION AND AUXILIARY RESULTS
- Each agent knows only its own local objective, and the problem's optimal solution exists and is unique under strong convexity.The agents are connected by a directed graph whose edges indicate which agent can send information to another.Source: §II · p. 3
- The local objectives are assumed strongly convex and smooth, with smoothness expressed through Lipschitz-continuous gradients.The assumptions apply to every agent's objective.Source: §II · p. 3
- The communication graph is assumed strongly connected, so there is a directed path between every pair of agents.The graph assumption is stated for the agents' communication network.Source: §II · p. 3
- Agents use a stochastic first-order oracle, and the paper imposes standard assumptions on the resulting gradient estimates and noise.The described noise assumptions allow processes dependent on the agent and current iterate; an i.i.d. zero-mean finite-second-moment case is also noted.Source: §II · p. 3
A. The S-AB algorithm
S-AB has each agent maintain two state variables and uses separate row- and column-stochastic weights in its distributed updates. The gradient-estimation state tracks the global gradient, and the deterministic zero-variance case recovers AB or push-pull.
A. The S-AB algorithm
- Each agent maintains two state variables, including a solution estimate and a global-gradient estimator.The variables are in R^p and indexed by iteration.Source: A. The S-AB algorithm · p. 4
- The algorithm uses row-stochastic A and column-stochastic B weights that follow the graph topology.The weights are positive exactly on the graph's communication links.Source: A. The S-AB algorithm · p. 4
- When stochastic-gradient variance is zero, S-AB recovers the AB or push-pull algorithm.The analysis assumes p = 1 for simplicity and can be extended to p > 1 with Kronecker products.Source: A. The S-AB algorithm · p. 4
B. Auxiliary Results
The auxiliary results establish contraction properties for the network weights and bounds used to analyze S-AB. They also relate disagreement among agents to gradient error.
B. Auxiliary Results
- The weight matrices A and B contract in their respective induced norms, with contraction factors σA and σB below 1.The norms are weighted using the non-1 Perron vectors of the row- and column-stochastic matrices.Source: B. Auxiliary Results · pp. 4–5
- Lemma 2 gives bounds for the stochastic-gradient iterates under Assumptions 2 and 4.The supplied passage identifies the lemma and its assumptions but does not show the bound itself.Source: B. Auxiliary Results · p. 6
- The gradient discrepancy is bounded by l√n times the agents’ consensus error.The bound relates h(xk) to the global gradient evaluated at the average iterate.Source: B. Auxiliary Results · p. 6
- For a nonnegative matrix X and positive vector x, Xx < ωx implies that ρ(X) < ω.Source: B. Auxiliary Results · p. 6
III. CONVERGENCE ANALYSIS
The convergence analysis bounds stochastic-gradient, consensus, optimality, and tracking errors. These bounds yield linear convergence to a neighborhood of the optimum for a fixed, sufficiently small step-size.
III. CONVERGENCE ANALYSIS
- Lemma 6 bounds the stochastic-gradient iterates under Assumptions 1–4.Source: §III · p. 6
- With a fixed, sufficiently small step-size, the norm of a vector composed of the three bounded quantities converges linearly to a ball around the optimum.The analysis takes full expectation after deriving conditional bounds for the quantities.Source: §III · pp. 6–7
- Lemma 7 bounds the network’s consensus error.Source: §III · p. 6
- Lemma 9 bounds the gradient-tracking error.Source: §III · p. 7
IV. MAIN RESULT
The main result establishes geometric convergence under a step-size condition that makes ρ(Gα) less than 1. The error bounds decrease as the step-size or gradient-noise variance decreases.
IV. MAIN RESULT
- When the stated step-size condition holds, ρ(Gα) < 1 and convergence is geometric with exponent ρ(Gα).The theorem also states that (I3 − Gα)−1bα has non-negative components.Source: §IV · p. 8
- The proof obtains an upper bound on the step-size by imposing sufficient inequalities on δ1, δ2, and δ3.It uses the condition Gαδ < δ for a positive vector δ to establish ρ(Gα) < 1.Source: §IV · pp. 8–9
- The theorem’s error bounds go to zero as the step-size gets smaller and the gradient-noise variance decreases.Source: §IV · p. 9
V. NUMERICAL EXPERIMENTS
The experiments evaluate S-AB on distributed logistic regression over a directed network, with private local image batches. S-AB performs better than AB in the reported comparison.
V. NUMERICAL EXPERIMENTS
- The experiment uses 20 agents on a directed graph generated by nearest-neighbor rules for logistic regression on 12,000 MNIST images of digits 7 and 8.Each agent holds 600 images, and the local batches are not shared.Source: §V · p. 9
- S-AB samples one data point from each agent’s local batch, while non-stochastic AB uses each agent’s full batch.The comparison includes centralized gradient descent using 12,000 gradients per iteration and centralized SGD using one sampled data point.Source: §V · p. 10
- The evaluation shows network residuals and training and test accuracy; testing uses 2,000 additional images not used for training.The graph topology and residuals are shown in Fig. 1.Source: §V · p. 10, Figure 1 · p. 10, Figure 2 · p. 10
- S-AB performs better than AB in the reported training- and test-accuracy comparison.Fig. 2 plots training accuracy on the left and test accuracy on the right; the horizontal axis is epochs.Source: §V · p. 10, Figure 2 · p. 10
VI. CONCLUSIONS
S-AB applies stochastic gradient descent to distributed data over arbitrary strongly connected graphs, using row- and column-stochastic weights. Under smooth, strongly convex local costs and a sufficiently small constant step-size, it converges linearly to a neighborhood of the global minimizer; real-world dataset simulations illustrate the theory.
VI. CONCLUSIONS
- Each agent samples a data point from its local batch at each iteration to implement stochastic S-AB on distributed data.The simulations use real-world datasets to illustrate the theoretical results.Source: §VI · pp. 10–11
- S-AB uses a two-phase update with row- and column-stochastic weights to handle arbitrary strongly connected graphs.The setup does not require doubly-stochastic weights.Source: §VI · pp. 10–11
- With a sufficiently small constant step-size, S-AB converges linearly to a neighborhood of the global minimizer for smooth, strongly convex local costs.The paper reports real-world dataset simulations to illustrate the theoretical results.Source: §VI · p. 11
APPENDIX
The appendix develops weighted-norm and conditional-expectation bounds used in the convergence proof, including contraction properties for the network mixing matrices.
APPENDIX
- The appendix uses identities for A−A∞ and B−B∞ to relate mixing errors to deviations from their limiting matrices.The stated identities are used in the proofs of (6) and (7).Source: PROOF OF LEMMA 1 · pp. 12–13
- The proof establishes a contraction bound for B−B∞ using its weighted norm and examines the spectral radius of H.The appendix writes H in terms of B−B∞ and the weighting matrix.Source: PROOF OF LEMMA 1 · p. 13
- The proof bounds s1 by controlling conditional-expectation terms involving changes in the gradient and gradient estimator.It then combines bounds on s1, s2, and s3 to complete the proof.Source: PROOF OF LEMMA 9 · pp. 17, 19