論文の概要: Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks

• arxiv url: http://arxiv.org/abs/2504.10598v1
• Date: Mon, 14 Apr 2025 18:00:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-16 22:11:49.266124
• Title: Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks
• Title（参考訳）: 最悪のオンライン分類を超えて、VCベースのベンチマークのためのレグレトバウンド
• Authors: Omar Montasser, Abhishek Shetty, Nikita Zhivotovskiy,
• Abstract要約: 我々は、オンラインバイナリ分類を再考し、最良クラスのバイナリ損失との競合から、緩やかなベンチマークとの競合へと焦点を移した。 我々は、小さな入力摂動に対して頑健な予測器の比較、ガウス平滑化下での良好な性能、あるいは所定の出力マージンを維持することを検討する。 我々のアルゴリズムは、VC次元とインスタンス空間の複雑さにのみ依存する後悔の保証を達成する。
• 参考スコア（独自算出の注目度）: 19.642496463491053
• License:
• Abstract: We revisit online binary classification by shifting the focus from competing with the best-in-class binary loss to competing against relaxed benchmarks that capture smoothed notions of optimality. Instead of measuring regret relative to the exact minimal binary error -- a standard approach that leads to worst-case bounds tied to the Littlestone dimension -- we consider comparing with predictors that are robust to small input perturbations, perform well under Gaussian smoothing, or maintain a prescribed output margin. Previous examples of this were primarily limited to the hinge loss. Our algorithms achieve regret guarantees that depend only on the VC dimension and the complexity of the instance space (e.g., metric entropy), and notably, they incur only an $O(\log(1/\gamma))$ dependence on the generalized margin $\gamma$. This stands in contrast to most existing regret bounds, which typically exhibit a polynomial dependence on $1/\gamma$. We complement this with matching lower bounds. Our analysis connects recent ideas from adversarial robustness and smoothed online learning.
• Abstract（参考訳）: 我々は、オンラインバイナリ分類を再考し、最良クラスのバイナリ損失との競合から、最適性のスムーズな概念を捉えた緩やかなベンチマークへの競合へと焦点を移した。 最小限のバイナリエラー(リトルストーン次元に結びついた最悪のケース境界につながる標準的なアプローチ)に対する後悔を測る代わりに、小さな入力の摂動に対して堅牢な予測器と比較し、ガウス的滑らか化の下でうまく機能するか、あるいは所定の出力マージンを維持するかを検討する。 それまでの例は、主にヒンジの喪失に限られていた。 我々のアルゴリズムは、VC次元とインスタンス空間の複雑さ(例えば、計量エントロピー)にのみ依存する後悔の保証を達成し、特に、一般化されたマージン$\gamma$への依存は$O(\log(1/\gamma))$のみである。 これは、通常1/\gamma$に多項式依存を示す、既存のほとんどの後悔境界とは対照的である。 我々はこれを下限と一致するように補完する。 我々の分析は、最近の敵の頑健さとスムーズなオンライン学習の考え方を結びつけている。

関連論文リスト

• No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization [26.415300249303748]
  本研究は, 一次アルゴリズムと双対アルゴリズムを弱適応化させることにより, 制約のサブ線形違反を回避可能であることを示す。 最初のケースでは、アルゴリズムがサブ線形後悔を保証することを示し、後者の場合、厳密な競合比を$rho/(1+rho)$とする。 この結果から,線形制約付き文脈帯域問題に対する新たな結果が得られる。
  論文  参考訳（メタデータ） (2024-05-10T16:22:33Z)
• Adversarial Contextual Bandits Go Kernelized [21.007410990554522]
  本研究では、ヒルベルト核空間に属する損失関数を組み込むことにより、逆線形文脈帯域におけるオンライン学習の問題を一般化する。 本稿では,損失関数を推定し,ほぼ最適の後悔の保証を再現するための新しい楽観的偏り推定器を提案する。
  論文  参考訳（メタデータ） (2023-10-02T19:59:39Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Data-Dependent Bounds for Online Portfolio Selection Without Lipschitzness and Smoothness [2.315156126698557]
  我々は,非Lipschitz,非滑らかな損失を伴って,オンライン凸最適化のためのデータ依存境界の最初の例を紹介する。 最悪事例におけるサブ線形後悔率を示すアルゴリズムを提案するとともに、データが「容易」である場合の対数的後悔を実現する。
  論文  参考訳（メタデータ） (2023-05-23T11:16:01Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR [13.165557713537389]
  我々は、強い適応性(SA)アルゴリズムを、動的後悔を制御するための原則的な方法と見なせることを示した。 我々は,オンラインKernel Ridge Regression(KRR)の最小限の最適性を確立する,ある罰則による新たな下限を導出する。
  論文  参考訳（メタデータ） (2021-11-22T21:52:47Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)

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

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