ADD-OPT: Accelerated Distributed Directed Optimization

Problem setting

• The objective is for networked agents to minimize the sum of local functions using information exchanged with neighboring agents.Each agent knows only its own objective function.Source: §I · p. 1

Prior work

• For strongly-convex objectives with globally Lipschitz-continuous gradients, prior undirected methods can achieve linear convergence.The paper contrasts these results with the more difficult directed-graph setting.Source: §I · p. 1

Directed-network challenge

• Directed graphs may lack doubly-stochastic weights, so methods designed for undirected networks do not directly apply.Row-stochasticity supports consensus, while column-stochasticity ensures equal contribution of local gradients.Source: §I · p. 1

Prior work

• Existing gradient-based directed methods using diminishing step-sizes converge relatively slowly at O(√(ln k/k)).The cited methods include Gradient-Push and directed distributed gradient descent.Source: §I · p. 1

Gap and contribution

• DEXTRA achieves linear convergence on directed graphs but requires a step-size interval whose positive lower bound may require global knowledge.ADD-OPT is proposed to remove this lower-bound restriction.Source: §I · p. 1

Assumptions

• ADD-OPT targets strongly-connected digraphs under strongly-convex, smooth local objectives, with agents knowing their out-degrees.The optimal solution is assumed to exist, be bounded, and be unique.Source: §II · p. 2

State variables

• Each agent maintains three vector variables and a scalar variable indexed by the iteration counter.The excerpt identifies the state variables as x, additional vector states, and y.Source: A. ADD-OPT Algorithm · p. 2

Communication

• At each iteration, agents assign weights to their states and send the weighted information to their out-neighbors.The weights are associated with directed communication links.Source: A. ADD-OPT Algorithm · p. 2

Updates

• Each agent receives information from its in-neighbors and updates its local state using the received values.The step-size α is a positive number whose admissible interval is established later.Source: A. ADD-OPT Algorithm · p. 2

Initialization

• The algorithm initializes the scalar states with y_i^0 = 1 and permits arbitrary initial vectors.Under strong connectivity, the scalar states remain nonzero.Source: A. ADD-OPT Algorithm · p. 3

Matrix representation

• For analysis, the agent updates are rewritten in matrix form using a weighted adjacency matrix and Kronecker products.The resulting matrix A is column-stochastic, and Y_k is invertible under the stated graph and initialization conditions.Source: A. ADD-OPT Algorithm · p. 3

Consensus interpretation

• Assuming the generated sequences converge, the limiting state satisfies a relation that places the agents’ estimates in a consensus subspace.The argument uses the limiting relation for y and the resulting structure of x.Source: B. Interpretation of ADD-OPT · p. 3

Optimality interpretation

• Summing the update relations yields the optimality condition for the distributed problem once the limiting state is in consensus.Thus the limiting estimate both reaches consensus and solves the optimization problem.Source: B. Interpretation of ADD-OPT · p. 3

Relation to DEXTRA

• DEXTRA and ADD-OPT differ in the weighting matrices used for the x-update.ADD-OPT replaces (I + A) with 2A and replaces the modified matrix with A^2.Source: C. ADD-OPT and DEXTRA · p. 3

Step-size comparison

• ADD-OPT has a zero greatest lower bound for its step-size, whereas DEXTRA’s greatest lower bound is strictly positive.The paper links DEXTRA’s positive lower bound to its inability to use the identity matrix without eliminating communication.Source: C. ADD-OPT and DEXTRA · pp. 3–4

III. MAIN RESULT

• ADD-OPT’s key linear relation reduces convergence analysis to the spectral radius of G and the decay of H_k.If ρ(G)<1 and H_k decays linearly, the error sequence converges linearly.Source: §III · p. 5
• ρ(G_α)<1 when the step-size satisfies α ∈ (0, ᾱ).The result follows after characterizing the step-sizes for which G_α can have an eigenvalue equal to one.Source: §III · p. 5
• Although convergence holds for sufficiently small step-sizes, the upper bound ᾱ depends on global knowledge and may require distributed estimation.Agents must also agree on the same step-size, which may be pre-programmed.Source: §III · pp. 5–6
• The auxiliary bounds use constants γ_1, γ_2, and γ with values below one to control the relevant matrix powers and error terms.Lemma 5 combines the decay properties associated with Y^k and G.Source: §III · p. 5
• Under the stated assumptions and α ∈ (0, ᾱ), ADD-OPT’s sequence z^k converges exactly to the unique optimizer z* at a linear rate.The theorem provides a positive constant M bounding the convergence error for every iteration k.Source: §III · pp. 5–6
• The analysis yields ||t^k||_2 = O(μ^k) for any μ ∈ (γ,1), which supplies the paper’s linear convergence characterization.The theorem transfers this bound to the optimizer sequence through the stated relation between ||z^k−z*||_2 and ||t^k||_2.Source: §III · p. 6

• Lemma 9 states that fixed-step gradient descent on a smooth, strongly-convex function contracts distance to the optimizer by a fixed ratio.For 0 < α < 2/(nl), the ratio is η = max(|1 − αnl|, |1 − αns|).Source: §IV · pp. 6–7
• Lemma 7 derives iterative equations governing the average sequences xk and wk.Source: §IV · p. 6
• The proof uses the initial condition w0 = ∇f0, equivalently w0 = g0, to establish the stated relation.Source: §IV · p. 6
• Lemma 8 provides inequalities derived from Eq. (24), including a bound involving the convergence of Yk toward Y∞.Source: §IV · pp. 6–7

• The proof bounds consensus, optimization, and gradient-tracking errors linearly in terms of their past values and ∥xk−1∥2.The recursion coefficients are entries of G and Hk−1.Source: §V · p. 7
• Step 1 bounds the disagreement ∥xk − Y∞xk∥ using the update relation and Lemma 7(b).Source: §V · p. 7
• Step 2 bounds ∥xk − z∗∥2 by interpreting x+ = xk−1 − αhk−1 as a centralized gradient-descent step.The contraction follows from the smooth, strongly-convex gradient-descent result in Lemma 9.Source: §V · p. 7
• The analysis uses Lipschitz continuity to control gradient differences and related error terms.Source: §V · p. 7
• Step 4 combines the bounds from the preceding steps to complete the convergence proof.Source: §V · p. 8

• The experiments analyze ADD-OPT on a distributed logistic regression problem over a directed graph.Source: §VI · p. 8
• Each agent has local feature-label pairs, and its objective function is defined from those training examples.Source: §VI · p. 8
• The experimental setting uses n = 10 agents, mi = 10 examples per agent, and p = 3 features.Source: §VI · p. 8

A. Convergence rate

• The experiment compares ADD-OPT, DEXTRA, Gradient-Push, Directed-Distributed Gradient Descent, and Weight Balanced-Distributed Gradient Descent.Source: A. Convergence rate · p. 8
• The network topology is the strongly-connected directed network shown in Fig. 1.Source: A. Convergence rate · p. 8, Figure 1 · p. 8
• ADD-OPT and DEXTRA have a fast linear convergence rate, while the other methods are sub-linear.Source: A. Convergence rate · p. 8, Figure 2 · p. 8

• 0.2 is approximately DEXTRA’s greatest lower-bound step-size, whereas ADD-OPT works with sufficiently small step-sizes.Source: B. Step-size range · p. 8
• 8.7/9.57 is the estimated theoretical upper bound for ADD-OPT’s step-size under the stated parameter setting.Source: B. Step-size range · p. 8
• 1.12 is the practical upper bound observed for ADD-OPT’s step-size in the given setting.Source: B. Step-size range · p. 8
• 1/(10l) is the estimated step-size bound when τ = ϵ = y = y− = 1, σ = 0.9, and s ≤ l.Source: B. Step-size range · p. 8

• α = 0.3 gives the best observed convergence rate because it minimizes the spectral radius ρ(Gα).The residual at the 200th iteration is also evaluated against α.Source: C. Convergence rate vs. step-sizes · p. 8
• Fig. 3 compares ADD-OPT and DEXTRA according to their step-size ranges.Source: Figure 3 · p. 9
• Fig. 4 presents the range of ADD-OPT’s step-size.Source: Figure 4 · p. 9
• ρ(Gα) < 1 approximately for α in (0, 0.3), matching the theoretical step-size bound.Source: C. Convergence rate vs. step-sizes · p. 9
• The spectral radius satisfies ρ(G) = 1 at α = 0 and α = α, and ρ(G) < 1 for α ∈ (0, α).Source: C. Convergence rate vs. step-sizes · p. 9

• Residuals decrease faster from Ga to Gb to Gc as the number of edges increases.Source: D. Convergence rate vs graph sparsity · p. 9
• More communication channels are associated with faster convergence in the compared directed graphs.Source: D. Convergence rate vs graph sparsity · p. 9, §VII · p. 9
• Fig. 6 shows three examples of strongly-connected directed graphs used in the sparsity experiment.Source: Figure 6 · p. 9, D. Convergence rate vs graph sparsity · p. 9