論文の概要: Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs

• arxiv url: http://arxiv.org/abs/2609.33760v2
• Date: Mon, 05 Oct 2026 17:10:22 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-10-06 20:36:37.911465
• Title: Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs
• Title（参考訳）: 確率入力と逆出力を用いたOracle効率の良いオンライン分類
• Abstract要約: 我々は、未知の分布と適応的に選択された損失から、i.d.コンテキストによる二項予測を考える。 観測コンテキスト毎にガウス摂動を用いた単純なFollow-the-Perturbed-Leaderアルゴリズムが,N$の専門家のクラスに対して,$widetilde O(sqrtTlog N)$ regretを達成することを示す。
• 参考スコア（独自算出の注目度）: 15.448990062628626
• License:
• Abstract: We consider binary prediction with i.i.d. contexts from an unknown distribution and adaptively chosen losses. We show that a simple Follow-the-Perturbed-Leader algorithm using a Gaussian perturbation for each observed context achieves $\widetilde O(\sqrt{T\log N})$ regret for a class of $N$ experts, while requiring one optimization-oracle call per round and no explicit enumeration of the class. For an infinite hypothesis class $\mathcal H$, the same algorithm achieves $\widetilde O(\sqrt{T\operatorname{VC}(\mathcal H)})$ regret. This resolves an open problem posed by Lazaric and Munos (2012), showing that hybrid classification is computationally as easy as statistical learning. As an application, we reduce the problem of contextual bandits with $K$ actions to classification through uniform exploration, achieving $\widetilde O(K^{2/3}T^{2/3}(\log N)^{1/3})$ regret. This matches the best known dependence on the horizon while removing the context-distribution access required by prior oracle-efficient methods.
• Abstract（参考訳）: 我々は、未知の分布と適応的に選択された損失から、i.d.コンテキストによる二項予測を考える。 観測コンテキスト毎にガウス摂動を用いた単純なFollow-the-Perturbed-Leaderアルゴリズムが$\widetilde O(\sqrt{T\log N})$ regret for a class of $N$ experts, while requires one optimization-oracle call per round and no explicit enumeration of the class。 無限の仮説クラス $\mathcal H$ に対して、同じアルゴリズムは $\widetilde O(\sqrt{T\operatorname{VC}(\mathcal H)})$ regret を達成する。 これは Lazaric と Munos (2012) が提起したオープンな問題を解き、ハイブリッド分類は統計的学習と同じくらい計算が容易であることを示す。 応用として、一様探索による分類に$K$アクションで文脈的包帯の問題を減らし、$\widetilde O(K^{2/3}T^{2/3}(\log N)^{1/3})$ regretとする。 これは、事前のオラクル効率の手法で必要とされるコンテキスト分散アクセスを取り除きながら、水平線への最もよく知られた依存と一致する。

関連論文リスト

• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
  本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。 具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
  論文  参考訳（メタデータ） (2024-08-21T01:39:42Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Metrical Task Systems with Online Machine Learned Advice [0.0]
  機械学習予測器によるオンラインアルゴリズムの強化は,予測器の精度が適切であれば,競争比を確実に低下させることができることを示す。 我々は、$n$タスク上の一様タスクシステムの特定のクラスに焦点を当て、最良の決定論的アルゴリズムは$O(n)$競争であり、最良のランダム化アルゴリズムは$O(log n)$競争である。
  論文  参考訳（メタデータ） (2020-12-17T04:56:51Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives [10.291482850329892]
  混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。 数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。 さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
  論文  参考訳（メタデータ） (2020-01-17T18:47:02Z)

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

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