Source-linked AI summary
Generalized Forward-Backward Splitting
Hugo Raguet, Jalal Fadili, Gabriel Peyré
TL;DR
The paper addresses convex objectives with one smooth but possibly non-simple term and multiple simple non-smooth terms. It proposes generalized forward-backward splitting with a gradient step and parallel proximity updates, proving convergence and robustness to computational errors. Imaging experiments show advantages over alternative splitting methods, while convergence rates and acceleration remain future work.
Problem
Existing proximal splitting methods do not explicitly handle n > 1 non-smooth terms together with a smooth but non-simple term without nested algorithms or auxiliary-variable limitations.
Method
The generalized forward-backward algorithm uses an explicit gradient step for F and parallel implicit proximity steps for the Gi terms.
Results
The algorithm converges under stated assumptions, is robust to gradient and proximity-computation errors, and shows advantages on large-scale imaging problems.
Takeaways & Limitations
The method enlarges the class of convex problems that can be addressed efficiently with proximal splitting while retaining fully separated operator computations.
Takeaways & Limitations
Convergence rates on the objective and multistep acceleration are left for future work.
Abstract
from arXiv · showhide
This paper introduces the generalized forward-backward splitting algorithm for minimizing convex functions of the form $F + \sum_{i=1}^n G_i$, where $F$ has a Lipschitz-continuous gradient and the $G_i$'s are simple in the sense that their Moreau proximity operators are easy to compute. While the forward-backward algorithm cannot deal with more than $n = 1$ non-smooth function, our method generalizes it to the case of arbitrary $n$. Our method makes an explicit use of the regularity of $F$ in the forward step, and the proximity operators of the $G_i$'s are applied in parallel in the backward step. This allows the generalized forward backward to efficiently address an important class of convex problems. We prove its convergence in infinite dimension, and its robustness to errors on the computation of the proximity operators and of the gradient of $F$. Examples on inverse problems in imaging demonstrate the advantage of the proposed methods in comparison to other splitting algorithms.
1 Introduction
The paper targets convex optimization problems combining one smooth, possibly non-simple term with multiple simple non-smooth terms. It introduces a fully split algorithm using the gradient of the smooth term and parallel proximity operators.
- State-of-the-Art in Splitting Methods: Existing forward-backward splitting handles one simple non-smooth term alongside a smooth function with Lipschitz-continuous gradient.
- State-of-the-Art in Splitting Methods: For more than two simple functions, existing approaches commonly introduce auxiliary variables and perform independent parallel proximal steps followed by averaging.
- State-of-the-Art in Splitting Methods: When the smooth term is not simple, prior work either uses nested sub-iterations or auxiliary-variable methods, creating practical or efficiency limitations.
- Applications in Image Processing: Inverse imaging problems naturally combine data-fidelity terms with non-smooth sparsity, total-variation, and composite regularizers.
- Contributions and Paper Organization: The proposed generalized forward-backward method applies an explicit gradient step and parallel implicit proximity steps for multiple simple functions, with convergence and error-robustness guarantees.
2 Generalized Forward-Backward Algorithm for Minimization Problems
The algorithm minimizes a convex sum with a differentiable smooth term and multiple simple terms by combining a gradient step with parallel proximal updates. Under stated qualification and step-size assumptions, it converges weakly, and uniformly convex objectives yield strong convergence.
- Problem Setting: The problem assumes F is convex and differentiable with 1/β-Lipschitz gradient, while each Gi belongs to Γ0(H) and is simple.
- Algorithm: Algorithm 1 updates each auxiliary zi with a relaxed proximity step using ∇F(x), then recomputes x as the weighted average of the auxiliary variables.
- Robustness: The method permits errors both in proximity-operator evaluations and in gradient evaluations.
- Convergence: Under either assumption set (A1) or (A2), the iterates converge weakly to a minimizer of the objective.
- Convergence: If (A2) holds and F is uniformly convex, convergence is strong to the unique global minimizer.
3 Monotone Operators and Inclusions
The paper recasts generalized forward-backward splitting as a monotone-inclusion method. This framework replaces subdifferentials with maximal monotone operators and uses product-space constructions to analyze parallel resolvent steps.
- Monotone Operator Extension: The generalized method extends from convex minimization to finding zeros of sums of maximal monotone operators, with one operator represented by a cocoercive single-valued map.
- Monotone Operator Extension: Subdifferentials of Γ0 functions provide the standard maximal monotone operators used to translate convex minimization into monotone inclusions.
- Operator Properties: Resolvents of maximal monotone operators are firmly non-expansive, a property used in the convergence analysis.
- Product Space: The product space H^n represents parallel operator components, while the consensus set S contains tuples with identical coordinates.
- Product Space: Concatenated scaled operators preserve maximal monotonicity when constructed from the component operators.
4 Generalized Forward-Backward Algorithm for Monotone Inclusions
The section reformulates the monotone inclusion as a fixed-point problem, builds a parallel proximal algorithm, and establishes convergence under stationary or varying step-size assumptions, including robustness to errors.
- Fixed-point formulation: The monotone inclusion is converted into an equivalent fixed-point equation for an operator combining reflected resolvents and the consensus projector.The construction uses auxiliary variables and weighted consensus geometry in a product Hilbert space.
- Fixed-point formulation: The consensus projector maps a product vector to the constant vector determined by the weighted barycenter ∑i ω_i z_i.Its projection characterization follows from minimizing the weighted squared distances to a common point.
- Algorithmic scheme: The resulting operator is assembled from non-expansive reflected resolvents, making its composition averaged and suitable for a Krasnosel’skiĭ–Mann iteration.The analysis establishes non-expansivity of the component resolvents and averagedness of the composed operator.
- Convergence and robustness: Under the theorem’s assumptions, the iterates converge weakly to a solution, while summable gradient and proximity errors are permitted.The stationary and varying-parameter cases use relaxation and error conditions specified through (A0)–(A2).
- Convergence and robustness: If the relevant monotonicity condition holds, the primal sequence converges strongly; uniform monotonicity of B yields strong convergence of the recovered solution sequence.The strong-convergence argument uses uniform monotonicity and a function vanishing only at zero.
- Convergence and robustness: The stationary-case assumptions can be weakened by replacing parameter and error requirements with corresponding summability conditions.The remark gives alternatives involving ∑t λt(1−αλt) and ∑t λt(∥ε1,t∥+∥ε2,t∥).
5 Discussion
The generalized forward-backward method connects to classical splitting schemes and is compared with related primal-dual and HPE approaches. The discussion also identifies unresolved convergence-rate questions and computational trade-offs.
- Special instances: The method specializes to relaxed forward-backward when one operator pair is used, inheriting convergence under assumptions (A0) and (A2).
- Open questions: Convergence rates for the objective and multistep acceleration remain proposed directions, while comparisons with Douglas-Rachford and Dykstra variants are left for future work.
- Special instances: With B ≡ 0 and constant γt, the method is equivalent to relaxed Douglas-Rachford on the product space, including stated relaxation and error conditions.
- Resolvents: The algorithm can compute the resolvent of a sum of maximal monotone operators by setting Bx = x − y and β = 1.
- Relation to related methods: Compared with block-decomposition HPE, generalized forward-backward supports computational errors and varying step sizes without HPE's additional dual variables.
6 Numerical experiments
The experiments apply generalized forward-backward to deblurring, inpainting, and composite imaging inverse problems with wavelet-based regularization. Across comparisons, the method benefits from explicit gradient steps and parallel proximal processing, especially in composite settings.
- Problem setup: The imaging experiments recover high-resolution images from noisy low-resolution observations using convolution, masking, or their composition as degradation operators.
- Regularization: The objective combines squared ℓ2 data fidelity with block ℓ1/ℓ2 structured sparsity and, in some experiments, total variation regularization.
- Regularization: Non-overlapping blocks permit blockwise soft-thresholding, while overlapping structures can be decomposed into finite unions of non-overlapping substructures.
- Regularization: Wavelet coefficients are grouped by resolution level and subband into square spatial blocks, with blocks of size S × S decomposed into S^2 non-overlapping structures.
- Results: For deblurring, generalized forward-backward is slightly better than comparison methods; for inpainting, it clearly outperforms them at similar computation times.
- Results: In composite problems, auxiliary variables reduce Douglas-Rachford efficiency, while HPE and CoPe require more computational time than generalized forward-backward.
7 Conclusion
The paper introduces a proximal splitting method for a smooth convex term plus several simple functions and establishes convergence and error robustness. Imaging experiments provide evidence of advantages on large-scale inverse problems, while convergence rates and acceleration remain open.
- The generalized forward-backward method handles a smooth term and several simple functions, extending proximal methods to this composite setting.
- The paper proves convergence and robustness to errors for a broader monotone-inclusion problem involving maximal monotone operators and one cocoercive operator.
- Numerical inverse-problem experiments show evidence of advantages for large-scale imaging problems.
- Objective convergence rates and multistep acceleration are left as future work.