論文の概要: Oracle-efficient Hybrid Learning with Constrained Adversaries
- arxiv url: http://arxiv.org/abs/2603.04546v1
- Date: Wed, 04 Mar 2026 19:31:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-06 22:06:10.947868
- Title: Oracle-efficient Hybrid Learning with Constrained Adversaries
- Title（参考訳）: 制約付きアドバナによるOracle効率のハイブリッドラーニング
- Authors: Princewill Okoroafor, Robert Kleinberg, Michael P. Kim,
- Abstract要約: 本稿では,ハイブリッド学習環境において,統計的最適性と計算効率を同時に達成するための一歩を踏み出した。
学習アルゴリズムの設計と解析のためのツールを多数開発しており、その中には"truncated entropy regularizer"を用いたFrank-Wolfeリダクションも含まれている。
鍵系として、アクションセットが高次元である場合のゼロサムゲームに対する平衡効率のアルゴリズムを与えるが、ペイオフ関数は低次元構造の一種を示す。
- 参考スコア（独自算出の注目度）: 6.10626521968742
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: The Hybrid Online Learning Problem, where features are drawn i.i.d. from an unknown distribution but labels are generated adversarially, is a well-motivated setting positioned between statistical and fully-adversarial online learning. Prior work has presented a dichotomy: algorithms that are statistically-optimal, but computationally intractable (Wu et al., 2023), and algorithms that are computationally-efficient (given an ERM oracle), but statistically-suboptimal (Wu et al., 2024). This paper takes a significant step towards achieving statistical optimality and computational efficiency simultaneously in the Hybrid Learning setting. To do so, we consider a structured setting, where the Adversary is constrained to pick labels from an expressive, but fixed, class of functions $R$. Our main result is a new learning algorithm, which runs efficiently given an ERM oracle and obtains regret scaling with the Rademacher complexity of a class derived from the Learner's hypothesis class $H$ and the Adversary's label class $R$. As a key corollary, we give an oracle-efficient algorithm for computing equilibria in stochastic zero-sum games when action sets may be high-dimensional but the payoff function exhibits a type of low-dimensional structure. Technically, we develop a number of tools for the design and analysis of our learning algorithm, including a novel Frank-Wolfe reduction with "truncated entropy regularizer" and a new tail bound for sums of "hybrid" martingale difference sequences.
- Abstract（参考訳）: ハイブリッドオンライン学習問題(Hybrid Online Learning Problem)は、未知の分布から特徴を引き出すが、ラベルは逆向きに生成される。
従来の研究では、統計的に最適だが計算的に難解なアルゴリズム(Wu et al , 2023)と、計算効率が良いアルゴリズム(ERMオラクルを付与する)と、統計的に最適であるアルゴリズム(Wu et al , 2024)という二分法が提案されていた。
本稿では,ハイブリッド・ラーニング・セッティングにおいて,統計的最適性と計算効率を同時に達成するための重要な一歩を踏み出した。
そのために、Adversaryが表現的だが固定的な関数のクラス$R$からラベルを選択することを制約される構造化された設定を考える。
このアルゴリズムは,学習者の仮説クラスである$H$とAdversaryのラベルクラスである$R$から派生したクラスのRademacher複雑性を用いて,後悔のスケーリングを行う。
鍵系として、アクションセットが高次元であるが、ペイオフ関数は低次元構造の一種を示すとき、確率ゼロサムゲームにおける平衡を計算するためのオラクル効率のアルゴリズムを与える。
技術的に、我々は学習アルゴリズムの設計と解析のためのツールを多数開発しており、その中には、"truncated entropy regularizer"を用いたFrank-Wolfeの削減や、"hybrid"マーチンゲール差分列の和に束縛された新しいテールなどがある。
関連論文リスト
- Efficient Uncoupled Learning Dynamics with $\ ilde{O}\!\left(T^{-1/4}\
ight)$ Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback [25.081005025442835]
両線形サドル点問題における学習アルゴリズムの終点収束について検討する。
我々の主な貢献は、非結合学習アルゴリズムの設計であり、高い確率でナッシュ平衡への最終点収束を保証する。
論文 参考訳（メタデータ） (2026-02-24T23:27:36Z) - Efficient Online Large-Margin Classification via Dual Certificates [0.2099922236065961]
双対定式化によるオフライン最大マージン問題について検討する。
得られた幾何学的洞察を用いて、オンライン設定のための原理的で効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2025-09-24T01:07:19Z) - Oracle Efficient Algorithms for Groupwise Regret [7.840453701379554]
睡眠専門家によるBlum & Lykouris(Blum & Lykouris)の簡易な修正は、外的後悔不在集団の考慮を減らし、よく理解された問題に効果的に還元できることを示す。
グループ間で一様に比較すると,従来のオンライン線形回帰アルゴリズムに比べ誤差が大幅に改善され,グループ的に反省する保証がないことがわかった。
論文 参考訳（メタデータ） (2023-10-07T02:17:22Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳（メタデータ） (2022-11-14T12:32:18Z) - On Efficient Online Imitation Learning via Classification [17.416831207557603]
分類に基づくオンライン模倣学習($textbfCOIL$)と、オラクル効率の良い後悔最小化アルゴリズムを設計するための基本的な可能性について検討する。
私たちの研究は、分類に基づくオンライン模倣学習を、重要なILセットアップとして、しっかりとした基礎に置きます。
論文 参考訳（メタデータ） (2022-09-26T17:34:36Z) - Local Stochastic Bilevel Optimization with Momentum-Based Variance
Reduction [104.41634756395545]
具体的には、まず、決定論的勾配に基づくアルゴリズムであるFedBiOを提案する。
FedBiOの複雑性は$O(epsilon-1.5)$である。
本アルゴリズムは数値実験において,他のベースラインと比較して優れた性能を示す。
論文 参考訳（メタデータ） (2022-05-03T16:40:22Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。
古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
論文 参考訳（メタデータ） (2022-02-09T19:22:34Z) - Adapting to Misspecification in Contextual Bandits [82.55565343668246]
我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。
我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2021-07-12T21:30:41Z) - Neural Active Learning with Performance Guarantees [37.16062387461106]
非パラメトリックなレシエーションにおけるストリーミング環境におけるアクティブラーニングの問題について検討する。
我々は最近提案されたニューラル・タンジェント・カーネル(NTK)近似ツールを用いて、アルゴリズムが操作する特徴空間と学習したモデルを上から計算する適切なニューラル埋め込みを構築する。
論文 参考訳（メタデータ） (2021-06-06T20:44:23Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
部分ラベル学習(Partial-label Learning, PLL)は、典型的な弱教師付き学習問題であり、各トレーニングインスタンスには、真のラベルである候補ラベルのセットが設けられている。
既存のほとんどの手法は、特定の方法で解決しなければならない制約付き最適化として精巧に設計されており、計算複雑性をビッグデータにスケールアップするボトルネックにしている。
本稿では,モデルと最適化アルゴリズムの柔軟性を備えた分類器の新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2020-02-19T08:35:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。