Abstract
He and Yuan's prediction-correction framework [SIAM J. Numer. Anal. 50: 700-709, 2012] is able to provide convergent algorithms for solving separable convex optimization problems at a rate of $O(1/t)$ in both ergodic and pointwise senses. This paper presents a faster prediction-correction framework at a rate of $O(1/t)$ in the non-ergodic sense (the last iteration) and $O(1/t^2)$ in the pointwise sense. Based on this faster framework, we provide three faster algorithms: a dual-update ADMM variant for two-block problems, a multi-block Gauss-Seidel variant, and a min-max solver with larger step sizes.
Introduction
Separable convex optimization problems are central to machine learning and image processing. These problems typically involve minimizing a sum of functions subject to linear constraints. The Alternating Direction Method of Multipliers (ADMM) is a standard approach, but its theoretical guarantees often focus on ergodic convergence—the average of all previous iterations. In practice, researchers typically prefer the last iterate (non-ergodic). For standard ADMM, the non-ergodic convergence rate is often $O(1/\sqrt{t})$. This paper addresses the challenge of creating a unified framework that guarantees faster $O(1/t)$ non-ergodic convergence and $O(1/t^2)$ pointwise convergence without requiring strong convexity.
Methodology: The Faster Prediction-Correction Framework
The authors build upon the Prediction-Correction framework originally popularized by He and Yuan. The "Faster" version introduced in this paper incorporates two key innovations:
- Accelerated Prediction (FPS): Instead of just using the current iterate, the new framework incorporates an extrapolation step using a sequence of weights $\{\tau^k\}$ defined by the recurrence $1/\tau^{k-1} = (1 - \tau^k)/\tau^k$, a hallmark of Nesterov-style acceleration.
- Pointwise Analysis: The framework provides a rigorous proof that the squared norm of the difference between iterates—the "pointwise" sense—decays at a rate of $O(1/t^2)$.
Key Results and Comparison
The paper's contributions are primarily theoretical, establishing a $O(1/t)$ non-ergodic rate for the primal-dual gap and a $O(1/t^2)$ pointwise rate.
As shown in the table above, the proposed framework ("This paper") provides a significant theoretical upgrade over traditional ADMM and other existing methods. Specifically, it achieves the same $O(1/t)$ rate for the last iterate that previous methods only achieved for the average iterate, while simultaneously improving the pointwise rate to $O(1/t^2)$.
Application to Min-Max Problems
For min-max (saddle point) problems, the new framework allows for a step-size condition of $rs > 0.75\rho(A^T A)$, which is more permissive than the standard $rs > \rho(A^T A)$ required by the original Chambolle-Pock algorithm.
This relaxation, combined with the accelerated rates, allows for larger steps and potentially faster progress in each iteration. The table highlights that this paper achieves both the improved non-ergodic rate and the superior pointwise rate under these more flexible conditions.
Conclusion
By integrating Nesterov-like extrapolation into the prediction-correction framework, this paper provides a unified theory for accelerating separable convex optimization. The resulting algorithms offer better theoretical guarantees for the last iterate, which is the most relevant metric for practical applications. Future work may involve empirical validation and exploring the framework's connection to second-order differential equations.
Summary updated