論文の概要: Bagging Robustly Learns VC Classes with Linear Sample Complexity

• arxiv url: http://arxiv.org/abs/2608.13514v1
• Date: Thu, 13 Aug 2026 17:36:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-14 18:29:38.618721
• Title: Bagging Robustly Learns VC Classes with Linear Sample Complexity
• Title（参考訳）: 線形サンプル複雑度でVCクラスをロバストに学習するBgging
• Abstract要約: 我々は,VC クラスが VC 次元$d$O において,サンプル複雑性の線形性に逆向きに頑健に学習可能であることを証明した。 この結果は、Breiman (1996) の古典的なバッグング(ブートストラップアグリゲーション)と堅牢な経験的リスク最小化(RERM)を組み合わせた単純な不適切なアルゴリズムによって達成される。 一般に、このオラクルモデルの学習者は、任意の数のトレーニング例を与えられたとしても、RERMオラクルへの$(dstar)$呼び出しを必要とします。
• 参考スコア（独自算出の注目度）: 12.259552039796025
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We revisit the problem of learning predictors robust to adversarial examples at test-time. We prove that VC classes are adversarially robustly learnable with sample complexity linear in the VC dimension $d$, providing an exponential improvement over the previous upper bound of Montasser, Hanneke, and Srebro (2019). Remarkably, this result is achieved with a simple improper algorithm that combines the classic heuristic bagging (bootstrap aggregation) of Breiman (1996) with robust empirical risk minimization (RERM). Our algorithm computes RERMs on $O(d^\star)$ independent bootstrap samples and outputs their majority vote, where $d^\star$ denotes the dual VC dimension. We complement this result with a lower bound showing that this is unavoidable: in general, any learner in this oracle model requires $Ω(d^\star)$ calls to an RERM oracle, even when given arbitrarily many training examples.
• Abstract（参考訳）: テスト時の敵例に頑健な予測器の学習の問題を再考する。 我々は、VCクラスがVC次元$d$の線形なサンプル複雑性で対角的に頑健に学習可能であることを証明し、以前のモンタッサー、ハネケ、スレブロ(2019)の上限よりも指数関数的に改善した。 顕著なことに、この結果はBreiman (1996) の古典的ヒューリスティック・バッグング(ブートストラップ・アグリゲーション)と堅牢な経験的リスク最小化(RERM)を組み合わせた単純な不適切なアルゴリズムで達成されている。 我々のアルゴリズムは、$O(d^\star)$独立ブートストラップサンプルを用いてRERMを計算し、その多数決を出力し、$d^\star$は二重VC次元を表す。 一般に、このオラクルモデルの学習者は、任意に多くのトレーニング例を与えられたとしても、RERMオラクルへの$Ω(d^\star)$呼び出しが必要である。

関連論文リスト

• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• 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)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• When are Local Queries Useful for Robust Learning? [25.832511407411637]
  本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。 我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。 我々は、0,1n$でハーフスペースに対してロバストな学習アルゴリズムを与え、その後、精度に縛られた敵に対して$mathbbRn$でハーフスペースに対してロバスト性を保証する。
  論文  参考訳（メタデータ） (2022-10-12T11:04:22Z)
• Robust Empirical Risk Minimization with Tolerance [24.434720137937756]
  我々は、(ロバストな)$textitempirical risk minimization$(RERM)の基本パラダイムについて研究する。 自然寛容なRERMは、$mathbbRd$を超える$gamma$-tolerantな学習VCクラスに十分であることを示す。
  論文  参考訳（メタデータ） (2022-10-02T21:26:15Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• Distributionally Robust Weighted $k$-Nearest Neighbors [21.537952410507483]
  少数のサンプルから堅牢な分類器を学ぶことは、マシンラーニングにおける重要な課題である。 本稿では, 重み付き$k$-アネレスト近傍のミニマックス分布に頑健な定式化について検討する。 我々は,この関数最適化問題を効率的に解くアルゴリズムである textttDr.k-NN を開発した。
  論文  参考訳（メタデータ） (2020-06-07T00:34:33Z)
• Proper Learning, Helly Number, and an Optimal SVM Bound [29.35254938542589]
  適切な学習アルゴリズムにより最適なサンプル複雑性を達成できるクラスを特徴付ける。 双対ヘリー数が有界であることと、$epsilon$ と $delta$ に適切な合同依存が存在することを示せる。
  論文  参考訳（メタデータ） (2020-05-24T18:11:57Z)

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

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