論文の概要: Bandit Convex Optimization with Gradient Prediction Adaptivity

• arxiv url: http://arxiv.org/abs/2605.22191v1
• Date: Thu, 21 May 2026 08:57:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-22 20:14:18.541863
• Title: Bandit Convex Optimization with Gradient Prediction Adaptivity
• Title（参考訳）: 勾配予測適応性を考慮したバンド凸最適化
• Authors: Shuche Wang, Adarsh Barik, Vincent Y. F. Tan,
• Abstract要約: 本研究では, 楽観的な勾配予測が, 最悪の後悔の保証を予測順応的に改善できるかどうかを考察する。 鍵となるアイデアは、分散が勾配ノルムではなく予測誤差でスケールする、新しい分散還元勾配推定器である。 我々は、$(sqrtmathbbE[S_T])$としてスケールする情報理論の下限を確立し、最も達成可能な予測適応的後悔の基本的な特徴を提供する。
• 参考スコア（独自算出の注目度）: 56.816177049016794
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bandit convex optimization (BCO) is a fundamental online learning framework with partial feedback, where the learner observes only the loss incurred at the chosen decision point in each round. In this work, we investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner. Specifically, given gradient predictions $m_t$, we seek regret bounds that scale with the cumulative prediction error $S_T=\sum_{t=1}^T \|\nabla f_t(x_t)-m_t\|^2.$ We first establish a negative result: under the single-point feedback protocol, an unavoidable $Ω(\sqrt{T})$ regret lower bound persists even when $S_T=o(T)$, showing that the variance of gradient estimation fundamentally obscures the benefit of accurate predictions. To overcome this barrier, we propose \emph{Two-Point Variance-Reduced Optimistic Gradient Descent} (TP-VR-OPT) for the two-point feedback setting. The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm. This yields a regret bound of $O\big(\sqrt{d\,\mathbb{E}[S_T]}\big),$ where $d$ is the decision dimension. Complementing this result, we establish an information-theoretic lower bound that scales as $Ω(\sqrt{\mathbb{E}[S_T]})$, providing a fundamental characterization of the best achievable prediction-adaptive regret and showing that TP-VR-OPT is optimal up to a factor of $\sqrt d$. We further develop adaptive variants that eliminate the need for prior knowledge of $\mathbb{E}[S_T]$ or the horizon $T$, and extend our framework to non-stationary environments, establishing dynamic regret guarantees that adapt simultaneously to the cumulative prediction error and the comparator path length.
• Abstract（参考訳）: Bandit Convex Optimization (BCO) は、学習者が各ラウンドにおいて選択された決定点における損失のみを観察する、部分的なフィードバックを伴う基本的なオンライン学習フレームワークである。 本研究では, 楽観的な勾配予測が, 最悪の後悔の保証を予測順応的に改善できるかどうかを検討する。 具体的には、勾配予測$m_t$が与えられたとき、累積予測誤差$S_T=\sum_{t=1}^T \|\nabla f_t(x_t)-m_t\|^2.$が負の結果を確立する。 この障壁を克服するために,2点フィードバック設定のためのemph{Two-Point Variance-Reduced Optimistic Gradient Descent} (TP-VR-OPT)を提案する。 鍵となるアイデアは、分散が勾配ノルムではなく予測誤差でスケールする、新しい分散還元勾配推定器である。 これにより、$O\big(\sqrt{d\,\mathbb{E}[S_T]}\big)の後悔境界が得られる。 この結果を補完し、情報理論の下限を$Ω(\sqrt{\mathbb{E}[S_T]})$とスケールし、最も達成可能な予測適応的後悔の基本的な特徴を与え、TP-VR-OPTが$\sqrt d$まで最適であることを示す。 我々はさらに、$\mathbb{E}[S_T]$や水平線$T$の事前知識を不要にし、我々のフレームワークを非定常環境に拡張し、累積予測誤差とコンパレータパス長に同時に適応する動的後悔保証を確立する適応的変種を開発する。

関連論文リスト

• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  自己蒸留(英: Self-distillation, SD)とは、教師自身の予測と地道の混合で学生を訓練する過程である。 任意の予測リスクに対して、各正規化レベルにおいて、最適に混合された学生がリッジ教師に改善されることが示される。 本稿では,グリッド探索やサンプル分割,再構成なしに$star$を推定する一貫したワンショットチューニング手法を提案する。
  論文  参考訳（メタデータ） (2026-02-19T17:21:15Z)
• OrthoGrad Improves Neural Calibration [0.0]
  $perp$Gradは、過信に対処するために降下方向を制約する。 $perp$Gradは、最適化のための幾何学的な修正である。
  論文  参考訳（メタデータ） (2025-06-04T22:12:46Z)
• Decision from Suboptimal Classifiers: Excess Risk Pre- and Post-Calibration [52.70324949884702]
  バッチ二分決定における近似的後続確率を用いた余剰リスクの定量化を行う。 我々は、再校正のみが後悔のほとんどに対処する体制と、後悔が集団的損失に支配される体制を識別する。 NLP実験では、これらの量によって、より高度なポストトレーニングの期待値が運用コストに値するかどうかが分かる。
  論文  参考訳（メタデータ） (2025-03-23T10:52:36Z)
• $(\epsilon, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits [29.966828248335972]
  我々は,学習者に対して,$epsilon$と$u$が不明な場合に,後悔の最小化問題を調査する。 AdaR-UCBは、適応しない重みを帯びたケースとほぼ一致した後悔の保証を享受する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2023-10-04T17:11:15Z)
• Lazy Lagrangians with Predictions for Online Learning [24.18464455081512]
  オンライン凸最適化における時間的差分制約による一般的な問題について考察する。 Follow-The-Regularized-Leaderイテレーションと予測適応動的ステップを組み合わせることで、新しい原始双対アルゴリズムを設計する。 我々の研究は、この制約されたOCO設定のためのFTRLフレームワークを拡張し、各最先端のグレディベースのソリューションより優れています。
  論文  参考訳（メタデータ） (2022-01-08T21:49:10Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• Online nonparametric regression with Sobolev kernels [99.12817345416846]
  我々は、ソボレフ空間のクラス上の後悔の上限を$W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$ とする。 上界は minimax regret analysis で支えられ、$beta> fracd2$ または $p=infty$ の場合、これらの値は(本質的に)最適である。
  論文  参考訳（メタデータ） (2021-02-06T15:05:14Z)
• Regret-Optimal Filtering [57.51328978669528]
  後悔最適化レンズによる線形状態空間モデルにおけるフィルタの問題を検討する。 我々は, 透視推定器の誤差エネルギー推定における後悔の概念に基づいて, フィルタ設計のための新しい基準を定式化する。 3つのリッキー方程式と1つのリャプノフ方程式を解くことで、後悔と最適推定が容易に実現できることを示す。
  論文  参考訳（メタデータ） (2021-01-25T19:06:52Z)
• Leveraging Predictions in Smoothed Online Convex Optimization via Gradient-based Algorithms [18.64335888217192]
  オンライン凸最適化は、時間的変化のあるステージコストと追加のスイッチングコストで検討する。 スイッチングコストはすべてのステージにカップリングをもたらすため、長期的な予測は品質の低下に悩まされる傾向がある。 本稿では,勾配に基づくオンラインアルゴリズムReceding Horizon Inexact Gradient (RHIG)を導入し,その性能を動的後悔によって解析する。
  論文  参考訳（メタデータ） (2020-11-25T06:25:51Z)
• Nearest Neighbour Based Estimates of Gradients: Sharp Nonasymptotic Bounds and Applications [0.6445605125467573]
  勾配推定は統計学と学習理論において重要である。 ここでは古典的な回帰設定を考えると、実値の正方形可積分 r.v.$Y$ が予測される。 代替推定法で得られた値に対して, 漸近的境界が改良されることを証明した。
  論文  参考訳（メタデータ） (2020-06-26T15:19:43Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。