PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Random Projection Algorithm for Convex Optimization

Soomin Lee, Angelia Nedich

arXiv:1211.5611v3math.OCeess.SY

TL;DR

The paper tackles fully distributed constrained convex optimization when agents have private, incomplete, or prohibitively large constraint sets. It proposes DRP, which combines local estimate averaging, gradient updates, and random component projections, and proves almost-sure convergence for the basic and mini-batch variants. Experiments apply the methods to distributed SVMs and report fast convergence.

  • Problem

    Distributed constrained optimization is needed when agents privately hold different objectives and constraints, especially when the full constraint set is unavailable or expensive to project onto.

  • Method

    DRP combines local communication and weighted estimate averaging with local gradient updates and random projections onto sampled constraint components.

  • Results

    The paper establishes almost-sure convergence of all agents to a common point in the optimal set, including for a mini-batch projection variant.

  • Takeaways & Limitations

    DRP applies to distributed problems with unknown or computationally prohibitive whole constraint sets, and experiments demonstrate fast convergence on text-classification SVMs.

  • Takeaways & Limitations

    The analysis assumes gradients are evaluated without errors; stochastic gradient errors are left for future work.

Abstract

from arXiv · show

Random projection algorithm is an iterative gradient method with random projections. Such an algorithm is of interest for constrained optimization when the constraint set is not known in advance or the projection operation on the whole constraint set is computationally prohibitive. This paper presents a distributed random projection (DRP) algorithm for fully distributed constrained convex optimization problems that can be used by multiple agents connected over a time-varying network, where each agent has its own objective function and its own constrained set. With reasonable assumptions, we prove that the iterates of all agents converge to the same point in the optimal set almost surely. In addition, we consider a variant of the method that uses a mini-batch of consecutive random projections and establish its convergence in almost sure sense. Experiments on distributed support vector machines demonstrate fast convergence of the algorithm. It actually shows that the number of iteration required until convergence is much smaller than scanning over all training samples just once.

I. INTRODUCTION

The paper addresses distributed constrained convex optimization when information and constraints are private, incomplete, or expensive to project onto. It proposes DRP, combining local communication, gradient updates, and random projections, with convergence for agents in changing networks.

  • Distributed sensor, wireless, and peer-to-peer network problems can be formulated as convex constrained minimization tasks.
  • Each agent has a private convex objective and closed convex constraint set, while no single location stores complete problem information.Memory, computational, privacy, mobility, and link-failure concerns motivate distributed, adaptive communication.
  • The method targets constraint sets formed by intersections of finitely many simple convex sets, avoiding projection onto the entire set.Whole-set projection can be computationally prohibitive when many components represent training samples.
  • DRP combines local estimate averaging with gradient descent and projection onto a randomly selected local constraint component.Agents maintain individual iterates and reveal or sample constraint components through random realizations.
  • The paper extends random-projection optimization to distributed settings and analyzes both the basic and mini-batch variants.
  • Under the proposed updates, agents eventually reach a common optimal solution despite the distributed network and projection-related challenges.

C. Assumptions on Random Set Process

The analysis assumes repeatedly sampled local constraints, suitable convexity and regularity, and a sufficiently connected, doubly stochastic time-varying network. Standard projection, matrix-convergence, and supermartingale results support the almost-sure convergence proofs.

  • Each agent samples local constraint components independently and identically, with every component having positive selection probability.The sampling sequences are independent of the initial estimates, and agents may use uniform probabilities when all components are available.
  • The time-varying communication graphs must remain sufficiently connected so information from all agents influences every iterate.The stated connectivity assumption is strong connectivity over bounded communication windows.
  • Weight matrices are doubly stochastic, respect the network topology, and assign uniformly positive weight to available neighbor information.These conditions support long-run equal influence and consensus among agents.
  • The proof uses nonexpansive projection properties, convergence of products of stochastic matrices, and a supermartingale convergence theorem.These tools establish limiting behavior for feasibility, consensus, and error sequences.

IV. BASIC RELATIONS

The basic relations organize the convergence proof by tracking progress toward optimality, feasibility, and consensus. They combine projected-gradient inequalities with conditional-expectation arguments over the algorithm’s history.

  • The analysis begins with a critical relation describing decreases in a distance-based quantity as the algorithm progresses.
  • Weighted averages of agent iterates are shown to approach the global constraint set asymptotically.
  • The disagreement among agents’ weighted averages diminishes with the number of iterations.
  • Conditional expectations are taken over the algorithm’s history before the current random constraint indices are realized.Given this history, the generated iterates and weighted averages are determined.
  • A projected-gradient lemma relates distances before and after a gradient step to quantify progress toward an optimizer over a feasible set.The relation applies to convex differentiable functions with Lipschitz-continuous gradients.

B. Projection Estimate

The projection estimate shows that agents’ averaged iterates approach the global constraint set almost surely, with squared-distance errors summable over time. This estimate alone does not establish common accumulation points or optimality.

  • Projection Estimate: The sequences {vi(k)} approach the constraint set X almost surely.The result concerns distance to X and does not require accumulation points to exist in X.
  • Projection Estimate: The sum of all squared distances to X over time is finite almost surely.Thus, the distances tend to zero as k →∞.
  • Projection Estimate: The estimate relies on doubly stochastic weights, bounded gradients on X, and the supermartingale theorem under the stated assumptions.The proof combines conditional distance relations with stepsize conditions and a time-delayed supermartingale argument.
  • Projection Estimate: Approach to X alone does not guarantee common accumulation points across agents or optimality of those points.A separate disagreement result is needed to establish shared accumulation behavior.

C. Disagreement Estimate

The disagreement estimate analyzes the agents’ deviations from their instantaneous average and treats projection and gradient updates as perturbations of a consensus process. Under diminishing weighted perturbations, disagreements vanish almost surely.

  • Disagreement Estimate: Agent disagreement is measured by ∥vi(k)−¯v(k)∥, the distance between each estimate and the instantaneous average.Here ¯v(k) is the average of the agents’ weighted estimates.
  • Disagreement Estimate: Lemma 6 states that a perturbed consensus protocol reaches consensus when its perturbations are sufficiently small.Lemma 7 applies this result to the agents’ weighted estimates under the stated assumptions.
  • Disagreement Estimate: The update can be written as xi(k + 1)=vi(k)+ei(k), where ei(k) is the projection-gradient perturbation.The perturbation is defined by ei(k)=xi(k + 1)−vi(k).
  • Disagreement Estimate: The perturbations are summable after weighting by the stepsizes: P∞ k=0 αk∥ei(k)∥<∞ almost surely.This relation is used to apply a perturbed-consensus convergence result.

V. ALMOST SURE CONVERGENCE OF DRP ALGORITHM

Under Assumptions 1–5, a nonempty optimal set, and the required stepsize conditions, the DRP iterates of every agent converge almost surely to one common random point in the optimal set.

  • V. ALMOST SURE CONVERGENCE OF DRP ALGORITHM: The proof links approach to X, diminishing disagreement, and an iterate relation analyzed with the supermartingale theorem.These components connect feasible accumulation behavior to optimal solutions.
  • V. ALMOST SURE CONVERGENCE OF DRP ALGORITHM: Under the stated assumptions and stepsize conditions, the iterates converge almost surely to a random point in the optimal set X ∗.The optimal set is assumed to be nonempty.
  • V. ALMOST SURE CONVERGENCE OF DRP ALGORITHM: All agents converge to the same limit x⋆∈X ∗: lim k→∞xi(k)=x⋆ for all i∈V almost surely.The shared limit follows after combining consensus, feasibility, and optimality arguments.
  • V. ALMOST SURE CONVERGENCE OF DRP ALGORITHM: The convergence argument uses bounded gradients on X and convexity of the objective functions and norm.The projected averages remain in X, enabling the bounded-gradient assumption in the analysis.

VI. DISTRIBUTED MINI-BATCH RANDOM PROJECTION ALGORITHM

The mini-batch variant applies several independent random projections consecutively after each distributed gradient step. Under the same assumptions and stepsize conditions, its iterates also converge almost surely to a common point in the optimal set.

  • VI. DISTRIBUTED MINI-BATCH RANDOM PROJECTION ALGORITHM: Several projections may yield a larger infeasibility reduction than a single projection at each iteration.This is the stated motivation for extending the DRP method.
  • VI. DISTRIBUTED MINI-BATCH RANDOM PROJECTION ALGORITHM: Each agent performs successive random projections on b independently sampled constraint components after forming vi(k)−αk∇fi(vi(k)).The mini-batch samples are mutually independent and independent of past realizations.
  • VI. DISTRIBUTED MINI-BATCH RANDOM PROJECTION ALGORITHM: Mini-batches are useful when each local constraint set has many components, because several samples can reduce iterate infeasibility more effectively.For about 10^4 simpler sets, the paper contrasts one sample with 100 samples as approximations of the full intersection.
  • VI. DISTRIBUTED MINI-BATCH RANDOM PROJECTION ALGORITHM: Under Assumptions 1–5, a nonempty optimal set, and the required stepsize condition, the mini-batch iterates converge almost surely to a random point in X ∗.All agents share the same limit: lim k→∞xi(k)=x⋆ for all i∈V almost surely.

VII. APPLICATION - DISTRIBUTED SUPPORT VECTOR MACHINES (DRSVM)

The paper applies the DRP algorithm and its mini-batch variant to Support Vector Machines, introducing SVMs and reporting numerical results on several datasets.

  • The section applies the DRP algorithm to Support Vector Machines.
  • It introduces SVMs before reporting numerical results on datasets.
  • The experiments evaluate both the DRP algorithm and its mini-batch variant.

A. Support Vector Machines

The SVM application distributes classification constraints across agents and evaluates DRP under different projection batches, network topologies, and agent counts. The experiments show that mini-batching reduces iterations and can reach good solutions before scanning all training samples once.

  • Support Vector Machines: SVM classification uses slack-variable constraints for each labeled example, allowing linearly non-separable cases.
  • Support Vector Machines: DRP partitions the SVM constraints among agents, with each local constraint corresponding to inequalities from assigned data examples.
  • Simulations: The experiments compare batch sizes b = 1, 100, and 1000, with b = 1 corresponding to the basic DRP algorithm.
  • Simulations: The simulations use three binary text-classification datasets, equally divide constraints among agents, and reserve 20% of data for testing.
  • Simulations: The experiments were conducted without a real networked environment, so communication delays and node or link failures were not considered.
  • Simulations: More projections per iteration require fewer convergence iterations across agent counts, while the clique generally converges no slower than the 3-regular expander graph.
  • Simulations: 4,800 projections and 48 gradient updates suffice for astro-ph with m = 6 and b = 100, versus 62,369 training data points.
  • Simulations: CRP and ten-agent DRP achieve almost identical objective values, although the b = 100 plot has a smaller final objective because the iteration-1000 stepsize is too small.

APPENDIX

The appendix extends the convergence analysis to the mini-batch random projection method. It transfers the key non-expansiveness and conditional-expectation relations from the single-projection analysis to establish almost sure convergence.

  • Successive projections onto randomly selected constraint components remain non-expansive relative to points in the feasible intersection.
  • The mini-batch proof starts from a basic iterate relation under the problem assumptions and bounds its coefficients using Aτ and Bτ.
  • The conditional-expectation analysis conditions on the algorithm history through time k − 1 while excluding the current random projection indices.
  • Lemma 5 and Lemma 7 remain valid for mini-batch iterates after applying the projection-distance and error bounds.
  • The proof uses the projection of the intermediate iterate onto the global feasible set and the non-expansiveness of each sampled projection.
  • The resulting relations reproduce the inequalities needed for the original convergence argument, completing the mini-batch proof.

4) Details of the Proof of Proposition 2:

The proof of Proposition 2 combines the preceding mini-batch inequalities with the single-projection convergence argument. Under the stated conditions, this yields almost sure convergence of the mini-batch method.

  • The proof combines the established mini-batch relations for projected iterates and network averaging.
  • Because αk → 0, the proof chooses a sufficiently large index so that 2αkL ≤ 3.
  • The combined inequalities recover the relation used in the proof of Proposition 1.
  • The mini-batch method therefore converges almost surely under the proposition's assumptions.

B. Projection onto the Intersection of Two Half-spaces

The projection onto the intersection of two half-spaces is handled by dividing the problem into four cases according to constraint satisfaction and the sign of v_i. The resulting projection may be v itself, a projection onto one hyperplane, or a projection onto both hyperplanes.

  • Notation: The notation uses a∈R^d, b∈R, and w_i for the i-th component of w, while e_i has one in coordinate i and zeros elsewhere.These definitions support the projection onto the hyperplane w_i=0.
  • Case analysis: The two half-spaces divide R^d into four cases based on whether ⟨a, v⟩≤b and whether v_i≥0.When both conditions hold, v already lies in the intersection, so w=v.
  • Case analysis: When ⟨a, v⟩>b and v_i<0, the projection lies on the intersection of ⟨a,w⟩=b and w_i=0.Finding this projection is formulated as an optimization problem and solved using a Lagrangian with multipliers θ and ζ.
  • Projection computation: For the two-hyperplane case, differentiating the Lagrangian and imposing primal feasibility yields the projection formula.The resulting coordinates set the i-th component to zero and adjust the other components using a_jθ∗.
  • Projection computation: When ⟨a,v⟩>b and v_i≥0, v is projected either onto ⟨a,w⟩=b or onto its intersection with w_i=0.The projection onto the first hyperplane is denoted by ˆw; its feasibility with respect to the second half-space determines the alternative.
Loading 1211.5611v3…