Asynchronous parallel primal-dual block coordinate update methods for affinely constrained convex programs

1 Introduction

• The proposed method addresses affinely constrained multi-block convex programs with a nonseparable objective, a setting few existing BCU works had studied.The problem class includes basis pursuit, portfolio optimization, and dual SVM formulations.Source: §1 · p. 2, §1.1 · p. 2, §1.2 · p. 3

1.2 Block coordinate update

• BCU updates one variable block at a time, making a sequence of smaller subproblems rather than updating the full variable.Prior BCU work chiefly addressed unconstrained or block-separably constrained problems; only a few works studied nonseparable objectives with affine constraints.Source: §1.2 · p. 3

1.3 Asynchronization

• Asynchronous methods avoid the idle waiting of synchronous workers, but outdated information complicates convergence analysis; most existing analyses cover unconstrained or block-separable constraints.Only a few cited exceptions concern separable problems with special affine constraints.Source: §1.3 · p. 3

1.4 Related works

• Prior cyclic primal-dual BCU methods can diverge without additional assumptions, while the proposed randomized method targets convergence under convexity.The cited remedies for cyclic methods include strong convexity, correction steps, random permutations, and Jacobi-type updates.Source: §1.4 · pp. 4–5

1.5 Contributions

• The paper proposes the first asynchronous primal-dual method for affinely constrained problems with a nonseparable objective; on one node, it becomes a serial randomized primal-dual BCU.With convexity and a primal-dual solution, objective values converge in probability to the optimum, constraint residuals to zero, and an ergodic rate is established; delayed gradients require a delay-dependent stepsize for analogous asynchronous results.Source: §1.5 · p. 5
• Experiments on basis pursuit, quadratic programming, and SVM report serial BCU performance comparable to or better than state-of-the-art methods and better speed-up than the synchronous counterpart.The paper reports these comparisons without supplying numerical values in the cited passages.Source: §1.5 · p. 5

1.6 Notation and Outline

• The paper defines notation for block variables, norms, and saddle points, and outlines algorithms, convergence analysis, experiments, and conclusions across the remaining sections.A function is called proximable when its proximal operator has a closed-form solution or is easy to compute.Source: §1.6 · p. 6

2 Algorithm

• The method applies block coordinate updates to the augmented Lagrangian formulation of the constrained problem.The multiplier is the augmented-Lagrangian dual variable, and β is a penalty parameter.Source: §2 · p. 6

2.1 Non-parallel method

• Each serial iteration uniformly samples one of m blocks, updates it while fixing the others, then updates the multiplier; randomization supports convexity-based convergence and parallelization.Linearizing the smooth objective term eases the block subproblem, and proximable terms permit simple updates.Source: §2.1 · pp. 6–7

2.2 Async-parallel method

• In parallel, workers compute block gradients while the master updates primal and dual variables; outdated gradients may be used, while the master’s residual and multiplier remain current.The master also computes gradients when no worker results arrive, keeping nodes working; the method may waste computation if workers produce gradients faster than the master can use them.Source: §2.2 · pp. 7–8
• The practical load-balance assumption makes gradient computation roughly at least p − 1 times the cost of the corresponding master updates, but the theoretical analysis does not require it.With one node, the method reduces to Algorithm 1; it does not reduce to the synchronous counterpart, which updates multiple blocks per step and generally needs a larger proximal weight.Source: §2.2 · pp. 7–8

3 Convergence analysis

• Algorithm 2 assigns workers to compute gradients at randomly selected blocks from read variable values, while the master updates primal and dual variables and the residual.The master uses a newly received block gradient or a freshly sampled block gradient in its update.Source: §3 · p. 9

3.1 Convergence results of Algorithm 1

• Algorithm 1’s convergence analysis supplies the basis for the async-parallel analysis, which extends the bounds to account for delayed gradients.The serial method is described as a special case of [14], with an easier and more succinct convergence analysis.Source: §3 · p. 8, §3.1 · p. 9
• Algorithm 1’s objective value converges in probability to the optimum, while its constraint residual converges in probability to zero.The analysis assumes a solution exists and imposes gradient Lipschitz conditions.Source: §3 · pp. 8–9, §3.1 · pp. 12–13
• The averaged point from Algorithm 1 has a sublinear ergodic convergence rate, and an iteration bound can guarantee an (ϵ, σ)-solution.An (ϵ, σ)-solution bounds the probabilities of objective error and constraint-residual error exceeding ϵ by σ.Source: §3 · p. 8, §3.1 · pp. 13–14

3.2 Convergence results of Algorithm 2

• Algorithm 2 has the same convergence-in-probability and ergodic-rate results under the stated delay-dependent conditions.The proof handles delayed gradients by bounding their cross terms; the delay is assumed uniformly bounded.Source: §3 · p. 8, §3.2 · pp. 15, 17, 18
• When τ = o(√m), delay only weakly affects the proximal-matrix settings; with equally fast nodes, the analysis indicates nearly linear speed-up on O(√m) nodes.At τ = 0, Algorithm 2 reduces to Algorithm 1 and their convergence results coincide.Source: §3.2 · p. 18

4.1 Basis pursuit

• Algorithm 1 performs significantly better than LALM and comparably to YALL1 on basis pursuit; its performance is only weakly affected by β.With β = √q, it is slightly better than YALL1 at q = 200 and performs equally well at q = 300 and 400.Source: §4.1 · p. 19, Figure 1 · p. 19, Figure 2 · p. 20

4.2 Quadratic programming

• With delay-dependent stepsizes, larger delays slow Algorithm 2, but using the same P_i matrices across delays leaves its convergence speed hardly affected.The authors suggest setting P_i according to Theorem 3.5 regardless of the delay, while noting that this may indicate their analysis is not tight.Source: Figure 3 · p. 20, §4.2 · p. 21, Figure 4 · p. 21

4.3 Support vector machine

• Async-parallel Algorithm 2 achieves significantly better speed-up than its sync-parallel counterpart on dual SVM, while its epoch convergence is nearly unchanged across core counts on rcv1 and news20.The sync-parallel method converges more slowly by epoch as core counts increase.Source: §4.3 · p. 22, Figure 5 · p. 22, Figure 7 · p. 23

• The proposed method addresses convex programming with nonseparable objectives and arbitrary linear constraints.Source: §5 · p. 24
• On a single node, the method reduces to randomized primal-dual BCU for multi-block linearly constrained problems.Source: §5 · p. 24
• The authors report convergence and rate results in probability under a convexity assumption, alongside numerical performance superior to other tested methods.Source: §5 · p. 24