跳转至

Minimax optimality for sequential gradient-free minimization of smooth functions and their derivatives

作者: Théo Paquier, Alexandre B Tsybakov, François Portier, Mohammadreza M Kalan
主题: 非参数 / 半参数
相关性: 7/10
链接: https://arxiv.org/abs/2609.18678

一、领域脉络与小综述

这个方向是什么

本文研究的根本问题是：在只知道函数属于某个 Hölder 光滑类、且只能获得带噪点观测（而非梯度信息）的条件下，序贯地选择查询点以最小化函数（或其 k 阶偏导数）的全局最小值，其最优的累积遗憾（cumulative regret）速率是多少？ 这是一个典型的"零阶随机优化"（zeroth-order stochastic optimization）问题，处于非参数估计、bandit 优化与 minimax 决策理论的交叉点。该方向的成熟度较高——针对 k=0（直接最小化函数本身）的情形已有大量工作，但精确的 minimax 常数与对数因子尚未完全闭合，且对"最小化导数"这一推广情形的系统性研究是空缺。

发展脉络（history）

  • 奠基工作（1950s–1990s）：Kiefer and Wolfowitz (1952) 提出经典的 Kiefer-Wolfowitz 随机逼近算法，开启了带噪梯度-free 优化的研究。Fabian (1967) 与 Polyak and Tsybakov (1990) 在渐近最优性上取得进展，后者给出了在光滑函数类上的渐近有效速率。
  • 非参数估计视角（1980s–2000s）：Stone (1982) 建立了局部多项式估计（LPE）在 Hölder 类上的最优收敛速率，为本文的估计器选择提供了理论基础。Tsybakov (1990) 与 Dippon (2003) 将局部多项式方法引入随机优化，建立了遗憾与估计误差之间的联系。
  • Bandit 与高维拓展（2010s–2020s）：Auer et al. (2007) 与 Kleinberg et al. (2008) 在连续臂 bandit 框架下给出了 Lipschitz 情形的遗憾界；Bubeck et al. (2011) 将结果推广到一般维度并设计了多项式时间算法。Wang et al. (2019) 给出了简单遗憾的上下界，但下界不尖锐（差一个对数因子）。Liu et al. (2021) 提出了改进的 bandit 算法，遗憾界为 T^{(β+d)/(2β+d)} log(T)^{(6β+d)/(2(2β+d))}，但未证明其最优性。Akhavan et al. (2020, 2024a,b) 利用高阶光滑性改进了常数，但同样未闭合 minimax 速率。
  • 本文的位置：作者将 k=0 的已知结果推广到任意 k 阶导数（0 ≤ k < β），给出了精确的非渐近 minimax 速率 T^{(β+d+k)/(2β+d)} log(T)^{(β-k)/(2β+d)}，并证明：(1) 被动设计（i.i.d. 查询点）即可达到最优；(2) 存在多项式时间算法匹配该速率。这填补了 Wang et al. (2019) 与 Liu et al. (2021) 之间的 gap。

子线索聚类

  1. 随机逼近与渐近最优性（Kiefer-Wolfowitz 传统）：关注渐近正态性与最优常数，代表为 Fabian (1967)、Polyak and Tsybakov (1990)、Mokkadem and Pelletier (2007)。本文不涉及渐近常数，聚焦非渐近速率。
  2. 非参数回归与局部多项式估计（Stone 传统）：关注估计器在 Hölder 类上的 sup-norm 风险，代表为 Stone (1982)、Tsybakov (2009)。本文的 Proposition 1 直接建立在此之上，但需要处理"估计器最小化器"而非估计器本身的风险。
  3. Bandit 优化与遗憾界（在线学习传统）：关注累积遗憾的上下界，代表为 Auer et al. (2007)、Kleinberg et al. (2008)、Bubeck et al. (2011)、Wang et al. (2019)、Liu et al. (2021)。本文的核心贡献在此线索上——给出了精确的 minimax 速率并闭合了 gap。
  4. 计算可行性（算法设计线索）：关注如何将统计最优的估计器转化为多项式时间算法。代表为 Bubeck et al. (2011) 的 X-armed bandit 算法。本文第 4 节通过随机网格离散化实现这一点。

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

  1. 被动 vs 序贯设计的价值：当只知道函数属于 Hölder 类而无额外结构时，序贯选择查询点能否带来速率上的优势？本文的回答是否——被动设计已最优。这是一个重要的概念性结论，因为它将问题从"在线优化"降维为"非参数估计 + 全局最小化"。
  2. 导数最小化的额外难度：最小化 k 阶导数（而非函数本身）是否改变 minimax 速率？本文给出的速率 T^{(β+d+k)/(2β+d)} 显示，k 越大速率越慢（指数分子增大），反映了估计高阶导数的额外代价。
  3. 对数因子的精确指数：已知结果中遗憾界含 log(T) 的幂次不精确（如 Liu et al. 的 (6β+d)/(2(2β+d)) 与本文的 (β-k)/(2β+d)），本文给出了精确指数。
  4. 计算与统计的权衡：全局最小化 LPE 在计算上不可行，随机网格离散化是否会损失速率？本文证明通过适当选择网格大小可以避免损失。

⚠️ 作者的 framing（这是作者的说法）

作者将本文定位为"闭合 k=0 情形下已知上下界之间的 gap，并将结果推广到 k 阶导数"。具体而言，作者声称： - 对 k=0，此前最好的上界（Liu et al. 2021）与下界（Wang et al. 2019 的局部版本）之间存在对数因子的 gap，本文给出了精确的 minimax 速率。 - 对 k>0，此前没有任何针对导数最小化的 minimax 分析，本文是第一个。 - 作者强调"被动设计即最优"这一结论，暗示序贯设计在纯 Hölder 光滑性假设下没有理论价值。

值得研究者注意的 framing 盲点： - 作者将"被动设计"定义为 i.i.d. 均匀采样，但没有讨论其他被动设计（如拉丁超立方体、低差异序列）是否可能更好。这是一个潜在的扩展点。 - 作者假设噪声是条件 sub-Gaussian，但没有讨论重尾噪声或异方差噪声的情形。 - 作者没有讨论自适应地选择带宽的可能性——LPE 的带宽 h 是预先固定的，若允许数据依赖的带宽选择，速率是否可改进？ - 作者没有讨论高维情形（d 随 T 增长）或函数类的其他光滑性度量（如 Besov 类，Singh 2021 声称处理但证明有误）。

张力

  • 未见明显对立引用：作者引用的工作之间没有直接矛盾。但存在一个隐含张力：Wang et al. (2019) 的简单遗憾下界为 T^{-β/(2β+d)}（不含对数因子），而本文的累积遗憾下界为 T^{(β+d+k)/(2β+d)} log(T)^{(β-k)/(2β+d)}。简单遗憾与累积遗憾之间的转换（乘以 T）暗示简单遗憾的最优速率为 T^{-(β-k)/(2β+d)} log(T)^{(β-k)/(2β+d)}，比 Wang et al. 的下界多一个对数因子。这意味着 Wang et al. 的下界可能不紧，或者简单遗憾与累积遗憾的转换不是 tight 的。这是一个值得深挖的技术点。

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

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

参数 / 目标量（estimand）： - β > 0：Hölder 光滑性参数（实数，不一定是整数）。ℓ = ⌊β⌋ 是最大整数严格小于 β。 - L > 0：Hölder 常数（定义在 (2) 式中，控制函数值及其直到 ℓ 阶导数的上界，以及 ℓ 阶导数的 Hölder 连续性）。 - k ∈ ℕ：目标导数的阶数，满足 0 ≤ k < β。α ∈ ℕᵈ 是多重指标，‖α‖₁ = k，目标函数是 f⁽ᵅ⁾(x) = ∂ᵏf / ∂x₁^α₁ … ∂x_d^α_d。 - f⁽ᵅ⁾* = min{x∈[0,1]ᵈ} f⁽ᵅ⁾(x)：目标导数的最小值（未知，要估计/逼近）。 - T：总查询步数（样本量）。 - d：输入维度。

随机变量 / 样本： - Xᵢ ∈ [0,1]ᵈ：第 i 步的查询点。在被动设计下，Xᵢ ~ U([0,1]ᵈ) i.i.d.。 - Yᵢ = f(Xᵢ) + ξᵢ：第 i 步的观测值（带噪函数值，不是梯度）。 - ξᵢ：条件 sub-Gaussian 噪声（Definition 1），满足 E[exp(tξᵢ)|Xᵢ] ≤ exp(σ²t²/2)，σ > 0 已知。 - ẑᵢ：第 i 步输出的估计量（对 f⁽ᵅ⁾ 最小化点的估计），是 (X_t, Y_t)_{t=1}^i 的可测函数。 - Π_T：所有序贯策略（查询点选择规则）的集合。

关键量： - 简单遗憾（simple regret）：E_f[f⁽ᵅ⁾(ẑT)] − f⁽ᵅ⁾，即最终估计点处导数与全局最小值的差距。 - 累积遗憾（cumulative regret）：R_T(f) = Σ_{i=1}^T (E_f[f⁽ᵅ⁾(ẑᵢ)] − f⁽ᵅ⁾_)，即每一步遗憾的总和。 - LPE(ℓ)：阶数为 ℓ 的局部多项式估计器，用于估计 f⁽ᵅ⁾(x)。其定义见 (7)-(8) 式，通过加权最小二乘拟合局部多项式得到。 - 带宽 h：LPE 的平滑参数，本文选择 h = a(log(T)/T)^{1/(2β+d)}，a > 0 为常数。

模型： - 函数类：f ∈ Σ(β, L)，即 f 是 ℓ 次连续可微，且所有 ℓ 阶偏导数满足 Hölder 条件（指数 β − ℓ），所有低阶导数有界（见 (2) 式）。 - 观测模型：Yᵢ = f(Xᵢ) + ξᵢ，ξᵢ 条件 sub-Gaussian。 - 查询策略：Xᵢ 可以是序贯的（依赖历史），也可以是 i.i.d. 的（被动）。

第二步：最小内核

核心命题（k=0, d=1, 被动设计）：

假设 f: [0,1] → ℝ 是 β-Hölder 函数（β > 0），观测 Yᵢ = f(Xᵢ) + ξᵢ，Xᵢ ~ U[0,1] i.i.d.，ξᵢ 是 sub-Gaussian 噪声。令 f̂T 为基于前 T 个观测的局部多项式估计器（阶数 ℓ = ⌊β⌋，带宽 h = a(log(T)/T)^{1/(2β+1)}），并令 x̂_T ∈ argmin{x∈[0,1]} f̂_T(x)。则：

E_f[f(x̂_T) − min f] ≤ C (log(T)/T)^{β/(2β+1)}。

为什么这个命题是核心？

  1. 它揭示了问题的本质结构：最小化一个带噪函数的全局最小值，其难度由"估计误差"和"逼近误差"共同决定。LPE 的 sup-norm 风险是 (log(T)/T)^{β/(2β+1)}（这是 Stone 1982 的经典结果），而"最小化器的函数值误差"被 sup-norm 误差控制（因为 f(x̂T) − min f ≤ 2‖f̂_T − f‖∞）。因此，估计问题的最优速率直接转化为优化问题的最优速率。

  2. 它展示了被动设计的充分性：i.i.d. 均匀采样已经足够达到最优速率。序贯策略的核心优势在于"利用历史信息集中采样"——但在纯 Hölder 光滑性假设下，最优采样密度是均匀的（因为函数在任意位置都可能有最小值），所以序贯策略没有额外信息可以利用。

  3. 它指出了证明的技术难点：控制 E[‖f̂T − f‖∞] 需要处理 sup-norm 风险，这涉及经验过程理论（empirical process theory）和局部多项式估计的偏差-方差权衡。本文的 Proposition 1 给出了非渐近的 sup-norm 界，这是整个证明的基石。

推广到 k 阶导数：

当目标变为最小化 f⁽ᵅ⁾（k 阶偏导数）时，核心命题变为：

E_f[f⁽ᵅ⁾(x̂_T) − min f⁽ᵅ⁾] ≤ C (log(T)/T)^{(β-k)/(2β+d)}。

为什么指数从 β/(2β+d) 变为 (β-k)/(2β+d)？

  • 估计 f⁽ᵅ⁾ 的 sup-norm 风险是 (log(T)/T)^{(β-k)/(2β+d)}（因为估计导数比估计函数本身更难，收敛速率更慢）。
  • 累积遗憾的指数为 (β+d+k)/(2β+d)，这是因为累积遗憾 = T × 简单遗憾，而简单遗憾的指数为 (β-k)/(2β+d)，所以 T × T^{-(β-k)/(2β+d)} = T^{(β+d+k)/(2β+d)}。

这个最小内核揭示了什么？

本文的核心数学贡献是：将"零阶随机优化"问题分解为"非参数估计"（LPE 的 sup-norm 风险）和"离散化逼近"（随机网格覆盖）两个子问题，并证明这两个子问题的困难程度恰好决定了优化的 minimax 速率。被动设计之所以最优，是因为在 Hölder 类上，均匀采样是最优的实验设计；序贯策略无法利用历史信息来改进采样密度。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：在只知道目标函数属于 β-Hölder 类、只能获得带噪函数值（无梯度）的条件下，序贯最小化函数的 k 阶偏导数（0 ≤ k < β）的 minimax 累积遗憾速率。
  2. 核心工具 / 方法：局部多项式估计器（LPE）+ 被动 i.i.d. 均匀采样 + 随机网格离散化；上界通过 LPE 的 sup-norm 风险界和网格覆盖论证建立，下界通过 Fano 不等式和构造硬函数类建立。
  3. 主要结论：minimax 累积遗憾速率为 T^{(β+d+k)/(2β+d)} log(T)^{(β-k)/(2β+d)}，被动设计即可达到最优，且存在多项式时间算法匹配该速率。

关键设定与假设

  • 函数类：Σ(β, L)，即 ℓ = ⌊β⌋ 次连续可微，所有 ℓ 阶偏导数满足 Hölder 条件（指数 β − ℓ），所有低阶导数有界（(2) 式）。相比已有工作（如 Liu et al. 2021 只考虑 β ≤ 1 或 Lipschitz 情形），本文允许任意 β > 0。
  • 噪声：条件 sub-Gaussian（Definition 1），比高斯噪声更一般，但比重尾噪声更严格。σ_ξ 已知。
  • 查询策略：允许任意序贯策略（Π_T），但上界在被动设计下证明。
  • 目标：最小化 f⁽ᵅ⁾，其中 α 是固定多重指标，‖α‖₁ = k。要求 k < β（否则导数不存在或不可控）。
  • 带宽选择：h = a(log(T)/T)^{1/(2β+d)}，a > 0 为常数。这是 LPE 的最优带宽选择，平衡偏差与方差。

相比已有工作的变化： - 相比 Wang et al. (2019)：本文给出了精确的对数因子指数（(β-k)/(2β+d)），而 Wang et al. 的下界为 T^{-β/(2β+d)}（不含对数因子），且只处理 k=0。 - 相比 Liu et al. (2021)：本文的遗憾界更紧（对数因子指数更小），且推广到 k > 0。 - 相比 Akhavan et al. (2024a,b)：本文不假设凸性或强凸性，只依赖 Hölder 光滑性。

主要结果

定理 1（上界，被动设计）：在 Assumptions 1–3 下，对任意 f ∈ Σ(β, L)，LPE 的最小化器 ẑT 满足 sup{f∈Σ(β,L)} E_f[f⁽ᵅ⁾(ẑ_T) − min f⁽ᵅ⁾] ≤ C (log(T)/T)^{(β-k)/(2β+d)}， 且累积遗憾 ≤ C T^{(β+d+k)/(2β+d)} log(T)^{(β-k)/(2β+d)}。

定理 3（下界，任意序贯策略）：对任意序贯策略和估计器序列， R*_T ≥ C T^{(β+d+k)/(2β+d)} log(T)^{(β-k)/(2β+d)}。

定理 2（多项式时间算法）：通过随机网格离散化（每步取 V_j = ⌊j^γ⌋+1 个辅助点，γ 满足特定条件），可以在多项式时间内达到定理 1 的速率。

证明路线：

  1. 上界：
  2. Step 1：将遗憾分解为估计误差：f⁽ᵅ⁾(x̂T) − min f⁽ᵅ⁾ ≤ 2‖f̂_T − f⁽ᵅ⁾‖∞。
  3. Step 2：证明 LPE 的 sup-norm 风险界（Proposition 1）：E[‖f̂T − f⁽ᵅ⁾‖∞²] ≤ C (log(T)/T)^{(β-k)/(2β+d)}。这需要控制 LPE 的偏差（Taylor 展开 + Hölder 条件）和方差（经验过程 + Bernstein 不等式）。
  4. Step 3：对每个 i，用 Proposition 1 控制 E[f⁽ᵅ⁾(ẑᵢ) − min f⁽ᵅ⁾]，然后求和得到累积遗憾。

  5. Step 4：对于多项式时间版本，用随机网格覆盖 [0,1]ᵈ，证明网格最小化器的函数值与全局最小化器的差距可以被控制（Proposition 2）。

  6. 下界：

  7. Step 1：构造硬函数类：将 [0,1]ᵈ 划分为 N 个小立方体，在每个立方体上放置一个"凸起"函数（类似 bump function），使得不同函数的 f⁽ᵅ⁾ 最小值出现在不同位置。
  8. Step 2：将问题转化为 N 元假设检验问题：如果算法能以高概率找到正确的立方体，则遗憾很小；否则遗憾很大。
  9. Step 3：用 Fano 不等式（Lemma 6）控制假设检验的最小错误概率。关键在于计算 KL 散度：由于噪声是 sub-Gaussian，KL 散度正比于信号幅度 a² 乘以观测数。
  10. Step 4：选择信号幅度 a 使得 KL 散度有界（≤ (log N)/8），从而错误概率 ≥ 1/8。此时遗憾 ≥ a × T × (1/8)，其中 a = a₀(log(T)/T)^{(β-k)/(2β+d)}。

技术技巧：

  • 经验过程理论：控制 sup-norm 风险时，使用 Bernstein 不等式和 chaining 论证（Lemma 5），处理随机设计下 LPE 的方差项。
  • Fano 不等式：下界证明中，使用 Fano 不等式将 minimax 遗憾与假设检验错误概率联系起来。关键技巧是构造"局部"硬函数类，使得 KL 散度可控。
  • 随机网格离散化：多项式时间算法中，用随机网格代替全局最小化，通过选择网格大小平衡逼近误差和计算复杂度。
  • 条件 sub-Gaussian 噪声：允许噪声依赖于 Xᵢ，但要求条件矩生成函数有界，这比独立同分布噪声更灵活。

真实例子与应用

本文为纯理论论文，无真实数据例子或模拟实验。 作者没有提供任何数值实验来验证定理的常数或有限样本行为。这是一个明显的局限——读者无法判断常数 C 的大小，也无法评估算法在中等样本量下的实际表现。

四、开放问题

  1. 常数优化：定理 1 和定理 3 中的常数 C 未明确给出，且可能相差很大。是否存在锐化常数的方法（如通过更精细的局部多项式选择或自适应带宽）？这扎根于定理 1 和定理 3 的陈述本身。

  2. 自适应带宽：本文的带宽 h 是预先固定的（依赖于 β 和 d）。若允许数据依赖的带宽选择（如 Lepski 方法），是否能在不知道 β 的情况下达到自适应 minimax 速率？这扎根于 Proposition 1 的证明中对 h 的固定选择。

  3. 高维情形：本文的速率随 d 指数恶化（因为常数 C 可能依赖 d）。当 d 随 T 增长时，速率如何变化？是否存在维数灾难的不可避免性证明，或者可以通过结构假设（如稀疏性、低秩性）获得更好的速率？这扎根于定理 1 中常数对 d 的依赖。

  4. 重尾噪声：Assumption 2 要求 sub-Gaussian 噪声。若噪声只有有限矩（如 E|ξ|^p < ∞），速率会如何变化？这扎根于 Assumption 2 的具体陈述。

  5. 异方差噪声：Assumption 2 允许噪声条件于 Xᵢ 是 sub-Gaussian，但方差 σ² 是常数。若噪声方差依赖于 X（如 Var(ξ|X) = σ²(X)），最优采样密度是否仍是均匀的？这扎根于 Assumption 2 的常数 σ 假设。

  6. 主动 vs 被动设计的精细比较：本文证明被动设计达到 minimax 速率，但没有排除序贯策略在常数上优于被动设计的可能性。是否存在序贯策略在常数上严格优于被动设计？这扎根于定理 1 和定理 3 的常数未匹配这一事实。

  7. Besov 类的推广：Singh (2021) 声称处理 Besov 类但证明有误。本文的方法能否推广到 Besov 类（或更一般的逼近空间）？这扎根于引言中对 Singh (2021) 的批评。

提醒：若要确认上述某条是否是真 gap，建议去读同一子领域近期约 5 篇论文（如 Akhavan et al. 2024a,b、Lattimore 2026、以及 bandit 优化方向的 NeurIPS/COLT 近三年论文）的引言——如果多篇都指向同一问题，说明是共识性 gap；如果互相矛盾，则可能是机会。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论