Source-linked AI summary
Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization
S. Sundhar Ram, A. Nedich, V. V. Veeravalli
TL;DR
The paper asks how stochastic subgradient errors affect distributed agents minimizing a sum of convex objectives under a common constraint. It develops a local consensus-based projected subgradient method and proves convergence and performance bounds under error and stepsize conditions.
Problem
The paper studies distributed constrained convex optimization when each agent has only partial, noisy access to its own component function and cannot rely on a central coordinator.
Method
Agents repeatedly average locally received iterates, apply noisy subgradient updates for their local objectives, and project onto the common constraint set.
Results
When mean errors diminish sufficiently fast, agents reach consensus and their iterates converge to a common optimal point with probability 1 and in mean square.
Takeaways & Limitations
The analysis provides explicit mean-performance bounds for bounded-second-moment errors under diminishing and non-diminishing stepsizes.
Takeaways & Limitations
The model assumes synchronous processing and no communication delays, noiseless links, and convex objective functions.
Abstract
from arXiv · showhide
We consider a distributed multi-agent network system where the goal is to minimize a sum of convex objective functions of the agents subject to a common convex constraint set. Each agent maintains an iterate sequence and communicates the iterates to its neighbors. Then, each agent combines weighted averages of the received iterates with its own iterate, and adjusts the iterate by using subgradient information (known with stochastic errors) of its own function and by projecting onto the constraint set. The goal of this paper is to explore the effects of stochastic subgradient errors on the convergence of the algorithm. We first consider the behavior of the algorithm in mean, and then the convergence with probability 1 and in mean square. We consider general stochastic errors that have uniformly bounded second moments and obtain bounds on the limiting performance of the algorithm in mean for diminishing and non-diminishing stepsizes. When the means of the errors diminish, we prove that there is mean consensus between the agents and mean convergence to the optimum function value for diminishing stepsizes. When the mean errors diminish sufficiently fast, we strengthen the results to consensus and convergence of the iterates to an optimal solution with probability 1 and in mean square.
1. Introduction.
The paper studies distributed constrained convex optimization when agents access local objective information imperfectly and exchange iterates locally. It characterizes how stochastic subgradient errors affect mean, almost-sure, and mean-square convergence.
- Motivation: Distributed optimization is useful when agents cannot efficiently or safely share objective functions with a coordinator or with one another.The motivation includes energy limits, privacy constraints, and fault-tolerant distributed processing.
- Problem and contribution: The proposed method addresses constrained minimization of a sum of convex functions known only partially to individual agents through stochastic subgradient information.It extends a distributed unconstrained method to constrained optimization with stochastic subgradient evaluations.
- Algorithm: Agents communicate iterates locally, average received values with their own iterates, apply noisy local subgradient information, and project onto the common constraint set.The information exchange model is synchronous and delayless, and the algorithm has no central coordinator.
- Related work: The analysis covers distributed incremental, consensus, and stochastic subgradient methods, while distinguishing this algorithm because all agents update simultaneously.The paper also distinguishes its local information model from methods where every agent has the complete objective function.
- Results: With diminishing mean errors, diminishing stepsizes yield mean consensus and mean convergence to the optimum function value.When mean errors diminish sufficiently fast, the results strengthen to consensus and convergence of iterates to an optimal solution with probability 1 and in mean square.
2. Problem, algorithm and assumptions.
The paper formulates distributed constrained minimization of a convex sum and uses consensus-weighted, noisy subgradient projection updates under connectivity and weight-balance assumptions.
- Problem: The network contains m agents solving constrained minimization of a sum of local functions over a common constraint set X.Each fi is defined on X, and the problem is assumed convex.
- Problem: Each agent knows its function only partially and obtains a noisy estimate of its subgradient, motivating a distributed and local algorithm.Differentiability is not assumed; subgradients are used where gradients do not exist.
- Algorithm: At every iteration, agents average accessible iterates, move along a noisy local subgradient direction, and project the result onto X.The stepsize is positive, and the projection is Euclidean.
- Assumptions: Connectivity over every Q consecutive graphs must be strong, while weights are nonnegative, row-stochastic, uniformly positive on available links, and column-stochastic.Agents include their own iterates among the available information, and the lower-bound constant need not be known to them.
- Algorithm: The averaging step is consensus-based, allowing every local objective to influence each agent equally in the long run.The update then performs a subgradient iteration for minimizing the local function over X.
3. Preliminaries.
The preliminaries collect convergence tools for random sequences, scalar convolutions, Euclidean geometry, projections, and products of doubly stochastic matrices.
- Euclidean inequalities: Convexity of the Euclidean norm and non-expansiveness of projection onto a nonempty closed convex set support the later distance estimates.These properties apply to convex combinations and projected iterates.
- Scalar sequences: Scalar convolution sequences are introduced and analyzed under limits, limit superiors, and limit inferiors of their input sequences.The convolution uses geometrically decaying weights βk−ℓ.
- Matrix products: The weight matrices are doubly stochastic, and their products converge geometrically toward equal influence across agents under the connectivity assumptions.The limiting matrix has entries associated with uniform consensus.
- Random-sequence convergence: Fatou’s lemma and a Robbins–Siegmund result provide tools for establishing convergence of nonnegative random sequences and summability of associated terms.The latter uses a conditional expectation inequality involving sequences Bk, Dk, Hk, and ζk.
4. Basic relations.
The basic relations prepare the convergence analysis by bounding agent disagreement relative to an auxiliary sequence and relating projected distances to objective-function differences.
- Agent disagreements: The analysis measures disagreement through the distance between each agent iterate wi,k and an auxiliary reference sequence yk.This reference-based measure replaces direct pairwise disagreement norms.
- Agent disagreements: A first lemma estimates the distance between yk and each agent iterate using bounded subgradients and the convergence rate of the weight-matrix products.The auxiliary sequence can be rewritten using the doubly stochastic weights.
- Iterate estimates: Projection non-expansiveness and convexity yield bounds on the auxiliary residual vectors pi,k.The averaged vector vi,k remains in the convex constraint set X.
- Iterate estimates: A second relation bounds distances from vi,k+1 to any z in X together with the function-value difference f(yk) − f(z).The derivation uses the Euclidean projection property, the subgradient inequality, convexity of squared norms, and doubly stochasticity.
- Aggregate relation: Summing the agent-wise relations produces the aggregate inequality that underlies the subsequent convergence results.The argument uses the column-sum property of the weights and subgradient norm boundedness.
5. Convergence in mean.
Under bounded mean-square subgradient errors, the analysis establishes consensus and objective-performance bounds for diminishing and non-diminishing stepsizes. When error means diminish, agents achieve mean consensus and mean convergence to the optimum for diminishing stepsizes, with stronger guarantees under faster decay.
- The analysis assumes uniformly bounded mean-square subgradient errors and, for performance bounds, a bounded constraint set with bounded subgradients.
- For diminishing stepsizes, expected disagreements converge to zero, yielding asymptotic consensus in mean.
- In the strongly connected, fixed-topology case, the error bound scales as m^4 when the relevant connectivity parameter is independent of the number of agents.
- Theorems 5.3 and 5.4 provide comparable error-bound forms, while running averages offer an advantage because convexity supports bounds for all subsequences of function evaluations.
- When error means diminish and stepsizes converge to zero, expected objective values converge to the optimum function value for both iterates and weighted running averages.
- For the error-free case, the suboptimality level diminishes inversely with the square root of the iteration count.
6. Almost sure and mean square convergence.
Under stronger error assumptions and suitable stepsizes, the algorithm progresses from mean consensus to consensus with probability 1 and in mean square, with iterates converging to a common optimum.
- Assumption 5 is stronger than Assumption 4, but they coincide for errors independent across iterations and agents.
- Theorem 6.1 establishes that agents’ disagreements converge to zero with probability 1 and in mean square.
- The stronger consensus result applies to a smaller class of stepsize sequences under the stricter error assumption.
- When the optimal set is nonempty and conditional mean errors diminish, the agents’ iterates converge to the same optimal point with probability 1 and in mean square.
- Theorem 6.2 does not require compactness of the constraint set when the stepsizes and conditional error means are square summable.
7. Implications.
The paper connects stochastic subgradient errors to sampling-based approximations used when agents cannot fully know their objective functions, and identifies conditions ensuring convergence results.
- Stochastic subgradient errors arise when an agent estimates an objective’s subgradient from samples of an incompletely known random environment.
- With independent samples and uniformly bounded gradient variance over the constraint set, the paper’s convergence theorems apply.
- For objectives parameterized by random variables, the Kiefer-Wolfowitz approximation produces errors whose conditional means can be controlled by the sequence β_i,k.
- Choosing β_i,k suitably can satisfy the mean-error conditions required by the convergence theorems.
8. Discussion.
The discussion quantifies performance under stochastic errors, clarifies the conditions for exact consensus and optimization, and identifies boundaries involving stepsizes, communication, timing, and convexity.
- With constant stepsizes, deviation from the error-bound diminishes at rate 1/t after t iterations.
- When expected errors and stepsizes converge to zero sufficiently fast, agents reach consensus and iterates converge to a common optimum with probability 1 and in mean square.
- Non-identical stepsizes preserve disagreement results but do not guarantee minimization of the objective sum rather than a weighted sum.
- The model assumes synchronous, delay-free processing, noiseless communication, and convex objective functions; extensions to asynchronous, noisy, or nonconvex settings remain open.