PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence Rates with Inexact Non-expansive Operators

Jingwei Liang, Jalal Fadili, Gabriel Peyré

arXiv:1404.4837v3math.OC

TL;DR

The paper studies convergence rates for inexact Krasnosel’skii–Mann iterations with non-expansive operators. It establishes global complexity bounds and local linear convergence under metric sub-regularity, and illustrates the analysis on splitting methods and examples.

  • Problem

    The paper addresses convergence-rate analysis for inexact Krasnosel’skii–Mann iterations built from non-expansive operators.

    Source: §1.1 · p. 2

  • Method

    The paper analyzes inexact Krasnosel’skii–Mann iterations and uses metric sub-regularity of the fixed-point operator to obtain a local rate.

    Source: §1.1 · p. 2, §4 · p. 9

  • Results

    Under metric sub-regularity, the distance of the iterates to the fixed-point set converges locally linearly.

    Source: §1.2 · p. 2, §4 · p. 9

  • Takeaways & Limitations

    The analysis is applied to splitting algorithms and examples that exhibit both global sub-linear and local linear convergence profiles.

    Source: §7 · p. 19

    The illustrated gradient-descent rate does not target the usual optimal linear rate, which can be obtained by locally modifying γ after the iterates enter the appropriate neighborhood.

    Source: Examples · p. 11

Abstract

from arXiv · show

In this paper, we present a convergence rate analysis for the inexact Krasnosel'skii-Mann iteration built from nonexpansive operators. Our results include two main parts: we first establish global pointwise and ergodic iteration-complexity bounds, and then, under a metric subregularity assumption, we establish local linear convergence for the distance of the iterates to the set of fixed points. The obtained iteration-complexity result can be applied to analyze the convergence rate of various monotone operator splitting methods in the literature, including the Forward-Backward, the Generalized Forward-Backward, Douglas-Rachford, alternating direction method of multipliers (ADMM) and Primal-Dual splitting methods. For these methods, we also develop easily verifiable termination criteria for finding an approximate solution, which can be seen as a generalization of the termination criterion for the classical gradient descent method. We finally develop a parallel analysis for the non-stationary Krasnosel'skii-Mann iteration. The usefulness of our results is illustrated by applying them to a large class of structured monotone inclusion and convex optimization problems. Experiments on some large scale inverse problems in signal and image processing problems are shown.

1 Introduction

Structured monotone inclusion problems motivate splitting methods, many of which can be expressed as inexact Krasnosel’skii–Mann fixed-point iterations. The paper develops global complexity bounds, local linear convergence under metric sub-regularity, applications to splitting methods, and an extension to non-stationary iterations.

1.1 Monotone inclusion and operator splitting methods

  • The inexact Krasnosel’skii–Mann iteration models splitting methods through a non-expansive fixed-point operator, with errors representing approximate operator evaluations.Many splitting algorithms evaluate individual operators, resolvents, and linear operators separately rather than resolvents of sums or compositions.Source: §1.1 · pp. 1–2

1.2 Contributions

  • With a nonempty fixed-point set, the paper establishes global pointwise and ergodic complexity bounds for asymptotic regularity and local linear convergence under metric sub-regularity.When the fixed point is unique, the sequence itself converges linearly.Source: §1.2 · p. 2

1.3.1 Global iteration-complexity bounds

  • The framework covers inexact iterations without requiring boundedness of the constraint set, unlike the exact bounded-set setting discussed for [3,21].The paper also establishes pointwise and ergodic rates and local linear convergence under metric sub-regularity.Source: §1.3.1 · p. 2

1.3.2 Local linear convergence

  • Compared with, the local linear result allows errors and iteration-dependent relaxation parameters, while assuming metric sub-regularity of Id − T.The paper notes that this assumption coincides with bounded linear regularity of T in.Source: §1.3.2 · p. 3

1.4 Paper organization

  • The paper introduces notation and monotone operator preliminaries, proves global and local rate results, applies them to splitting methods, and then treats the non-stationary case.Source: §1.4 · p. 4

2 Preliminaries

The preliminaries establish the operator and space notation used to state the paper’s convergence results. They cover non-expansive and averaged operators, monotone operators, and product-space constructions.

2 Preliminaries

  • The paper fixes notation for a real Hilbert space, convex functions and proximity operators, and basic operator concepts such as domains, graphs, resolvents, and zeros.Source: §2 · p. 4

2.1 Non-expansive operators and quasi-Fejér monotone sequences

  • Averaged operators include firmly non-expansive operators, and the preliminaries collect properties that support relaxation, convex combination, and composition of such maps.The stated lemmas characterize firmly non-expansive maps and describe closure properties for finite families of averaged operators.Source: §2.1 · pp. 4–5

2.2 Monotone operators

  • Monotone operators are introduced through their graph, with maximal monotonicity meaning that the graph has no proper monotone extension.Source: §2.2 · p. 5

2.3 Product Space

  • The product-space construction uses a weighted Hilbert space and a diagonal subspace, then defines componentwise operators and their resolvents and reflections.The canonical isometry maps a point to the vector with that point in every component.Source: §2.3 · p. 5

3 Global iteration-complexity bounds

The inexact Krasnosel’skiĭ–Mann iteration relaxes a non-expansive fixed-point update and adds an approximation error. The section establishes global pointwise and ergodic complexity bounds, including an O(1/ϵ) pointwise criterion and a sharper exact-case residual property.

3 Global iteration-complexity bounds

  • Under the theorem’s conditions, the inexact iteration has a pointwise complexity bound, with an extension to α-averaged operators allowing iteration-dependent λk.The supplied theorem passage states the bound but does not expose its formula; the averaged-operator extension permits λk in ]0, 1/α].Source: §3 · p. 7, Remark 2 · pp. 7–8

Remark 2

  • O(1/ϵ) iterations suffice for the pointwise criterion ||T′zk||^2 ≤ ϵ, and for gradient descent the bound is reported as best-known.The criterion measures the fixed-point residual; for gradient descent, T′ is the gradient.Source: Remark 2 · p. 7
  • In the exact case, the residual sequence ||ek|| is non-increasing, a monotonicity property noted as sharper than the cited result [21].The cited comparison is specifically to [21, Proposition 11].Source: Remark 2 · p. 7
  • Theorem 2 establishes an ergodic complexity bound when the weighted errors satisfy ∑k λk||εk|| < +∞.The result also applies to α-averaged operators with λk in ]0, 1/α].Source: Remark 2 · p. 8, Remark 3 · p. 8

Remark 3

  • The section also derives convergence bounds for the step differences zk − zk+1 from the pointwise and ergodic results.The pointwise bound is stated for stepsizes bounded away from zero and one; the ergodic bound follows by replacing Λk with k + 1.Source: Remark 3 · p. 8

4 Local linear convergence rate

The section analyzes when the global sub-linear behavior of fixed-point methods gives way to local linear convergence. Under metric sub-regularity of T′ = Id − T, it establishes local linear convergence of the distance to the fixed-point set, with illustrative cases for Douglas–Rachford splitting and gradient descent.

4 Local linear convergence rate

  • Metric sub-regularity of T′ relates distance from fixT to the residual ||z − Tz||, motivating its use to obtain a local rate beyond the global O(1/k) distance rate.The theorem’s local result is for starting points in a neighborhood of a fixed point.Source: §4 · pp. 8–9
  • Metric sub-regularity of T′ at a fixed point yields local linear convergence of the distance dk to fixT for initial points in a specified neighborhood, under the theorem’s error condition.When the fixed point is unique, the theorem applies to the iterates’ distance from that point; the α-averaged case follows by adjusting λk and κ.Source: §4 · p. 9, Remark 4 · p. 10

Remark 5

  • The metric sub-regularity modulus can be difficult to compute generally, even when T′ is differentiable.The section notes differentiability with nonsingular derivatives and uniformly bounded inverse operator norms as a sufficient condition for sub-regularity.Source: Remark 5 · p. 10

Examples

  • For Douglas–Rachford splitting on two subspaces in R² meeting at angle θ, the rate is ζk = 1 − (2 − λk)λk sin²θ, with the optimal stated rate cos²θ at λk = 1.The sub-regularity modulus is 1/sin θ; the cited rate is described as optimal in.Source: Examples · p. 11
  • For t = γδM ∈ (0, 2), where cnd = δM/δm is the condition number of the Hessian of f along Ω, the smallest ζ3 is attained at t = 1, i.e., γ = 1/δM.Observed and theoretical convergence profiles exhibit two regimes: global sub-linear, then local linear.Source: Examples · p. 11
  • The example does not pursue the usual optimal strongly-convex gradient-descent rate obtainable by changing γ after entering the appropriate neighborhood.The passage describes local step-size modification as a possibility, not part of the example’s aim.Source: Examples · p. 11

5 Applications

The applications cast several operator-splitting schemes as Krasnosel’skiĭ–Mann iterations, allowing the global complexity results to apply. The section also derives stopping criteria for generalized forward–backward, Douglas–Rachford/ADMM, and primal–dual methods.

5.1 Generalized Forward–Backward splitting

  • Generalized Forward–Backward (GFB) fits the inexact Krasnosel’skiĭ–Mann framework, so its iterates inherit the pointwise and ergodic complexity bounds.The fixed-point formulation also yields convergence results for the associated structured monotone inclusion.Source: §5.1 · p. 12, §5 · p. 12

Remark 6

  • GFB provides an ϵ-accurate solution in at most O(1/ϵ) iterations under its criterion, generalizing gradient descent’s best-known complexity bounds and recovering FBS’s sub-differential criterion when n = 1.Source: Remark 6 · p. 13

5.2 Douglas–Rachford splitting and ADMM

  • Douglas–Rachford splitting with summable error sequences fits the inexact iteration and therefore obeys the section’s global complexity bounds.ADMM’s pointwise complexity is stated as O(1/k), using its relation to Douglas–Rachford splitting on the Fenchel dual.Source: §5.2 · p. 14, Remark 7 · p. 14
  • The Douglas–Rachford residual construction gives gk+1 ∈ A1uk+1 + A2vk+1 and under the stated stepsize and summable-error conditions supports a stopping criterion.The criterion concerns the corresponding monotone inclusion.Source: §5.2 · p. 14

5.3 Primal–Dual splitting

  • The primal–dual splitting iteration has a forward–backward structure and, with summable errors, inherits the section’s iteration-complexity bounds.Its fixed points correspond to zeros of C + D + E.Source: §5.3 · p. 15
  • Proposition 4 supplies a stopping criterion for the primal–dual monotone inclusion, while the section leaves an ergodic bound undeveloped.The authors omit the ergodic bound for brevity.Source: §5.3 · p. 15

6 Non-stationary Krasnosel’ski˘ı-Mann iteration

The non-stationary Krasnosel’ski˘ı–Mann iteration perturbs a fixed-operator iteration through operator drift and approximation error. Under summability and regularity conditions it converges, admits complexity bounds, and supports an application to non-stationary GFB.

6.1 General convergence analysis

  • Summable approximation and operator-drift errors yield strong convergence of the error sequence and weak convergence of iterates to a fixed point of TΓ.The analysis treats non-stationarity as a summable perturbation of the stationary iteration.Source: §6.1 · p. 16
  • With stronger summability of the non-stationarity error, the iteration has pointwise and ergodic complexity bounds; when inf_k λk > 0, the ergodic rate is O(1/k).The convergence analysis requires assumptions on the relaxed operators, approximation errors, and operator drift.Source: §6.1 · p. 17
  • Under metric sub-regularity of Id − TΓ, local convergence of the distance to fixTΓ depends on approximation and operator-drift errors; sublinear drift can dominate.If both errors decay linearly, the distance to the fixed-point set does as well.Source: §6.1 · p. 17

6.2 Application to non-stationary GFB

  • For GFB, the parameter γ is allowed to vary along the iteration, and the analysis concludes that condition (A.5) is fulfilled.For γk ∈ ]0, 2β[, Tγk is αk-averaged.Source: §6.2 · pp. 17, 19
  • For non-stationary GFB, weak convergence to a fixed point of Tγ holds under the stated assumptions, and stronger summability of parameter changes gives the pointwise complexity bound.The parameter sequence satisfies γk ∈ [γ, γ] ⊂ ]0, 2β[ and a summability condition on λk|γk − γ|.Source: §6.2 · p. 18

Remark 9

  • For non-stationary DRS and FDRS, Theorem 5 applies when their fixed-point operators depend on γk, but the parameter summability assumption is generally hard to remove.Even with εk = 0, non-stationary GFB retains a parameter-drift error, so its local rate depends on how quickly |γk − γ| tends to zero.Source: Remark 9 · p. 19

7 Conclusion

The paper establishes global complexity bounds and local linear convergence under metric sub-regularity, then extends the analysis to non-stationary iterations. It applies the results to splitting methods and illustrates them on examples, while noting limits on rate sharpness and the difficulty of computing the sub-regularity modulus.

7 Conclusion

  • The paper provides global iteration-complexity bounds for inexact Krasnosel’ski˘ı–Mann iterations and a unified local linear convergence analysis under metric sub-regularity.The local rate depends on the fixed-point operator’s sub-regularity modulus, which is not straightforward to compute in general.Source: §7 · p. 19
  • The results extend to non-stationary iterations and are applied to monotone operator splitting algorithms, with examples showing global sub-linear and local linear convergence profiles.Source: §7 · p. 19
  • The rate estimates are not necessarily sharp; exploiting additional problem structure may yield sharper rates.The authors identify sharper rate analysis as future work.Source: §7 · p. 19

Supplementary Material

The supplementary material adds a GFB iteration-complexity bound and a detailed discussion of Vũ’s Primal–Dual splitting method. It also applies the results to structured monotone inclusions and convex optimization problems, with large-scale signal and image-processing inverse-problem experiments.

Supplementary Material

A Introduction

  • The results are applied to structured monotone inclusions and convex optimization problems, with experiments on large-scale inverse problems in signal and image processing.Source: A Introduction · p. 22

B GFB method

The supplementary GFB analysis derives an iteration-complexity bound from the fixed-point iteration. It defines quantities linked to the monotone inclusion and bounds a residual expression under earlier conditions.

B GFB method

  • The supplement establishes an additional iteration-complexity bound for GFB.Source: B GFB method · p. 22
  • The proposition relates gk+1 to the resolvent-defined operator Aγ through gk+1 ∈ (1/γ)Aγpk+1.Source: B GFB method · p. 22
  • Under conditions from Corollary 1 and Theorem 2, the proposition gives a bound on a residual involving ḡk+1 and B_S p̄k+1.Source: B GFB method · p. 22

C V˜u’s Primal–Dual splitting method

The section expresses Vũ’s Primal–Dual splitting method through quantities for the fixed-point iteration and states results for its dual inclusion. It also translates the analysis between the K and F metrics.

C Vũ’s Primal–Dual splitting method

D Numerical experiments

The experiments apply GFB and Vũ’s Primal–Dual splitting method to three inverse problems. The reported TV deconvolution and matrix-completion behaviors are consistent with the paper’s convergence analysis.

D Numerical experiments

  • The experiments cover anisotropic TV deconvolution, non-negative matrix completion, and principal component pursuit, solved using GFB and Vũ’s Primal–Dual splitting method.The supplied subsections describe the first two problems in detail.Source: D Numerical experiments · p. 25

D.1 Anisotropic TV deconvolution

  • For TV deconvolution, both methods exhibit local linear convergence; the pointwise profile transitions from global sublinear to local linear, while ergodic convergence follows O(1/k).The local linear curve is fitted to observations because the regularity modulus needed for the theoretical rate is difficult to estimate.Source: §D.1 · pp. 25–26

D.2 Non-negative matrix completion

  • For non-negative matrix completion, observed global and local convergence behaviors are similar to those in the TV deconvolution experiment.The test uses a 400 × 300 matrix of rank 20 and a random projection mask.Source: §D.2 · p. 26

D.3 Principal component pursuit

The principal component pursuit experiments use low-rank and sparse components to decompose video, while the non-stationary GFB experiment compares its rates with the stationary iteration. The video decomposition recovers the background and identifies moving pedestrians and their shadows; some non-stationary settings eventually become sublinear.

D.3 Principal component pursuit

  • The PCP formulation models a low-rank background and sparse foreground with perturbation, adding non-negativity to the low-rank component for video decomposition.The motivation is that backgrounds are similar across frames while moving objects appear intermittently.Source: §D.3 · pp. 26–27
  • In the synthetic PCP example, Figure C compares the pointwise convergence of GFB and PDS and displays their criteria from Propositions 4 and C.3.The example uses a 400 × 300 matrix with rank 20 low-rank component and 25% sparsity.Source: §D.3 · p. 27, Figure C · p. 27
  • On a 400-frame video, GFB’s low-rank component recovers the background, while its sparse component identifies moving pedestrians and their shadows.The frames are stacked as columns of a 110592 × 400 matrix.Source: §D.3 · pp. 27–28

D.4 Non-stationary iteration

  • Non-stationary iterations are slower than stationary ones globally and locally; two tested parameter settings eventually become sublinear, with iteration behavior controlled by perturbation error.The authors state that the observed result supports their assumption about convergence of the non-stationary iteration.Source: §D.4 · p. 29
Loading 1404.4837v3…