📊 statistics

High-probability zeroth-order online convex optimisation beyond Euclidean geometry

本文利用锥测度采样，针对具有 $\ell_q$ -Lipschitz 损失的零阶在线凸优化问题以及采用 $\ell_p$ 正则化的 FTRL 算法，建立了统一的高概率后悔界，证明了 $q \in [1,2]$ 情形下的最优性，同时揭示了 $q > 2$ 时存在的固有差距。

原作者： David Janz, El-Mahdi El-Mhamdi, Arya Akhavan

发布于 2026-05-12

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： David Janz, El-Mahdi El-Mhamdi, Arya Akhavan

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图在一个广阔、迷雾笼罩的山谷中找到最低点（函数的“最小值”）。在一个理想的世界里，你会拥有一张地图或指南针，能确切地告诉你哪个方向是“向下”的（梯度）。但在这篇论文中，作者们处理的情况是：你没有地图，也没有指南针。你只能迈出一小步，感受地面，然后问：“这里比刚才高还是低？”这被称为零阶优化。

本文解决的是这个问题的一个特定且棘手的版本：在线凸优化。

**“在线”**意味着你是一步步做出决策的，就像玩一个你不知道下一步会发生什么的游戏。
**“凸”**意味着山谷具有优美、平滑的碗状形状（没有隐藏的山丘或奇怪的凸起），这使得在理论上找到谷底成为可能。
**“零阶”**意味着你只能在两个特定点“品尝”地面来推测坡度，而不是看到整座山。

以下是他们工作的分解，使用了简单的类比：

1. 问题：在黑暗中推测坡度

通常，要找到山谷的底部，你需要知道坡度。既然你看不到坡度，你就必须推测它。标准的做法是在彼此靠近的两个点“戳”地面（一步向前，一步向后），然后观察高度差。这被称为两点有限差分估计量。

作者问道：如果地面的形状不同，我们如何最好地推测坡度？

山谷是圆形的（欧几里得范数）吗？
它是菱形的（L1 范数）吗？
它是方形的（L∞范数）吗？

他们研究了当“地面”（损失函数）和“游戏规则”（几何结构）可以是上述任何形状时，如何推测坡度。

2. 创新：“圆锥”采样策略

为了推测坡度，你需要选择一个方向去“戳”地面。

旧方法： 大多数人随机选择一个方向，就像掷骰子在一个完美的球体（如篮球）上选择方向一样。
本文的方法： 作者建议基于不同形状（如菱形或立方体）上的**“圆锥测度”**来选择方向。

类比： 想象你被蒙住眼睛在一个房间里。

如果房间是球形的，你可能会原地旋转并指向一个随机方向。
如果房间是立方体的，根据你要寻找的目标，随机指向角落可能比指向平坦的墙壁更好。
作者发现，对于某些形状的“山谷”，指向立方体或菱形的角落（或特定边缘）比在球体上随机指向能给出更准确的坡度推测。

3. 重大主张：“高概率”保证

大多数先前的研究说：“平均而言，经过多次尝试，这种方法效果良好。”
作者说：“不，我们可以证明，几乎每一次运行该方法，它都会效果良好。”

隐喻： 想象一位天气预报员。
- 旧方法： “平均而言，50% 的时间会下雨。”（如果你需要知道今天是否会下雨，这对你没有帮助）。
- 新方法： “我们可以以 99% 的确定性保证今天不会下雨。”
该论文证明了他们的算法是可靠的。它不仅仅“平均”有效；即使在最坏的情况下，只要“迷雾”（数据中的噪声）不过于疯狂，它也能始终如一地发挥作用。

4. “任意时刻”特性

该算法是数据驱动的，并且具有任意时刻（anytime）特性。

类比： 想象你在玩一个视频游戏，你不知道有多少关。有些算法需要你告诉它们：“游戏在 100 关结束”，以便它们规划行动。
这个算法不在乎。它可以开始游戏，无论游戏在 10 关结束还是在 10,000 关结束，它都能即时适应。它不需要知道“视界”（游戏的终点）就能进行最优操作。

5. 结果中的“差距”

作者发现了一个有趣的局限性。

对于“平滑”山谷（q ≤ 2）： 他们的方法是推测坡度的绝对最佳方式。他们证明了不可能做得更好。
对于“尖锐”山谷（q > 2）： 存在一个差距。他们的方法有效，但并未达到理论极限所暗示的完美程度。
隐喻： 想象试图在干草堆里找一根针。
- 如果干草堆柔软且圆润（q ≤ 2），他们的工具能完美地找到针。
- 如果干草堆由尖锐、参差不齐的尖刺组成（q > 2），他们的工具仍然能找到针，但似乎工具本身（他们“戳”地面的方式）可能是问题所在，而不是他们的数学。他们怀疑，对于这些“尖锐”的形状，未来可能需要一种完全不同的“戳”法。

他们所做工作的总结

创造了一种推测坡度的新方法，通过基于不同几何形状（球体、菱形、立方体）的方向来“戳”地面。
证明了它几乎每次都能奏效（高概率），而不仅仅是平均有效。
使其具有灵活性，因此它可以在不知道任务将持续多久的情况下工作。
发现了一个局限：它对某些形状是完美的，但对于非常“尖锐”的形状，当前推测坡度的方法可能存在固有的缺陷，为未来的研究人员留下了一个谜题。

简而言之，他们构建了一个更可靠、更灵活且经过数学证明的“蒙眼探险家”，用于寻找复杂、多形状山谷的底部。

技术摘要：超越欧几里得几何的高概率零阶在线凸优化

问题设定
本文解决了零阶设置下的在线凸优化（OCO）问题，其中学习者仅能访问函数值而非梯度。具体设定涉及从分布 $\mu$ 中抽取的一系列随机 Lipschitz 损失函数 $f_t$ 。虽然实现 $f_t$ 不必是凸的，但假设其均值函数 $F_\mu(x) = \mathbb{E}_{f \sim \mu}[f(x)]$ 是凸的。学习者在紧凸集 $\Theta \subset \mathbb{R}^d$ 上运行，旨在最小化伪 regret：
$R_n^\mu = \sup_{u \in \Theta} \sum_{t=1}^n \left( F_\mu(x_t) - F_\mu(u) \right)$
反馈模型允许学习者在每轮查询两个点 $x_t \pm h_t \zeta_t$ 处的函数值，其中方向 $\zeta_t$ 根据锥测度从 $\ell_r$ -球的边界采样。损失函数被假定为关于 $\ell_q$ 范数是 $L$ -Lipschitz 的，且算法在“跟随正则化领导者”（FTRL）框架内采用 $\ell_p$ -强凸正则化项。

方法论
本文提出了一种自适应的、任意时间算法（SOLO FTRL），该算法利用随机化两点有限差分梯度估计器。核心方法论创新在于几何推广和概率分析：

广义梯度估计：梯度估计器是利用从 $\ell_r$ 球边界（ $\zeta \sim \partial B_d^r$ ）上的锥测度采样的方向构建的。估计器定义为：
$g_t = \frac{d}{2h_t} \left( f_t(x_t + h_t \zeta_t) - f_t(x_t - h_t \zeta_t) \right) n_r(\zeta_t)$
其中 $n_r(\zeta)$ 是 $\ell_r$ 球面在 $\zeta$ 处的单位法向量。这推广了经典的球面估计器（ $r=2$ ），并允许 $\ell_1$ 或 $\ell_\infty$ 采样几何。
矩分析与集中性：与以往依赖期望界（通常使用二阶矩）的工作不同，本分析在双范数 $\ell_{p^*}$ 中建立了梯度估计器的所有矩界。通过证明双范数平方误差序列满足序列 Bernstein 矩条件（SBM），作者推导出了时间一致的高概率集中不等式。这涉及利用 Lipschitz 函数在 $\ell_r$ 球面上的测度集中结果来控制梯度估计器的尾部行为。
自适应算法：该算法完全由数据驱动，无需知道时间范围 $n$ 或从矩分析中导出的最坏情况常数。它仅需指定几何参数（ $p, r$ ）、正则化项以及定义域大小的上界。

主要贡献

统一的高概率界：本文提供了针对所有几何组合 $p, q, r \in [1, \infty]$ 的零阶 OCO 的首个统一高概率 regret 界。这些界适用于具有凸均值的随机 Lipschitz 损失，将以往的期望保证加强为时间一致的高概率陈述。
梯度估计器矩界：作者证明了 $\ell_r$ -随机化两点梯度估计器在双范数 $\ell_{p^*}$ 中的新颖矩界。这些结果追踪了对采样几何（ $r$ ）和 Lipschitz 范数（ $q$ ）的依赖关系，确立了累积平方双范数表现为次 Gamma 过程。
与算法无关的下界：本文针对同一问题类建立了常数概率下界。这些界改进了以往的期望结果（特别是对于 $p=q=1$ ，去除了 $\sqrt{\log d}$ 因子），并通过单一构造覆盖了 $p, q \in [1, \infty]$ 的全范围。
识别 $q > 2$ 时的差距：分析揭示了当 $q > 2$ 时上下界之间存在差异。作者认为这并非证明的伪影，而是表明在此机制下，标准随机化两点梯度估计器存在内在的次优性，因为它们未能利用高 $q$ Lipschitz 函数中固有的稀疏性。

主要结果
主要理论结果（定理 2.3）指出，以至少 $1-\delta$ 的概率，regret 满足：
$R_n^\mu \leq 22R\sqrt{\nu_r} \left( \sqrt{n \Lambda_n^*(\delta)} + 11 d^{\gamma_r} \log(32n/\delta)^{3/2} \right)$
其中 $\nu_r$ 是依赖于 $L, d, p, q, r$ 的代理方差，且 $\gamma_r = (1/p - 1/r)_+$ 。项 $\sqrt{\log \log n}$ 源于该界的任意时间性质。

下界（定理 2.4）表明，对于任何两点算法，都存在一个问题实例，其 regret 至少为 $d^{(1/2 + 1/q - 1/p)_+} LR\sqrt{n}$ 量级，且具有常数概率。

意义与主张
本文声称提供了超越欧几里得设置（ $p=q=r=2$ ）的零阶在线凸优化的首个统一处理。通过将分析从期望转向高概率，结果提供了更强的、时间一致的保证，适用于自适应和任意时间设置。

该工作突出了当前方法论的一个具体局限性：对于 $q > 2$ ，标准随机化梯度估计器似乎比理论下界次优。作者指出，这种差距产生的原因是这些估计器缺乏一种机制来利用 $q > 2$ 机制中“困难”实例的稀疏性，而下界构造明确利用了这一属性。这一发现表明，该机制下的未来改进可能需要根本不同的估计器结构，而不仅仅是对现有有限差分方法的细化分析。