Distributed Optimization over Directed Graphs with Row Stochasticity and Constraint Regularity

1 Introduction

• Column-stochastic weights can require agents to know out-degrees or control outgoing weights, making them impractical in broadcast-based networks.Row-stochastic weights let agents choose weights on received information without acknowledgment signals, but can yield nonoptimal solutions without addressing their nonuniform stationary distribution.Source: §1 · p. 2
• The proposed algorithms use row-stochastic weights and concurrently estimate the stationary distribution while updating local optimization states.The agents need different IDs and only an upper bound on network size; the estimation adds no communication overhead.Source: §1 · p. 2
• The unified convergence analysis covers constrained and unconstrained problems with nonidentical, unbounded local sets and no required interior point in their intersection.It assumes regularity of the local constraint sets and allows convex, potentially nondifferentiable costs.Source: §1 · p. 2
• O(ln(t)/t) objective-error convergence is achieved with a step size diminishing at O(1/t).The bound concerns the absolute objective error at each agent’s available local estimate.Source: §1 · p. 3
• Compared with the preliminary work, this paper adds an algorithm variation, relaxes identical compact-set assumptions, and analyzes convergence rates for both algorithms.The introduction states that the proof technique relies on regularity of the local constraint sets.Source: §1 · p. 3

• The objective is the sum of agents’ private convex costs, minimized over the intersection of their local constraint sets.Source: §2 · p. 3
• The algorithm assumes closed convex local sets with a nonempty intersection, regularity, bounded subgradients on U, and a nonempty solution set.Source: §2 · p. 4
• The regularity condition permits nonidentical, unbounded constraint sets and an intersection without interior, while covering identical-set and unconstrained cases.The passage also gives compact sets with nonempty-interior intersection and hyperplanes or half-spaces as examples.Source: §2 · p. 4
• A fixed, strongly connected directed graph uses locally chosen row-stochastic weights, without requiring column or double stochasticity.Each agent controls its own row of the weight matrix.Source: §2 · p. 4
• Algorithm 1 scales each private-cost subgradient by z_ii(t), while a consensus iteration estimates the left normalized Perron eigenvector of W.If agents know the corresponding eigenvector entries in advance, the estimation iteration is unnecessary.Source: §2 · pp. 4–5
• Algorithm 2 is a variation that evaluates each agent’s subgradient at its current local iterate; an in-depth comparison with Algorithm 1 is out of scope.Interchanging optimization and consensus steps can often improve convergence speed to a solution neighborhood with constant step size.Source: §2 · p. 5
• Diminishing step sizes are used for convergence, while the convergence-rate analysis allows a less restrictive step-size assumption.Source: §2 · p. 5

3 Basic relations and convergence results

• The weight-matrix powers converge geometrically to 1π^T, where π is the positive normalized left Perron eigenvector.The convergence rate λ lies between |λ2(W)| and 1.Source: §3 · p. 5
• For both algorithms, the analysis bounds estimate evolution and disagreement using the step sizes and accumulated projection errors.The section relates these errors through bounds involving γ(t), which combines step-size and projection-error effects.Source: §3 · p. 7
• Constraint-set regularity and a nonincreasing step-size sequence yield a common evolution relation used to prove convergence for both algorithms.The relation is stated uniformly over feasible points in X.Source: §3 · pp. 7–8
• Both algorithms converge to the same optimal solution at every agent under Assumptions 1–5.Theorem 4 states that there exists an optimal solution x* such that each agent’s estimate converges to it.Source: §3 · p. 8
• The proof establishes that projection errors vanish, enabling the agents’ estimates to approach a feasible optimal solution.The argument also shows that the objective values along a subsequence of feasible comparison points approach the optimum.Source: §3 · pp. 8–9

4 Rate of convergence

• The analysis accommodates nonidentical, unbounded constraint sets and cases where the global constraint set has empty interior.Because the agents’ estimates and weighted average need not be feasible, local analysis around an optimum does not readily apply.Source: §4 · p. 9
• The convergence bound combines the distance from each agent’s local estimate to a feasible point with the global objective error at that point.The feasible comparison point is not directly available to each agent, whereas its local estimate can be computed locally and may be infeasible.Source: §4 · p. 9
• The O(ln t/t) rate also holds for constrained problems with nonidentical sets, even when the local estimates are infeasible.The paper states this rate is also achieved by existing distributed methods in narrower settings.Source: §4 · p. 11
• The spectral gap 1 − |λ2(W)| affects the constants in the convergence bounds.The paper notes that strong connectivity matters and suggests step sizes O(n^-σ), for example σ = 2 or 3, to lower the order of E(t).Source: §4 · p. 11

5 Numerical example

• The example uses ℓ1-regularized logistic loss with r=500, m=50, q=36, and σ=50, and its local constraint sets are unbounded with an empty-interior intersection.The data and constraints are generated from normally distributed random numbers and distributed across the nodes.Source: §5 · pp. 11–12
• For comparison, Algorithms 1 and 2 use α(t)=n^-3(t+1)^-0.8, while DPS-(a) and DPS-(b) use α′(t)=n^-2(t+1)^-0.8.The step sizes differ by a factor of n because the proposed algorithms scale subgradients by π_i^-1.Source: §5 · p. 12
• Both Algorithms 1 and 2 converge to x*, while DPS-(a) and DPS-(b) fail; deleting link 1 → 2 preserves convergence but slows it.The modified network remains strongly connected, but its spectral gap is reduced.Source: §5 · p. 12
• The scaled theoretical bound and |F(˜xi(t))−F*| have similar convergence rates, although the bound is very loose.The paper attributes the looseness to rough estimates of Ci; reduced network connectivity also slows convergence.Source: §5 · p. 12

6 Conclusions and discussion

• The two modified DPS algorithms require only a row-stochastic weight matrix, and their convergence and convergence rates are studied.The analysis covers constrained and unconstrained problems, with local sets that may be bounded or unbounded and identical or nonidentical.Source: §6 · p. 12
• Figures 2 and 3 depict accuracy for Algorithms 1, 2, and DPS methods, and objective errors at the local estimates, respectively.Figure 3 also includes a scaled version of the theoretical upper bound.Source: Figure 2 · p. 12, Figure 3 · p. 12
• The augmented iteration for estimating the stationary distribution can also adjust gradient magnitudes in other consensus-and-gradient algorithms.The paper reports simulation observations for modifications of methods in and a linearly convergent algorithm under strong convexity in [47].Source: §6 · p. 12
• The convergence analysis may be adapted to relax compactness requirements or impose regular constraints in other projected or subgradient methods, including time-varying networks with fixed delays.The discussion cites and [34] as examples.Source: §6 · p. 13