Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds

技术摘要：超越哈达玛流形的去中心化在线黎曼优化

问题表述
本文研究了在可能具有正曲率的流形上进行去中心化在线黎曼优化的问题，扩展了以往仅限于哈达玛流形（具有非正曲率）的限制性设定。目标是使一个包含 $n$ 个智能体的网络在每个时间步 $t$ 协作最小化全局目标函数 $f_t(\cdot) = \frac{1}{n}\sum_{i=1}^n f_{i,t}(\cdot)$，其中每个智能体 $i$ 仅观测其局部损失函数 $f_{i,t}$。智能体在两种反馈机制下运行：

1. 全梯度反馈： 智能体可以获得其局部函数的精确黎曼梯度。
2. 两点带计（Bandit）反馈： 智能体仅能接收两个相邻点的函数值，需要构建梯度估计量。

决策变量和比较点 $x^*$ 被约束在黎曼流形 $\mathcal{M}$ 的一个测地凸子集 $\mathcal{X}$ 中。主要的计算挑战源于正曲率空间中缺乏全局凸性，以及流形的非线性特征，这使得在欧几里得去中心化优化中使用的标准共识步骤变得复杂。

方法论
作者提出了一个依赖于三个核心方法论组件的统一框架：

1. 曲率感知共识步骤：
   本文使用了一个在切空间中定义的特定共识更新规则：
   $$x_{i,t+1} = \text{Exp}_{y_{i,t+1}}\left(s \sum_{j=1}^n w_{ij} \text{Log}_{y_{i,t+1}}(y_{j,t+1})\right)$$
   其中 $y_{i,t+1}$ 是局部梯度更新与投影的结果，$W$ 是一个双随机通信矩阵，$s$ 是共识步长。不同于以往依赖于环境空间线性或哈达玛流形全局凸性的工作，本研究分析了该步骤在具有有界截面曲率 $K \in [K_{\min}, K_{\max}]$ 的一般流形上的线性方差缩减。分析通过优化步长 $s$ 来平衡由曲率引起的凸性和光滑性之间的权衡。

2. 全信息算法（算法 1）：
   在全梯度设定下，智能体执行黎曼梯度下降步骤，随后投影到可行集 $\mathcal{X}$，然后执行上述共识步骤。其遗憾分析将总误差分解为网络误差（局部变量与全局弗雷歇均值之间的差异）和局部优化误差。网络误差通过在共识分析中建立的线性方差缩减性质来界定。

3. 带计反馈算法（算法 2）与平滑处理：
   在两点带计设定下，作者采用了随机平滑技术。智能体从切空间球面均匀采样方向，并在间隔为平滑参数 $\delta$ 的两个点处评估函数。这生成了一个梯度估计量 $g^\delta_{i,t}$。

   • 次凸性分析： 由于平滑破坏了严格的测地凸性，作者证明了平滑后的目标函数是 $\delta$-测地次凸（subconvex） 的。他们证明了与完美凸性的偏差受 $\delta$ 线性控制。
   • 定义域收缩： 为了在评估靠近边界的点时确保可行性，算法在原始定义域的收缩子集 $(1-\tau)\mathcal{X}$ 上运行。

核心贡献
本文做出了以下具体的计算贡献：

• 一般流形上的线性方差缩减： 作者建立了具有正曲率和负曲率流形的共识步骤的线性收敛性（定理 III.2）。这是通过优化共识步长来管理凸性与光滑性之间的权衡实现的，这一挑战在负曲率自然强化凸性的哈达玛设定中并不存在。
• 全信息的 $O(\sqrt{T})$ 遗憾： 对于一般流形（可能具有正曲率），本文证明了去中心化梯度下降算法的静态遗憾界为 $O(\sqrt{T})$（定理 IV.2）。这达到了欧几里得设定中已知的最优速率，表明去中心化和正曲率不会渐近地降低遗憾速率。
• 首个带计反馈的 $O(\sqrt{T})$ 遗憾： 本文提供了在两点带计反馈下，去中心化在线黎曼优化的第一个 $O(\sqrt{T})$ 静态遗憾界（定理 V.2）。这是通过使用一种计算高效的梯度估计量以及对平滑目标函数次凸性的严谨分析实现的。
• 广义几何工具： 作者开发并扩展了适用于具有任意符号曲率界的流形的几何比较不等式（引理 VII.3–VII.4），其常数由 $K_{\min}$ 和 $K_{\max}$ 显式定义。

结果

• 理论界限： 推导出的静态遗憾界在全梯度和两点带计反馈设定下均为 $O(\sqrt{T})$。这些界限中的常数取决于流形的曲率、网络的连通性（通过 $W$ 的第二大奇异值）以及定义域的直径，但其相对于时间跨度 $T$ 的渐近速率保持最优。
• 数值实验： 实验是在一个 16 维单位球面（一种正曲率流形）及 50 个智能体上进行的。实验结果证实了算法的收敛性，累积遗憾按预期增长。实验表明，较大的共识步长通常会导致较低的遗憾，因为其带来了更快的共识速率；同时，由于梯度估计的方差，带计设定表现出比全信息设定更慢的收敛速度。

意义
本文声称其意义在于弥补了曲率空间下去中心化优化理论理解中的关键空白。

• 超越哈达玛： 此前关于去中心化黎曼优化的理论保证主要局限于哈达达玛流形。这项工作将这些保证扩展到了具有正曲率的流形，在这些流形中，测地距离并不能诱导出全局凸结构。
• 带计设定： 它解决了此前未被探索的在带计反馈下的去中心化在线黎曼优化领域，提供了该设定下的首个亚线性遗憾界。
• 最优性： 结果表明，即使在存在正曲率和有限反馈的情况下，只要采用曲率感知的共识和平滑技术，欧几里得去中心化在线优化中可实现的根本性 $O(\sqrt{T})$ 遗憾速率仍得以保持。

作者指出，虽然这些界限在 $T$ 方面是优化的，但未来的工作可以研究这些界限对网络连通性和曲率参数的具体依赖关系，并设计在这些特定参数下具有证明最优性的算法。