Source-linked AI summary
A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity
Yura Malitsky, Matthew K. Tam
TL;DR
The paper addresses monotone inclusions for which forward-backward splitting lacks convergence guarantees without cocoercivity. It proposes forward-reflected-backward splitting, which retains Lipschitz-based weak convergence while using one forward evaluation per iteration, and discusses several extensions.
Problem
Forward-backward splitting is difficult to apply when the single-valued monotone operator is Lipschitz but not cocoercive.
Method
The paper introduces a forward-reflected-backward modification of forward-backward splitting for zeros of sums of two monotone operators.
Results
The proposed method converges weakly under Lipschitz continuity of B, like Tseng’s method, while requiring one forward evaluation instead of two.
Takeaways & Limitations
The method offers a splitting alternative for monotone inclusions without cocoercivity and is extended to linesearch, inertial, relaxed, stochastic, and three-operator settings.
Takeaways & Limitations
Inertial extensions can reduce the admissible stepsize range when B is merely monotone.
Abstract
from arXiv · showhide
In this work, we propose a simple modification of the forward-backward splitting method for finding a zero in the sum of two monotone operators. Our method converges under the same assumptions as Tseng's forward-backward-forward method, namely, it does not require cocoercivity of the single-valued operator. Moreover, each iteration only requires one forward evaluation rather than two as is the case for Tseng's method. Variants of the method incorporating a linesearch, relaxation and inertia, or a structured three operator inclusion are also discussed.
1 Introduction
The paper studies monotone inclusions where standard forward-backward splitting requires cocoercivity, and introduces a one-forward-evaluation alternative under Lipschitz continuity. It also situates the method among splitting approaches and outlines extensions to related optimization and saddle-point problems.
- Problem setting: Monotone inclusions seek x ∈ H satisfying 0 ∈ (A + B)(x), with applications across mathematical optimization.The paper assumes A and B are maximally monotone, B is locally Lipschitz continuous, and a solution exists.
- Splitting methods: Splitting methods solve operator-sum problems by evaluating individual operators through forward steps and resolvents through backward steps.The resolvent is J_A = (I + A)^−1.
- Existing methods: Forward-backward splitting uses one forward evaluation of B and one backward evaluation of A, but weak convergence requires cocoercivity of B.For 1/L-cocoercive B, the stated stepsize range is λ ∈ (0, 2/L).
- Existing methods: Cocoercivity is stronger than Lipschitz continuity, limiting forward-backward applicability to general monotone inclusions.Without cocoercivity, convergence requires stronger assumptions or backtracking.
- Existing methods: Tseng’s forward-backward-forward method replaces cocoercivity with Lipschitzness of B but requires two forward evaluations per iteration.Its weak convergence guarantee uses B L-Lipschitz and λ ∈ (0, 1/L).
- Proposed method: The proposed forward-reflected-backward method has the same Lipschitz-based convergence assumptions as Tseng’s method while requiring only one forward evaluation per iteration.For fixed λ, weak convergence is stated when B is L-Lipschitz and λ < 1/(2L).
2 Forward-reflected-backward splitting
The forward-reflected-backward method solves monotone inclusions with a monotone Lipschitz operator using one forward and one backward evaluation per iteration. Under suitable stepsizes it converges weakly, and strong monotonicity yields linear convergence.
- Algorithm: The method applies to maximally monotone A and monotone L-Lipschitz B, using one forward evaluation and one backward evaluation per iteration.Its resolvent-based update can be written as an inclusion involving the current and previous forward evaluations.
- Special cases: The forward-reflected-backward scheme recovers the proximal point algorithm when B = 0 and known projected reflected-gradient, Popov, and optimistic-gradient methods in special cases.For unconstrained variational inequalities, the method coincides with Popov’s algorithm up to a change of variable.
- Weak convergence: Under the stated variable-stepsize conditions, the generated sequence converges weakly to a zero of A + B.The convergence analysis also establishes boundedness and asymptotic regularity, with ∥x_k − x_{k+1}∥→0.
- Convergence rates: For constant stepsizes, weak convergence holds when λ satisfies the theorem’s bound, while strong monotonicity of A gives R-linear convergence to the unique solution.The linear-convergence result assumes A is m-strongly monotone and B remains monotone and L-Lipschitz.
- Comparison: On one classical skew-symmetric problem, the forward-reflected-backward method is faster than Tseng’s method in iteration count, but no general performance claim is made.The comparison is problem-specific and concerns iterations rather than computational cost more broadly.
3 Forward-reflected-backward splitting with linesearch
The linesearch variant removes the need to know a global Lipschitz constant by adapting stepsizes during iterations. In finite-dimensional spaces, it converges for monotone locally Lipschitz operators.
- Motivation: The linesearch addresses the difficulty that global Lipschitz constants can be expensive to obtain and can produce over-conservative stepsizes.The procedure is designed for settings where only local Lipschitz continuity is available.
- Convergence: In finite-dimensional H, the linesearch method converges to a point in (A + B)^−1(0) when A is maximally monotone and B is monotone and locally Lipschitz continuous.The proof uses boundedness of the iterates and the fact that locally Lipschitz operators are Lipschitz on bounded sets.
- Well-definedness: The linesearch terminates whenever B is locally Lipschitz, so the stepsizes are well defined.This termination property supports applying the convergence analysis without requiring a known global Lipschitz constant.
- Algorithm: At each iteration, the algorithm selects λ_k from a geometrically adjusted sequence until the linesearch condition is satisfied.The parameter ρ permits either retaining the previous stepsize or attempting a larger one, with larger steps potentially requiring more searches.
4 Relaxed inertial forward-reflected-backward splitting
The section develops a relaxed inertial forward-reflected-backward method for monotone inclusions, with convergence under either Lipschitz or cocoercive assumptions on B. It also characterizes admissible parameters and shows that inertia affects the allowable stepsizes differently in the two cases.
- Algorithm and assumptions: The relaxed inertial algorithm uses parameters α, β, and λ, with admissible choices depending on the properties of B.The method is analyzed for monotone L-Lipschitz or 1/L-cocoercive B.
- Admissible parameters: Figure 1 maps the upper bound for λL over α and β, marking infeasible parameter combinations in black and larger admissible values with lighter colors.The bounds are determined by conditions (41) and (42).
- Convergence: Under the theorem’s assumptions, the generated sequence (xk) converges weakly to a point in (A + B)−1(0).The result applies to maximally monotone A and nonempty solution sets.
- Interpretation: Inertia increases admissible stepsizes when B is cocoercive but has the opposite effect when B is merely monotone.The section also notes that setting B = 0 recovers the classical inertial proximal algorithm.
5 Three operator splitting
The section extends forward-reflected-backward splitting to a structured three-operator inclusion, combining a maximally monotone operator, a monotone Lipschitz operator, and a cocoercive operator. The resulting scheme exploits this structure to permit a less restrictive stepsize condition while retaining weak convergence.
- Problem setting: The target problem is to find x ∈ H such that 0 ∈ (A + B + C)(x).A is maximally monotone, B is monotone and L1-Lipschitz, and C is 1/L2-cocoercive.
- Stepsize comparison: Applying the two-operator method to A and B + C would instead use the combined Lipschitz bound L = L1 + L2.The structured scheme is introduced to improve on that resulting stepsize restriction.
- Structured method: The proposed modification exploits the operator structure and requires only λ > 0 satisfying the section’s improved bound.The improvement is stated relative to applying the two-operator method to A and B + C.
- Iteration: The modified scheme uses a standard forward step for C, as in the forward-backward method.This separates the treatment of C from the reflected correction associated with the other operator terms.
- Convergence: The three-operator theorem guarantees that (xk) converges weakly to a point in (A + B + C)−1(0).The guarantee assumes the solution set is nonempty and the theorem’s stepsize condition holds.
6 Between forward-backward and forward-reflected-backward
This section studies a stochastic intermediate variant that replaces the full reflected correction by a randomly selected component correction. Despite this perturbation, the method converges weakly almost surely without cocoercivity, though it still requires a full evaluation of B each iteration.
- Structured stochastic setting: The method assumes B decomposes as B = ∑_{i=1}^n Bi, with each Bi monotone and L-Lipschitz continuous.The analysis is carried out in a separable Hilbert space.
- Randomized correction: At each iteration, ik is chosen uniformly from {1, …, n}, and the reflected difference B(xk) − B(xk−1) is replaced by Bik(xk) − Bik(xk−1).The scheme therefore uses a randomly selected component in the correction term.
- Practical implication: The algorithm still requires one full evaluation of B in every iteration, limiting the immediate practical benefit of the randomized correction.The paper nevertheless reports convergence without cocoercivity despite the small random perturbation.
- Convergence: The resulting sequence converges weakly almost surely to a point in (A + B)−1(0).This is established under the theorem’s stepsize and operator assumptions.
- Proof strategy: The proof uses conditional expectations and a supermartingale convergence theorem to establish boundedness, vanishing successive differences, and convergence of weak cluster points.These steps lead to an (A + B)−1(0)-valued random limit.
7 Concluding remarks
The concluding section identifies open directions for understanding and extending the proposed forward-reflected-backward method. These include fixed-point interpretations, lower-cost stochastic or coordinate updates, and acceleration.
- Research outlook: The paper closes by framing these fixed-point, stochastic, coordinate, and acceleration questions as unresolved research directions.The conclusion presents them as possible extensions rather than established properties of the current method.
- Fixed point interpretations: A fixed-point interpretation remains open because the composition M ◦ T lacks sufficiently clear properties for a convergence proof.Although M is firmly nonexpansive, T need not be.
- Stochastic and coordinate extensions: Stochastic approximations and block-coordinate variants could reduce per-iteration costs when evaluating B is computationally expensive.Both directions would use low-cost approximations of B(xk).
- Acceleration schemes: The method may also be adapted with acceleration schemes motivated by accelerated proximal-gradient methods for sums of convex functions.The proposed connection is presented as a direction for further research.