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

arXiv: https://arxiv.org/abs/2606.28307 · HTML: https://mlsanity.com/paper/2606.28307/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 46 references that are in the map.
- First posted on arXiv 26 Jun 2026.

## Builds on (most cited first, 18 of 18)

- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Global Convergence of ADMM in Nonconvex Nonsmooth Optimization](https://mlsanity.com/paper/1511.06324/) (2015)
- [Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems](https://mlsanity.com/paper/1410.1390/) (2014)
- [On Nonconvex Decentralized Gradient Descent](https://mlsanity.com/paper/1608.05766/) (2016)
- [First Order Methods beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problems](https://mlsanity.com/paper/1706.06461/) (2017)
- [First-order methods almost always avoid saddle points: the case of vanishing step-sizes](https://mlsanity.com/paper/1906.07772/) (2019)
- [Bregman Alternating Direction Method of Multipliers](https://mlsanity.com/paper/1306.3203/) (2013)
- [Learning Deep Models: Critical Points and Local Openness](https://mlsanity.com/paper/1803.02968/) (2018)
- [Convergence of multi-block Bregman ADMM for nonconvex composite problems](https://mlsanity.com/paper/1505.03063/) (2015)
- [Convergence for nonconvex ADMM, with applications to CT imaging](https://mlsanity.com/paper/2006.07278/) (2020)
- [Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems](https://mlsanity.com/paper/1410.8625/) (2014)
- [A Decentralized Primal-Dual Framework for Non-convex Smooth Consensus Optimization](https://mlsanity.com/paper/2107.11321/) (2021)
- [Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems](https://mlsanity.com/paper/1702.01850/) (2017)
- [Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems](https://mlsanity.com/paper/1904.09712/) (2019)
- [Bregman Proximal Linearized ADMM for Minimizing Separable Sums Coupled by a Difference of Functions](https://mlsanity.com/paper/2401.02635/) (2024)
- [Local and Global Convergence of General Burer-Monteiro Tensor Optimizations](https://mlsanity.com/paper/2201.02298/) (2022)

## Abstract (arXiv)

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. We extend the analysis to a multi-block star consensus formulation for distributed optimization. The technical novelty lies in a determinant reduction with a Bregman-specific symmetrization and scaling step in the two block spectral argument, together with a null space cancellation exploiting the star graph structure in the consensus case. Numerical experiments on distributed matrix factorization illustrate the theory, and a symmetric tensor factorization example demonstrates the broader Bregman proximal splitting idea beyond the separable consensus setting.