ADMM Fails to Achieve an $O(K^{-1})$ Ergodic KKT Residual Bound

Abstract

The Karush--Kuhn--Tucker (KKT) residual is a fundamental measure of first-order optimality and, under an error bound condition, is comparable to the distance to the KKT solution set up to constant factors. Despite the $O(K^{-1})$ ergodic rates known for objective error and feasibility violations, we show that the KKT residual of classical ADMM cannot, in general, satisfy a uniform $O(K^{-1})$ bound. Specifically, we construct a fixed-dimensional, horizon-dependent family of two-block convex optimization problems for which the KKT residual is $Ω(K^{-1/2})$ at both the last iterate and the equal-weight ergodic average at the prescribed horizon $K$. Consequently, a uniform $O(K^{-1})$ KKT residual bound is impossible for either output.

Disclosure

“stance up to constant factors. The same example also demonstrates that Halpern acceleration can improve both the KKT residual and the solution-set distance from Θ(K −1/2 ) for the equal-weight ergodic average to Θ(K −1 ). Acknowledgments GPT-5.6 was used as an auxiliary tool in developing the lower-bound construction. All mathe- matical arguments were independently verified by the authors. The work of Defeng Sun was sup- ported by the Research Center for Intelligent Operations Res”

PDF page 15

Classification

Substantial mathematical content or result generation

Multiplier

10

Verified

2026-08-23T05:19:36.772755Z

Structural counts