PaperlayerView exact revision on arXiv

Source-linked AI summary

Randomized Primal-Dual Proximal Block Coordinate Updates

Xiang Gao, Yangyang Xu, Shuzhong Zhang

arXiv:1605.05969v3math.OCcs.NAmath.NAstat.ML

TL;DR

Multi-block ADMM may fail to converge beyond two blocks, and existing randomized primal-dual convergence results require bounded constraint sets. This paper proposes randomized proximal block updates for coupled, linearly constrained convex problems; under convexity it establishes an O(1/t) rate and extends the approach to stochastic objectives.

  • Problem

    Multi-block ADMM may fail to converge with more than two blocks, while a reviewed randomized primal-dual method assumes bounded constraint sets.

    Source: Multi-block ADMM and its variants · p. 4

  • Method

    RPDBU uniformly selects subsets of variable blocks and uses proximal updates with linearization to handle coupled objective terms.

    Source: §1.3 · p. 6

  • Results

    Under mere convexity, the method establishes an expected O(1/t) convergence rate for the general problem and extends to stochastic objectives.

    Source: §1.3 · p. 6, §7 · p. 23

  • Takeaways & Limitations

    The framework includes the reviewed randomized primal-dual scheme and proximal Jacobian ADMM, and strengthens their convergence guarantees in the stated ways.

    Source: §1.3 · p. 6

    The convergence result assumes convex objectives and Lipschitz-continuous partial gradients for the coupled functions.

    Source: §3 · p. 10

Abstract

from arXiv · show

In this paper we propose a randomized primal-dual proximal block coordinate updating framework for a general multi-block convex optimization model with coupled objective function and linear constraints. Assuming mere convexity, we establish its $O(1/t)$ convergence rate in terms of the objective value and feasibility measure. The framework includes several existing algorithms as special cases such as a primal-dual method for bilinear saddle-point problems (PD-S), the proximal Jacobian ADMM (Prox-JADMM) and a randomized variant of the ADMM method for multi-block convex optimization. Our analysis recovers and/or strengthens the convergence properties of several existing algorithms. For example, for PD-S our result leads to the same order of convergence rate without the previously assumed boundedness condition on the constraint sets, and for Prox-JADMM the new result provides convergence rate in terms of the objective value and the feasibility violation. It is well known that the original ADMM may fail to converge when the number of blocks exceeds two. Our result shows that if an appropriate randomization procedure is invoked to select the updating blocks, then a sublinear rate of convergence in expectation can be guaranteed for multi-block ADMM, without assuming any strong convexity. The new approach is also extended to solve problems where only a stochastic approximation of the (sub-)gradient of the objective is available, and we establish an $O(1/\sqrt{t})$ convergence rate of the extended approach for solving stochastic programming.

1 Introduction

The introduction motivates a general multi-block convex optimization model with coupled objective terms and linear constraints, then reviews limits of existing multi-block methods. It presents RPDBU as a randomized, proximal framework intended to address these settings and extend to stochastic objectives.

1.1 Motivating examples

  • The constrained lasso and extended linear-quadratic programming are presented as examples that can be formulated within the paper’s multi-block model.The examples use block-partitioned variables and, where needed, slack variables.Source: §1.1 · pp. 2–3

Multi-block ADMM and its variants

  • Multi-block ADMM can fail to converge when there are at least three blocks, including a reported three-block divergence example.Prior work addresses this through modifications, additional assumptions, or other conditions.Source: Multi-block ADMM and its variants · pp. 4–5

Primal-dual method for bilinear saddle-point problems

  • The reviewed randomized primal-dual method has an O(1/t) rate under bounded constraint sets, while its single-x-block case is the method in.The cited randomized scheme selects one x block uniformly and then updates z.Source: Primal-dual method for bilinear… · pp. 5–6

1.3 Contributions and organization of this paper

  • RPDBU selects a uniformly random subset of variable blocks and uses proximal updates that can decouple selected blocks for parallel computation.The paper distinguishes this subset selection from random-permutation approaches.Source: §1.3 · p. 6
  • Under mere convexity, the method accommodates coupled objective terms by linearization and establishes an expected O(1/t) rate, while also extending to stochastic objectives with an O(1/√t) rate.The stochastic extension assumes an unbiased estimator of the objective’s (sub-)gradient.Source: §1.3 · pp. 6–7
  • The framework includes the randomized primal-dual scheme and proximal Jacobian ADMM as special cases, with convergence-rate guarantees that remove the former’s bounded-constraint-set assumption and improve the latter’s measure.For proximal Jacobian ADMM, the stated rate concerns both objective value and feasibility violation.Source: §1.3 · p. 6

2 Randomized Primal-Dual Block Coordinate Update Algorithm

The algorithm randomly selects blocks, applies prox-linear updates based on the augmented Lagrangian, and updates the multiplier. Its setup defines block-indexed variables and functions, while the preliminaries state an optimality characterization.

2.1 Notations

  • The notation groups the block variables and separable functions by index sets, and defines a matrix-weighted norm for positive semidefinite W.The sets are X = X1 × · · · × XN and Y = Y1 × · · · × YM.Source: §2.1 · p. 7

2.2 Algorithm

  • At each iteration, RPDBU uniformly samples fixed-size subsets of x and y blocks, applies prox-linear updates to them, and then updates the Lagrangian multiplier.The coupled functions are linearized and proximal terms are added before minimizing; suitable terms can make selected-block updates separable and parallelizable.Source: §2.2 · pp. 8–9

2.3 Preliminaries

  • The preliminaries aggregate the smooth and nonsmooth objective terms and characterize a solution through the existence of a multiplier satisfying an inequality.They also introduce the primal-dual linear mapping H(w).Source: §2.3 · p. 9

3 Convergence Rate Results

The section establishes sublinear convergence results for Algorithm 1 across three variable-block structures: no y variable, a single y block, and multiple y blocks. Its analysis uses different parameter settings for these cases.

3 Convergence Rate Results

  • The analysis assumes closed convex variable sets, smooth convex functions, proper closed convex component functions, a solution, and Lipschitz-continuous partial gradients.The selected x and y updates are decoupled by the chosen matrices, allowing them to be computed in parallel.Source: §3 · p. 10
  • The proof begins with one-step inequalities for Algorithm 1 and derives bounds for feasible points.The one-step analysis takes expectation over the selected block conditional on prior history.Source: §3 · p. 11
  • A further lemma connects convergence measures and, with an optimal solution, supports bounds for objective error and constraint violation.The deterministic version of the connection reduces to Lemma 2.4 in.Source: §3 · p. 12

3.1 Multiple x blocks and no y variable

  • For multiple x blocks and no y variable, the result strengthens Prox-JADMM by establishing an O(1/t) rate for both feasibility violation and objective value.This case is a parallel block-coordinate version of the linearized augmented Lagrangian method.Source: §3.1 · p. 13

3.2 Multiple x blocks and a single y block

  • When y is a single block, Algorithm 1 selects all y blocks each iteration, and Theorem 3.7 establishes sublinear ergodic convergence under Assumptions 1–3.This case uses a different technique for handling y than the no-y case.Source: §3.2 · pp. 13–14

3.3 Multiple x and y blocks

  • With multiple x and y blocks, equal selection ratios n/N and m/M yield an O(1/t) convergence rate under the stated assumptions.The ratios can be matched without loss of generality by adding zero components if necessary.Source: §3.3 · pp. 14–15
  • The parameter conditions for the general multi-block case vary with the selected block fractions, and neither stated condition generally implies the other.One condition may be weaker when block fractions are large; the other is more likely weaker when they are small.Source: §3.3 · p. 15

4 Randomized Primal-Dual Coordinate Approach for Stochastic Programming

The section extends the primal-dual coordinate method to stochastic objectives represented as expectations, using stochastic gradient information. It establishes sublinear convergence results and discusses extensions to other objective settings.

4 Randomized Primal-Dual Coordinate Approach for Stochastic Programming

  • The analysis can be extended to stochastic g and nonzero g and v; penalized and constrained regression is given as an example of the problem form.The cited example includes (2) as a special case.Source: §4 · p. 15
  • Algorithm 2 applies randomized primal-dual coordinate updates to an expectation-form objective, using Gk as a stochastic approximation of ∇f(xk).The section assumes the objective's coupled function has the form f(x) = Eξfξ(x).Source: §4 · pp. 15–16
  • The analysis establishes sublinear convergence for Algorithm 2 with parameter choices that depend on whether the iteration horizon is fixed.The proposition specifies an initially feasible point with Ax0 = b and λ0 = 0; for a fixed horizon, αk is chosen proportional to √t.Source: §4 · pp. 17–18
  • The sublinear convergence result also applies when f is nondifferentiable, convex, and Lipschitz continuous.The section uses bounded subgradients implied by Lipschitz continuity in extending the analysis.Source: §4 · p. 18

5 Numerical Experiments

The experiments test the randomized primal-dual method on nonnegativity-constrained quadratic programming. They examine parallel speed-up and compare the method with two alternatives.

5 Numerical Experiments

  • The proposed method achieves nearly linear speed-up when using 1, 2, and 4 cores in the parallelization experiment.The test uses m = 200 and n = 2000, with each component of x treated as one block.Source: §5 · p. 19
  • The comparison experiment uses a singular Q, so the tested quadratic program is not strongly convex.It compares RPDBU with linearized ALM and cyclic linearized ADMM.Source: §5 · p. 19
  • RPDBU is comparable to cyclic linearized ADMM and significantly better than linearized ALM on the tested problem.The comparison uses 100 blocks of 50 variables and updates one randomly selected block per iteration; one epoch equals 100 block updates.Source: §5 · pp. 19–20, Figure 2 · p. 20

6 Connections to Existing Methods

The proposed algorithms specialize to several existing methods and recover or strengthen convergence results. Their connections include randomized coordinate descent, stochastic block proximal gradient, multi-block ADMM, Prox-JADMM, and a randomized primal-dual scheme.

6.1 Randomized proximal coordinate descent

  • With no coupled function and one selected block, Algorithm 1 reduces to randomized proximal coordinate descent; selecting multiple blocks yields parallel coordinate descent.The section also states that its result can be strengthened to non-ergodic convergence for this unconstrained setting because the objective is nonincreasing.Source: §6.1 · p. 21

6.2 Stochastic block proximal gradient

  • Selecting one block per iteration reduces Algorithm 2 to stochastic block proximal gradient, and Proposition 4.3 recovers its convergence result.The referenced method replaces the partial gradient with a stochastic approximation.Source: §6.2 · p. 21

6.3 Multi-block ADMM

  • Randomly updating one block and then the multiplier guarantees an O(1/t) convergence rate for the multi-block ADMM variant.The section identifies randomization as key to this convergence result.Source: §6.3 · p. 21

6.4 Proximal Jacobian parallel ADMM

  • With all blocks updated in parallel and specified proximal terms, Algorithm 1 reduces to Prox-JADMM and gives a rate in objective value and feasibility.The cited prior result established an order-1/t rate based on the squared difference between consecutive iterates.Source: §6.4 · p. 22

6.5 Randomized primal-dual scheme in (9)

  • The randomized primal-dual scheme is a special case of Algorithm 1, and adding a proximal term to its y-update removes the bounded-constraint-set assumption for its O(1/t) result.The earlier result in [9] required boundedness of X and Z.Source: §6.5 · p. 23

7 Concluding Remarks

RPDBU establishes sublinear convergence for multi-block convex optimization under convexity alone, and its randomized updates recover several existing algorithms as special cases. The framework also extends to stochastic objectives, while a deterministic counterpart remains open.

7 Concluding Remarks

  • O(1/t) convergence is established for RPDBU under convexity alone, without restrictions on the constraint matrices.The rate is for the objective function and feasibility measure.Source: §7 · p. 23
  • With stochastic (sub-)gradient estimates and adaptively chosen αk, the extended method has an O(1/√t) convergence rate.Source: §7 · p. 23
  • Without a coupled function f, RPDBU reduces to randomized multi-block ADMM, whose convergence follows from the analysis.Source: §7 · p. 23
  • Taking the sampling set as the whole set and choosing special matrices yields the proximal Jacobian ADMM as a special case.Source: §7 · p. 23
  • Whether a deterministic RPDBU counterpart, such as a cyclic update rule with a proximal term, retains similar convergence remains open.Source: §7 · p. 23

A Proofs of Lemmas

The appendix proves intermediate lemmas and inequalities used in the main results. Its arguments invoke optimality, convexity, expectation, and elementary calculus.

A Proofs of Lemmas

  • The appendix introduces ˜P and ˜Q before presenting proofs of the lemmas used for the main results.Source: A Proofs of Lemmas · p. 27

A.1 Proof of Lemma 3.1

  • Lemma 3.1 derives relations (23) and (24) from optimality and rearranged terms, using convexity and Lipschitz continuity in its expectation calculations.Source: §A.1 · pp. 27–29

A.2 Proof of Lemma 3.3

  • Setting x = x* and y = y* in (29) gives an expression for any λ; its last equality follows from feasibility of (x*, y*), and for γ > 0, λ is restricted to Bγ.Source: §A.2 · p. 29

A.3 Proof of Inequalities (50c) and (50d) with αk = α0 √

  • Elementary calculus shows ψ(k) decreases with k, establishing inequality (50c).Source: §A.3 · pp. 29–30

B Proofs of Theorems

B.1 Proof of Theorem 3.6

The proof takes expectations of the two intermediate inequalities and sums them over iterations. It combines the resulting bounds with the initial multiplier choice and auxiliary lemmas to obtain the stated result.

B.1 Proof of Theorem 3.6

  • The proof sums the expected forms of (23) and (24) from k = 0 through t, then combines the resulting bounds.Source: §B.1 · pp. 30–31
  • The argument uses Φ(x, y) = F(x) + G(y), the definition of H, and the relation θ = ρρx to cancel terms.Source: §B.1 · p. 31
  • The stated result follows using λ0 = 0 and Lemmas 3.3 and 3.5 with γ = max{1 + ∥λ∗∥, 2∥λ∗∥}.Source: §B.1 · p. 32

B.2 Proof of Theorem 3.7

The proof of Theorem 3.7 combines intermediate inequalities for the y and multiplier updates, then applies convexity and auxiliary lemmas to obtain the result.

B.2 Proof of Theorem 3.7

  • The proof combines inequalities for the y update and multiplier with earlier bounds, using the formula for λk.Source: §B.2 · p. 32
  • The argument uses (18) and the condition on ˜P, ˜Q, and ρ to derive the subsequent bound.Source: §B.2 · pp. 33–34
  • Convexity of Φ and (20), followed by Lemmas 3.3 and 3.5 with γ = max{1 + ∥λ∗∥, 2∥λ∗∥}, yields result (37).Source: §B.2 · p. 34

B.3 Proof of Theorem 3.8

The proof combines inequalities and convexity properties to obtain the desired result under the stated condition on ˆP and ˆQ.

B.3 Proof of Theorem 3.8

  • When ˆP and ˆQ satisfy (39b), inequality (92) holds after bounding the right-hand side of (89).The bound uses (90), (91), and ∥˜λt+1 − λt∥2 ≥ ∥λt+1 − λt∥2.Source: §B.3 · p. 35
  • The proof combines inequalities (94) and (93), using convexity of Φ and properties (20) of H.Source: §B.3 · p. 36
  • The proof concludes that the desired result follows from Lemmas 3.3 and 3.5 with γ = max{1 + ∥λ∗∥, 2∥λ∗∥}.Source: §B.3 · p. 36

B.4 Proof of Theorem 4.2

Theorem 4.2 is proved by summing weighted inequalities using the nonincreasing sequence αk; Proposition 6.1 is verified by rewriting the updates with proximal and Moreau identities.

B.4 Proof of Theorem 4.2

  • The proof sums (98) over k = 0 through t − 1 with (99), using nonincreasing αk and (96) to derive the bound.It also uses Young’s inequality and the update formula for λ; ˜P is defined as ˆP − ρA⊤A.Source: §B.4 · pp. 37–38
  • The proof derives the desired result using Lemma 3.3 and properties of H after applying convexity of Φ and (20).Source: §B.4 · pp. 38–39

B.5 Proof of Proposition 6.1

  • Proposition 6.1 is verified by rewriting update (9b) as a proximal mapping and using Moreau’s identity to establish the update relations.The proof then substitutes the formula for z̄k into (9a) to recover (63a).Source: §B.5 · p. 39
Loading 1605.05969v3…