曲率无关的 Hadamard 流形上分布式在线优化的遗憾界

# Hadamard流形上分布式在线优化的曲率无关遗憾界
来源: https://arxiv.org/html/2609.13646
Emre Sahinoglu, Shahin Shahrampour††thanks:本工作部分受美国国家科学基金会ECCS-2240788奖项以及NSF CAREER奖项ECCS-2442321资助。††thanks:作者隶属于波士顿东北大学机械与工业工程系，邮编02115。邮箱: \{cai\.zha; sahinoglu\.m;s\.shahrampour\}@northeastern\.edu\.

###### 摘要

本工作研究Hadamard流形上的去中心化在线黎曼优化。先前基于测地凸性（g-凸性）的工作在优化分析中可能需要曲率信息，通常体现为对截面曲率的有限下界约束。曲率也可能影响切空间黎曼共识方案的步长或收缩因子。本文针对一类更窄的水平面凸（h-凸）函数，放松了对曲率的依赖性。我们研究了分布式黎曼在线梯度下降算法（D-ROGD），该算法结合了局部黎曼h-次梯度更新与隐式Fréchet均值共识。对于h-凸和强h-凸局部目标函数，我们分别建立了O(√T)和O(log T)的静态遗憾界，其关于时间T的收敛速率与欧几里得空间对应速率一致，网络依赖性仅由谱隙决定。据我们所知，这是Hadamard流形上首个曲率无关的去中心化在线优化遗憾保证。双曲嵌入实验结果验证了理论预测的速率，且未观察到因曲率引起的性能下降。

###### 索引关键词:

在线优化、黎曼优化、分布式优化、Hadamard流形、水平面凸性、遗憾界。

## I 引言

许多控制与工程问题自然涉及约束在非线性几何空间中的决策变量。典型例子包括对称正定矩阵的协方差估计与平均[1 (https://arxiv.org/html/2609.13646#bib.bib1)]、具有结构化正定变量的黎曼系统辨识[2 (https://arxiv.org/html/2609.13646#bib.bib2)]，以及基于控制约束导出的子流形上的反馈策略合成[3 (https://arxiv.org/html/2609.13646#bib.bib3)]。黎曼优化为此类问题提供了框架，允许在尊重决策空间几何结构的同时直接在底层流形上进行优化[4 (https://arxiv.org/html/2609.13646#bib.bib4), 5 (https://arxiv.org/html/2609.13646#bib.bib5)]。

另一方面，许多控制、估计和学习系统的序列与分布式特性，推动了黎曼优化的在线化与去中心化扩展。在线设置中，目标函数随时间变化且仅在决策做出后才被揭示[6 (https://arxiv.org/html/2609.13646#bib.bib6), 7 (https://arxiv.org/html/2609.13646#bib.bib7)]；而去中心化设置中，数据和/或计算分布在代理网络中[8 (https://arxiv.org/html/2609.13646#bib.bib8)]。结合这两种设置，我们考虑代理依次更新其流形值的决策，观察私有局部损失，并仅与相邻代理通信，目标是在回顾视角下相对于最佳固定集体决策实现较小的遗憾。虽然该框架在欧几里得领域已被充分理解，但其黎曼对应物引入了额外的几何挑战。

与欧几里得设置不同，曲率可通过两种不同机制影响去中心化在线黎曼优化。在优化侧，标准的g-凸性分析依赖于黎曼余弦不等式，其中包含因子√\|κ\|D coth(√\|κ\|D)，这要求截面曲率具有有限下界，且性能随曲率κ和域直径D增大而恶化[9 (https://arxiv.org/html/2609.13646#bib.bib9)]。在网络侧，依赖曲率的切空间共识方案可能需要依赖曲率的步长和收缩因子[10 (https://arxiv.org/html/2609.13646#bib.bib10), 11 (https://arxiv.org/html/2609.13646#bib.bib11), 12 (https://arxiv.org/html/2609.13646#bib.bib12)]。隐式Fréchet均值共识避免了这种对Hadamard流形的依赖[10 (https://arxiv.org/html/2609.13646#bib.bib10)]，但与O(log T)遗憾所需的递减步长相兼容的曲率无关误差保证尚未建立。因此，曲率无关的遗憾界需要同时控制优化进展和网络误差，且不包含曲率相关项。

我们通过互补的几何机制解决这两个曲率依赖的来源。在优化侧，我们采用水平面凸性（h-凸性），它通过Busemann函数提供无曲率的不等式[13 (https://arxiv.org/html/2609.13646#bib.bib13), 14 (https://arxiv.org/html/2609.13646#bib.bib14)]。在网络侧，我们采用隐式加权Fréchet均值共识，其收缩仅依赖于网络连通性，无需依赖曲率的共识步长[10 (https://arxiv.org/html/2609.13646#bib.bib10)]。然后，我们针对任意步长调度开发了曲率无关的网络误差分析，适应h-凸和强h-凸在线两种情形，而无需截面曲率具有有限下界。这种曲率无关性是以更受限的目标函数类和每轮需要求解Fréchet均值子问题为代价的。我们的主要贡献如下：

- • 曲率无关遗憾。我们提出分布式黎曼在线梯度下降（D-ROGD），并分别为h-凸和强h-凸损失建立O(√T)和O(log T)的静态遗憾界（定理III\.2 (https://arxiv.org/html/2609.13646#S3.Thmtheorem2)和III\.3 (https://arxiv.org/html/2609.13646#S3.Thmtheorem3)），无需截面曲率具有有限下界。这些速率在T方面与欧几里得对应速率一致，网络依赖性由谱隙控制[15 (https://arxiv.org/html/2609.13646#bib.bib15), 16 (https://arxiv.org/html/2609.13646#bib.bib16)]。据我们所知，这是Hadamard流形上首个曲率无关的去中心化在线优化遗憾保证。
- • 任意步长下的网络误差。我们在任意步长调度下，建立了由隐式加权Fréchet均值共识引起的网络误差的曲率无关界（引理III\.1 (https://arxiv.org/html/2609.13646#S3.Thmtheorem1)），网络依赖性仅由谱隙决定。该界对递减步长（包括强h-凸分析中的ηₜ=1/(μt)）仍然有效。虽然此结果对我们建立遗憾界至关重要，但其本身也可能具有独立意义。
- • 数值验证。我们在真实层次数据的双曲嵌入上评估D-ROGD，同时改变流形曲率和网络连通性。实验显示的遗憾增长与理论速率一致，未观察到随曲率增加的系统性恶化，并证实较差的网络连通性会导致更高的遗憾，这与理论界的谱隙依赖性预测一致。

### I‑A 文献综述

**黎曼在线优化与曲率无关性**。黎曼流形上的在线优化主要基于g-凸性发展，将经典遗憾分析扩展到弯曲决策空间[6 (https://arxiv.org/html/2609.13646#bib.bib6), 7 (https://arxiv.org/html/2609.13646#bib.bib7)]。后续工作考虑了零阶反馈与跟踪[17 (https://arxiv.org/html/2609.13646#bib.bib17)]、无投影在线优化[18 (https://arxiv.org/html/2609.13646#bib.bib18)]以及具有动态遗憾的乐观方法[19 (https://arxiv.org/html/2609.13646#bib.bib19)]。该文献的一个持续特征是，标准的g-凸分析依赖几何比较不等式，其常数取决于截面曲率的有限下界[9 (https://arxiv.org/html/2609.13646#bib.bib9)]，这激励了近期对曲率无关在线保证的研究。一条由Roux等人[20 (https://arxiv.org/html/2609.13646#bib.bib20)]提出的路径保留g-凸性，通过非精确隐式更新去除几何常数，代价是用近似求解的隐式子问题替代标准显式一阶步骤。h-凸性提供了一条互补的结构路径，它在Hadamard流形上使用Busemann函数获得曲率无关的比较不等式[13 (https://arxiv.org/html/2609.13646#bib.bib13), 21 (https://arxiv.org/html/2609.13646#bib.bib21)]。基于此框架，Sahinoglu和Shahrampour[14 (https://arxiv.org/html/2609.13646#bib.bib14)]分别建立了h-凸和强h-凸目标函数在线优化的曲率无关O(√T)和O(log T)遗憾界。然而，这些结果涉及单个在线学习者，留下了如何在去中心化设置中保持曲率无关性的问题，因为网络分歧引入了额外的几何挑战。

**去中心化黎曼优化与共识**。分布式在线黎曼优化迄今主要基于g-凸性发展。Chen和Sun[10 (https://arxiv.org/html/2609.13646#bib.bib10)]在Hadamard流形上分析了动态遗憾，而Sahinoglu和Shahrampour[11 (https://arxiv.org/html/2609.13646#bib.bib11)]将分布式在线优化扩展到Hadamard流形之外，涵盖零阶反馈的场景。最近，Cai等人[12 (https://arxiv.org/html/2609.13646#bib.bib12)]使用适应递减步长的网络误差分析，为强g-凸目标函数建立了O(log T)遗憾界。尽管有这些进展，曲率相关量仍然存在于g-凸下的优化分析或共识机制中。相比之下，我们结合h-凸性与隐式加权Fréchet均值共识，并建立了任意步长调度下曲率无关的分歧界。这使得遗憾分析的优化和网络部分都能保持对截面曲率界的独立性。

## II 预备知识

我们在Hadamard流形M上工作，即具有非正截面曲率的完备单连通黎曼流形。对于x∈M，记TₓM为切空间，⟨·,·⟩ₓ为黎曼度量，其诱导范数‖v‖ₓ := √⟨v,v⟩ₓ，当含义明确时省略下标，d(·,·)为诱导测地距离。为简洁起见，对于x,y∈M，我们也记‖xy‖ := d(x,y)。集合X⊆M是测地凸（g-凸）的，如果连接X中任意两点的测地线段完全位于X中。指数映射Expₓ: TₓM → M和对数映射Logₓ: M → TₓM在Hadamard流形上是全局定义良好的，更多背景知识参见[4 (https://arxiv.org/html/2609.13646#bib.bib4), 5 (https://arxiv.org/html/2609.13646#bib.bib5)]。

### II‑A 问题描述

#### II‑A1 去中心化在线黎曼优化

考虑n个代理通过由对称双随机矩阵W=(wᵢⱼ)∈ℝⁿˣⁿ描述的网络进行通信，其中当i≠j时，wᵢⱼ>0仅当代理i和j是邻居[10 (https://arxiv.org/html/2609.13646#bib.bib10), 8 (https://arxiv.org/html/2609.13646#bib.bib8)]。在每轮t∈[T]:={1,...,T}，代理i从公共可行集X⊆M中选择决策xᵢ,ₜ，并在xᵢ,ₜ处获得一阶反馈。全局损失定义为

fₜ(x) := (1/n) ∑ᵢ₌₁ⁿ fᵢ,ₜ(x).   (1)
我们通过静态遗憾评估代理的集体性能，它衡量代理决策与回顾视角下的最佳固定集体决策之间的累积差距，两者均基于全局损失序列评估。具体而言，

Reg(T) := (1/n) ∑ᵢ₌₁ⁿ ∑ₜ₌₁ᵀ fₜ(xᵢ,ₜ) - ∑ₜ₌₁ᵀ fₜ(x*),   (2)
其中x* ∈ argmin_{x∈X} ∑ₜ₌₁ᵀ fₜ(x)。目标是设计一个去中心化算法，仅使用局部损失信息和邻居间通信，实现次线性遗憾Reg(T) = o(T)。

为在流形上执行共识，我们使用加权Fréchet均值作为欧几里得平均的内蕴类似物。给定点{zⱼ}ⱼ₌₁ⁿ⊂M和权重wⱼ≥0（∑ⱼ₌₁ⁿ wⱼ=1），它们的加权Fréchet均值定义为

z̄_w := argmin_{z∈M} { ∑ⱼ₌₁ⁿ wⱼ d²(z, zⱼ) },   (3)
这在Hadamard流形上是唯一定义的[22 (https://arxiv.org/html/2609.13646#bib.bib22)]。在去中心化设置中，代理i使用权重{wᵢⱼ}ⱼ₌₁ⁿ通过此最小化聚合其邻居的迭代点，产生隐式共识更新[10 (https://arxiv.org/html/2609.13646#bib.bib10)]。与欧几里得空间中的线性平均不同，该更新通过流形上的优化问题定义。

对于等权重情况，我们记集合{zᵢ}ᵢ₌₁ⁿ⊂M的Fréchet均值为z̄ := argmin_{z∈M} (1/n) ∑ᵢ₌₁ⁿ d²(z, zᵢ)，并定义相应的Fréchet方差为

V_F({zᵢ}ᵢ₌₁ⁿ) := (1/n) ∑ᵢ₌₁ⁿ d²(z̄, zᵢ).   (4)
Fréchet方差作为代理间分歧的几何度量，将用于刻画隐式共识步的收缩性。

#### II‑A2 水平面凸性

函数f: M→ℝ是测地凸（g-凸）的，如果其限制在每条测地线上在欧几里得意义下是凸的[9 (https://arxiv.org/html/2609.13646#bib.bib9), 23 (https://arxiv.org/html/2609.13646#bib.bib23)]。h-凸性是Hadamard流形上更强的概念，它使用Busemann函数作为欧几里得凸性中仿射函数的类似物；关于它们的构造和几何解释，我们参考[13 (https://arxiv.org/html/2609.13646#bib.bib13), 14 (https://arxiv.org/html/2609.13646#bib.bib14)]。对于单位速度测地射线γ: [0,∞)→M，其Busemann函数定义为B_γ(x) := lim_{t→∞} (d(x, γ(t)) - t)。