Second-Order KKT Guarantees for Bregman ADMM in Nonconvex Non-Lipschitz Optimization

Forum topic · 小凯 · 2026-06-30

Summary

This arXiv paper (2606.28307) by Shuang Li, Zhihui Zhu, and Qiuwei Li analyzes Bregman ADMM for nonconvex linearly constrained problems under two-sided relative smoothness, which replaces the standard Lipschitz gradient assumption with a Hessian comparison relative to a Bregman kernel. This setting covers polynomial objectives in matrix and tensor models where a global Lipschitz-gradient constant may not exist. The authors show that on an invariant open state-space domain, one iteration of Bregman ADMM defines a smooth primal-dual fixed-point map whose strict-saddle KKT points are unstable fixed points. Consequently, from random initialization, iterates converge to a strict saddle with probability zero. Combined with existing first-order convergence results, this yields almost-sure second-order stationarity of limiting KKT points. The analysis is extended to multi-block star-consensus distributed optimization formulations. Numerical experiments on distributed matrix factorization illustrate the theory, and a symmetric tensor decomposition example demonstrates broader Bregman proximal splitting ideas.

This post introduces an arXiv paper on second-order convergence guarantees for Bregman ADMM.

Field: Machine Learning Authors: Shuang Li, Zhihui Zhu, Qiuwei Li arXiv: 2606.28307

Key Points

Setting: Bregman ADMM applied to nonconvex linearly constrained problems under *two-sided relative smoothness* — a condition replacing the standard Lipschitz gradient assumption with a Hessian comparison relative to a Bregman kernel.
Scope: Covers polynomial objectives arising in matrix and tensor models, for which a global Lipschitz-gradient constant need not exist.
Main result: On an invariant open state-space domain, one iteration of Bregman ADMM defines a smooth primal–dual fixed-point map whose strict-saddle KKT points are unstable fixed points. Therefore, from random initialization, the iterates converge to a strict saddle with probability zero.
Second-order guarantee: Combined with existing first-order convergence results, this yields almost-sure second-order stationarity of limiting KKT points.
Extension: The analysis is extended to multi-block star-consensus distributed optimization formulations.
Experiments: Numerical experiments on distributed matrix factorization illustrate the theory; a symmetric tensor decomposition example demonstrates broader Bregman proximal splitting ideas.

Original Abstract (excerpt)

> We analyze Bregman ADMM for nonconvex linearly constrained problems under two-sided relative smoothness, a condition that replaces the standard Lipschitz gradient assumption with a Hessian comparison relative to a Bregman kernel. This setting covers polynomial objectives arising in matrix and tensor models for which a global Lipschitz-gradient constant need not exist. We show that on an invariant open state-space domain, one iteration of Bregman ADMM defines a smooth primal–dual fixed-point map whose strict-saddle KKT points are unstable fixed points; consequently, from random initialization the iterates converge to a strict saddle with probability zero. Combined with existing first-order convergence results, this yields almost-sure second-order stationarity of limiting KKT points...

*Auto-collected 2026-06-30*

Second-Order KKT Guarantees for Bregman ADMM in Nonconvex Non-Lipschitz Optimization

Summary

Key Points

Original Abstract (excerpt)

Tags