PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Primal-Dual Hybrid Gradient Methods for Saddle-Point Problems

Tom Goldstein, Min Li, Xiaoming Yuan, Ernie Esser, Richard Baraniuk

arXiv:1305.0546v2math.NAcs.NA

TL;DR

PDHG convergence speed is sensitive to user-chosen stepsizes, which may depend on unknown spectral information. This paper develops adaptive schemes and proves convergence conditions for them. The reported experiments show adaptive methods compare favorably with non-adaptive implementations, while backtracking performs at least as well as methods requiring spectral information.

  • Problem

    PDHG's convergence speed depends heavily on user-chosen stepsizes, and the required restriction depends on potentially unknown spectral properties of A.

    Source: §I · p. 1

  • Method

    The paper develops adaptive PDHG schemes that automatically tune stepsizes and provides practical implementations satisfying proven convergence conditions.

    Source: §I · p. 1, §VIII · p. 14

  • Results

    Adaptive backtracking performs at least as well as methods requiring spectral information, while adaptive backtracking and non-backtracking methods have similar average performance on imaging problems.

    Source: B. Discussion · pp. 13–14, §VIII · p. 14

  • Takeaways & Limitations

    Because backtracking requires no spectral information, it is useful for black-box solvers, including generic linear-programming solvers.

    Source: §VIII · p. 14

Abstract

from arXiv · show

The Primal-Dual hybrid gradient (PDHG) method is a powerful optimization scheme that breaks complex problems into simple sub-steps. Unfortunately, PDHG methods require the user to choose stepsize parameters, and the speed of convergence is highly sensitive to this choice. We introduce new adaptive PDHG schemes that automatically tune the stepsize parameters for fast convergence without user inputs. We prove rigorous convergence results for our methods, and identify the conditions required for convergence. We also develop practical implementations of adaptive schemes that formally satisfy the convergence requirements. Numerical experiments show that adaptive PDHG methods have advantages over non-adaptive implementations in terms of both efficiency and simplicity for the user.

I. INTRODUCTION

PDHG separates primal and dual updates, but its convergence speed depends strongly on stepsizes that users may not know how to choose. The paper identifies convergence conditions for adaptive stepsizes and proposes practical schemes that enforce them.

I. INTRODUCTION

  • PDHG decouples the terms involving f and g, often allowing explicit updates instead of expensive minimization subproblems.This is useful when f and g lack shared properties but can be minimized independently.Source: §I · p. 1

II. THE PRIMAL-DUAL HYBRID GRADIENT METHOD

  • Users must choose PDHG stepsizes carefully: convergence speed is sensitive to them, and the admissible range depends on potentially unknown spectral properties of A.For constant stepsizes, convergence is known under στ < 1/ρ(A^T A); non-constant stepsizes may fail even when that inequality holds.Source: §I · p. 1, §II · p. 2

I. INTRODUCTION

  • Adaptive PDHG schemes automatically tune stepsizes and are presented with convergence guarantees and practical implementations that satisfy the required conditions.The paper identifies specific stepsize conditions for convergence, including for adaptive methods.Source: §I · p. 1, §II · p. 2

A. Optimality Conditions and Residuals

The section defines primal and dual residuals from the optimality conditions and uses them to measure convergence. It also shows how total-variation denoising fits the saddle-point framework solved by PDHG.

A. Optimality Conditions and Residuals

  • Primal and dual residuals are formed from the optimality conditions and provide a measure of algorithm convergence.The residual vectors belong to the corresponding primal and dual residual sets at the current iterate.Source: A. Optimality Conditions and Residuals · p. 2
  • Residual convergence is more general than convergence of iterate subsequences because the saddle-point solution need not be unique.The problem is assumed feasible so its resolvent minimizations and optimality conditions admit a solution.Source: A. Optimality Conditions and Residuals · pp. 2–3

A. Total-Variation Denoising

  • Total-variation denoising fits PDHG's saddle-point form by expressing the TV term as a maximization over a dual variable.The squared-error term fits f, the gradient operator is A, and the dual constraint set is C∞.Source: A. Total-Variation Denoising · p. 3

B. TVL1

The paper expresses TVL1, convex segmentation, and compressed-sensing problems in saddle-point form for PDHG. In the single-pixel-camera setting, PDHG updates can be explicit and avoid expensive minimization substeps.

B. TVL1

  • TVL1 replaces the squared-error data term with an ℓ1 term, making the model effective for heavy-tailed noise such as shot or salt-and-pepper noise.Source: B. TVL1 · p. 3

C. Globally Convex Segmentation

  • In the CEN segmentation model, an inner-product term steers pixels toward one of two labels while the TV term encourages smooth boundaries.The model is formulated for PDHG through a saddle-point representation.Source: C. Globally Convex Segmentation · p. 3

D. Compressed Sensing / Single-Pixel Cameras

  • For compressed-sensing problems using a subsampled orthogonal transform, PDHG steps can be explicit, avoiding expensive minimization substeps.The transform can be a Hadamard or Fourier matrix; the single-pixel camera uses measured Hadamard coefficients.Source: D. Compressed Sensing / Single-Pixel… · pp. 3–4

F. Linear Programming

Residual balancing adapts PDHG stepsizes to trade off primal and dual residuals. A scaling parameter accounts for changes in input units, and the residual norm can be chosen to reduce sensitivity to outliers.

IV. RESIDUAL BALANCING

  • A large primal stepsize favors a small primal residual but can enlarge the dual residual, while a small one reverses that tradeoff.Source: §IV · p. 4
  • Residual balancing adjusts primal and dual stepsizes to keep the residuals roughly equal after scaling, increasing one stepsize while decreasing the other when imbalance grows.The paper uses the ℓ1 norm, which it reports is less sensitive to outliers and somewhat better than ℓ2 on some problems.Source: §IV · pp. 4–5
  • The scaling parameter s accounts for input-unit changes that alter the relative residual sizes.For image processing, the paper recommends [0, 255] scaling with s = 1, or [0, 1] scaling with s = 255.Source: §IV · p. 5

V. ADAPTIVE METHODS

The section presents two adaptive PDHG methods and explains how their stepsize rules are paired with convergence guarantees. One method uses a known spectral bound; the backtracking variant can proceed without it.

A. Adaptive PDHG

  • With a bound on ρ(A^T A), the first method enforces the non-adaptive stability condition, which alone is insufficient to guarantee convergence with adaptive stepsizes.The section’s later algorithm adjusts stepsizes according to the relative primal and dual residuals.Source: §V · p. 5, A. Adaptive PDHG · p. 5

B. Backtracking PDHG

  • Backtracking needs no knowledge of ρ(A^T A) and permits steps that violate the usual stability condition, which can be faster for highly sparse solutions.The method decreases stepsizes when its backtracking condition fails; the backtracking step is activated only finitely many times.Source: §V · p. 5, B. Backtracking PDHG · p. 5

V. ADAPTIVE METHODS

  • Both methods have convergence guarantees: the norm of their residuals goes to zero.The backtracking method enforces its condition at each step and requires either X or Y to be bounded for the stated guarantee.Source: §V · p. 5, B. Backtracking PDHG · p. 5

A. Adaptive PDHG

  • The first method adjusts primal and dual stepsizes when residuals differ by more than Δ, while α_k decreases after each update to support convergence.If the residuals are comparable, the stepsizes remain unchanged.Source: A. Adaptive PDHG · p. 5

VI. CONVERGENCE THEORY

The section formulates PDHG in variational-inequality terms and uses that framework to state convergence results. These include vanishing residuals and an O(1/k) ergodic convergence rate.

A. Variational Inequality Formulation

B. Stepsize Conditions

The convergence analysis identifies bounded stepsizes and summable changes, plus a stability condition, as requirements for convergence. It shows how the adaptive and backtracking implementations meet those requirements and sketches the proof strategy.

B. Stepsize Conditions

  • Convergence requires bounded stepsizes, summable φ_k, and either a spectral stability condition or a backtracking condition with a bounded feasible space.The spectral condition is simpler to enforce, while backtracking can allow larger steps that violate it.Source: B. Stepsize Conditions · p. 7

C. Convergence of the Adaptive Method

  • The adaptive method keeps τ_kσ_k constant below the spectral bound and makes nonzero φ_k values geometrically decreasing, satisfying its convergence conditions.The paper concludes that this implementation’s convergence is guaranteed.Source: C. Convergence of the Adaptive Method · p. 7

D. Convergence of the Backtracking Method

E. Sketch of Proof

  • The proof uses a Fejér inequality, then bounds terms involving M_k because that matrix changes and may be indefinite under backtracking.Those bounds allow the convergence argument to proceed even when M_k is indefinite.Source: E. Sketch of Proof · pp. 7–8

F. Preliminary Lemmas

The preliminary lemmas establish bounds needed for convergence analysis, including when the matrix used in the Fejér argument may be indefinite. Under the stated stepsize conditions, they also show that backtracking occurs only finitely many times.

F. Preliminary Lemmas

  • Backtracking can occur only finitely many times because sufficiently small τ_kσ_k makes the backtracking ratio less than one.The lemma links the eventual reduction in the stepsize product to the finite number of backtracking activations.Source: F. Preliminary Lemmas · p. 8
  • The Fejér inequality alone does not establish convergence because M_k changes and can be indefinite; the lemmas bound terms involving M_k to address this.When C1 holds, the stability condition makes M_k positive definite.Source: F. Preliminary Lemmas · p. 8
  • The lemmas bound the iterates from above under conditions A, B, and C, including when C2 holds and one feasible space is bounded.The argument also gives upper bounds on the primal and dual distances to a solution.Source: F. Preliminary Lemmas · pp. 9–10
  • Under conditions A, B, and C, the M_k quantity has a lower bound, so it does not approach negative infinity even when M_k is indefinite.This supplies a lower bound complementary to the upper bound established by Lemma 3.Source: F. Preliminary Lemmas · p. 10

G. Convergence Theorems

The convergence theorems establish residual convergence for Algorithm 1 under specified stepsize conditions and give an O(1/t) ergodic rate. A second theorem provides a convergence bound for a sequence defined under conditions A, B, and C.

G. Convergence Theorems

  • Algorithm 1 converges in the residuals when its stepsizes satisfy conditions A and B, and either C1 or C2.The proof strategy controls residuals while accounting for the changing Mk-norms across iterations.Source: G. Convergence Theorems · p. 10
  • Under conditions A, B, and C, Theorem 2's defined sequence satisfies the stated convergence bound.Source: G. Convergence Theorems · p. 11
  • The algorithm has an O(1/t) convergence rate in an ergodic sense.The argument bounds the iterates and the stepsize-dependent matrices used in the analysis.Source: G. Convergence Theorems · p. 11

VII. NUMERICAL RESULTS

The numerical study compares four PDHG variants: two adaptive schemes and two constant-stepsize baselines. The experiments use common initialization and stopping choices, with backtracking parameters specified separately.

VII. NUMERICAL RESULTS

  • The runs use α0 = 0.5, ∆ = 1.5, and η = 0.95; backtracking uses γ = 0.75 and β = 0.95.Source: §VII · p. 12
  • Unless otherwise specified, the algorithms stop when both primal and dual residual norms are below 0.05.Source: §VII · p. 12
  • The four variants comprise adaptive PDHG with backtracking, adaptive PDHG without backtracking, and two constant-stepsize baselines.The adaptive backtracking method initializes stepsizes using formula (31); one constant baseline uses the final stepsizes of the adaptive method without backtracking.Source: §VII · p. 12

A. Experiments

The experiments apply adaptive PDHG to denoising, segmentation, compressed sensing, linear programming, and complex-valued signal approximation. In denoising, the backtracking and non-backtracking adaptive methods perform similarly, while backtracking outperforms the non-backtracking method on the linear-programming test.

Rudin-Osher-Fatemi and TVL1 Denoising

Convex Segmentation

Compressed Sensing

  • The compressed-sensing experiment reconstructs a Shepp-Logan phantom from subsampled Hadamard measurements, with a 10% noisy-coefficient reconstruction shown.The experiments use 5%, 10%, and 20% random coefficient samples; the 10% reconstruction is depicted in false color to accentuate small features.Source: Compressed Sensing · p. 12, Figure 4 · p. 13

ℓ∞ Minimization

  • The complex-valued signal-approximation tests use a randomly subsampled discrete Fourier matrix and report results at approximation accuracies ϵ = 1, 0.1, and 0.01.The input signal is a vector of random Gaussian variables.Source: Compressed Sensing · p. 12

General Linear Programming

  • On the sc50b linear program, backtracking outperformed the non-backtracking algorithm, while PDHG was less efficient than Matlab's linprog for this small-scale problem.The test recovers 40 unknowns subject to 30 inequality and 20 equality constraints; linprog took approximately 0.05 seconds.Source: General Linear Programming · p. 13

B. Discussion

The imaging results show similar average performance between adaptive backtracking and the spectral-information variant. The conclusion highlights backtracking’s lack of spectral-input requirements and the adaptive methods’ convergence guarantees.

B. Discussion

  • Adaptive backtracking and the variant using known L have similar average performance on imaging problems, with neither consistently outperforming the other.Table I reports iteration counts for each problem/algorithm and total runtime in parentheses.Source: B. Discussion · p. 13, Table I · p. 14
  • Backtracking can outperform the conventional stepsize restriction by using longer steps; for ROF denoising at µ = 0.01, τkσk ended at 0.14 versus the 0.125 bound.Source: B. Discussion · p. 14
  • The best stepsize changes with the active set and remaining error, so a non-adaptive method using the adaptive scheme’s final stepsizes did not always outperform unoptimized stepsizes.For the illustrated imaging problem, both adaptive methods favored large τk early, then τk decayed.Source: B. Discussion · p. 14

VIII. CONCLUSION

  • The adaptive schemes have rigorous convergence results, and their practical implementations formally satisfy the identified convergence requirements.Source: §VIII · p. 14
  • Backtracking performs at least as well as methods requiring spectral information, while adaptive PDHG improves efficiency and user simplicity over non-adaptive implementations.The backtracking variant needs no problem-specific spectral information, making it useful for black-box solvers.Source: §VIII · p. 14
Loading 1305.0546v2…