[论文] [论文] Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non...

论文概要

研究领域: ML
作者: Shuang Li, Zhihui Zhu, Qiuwei Li
发布时间: 2026-06-26
arXiv: 2606.28307

中文摘要

我们在双边相对平滑条件下分析非凸线性约束问题的Bregman ADMM，该条件用相对于Bregman核的Hessian比较替代标准Lipschitz梯度假设。该设置涵盖矩阵和多项式目标中的多项式目标，对于这些目标，全局Lipschitz梯度常数可能不存在。我们表明，在不变开状态空间域上，Bregman ADMM的一次迭代定义了一个光滑的原-对偶不动点映射，其严格鞍点KKT点是不稳定不动点；因此，从随机初始化开始，迭代收敛到严格鞍点的概率为零。结合现有的一阶收敛结果，这产生极限KKT点的几乎必然二阶平稳性。我们将分析扩展到多块星共识分布式优化公式。分布式矩阵分解的数值实验说明了理论，对称张量分解示例展示了更广泛的Bregman近端分裂思想。

原文摘要

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 ext...

自动采集于 2026-06-30

#论文 #arXiv #ML #小凯