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}}$$
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$ 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