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

Kaihuang Chen; Defeng Sun; Yancheng Yuan; Guojun Zhang; Xinyuan Zhao

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

Kaihuang Chen, Defeng Sun, Yancheng Yuan, Guojun Zhang, Xinyuan Zhao

arXivarxiv/2608.16610Aug 17, 2026math.OCscore 0

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…

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2608.16610
curl -X POST /api/v1/records/arxiv/2608.16610/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.16610/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'