Iteration-Complexity of a Generalized Forward Backward Splitting Algorithm

Jingwei Liang, Jalal Fadili, Gabriel PeyréarXiv 2013 · DOI · arXiv

In the world of signal processing, image reconstruction, and machine learning, we often find ourselves trying to solve "structured" optimization problems. These are problems where the goal is to minimize a sum of different functions, each representing a different constraint or prior (like smoothness or sparsity). One of the most powerful tools for this is the Generalized Forward-Backward (GFB) splitting algorithm.

While researchers knew GFB worked, a critical question remained: How fast does it work? This paper by Liang, Fadili, and Peyré provides the answer, establishing the "iteration-complexity" for GFB, even when the calculations aren't performed perfectly.

TL;DR

This paper provides the first formal iteration-complexity bounds for the inexact Generalized Forward-Backward (GFB) algorithm. It proves that the algorithm reaches an $\epsilon$-approximate solution in $O(1/\epsilon)$ iterations pointwise and $O(1/\sqrt{\epsilon})$ iterations in an ergodic (averaged) sense, even in the presence of summable computational errors.

What Problem Does This Paper Address?

Many optimization problems take the form: $$\min_{x \in \mathcal{H}} f(x) + \sum_{i=1}^n h_i(x)$$ Here, $f$ is a "smooth" function (it has a Lipschitz continuous gradient), and the $h_i$ terms are "simple" but potentially non-smooth (like the $L_1$ norm used for sparsity).

The GFB algorithm is designed to solve this by "splitting" the problem: it takes a gradient step on the smooth part ($f$) and then applies "proximal operators" (a kind of generalized projection) to each of the non-smooth parts ($h_i$).

The Gap: Prior to this work, the convergence rates for GFB—especially when the gradient or proximal operators are computed with some error (the "inexact" case)—were not well-established. Engineers and scientists needed to know how many iterations were required to reach a specific level of precision.

Methods

The authors analyze GFB by viewing it through the lens of fixed-point theory.

  1. Averaged Operators: They show that the GFB iteration can be written as a composition of "$\alpha$-averaged operators." These are mathematical mappings that are "well-behaved" enough to guarantee they eventually settle into a fixed point (the solution).
  2. Inexactness Modeling: They explicitly include error terms ($\varepsilon^k$) in the algorithm's steps. This accounts for the reality that numerical solvers often approximate gradients and proximal mappings.
  3. Complexity Analysis: They derive two types of bounds:
  4. Pointwise: The performance of the algorithm at the current iteration $k$.
  5. Ergodic: The performance of the average of all iterations up to $k$.
  6. Termination Criterion: They propose a verifiable termination criterion based on the "fixed-point residual." This is a practical way for a user to know when the algorithm has actually converged to a desired tolerance.

Datasets

The authors validate their theoretical findings using a video processing task known as Principal Component Pursuit (PCP).

  • The Data: A video sequence consisting of $436 \times 384$ pixel frames (288 frames total).
  • The Task: Decomposing the video into a "low-rank" background (the static scene) and a "sparse" foreground (moving objects).
  • The Setup: They reformulated the PCP problem into the $f + \sum h_i$ structure to show that GFB can handle complex constraints like non-negativity and nuclear norm minimization simultaneously.

Key Insights and Ideas

  • The "Aha" Moment on Errors: The paper proves that as long as the computational errors are "summable" (meaning they decrease fast enough over time), they do not degrade the overall convergence rate of the algorithm.
  • Fixed-Point Residual as a Proxy: In complex non-smooth optimization, you can't always check the "gradient" to see if you're done. The authors show that the norm of the fixed-point residual is a reliable and mathematically sound substitute for the gradient norm.
  • Ergodic Speedup: A major insight is that while the current iteration might oscillate slightly, the average of all iterations converges significantly faster ($O(1/\sqrt{\epsilon})$ vs $O(1/\epsilon)$), suggesting that "averaging" is a powerful strategy for users of GFB.

Key Results

  • Pointwise Rate: To reach a residual error of $\epsilon$, the algorithm requires $O(1/\epsilon)$ iterations.
  • Ergodic Rate: To reach the same error level using the average of iterates, it only requires $O(1/\sqrt{\epsilon})$ iterations.
  • Empirical Validation: In the video decomposition experiment (Fig. 1), the "practical" convergence curves perfectly match the "theoretical" slopes predicted by the authors' theorems. This confirms that the bounds are "tight" and reflect real-world performance.

Limitations and Future Work

  • Summable Errors: The proof relies on the assumption that errors are summable. If a system has a constant "noise floor" in its calculations, the algorithm may reach a plateau rather than converging indefinitely.
  • Parameter Sensitivity: The rates depend on constants like the Lipschitz coefficient ($\beta$). In many real-world problems, estimating $\beta$ accurately can be difficult, which might affect the practical choice of step sizes.
  • Acceleration: This paper focuses on the standard GFB. A natural next step (which has been explored in subsequent literature) is applying "Nesterov-style" acceleration to GFB to see if the pointwise rate can be improved further.

Summary updated

Abstract

In this paper, we analyze the iteration-complexity of Generalized Forward--Backward (GFB) splitting algorithm, as proposed in \cite{gfb2011}, for minimizing a large class of composite objectives $f + \sum_{i=1}^n h_i$ on a Hilbert space, where $f$ has a Lipschitz-continuous gradient and the $h_i$'s are simple (\ie their proximity operators are easy to compute). We derive iteration-complexity bounds (pointwise and ergodic) for the inexact version of GFB to obtain an approximate solution based on an easily verifiable termination criterion. Along the way, we prove complexity bounds for relaxed and inexact fixed point iterations built from composition of nonexpansive averaged operators. These results apply more generally to GFB when used to find a zero of a sum of $n > 0$ maximal monotone operators and a co-coercive operator on a Hilbert space. The theoretical findings are exemplified with experiments on video processing.
BibTeX
@misc{liang2013iteration,
  author = {Jingwei Liang and Jalal Fadili and Gabriel Peyré},
  title = {{Iteration-Complexity of a Generalized Forward Backward Splitting Algorithm}},
  year = {2013},
  eprint = {1310.6636},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1310.6636},
}
Figure