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

技术摘要：非凸及非 Lipschitz 连续优化中 Bregman ADMM 的二阶 KKT 保证

问题建模
本文研究了非凸且具有线性约束的优化问题，其中目标函数可能缺乏全局 Lipschitz 连续梯度。研究重点是两块（two-block）形式：
$$\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,$$
其中 $f_1$ 和 $f_2$ 可以是非凸的。这一设定受到矩阵和张量模型中多项式目标的启发，在这些模型中，标准的 Lipschitz 梯度假设往往失效，因为 Hessian 范数 $\|\nabla^2 f\|$ 可能无界。作者还将分析扩展到了与分布式优化相关的多块全局一致性（multi-block global consensus）形式。

方法论与框架
作者分析了 Bregman ADMM，这是交替方向乘子法的一种变体，它使用 Bregman 散度取代了欧几里得近端项（Euclidean proximal terms）。这使得算法能够在相对平滑性（以及多块情况下的相对双平滑性）而非全局 Lipschitz 平滑性下运行。

• 相对平滑性： 分析依赖于双侧 Hessian 比较条件：$L_f \nabla^2 h(x) \pm \nabla^2 f(x) \succeq 0$，其中 $h$ 是一个强凸核函数。该框架通过选择适当的多项式核函数来适应多项式目标。
• 算法结构： 该方法在 Bregman 近端原变量更新和对偶上升步之间进行交替。作者将算法的一次迭代视为定义在不变开状态空间域上的光滑原-对偶不动点映射 $g$。
• 动力系统视角： 核心理论机制遵循动力系统观点。作者旨在证明严格鞍点（即不是二阶平稳点的 KKT 点）对应于映射 $g$ 的不稳定不动点。通过调用稳定流形定理（Stable Manifold Theorem），他们论证了收敛到此类不稳定点的初始值集合其勒贝格测度为零。

核心贡献

1. 无需 Lipschitz 梯度的严格鞍点规避： 本文确立了在相对（双）平滑性条件下，对于 Bregman ADMM，严格鞍点 KKT 点是不稳定不动点。因此，在随机初始化下，迭代几乎以概率零收敛到严格鞍点。这一结果在不需要全局 Lipschitz 梯度常数的情况下成立，解决了以往分析（如 [5]）依赖于欧几里得几何的局限性。
2. 谱论方面的技术创新： 证明不稳定性需要在 Bregman 设定下进行非平凡的适配：
   • 两块情况： 作者开发了一种涉及 Bregman 特有的对称化与缩放步骤的行列式约简方法。与欧几里得情况不同，约简后的谱问题并非天然对称；作者引入了对角重缩放来使矩阵对称化，并识别出严格鞍点方向。
   • 多块一致性情况： 对于星型一致性（star-consensus）形式，证明利用了零空间抵消（null space cancellation）论证。星型图的特定结构（中心节点与外围耦合）使得一致性惩罚项在等 $x$ 测试方向上消失，从而隔离了目标函数的负曲率。
3. 极限点的二阶平稳性： 通过结合严格鞍点规避结果与现有的一阶收敛保证（这些保证在满足诸如有界性和 Kurdyka-Łojasiewicz 不等式等条件下确保收敛至 KKT 点），作者得出结论：极限 KKT 点几乎处处是二阶平稳的。
4. 向分布式优化的扩展： 该框架被扩展到多块一致性问题，证明了在代理通过星型拓扑进行通信的分布式设置中，同样的严格鞍点规避保证依然成立。

结果与数值实验
理论发现通过两个超出全局 Lipschitz 平滑范畴的多项式模型的数值实验得到了验证：

• 分布式矩阵分解： 算法成功解决了分布式低秩矩阵恢复问题。实验表明，目标函数和一致性残差能迅速收敛至机器精度，证实了算法处理非 Lipschitz 多项式目标的能力。
• 对称张量分解： 作者将 Bregman 近端分裂思想应用于对称张量分解。虽然理论保证严格适用于可分离目标，但该实验展示了 Bregman 正则化在稳定耦合多项式目标的子问题中的实际效用。算法在最小化重建误差的同时，驱动各因子趋于一致。

意义与主张
本文声称，此前在欧几里得近端方法及 Lipschitz 假设下建立的严格鞍点规避机制，在相对平滑性的 Bregman ADMM 中依然存在。其意义在于将二阶收敛保证扩展到了更广泛的非凸问题类（特别是具有多项式目标的模型），在这些问题中，标准的平滑常数在全局范围内并不存在。

作者强调，将近端项扩展为 Bregman 项并非简单的替换，而是需要通过重新推导不稳定性证明来处理 Bregman 几何，特别是要处理由核 Hessian 引入的度量块。这项工作弥补了非凸 Bregman 方法的一阶收敛结果与避免严格鞍点的理想性质之间的鸿沟，从而确保在矩阵和张量分解等结构化问题中，极限点更有可能成为局部（通常也是全局）极小值点。