論文の概要: Optimal High-Probability Regret for Online Convex Optimization with Two-Point Bandit Feedback
- arxiv url: http://arxiv.org/abs/2603.25029v1
- Date: Thu, 26 Mar 2026 04:52:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-27 20:52:48.10767
- Title: Optimal High-Probability Regret for Online Convex Optimization with Two-Point Bandit Feedback
- Title（参考訳）: 2点帯域フィードバックを用いたオンライン凸最適化のための最適高確率レギュレータ
- Authors: Haishan Ye,
- Abstract要約: 本稿では,2点帯域幅フィードバックによるオンライン凸最適化の問題点について考察する。
O(d(log T + log (1/))/)$$$$$-strongly convex loss。
- 参考スコア（独自算出の注目度）: 17.238068736229014
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of Online Convex Optimization (OCO) with two-point bandit feedback in an adversarial environment. In this setting, a player attempts to minimize a sequence of adversarially generated convex loss functions, while only observing the value of each function at two points. While it is well-known that two-point feedback allows for gradient estimation, achieving tight high-probability regret bounds for strongly convex functions still remained open as highlighted by \citet{agarwal2010optimal}. The primary challenge lies in the heavy-tailed nature of bandit gradient estimators, which makes standard concentration analysis difficult. In this paper, we resolve this open challenge by providing the first high-probability regret bound of $O(d(\log T + \log(1/δ))/μ)$ for $μ$-strongly convex losses. Our result is minimax optimal with respect to both the time horizon $T$ and the dimension $d$.
- Abstract（参考訳）: 本稿では,オンライン凸最適化 (OCO) の問題について考察する。
この設定では、プレイヤーは、各関数の値を2点でのみ観察しながら、逆発生した凸損失関数の列を最小化しようとする。
2点フィードバックが勾配推定を可能にすることはよく知られているが、強い凸関数に対する厳密な高確率な後悔境界を達成することは、 \citet{agarwal2010optimal} が強調したように、まだ開のままである。
主な課題は、標準濃度分析を困難にしているバンディット勾配推定器の重い尾を持つ性質にある。
本稿では、このオープンチャレンジを、$O(d(\log T + \log(1/δ))/μ)$$$μ$-strongly convex loss の最初の高確率後悔境界を提供することによって解決する。
我々の結果は、時間的地平線$T$と次元$d$の両方に対して最適である。
関連論文リスト
- Online Min-Max Optimization: From Individual Regrets to Cumulative Saddle Points [9.267347813727824]
本研究では,コンベックス・コンケーブ設定を超える様々な性能対策の下で,累積サドル点に基づくmin-max最適化のオンラインバージョンについて検討する。
個々人の後悔と相反する後悔の動的な概念について、両面のPolyak-ojasiewicz (PL)条件の下で境界を導出する。
論文 参考訳（メタデータ） (2026-02-11T06:29:37Z) - Non-stationary Bandit Convex Optimization: A Comprehensive Study [28.086802754034828]
Bandit Convex Optimizationは、シーケンシャルな意思決定問題のクラスである。
非定常環境でこの問題を研究する。
非定常性の標準的な3つの基準の下で、後悔を最小限に抑えることを目指しています。
論文 参考訳（メタデータ） (2025-06-03T15:18:41Z) - Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。