A Global Convergence Analysis of Consensus ALADIN for Convex Optimization

技术摘要：基于共识 ALADIN 的凸优化全局收敛性分析

问题表述
本文研究了分布式共识优化 (DCO) 问题，这类问题在机器学习、最优控制和电网中广泛存在。具体问题被表述为最小化一个有限和目标函数 $\Phi(y) = \sum_{i=1}^N f_i(y)$，其中 $f_i$ 代表智能体 $i$ 的局部目标。为了实现分布式计算，该问题通过引入局部变量 $x_i$ 并约束其等于全局变量 $y$（即对于所有 $i$，有 $x_i = y$）进行了重构。本文重点研究该问题的光滑且强凸实例。

方法论：CAPTAIN
作者提出了 CAPTAIN（带有参数调优和自适应不精确牛顿法的 C-ALADIN），这是一种基于共识增广拉格朗日交替不精确牛顿法 (C-ALADIN) 框架的新型分布式算法。

1. 核心机制： CAPTAIN 将标准的 C-ALADIN 迭代（涉及求解局部子问题和共识协调步骤）与一个辅助变量 $z[t]$ 相结合。
2. 自适应 Hessian 更新： 不同于需要使用恒定 Hessian 近似值 ($M_i$) 来保证全局收敛性的现有 C-ALADIN 方法，也不同于在更新 Hessian 时缺乏全局收敛保证的标准二阶方法，CAPTAIN 采用了一种触发条件来更新 $M_i$。
   • 只有当满足以下两个条件时，才会更新 Hessian 近似值 $M_i$：
     1. 充分下降： 全局目标函数值 $\Phi(y^{[k+1]})$ 相对于辅助变量 $z[t]$ 有充分下降，即 $\Phi(y^{[k+1]}) < \Phi(z[t]) - \frac{\gamma[t]}{2}\|y^{[k+1]} - z[t]\|^2$。
     2. 非微小步长： 步长 $\|y^{[k+1]} - z[t]\|$ 超过阈值 $\epsilon$。
   • 参数 $\gamma[t]$ 被自适应地设置为 Hessian 矩阵之和的最小特征值，从而在下降需求与更新速度之间取得平衡。
3. 算法流程：
   • 优化阶段： 智能体执行与无导数版本 C-ALADIN (DFC-ALADIN) 相同的局部更新和协调过程。
   • 更新阶段： 如果满足触发条件，则将 $z[t]$ 更新为当前的全局估计值，并刷新局部 Hessian 近似值 $M_i$（例如，更新为 $\nabla^2 f_i(z[t+1])$）。如果条件不满足，则 $M_i$ 保持不变。

主要贡献

• 首个具有 Hessian 更新的全局收敛性： 本文声称提出了第一个在处理光滑强凸 DCO 问题时，既能保证全局收敛性又允许进行 Hessian 更新的 C-ALADIN 框架。以往的工作要么固定 Hessian（损失了数值加速性能），要么在更新 Hessian 时缺乏全局收敛性证明。
• 理论保证：
  • 有限次更新： 作者证明了辅助变量 $z[t]$ 仅会被更新有限次（定理 1）。因此，在有限次迭代后，Hessian 矩阵将变为固定值，算法退化为具有全局收敛性的 DFC-ALADIN。
  • 次线性衰减： 连续两次辅助变量更新之间的最小距离呈次线性衰减（$O(1/\sqrt{T})$，其中 $T$ 为更新次数）（定理 2）。
  • 全局收敛： 原变量序列收敛至全局最优解。
• 数值性能： 算法在 $\ell_2$-正则化逻辑回归上进行了测试。结果表明，CAPTAIN 通过以显著更少的迭代次数达到最优解，表现优于基准方法（包括共识 ADMM、DQM、RC-ALADIN 和 DFC-ALADIN）。使用基于 BFGS 的 Hessian 重构或数据驱动初始化的变体进一步提高了效率。

结果与意义
本文证明了在分布式设置中，将二阶信息的数值优势（曲率利用）与全局收敛性的鲁棒性结合起来是可行的。

• 意义： 本文的主要贡献在于解决了 ALADIN 文献中一个长期存在的局限性：即利用更新的 Hessian 信息以提高速度与维持用于全局收敛性的 Lyapunov 函数之间的权衡。通过引入辅助变量和特定的触发条件，作者展示了可以在不牺牲全局收敛性理论保证的前提下进行 Hessian 更新。
• 声明的审慎性： 作者指出，虽然算法在全局范围内收敛，但由于停止准则的存在，辅助变量本身并不一定收敛到最优解 $y^*$；相反，更新序列会有限次终止，从而允许底层的固定 Hessian 算法驱动解趋向最优。论文也承认，未来仍需进一步研究以加速收敛、降低通信成本，并将该方法扩展到去中心化、异步和有向网络设置中。

实验验证
在 ijcnn1.tr 数据集（分布在 100 个智能体中）上的数值实验证实了理论发现。与一阶方法（共识 ADMM）以及其他缺乏全局收敛保证的二阶变体（如本特定设置下的 GIANT）或使用固定 Hessian 的方法（如 DFC-ALADIN）相比，CAPTAIN 以更少的迭代次数实现了高精度。模拟中观察到的辅助变量更新的次线性衰减与理论上的 $O(1/\sqrt{T})$ 界限相符。