PaperlayerView exact revision on arXiv

Source-linked AI summary

Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions

Damek Davis, Wotao Yin

arXiv:1407.5210v3math.OC

TL;DR

The paper addresses limited convergence-rate understanding for DRS, PRS, and ADMM under stronger regularity conditions. It analyzes relaxed PRS and ADMM across unconstrained and linearly constrained convex problems, using elementary inequalities and summability arguments. The resulting rates adapt to regularity, improve worst-case nonsmooth guarantees, and are comprehensive under standard assumptions, though linear convergence is not generally available without regularity.

  • Problem

    The paper studies how convergence rates for DRS, PRS, and ADMM improve under regularity assumptions beyond general convexity.

  • Method

    The authors analyze relaxed PRS for unconstrained composite problems and relaxed ADMM for linearly constrained problems using fundamental inequalities, summable-sequence arguments, and regularity assumptions.

  • Results

    The analysis provides convergence rates for relaxed PRS and ADMM, including rates that improve worst-case nonsmooth guarantees and, in some ADMM scenarios, ensure R-linear convergence.

  • Takeaways & Limitations

    The derived rates help select iteration budgets, stopping criteria, and worst-case complexity comparisons, while explaining relaxed PRS and ADMM performance under regularity.

  • Takeaways & Limitations

    Without regularity, relaxed PRS need not converge linearly and can converge in norm arbitrarily slowly for feasibility problems.

Abstract

from arXiv · show

Splitting schemes are a class of powerful algorithms that solve complicated monotone inclusion and convex optimization problems that are built from many simpler pieces. They give rise to algorithms in which the simple pieces of the decomposition are processed individually. This leads to easily implementable and highly parallelizable algorithms, which often obtain nearly state-of-the-art performance. In this paper, we provide a comprehensive convergence rate analysis of the Douglas-Rachford splitting (DRS), Peaceman-Rachford splitting (PRS), and alternating direction method of multipliers (ADMM) algorithms under various regularity assumptions including strong convexity, Lipschitz differentiability, and bounded linear regularity. The main consequence of this work is that relaxed PRS and ADMM automatically adapt to the regularity of the problem and achieve convergence rates that improve upon the (tight) worst-case rates that hold in the absence of such regularity. All of the results are obtained using simple techniques.

1 Introduction

The paper analyzes relaxed PRS and ADMM for monotone inclusion and convex optimization problems, deriving convergence rates under regularity assumptions and clarifying practical parameter choices. Its results cover objective, residual, feasibility, and solution errors, with stronger guarantees in regular settings.

  • Motivation: Splitting schemes process simpler problem components individually, enabling parallel and distributed implementations for large-scale applications.The paper situates DRS, PRS, and ADMM in optimization, signal recovery, machine learning, image processing, and related applications.
  • Problem settings: The paper applies relaxed PRS to unconstrained composite problems and relaxed ADMM to linearly constrained problems.The unconstrained model supports data fitting and priors such as sparsity, low rank, or smoothness; the constrained model supports variable splitting and distributed optimization.
  • Main contribution: The paper explains that relaxed PRS and ADMM adapt to problem regularity and improve upon worst-case nonsmooth rates.The authors present the results as complementing earlier general-convexity analyses and as explaining strong practical performance.
  • Convergence analysis: The analysis derives rates for relaxed PRS objective errors and fixed-point residuals, and for relaxed ADMM constraint violations and objective errors.Several relaxed PRS rates are tight up to constant factors by counterexamples from prior work.
  • Convergence analysis: The convergence-rate tables specify relaxation-parameter ranges, ergodic qualifications, and additional step-size conditions for relaxed PRS and ADMM.For ADMM, cases 3–6 ensure R-linear convergence; for PRS, the tables distinguish general relaxed parameters from DRS with properly bounded step size.
  • Practical implications: When one objective is differentiable, relaxed PRS can match forward-backward splitting with suitable stepsizes and retain an o(1/(k + 1)) best-iterate rate for any stepsize.The comparison also states that forward-backward splitting may fail to converge when the gradient Lipschitz constant is unknown, whereas relaxed PRS can avoid an expensive line search.

2 Strong convexity

The analysis derives convergence bounds for relaxed PRS using an auxiliary inequality. Under strong convexity, the iterates converge strongly to a minimizer, while best-iterate bounds do not automatically extend to the full sequence.

  • If either f or g is strongly convex and relaxation parameters stay bounded away from zero, x_k converges strongly to a minimizer of f + g.
  • Equation (2.1) is the main inequality used to derive linear convergence of relaxed PRS.
  • The auxiliary term bound yields an o(1/(k + 1)) rate for the relevant best-iterate quantity.
  • Because the objective-related values are not necessarily monotonic, it is unclear whether the best-iterate rate extends to the entire sequence.

3 Lipschitz derivatives

Under Lipschitz-gradient assumptions, relaxed PRS admits summability-based objective-error and fixed-point-residual rates, with stronger bounds for suitable stepsizes and relaxation choices. The analysis also identifies stepsize thresholds and compares the resulting guarantees with FBS and DRS.

  • When at least one gradient is Lipschitz, objective errors are summable for suitable relaxation parameters, yielding several possible convergence rates.
  • DRS is at least as fast as FBS when γ is sufficiently small, and best-iterate rates retain essentially the same constant over a broad γ range.
  • The stepsize γ affects relaxed PRS because reflection operators for differentiable functions have stronger contraction properties only when γ is sufficiently small.
  • For γ below specified thresholds, DRS achieves o(1/(k + 1)^2) fixed-point-residual rates and o(1/(k + 1)) objective-error rates.
  • The DRS analysis covers γ ≤ κβ, whereas FBS guarantees the same objective-error and fixed-point-residual orders for γ < 2β.

4 Linear convergence

The paper establishes linear convergence of relaxed PRS when strong convexity and Lipschitz differentiability provide suitable regularity. Contraction factors depend on relaxation, stepsizes, and the location of the regularity across f and g.

  • If at least one function has a Lipschitz gradient and at least one is strongly convex, relaxed PRS is expected to converge linearly to a unique minimizer.
  • A contraction bound ∥z_{k+1} − z*∥ ≤ C(λ_k)∥z_k − z*∥ yields linear rates for iterates, subgradient errors, fixed-point residuals, and objective errors when sup C_j < 1.
  • When g is both strongly convex and smooth, the contraction factor is C(λ) = (1 − 4γλμ_g/(1 + γ/β_g)^2)^{1/2}.
  • For regularity in g, the contraction factor is minimized at γ = β_g, and full PRS can converge in one step for g = (1/2)∥·∥^2.
  • When f carries both regularity properties, linear convergence of relaxed PRS is obtained, but the unrelaxed PRS case does not follow from this result.
  • If smoothness and strong convexity are split across the two functions, the mixed-case factor depends on min{γμ, β/γ, 1 − λ}.

5 Feasibility Problems with regularity

For feasibility problems modeled with squared distance functions, bounded linear regularity yields explicit linear convergence of relaxed PRS and its MAP special case. The results also describe parameter choices, comparisons with prior rates, and an infeasible-case limit.

  • Bounded linear regularity controls distances to the intersection on bounded regions and is the key assumption for linear convergence.
  • If the contraction constant satisfies C = sup_j C(γ_f,j, γ_g,j, λ_j, μ_ρ) < 1, the iterates converge linearly to a point in C_f ∩ C_g.
  • The contraction constant is minimized at γ′ = 1/2 and then at γ = 1/2, with monotonic improvement as λ increases.
  • The feasibility rate improves on a prior cyclic-projections rate under the same regularity setting.
  • With γ_f,k = γ_g,k = 1/2 and λ_k = 1, MAP is a special case of PRS and converges linearly under the same regularity assumptions.
  • In the infeasible case, MAP can converge weakly to a set characterized by a common gap-vector relation, with the projected difference converging strongly to that gap vector.

6 From relaxed PRS to ADMM

Section 6 connects relaxed PRS applied to a Lagrange dual problem with relaxed ADMM, then transfers regularity and convergence results between dual and primal formulations.

  • Algorithm: The relaxed ADMM iteration updates y, the dual variable, and x through alternating minimizations of the augmented Lagrangian with relaxation terms.The algorithm initializes x and y at zero, uses γ > 0, and permits relaxation parameters in (0,1].
  • Dual formulation: Relaxed ADMM is obtained by applying relaxed PRS to the Lagrange dual of the constrained convex optimization problem.The section uses ADMM's known relationship with DRS on the Lagrange dual and identifies relaxed ADMM with relaxed PRS on the dual problem.
  • Regularity transfer: Proposition 6.1 transfers strong convexity to conjugate differentiability and Lipschitz gradients, and transfers Lipschitz gradients to conjugate strong convexity.These conjugacy relations provide the basis for expressing dual regularity through primal assumptions.
  • Regularity transfer: Proposition 6.2 characterizes dual regularity using the linear operators and primal functions: α-strong monotonicity with (1/β)-Lipschitz gradients yields αβ-strong convexity.Primal strong convexity also yields dual differentiability with gradient Lipschitz constant ∥A∥^2/µ or ∥B∥^2/µ.
  • Primal consequences: Section 6 translates relaxed PRS convergence rates into ADMM rates for primal objective errors, constraint violations, and strong convergence of associated quantities.The translation uses fundamental inequalities relating ADMM sequences to primal and dual objective functions.
  • Primal consequences: Theorem 6.1 states best-iterate and o(1/(k + 1)) convergence results for ADMM under assumptions that allow Lipschitz and strong-convexity constants to vanish.The analysis explicitly permits zero regularity constants, covering cases where the corresponding properties may fail.

3. General convergence: If τ

The section derives sublinear and linear convergence results for relaxed PRS and ADMM under regularity assumptions, and compares relaxed PRS with MAP in feasibility problems.

  • General convergence: For strongly convex g, λk ≡ 1/2 and γ < κµg/∥B∥^2 yield o(1/k) primal objective error convergence.The same setting also provides a convergence rate for constraint violations through the fixed-point residual.
  • Feasibility problems: Without regularity, relaxed PRS for feasibility problems generally cannot be expected to converge linearly and may converge in norm arbitrarily slowly.This limitation motivates analyzing fixed-point residual and objective-error rates instead of relying on norm convergence.
  • Feasibility problems: For feasibility problems, relaxed PRS produces ergodic iterates with distance O(1/Λk) between the sets, and this rate is optimal in the cited result.The comparison notes that the rate is strictly slower than the rate obtained under the regularity considered elsewhere in the section.
  • Comparison with MAP: MAP can have faster rates when the sets intersect regularly, whereas relaxed PRS is faster in the absence of regularity according to the cited comparisons.The paper presents this as a phenomenon whose general characterization remains open.
  • Model fitting: For model fitting, the best auxiliary term converges at o(1/(k + 1)), the ergodic term at O(1/Λk), and the full sequence at a further sublinear rate.If the loss l is Lipschitz, the loss discrepancy satisfies o(1/(k + 1)); linear convergence is available in the listed regularity cases.
  • Linear convergence: Relaxed ADMM has linear convergence in four stated regularity scenarios involving strong convexity, differentiability, and strong monotonicity of the problem components and operators.The section translates these scenarios into linear rates for objective errors and constraint violations.

8 Conclusion

The paper gives a comprehensive convergence-rate analysis of relaxed PRS and ADMM under standard convex-optimization regularity assumptions, using simple proof ingredients and identifying rates that cannot generally be improved.

  • Conclusion: The analysis covers relaxed PRS and ADMM under strong convexity, Lipschitz differentiability, and related regularity assumptions.It is presented as a comprehensive convergence-rate treatment under standard convex-optimization conditions.
  • Conclusion: Several derived convergence rates are unimprovable up to constant factors by comparison with counterexamples developed in earlier work.The conclusion explicitly combines this paper's results with those examples to characterize the rates.
  • Conclusion: The proofs combine a summable-sequence convergence lemma, a simple diagram, and fundamental inequalities relating fixed-point residuals to objective errors.These ingredients support the rate derivations for relaxed PRS and ADMM.

A Technical results from Section 3.1

This technical section develops descent, monotonicity, contraction, and summability tools used to derive convergence rates for relaxed PRS when one component is differentiable with a Lipschitz gradient.

  • Role in the analysis: The resulting proof toolkit combines descent, contraction, monotonicity, and summability to establish the convergence-rate results used in Section 3.The section includes the supporting identities and proofs for these ingredients.
  • Descent tools: The descent theorem converts Lipschitz differentiability of a convex function into an upper bound and a cocoercive inequality.These inequalities are repeatedly used in later convergence arguments.
  • Contraction: Lipschitz gradients provide extra contraction and bounds relating successive gradient differences to successive proximal-point differences.These estimates connect the differentiable component's regularity to the splitting iteration's contraction behavior.
  • Monotonicity: A fundamental inequality for differentiable functions supports construction of a monotonic sequence that dominates the objective error.The construction introduces θ ∈ [0, 1] and optimizes it to enlarge the admissible stepsize range.
  • Monotonicity: Choosing (γ*, θ*) = (κβ, 1 − 1/κ^2) maximizes the range of implicit stepsizes for which the constructed sequence remains monotonic.The constant κ is defined through the positive root of x^3 + x^2 − 2x − 1.
  • Summability: If γ < κβ, selecting θ = θ* yields summability of the sequence controlling the objective error; otherwise the analysis uses θ = 1.The summability result is a key input for converting residual bounds into convergence rates.

C Proofs from Section 5

This section establishes fixed-point, boundedness, and feasibility properties for relaxed PRS, supporting convergence analysis under varying stepsizes and relaxation parameters.

  • The fixed points of T_PRS are characterized through zeros of ∂f + ∂g and associated subgradient pairs.
  • PRS remains nonexpansive, following from the nonexpansiveness of the reflection mapping.
  • For feasibility problems, the fixed-point set of T_PRS is exactly C_f ∩ C_g, independently of the positive implicit stepsizes.
  • When relaxation parameters satisfy λ_k ∈ (0,1], the squared distance to any point in C_f ∩ C_g is monotonically nonincreasing.
  • The feasibility analysis uses an upper fundamental inequality for relaxed PRS, obtained by applying the general inequality to scaled distance functions.

D Extension of results of Section 5 to multiple sets

The paper extends the two-set feasibility analysis to multiple sets by working in a product space, where linear regularity transfers to a pair involving a diagonal set.

  • Product-space formulation: A collection of multiple closed convex sets is linearly regular exactly when the corresponding product-set and diagonal-set pair has the same property.
  • Product-space formulation: The multiple-set feasibility problem is modeled on H^m using the product set C_1 × ··· × C_m and the diagonal set D.
  • Algorithm: The product-space iteration uses separate implicit stepsizes, relaxation parameters, and an initial point in H^m.
  • Scope: Weighted projection averages and set-specific implicit stepsizes are possible extensions, but the paper does not pursue them.
  • Linear convergence: Under bounded linear regularity and a uniform contraction condition C < 1, the multiple-set iterates converge linearly to (C_1 × ··· × C_m) ∩ D.
  • MAP consequence: Averaged MAP is a special case of PRS, and its projected sequence converges linearly to a point in C_1 ∩ ··· ∩ C_m.

F Applications to conic programming

This section applies relaxed PRS and DRS to conic programming through homogeneous self-dual feasibility formulations, with linear convergence available when the relevant sets are linearly regular.

  • Problem formulation: Linear and semidefinite programming are formulated as minimizing linear objectives subject to linear and semidefinite constraints.
  • Homogeneous self-dual embedding: The homogeneous self-dual embedding introduces slack variables and seeks a point in C_f ∩ C_g satisfying the embedding relations.
  • Linear programming: For linear programming, the feasible-set pair is linearly regular in finite dimensions, enabling linear convergence of relaxed PRS to the intersection.
  • Splitting constraints: Linear constraints can be split into smaller sets, allowing DRS or relaxed PRS to use product-space formulations with a diagonal set.
  • Practical considerations: The practical performance of alternative function pairs cannot generally be predicted, although the indicator-function pair may perform better on badly conditioned problems.
  • Semidefinite programming: For semidefinite programming, linear regularity is not guaranteed; the relevant condition concerns whether the relative interior of C_f intersects C_g.
  • Computational bottleneck: Projection onto the semidefinite cone remains the main computational bottleneck, with no identified way to reduce its cost.
Loading 1407.5210v3…