2025-11-10T03:06:05.923380

Revisit First-order Methods for Geodesically Convex Optimization

Shu, Jiang, Shi et al.
In a seminal work of Zhang and Sra, gradient descent methods for geodesically convex optimization were comprehensively studied. In particular, Zhang and Sra derived a comparison inequality that relates the iterative points in the optimization process. Since their seminal work, numerous follow-ups have studied different downstream usages of their comparison lemma. In this work, we introduce the concept of quasilinearization to optimization, presenting a novel framework for analyzing geodesically convex optimization. By leveraging this technique, we establish state-of-the-art convergence rates -- for both deterministic and stochastic settings -- under weaker assumptions than previously required. The technique of quasilinearization may prove valuable for other non-Euclidean optimization problems.
academic

Revisit First-order Methods for Geodesically Convex Optimization

基本信息

  • 论文ID: 2504.06814
  • 标题: Revisit First-order Methods for Geodesically Convex Optimization
  • 作者: Yunlu Shu, Jiaxin Jiang, Lei Shi, Tianyu Wang (复旦大学)
  • 分类: math.OC (数学优化与控制)
  • 发表时间: 2025年10月16日 (arXiv v4版本)
  • 论文链接: https://arxiv.org/abs/2504.06814

摘要

本文重新审视了测地凸优化中的一阶方法。Zhang和Sra在其开创性工作中全面研究了测地凸优化的梯度下降方法，特别是推导了关联优化过程中迭代点的比较不等式。本文引入了拟线性化(quasilinearization)概念到优化领域，提出了分析测地凸优化的新框架。通过利用这一技术，在比以往更弱的假设条件下，为确定性和随机设置建立了最先进的收敛率。拟线性化技术可能对其他非欧几里德优化问题具有价值。

研究背景与动机

问题定义

本文研究Hadamard流形上的优化问题： min⁡x∈Mf(x)\min_{x \in M} f(x) 其中M是配备黎曼度量g的Hadamard流形。

研究动机

  1. 现有方法的局限性：Zhang和Sra的经典方法依赖于两个强假设：
    • (A1) 截面曲率的一致下界 (CBB条件)
    • (A2) 轨迹直径的先验上界
  2. 实际问题：许多重要的Hadamard流形不满足CBB条件，例如翘曲积流形，其曲率可能趋于负无穷。
  3. 核心挑战：如何在去除假设(A1)和(A2)的同时保持最先进的收敛率？

核心贡献

  1. 引入拟线性化框架：首次将Berg和Nikolaev的拟线性化概念应用于优化问题分析
  2. 去除强假设：在不需要曲率下界和有界域假设的条件下建立收敛保证
  3. 确定性优化：对测地凸函数实现O(1/t)收敛率
  4. 随机优化：对光滑测地凸函数实现Õ(1/√t)收敛率
  5. 理论突破：提供了Question (Q)的肯定答案，即可以在更弱假设下保持最优收敛率

方法详解

拟线性化内积

对于流形M上的任意两个有序测地线段xy→\overrightarrow{xy}和zw→\overrightarrow{zw}，拟线性化内积定义为：

⟨xy→,zw→⟩=∣xy→∣∣zw→∣cos⁡q(xy→,zw→)\langle\overrightarrow{xy}, \overrightarrow{zw}\rangle = |\overrightarrow{xy}||\overrightarrow{zw}|\cos_q(\overrightarrow{xy}, \overrightarrow{zw})

其中： cos⁡q(xy→,zw→)=∣xw→∣2+∣yz→∣2−∣xz→∣2−∣yw→∣22∣xy→∣∣zw→∣\cos_q(\overrightarrow{xy}, \overrightarrow{zw}) = \frac{|\overrightarrow{xw}|^2 + |\overrightarrow{yz}|^2 - |\overrightarrow{xz}|^2 - |\overrightarrow{yw}|^2}{2|\overrightarrow{xy}||\overrightarrow{zw}|}

拟凸性定义

函数f是q-凸的，如果： f(x)≥f(y)+⟨yExpy(gradf(y))→,yx→⟩+μ2d2(x,y)f(x) \geq f(y) + \langle\overrightarrow{y\text{Exp}_y(\text{grad}f(y))}, \overrightarrow{yx}\rangle + \frac{\mu}{2}d^2(x,y)

近端梯度算法

核心算法采用隐式近端更新： xt=Expxt+1(ηgradf(xt+1))x_t = \text{Exp}_{x_{t+1}}(\eta \text{grad}f(x_{t+1}))

等价于求解： xt+1=arg⁡min⁡z{f(z)+12ηd(xt,z)2}x_{t+1} = \arg\min_z \left\{f(z) + \frac{1}{2\eta}d(x_t, z)^2\right\}

理论分析

主要定理

定理1（确定性情况）：设f是Hadamard流形M上的测地凸函数，近端梯度算法满足： f(xt)−f(x∗)≤∣x0x∗→∣2ηtf(x_t) - f(x^*) \leq \frac{|\overrightarrow{x_0x^*}|^2}{\eta t}

定理2（随机情况）：在有界方差假设下，随机近端梯度算法with步长ηt=12Lt\eta_t = \frac{1}{2L\sqrt{t}}满足： 1∑t=1Tαt∑t=1Tαt(EF(xt)−F(x∗))≤∣x0x∗→∣22∑t=1Tαt+σ2log⁡(T+1)∑t=1Tαt\frac{1}{\sum_{t=1}^T \alpha_t}\sum_{t=1}^T \alpha_t(\mathbb{E}F(x_t) - F(x^*)) \leq \frac{|\overrightarrow{x_0x^*}|^2}{2\sum_{t=1}^T \alpha_t} + \frac{\sigma^2 \log(T+1)}{\sum_{t=1}^T \alpha_t}

关键技术洞察

  1. 拟线性化的优势：
    • 适用于所有Hadamard流形，无需曲率下界
    • 保持类似欧几里德空间的代数性质
    • 与测地凸性自然兼容
  2. 证明技巧：
    • 利用Lemma 2建立拟线性化内积与标准内积的关系
    • 通过望远镜求和技术处理迭代不等式
    • 巧妙避开了传统的三角比较定理限制

实验设置与结果

对比分析

论文通过表格形式对比了不同方法的假设条件和收敛率：

方法需要曲率下界?需要有界域?需要求解复杂方程?收敛率
Zhang & Sra是是否O(t⁻¹)
Liu et al.否是是O†(t⁻²)
本文方法否否否O(t⁻¹)

实现细节

论文提供了近端算子的高效实现方法：

  • 通过梯度下降求解强测地凸子问题
  • 温启动策略提高计算效率
  • 收敛保证：f(zt)−f(z∗)≤(1−μ4L0)t(f(z0)−f(z∗))f(z_t) - f(z^*) \leq (1-\frac{\mu}{4L_0})^t(f(z_0) - f(z^*))

相关工作

历史发展

  1. 经典工作：Bonnabel (2013)和Zhang & Sra (2016)建立了基础分析框架
  2. 后续研究：多项工作尝试放松假设条件，但都未能完全解决Question (Q)
  3. 技术路线：传统方法依赖Toponogov三角比较定理，本文开辟了拟线性化新路径

技术对比

  • 传统方法：依赖截面曲率下界，分析复杂
  • 本文方法：利用拟线性化，假设更弱，分析更简洁
  • 计算复杂度：避免了求解涉及Exp⁻¹和Γ的复杂方程

结论与讨论

主要结论

  1. 成功回答了十年来的开放问题Question (Q)
  2. 建立了在最弱假设下的最优收敛率
  3. 为非欧几里德优化提供了新的分析工具

局限性

  1. 仍需要Hadamard流形结构（非正曲率）
  2. 近端算子可能需要数值求解
  3. 常数因子可能不是最优的

未来方向

  1. 扩展到非光滑优化问题
  2. 研究加速方法的可能性
  3. 应用到具体的机器学习问题

深度评价

优点

  1. 理论突破：解决了领域内的重要开放问题
  2. 方法创新：拟线性化技术的引入具有开创性
  3. 假设最弱：在最少假设条件下实现最优收敛率
  4. 分析简洁：证明相比传统方法更加直接

不足

  1. 实验验证不足：缺乏数值实验验证理论结果
  2. 应用场景有限：主要关注理论分析，实际应用展示不足
  3. 常数分析：未提供收敛常数的精确估计

影响力

  1. 理论价值：为黎曼优化理论做出重要贡献
  2. 方法论意义：拟线性化技术可能影响更广泛的非欧几里德优化
  3. 实用潜力：为实际应用中的流形优化提供更强的理论保证

适用场景

  1. 机器学习中的流形约束优化
  2. 计算几何中的测地问题
  3. 数值偏微分方程求解
  4. 经济学中的均衡计算

参考文献

论文引用了61篇相关文献，主要包括：

  • Berg & Nikolaev (2008): 拟线性化的原始工作
  • Zhang & Sra (2016): 测地凸优化的经典分析
  • Bonnabel (2013): 黎曼流形上的随机梯度下降
  • 多篇关于Hadamard流形优化的近期工作

总体评价：这是一篇高质量的理论论文，通过引入拟线性化技术成功解决了测地凸优化领域的重要开放问题。虽然缺乏数值实验，但其理论贡献显著，为非欧几里德优化提供了新的分析框架和工具。