論文の概要: The Price of Hidden Curvature: An $\widetildeΩ (d^{5/4} \sqrt{T})$ Lower Bound for Bandit Convex Optimization
- arxiv url: http://arxiv.org/abs/2607.18652v1
- Date: Tue, 21 Jul 2026 02:44:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-22 19:05:05.298288
- Title: The Price of Hidden Curvature: An $\widetildeΩ (d^{5/4} \sqrt{T})$ Lower Bound for Bandit Convex Optimization
- Title（参考訳）: 隠れ曲率:$\widetildeΩ (d^{5/4} \sqrt{T})$ lower bound for Bandit Convex Optimization
- Authors: Nived Rajaraman,
- Abstract要約: 我々は,$widetilde(d5/4sqrt T)$が$dsqrtT$よりも速く成長することを示す。
これは、この問題に対して$dsqrtT$よりも早く成長する最初の非自明な後悔の低い境界を示す。
- 参考スコア（独自算出の注目度）: 4.774251262663345
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We establish a $\widetildeΩ(d^{5/4}\sqrt T)$ lower bound on the minimax expected regret of stochastic bandit convex optimization of $1$-Lipschitz functions on the Euclidean ball. This presents the first nontrivial regret lower bound that grows faster than $d\sqrt{T}$ for this problem, establishing that stochastic bandit convex optimization is fundamentally harder than linear bandits. 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}_2$, each function is the scaled soft maximum of a "tube", $r^{-1} \| W^\star a^1 - \frac{r}{8\varepsilon} a^2 \|_2$ (hyperparameterized by $\varepsilon,r$), and a squared distance function, $\frac12 \| a^1 - u^\star \|_2^2 - \frac12 \| u^\star \|_2^2$. Here, $W^\star \in \mathbb{R}^{d \times d}$ is an unknown linear transformation, and $u^\star \in \mathbb{R}^{d}$ is an unknown vector which must be learned to minimize the function. Observations are informative about $u^\star$ only when the learner's action lies near the tube determined by $W^\star$, satisfying $a^2 \approx \frac{8\varepsilon}{r} W^\star a^1$: thus the learner must either find this tube without knowing $W^\star$, or spend observations learning useful directions of $W^\star$. Formally, our regret analysis exploits this tradeoff by bounding the posterior spread of Fisher information matrices obtained under an adaptive sequence of actions. Together, these ingredients give a sample complexity lower bound of $\widetildeΩ(d^{5/2}/\varepsilon^2)$ to find an $\varepsilon$-optimal action, which translates to an $\widetildeΩ (d^{5/4} \sqrt{T})$ regret lower bound. We also extend this lower bound to the unconstrained setting where the action space is $\mathbb{R}^d$.
- Abstract（参考訳）: ユークリッド球面上の1$-Lipschitz関数の確率的バンディット凸最適化を期待するミニマックス上の$\widetildeΩ(d^{5/4}\sqrt T)$下界を確立する。
これは、この問題に対して$d\sqrt{T}$よりも早く成長する最初の非自明な後悔の下界を示し、確率的帯域幅凸最適化が線形帯域幅よりも根本的に難しいことを証明している。
作用 $a = (a^1,a^2) \in \mathbb{B}^{2d}_2$ に対して、各関数は "tube", $r^{-1} \| W^\star a^1 - \frac{r}{8\varepsilon} a^2 \|_2$ ($\varepsilon,r$ でハイパラメトリック化された) のスケールされたソフトマックスであり、平方距離関数 $\frac12 \| a^1 - u^\star \|_2^2 - \frac12 \| u^\star \|_2^2- \frac12 \| u^\star \|_2^2$ である。
ここで、$W^\star \in \mathbb{R}^{d \times d}$ は未知線型変換であり、$u^\star \in \mathbb{R}^{d}$ は函数を最小化するために学習しなければならない未知ベクトルである。
a^2 \approx \frac{8\varepsilon}{r} W^\star a^1$; したがって、学習者は、$W^\star$を知らずに、または$W^\star$の有用な方向を学ぶために、このチューブを見つける必要がある。
形式的には、我々の後悔分析はこのトレードオフを利用して、適応的な行動列で得られたフィッシャー情報行列の後方拡散を束縛する。
これらの成分はともに、$\widetildeΩ(d^{5/2}/\varepsilon^2)$のサンプル複雑性下限を$\widetildeΩ(d^{5/4} \sqrt{T})$の後悔下限を$\widetildeΩ(d^{5/4} \sqrt{T})に翻訳する$\varepsilon$-Optitimalアクションを見つけるために、サンプル複雑性下限を$\widetildeΩ(d^{5/2}/\varepsilon^2)$に与える。
また、この下限は、作用空間が$\mathbb{R}^d$であるような制約のない設定にまで拡張する。
関連論文リスト
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model [26.860985092865203]
ランダム順序モデルにおいて、損失関数の多元集合が逆向きに選択されるが、一様ランダムな順序で表されるオンライン学習について検討する。
提案手法は,無作為順序モデルにおける小さめの後悔境界の確立において,スパーシフィケーションと関連する手法のパワーに光を当てるものである。
論文 参考訳（メタデータ） (2026-02-10T06:46:01Z) - Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
論文 参考訳（メタデータ） (2025-08-09T08:28:06Z) - Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards [38.53963338592248]
従来の作業に比べて,ミニマックスの後悔点の上下境界が改善した。
実験設計により導かれる新しい除去アルゴリズムを提案する。
例えば$l_p$-norm balls for $p le 1 + epsilon$の場合、$d$への依存をさらに減らすことができる。
論文 参考訳（メタデータ） (2025-06-05T09:07:26Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function
Approximation: Minimax Optimal and Instance-Dependent Regret Bounds [26.277745106128197]
本研究では,線形関数近似を用いた強化学習におけるそのような報奨の課題に対処する。
我々はまず,重み付き線形包帯に対するtextscHeavy-OFUL というアルゴリズムを設計し,インセンス依存の$T$-round regret of $tildeObig を実現した。
我々の結果は、オンライン回帰問題全般において、重くノイズを扱うことに独立した関心を持つような、新しい自己正規化集中不等式によって達成される。
論文 参考訳（メタデータ） (2023-06-12T02:56:09Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳（メタデータ） (2021-03-10T07:33:03Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。