技术摘要：隐藏曲率的价格

问题陈述

本文探讨了随机强力凸优化（Stochastic Bandit Convex Optimization, BCO）的根本极限。在这种设定下，学习者试图在凸动作空间 $\mathcal{A} \subseteq \mathbb{R}^d$ 上最小化一个未知的凸函数 $f: \mathcal{A} \to \mathbb{R}$，通过序列化选择动作 $a_t$ 并接收噪声观测值 $r_t = f(a_t) + Z_t$，其中 $Z_t$ 是独立同分布的高斯噪声。性能指标是极小极大期望遗憾（Minimax Expected Regret），定义为 $T$ 轮内学习者的累积损失与最优损失之间的最坏情况差值。

在此项工作之前，已知针对一般 Lipschitz 凸函数的最强维度相关下界为 $\tilde{\Omega}(d\sqrt{T})$，这继承自线性强力（Linear Bandits）问题。这表明凸强力可能并不比线性强力本质上更难。本文研究了对于欧几里得球体 $\mathcal{A} = B^d_2$ 上的 1-Lipschitz 凸函数类以及无约束空间 $\mathcal{A} = \mathbb{R}^d$，这一直觉是否成立。

方法论与构造

作者构造了一个“困难”的凸函数类，旨在迫使学习隐藏几何结构与估计目标参数之间产生权衡。该构造在 $2d$ 维空间中运行，将动作拆分为 $a = (a_1, a_2) \in \mathbb{R}^d \times \mathbb{R}^d$。

困难函数类

基真函数 $f_{\theta^*}$ 由一个隐藏的线性变换 $W^* \in \mathbb{R}^{d \times d}$ 和一个目标向量 $u^* \in \mathbb{R}^d$ 参数化。该函数被定义为两个分支的缩放 Soft-maximum：

1. 管状分支（The Tube Branch）： 一个平方距离项 $\frac{1}{r} \| W^* a_1 - \frac{r}{8\varepsilon} a_2 \|^2$。仅当 $a_2 \approx \frac{8\varepsilon}{r} W^* a_1$ 时，该项才较小，这在动作空间中定义了一个狭窄的“管子”。
2. 目标分支（The Target Branch）： 一个平方距离项 $\frac{1}{2} \| a_1 - u^* \|^2 - \frac{1}{2} \| u^* \|^2$，其在 $a_1 \approx u^*$ 时达到最小。

形式化函数为：
$$f_{\theta^*}(a) = \varepsilon \cdot \text{softmax}\left( \frac{1}{r} \left\| W^* a_1 - \frac{r}{8\varepsilon} a_2 \right\|^2, \frac{1}{2} \| a_1 - u^* \|^2 - \frac{1}{2} \| u^* \|^2 \right)$$

核心难点

为了实现低遗憾，学习者必须找到一个使两个分支都较小的动作。这需要：

1. 定位 $u^*$（目标）。
2. 满足管约束 $a_2 \approx \frac{8\varepsilon}{r} W^* a_1$。

至关重要的是，除非学习者的动作位于管内，否则管状分支会主导函数值。如果学习者选择管外的动作，无论 $a_1$ 与 $u^*$ 有多接近，观测值都无法提供关于 $u^*$ 的任何信息。由于 $W^*$ 是未知的，学习者无法确定性地进入管内。他们必须要么：

• 探索 $W^*$： 花费样本来学习 $W^*$ 的方向，以预测管的位置。
• 猜测管的位置： 通过猜测 $W^* a_1$ 来尝试进入管内，但在没有先验知识的情况下，这极难实现。

这产生了一种张力：学习 $u^*$ 需要处于管内，但寻找管本身则需要学习 $W^*$。

分析框架

证明采用了带有 $W^*$ 和 $u^*$ 高斯先验的贝叶斯框架。分析依赖于两个关键的信息论量：

1. 关于 $u^*$ 的似然费舍尔信息量 ($\mathcal{I}^u_n$)： 衡量关于 $u^*$ 获取的信息。论文证明，要将 $u^*$ 的估计误差降至常数级，$\mathcal{I}^u_n$ 必须具有许多大的特征值。
2. 关于 $W^*$ 的后验费舍尔信息量 ($K_t$)： 衡量关于隐藏映射 $W^*$ 获取的信息。

核心技术贡献是 引理 2.2，它确立了这两个矩阵之间的“张力”。它表明，获取足够关于 $u^*$ 的费舍尔信息（以获得 $\mathcal{I}^u_n$ 的大特征值）的代价，受限于学习 $W^*$ 的代价。具体而言，由关于 $u^*$ 获取的信息加权的 $W^*$ 费舍尔信息包络的反矩阵的迹是受限的。这迫使学习者在能够有效学习 $u^*$ 之前，必须花费大量的样本来学习 $W^*$。

关键结果

估计下界

定理 1.1 确立了寻找 $\varepsilon$-最优动作所需的样本复杂度下界。对于在欧几里得球 $B^d_2$ 上进行 $n$ 次查询的任何自适应学习者，若 $n < c_2 \frac{d^{5/2}}{\varepsilon^2 \log(ed)}$，则存在该困难类中的一个函数，使得期望次优性至少为 $c_0 \varepsilon$。

遗憾下界

推论 1.2 将估计界转化为遗憾下界。对于 $T \geq C d^3 / \log(ed)$，$T$ 轮内的极小极大遗憾满足：
$$\mathfrak{R}^*_T(d; B^d_2) \geq c d^{5/4} \sqrt{\frac{T}{\log(ed)}}$$
通过定理 5.2 中的平滑锥扩展，该结果被推广到无约束设置 $\mathcal{A} = \mathbb{R}^d$，该扩展保持了单位球外的硬度特性。

紧致性

定理 5.1 展示了一个两阶段贝叶斯算法 (E2B)，它对于用于下界构造的特定高斯先验达到了 $\tilde{O}(d^{5/2}/\varepsilon^2)$ 的上界。这表明下界对于所构造的先验是紧致的，证实了 $d^{5/4}$ 因子并非证明技术的产物，而是此类函数的一个基本属性。

意义与主张

本文声称建立了第一个非平凡的随机强力凸优化遗憾下界，该下界严格大于线性强力的 $\tilde{\Omega}(d\sqrt{T})$。

1. 凸强力与线性强力的分离： 该结果证明，在欧几里得球上，随机强力凸优化在本质上比线性强力更难。虽然线性强力随 $d\sqrt{T}$ 缩放，但构造的凸实例随 $d^{5/4}\sqrt{T}$ 缩放。
2. 隐藏曲率的作用： 硬度源于“隐藏曲率”——即需要学习一个决定信息揭示区域（管）几何结构的隐藏线性变换 ($W^*$)。这种结构阻止了学习者使用适用于光滑或线性函数的标准线性化论证。
3. 当前上界的局限性： 论文指出，目前已知的最佳上界为 $\tilde{O}(d^{3/2}\sqrt{T})$。下界 ($d^{5/4}$) 与上界 ($d^{3/2}$) 之间的差距仍然存在。作者推测真实的极小极大速率可能是 $\tilde{\Theta}(d^{3/2}\sqrt{T})$，这表明当前的下界构造虽然对特定先验是最优的，但可能未能捕捉到一般问题的完整难度，或者需要更紧致的上界。

作者明确指出，其构造依赖于学习扰动参数 $W^*$ 与目标 $u^*$ 之间的特定权衡，并且简单的扩展（如增加更多的管或改变宽度）并不能立即产生更强的指数，这突显了这种硬度的特定几何性质。