Source-linked AI summary
An inertial forward-backward algorithm for monotone inclusions
Dirk A. Lorenz, Thomas Pock
TL;DR
The paper addresses computation of zeros of sums of monotone operators when one component is co-coercive, extending splitting methods beyond simpler smooth optimization settings. It proposes an inertial forward-backward algorithm with extrapolation and variable-metric preconditioning, proves convergence in Hilbert spaces, and reports faster convergence with essentially unchanged per-iteration complexity.
Problem
Finding zeros of sums of monotone operators is broadly useful, but general forward-backward schemes have weak convergence guarantees and proximal evaluations may be prohibitively expensive.
Method
The method modifies forward-backward splitting by evaluating the co-coercive operator at an inertial extrapolate and introducing a symmetric positive definite variable metric.
Results
The algorithm is proven convergent in a general Hilbert space setting and recovers several recent first-order methods as special cases.
Takeaways & Limitations
Numerical experiments show faster convergence from the inertial term while keeping each iteration’s computational complexity basically unchanged.
Takeaways & Limitations
For general monotone operators in the forward-backward setting, convergence requires restrictive step-size conditions comparable to unconstrained subgradient descent.
Abstract
from arXiv · showhide
In this paper, we propose an inertial forward backward splitting algorithm to compute a zero of the sum of two monotone operators, with one of the two operators being co-coercive. The algorithm is inspired by the accelerated gradient method of Nesterov, but can be applied to a much larger class of problems including convex-concave saddle point problems and general monotone inclusions. We prove convergence of the algorithm in a Hilbert space setting and show that several recently proposed first-order methods can be obtained as special cases of the general algorithm. Numerical results show that the proposed algorithm converges faster than existing methods, while keeping the computational cost of each iteration basically unchanged.
1 Introduction
The paper motivates splitting methods for monotone inclusions and proposes an inertial forward-backward framework that combines extrapolation with variable-metric preconditioning. It targets broader monotone problems while retaining tractable iterations and encompassing several established algorithms.
- Problem: The central problem is finding a zero of a maximal monotone operator in a real Hilbert space, encompassing variational inequalities, nonsmooth convex optimization, and convex-concave saddle-point problems.These problems have applications in image processing, computer vision, machine learning, and signal processing.
- Problem: The proximal point algorithm converges for general monotone operators, but evaluating its resolvent can be as difficult as solving the original problem.Inexact resolvent computation is also difficult to control in practice.
- Splitting methods: Forward-backward splitting makes an explicit step with respect to B followed by an implicit step with respect to A, exploiting separately computable operator components.When B is L-Lipschitz and λ_k < 2/L, the method converges to a zero of A + B.
- Splitting methods: For general monotone A and B, forward-backward convergence has weak guarantees requiring step-size restrictions comparable to unconstrained subgradient descent.The setting improves when B is single-valued and Lipschitz, including gradients of smooth convex functions.
- Inertial methods: Inertial methods extrapolate using x_k − x_{k−1}; heavy-ball acceleration combines this direction with the current antigradient direction.The inertial proximal point method extends this idea to maximal monotone operators under conditions on α_k and λ_k.
- Optimal methods: Nesterov’s method evaluates the gradient at an extrapolated point and achieves an efficiency estimate equivalent up to constants to first-order lower complexity bounds.FISTA combines Nesterov’s and proximal-point ideas within forward-backward splitting and handles an additional simple nonsmooth term.
- Proposed method: The proposed meta-algorithm evaluates B at the inertial extrapolate and uses a symmetric positive definite map M as a preconditioner or variable metric.It generalizes forward-backward splitting and includes several recent convex optimization algorithms as special cases.
2 Proposed algorithm
The paper proposes an inertial forward-backward method for finding zeros of A+B, using extrapolation before forward and backward evaluations. Under monotonicity, cocoercivity, and parameter conditions, its iterates converge weakly to solutions.
- Algorithm: The method uses yk = xk + αk(xk − xk−1) followed by xk+1 = (M + λkA)−1(M − λkB)(yk).M is a positive definite linear map that can serve as a preconditioner.
- Algorithm: The proposed algorithm modifies forward-backward splitting by evaluating B at the inertial extrapolate yk.This reformulation retains a forward step for B and a backward resolvent step for A.
- Assumptions: B is assumed single-valued and cocoercive, while A and B are maximal monotone operators in a Hilbert space.The cocoercivity is specified relative to L−1, with M and L linear, bounded, selfadjoint, and positive definite.
- Convergence: Under the theorem’s conditions on αk, λk, M, and L, xk converges weakly to a zero of A+B.The proof uses monotonicity, cocoercivity, recursive estimates, boundedness, and Opial’s theorem.
3 Application to convex-concave saddle-point problems
The paper specializes its inertial forward-backward framework to convex-concave saddle-point problems, using preconditioning to make otherwise expensive primal-dual iterations feasible. It establishes weak convergence under explicit parameter conditions and recovers several established optimization algorithms as special cases.
- Problem formulation: The saddle-point formulation uses convex functions G, Q, F ∗, and P ∗ together with a bounded linear operator K, with Q and P ∗ having Lipschitz gradients.The associated optimality system is expressed through monotone operators A and B on the product space X × Y.
- Preconditioning: Standard splitting is generally impractical because evaluating the proximal mapping of A may be prohibitively expensive.The method chooses a symmetric positive definite preconditioner M to cancel an off-diagonal block and make the primal-dual iteration feasible.
- Algorithm: The resulting inertial primal-dual forward-backward algorithm applies implicit proximal steps and explicit gradient or linear-operator steps to the primal and dual variables.Its dual update uses the resolvent of ∂F ∗ together with ∇P ∗ and K, while the construction is obtained from the preconditioned general iteration.
- Convergence: Theorem 5 states weak convergence of the iterates to a solution of the saddle-point problem under the stated step-size, inertial-parameter, and iterate conditions.The proof uses co-coercivity of the gradients, positive definiteness conditions, and the general convergence theorem.
- Convergence: Choosing γ, δ ∈(0, 2), r > 0, feasible primal and dual step sizes, and a nondecreasing inertial sequence yields weak convergence under the stated ε condition.The normalized parameters γ and δ control primal and dual step sizes, while r controls their relative scaling.
- Special cases: The framework recovers forward-backward splitting, Nesterov acceleration, the accelerated proximal point algorithm, FISTA, and several primal-dual methods through parameter choices.In particular, Nesterov’s method, the accelerated proximal point algorithm, and FISTA achieve an O(1/k2) function-gap rate, although convergence of FISTA iterates remains unresolved here.
4 Numerical experiments
The numerical experiments evaluate inertial forward-backward and primal-dual variants on image-processing and saddle-point problems, showing faster convergence under suitable parameter choices. They also identify stability limits associated with inertia, step-size ratios, and overrelaxation.
- FISTA error behavior: The FISTA safeguard keeps the error sequence convergent at rate 1/k2 when the parameter c is too small, while sufficiently large c leaves the original FISTA iterates unchanged.The safeguard shrinks αk only in the insufficient-c case.
- Primal-dual parameter study: For τ/σ = 0.1, dynamically increasing αk produces the fastest primal-dual convergence and performance similar to FISTA.For τ/σ = 0.01, convergence holds up to αk = 1/2 but fails for the dynamic choice.
- Inertia versus overrelaxation: Both inertial forces and overrelaxation improve the plain primal-dual method, while overrelaxation exhibits numerical oscillations near ρk = 2.The comparison uses αk = 1/2 for inertia, ρk = 1.9 for overrelaxation, and τ/σ = 0.01.
- Image deconvolution and primal-dual variants: For both explicit and split-dual variants, inertia accelerates convergence, and their asymptotic convergence is considerably faster than O(1/k2).The explicit variant is faster early in the iterations, while stopping occurs once the primal energy gap falls below 10−2.
5 Conclusion
The paper concludes that its inertial forward-backward framework converges in Hilbert spaces and unifies several first-order methods. Numerical experiments show faster convergence without substantially increasing per-iteration complexity, while worst-case rates remain future work.
- Contribution: The algorithm solves sums of a monotone operator with an easy resolvent and a co-coercive monotone operator.The convergence result is established in a general Hilbert space setting.
- Generalization: The framework generalizes FISTA and the Chambolle–Pock primal-dual algorithm and yields inertial primal-dual methods for convex-concave programming.These methods appear as special cases of the general algorithm.
- Numerical consequence: Numerical experiments show faster convergence from the inertial term while keeping each iteration’s computational complexity basically unchanged.
- Open limitation: Worst-case convergence rates for particular problem classes remain an open direction for future work.