揭示凸优化中隐藏曲率的代价，证明其比线性带宽优化更难。
The Price of Hidden Curvature: Improved Lower Bounds for Bandit Convex Optimization
- 构造一类隐藏曲率的凸函数，迫使学习者先探测几何结构
- 在 n≥d^{10/3} 时，最小最大损失下界达 Ω(d^{4/3}√n)
- 适用于研究带宽优化理论下界的学者
本文针对 d 维欧氏球上 1-利普希茨凸函数的随机带宽凸优化问题，建立了改进的极小极大期望遗憾下界。当时间跨度 n≥d^{10/3} 时，证明了 Ω(d^{4/3}√n) 的下界，首次得到超越线性带宽优化中 d√n 依赖性的非平凡结果，表明随机带宽凸优化本质上比线性带宽优化更困难。当 d²≤n≤d^{10/3} 时，获得 Ω(√d·n^{3/4}) 的下界，与 Flaxman 等人（2005）算法的遗憾性能匹配，确立了该算法在此区间的最优性。所构造的难题函数在 2d 维空间中定义为：动作 a=(a¹,a²) 时，函数为缩放后的软最大值，涉及一个‘管状’项 r⁻¹‖W⋆a¹ - (r/(8ε))a²‖ 与平方距离项 ½‖a¹-u⋆‖² - ½‖u⋆‖²。其中 u⋆∈ℝᵈ 为未知最优解，W⋆∈ℝ^{d×d} 隐含可观察曲率的区域。只有在动作接近隐藏管状结构 a²≈(8ε/r)W⋆a¹ 时，才能获取关于 u⋆ 的有效信息；远离该区域时，管状项会掩盖二次项。因此学习者必须付出代价以揭示由 W⋆ 编码的几何结构，才能利用曲率定位最优解。形式化此权衡后，得到寻找 ε-最优动作的样本复杂度下界为 Ω( d^{5/2}/ε² ∧ d²/ε⁴ )，最终导出 Ω( d^{4/3}√n ∧ √d·n^{3/4} ) 的遗憾下界。
原文摘要 · Abstract (English)
We establish improved lower bounds on the minimax expected regret of stochastic bandit convex optimization for $1$-Lipschitz functions on the $d$-dimensional Euclidean ball. For time horizons $n\ge d^{10/3}$, we prove a lower bound of $Ω(d^{4/3}\sqrt{n})$, the first nontrivial bound that exceeds the $d\sqrt{n}$ dependence of linear bandits, showing that stochastic bandit convex optimization is fundamentally harder than linear bandits. For $d^2\le n\le d^{10/3}$, we obtain a lower bound of $Ω(\sqrt{d}n^{3/4})$, matching the regret of the algorithm of Flaxman et al. (2005), establishing its optimality in this regime. The hard class of convex functions we construct takes the following form in dimension $2d$: for an action $a=(a^1,a^2)\in \mathbb{B}^{2d}$, each function is the scaled soft maximum of a "tube", $r^{-1}\|W^\star a^1-\frac{r}{8\varepsilon}a^2 \|$ (hyperparameterized by $\varepsilon,r$), and a squared distance function, $\frac12\|a^1-u^\star\|^2-\frac12\|u^\star\|^2$. Here $u^\star\in\mathbb{R}^d$ is the unknown target determining the minimizer, while $W^\star\in\mathbb{R}^{d\times d}$ hides the region in which the quadratic curvature is observable. Indeed, observations reveal substantial information about $u^\star$ only when the learner acts near the hidden tube $a^2\approx \frac{8\varepsilon}{r}W^\star a^1$; away from it, the tube branch masks the quadratic branch. Thus the learner must pay to uncover the geometry encoded by $W^\star$ before it can effectively exploit the curvature that identifies $u^\star$. Formalizing this tradeoff yields a sample complexity lower bound of $Ω(\frac{d^{5/2}}{\varepsilon^2}\wedge\frac{d^2}{\varepsilon^4})$ for finding an $\varepsilon$-optimal action, and ultimately the $Ω(d^{4/3}\sqrt{n}\wedge\sqrt{d}n^{3/4})$ regret lower bound. The proof was developed by GPT-5.5 Pro and GPT-5.6 Sol Pro under the authors' guidance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。