提出Bregman ADMM在非凸非利普希茨问题中的二阶稳定保证,确保收敛到真正极值点。
Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimization
- 用Bregman核替代梯度利普希茨假设,处理矩阵/张量模型等无全局光滑性的场景
- 证明随机初始化下迭代收敛到严格鞍点的概率为零,极限点几乎必然满足二阶驻定
- 适用于分布式优化与非可分结构,理论创新源于特定对称化与零空间抵消技巧
本文研究在双侧相对光滑性条件下,非凸线性约束问题的Bregman ADMM算法。该条件以海森矩阵与Bregman核的相对比较取代标准的梯度利普希茨假设,涵盖矩阵与张量模型中常见的多项式目标函数,其全局梯度利普希茨常数可能不存在。我们证明,在一个不变的开状态空间域上,每一步Bregman ADMM定义了一个平滑的原-对偶不动点映射,其严格鞍点为不稳定不动点;因此,从随机初始化出发,迭代序列几乎必然不收敛到严格鞍点。结合已有的一阶收敛结果,可得极限KKT点几乎必然满足二阶平稳性。分析进一步扩展至多块星型共识形式的分布式优化。技术核心在于:针对两块情形的谱论证引入了与Bregman相关的对称化与缩放步骤,并利用星图结构实现零空间抵消。数值实验在分布式矩阵分解中验证了理论,对称张量分解示例展示了该方法在非可分共识设置外的推广能力。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。