論文の概要: Boosting with List-Decodable Codes

• arxiv url: http://arxiv.org/abs/2607.05791v1
• Date: Tue, 07 Jul 2026 03:34:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-08 21:24:51.380988
• Title: Boosting with List-Decodable Codes
• Title（参考訳）: List-Decodable Codesによるブースティング
• Abstract要約: 我々は,$O(log frac1)$-XORの下で閉じた任意のクラスに対して,新しいブースティングアルゴリズムを提案する。 我々のアルゴリズムは、ブーピングとリストデコダブルコードの間の新しい単純な接続から生まれる。
• 参考スコア（独自算出の注目度）: 4.3070965805068875
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Boosting is a fundamental technique for generically improving the accuracy of learning algorithms (Schapire 1989). Existing boosting algorithms construct a strong learner using $O(\log(\frac{1}ε)/γ^2)$ calls to a $γ$-advantage weak learner, and this round complexity is known to be optimal for generic boosters that succeed on all concept classes (Freund 1995). We show that this lower bound can be circumvented for concept classes that satisfy a mild closure property. Specifically, we present a new boosting algorithm that, for any class $\mathcal{F}$ closed under $O(\log \frac{1}γ)$-XOR, strong learns $\mathcal{F}$ using $O(\log \frac{1}ε)$ calls to a $γ$-advantage weak learner and a single batch of $\tilde{O}(\log(\frac{1}ε)/γ^2)$ additional samples. Our algorithm arises from a new and simple connection between boosting and list-decodable codes. Viewing the target function as a message, we run the weak learner on its encoding and view the resulting weak hypothesis as a corrupted codeword. Feeding this corrupted codeword to a list decoder, we obtain a small list of candidate hypotheses, at least one of which is a strong hypothesis for the original function. Using additional samples, we identify and output this strong hypothesis.
• Abstract（参考訳）: ブースティングは、学習アルゴリズムの精度を総合的に改善するための基本的な技術である(Schapire 1989)。 既存のブースティングアルゴリズムは、$O(\log(\frac{1}ε)/γ^2)$コールを使って強力な学習者を構築する。 この下界は、軽度の閉包性を満たす概念クラスに対して回避可能であることを示す。 具体的には、任意のクラス$\mathcal{F}$を$O(\log \frac{1}γ)$-XORで閉じた場合には、$O(\log \frac{1}ε)$で$\mathcal{F}$を学習する。 我々のアルゴリズムは、ブーピングとリストデコダブルコードの間の新しい単純な接続から生まれる。 ターゲット関数をメッセージとして見ていると、そのエンコーディング上で弱い学習者を実行し、結果として弱い仮説を破損したコードワードとみなす。 この破損したコードワードをリストデコーダに入力すると、候補仮説の小さなリストが得られ、そのうちの少なくとも1つは元の関数に対する強い仮説である。 追加のサンプルを用いて、この強い仮説を特定し、出力する。

関連論文リスト

• The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
  スムースブースターは任意の例にあまり重みを付けない分布を生成する。 もともとは耐雑音性のために導入されたが、そのようなブースターは微分プライバシー、軽度、量子学習理論にも応用されている。
  論文  参考訳（メタデータ） (2024-09-17T23:09:25Z)
• The Cost of Parallelizing Boosting [1.9235143628887907]
  本研究は,学習用弱強化アルゴリズムの並列化コストについて検討する。 ブースティングの"軽い"並列化でさえ、トレーニングの複雑さが指数関数的に爆発的に大きくなる必要があることを示す。
  論文  参考訳（メタデータ） (2024-02-23T07:03:52Z)
• A Competitive Algorithm for Agnostic Active Learning [5.4579367210379335]
  アクティブな学習のための最も一般的なアルゴリズムは、不一致係数と呼ばれるパラメータでその性能を表現する。 我々は、任意の二進仮説クラス$H$と分布$D_X$ over$X$に対して最適なアルゴリズムと競合するアルゴリズムを得る。 我々のアルゴリズムの$O(log |H|)$オーバーヘッドよりは、NPハードである。
  論文  参考訳（メタデータ） (2023-10-28T19:01:16Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。 我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。 EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
  論文  参考訳（メタデータ） (2023-10-23T18:26:00Z)
• 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)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)
• RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
  RNNは、自然言語構文の足場を反映した境界階層言語を効率的に生成できることを示す。 Dyck-($k$,$m$)は、よくネストされた括弧($k$型)と$m$バウンドされたネスト深さの言語である。 明示的な構成により,$O(m log k)$ hidden units の RNN がメモリの指数的削減に十分であることを示す。
  論文  参考訳（メタデータ） (2020-10-15T04:42:29Z)
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
  連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。 我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-06-11T00:55:35Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Quantum Boosting [8.93449755281201]
  ブースティングは、弱い不正確な機械学習アルゴリズムを強力な正確な学習アルゴリズムに変換するテクニックである。 量子技術が古典的AdaBoostの時間複雑性をいかに改善できるかを示す。
  論文  参考訳（メタデータ） (2020-02-12T15:47:54Z)

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

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