Source-linked AI summary
A new primal-dual algorithm for minimizing the sum of three functions with a linear operator
Ming Yan
TL;DR
The paper studies minimizing a sum of three functions under smoothness and operator assumptions. It proposes PD3O, which recovers established two-function primal-dual algorithms as special cases, and reports convergence guarantees and favorable comparisons with other three-function methods.
Problem
The paper addresses minimizing f(x) + g(x) + h□l(Ax) for convex functions, a form that covers problems in image and signal processing, statistics, and machine learning.
Source: §1 · pp. 1–2Method
PD3O is a primal-dual three-operator splitting algorithm that generalizes Chambolle-Pock and PAPC and recovers Davis-Yin when A = I with special parameters.
Source: §1 · p. 4Results
The iteration is α-averaged, the primal-dual gap has an ergodic convergence result, and linear convergence is shown under additional assumptions; experiments report effectiveness and efficiency.
Source: §1 · p. 5, §5 · p. 21Takeaways & Limitations
Compared with PDFP, AFBA, and Condat-Vu, PD3O combines low per-iteration complexity with a large range of convergence-acceptable parameters.
Source: §5 · p. 21The stated problem class assumes bounded linear A, Lipschitz-continuous gradients for f and l*, and proximal mappings for g and h that are analytical or efficiently computable.
Source: §1 · p. 2
Abstract
from arXiv · showhide
In this paper, we propose a new primal-dual algorithm for minimizing $f(x) + g(x) + h(Ax)$, where $f$, $g$, and $h$ are proper lower semi-continuous convex functions, $f$ is differentiable with a Lipschitz continuous gradient, and $A$ is a bounded linear operator. The proposed algorithm has some famous primal-dual algorithms for minimizing the sum of two functions as special cases. E.g., it reduces to the Chambolle-Pock algorithm when $f = 0$ and the proximal alternating predictor-corrector when $g = 0$. For the general convex case, we prove the convergence of this new algorithm in terms of the distance to a fixed point by showing that the iteration is a nonexpansive operator. In addition, we prove the $O(1/k)$ ergodic convergence rate in the primal-dual gap. With additional assumptions, we derive the linear convergence rate in terms of the distance to the fixed point. Comparing to other primal-dual algorithms for solving the same problem, this algorithm extends the range of acceptable parameters to ensure its convergence and has a smaller per-iteration cost. The numerical experiments show the efficiency of this algorithm.
1 Introduction
The paper introduces PD3O for a three-function primal-dual problem and relates it to existing splitting methods. It presents theoretical convergence results and reports advantages over other algorithms for the same problem.
1 Introduction
- Earlier reformulations can introduce extra dual variables or an inconvenient proximal mapping, while existing three-function methods trade parameter range against iteration cost.The forward-backward-forward scheme requires two gradient evaluations and four linear operators per iteration; PDFP uses two proximal mappings of g, while AFBA has a conservative stepsize.Source: §1 · pp. 3–4
- When A = I, PD3O recovers Davis-Yin and thereby connects to several two-operator splitting schemes.These include forward-backward, backward-forward, Peaceman-Rachford, and forward-Douglas-Rachford splitting.Source: §1 · pp. 4–5
- PD3O combines low per-iteration complexity with PDFP's larger convergence-parameter range; experiments show advantages over Condat-Vu, AFBA, and PDFP.It recovers Chambolle-Pock and PAPC when f or g is absent.Source: §1 · pp. 3–4
- The PD3O iteration is proved α-averaged, a stronger result than the nonexpansiveness-only result for PAPC.The paper also shows Chambolle-Pock is equivalent to Douglas-Rachford splitting under a different metric.Source: §1 · p. 5
- The paper establishes ergodic convergence for the primal-dual gap and linear convergence under additional assumptions.It also reports convergence of the general convex-case iteration.Source: §1 · p. 5
2 Connections to existing algorithms
The section relates PD3O to established splitting methods through special cases, then compares its convergence parameters and per-iteration costs with PDFP, Condat–Vu, and AFBA.
2 Connections to existing algorithms
- For the comparison, the algorithm is reformulated by replacing z with x-bar, and the section sets l = ι{0} to simplify the infimal-convolution case.The reformulation uses x-bar = 2x − z − γ∇f(x) − γAᵀs.Source: §2 · p. 5
2.1 Three special cases
- With g = 0 PD3O reduces to PAPC, with f = 0 it reduces to Chambolle–Pock, and with A = I and γδ = 1 it reduces to Davis–Yin.The PAPC iteration is also shown to be α-averaged; Chambolle–Pock is shown equivalent to Douglas–Rachford splitting under a different metric.Source: §2.1 · p. 6
2.2 Comparison with three primal-dual algorithms for three functions
- PD3O allows more freedom in parameter choice than Condat–Vu, while AFBA has a more conservative parameter range than PDFP and Condat–Vu.Table 1 compares convergence conditions and their relations to the reduced primal-dual algorithms; the supplied passage does not give its cell values.Source: §2.2 · p. 7, Table 1 · p. 7
- PD3O adds no per-iteration cost over Condat–Vu apart from storing ∇f(x), whereas PDFP applies proxγg twice and can cost more than the other algorithms.When the proximal mapping is simple, PDFP's additional cost may be small relative to other operations in an iteration.Source: §2.2 · pp. 7–8
3 The proposed primal-dual algorithm
This section analyzes the convergence properties of PD3O, relating its fixed points to minimizers and establishing convergence results for the general convex case. It also gives an ergodic primal-dual gap bound and linear convergence under additional assumptions, with averagedness results for the Chambolle–Pock and PAPC special cases.
3.1 Notation and preliminaries
- The analysis uses a weighted metric M, requiring it to be positive definite when ∇l* is nonconstant and only positive semidefinite when ∇l* is constant.The preliminaries also assume f, g, h, and l are proper lower semi-continuous convex functions.Source: §3.1 · p. 8
3.2 Convergence analysis for the general convex case
- When M is positive definite and gamma <= 2beta, PD3O is nonexpansive and is alpha-averaged with alpha = 2beta/(4beta-gamma).The analysis establishes nonexpansiveness using the weighted norm on the primal-dual variables.Source: §3.2 · p. 11
- The Chambolle–Pock case is firmly nonexpansive when gamma delta ||AA^T|| <= 1, while the PAPC case is alpha-averaged when gamma < 2beta and gamma delta ||AA^T|| < 1.For PAPC, alpha = 2beta/(4beta-gamma).Source: §3.2 · p. 13
- A fixed point (z*, s*) yields an optimal solution prox_gamma g(z*), and every optimal solution satisfying the stated inclusion corresponds to such a fixed point.The converse correspondence is stated for optimal solutions satisfying 0 ∈ ∂g(x*) + ∇f(x*) + A^T∂(h□l)(Ax*).Source: §3.2 · p. 13
- For gamma < 2beta, iterates stay at nonincreasing distance from a fixed point, the fixed-point residual tends to zero, and the sequence converges weakly to a fixed point.The residual sequence is also monotonically nonincreasing.Source: §3.2 · p. 14
- If X is finite dimensional, z^k converges strongly, and x^k does as well because the proximal operator in (4a) is nonexpansive.Source: §3.2 · p. 15
3.3 O(1/k)-ergodic convergence for the general convex case
- For γ ≤ β under Assumption 1, the ergodic primal-dual gap is bounded by 1/[2(k + 1)γ] times the squared initial distance in the I,M norm.The bound applies to L(x̄k, s) − L(x, s̄k+1) for the ergodic iterates and any (x, s) in X × S.Source: §3.3 · p. 15
3.4 Linear convergence rate for special cases
- When g has an Lg-Lipschitz continuous gradient, PD3O converges linearly if γ < 2β, τh* + τl* > 0, and τf + τg > 0, yielding ρ < 1.The result is stated under Assumption 1.Source: §3.4 · p. 18
4 Numerical experiments
The fused-lasso experiments compare four unaccelerated primal-dual algorithms while varying their stepsizes. PD3O and PDFP can use larger stepsizes than Condat-Vu and AFBA, and PD3O is slightly better than PDFP in the reported comparison.
4 Numerical experiments
- The experiment uses n = 500, p = 10000, a standard-Gaussian random matrix A, Gaussian noise of variance 0.01, and μ1 = 20 and μ2 = 200.Only iteration counts are recorded because per-iteration costs are described as very close; the extra proximal mapping in PDFP can be ignored in this example.Source: §4 · p. 20
- Figure 1 compares primal objective values and distances to the optimum against iteration number, varying γ in the top plots and λ in the bottom plots.The top plots fix λ = 1/8; the bottom plots fix γ = 1.9β.Source: Figure 1 · p. 20
- PD3O and PDFP converge faster with larger γ, while Condat-Vu and AFBA do not satisfy their convergence conditions at γ = 1.5β or 1.99β when λ = 1/8.When all four converge at γ = β, their performance is very close; the reported speed is almost linear in γ, with doubling γ reducing iterations by half.Source: §4 · p. 21
- With γ = 1.9β, increasing λ from 1/8 to 1/4 brings no convergence improvement and performs worse after 2000 iterations; PD3O is slightly better than PDFP in iterations and per-iteration complexity.The authors suggest choosing λ somewhat large, but report little additional advantage once it is large enough in this experiment.Source: §4 · p. 21
5 Conclusion
The conclusion presents PD3O as a primal-dual three-operator splitting scheme for the three-function problem. It identifies two-function special cases and advantages over three existing primal-dual algorithms, while leaving acceleration and other modifications for future work.
5 Conclusion
- PD3O solves the three-function problem and recovers Chambolle-Pock and PAPC as special cases for two-function problems.With A = I and special parameters, it reduces to Davis-Yin.Source: §5 · p. 21
- Compared with PDFP, AFBA, and Condat-Vu, PD3O combines low per-iteration complexity with a large range of convergence-acceptable parameters.Source: §5 · p. 21
- The numerical experiments show the effectiveness and efficiency of PD3O; acceleration and other modifications remain future work.Source: §5 · p. 21