Source-linked AI summary
Distributed Subgradient Projection Algorithm over Directed Graphs: Alternate Proof
Ran Xin, Chenguang Xi, Usman A. Khan
TL;DR
Distributed optimization over directed networks lacks the symmetry assumed by many constrained methods. This paper introduces D-DPS, which uses surplus consensus to handle directed communication, and proves convergence to the optimum at rate O(ln k/√k).
Problem
Constrained distributed optimization has mainly been studied under undirected communication, leaving the directed-network setting insufficiently addressed.
Method
D-DPS combines projected subgradient updates with surplus consensus and row- and column-stochastic weighting to address directed-network asymmetry.
Results
D-DPS makes agent states converge to a common accumulation state whose objective value reaches the optimum at rate O(ln k/√k).
Takeaways & Limitations
The directed communication restriction does not affect the convergence speed compared with distributed projected subgradient optimization over undirected graphs.
Abstract
from arXiv · showhide
We propose Directed-Distributed Projected Subgradient (D-DPS) to solve a constrained optimization problem over a multi-agent network, where the goal of agents is to collectively minimize the sum of locally known convex functions. Each agent in the network owns only its local objective function, constrained to a commonly known convex set. We focus on the circumstance when communications between agents are described by a \emph{directed} network. The D-DPS combines surplus consensus to overcome the asymmetry caused by the directed communication network. The analysis shows the convergence rate to be $O(\frac{\ln k}{\sqrt{k}})$.
I. INTRODUCTION · II. PROBLEM FORMULATION AND ALGORITHM
The paper addresses constrained distributed convex optimization over strongly connected directed networks, where agents share states rather than objective functions. It introduces D-DPS to combine projection and subgradient updates with directed-network communication.
- I. INTRODUCTION: The formulation is motivated by applications including distributed sensor networks, machine learning, and low-rank matrix completion.These examples are presented as applications of distributed constrained minimization of sums of convex functions.
- I. INTRODUCTION: D-DPS addresses an underexplored setting because prior directed-graph subgradient methods cited here solve unconstrained problems.The introduction contrasts D-DPS with Subgradient-Push, surplus-consensus methods, weight-balancing methods, and DEXTRA.
- I. INTRODUCTION: The main contribution is D-DPS, a protocol for constrained distributed optimization over directed graphs with agent-specific convex feasible sets.The paper emphasizes that extending unconstrained methods to directed, constrained settings is non-trivial because projection is not generally nonexpansive.
- II. PROBLEM FORMULATION AND ALGORITHM: Agents communicate over a strongly connected directed graph, where ordered edges specify which agents can send information to others.Strong connectivity requires a directed path between every ordered pair of agents.
- II. PROBLEM FORMULATION AND ALGORITHM: The target problem minimizes the sum of locally known convex, possibly nondifferentiable functions over a common closed convex set.Each function f_i is known only by agent i, while the feasible set X is shared across agents.
- II. PROBLEM FORMULATION AND ALGORITHM: The analysis assumes bounded subgradients for convex local objectives and a nonempty optimal solution set.Specifically, each subgradient norm is bounded by B_fi, and the common optimization problem has at least one optimal solution.
- II. PROBLEM FORMULATION AND ALGORITHM: The distributed protocol requires agents to exchange only their current states with out-neighbors, not their local objective functions.This preserves the distributed-information structure in which each agent retains exclusive knowledge of its own objective.
A. Algorithm: D-DPS
D-DPS combines state estimates with weighted auxiliary variables to support distributed optimization over directed graphs. Its proof establishes consensus of agent states and convergence of the common accumulation state to an optimal solution.
- A. Algorithm: D-DPS: At each iteration, agents send their state estimates together with weighted auxiliary variables, and update using information from in-neighbors.The state estimate and auxiliary variable are transmitted at iteration k + 1; agent i then updates using received in-neighbor information.
- A. Algorithm: D-DPS: Each agent can set its out-weight b_ij to 1/|N_out_j| using only its out-degree, under a standard directed-graph implementation assumption.The supplied passage specifies this out-weight choice and identifies the assumption as standard in related directed distributed optimization literature.
- A. Algorithm: D-DPS: The algorithm uses a small positive constant ϵ and a non-increasing diminishing step-size α_k satisfying persistence conditions.The passage states that α_k is nonnegative, non-increasing, and subject to persistence conditions, including a finite sum condition.
- A. Algorithm: D-DPS: All agent states converge to a common accumulation state, which achieves the optimal objective value f*.The result states x∞_i = x∞_j and f(x∞) = f* for all agents i and j.
B. Preliminaries
The preliminaries define the row- and column-stochastic weighting matrices underlying the directed graph and establish convergence properties for the augmented matrix M. They also recall projection inequalities for nonempty closed convex sets.
- Weighting-matrix preliminaries: A row-stochastic matrix A and a column-stochastic matrix B represent the same underlying directed graph, and together define the 2n-dimensional weighting matrix M.The matrix M is central to the convergence analysis of D-DPS in Section III.
- Weighting-matrix preliminaries: The entries of M^k converge geometrically, with bounded constants Γ and γ ∈ (0, 1).The geometric rate is stated for all matrix-entry indices i and j.
- Projection preliminaries: For a nonempty closed convex set X, the projection operator satisfies an inner-product inequality and a squared-distance inequality.For y ∈ X and x ∈ R^p, projection reduces the distance to y while accounting for the projection residual.
III. CONVERGENCE ANALYSIS
The convergence analysis recasts D-DPS as a distributed subgradient method with a directed-network weighting matrix and perturbation terms. It establishes consensus among agent estimates, vanishing additional variables, and convergence of the accumulation state's objective value to the optimum.
- Algorithm representation: D-DPS is represented as a distributed subgradient method using weighting matrix M and perturbation g_k instead of a doubly stochastic matrix and subgradient.The compact representation collects the algorithm's weights in matrices A, B, and M.
- Convergence properties: The proof framework establishes both consensus and optimality properties for D-DPS under Assumptions A1 and A2.Consensus concerns agent estimates and additional variables, while optimality concerns the objective value at the accumulation state.
- Consensus property: The consensus analysis shows agent-estimate disagreement converges to zero, each estimate approaches an accumulation state, and every additional variable converges to zero.These claims are stated for all relevant agents and follow from the convergence-proof structure and Lemma 3 under the stated assumptions.
- Optimality property: The optimality analysis shows that the objective value at the accumulation state converges to the optimal value, f*.This conclusion is derived after establishing the consensus property.
A. Perturbation bounds
This section bounds the perturbation term g_k under Assumptions A1 and A2. With a sufficiently small algorithm constant ϵ, the perturbation admits bounded cumulative estimates and converges to zero.
- A. Perturbation bounds: Under Assumptions A1 and A2, Lemma 4 establishes a bounded constant D controlling g_k for all K ≥ 2.The condition requires ϵ ≤ 1−γ^2nΓγ, and α_k is the algorithm’s diminishing step-size.
- A. Perturbation bounds: Lemma 5 shows that the perturbation g_k goes to zero and that its cumulative quantity is bounded by some constant C for all K ≥ 0.The result follows from Lemma 4 under the same assumptions and small-ϵ condition.
- A. Perturbation bounds: The constant C is defined explicitly in terms of n, B, D, γ, ϵ, and Γ.The supplied expression specifies C = nBD(1−γ) 1−(1+2nϵΓ)γ.
B. Consensus in Estimates
The analysis bounds estimate disagreement and perturbations, then combines these bounds to establish consensus for the algorithm under Assumptions A1 and A2. In particular, the relevant limiting quantity tends to zero, showing network-wide consensus.
- B. Consensus in Estimates: Lemma 3 bounds disagreement between agents’ estimates and the accumulation state, while Lemmas 4 and 5 bound the perturbation.
- B. Consensus in Estimates: Combining the disagreement and perturbation bounds establishes the consensus property of the algorithm.
- B. Consensus in Estimates: The algorithm achieves consensus over the network, with the limiting quantity g_k tending to zero.This conclusion is established for the sequence generated by Eq. (5) under Assumptions A1 and A2.
C. Optimality
The optimality analysis builds on consensus among all agents and examines whether the accumulation state converges to an optimal solution. Lemmas 7–9 develop this argument under progressively stated assumptions for sequences generated by Eq. (5).
- C. Optimality: The analysis first establishes that all agents reach consensus, then targets convergence of the accumulation state to an optimal solution.
- C. Optimality: Lemma 7 analyzes the sequence generated by Eq. (5) under Assumptions A1 and A2 for all K ≥ 0.
- C. Optimality: The subsequent optimality statement considers the Eq. (5) sequence relative to any x* ∈ X* under Assumptions A1, A2, and A3.
(a) The sequence
This subsection analyzes the sequence generated by Eq. (5), deriving bounds from column stochasticity and gradient constraints. It establishes monotonicity and convergence properties used to identify an optimal limit point.
- The proof uses the column-sum property of M to derive the accumulation-state relation for the sequence.
- Bounding the terms s1, s2, and s3 with the gradient bound, Lemma 2(a), Lemma 5, and Lemma 8 yields the key sequence inequality.The analysis shows s3 ≤ 0 before combining the three term bounds.
- The resulting relation implies that {r_k} is non-increasing and nonnegative, so it converges to a nonnegative limit.
- Theorem 1 formalizes the behavior of the sequence generated by Eq. (5) under Assumptions A1, A2, and A3 for every agent i ∈ V.
- The proof then uses subsequences, boundedness, and continuity of f to show that a limit point y belongs to X* and is identified with x*.It first establishes infinitely many terms near the optimum and extracts a convergent subsequence.
D. Convergence Rate
With step-size α_k = k^-1/2, the analysis establishes a convergence rate of O(ln k/√k). This rate matches the distributed projected subgradient method for constrained optimization over undirected graphs, so directed communication does not affect convergence speed.
- D. Convergence Rate: The analysis chooses the step-size α_k = k^-1/2 and applies logarithmic inequalities to bound the convergence terms.The first and second terms in Eq. (24) are analyzed separately before combining their orders.
- D. Convergence Rate: The convergence rate matches the distributed projected subgradient method for constrained optimization over undirected graphs, indicating that directed graphs do not reduce convergence speed.This comparison is made with the method cited as.
IV. NUMERICAL RESULTS
Numerical experiments apply D-DPS to constrained logistic regression over a strongly connected, non-balanced directed graph. D-DPS matches competing methods’ convergence order while being suited to constrained problems, and its disagreement and auxiliary variables converge to zero.
- Logistic regression setup: The experiment applies D-DPS to distributed logistic regression with n = 10 agents, m_i = 10 samples per agent, and p = 100 features.The decision variable is restricted to a ball in R^p to avoid overfitting.
- Network topology: The directed communication topology is strongly connected but non-balanced.The network is the digraph shown in Fig. 1.
- Convergence behavior: The agents’ state-estimate disagreements and additional variables converge to zero, consistent with Lemma 6.The experiment plots convergence as a function of k and separately shows disagreement with the accumulation state and the additional variables.
- Algorithm comparison: D-DPS, Subgradient-Push, and WBSD achieve the same convergence-rate order, while D-DPS is better suited to constrained problems.SP and WBSD require an approximate unconstrained formulation using regularization to replace the original constraint.
V. CONCLUSIONS
The paper presents D-DPS for constrained optimization over directed multi-agent networks, using stochastic matrices to address directed-network asymmetry. D-DPS converges to the optimal solution at rate O(ln k / sqrt(k)), while future work considers directed, time-varying graphs with possibly asynchronous exchange.
- V. CONCLUSIONS: D-DPS solves constrained optimization over directed multi-agent networks by collectively minimizing the sum of locally known convex functions.
- V. CONCLUSIONS: D-DPS constructs both row-stochastic and column-stochastic matrices, enabling agents to overcome asymmetry in directed communication networks.
- V. CONCLUSIONS: O(ln k / sqrt(k)): D-DPS converges to the optimal solution at this rate, where k is the number of iterations.
- V. CONCLUSIONS: Future work will address distributed constrained optimization over directed, time-varying graphs with possibly asynchronous information exchange.