技术摘要：针对强测地凸函数的去中心化在线黎曼优化

1. 问题陈述

本文研究了黎曼流形上的去中心化在线优化问题。在这种设定下，由 $n$ 个智能体组成的网络协作最小化一个随时间变化的全局损失函数 $f_t = \frac{1}{n}\sum_{i=1}^n f_{i,t}$，其中每个智能体 $i$ 仅按顺序观测其局部损失 $f_{i,t}$。智能体仅通过固定通信图与其邻居进行通信。

研究重点是定义在具有有界截面曲率（包括正曲率，如球面）的流形上的强测地凸（strongly g-convex）损失函数。性能指标是静态遗憾（static regret），定义为智能体的集体累积损失与事后最佳固定决策的累积损失之差。

研究空白： 虽然中心化在线黎曼优化和去中心化欧几里得在线优化均能针对强凸/强测地凸损失实现 $O(\log T)$ 的最优遗憾率（这相对于一般凸损失的 $O(\sqrt{T})$ 率是一个显著提升），但现有的去中心化黎曼方法仅能实现 $O(\sqrt{T})$ 的测地凸率。由于衰减步长（实现对数速率所必需）与现有假设固定步长的网络误差分析之间存在不兼容性，去中心化黎曼设置下的强测地凸领域仍处于未被探索的状态。

2. 方法论

作者为每个智能体在每个时间步 $t$ 提出了一个两步算法：

1. 梯度下降步： 智能体 $i$ 执行投影黎曼梯度下降更新：
   $$y_{i,t+1} = P_X \left( \text{Exp}_{x_{i,t}}(-\eta_t \nabla f_{i,t}(x_{i,t})) \right)$$
   其中 $\eta_t$ 是衰减步长，$P_X$ 是向可行集 $X$ 的投影。
2. 共识步： 智能体 $i$ 执行一个感知曲率的共识更新，利用指数映射和对数映射来近似邻居迭代值的加权弗雷歇均值（Fréchet mean）：
   $$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)$$
   其中 $s$ 是固定的共识步长，$W$ 是双随机通信矩阵。

分析涵盖了两种反馈设置：

• 全信息（Full Information）： 智能体观测到精确的黎曼梯度。
• 两点带状反馈（Two-Point Bandit）： 智能体仅观测两个扰动点处的函数值，并构建零阶梯度估计量。

关键技术挑战与解决方案

• 衰减步长 vs. 网络误差： 现有的去中心化黎曼优化分析假设固定步长，这会导致静态的网络误差项。作者开发了一种新的感知曲率的网络误差分析，用于处理时变（衰减）调度。他们证明了网络误差是以过去步长的加权和（几何卷积）形式累积的，而非单一的静态项，并证明该和保持为 $O(\log T)$。
• 正曲率： 在具有正曲率的流形上，度量投影 $P_X$ 不一定是非扩张的，这引入了一个额外的误差项。为了控制这一点，作者采用了形式为 $\eta_t = O(1/(t+c_0))$ 的偏移衰减步长，而非标准的 $O(1/t)$。
• 带状反馈与平滑： 在带状反馈设置中，平滑损失函数会破坏强测地凸性质。作者引入了一种新颖的**强亚测地凸（strong sub-g-convexity）**论证。他们证明了平滑后的代理函数在可控的附加松弛项范围内满足强凸类不等式。这使得他们能够通过将平滑参数 $\delta$（具体为 $\delta = O(T^{-2})$）与衰减步长进行联合调节，从而维持 $O(\log T)$ 的速率。

3. 核心贡献

1. 首次实现去中心化黎曼优化中的 $O(\log T)$ 遗憾： 本文确立了去中心化在线黎曼设置下针对强测地凸损失的第一个 $O(\log T)$ 静态遗憾界。该界限在依赖于曲率常数和通信矩阵谱隙的情况下，与欧几里得及中心化黎曼设置下强凸损失的极小极大最优速率相匹配。
2. 新颖的网络误差分析： 作者为衰减步长下的网络共识误差提供了一套通用的分析方法。他们证明了误差表现为过去步长的几何卷积，并且保持为对数级别，解决了衰减调度与现有固定步长分析之间的不兼容问题。
3. 扩展至带状反馈： 该工作将对数遗憾保证扩展到了两点带状反馈设置。通过开发用于平滑代理函数的强亚测地凸引理，并联合调节平滑半径与步长，他们在存在投影/收缩误差以及凸性退化的情况下，依然保持了 $O(\log T)$ 的速率。

4. 结果

• 理论界限：
  • 全信息： 定理 3.2 证明了静态遗憾界为 $R_1 \log(1 + \frac{T\mu D}{L}) + R_2$。
  • 带状反馈： 定理 4.5 证明了期望静态遗憾界为 $R'_1 \log(1 + \frac{T\mu D}{dL}) + R'_2$。
  • 两者都依赖于谱隙 $(1-\sigma_2(W))^{-1}$，反映了去中心化的代价。
• 数值实验：
  • 超球面 ($S^7$)： 在正曲率流形上的实验证实，所提出的强测地凸调度实现了遗憾的对数增长，显著优于 $O(\sqrt{T})$ 基准。观察到较大的共识步长可以降低遗憾。
  • SPD 流形 (FLUXNET2015)： 使用对称正定（SPD）矩阵流形（Hadamard 流形）上的真实数据集，所提方法在全信息设置下达到了约 46.8 的最终遗憾，而凸基准约为 76.9。带状变体也显示出亚线性增长，但由于零阶估计的方差，其遗憾值较高。

5. 意义与主张

本文声称解决了是否能在去中心化在线黎曼优化中获得强凸性带来的对数遗憾改进这一根本问题。作者通过以下方式肯定地回答了这个问题：

• 弥合了强凸目标下中心化与去中心化黎曼优化速率之间的差距。
• 提供了第一个处理去中心化黎曼共识中衰减步长的理论框架，而这是实现对数遗憾的必要条件。
• 证明了只要满足特定的几何约束（有界直径、单射半径），即使在正曲率流形的带状设置中，也可以利用强测地凸性。

该工作被视为一个基础性的步骤，并指出虽然它实现了静态遗憾的最优速率，但未来的工作可以探索加速 Gossip 方案以改善对谱隙的依赖关系，并将这些结果扩展到动态遗憾设置中。