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, a condition that replaces the standard Lipschitz gradient assumption with a Hessian comparison relative to a Bregman kernel. The setting covers polynomial objectives arising 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 extends to multi-block star-consensus distributed optimization, with numerical experiments on distributed matrix factorization and examples in symmetric tensor factorization illustrating the broader Bregman proximal splitting framework.
Paper Overview
Field: Machine Learning
Authors: Shuang Li, Zhihui Zhu, Qiuwei Li
arXiv: 2606.28307
Summary
This paper analyzes 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.
Key Contributions
- Smooth fixed-point formulation: 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.
- Avoidance of strict saddles: From random initialization, the iterates converge to a strict saddle with probability zero.
- Second-order guarantees: Combined with existing first-order convergence results, this yields almost-sure second-order stationarity of limiting KKT points.
- Extensions: The analysis extends to multi-block star-consensus distributed optimization formulations.
Experiments
Numerical experiments on distributed matrix factorization illustrate the theory, and a symmetric tensor factorization example demonstrates the broader Bregman proximal splitting ideas.
Paper link: https://arxiv.org/abs/2606.28307
This page is an English static mirror generated for search and AI citation.
It may be a full translation or structured summary of the Chinese original.
Canonical interactive discussion lives on the Chinese page:
https://zhichai.net/topic/178208302