Solving separable convex optimization problems: Faster prediction-correction framework

Tao Zhang, Yong Xia, Shiru LiarXiv 2023 · DOI · arXiv

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:

  1. 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.
  2. 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.

Comparison of convergence rates for various algorithms solving separable convex optimization problems. The proposed framework achieves superior non-ergodic and pointwise rates.

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.

Comparison of step-size conditions and convergence rates for min-max problems. The proposed framework allows for larger step sizes while maintaining faster convergence rates.

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

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)$ ($t$ represents iteration times) in both ergodic (the average of iteration) 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 the faster prediction-correction framework, we give three faster algorithms which enjoy $O(1/t)$ in the non-ergodic sense of primal-dual gap and $O(1/t^2)$ in the pointwise sense. The first algorithm updates dual variable twice when solving two-block separable convex optimization with equality linear constraints. The second algorithm solves multi-block separable convex optimization problems with linear equality constraints in Gauss-Seidel way. The third algorithm solves minmax problems with larger step sizes.
BibTeX
@misc{zhang2023solving,
  author = {Tao Zhang and Yong Xia and Shiru Li},
  title = {{Solving separable convex optimization problems: Faster prediction-correction framework}},
  year = {2023},
  eprint = {2304.02465},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2304.02465},
}
Figure