Stochastic and incremental subgradient methods for convex optimization on Hadamard spaces

Each language version is independently generated for its own context, not a direct translation.

这是一篇关于如何在“弯曲”的世界里做数学优化的论文。为了让你轻松理解，我们可以把这篇论文的核心思想想象成一场**“在奇怪地形上寻找最低点”的探险**。

1. 背景：我们在哪里？（哈达马空间）

想象一下，传统的数学优化（比如找函数的最小值）通常发生在平坦的欧几里得空间里，就像在一张平整的大操场上跑步。在这里，你可以画直线，可以用简单的“斜率”（导数）来判断往哪走能下坡。

但现实世界（以及很多科学问题，比如生物进化树的比较、正定矩阵的分析）并不在平地上。它们发生在**哈达马空间（Hadamard spaces）**里。

比喻：这就像是在弯曲的地球表面、双曲空间（像马鞍面），甚至是由树枝组成的树状空间（BHV 树空间）上。
问题：在这些地方，没有“直线”，也没有传统的“斜率”。如果你试图用旧地图（传统数学工具）导航，会迷路。特别是，传统的“次梯度”（Subgradient，一种告诉我们要往哪个方向走的箭头）依赖于线性结构，而在这些弯曲空间里，这种结构不存在。

2. 核心难题：没有“指南针”怎么办？

在平坦的操场上，如果我们要找最低点，我们会看脚下的坡度，然后顺着最陡的下坡方向走。这个“坡度”就是次梯度。

但在弯曲的树状空间或双曲空间里：

你无法定义一个通用的“向量”来指路。
之前的尝试（比如利用切空间）太复杂，而且需要空间有特定的曲率限制，就像要求你的鞋子必须适应某种特定的地形，换一种地形就不行了。

这篇论文的突破：作者们发明了一种全新的“指南针”，叫做Busemann 次梯度（Busemann subgradient）。

3. 新工具：Busemann 次梯度（基于“光”的导航）

作者们没有试图在弯曲的地面上画直线，而是利用了**“射线”（Rays）和“布塞曼函数”（Busemann functions）**。

创意比喻：无限远处的灯塔
想象你在一个巨大的、弯曲的迷宫里。传统的次梯度是告诉你“往左下走”。但在这里，作者说：“别管具体的向量，想象有一束光从无限远处射过来（射线），或者想象有一个在无限远处的灯塔（布塞曼函数）。”
- Busemann 次梯度就是告诉你：“沿着这条射线，以这个速度前进，就能保证你离目标更近。”
- 它不再是一个复杂的向量，而是一个**“方向 + 速度”**的组合。这就像是在弯曲的地球上，你不需要知道经纬度坐标的微小变化，只需要知道“沿着这条经线一直走”以及“走多快”。

4. 解决方案：随机和增量算法

有了这个新指南针，作者设计了两种新的“探险策略”来解决复杂的优化问题（比如找一组树的“中位数”）：

随机子梯度法（Stochastic Method）：
- 比喻：想象你要找一堆散落在森林里的宝藏的平均位置。你不需要每次看完所有树再决定怎么走。你随机挑一棵树，看看它给你的“指南针”指向哪里，走一步；再随机挑一棵，再走一步。
- 优势：就像在迷雾中，不需要看清全貌，只要每走一步都稍微往对的方向挪一点，最终也能汇聚到中心。
增量子梯度法（Incremental Method）：
- 比喻：你按顺序（1, 2, 3...）检查每一棵树，每看一棵就调整一次路线。
- 优势：这种方法更有序，适合数据量固定且需要精确控制的情况。

关键发现：作者证明了，虽然地形很怪，但只要用这种新的“指南针”，这两种方法的效率（收敛速度）和我们在平坦操场上用的老方法是一样好的！它们都能在合理的步数内找到答案。

5. 实际应用：寻找“树的中位数”

论文最后展示了一个具体的例子：BHV 树空间中的中位数问题。

场景：在生物学中，科学家有很多棵“进化树”（描述物种如何分化的树）。他们想知道这些树的“平均”或“中间”形态是什么。
挑战：树的空间是弯曲的，而且有很多分支。传统的“平均”在这里行不通。
结果：作者用他们的新算法，成功地在这些复杂的树状空间中找到了“中位数树”。这就像在无数种可能的进化路径中，找到了最能代表这一组数据的“典型路径”。

6. 总结：为什么这很重要？

打破局限：以前，很多优化问题只能在平坦的数学世界里解决。这篇论文把工具箱扩展到了弯曲、树状、非线性的世界。
简单而强大：他们抛弃了复杂的线性代数技巧，转而使用更几何化、更直观的“射线”概念。
通用性：这种方法不仅适用于找树的中心，还适用于任何需要在弯曲空间里找“最佳点”的问题（比如最小包围球、某些统计估计等）。

一句话总结：
这篇论文发明了一种**“在弯曲和树状地形上也能精准导航的新指南针”**，让计算机能够高效地解决以前难以处理的复杂优化问题，就像给在迷宫里探险的人发了一副能看透无限远处的眼镜。

Each language version is independently generated for its own context, not a direct translation.

这是一份关于论文《Hadamard 空间上凸优化的随机和增量次梯度方法》（Stochastic and incremental subgradient methods for convex optimization on Hadamard spaces）的详细技术总结。

1. 研究背景与问题 (Problem)

背景：凸优化在欧几里得空间和希尔伯特空间之外具有广泛应用。非正曲率度量空间（即 Hadamard 空间或 CAT(0) 空间）提供了一个更广泛的框架，涵盖了双曲空间、度量树（如 BHV 树空间）以及更一般的 CAT(0) 立方复形。
核心挑战：
- 在 Hadamard 空间中，缺乏线性结构使得传统的对偶（Dual）构造（如欧几里得空间中的线性次梯度）变得模糊或不可用。
- 现有的基于**近端（Proximal）**的方法（如近端点算法）虽然理论上可行，但在实际计算中往往难以实现，因为近端算子通常涉及复杂的二分搜索或难以求解的子问题，且步长参数与更新长度之间的关系不明确。
- 现有的基于流形的次梯度方法依赖于局部线性化（切空间）和指数映射，这要求空间具有下界曲率限制，且技术复杂，无法推广到一般的 Hadamard 空间（如树空间）。
- 基于“支撑射线（Supporting Rays）”的 horospherical 次梯度方法虽然适用于一般 Hadamard 空间，但要求目标函数具有准凸性，且难以处理结构化目标函数（如多个分量之和），因为支撑射线的组合性质不明确。

研究目标：开发一种适用于一般 Hadamard 空间的次梯度方法，该方法不依赖线性结构或曲率下界，能够处理结构化凸优化问题（如分量之和），并具有与欧几里得空间相当的复杂度保证。

2. 方法论 (Methodology)

论文提出了一种基于 Busemann 次梯度（Busemann Subgradients） 的全新框架，主要包含以下核心概念和算法：

2.1 理论基础：Busemann 次梯度

Busemann 函数：利用射线（Ray）定义的 Busemann 函数 $b_\xi$ 作为 Hadamard 空间中仿射函数的自然推广。
边界锥（Boundary Cone）：引入空间 $X$ 在无穷远处的边界 $X_\infty$ 及其上的锥拓扑，定义边界锥 $CX_\infty = X_\infty \times \mathbb{R}_+ / \sim$ 。
定义：函数 $f$ 在点 $x$ 处的 Busemann 次梯度 定义为元素 $[\xi, s] \in CX_\infty$ ，满足次梯度不等式：
$f(y) - f(x) \ge s(b_\xi(y) - b_\xi(x)) \quad \forall y \in C$
其中 $s \ge 0$ 代表“速度”， $\xi$ 代表方向。
性质：
- 在欧几里得空间中，Busemann 次梯度等价于传统的次梯度（通过 $[\xi, s] \leftrightarrow -s\xi$ 对应）。
- 距离函数 $d(\cdot, a)$ 及其凸组合（如 $p$ -均值问题）是 Busemann 次可微的。
- 关键局限：Busemann 次可微性不保持加法封闭性（即两个 Busemann 次可微函数的和不一定次可微）。这解释了为什么必须采用**分裂（Splitting）**策略来处理结构化目标函数。

2.2 算法设计

针对结构化目标函数 $f(x) = \sum_{i=1}^m f_i(x)$ ，论文提出了两种算法：

随机 Busemann 次梯度法 (Algorithm 1)：
- 在每次迭代中随机选择一个分量 $f_i$ 。
- 调用 Oracle 获取 $f_i$ 在 $x_k$ 处的 Busemann 次梯度 $[\xi_k, s_k]$ 。
- 沿射线 $r_{x_k, \xi_k}$ 以速度 $s_k$ 移动步长 $t_k$ ，然后投影回可行集 $C$ 。
增量 Busemann 次梯度法 (Algorithm 2)：
- 按循环顺序依次处理每个分量 $f_1, \dots, f_m$ 。
- 在每个分量上执行一次次梯度更新，形成一轮迭代。

2.3 复杂度分析

证明了在直径有界（ $D$ $D$ ）且 Lipschitz 常数有界（ $L$ $L$ ）的条件下，使用步长 $t_k \propto 1/\sqrt{k}$ $t_{k} \propto 1/ k$ ：
- 随机方法：期望最优值误差为 $O(mLD / \sqrt{k})$ 。
- 增量方法：确定性最优值误差为 $O(mLD / \sqrt{k})$ 。
这些复杂度界限与欧几里得空间中的经典次梯度方法完全一致。

3. 主要贡献 (Key Contributions)

新的次梯度概念：首次系统性地定义了基于 Busemann 函数的次梯度，成功将次梯度方法推广到没有线性结构的 Hadamard 空间，且无需曲率下界假设。
几何直观与计算可行性：
- 将次梯度解释为“射线 + 速度”，比近端算子更直观、更易计算。
- 证明了距离函数、Busemann 函数及其凸组合（如 $p$ -均值）均具有 Busemann 次梯度，且易于计算。
结构化优化的分裂策略：
- 揭示了 Busemann 次可微性不满足加法封闭性，从而论证了必须使用随机或增量分裂方法来处理分量之和。
- 克服了基于支撑射线的 horospherical 方法在处理分量之和时的局限性。
严格的复杂度保证：建立了与欧几里得空间相当的 $O(\epsilon^{-2})$ 迭代复杂度，证明了该方法在理论上的高效性。
应用验证：将方法应用于 BHV 树空间（Tree Space） 中的中位数（Median）和 $p$ -均值问题，并提供了数值实验验证。

4. 实验结果 (Results)

实验设置：在 $T_4$ （4 个叶节点的树空间，由 15 个二维象限组成的 CAT(0) 空间）上测试。
测试问题：计算给定树集合的加权中位数（Weber 问题， $p=1$ ）。
对比算法：与文献 [6] 中的循环近端点算法（Cyclic Proximal Point）进行对比。
发现：
- 收敛性：随机和增量算法均能有效收敛到最优解。
- 步长选择：虽然理论推荐 $t_k \sim 1/\sqrt{k}$ ，但在增量算法中， $t_k = 1/k$ 在实际表现上往往更优（尽管随机算法在 $1/k $步长下表现不佳，需$ 1/\sqrt{k}$）。
- 效率：随机算法仅需增量算法 $1/3$ 的 Oracle 调用次数（因为每次迭代只处理一个分量），表现出极高的效率。
- 粘性现象（Stickiness）：在 Example 8.2 中，观察到中位数落在低维边界（脊线）上的“粘性”现象，算法成功处理了这种情况。
- 与近端法对比：在典型的中位数问题上，次梯度方法与近端点方法性能相当，但次梯度方法在实现上更简单（无需解决复杂的近端子问题）。

5. 意义与影响 (Significance)

理论突破：解决了非正曲率空间优化中“次梯度”定义的难题，填补了从欧几里得空间到一般 Hadamard 空间优化理论的重要空白。
算法实用性：为处理树空间（BHV 空间）、双曲空间等复杂几何结构上的优化问题提供了实用工具。这对于系统发育树分析、形状分析等领域具有重要意义。
通用性：该方法不仅适用于 $p$ -均值问题，还可推广到最小包围球、Tyler's M-估计量以及 Horn 问题等更广泛的优化场景。
未来方向：论文指出，虽然 Busemann 次梯度在 Hadamard 空间有效，但在曲率有上界但可能为正（Alexandrov 空间）的情况下，该概念可能失效，这为未来的研究留下了空间。

总结：该论文通过引入基于 Busemann 函数的次梯度概念，成功地将经典的随机和增量次梯度方法推广到了非线性的 Hadamard 空间。该方法不仅具有坚实的几何基础，而且提供了与经典欧几里得情形相匹配的复杂度保证，为复杂几何空间上的大规模凸优化问题提供了一套高效、可实现的解决方案。