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

Technical Summary: Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimization

Problem Formulation
The paper addresses the optimization of nonconvex, linearly constrained problems where the objective functions may lack globally Lipschitz continuous gradients. The primary focus is on the two-block formulation:
$$\min_{x \in \mathbb{R}^n, y \in \mathbb{R}^m} f_1(x) + f_2(y) \quad \text{s.t.} \quad Ax + By = b,$$
where $f_1$ and $f_2$ can be nonconvex. This setting is motivated by polynomial objectives arising in matrix and tensor models, where standard Lipschitz gradient assumptions often fail because the Hessian norm $\|\nabla^2 f\|$ may be unbounded. The authors also extend the analysis to a multi-block global consensus formulation relevant to distributed optimization.

Methodology and Framework
The authors analyze Bregman ADMM, a variant of the Alternating Direction Method of Multipliers that replaces Euclidean proximal terms with Bregman divergences. This allows the algorithm to operate under relative smoothness (and relative bi-smoothness for multi-block cases) rather than global Lipschitz smoothness.

• Relative Smoothness: The analysis relies on a two-sided Hessian comparison condition: $L_f \nabla^2 h(x) \pm \nabla^2 f(x) \succeq 0$, where $h$ is a strongly convex kernel function. This framework accommodates polynomial objectives by selecting appropriate polynomial kernels.
• Algorithmic Structure: The method alternates between Bregman-proximal primal updates and a dual ascent step. The authors treat one iteration of the algorithm as a smooth primal-dual fixed-point map $g$ defined on an invariant open state-space domain.
• Dynamical Systems Approach: The core theoretical mechanism follows the dynamical systems viewpoint. The authors aim to show that strict saddle points (KKT points that are not second-order stationary) correspond to unstable fixed points of the map $g$. By invoking the Stable Manifold Theorem, they argue that the set of initializations converging to such unstable points has Lebesgue measure zero.

Key Contributions

1. Strict-Saddle Avoidance without Lipschitz Gradients: The paper establishes that for Bregman ADMM, under relative (bi-)smoothness, strict saddle KKT points are unstable fixed points. Consequently, with random initialization, the iterates converge to a strict saddle with probability zero. This result holds without requiring a global Lipschitz gradient constant, addressing a key limitation of previous analyses (e.g., [5]) that relied on Euclidean geometry.
2. Technical Novelty in Spectral Arguments: The proof of instability requires non-trivial adaptations to the Bregman setting:
   • Two-Block Case: The authors develop a determinant reduction involving a Bregman-specific symmetrization and scaling step. Unlike the Euclidean case, the reduced spectral problem is not naturally symmetric; the authors introduce a diagonal rescaling to symmetrize the matrix and identify a strict saddle direction.
   • Multi-Block Consensus Case: For the star-consensus formulation, the proof utilizes a null space cancellation argument. The specific structure of the star graph (hub and peripheral coupling) allows the consensus penalty to vanish along the equal-$x$ test direction, isolating the negative curvature of the objective.
3. Second-Order Stationarity of Limit Points: By combining the strict-saddle avoidance result with existing first-order convergence guarantees (which ensure convergence to a KKT point under conditions like boundedness and the Kurdyka-Łojasiewicz inequality), the authors conclude that limiting KKT points are almost surely second-order stationary.
4. Extension to Distributed Optimization: The framework is extended to a multi-block consensus problem, proving that the same strict-saddle avoidance guarantees hold for distributed settings where agents communicate via a star topology.

Results and Numerical Experiments
The theoretical findings are validated through numerical experiments on two polynomial models that fall outside the globally Lipschitz-smooth regime:

• Distributed Matrix Factorization: The algorithm successfully solves a distributed low-rank matrix recovery problem. The experiments demonstrate rapid convergence of the objective and consensus residuals to machine precision, confirming the algorithm's ability to handle non-Lipschitz polynomial objectives in a distributed setting.
• Symmetric Tensor Factorization: The authors apply the Bregman proximal splitting idea to symmetric tensor factorization. While the theoretical guarantee strictly applies to separable objectives, this experiment illustrates the practical utility of the Bregman regularization in stabilizing subproblems for coupled polynomial objectives. The algorithm drives the factors toward agreement while minimizing the reconstruction error.

Significance and Claims
The paper claims that the strict-saddle avoidance mechanism, previously established for Euclidean proximal methods under Lipschitz assumptions, survives the transition to Bregman ADMM under relative smoothness. The significance lies in extending second-order convergence guarantees to a broader class of nonconvex problems (specifically those with polynomial objectives) where standard smoothness constants do not exist globally.

The authors emphasize that the extension is not a trivial substitution of proximal terms; it requires re-deriving the instability proof within the Bregman geometry, specifically handling the metric blocks introduced by the kernel Hessians. The work bridges the gap between first-order convergence results for nonconvex Bregman methods and the desirable property of avoiding strict saddles, thereby ensuring that limiting points are likely to be local (and often global) minimizers in structured problems like matrix and tensor factorization.