論文の概要: Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization

• arxiv url: http://arxiv.org/abs/2610.00254v1
• Date: Wed, 23 Sep 2026 22:25:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:23.584217
• Title: Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization
• Title（参考訳）: Sharp Oracle-Regretがプロジェクションフリーのオンライン凸最適化のためのトレードオフを発表
• Abstract要約: 我々は, オンライン凸最適化において, 実現可能な集合へのアクセスが正確な線形最適化オラクルに制限された場合に達成可能な後悔を特徴づける。 コンベックス$G$-Lipschitzの損失に対して、直径は最大$D$、合計$Q$オークルコールは$Q$、厳格な制限はラウンド当たり$B$である。
• 参考スコア（独自算出の注目度）: 55.29259818039367
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We characterize the regret attainable in online convex optimization when access to the feasible set is limited to an exact linear optimization oracle. The learner is given an inscribed ball and a diameter bound and must remain feasible on every consistent instance. For convex $G$-Lipschitz losses, diameter at most $D$, a total allowance of $Q$ oracle calls, and a strict limit of $B$ calls per round, the dimension-free minimax expected regret is $Θ(GD\max\{\sqrt T,T/(1+\min\{Q,BT\})^{1/4}\})$. The lower bound applies to arbitrary randomized learners. Universal feasibility first forces each action into the hull of the supplied ball and the preceding oracle replies. A fixed-body construction then couples fresh phase directions to a shared simplex, making useful replies costly repeatedly even though all losses have a common minimizer. A counted approximate-gradient method with interleaved blocks attains the matching rate. Total-budget and strict per-round guarantees follow as special cases, including the $T^{3/4}$ rate with one call per round and the quadratic total budget needed for $\sqrt T$ regret. For prescribed smoothness $β$, an analytic construction yields a curvature-dependent lower bound and identifies the threshold above which the general characterization remains sharp.
• Abstract（参考訳）: 我々は, オンライン凸最適化において, 実現可能な集合へのアクセスが正確な線形最適化オラクルに制限された場合に達成可能な後悔を特徴づける。 学習者には、入力されたボールと直径の制限が与えられ、一貫したすべてのインスタンスで実行可能でなければならない。 凸$G$-Lipschitz損失、最大$D$、合計$Q$oracleコールの許容値、およびラウンド当たり$B$コールの厳密な制限に対して、次元自由最小値期待の後悔は$(GD\max\{\sqrt T,T/(1+\min\{Q,BT\})^{1/4}\})$である。 下限は任意のランダム化学習者に適用される。 普遍的な実現性は、まず各アクションを供給されたボールの船体に強制し、それ以前のオラクルの応答を応答させる。 固定体構造は、新しい位相方向を共有単純度に結合し、すべての損失が共通の最小化器を有するにもかかわらず、有用な応答を低コストで繰り返し行う。 インターリーブブロックを持つカウントされた近似勾配法は、マッチングレートを達成する。 総予算と1ラウンド当たりの厳格な保証は特別なケースとして扱われ、例えば1ラウンドにつき1コールのT^{3/4}$レートと、後悔する$\sqrt T$に対して必要な2つの予算がある。 所定の滑らか度$β$に対して、解析的な構成は曲率に依存した下界をもたらし、一般的な特徴が鋭いままであるしきい値を特定する。

関連論文リスト

• 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)
• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。 スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
  論文  参考訳（メタデータ） (2026-09-07T01:38:41Z)
• Parameter-Free Dynamic Regret for Online Convex Optimization under Heavy-Tailed Noise [55.29259818039367]
  重音下での非定常環境におけるオンライン凸最適化(OCO)について検討した。 ブロック長の幾何プール上に再起動したAdaGrad専門家を組み合わせたパラメータフリーアルゴリズムである textbfHT-PAder を提案する。 有限分散(p=2$)の特別な場合であっても、HT-パダーはパラメータフリーのミニマックスの普遍的後悔保証を提供する。
  論文  参考訳（メタデータ） (2026-07-29T15:58:18Z)
• Online Convex Optimization with a Separation Oracle [10.225358400539719]
  本稿では,オンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。 我々のアルゴリズムは、$widetildeO(sqrtdT + kappa d)$の償却バウンダリを達成し、ラウンド毎に$widetildeO(1)の呼び出ししか必要としない。
  論文  参考訳（メタデータ） (2024-10-03T13:35:08Z)
• Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
  我々は,個別かつ不可逆な意思決定を対象とするオンライン学習と最適化の問題を定義した。 各期間において、意思決定者は、オープンする施設を選択し、それぞれの成功に関する情報を受け取り、将来の決定を導くために分類モデルを更新する。 目的は,多数の施設を対象とする地平線を特徴とし,カバー対象を反映するチャンス制約の下で施設開口を最小化することである。
  論文  参考訳（メタデータ） (2024-06-20T23:00:25Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)

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

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