PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymmetric Forward-Backward-Adjoint Splitting for Solving Monotone Inclusions Involving Three Operators

Puya Latafat, Panagiotis Patrinos

arXiv:1602.08729v3math.OC

TL;DR

Classical splitting methods are not well equipped for three-operator monotone inclusions, and FBFS requires two evaluations of the cocoercive operator per iteration when it combines that operator with the bounded linear one. The paper introduces Asymmetric Forward-Backward-Adjoint splitting (AFBA), which handles the inclusion directly and recovers several classical algorithms as special cases. It establishes convergence rates for AFBA, including linear convergence under metric subregularity.

  • Problem

    Classical FBS and DRS are designed for two operators, while FBFS can combine the bounded linear and cocoercive operators but then requires two evaluations of the cocoercive operator per iteration.

    Source: §1 · p. 1

  • Method

    AFBA solves the three-operator monotone inclusion without reformulation, using asymmetric preconditioning to recover and unify existing splitting schemes.

    Source: §1 · p. 2

  • Results

    AFBA has big-O(1/(n + 1)) and little-o(1/(n + 1)) convergence rates, and linear convergence under metric subregularity of the underlying operator.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Because AFBA generalizes a wide range of algorithms, its convergence analysis provides a systematic way to deduce rates for many algorithms.

    Source: §1 · p. 2

    The paper does not consider the easily derived generalization of Lemma 5.2 to several composite functions.

    Source: §5 · p. 20

Abstract

from arXiv · show

In this work we propose a new splitting technique, namely Asymmetric Forward-Backward-Adjoint splitting, for solving monotone inclusions involving three terms, a maximally monotone, a cocoercive and a bounded linear operator. Classical operator splitting methods, like Douglas-Rachford and Forward-Backward splitting are special cases of our new algorithm. Asymmetric Forward-Backward-Adjoint splitting unifies, extends and sheds light on the connections between many seemingly unrelated primal-dual algorithms for solving structured convex optimization problems proposed in recent years. More importantly, it greatly extends the scope and applicability of splitting techniques to a wider variety of problems. One important special case leads to a Douglas-Rachford type scheme that includes a third cocoercive operator.

1. Introduction

The paper targets monotone inclusions with a maximally monotone, bounded linear, and cocoercive operator, a combination classical splittings do not handle directly without trade-offs. It introduces AFBA to solve these inclusions and connect them to primal-dual algorithms, with convergence-rate results and applications to structured convex optimization.

1. Introduction

  • Classical Forward-Backward and Douglas-Rachford splitting are designed for two operators, while Forward-Backward-Forward handles the three-term inclusion by treating M + C together and evaluating C twice per iteration.The inclusion has A maximally monotone, M bounded linear, and C cocoercive.Source: §1 · p. 1
  • AFBA solves the three-operator inclusion without reformulation, and its asymmetric preconditioning unifies existing primal-dual schemes and yields new ones.Forward-Backward, Douglas-Rachford, and Proximal Point algorithms arise as special cases.Source: §1 · p. 2
  • AFBA has O(1/(n + 1)) and o(1/(n + 1)) convergence rates; metric subregularity also guarantees linear convergence without parameter restrictions.The paper says the rates hold under mild conditions in many cases.Source: §1 · p. 2
  • For structured convex optimization, the saddle-point formulation avoids proximal mappings of linearly composed functions and lets AFBA recover existing methods, often with broader convergent step-size and relaxation ranges.The resulting algorithms require matrix-vector products, gradients, and proximal updates.Source: §1 · pp. 2–3

2. Backround and Preliminary Results

This section establishes Hilbert-space notation and recalls operator and convex-analysis definitions used later. It also defines weighted norms and the proximal, projection, and normal-cone constructions.

2. Backround and Preliminary Results

  • A strongly positive self-adjoint operator U defines a weighted inner product and norm on H, and the induced operator norm is measured in that metric.The section also gives the corresponding operator norm through U^(1/2) L U^(-1/2).Source: §2 · p. 3
  • For a set-valued operator, the section defines its domain, graph, zero set, inverse, and resolvent, and characterizes monotonicity and maximal monotonicity.The resolvent is J_A = (Id + A)^(-1).Source: §2 · p. 3
  • For proper lower semicontinuous convex functions, the section defines Fenchel conjugates and subdifferentials; the resolvent of a subdifferential is the proximal operator.The subdifferential of f has inverse ∂f*.Source: §2 · pp. 3–4
  • For a nonempty closed convex set, its indicator's subdifferential is the normal cone, and the section defines weighted distance and projection onto the set.Without a superscript, distance and projection use the canonical norm.Source: §2 · p. 4

3. Asymmetric Forward-Backward-Adjoint Method

AFBA addresses three-operator inclusions using a selectable metric for expressing cocoercivity. Its convergence analysis identifies the relevant fixed-point set, establishes convergence of transformed iterates, and gives convergence rates and stronger properties under specified conditions.

3. Asymmetric Forward-Backward-Adjoint Method

  • Choosing P is central to AFBA: expressing C’s cocoercivity in the P-norm simplifies the convergence statements without restricting the setting.The passage notes that convergence in the canonical and P-norms is equivalent, while the canonical-norm formulation would involve norms of P and P⁻¹.Source: §3 · p. 4

3.1. Convergence Analysis.

  • AFBA iterates are Fejér monotone and converge weakly to a zero of T, while the auxiliary sequence converges strongly to zero.When C ≡ 0, the convergence statements also hold with δ = 2.Source: §3.1 · p. 5
  • Under further step-size restrictions, the sequence itself has big-O(1/(n + 1)) and little-o(1/(n + 1)) convergence rates; the little-o rate additionally requires (6), (16), and λ_n(δ − λ_n) ≥ τ > 0.Source: §3.1 · pp. 7–8
  • If T is metrically subregular at every solution and either H is finite-dimensional or U = H, distances to zer(T) converge Q-linearly and iterates converge R-linearly.The auxiliary sequence norms also converge R-linearly to zero; for C ≡ 0, the result holds with δ = 2.Source: §3.1 · p. 9
  • For C ≡ 0 with M skew-adjoint, AFBA permits positive, not necessarily strongly positive, P; in finite dimensions, the resulting iteration converges under the stated continuity and step-size assumptions.The theorem also gives ∥Pz_{n+1} − Pz_n∥² = o(1/(n + 1)).Source: §3.1 · pp. 10–11
  • The analysis proves Fix(G′) = Q zer(T), Fejér monotonicity and convergence of x_n to that set, while G(z_n) converges to a zero of T.The proof also establishes convergence of z_n.Source: §3.1 · pp. 12–13
  • The analysis establishes big-O convergence for (Pz_n) and little-o convergence for ∥x_n − x_{n+1}∥².Source: §3.1 · p. 14

4. Operator Splitting Schemes as Special Cases

The section shows how choices of AFBA parameters recover classical splitting schemes and produce a Douglas–Rachford-type method with a forward term. It also gives convergence results and compares the method’s parameter range with an existing three-operator scheme.

4.1. Forward-Backward Splitting.

  • For FBS, γ can range over ]0, 4β[, wider than the standard averaged-operator bound ]0, 2β].If C ≡ 0, FBS reduces to the classical proximal point algorithm.Source: §4.1 · p. 14

4.2. Solodov and Tseng.

  • With C ≡ 0, A = N_X, and H = Id, Algorithm 1 recovers the Solodov–Tseng scheme [33, Algorithm 2.1].For skew-adjoint M, a specified parameter choice simplifies Algorithm 1 to the update shown in the section.Source: §4.2 · p. 14

4.3. Forward-Backward-Forward Splitting.

  • When C ≡ 0, the forward-backward-forward specialization yields FBFS for the skew-adjoint Lipschitz operator M.The cited stepsize range is γ ∈ ]0, ∥M∥^-1[.Source: §4.3 · p. 14

4.4. Douglas-Rachford Type with a Forward Term.

  • The section selects P, K, and S to derive a Douglas–Rachford-type splitting that includes a forward term.Algorithm 2 uses resolvent updates for D and E, a forward evaluation of F, and relaxation parameters.Source: §4.4 · pp. 15–16
  • For θ = 2, the forward-term Douglas–Rachford-type method converges weakly under the stated finite-dimensional conditions; when F ≡ 0 and metric subregularity holds, linear convergence follows without additional assumptions.For θ ∈ [0, 2[, the authors omit convergence-rate results, though they say rates can be deduced from Theorem 3.2.Source: §4.4 · p. 16
  • Algorithm 2 places the forward step before the backward update, unlike the three-operator Douglas–Rachford generalization in [18].For θ ∈ [0, 2[, its step-size range can be larger, but reducing θ tightens the relaxation-parameter bound and may not help in practice.Source: §4.4 · pp. 16–17
  • When F ≡ 0 and θ = 2, Algorithm 2 recovers classical Douglas–Rachford splitting with ρ_n = 1.This parameter choice is identified as the classical DRS special case.Source: §4.4 · p. 17

5. Structured Nonsmooth Convex Optimization

This section applies AFBA’s flexible parameters to structured nonsmooth convex optimization, presenting a framework that unifies and generalizes primal-dual schemes and includes special cases such as forward Douglas–Rachford and a three-block ADMM. It gives convergence guarantees and conditions for the general algorithm and its special cases, and describes their relations to other methods.

5. Structured Nonsmooth Convex Optimization

  • Independent choices of P, K, and S let AFBA recover or generalize schemes by Vu and Condat, Briceño-Arias and Combettes, and Drori, Sabach, and Teboulle, and motivate a three-block ADMM generalization.The section presents these connections in Figure 1.Source: §5 · p. 17
  • The strong-positivity bound for P is less conservative than an alternative, and the selected S and D are strongly positive under the same condition as P.The latter choice adds no parameter constraint; the larger positivity parameter also yields a less conservative cocoercivity parameter for C.Source: §5 · p. 20
  • Algorithm 3’s iterates converge weakly to a primal-dual solution under the theorem’s stated conditions, with less conservative conditions available when l = ι{0} or h ≡ 0.For equal step parameters, the general condition simplifies to γ < 4/(2θ∥L∥ + max{βh,βl}).Source: §5 · pp. 21–22

5.1. Special Case θ = 2.

  • At θ = 2, Algorithm 3 specializes to the Vu–Condat method, with convergence conditions less restrictive than those of and stated big-O and little-o rates.The rate result requires λn(δ − λn) to be bounded below by a positive constant.Source: §5.1 · pp. 22–23

5.2. Special Case θ = 0, µ = 1

  • At θ = 0 and µ = 1, the scheme generalizes Briceño-Arias and Combettes, loses Gauss–Seidel-type proximal updates, and has positive definite P for any γi > 0.With αn = 1 it converges weakly under the stated conditions; when γ1 = γ2, h ≡ 0, and l = ι{0}, it recovers the error-free version of [6, Algorithm (4.8)].Source: §5.2 · pp. 23–24

5.3. Special Case θ = 1, µ = 1.

  • At θ = 1 and µ = 1, Algorithm 3 gives Arrow–Hurwicz updates that generalize the scheme of Drori, Sabach, and Teboulle, with weak convergence under the stated conditions.An o(1/(n + 1)) rate is also derived, but under more restrictive conditions than those for convergence.Source: §5.3 · pp. 24–25
  • The part relates Algorithm 6 to Algorithm 3 with µ=0, h≡0, and l=ι{0}, and identifies Algorithm 7 as the Douglas–Rachford-type scheme with a forward term.Algorithm 8 applies Algorithm 7 to a dual formulation.Source: §5.4 · pp. 25–26

5.4. Special Case: µ = 0.

  • For h≡0 and l=ι{0}, Algorithm 6 converges weakly to a solution pair under either of Proposition 5.4’s parameter conditions.The supplied passage states the convergence conclusion but only partially specifies those conditions.Source: §5.4 · p. 26
  • Algorithm 8 is derived by applying Algorithm 7 with unit relaxation to the dual problem; its first minimization uses the normal Lagrangian and can run in parallel with the second step.The first minimization is trivially distributable when f1 is block-separable.Source: §5.4 · pp. 26, 28
  • Algorithm 8’s three-block ADMM converges to a saddle point when the saddle set is nonempty, the spaces are finite-dimensional, θ∈]1,2[, f1 is strongly convex, and ker(L2)=ker(L3)={0}.The stated result also assumes fi∈Γ0(Hi) and b∈H4.Source: §5.4 · p. 27
  • Unlike the formulation in [18], Algorithm 8 updates x1 and x2 in parallel and evaluates its augmented-Lagrangian updates at (θ−1)yn+(2−θ)yn−1, while requiring rank assumptions on L2 and L3.The passage also says its stepsize bound is always larger than the bound in [18, Theorem 2.1].Source: §5.4 · p. 28

6. Conclusion and Future Work

AFBA unifies and extends operator-splitting methods for three-term monotone inclusions, with asymmetric preconditioning as its central feature. The paper identifies further algorithmic directions and potential application areas.

6. Conclusion and Future Work

  • The authors identify asymmetric preconditioning as the feature behind AFBA’s potential for extensions and new algorithmic schemes.They propose exploring block-triangular choices for Gauss-Seidel-type updates, replacing the linear operator with a Lipschitz operator, and randomized variants for block-structured problems.Source: §6 · p. 28

7. Appendix

The appendix collects proofs omitted from the main text, including convergence arguments and derivations for special cases.

7. Appendix

  • For the parameterized case, the proof establishes cocoercivity of C and selects step sizes to meet the convergence condition.The step-size construction uses a positive lower bound and a further bound dependent on ρ_n and the cocoercivity parameter.Source: §7 · pp. 30–31
  • Algorithm 2’s convergence proof applies Theorem 3.1 after choosing λ_n so that α_n = ρ_n.The proof also uses the change of variables s_n = x_n − γy_n and Moreau’s identity to obtain the algorithm.Source: §7 · p. 31
  • The proof establishes strong positivity of the preconditioning operators across parameter ranges, supporting the convergence analysis.For θ in [0, 2), the argument selects a positive constant below specified bounds; for θ ≥ 2, it uses a different bound.Source: §7 · p. 32
  • Algorithm 4’s proof applies Theorem 3.1 with α_n = 1 after establishing sufficient bounds on λ_n.Strong positivity of P, S, and D is used, with the step sizes bounded above and below to satisfy the convergence condition.Source: §7 · p. 33
Loading 1602.08729v3…