The Chen-Teboulle algorithm is the proximal point algorithm

Stephen BeckerarXiv 2019 · DOI · arXiv

Abstract

We revisit the Chen-Teboulle algorithm using recent insights and show that this allows a better bound on the step-size parameter.

Introduction

In optimization, a common objective is to minimize functions of the form $f(x) + g(Ax)$, where $A$ is a linear operator. This structure appears frequently in image processing, compressed sensing, and machine learning. While proximity operators for $f$ and $g$ might be computationally efficient, the coupling term $Ax$ complicates the joint problem.

The Chen-Teboulle (CT) algorithm, introduced in 1994, was a pioneering method to "split" these components. However, its original analysis led to conservative step-size limits. This paper unifies the CT algorithm with modern proximal splitting theory, simplifying its analysis and significantly improving its efficiency.

The Scaled Norm Viewpoint

The core contribution of this work is the realization that the CT algorithm is a specific instance of the classic Proximal Point Algorithm (PPA). The analysis begins by recasting the optimality conditions of the problem as a single operator $\mathcal{A}$ acting on a product space of primal and dual variables $(x, z, y)$. By viewing the CT algorithm through the lens of the PPA, we can leverage the well-understood properties of the latter.

The standard PPA finds a zero of an operator by repeatedly applying a resolvent operator: $x_{k+1} = (I + \tau^{-1}\mathcal{A})^{-1}x_k$. The key innovation here is the use of a "scaled norm" induced by a specific positive-definite matrix $V$, rather than the standard Euclidean norm. By strategically selecting $V$ such that its off-diagonal elements cancel out the coupling terms in $\mathcal{A}$, the resulting update equations decouple into the simple steps characteristic of the CT algorithm. This "cancellation trick" places CT in the same family as modern methods like Chambolle-Pock (2011) or He-Yuan (2012).

Improved Step-Size Bounds

The unification of CT with the PPA framework allows for a more robust analysis of convergence. The original 1994 analysis suggested a step-size limit of: $$\lambda_1 = \frac{1}{2 \max(\|A\|, 1)}$$ Our new analysis proves that convergence is guaranteed for a much larger range: $$\lambda_2 = \frac{1}{\sqrt{\|A\|^2 + 1}}$$

Comparison of the original stepsize bound $\lambda_1$ and the improved bound $\lambda_2$ as a function of $\|A\|$.

As illustrated in the comparison above, the new bound $\lambda_2$ is consistently larger than the original $\lambda_1$. The magnitude of this improvement is most evident when examining the ratio between the two bounds.

The ratio $\lambda_2/\lambda_1$ highlights that the new analysis provides a stepsize bound up to twice as large as the original.

The ratio $\lambda_2/\lambda_1$ shows that the new bound allows for step sizes that are nearly twice as large as the old bound, particularly when the operator norm $\|A\|$ is small. In practice, larger step sizes typically translate to faster convergence rates.

Limitations

While this work provides a tighter theoretical bound, it focuses specifically on the Chen-Teboulle algorithm. Further research is needed to explicitly derive similar bounds for more complex problem structures (e.g., $f(E_1x + b_1) + g(E_2x + b_2)$). Additionally, while the theoretical upper bound is improved, the optimal step-size selection within this range remains problem-dependent and would benefit from empirical validation on real-world datasets.

Conclusion

By identifying the Chen-Teboulle algorithm as a Proximal Point Algorithm in a scaled norm, we provide both a simpler convergence proof and a significantly improved step-size bound. This theoretical advancement bridges the gap between early splitting methods and modern proximal theory, offering a more efficient tool for solving coupled optimization problems.

Summary updated

Abstract

We revisit the Chen-Teboulle algorithm using recent insights and show that this allows a better bound on the step-size parameter.
BibTeX
@misc{becker2019chen,
  author = {Stephen Becker},
  title = {{The Chen-Teboulle algorithm is the proximal point algorithm}},
  year = {2019},
  eprint = {1908.03633},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1908.03633},
}
Figure