論文の概要: An $Ω(T^{3/4})$ lower bound for projection-free online learning with linear minimization oracles
- arxiv url: http://arxiv.org/abs/2610.37845v1
- Date: Tue, 27 Oct 2026 18:53:23 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-31 05:25:12.317978
- Title: An $Ω(T^{3/4})$ lower bound for projection-free online learning with linear minimization oracles
- Title（参考訳）: 1$Ω(T^{3/4})$ lower bound for projection-free online learning with linear minimization oracles
- Abstract要約: 本研究は,決定集合を扱うための線形最小化オーラクルを用いたプロジェクションフリーオンライン学習アルゴリズムについて考察する。
我々は任意のプロジェクションフリーアルゴリズムに対して、万能最悪の後悔の少ない$(T3/4 m-1/4)を証明した。
- 参考スコア（独自算出の注目度）: 7.622384395929584
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This work considers projection-free online learning algorithms with linear minimization oracles for handling the decision set. For Online Frank--Wolfe (OFW), regret upper bounds were already known for specific OFW tunings [Hazan and Kale, 2012, Hazan, 2016] which scaled as $T^{3/4}$ (where $T$ is the horizon length). However, it remained an open question whether the regret of all OFW tunings scaled as $T^{3/4}$. We answer that question, proving a universal worst-case regret lower bound $Ω(T^{3/4} m^{-1/4})$ for any projection-free algorithm that makes at most $m$ linear minimization oracle calls per round. The analysis suggests an extended OFW to resort to multiple linear optimizations per round, for which we prove a regret upper bound $O(\max \{ T^{3/4} m^{-1/4}, \sqrt{T} \})$.
- Abstract（参考訳）: 本研究は,決定集合を扱うための線形最小化オーラクルを用いたプロジェクションフリーオンライン学習アルゴリズムについて考察する。
Online Frank-Wolfe (OFW)では、OFWの特定のチューニング(Hazan and Kale, 2012 Hazan, 2016)ですでに、T^{3/4}$(T$は地平線長)とスケールしていた。
しかし、すべてのOW調律の後悔が$T^{3/4}$にスケールしたかどうかについては未解決のままである。
我々は、任意の射影自由アルゴリズムに対して、一ラウンドあたりの線形最小化のオラクル呼び出しを少なくとも$m$とする、普遍的な最悪の後悔の少ない$Ω(T^{3/4} m^{-1/4})を証明して、その質問に答える。
この分析により、OWは1ラウンドあたりの複数の線形最適化に頼り、ここでは後悔の上限である$O(\max \{ T^{3/4} m^{-1/4}, \sqrt{T} \})$を証明している。
関連論文リスト
- Minimax-Optimal Small-Loss Bounds for Online Linear Optimisation on $\ell_p$ Balls [1.4975436239088316]
Follow-the-regularized-leaderアルゴリズムは、損失シーケンス毎に、$T$や$_T$を知らずに、後悔する$O_pを達成する。
平均がゼロ座標を持たない i.d. 損失に対しては、期待される後悔の正確な$log T$係数を計算する。
論文 参考訳（メタデータ） (2026-10-26T18:15:38Z) - Geometry-Dependent Bounds for Online Non-Monotone DR-Submodular Maximization [55.29259818039367]
凸閉集合上の逆オンライン非負の非単調DR-部分モジュラ函数について検討する。
学習者は、目的を観察する前に各アクションを学習し、後から最高の固定アクションと競合する。
定数対物列は、最適に多くの1次クエリでオフラインの$(4/9-varepsilon)$近似を生成する。
論文 参考訳（メタデータ） (2026-09-30T18:26:29Z) - Lower Bounds for Linear-Oracle Online Learning [0.0]
ワイベルらは固定係数法は不可能であると推測した。
我々はそれらの予想を証明し、その下限をオラクルのみのモデルにおける決定論的学習者すべてに拡張する。
最新の勾配の非ゼロ係数を持つ1回の固定スケジュールの場合、第2の構成は、発行されたクエリごとにユニークな最小値を持つ少なくとも3ドルLDT3/4/4$の後悔を与える。
論文 参考訳（メタデータ） (2026-09-29T18:34:43Z) - Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization [55.29259818039367]
我々は, オンライン凸最適化において, 実現可能な集合へのアクセスが正確な線形最適化オラクルに制限された場合に達成可能な後悔を特徴づける。
コンベックス$G$-Lipschitzの損失に対して、直径は最大$D$、合計$Q$オークルコールは$Q$、厳格な制限はラウンド当たり$B$である。
論文 参考訳（メタデータ） (2026-09-23T22:25:52Z) - Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。
スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文 参考訳（メタデータ） (2026-09-07T01:38:41Z) - Swap Regret Minimization Through Response-Based Approachability [66.39400409563976]
オンライン最適化において,スワップ後悔という異なる概念を最小化することの問題点を考察する。
我々は、一般凸集合に対して$O(d3/2 sqrtT)$リニアスワップ後悔を保証し、集合が中央対称であるときに$O(d sqrtT)$を保証し、より単純で効率的なアルゴリズムを開発する。
論文 参考訳（メタデータ） (2026-02-05T23:43:25Z) - A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees [58.59385794080679]
本稿では,後悔を遅延非依存の学習項と遅延誘発のドリフト項に分解する連続時間モデルを提案する。
バンディット凸最適化では,最先端の1次数に適合する遅延依存項を用いて,既存の残差境界を大幅に改善する。
論文 参考訳（メタデータ） (2026-02-02T18:17:34Z) - Exploiting Curvature in Online Convex Optimization with Delayed Feedback [6.390468088226495]
曲面損失と遅延フィードバックを用いたオンライン凸最適化問題について検討する。
次数$minsigma_maxln T, sqrtd_mathrmtot$を後悔する規則化リーダの変種を提案する。
次に、exp-concave損失を検討し、適応的な学習率チューニングで遅延を処理するためにOnline Newton Stepアルゴリズムを拡張した。
論文 参考訳（メタデータ） (2025-06-09T09:49:54Z) - Non-stationary Projection-free Online Learning with Dynamic and Adaptive
Regret Guarantees [36.746745619968024]
本研究では,非定常プロジェクションフリーオンライン学習について検討し,動的後悔と適応的後悔を選択して評価を行った。
我々の結果は、プロジェクションフリーオンライン学習における最初の一般的な動的後悔境界であり、既存の$mathcalO(T3/4)$static regretを復元することができる。
本稿では,$tildemathcalO(tau3/4)$ アダプティブリフレッシュバウンドを長さ$tauの任意の間隔で達成するためのプロジェクションフリーな手法を提案する。
論文 参考訳（メタデータ） (2023-05-19T15:02:10Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。