Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications

Antonin Chambolle; Matthias J. Ehrhardt; Peter Richtárik; Carola-Bibiane Schönlieb

Source-linked AI summary

Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications

Antonin Chambolle, Matthias J. Ehrhardt, Peter Richtárik, Carola-Bibiane Schönlieb

arXiv:1706.04957v2Jun 15, 2017math.OCcs.CVmath.NA

TL;DR

The paper addresses the cost of repeatedly performing all PDHG operations for separable-dual saddle-point problems. It introduces a stochastic, arbitrarily sampled extension with convergence analysis covering deterministic special cases and reports superior imaging performance. The scope includes general convex-concave problems and partially or fully strongly convex/smooth settings.

Problem
Repeatedly performing all simple PDHG operations can still be too costly, motivating a method that updates only selected dual-variable operations.
Method
The paper extends PDHG to i.i.d. proper arbitrary sampling of dual-variable blocks and analyzes convergence using a framework that includes the deterministic case.
Results
Several stochastic variants show superior empirical performance on a variety of imaging optimization problems, while known deterministic convergence results are recovered as special cases.
Takeaways & Limitations
The method enables stochastic PDHG updates with only a subset of dual operations per iteration and supports convergence under broad fixed sampling schemes.
Takeaways & Limitations
The present optimal sampling strategies are limited to scalar-valued step sizes and serial sampling, with adaptive, multi-block, and parallel extensions left for future work.

Abstract

from arXiv · show

We propose a stochastic extension of the primal-dual hybrid gradient algorithm studied by Chambolle and Pock in 2011 to solve saddle point problems that are separable in the dual variable. The analysis is carried out for general convex-concave saddle point problems and problems that are either partially smooth / strongly convex or fully smooth / strongly convex. We perform the analysis for arbitrary samplings of dual variables, and obtain known deterministic results as a special case. Several variants of our stochastic method significantly outperform the deterministic variant on a variety of imaging tasks.

1. Introduction.

The paper introduces a stochastic PDHG extension that updates only selected dual-variable operations, supports broad sampling schemes, and recovers deterministic results as a special case. Its analysis covers improved rates, acceleration under strong convexity, and scaling-invariant parameter choices.

1. Introduction.: PDHG is widely used for convex saddle-point problems, but even its simple matrix-vector operations can be too costly to perform at every iteration.The paper motivates reducing per-iteration computational work in imaging and other applications.
1. Introduction.: The proposed stochastic PDHG updates only a few operations for each iteration and incrementally reuses information to reduce variance effects.The method targets saddle-point problems separable in the dual variable.
1. Introduction.: The stochastic algorithm and analysis recover almost all deterministic results when every iteration performs all computations.The deterministic and stochastic cases can therefore be treated through a single proof.
1. Introduction.: Arbitrary-sampling convergence holds for i.i.d. samplings in which every computation has non-zero selection probability.This framework generalizes analyses restricted to specific samplings.
1. Introduction.: Strong convexity accelerates convergence from O(1/K) to O(1/K2), while strongly convex serial-sampling parameters can be chosen independently of scaling.The paper also reports better rates than prior results in a special uniform setting.

2. General Problem.

The paper formulates a separable convex optimization problem in product Hilbert spaces and converts it into an equivalent convex-concave saddle-point problem. It then permits arbitrary proper sampling of dual-variable blocks within the PDHG framework.

2. General Problem.: The dual space is a product Y = Qn_i=1 Yi, with block components yi and a summed inner product and norm.The primal-dual space combines X and Y.
2. General Problem.: A bounded linear operator A maps X to Y blockwise as (Ax)i = Aix, with adjoint A∗y formed by summing the block adjoints.This block structure supports separable dual computations.
2. General Problem.: The model assumes convex functions g and separable f(y) = Pn_i=1 fi(yi), then uses Fenchel conjugacy to obtain an equivalent saddle-point formulation.The primal solution is the primal component of a saddle point.
2. General Problem.: Regularity is analyzed in three cases: no strong convexity, partial strong convexity, and full strong convexity.The parameters satisfy µg, µi ≥ 0, with the corresponding positive inequalities defining the latter cases.
2. General Problem.: The stochastic setting samples a random dual-variable subset i.i.d. from a fixed proper distribution, requiring every block to have positive selection probability.Full sampling and serial sampling are examples, but other subset samplings are also admissible.

3. Algorithm.

Algorithm 1 extends PDHG by sampling dual blocks and evaluating their operators selectively, while retaining positive-definite step operators and extrapolation. Convergence analysis for broad samplings uses an expected separable overapproximation inequality.

3. Algorithm.: Algorithm 1 uses self-adjoint positive-definite operators T and Si together with scalar extrapolation θ > 0 and a probability operator Q.These choices keep the stochastic updates well-defined.
3. Algorithm.: Both primal and dual iterates are random variables, but only the dual iterate directly depends on the current sampling.The primal iterate depends indirectly on all earlier samplings.
3. Algorithm.: At each iteration, the method selects a subset S(k+1) of dual indices and updates only the corresponding dual blocks.The primal update uses the stored dual information before the selected-block update.
3. Algorithm.: Only Ai and A∗i for selected indices need evaluation, while A∗y(k) can be stored from the previous iteration.This reduces repeated operator evaluations while requiring memory comparable to the primal variable.
3. Algorithm.: The general convex convergence analysis handles the broad sampling class through the expected separable overapproximation inequality.This inequality is the main analytical device for arbitrary sampling.

4. General Convex Case.

The general convex analysis establishes convergence of the stochastic PDHG under arbitrary samplings using ESO parameters, recovering deterministic behavior under full sampling and yielding almost-sure and expected 1/K guarantees.

Expected Separable Overapproximation: ESO parameters quantify sampling-dependent bounds used to analyze expected inner products and convergence for arbitrary random subsets of dual blocks.They are not unique; tighter parameters are desirable because they influence algorithmic choices such as extrapolation.
Sampling and deterministic limit: The stochastic algorithm updates selected dual blocks while retaining information from previous iterations, and full sampling recovers the deterministic PDHG setting.For full sampling, all blocks are selected with probability one; serial sampling selects one block according to its sampling probability.
Convergence guarantees: Under the condition v_i < p_i, the Bregman distance between iterates and any saddle point converges to zero almost surely.The theorem assumes convex primal and dual functions and uses ESO parameters associated with the sampling.
Convergence guarantees: The expected partial primal-dual gap and expected Bregman distance converge at rate 1/K in the general convex case.The partial primal-dual gap is defined over bounded sets containing the relevant saddle point when applicable.
Interpretation and scope: The Bregman-distance guarantee implies norm convergence when the relevant functional h is strictly convex, but otherwise describes a more generalized convergence notion.For an ℓ1-norm, zero Bregman distance corresponds to matching support and sign; if h ≡ 0, the convergence statement has no meaning.

5. Semi-Strongly Convex Case.

The semi-strongly convex analysis develops stochastic PDHG variants with acceleration on either the dual or primal variable, obtaining faster convergence under strong-convexity and ESO conditions.

Setup: The analysis restricts step sizes to scalar values for simplicity, while noting that much of the theory also applies to operator-valued step sizes.The strong-convexity setting concerns cases where either dual conjugates or the primal functional is strongly convex.
Primal acceleration: PA-SPDHG accelerates on the primal variable while retaining stochastic dual-block updates selected at each iteration.Its iteration includes proximal primal updates, subset selection, and extrapolation based on the updated step size.
Dual acceleration: DA-SPDHG accelerates on the dual variable through adaptive primal and dual step-size updates and extrapolation after randomly selecting dual blocks.The algorithm uses a scalar auxiliary dual step size and sampling sets S^(k).
Dual strong convexity: When dual components are strongly convex, Theorem 5.1 provides an eventual accelerated convergence estimate under initial-step-size and ESO-parameter conditions.The estimate applies for all K beyond a finite threshold K̃, which is described as usually fairly small.
Primal acceleration: The primal-acceleration variant converges at rate O(1/K^2) when the ESO parameters satisfy v_i < p_i.This condition links the accelerated rate to the sampling probabilities and the sampling-dependent ESO bounds.

6. Strongly Convex Case.

In the strongly convex case, the analysis establishes linear convergence and derives scaling-invariant serial-sampling parameters and rates for uniform, importance, and optimal sampling. The optimal sampling rate is strictly better when condition numbers differ, while the framework also recovers deterministic results and supports minibatches.

Linear convergence: The strongly convex analysis proves that Algorithm 1 converges linearly to the saddle point under suitable step-size and extrapolation conditions.The conditions involve the ESO parameters of the sampling and strong-convexity constants.
Scaling invariance: The proposed condition numbers are scaling invariant, so rescaling the primal and dual variables cannot improve the derived rates.The condition numbers combine operator norms with the strong-convexity parameters.
Serial sampling: For serial sampling, the analysis derives convergence-rate parameters for uniform, importance, and optimal sampling based on the problem condition numbers.Uniform sampling assigns equal probabilities, whereas importance sampling samples blocks proportionally to the square root of their condition numbers.
Serial sampling: Optimal sampling matches uniform sampling when all condition numbers are equal and is strictly better when they differ.The analysis also states that optimal sampling is better than importance sampling.
Deterministic and minibatch cases: The stochastic algorithm reduces to the deterministic algorithm when every block is computed, and its analysis recovers almost all corresponding deterministic statements.The framework also extends to fixed-size minibatch samplings, while the analyzed comparison focuses on serial samplings.
Comparison to prior rates: Compared with the referenced method, the proposed rate is slightly better for uniform single-row sampling and can improve further with non-uniform sampling when row norms differ.For minibatch size greater than one, the passage reports larger rate differences because the comparison method estimates condition numbers conservatively.

7. Numerical Results.

The numerical experiments evaluate SPDHG and accelerated variants on PET reconstruction, TV denoising, and Huber-TV deblurring. Across these imaging tasks, stochastic sampling and acceleration consistently improve convergence relative to deterministic baselines.

Experimental parameters: The experiments used uniform sampling with subset counts varying across deterministic and stochastic settings, including 50 and 250 PET subsets.Step sizes were selected separately for the compared algorithms and sampling configurations.
7.1. Non-Strongly Convex PET Reconstruction.: After 5 epochs with 50 uniformly sampled subsets, both stochastic methods made more progress toward the saddle point than PDHG with the same operator evaluations.The comparison includes PDHG, Pesquet&Repetti, and SPDHG.
7.1. Non-Strongly Convex PET Reconstruction.: PET reconstruction with TV showed SPDHG converging faster than deterministic PDHG and Pesquet&Repetti, while ergodic Bregman distance followed O(1/K).Figure 1 compares convergence using ergodic Bregman distance and relative objective.
7.2. TV denoising with Gaussian Noise (Primal Acceleration).: In TV denoising, accelerated algorithms were much faster than non-accelerated versions, and stochastic PA-SPDHG exceeded deterministic PA-PDHG.Accelerated SPDHG converged as 1/K^2 in the norm of the primal part, with visual confirmation from denoised images.
7.3. Huber-TV Deblurring (Dual Acceleration).: For Huber-TV deblurring, acceleration improved dual and primal convergence, while combining randomization with acceleration produced further speed-ups and O(1/K^2) dual-distance convergence.The same number of epochs could also yield sharper images with randomization.
7.4. PET Reconstruction (Linear Rate).: In strongly convex PET reconstruction, randomization accelerated both saddle-point distance and objective convergence; SPDHG with 50 subsets was much faster than Pesquet&Repetti.The experiments also confirmed linear convergence and showed SPDHG visually close to the saddle point after 10 epochs.

8. Conclusions and Future Work.

The paper concludes that SPDHG provides a stochastic generalization of PDHG for dual-separable convex-concave saddle problems, with arbitrary-sampling analysis and strong imaging performance. Future work targets adaptive probabilities, broader strong-convexity assumptions, and non-serial sampling strategies.

Conclusions: The authors propose a stochastic PDHG generalization for convex-concave saddle problems separable in the dual variable.The algorithm updates only a random subset of dual variables while retaining convergence analysis under arbitrary sampling.
Conclusions: The analysis recovers known deterministic convergence results as special cases and supports optimal step-size choices with strong empirical imaging performance.The reported empirical performance spans a variety of imaging optimization problems.
Future Work: Future work includes iteration-dependent probabilities, stronger use of strong-convexity parameters, and extensions to multi-block or parallel sampling.The current optimal sampling strategies are limited to scalar-valued step sizes and serial sampling.

Appendix A. Postponed Proofs.

The appendix postpones technical proofs establishing the stochastic convergence estimates and accelerated-rate results. Its arguments use proximal-operator inequalities, expectation identities, extrapolation, and generalized distance estimates.

Proofs: The proof of Lemma 4.2 combines the definitions of y+ and Q with completing-the-square manipulations and expectation estimates.The argument invokes the ESO inequality and the sampling expectation definition.
Proofs: The proof of Lemma 4.4 sums proximal-operator inequalities and completes generalized primal and dual distances on the product space.The derivation uses the product-space inner product and norm identities.
Proofs: The proof of Lemma 5.2 follows the Lemma 4.3 argument for a saddle point and rewrites Lemma 4.4 accordingly.The proof specializes the estimate to w♯=(x♯,y♯).
Proofs: The appendix also records extrapolation and conditional-expectation steps used to derive the stochastic convergence assertion.These steps connect the algorithmic extrapolation to the expected inequalities used in the proofs.