Gradient-free stochastic optimization of derivatives under strong convexity

作者: Arya Akhavan, Sirine Louati, Alexandre B. Tsybakov
主题: 统计计算 / 算法
相关性: 6/10
链接: https://arxiv.org/abs/2607.07249

---

一、领域脉络与小综述

这个方向是什么

这个子方向是无梯度（零阶）随机优化，研究的是：在只能对未知函数进行带噪声的查询（即只能获得函数值，无法获得梯度）的条件下，如何通过序贯地选择查询点来逼近该函数的最小值。其核心统计问题是：在给定的查询预算下，优化误差（函数值与真最小值之差）能以多快的速率衰减？这个速率如何依赖于问题的维度、目标函数的平滑性（Hölder 正则性）、强凸性以及噪声水平？当前，对于直接优化目标函数本身（即 k=0 的情况），其 minimax 最优速率已经基本清晰。本文则将问题推广到一个更难的设定：优化目标函数的 k 阶偏导数，而只能查询原函数本身。

发展脉络（history）

1. 奠基工作：随机逼近与无梯度优化。该领域可追溯到 Kiefer & Wolfowitz (1952) 的经典工作，他们提出了用有限差分近似梯度的随机逼近方法。Nemirovski & Yudin (1983) 的专著系统化了随机扰动方案。Polyak & Tsybakov (1990) 则建立了强凸函数在无梯度设定下的 minimax 最优速率，这是 k=0 情况下的一个里程碑。

2. 主要进展：从 Lipschitz 到高阶光滑性。后续工作主要沿着两条线展开：

   • 一般凸/强凸函数：Flaxman et al. (2004) 开创了 bandit 凸优化，通过单点反馈估计梯度。Ghadimi & Lan (2013) 和 Duchi et al. (2015) 等则建立了更一般的随机和非随机设定下的收敛保证。Shamir (2013, 2017) 给出了信息论下界，揭示了维度依赖的本质。
   • 利用高阶光滑性：Bach & Perchet (2016) 首次证明，对于无限可微函数，可以利用高阶光滑性来改善无梯度优化的速率。Akhavan et al. (2020) 和 Novitskii & Gasnikov (2021) 进一步将这一思想推广到强凸函数，得到了目前 k=0 情况下已知最好的维度指数 2 - 1/β（对于 β>2）。Akhavan et al. (2024b) 和 Yu et al. (2024) 则分别改进了分析和算法。

3. 当前 Frontier 与本文位置：上述所有工作都聚焦于 k=0 的情况。本文首次将无梯度优化问题推广到 k≥1，即优化目标函数的导数。作者明确指出：“To the best of our knowledge, optimizing functions from indirect observations was not considered, despite its relevance...”（Section 1）。本文填补了这一空白，建立了该问题在 N 上的 minimax 最优速率 N^{-(β-1)/(β+k)}，并给出了一个达到该速率（除维度因子外）的算法。

子线索聚类

1. 无梯度优化算法与上界：这是最核心的线索，包括 Kiefer & Wolfowitz (1952), Polyak & Tsybakov (1990), Flaxman et al. (2004), Ghadimi & Lan (2013), Duchi et al. (2015), Nesterov & Spokoiny (2017), Bach & Perchet (2016), Akhavan et al. (2020, 2021, 2024b), Novitskii & Gasnikov (2021), Yu et al. (2024)。这些工作提出并分析了各种基于核估计或随机扰动的梯度近似方法，并给出了非渐近收敛上界。

2. 无梯度优化的信息论下界：这条线索旨在刻画问题的固有难度，包括 Shamir (2013, 2017), Jamieson et al. (2012)。他们通过构造难以区分的函数对，建立了 minimax 下界，证明了某些速率是不可超越的。本文的下界证明（Theorem 5.2）也属于这一线索。

3. 非参数统计中的间接观测问题：这条线索为本文的问题提供了统计视角。包括密度解卷积（Carroll & Hall, 1988; Butucea & Tsybakov, 2008; Lepski & Willer, 2019）和线性逆问题（Cavalier, 2008; Bissantz & Holzmann, 2008）。这些工作研究的是从间接观测中估计整个函数（或其导数），而非优化其最小值。Wieczorek (2010) 研究了一维解卷积模型中密度导数的众数估计，是本文最直接的非参数统计相关文献。

4. 被动（非序贯）优化：Tsybakov (1990a, 1990b), Nazin et al. (1989, 1992), Krishnamurthy & Yin (2022), Akhavan et al. (2024a) 研究的是观测点固定（i.i.d.）的被动方案，其最优速率通常比主动（序贯）方案慢得多，且维度依赖是指数级的。本文强调其主动方案的优势。

这个方向在追问的核心问题

1. 最优速率：对于给定的目标函数类（如强凸、Hölder 光滑），优化误差的 minimax 最优速率是什么？它如何依赖于查询次数 N、维度 d 和光滑参数 β？
2. 维度诅咒：无梯度优化中，维度 d 对速率的影响有多大？能否通过利用高阶光滑性来缓解维度诅咒？
3. 主动 vs. 被动：主动（序贯）选择查询点相比被动（i.i.d.）方案能带来多大的速率提升？
4. 间接观测的代价：当目标函数是原函数的导数时，优化难度如何变化？速率如何退化？

⚠️ 作者的 framing

作者将问题框架化为“无梯度优化”与“非参数统计中逆问题”的交叉点。他们声称：“To the best of our knowledge, no prior work provides a minimax analysis for optimizing higher order derivatives using noisy zero-order queries under a sequential observation scheme.” 这使得本文成为该子问题的“显然的下一步”。

• 被淡化/回避的竞争路线：作者将本文与“被动方案”（如 Tsybakov 1990a）和“密度解卷积”（Wieczorek 2010）进行了对比，强调主动方案的优势。他们淡化了这些被动方案中可能存在的、针对特定结构（如可加模型）的更优速率。作者在 Section 7 中承认，对于可加模型，其另一篇工作（Akhavan & Tsybakov, 2025）表明无梯度优化中并无增益，这与非参数估计中的结论形成对比。
• 值得研究者去查的问题：作者在引言中提到了“linear inverse problems in nonparametric regression”（Bissantz & Holzmann, 2008; Cavalier, 2008），但并未深入讨论。这些文献中关于“估计导数”的 minimax 速率（通常是指数级维度依赖）与本文的“优化导数”的速率（多项式维度依赖）之间的巨大差异，是一个值得深究的张力点。为什么“估计”和“优化”在间接观测下会有如此不同的维度行为？这是否是主动查询带来的根本性改变？

张力

未见明显对立引用。所有被引工作基本都沿着“给定假设，推导上界/下界”的范式，彼此之间没有在相同设定下得出矛盾结论。主要的“张力”体现在不同设定（如主动 vs. 被动，k=0 vs. k≥1）之间的速率差异，这恰恰是本文要揭示的。

二、最核心、最简单的例子 / 数学问题

第一步：把符号、模型、可观测数据交代清楚

• 符号：

  • g: ℝ^d → ℝ：未知的底层函数，研究者只能对其进行带噪声的查询。
  • f(x) = ∂_j^k g(x)：目标函数，是 g 沿第 j 个坐标方向的 k 阶偏导数。我们要最小化 f。
  • x* = argmin_{x∈Θ} f(x)：f 在紧凸集 Θ ⊂ ℝ^d 上的唯一最小值点（由 f 的强凸性保证）。
  • f* = f(x*)：f 的最小值。
  • N：总查询预算（oracle budget）。
  • T：算法迭代步数。本文中，N = 2dT，即每步对每个坐标方向进行 2 次查询。
  • x_t：第 t 步迭代的当前点。
  • η_t：第 t 步的步长。
  • h：平滑参数（带宽），用于控制梯度估计的偏差-方差权衡。
  • ξ_t：第 t 次查询的噪声，满足 E[ξ_t^2] ≤ σ^2。
  • β：Hölder 光滑参数，g ∈ F_{β+k}(L) 意味着 g 的 ⌊β+k⌋ 阶导数 Hölder 连续，指数为 β+k - ⌊β+k⌋。
  • α：f 的强凸参数。
  • K_k(u), K_1(v)：用于梯度估计的核函数，定义在 [-1/2, 1/2] 上，满足特定的矩条件。

• 模型：

  • 数据生成机制：在每一步 t，算法选择一个查询点 z_t ∈ ℝ^d，并观测到带噪声的函数值 y_t = g(z_t) + ξ_t。噪声 ξ_t 可以是随机的，但不要求零均值或独立（仅要求二阶矩有界）。
  • 目标函数类：g 属于一个精心定义的函数类 F'_{α,β,k}(...)，该函数类要求：
    1. g 具有 β+k 阶 Hölder 光滑性。
    2. f = ∂_j^k g 在 Θ 上是 α-强凸的。
    3. f 和 g 的梯度满足有界性和 Lipschitz 条件。
  • 要估的对象：f 的最小值点 x* 和最小值 f*。我们关心的是优化误差 E[f(ẋ_N) - f*]。

• 可观测数据：

  • 可观测：研究者可以主动、序贯地选择查询点 z_t，并观测到带噪声的函数值 y_t = g(z_t) + ξ_t。这是唯一的信息来源。
  • 不可观测/潜在：
    • 函数 g 本身是未知的。
    • 目标函数 f = ∂_j^k g 的值和梯度是不可直接观测的。研究者必须从 g 的噪声观测中间接推断 f 的信息。
    • 噪声 ξ_t 的具体实现是不可观测的。
    • 函数 g 的高阶导数也是不可观测的，只能通过假设（Hölder 光滑性）来约束其行为。

第二步：讲最小内核

本文的核心思想可以用一个最简特例来理解：d=1（一维），k=1（优化一阶导数），β=2（g 二阶光滑，即 g' 一阶光滑）。

• 设定：

  • d=1，j=1（唯一坐标方向）。Θ = [a, b] ⊂ ℝ 是一个区间。
  • g: ℝ → ℝ 是未知函数，满足 g ∈ F_3(L)（即 g''' 有界），且 f(x) = g'(x) 是 α-强凸的。
  • 我们只能查询 g(x) + ξ，目标是找到 f 的最小值点 x*，即 g'(x*) = 0 且 g''(x*) > 0。

• 核心困难：我们无法直接计算 f'(x) = g''(x)。我们只能通过 g 的带噪声值来估计它。

• 核心想法（核估计 + 随机梯度下降）：

  1. 梯度估计：为了估计 f'(x_t) = g''(x_t)，我们使用一个基于核的估计器。在 d=1, k=1 时，估计器（公式 9）简化为： ğ_t = [K_1(U_t) * K_1(V_t) / (2h^2)] * (y_t^+ - y_t^-) 其中：
     • U_t, V_t 是独立均匀分布在 [-1/2, 1/2] 上的随机变量。
     • 查询点为 z_t^+ = x_t + hU_t + hV_t 和 z_t^- = x_t + hU_t - hV_t。
     • y_t^± = g(z_t^±) + ξ_t^± 是观测值。
     • K_1(u) 是一个核函数，满足 ∫ K_1(u) du = 0 和 ∫ u K_1(u) du = 1。
  2. 直觉：这个估计器通过两个随机扰动 hU_t 和 hV_t 来“探测” g 的二阶导数。hU_t 的扰动用于提取 g 的一阶导数信息（通过 K_1 核），而 hV_t 的扰动则用于提取 g 的二阶导数信息（通过另一个 K_1 核）。整个构造类似于一个随机化的二阶有限差分。
  3. 偏差-方差权衡：
     • 偏差：由于 g 是光滑的，这个估计器是有偏的。Lemma 5.1 证明，偏差的阶为 O(h^{β-1}) = O(h)（因为 β=2）。h 越小，偏差越小。
     • 方差：估计器除以了 h^{k+1} = h^2，因此方差会随着 h 的减小而急剧增大。Lemma 5.2 证明，方差的阶为 O(h^{-2(k+1)}) = O(h^{-4})。
  4. 优化算法：使用投影随机梯度下降（公式 5）： x_{t+1} = Π_Θ( x_t - η_t * ğ_t ) 其中 η_t 是步长。
  5. 最终速率：通过选择合适的 h 来平衡偏差和方差，可以得到优化误差的速率。在 d=1, k=1, β=2 的特例下，Theorem 5.1 给出的上界为 O(N^{-(β-1)/(β+k)}) = O(N^{-1/3})。这个速率比直接优化 g（k=0）时的 O(N^{-1/2}) 要慢，这正是因为间接观测（优化导数）带来了额外的困难。

• 这个特例揭示了什么：

  • 问题的本质：这是一个偏差-方差权衡问题。h 是控制这个权衡的旋钮。
  • 为什么难：为了估计 f 的梯度，我们需要从 g 的观测中提取高阶导数信息，这导致了估计器方差随 h 的幂次爆炸。为了控制方差，我们不能让 h 太小，但这又会引入偏差。最优的 h 必须平衡两者。
  • 速率退化的原因：与 k=0 相比，k=1 时方差项中的 h 指数从 -2 变为 -4，导致最优 h 更大，最终速率更慢。这量化了“优化导数”的额外代价。

三、这篇论文做了什么

三句话

1. 研究了什么问题：在只能对未知函数 g 进行带噪声的序贯查询的条件下，最小化其 k 阶偏导数 f = ∂_j^k g 的随机优化问题。
2. 核心工具/方法：提出了一种基于两个核函数（K_k 和 K_1）的梯度估计器，并将其嵌入到投影随机梯度下降算法中。该估计器通过精心设计的随机扰动和核函数的矩条件，从 g 的观测值中无偏（渐近地）提取 ∇f 的信息。
3. 主要结论：建立了该问题的 minimax 最优速率 N^{-(β-1)/(β+k)}（在 N 上），并给出了一个达到该速率（除一个维度因子 d^{(2β+k-1)/(β+k)} 外）的算法。

关键设定与假设

在第二节最小记号的基础上，补全完整设定：

• 函数类 F'_{α,β,k}(L, L_f, G, G_g, \bar{L})：这是本文的核心假设集合，比第二节的简单例子更精细。它要求：

  • (a) g ∈ F_{β+k}(L)：g 具有 β+k 阶 Hölder 光滑性。这是利用高阶光滑性加速优化的基础。
  • (b) f 在 Θ 上 α-强凸。这是保证梯度下降算法线性收敛（在无偏梯度下）的关键，也是下界构造中分离两个假设的基础。
  • (c) ∇f 是 L_f-Lipschitz 的。用于将参数误差转化为优化误差（公式 4）。
  • (d) ||∇f(x)|| ≤ G 在 Θ 上。用于控制梯度估计器的二阶矩。
  • (e) ||∇g(x)|| ≤ G_g 在 Θ_+（Θ 的单位扩张）上。用于控制梯度估计器的方差。
  • (f) ∇g 是 \bar{L}-Lipschitz 的。同样用于控制方差。
  • (g) f 的最小值点 x* 在 Θ 的内部。这是使用一阶最优性条件 ∇f(x*)=0 的前提。
  • 相比已有文献的强化/放宽：相比 k=0 的文献（如 Akhavan et al. 2020），本文增加了对 g 的梯度（G_g, \bar{L}）的假设，这是分析 k≥1 时梯度估计器方差所必需的。这些假设是合理的，因为要估计 f 的梯度，需要控制 g 的二阶行为。

• 核函数的矩条件：这是本文方法的核心技术细节。

  • K_k 满足：∫ u^a K_k(u) du = 0 for a ∈ {0, ..., ℓ*} \ {k}, 且 ∫ u^k K_k(u) du = k!。这保证了在泰勒展开中，只有 k 阶导数项被保留，其余低阶项被消除。
  • K_1 满足：∫ v^b K_1(v) dv = 0 for b=0 和奇数 b ≥ 3, 且 ∫ v K_1(v) dv = 1。这保证了在泰勒展开中，只有一阶导数项被保留，其余奇数阶项（三阶、五阶等）被消除。
  • 相比已有文献的强化/放宽：这种双核构造是本文的创新，专门为估计混合偏导 ∂_l ∂_j^k g 而设计。K_k 负责提取 k 阶导数，K_1 负责提取一阶导数。这与 k=0 时只用单个核（如 Bach & Perchet 2016）不同。

主要结果

• Theorem 5.1 (Upper Bound)：

  • 陈述：对于算法（5），在合适的参数选择下（η_t = γ/(t+t_0), h = κ T^{-1/(2(β+k))}），经过 T 步（N=2dT 次查询），优化误差的上界为： sup_{g∈F'} E[f(x_T) - f(x*)] ≤ C d^{(2β+k-1)/(β+k)} N^{-(β-1)/(β+k)}
  • 直觉：速率 N^{-(β-1)/(β+k)} 由偏差-方差权衡决定。h 的最优选择 ∝ T^{-1/(2(β+k))} 使得偏差项 O(d h^{2(β-1)}) 和方差项 O(d h^{-2(k+1)}/T) 达到平衡，均为 O(d T^{-(β-1)/(β+k)})。维度因子 d^{(2β+k-1)/(β+k)} 来源于 d 个坐标方向上的方差累积和偏差的维度依赖。
  • 必要条件：β ≥ 2，γ ≥ 4/α，t_0 ≥ αγ。这些条件保证了递归不等式（20）中的系数 q ≥ 2，从而可以应用 Lemma 6.1。
  • 解决的技术难点：如何同时控制偏差（Lemma 5.1）和方差（Lemma 5.2），并将它们嵌入到随机梯度下降的收敛分析中（Lemma 6.1 的递归不等式）。

• Theorem 5.2 (Lower Bound)：

  • 陈述：对于任何序贯算法和任何基于 N 次查询的估计器，存在一个常数 C，使得： inf_{alg Φ} sup_{g∈F'} E[f(ẋ_N) - f(x*)] ≥ C N^{-(β-1)/(β+k)}
  • 直觉：通过构造两个难以区分的函数 g_+ 和 g_-，它们的 k 阶导数 f_+ 和 f_- 的最小值点相距足够远。任何算法都无法可靠地判断当前观测来自哪个函数，因此必然产生一个与分离距离成正比的优化误差。这个分离距离被设计为 ∝ N^{-(β-1)/(β+k)}。
  • 必要条件：β ≥ 2，噪声为高斯（用于计算 KL 散度）。函数类 F' 中的参数需要满足一定的下界（如 L > L_0），以保证构造的函数属于该类。
  • 解决的技术难点：构造一个函数对 (g_+, g_-)，使得：
    1. 它们都属于函数类 F'（满足所有光滑性、强凸性、有界性条件）。
    2. 它们的 k 阶导数 f_± 的最小值点 x*_± 充分分离。
    3. 从 g_± 的噪声观测中，这两个函数在统计上难以区分（KL 散度有界）。这需要精巧地设计一个“凸函数 + 小 bump”的构造，其中 bump 的幅度和尺度被精确控制。

证明路线与技术技巧

• 整体路线（以上界证明为例）：

  1. 梯度估计：设计基于双核的梯度估计器 ğ_t（公式 9）。
  2. 偏差分析：通过泰勒展开和核函数的矩条件，证明 ğ_t 的条件期望与真实梯度 ∇f(x_t) 的偏差为 O(h^{β-1})（Lemma 5.1）。
  3. 方差分析：利用 g 和 f 的光滑性及有界性假设，证明 ğ_t 的条件二阶矩有上界 O(1 + d h^{2(β-1)} + d h^{-2(k+1)})（Lemma 5.2）。
  4. 递归不等式：利用强凸性，将一步迭代的期望参数误差 E[||x_{t+1} - x*||^2] 与上一步的误差联系起来，得到一个形如 u_{t+1} ≤ (1 - q/(t+t_0)) u_t + A/(t+t_0) + B/(t+t_0)^2 的递归不等式（公式 33）。其中 A 项来自偏差的平方，B 项来自方差。
  5. 解递归不等式：使用一个非渐近版本的 Chung's Lemma（Lemma 6.1）来求解这个递归不等式，得到 E[||x_T - x*||^2] 的上界。
  6. 转换为优化误差：利用 ∇f 的 Lipschitz 连续性（公式 4），将参数误差上界转换为优化误差上界 E[f(x_T) - f(x*)]。
  7. 选择最优 h：通过最小化优化误差上界中关于 h 的项（偏差 ∝ d h^{2(β-1)} 和方差 ∝ d h^{-2(k+1)}/T），得到最优 h ∝ T^{-1/(2(β+k))}，并代入得到最终速率。

• 关键跳跃点：

  • Lemma 5.1 的证明：关键在于利用核函数的矩条件（7）和（8）来消除泰勒展开中除了 (a,b) = (k,1) 项之外的所有项。这需要验证 (k,1) 项确实在求和范围内（即 k+1 ≤ ℓ*），这由 β > 1 保证。
  • Lemma 5.2 的证明：关键在于将 g(x+s) - g(x-s) 的方差分解为 P+Q+R 三部分，并分别利用 ∇g 的 Lipschitz 性和有界性进行控制。这展示了如何将 g 的局部光滑性转化为梯度估计器方差的显式上界。
  • Lemma 6.1 的证明：这是分析的核心技术工具。它处理了递归不等式中两个不同阶数的强迫项（A/(t+t_0) 和 B/(t+t_0)^2）。A 项（来自偏差）导致一个不随 T 衰减的残差 2A/q，而 B 项（来自方差）则随 T 衰减。这个引理精确刻画了偏差对最终收敛误差的永久性影响。

• 技术技巧点名：

  • 核估计 (Kernel Estimation)：用于从带噪声的函数值中估计梯度。具体地，使用了两个核函数来分别提取 k 阶和一阶导数信息。
  • 泰勒展开与矩条件 (Taylor Expansion & Moment Conditions)：用于分析核估计器的偏差，通过精心设计的矩条件消除低阶项。
  • Chung 型递归不等式 (Chung-type Recursion)：用于分析带衰减步长的随机梯度下降的收敛性。本文使用了其非渐近版本（Lemma 6.1），并处理了多个强迫项。
  • Minimax 下界构造 (Minimax Lower Bound Construction)：通过构造两个难以区分的假设（函数对），并利用 KL 散度、Pinsker 不等式和 Le Cam 方法，将优化误差下界与假设的分离距离联系起来。
  • 隐函数定理 (Implicit Function Theorem)：在下界证明中，用于分析扰动后函数 f_± 的最小值点 x*_± 如何随扰动参数变化，从而精确控制两个最小值点的分离距离。

真实例子与应用

本文为纯理论，无实证例子。

🔎 结论是否比证明窄

• 维度依赖：Theorem 5.1 的上界包含一个维度因子 d^{(2β+k-1)/(β+k)}，而 Theorem 5.2 的下界与 d 无关。作者在 Section 7 中明确承认：“Whether the exponent (2β+k-1)/(β+k) here is sharp is an open question.” 这意味着上界在 d 上可能不是紧的，结论比证明所保证的要弱。这是一个重要的开放问题。
• β ≥ 2 的限制：Theorem 5.1 和 5.2 都要求 β ≥ 2。作者在 Section 4 中假设 β > 1，但主要结果却限制在 β ≥ 2。对于 1 < β < 2 的情况，结论是否成立？作者没有讨论。这可能是因为下界证明中需要 β ≥ 2 来保证 h^{β-2} 项不发散（见公式 52 附近），而上界分析可能也需要类似的条件。
• 单坐标偏导数的限制：本文只考虑了沿单一坐标方向 j 的 k 阶偏导数 f = ∂_j^k g。作者在 Section 7 中指出，推广到混合偏导数需要“substantially different gradient estimators”。因此，结论的适用范围比“优化任意 k 阶导数”这个更泛化的 claim 要窄。

四、开放问题

1. 维度依赖的紧性：上界中的维度因子 d^{(2β+k-1)/(β+k)} 是否紧？能否构造一个下界证明，使其也包含一个 d 的依赖项？或者能否改进算法，消除或降低这个维度因子？扎根点：Section 7, “Whether the exponent (2β+k-1)/(β+k) here is sharp is an open question.”

2. 弱化强凸性假设：能否将 f 的强凸性假设放松为一般的凸性？这将改变问题的几何结构，需要重新审视上界和下界的证明技术。扎根点：Section 7, “relaxing the strong convexity assumption on f to mere convexity.”

3. 单点反馈模型：本文使用的是两点反馈（每步每个坐标查询两次）。如果每步只能查询一次（单点反馈），最优速率会如何变化？这会引入额外的偏差-方差权衡。扎根点：Section 7, “Studying one-point oracle models... would introduce additional bias-variance trade-offs.”

4. 自适应程序：本文的算法需要知道光滑参数 β 来选择最优的 h。能否设计一个自适应的程序，在不预先知道 β 的情况下达到相同的 minimax 最优速率？扎根点：Section 7, “develop adaptive procedures that do not require prior knowledge of the smoothness parameter β.”

---

Maintained by 陈星宇 · Homepage · Source on GitHub

评论