論文の概要: Sample-Near-Optimal Agnostic Boosting with Improved Running Time

• arxiv url: http://arxiv.org/abs/2601.11265v2
• Date: Mon, 19 Jan 2026 12:56:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-21 18:45:13.563695
• Title: Sample-Near-Optimal Agnostic Boosting with Improved Running Time
• Title（参考訳）: ランニング時間の改善によるサンプル・ナア・オプティカル・アグノスティック・ブースティング
• Authors: Arthur da Cunha, Mikael Møller Høgsgaard, Andrea Paudice,
• Abstract要約: ブースティングは、ランダムな推測よりもわずかに優れた弱い学習者を高い精度で強力な学習者に変える強力な方法である。 そこで本研究では,問題の他のパラメータを考慮に入れた場合,サンプルサイズで時間的に動作する,近似的なサンプル複雑性を持つ最初の非依存的ブースティングアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 10.9284286893389
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Boosting is a powerful method that turns weak learners, which perform only slightly better than random guessing, into strong learners with high accuracy. While boosting is well understood in the classic setting, it is less so in the agnostic case, where no assumptions are made about the data. Indeed, only recently was the sample complexity of agnostic boosting nearly settled arXiv:2503.09384, but the known algorithm achieving this bound has exponential running time. In this work, we propose the first agnostic boosting algorithm with near-optimal sample complexity, running in time polynomial in the sample size when considering the other parameters of the problem fixed.
• Abstract（参考訳）: ブースティングは、ランダムな推測よりもわずかに優れた弱い学習者を高い精度で強力な学習者に変える強力な方法である。 ブースティングは古典的な設定ではよく理解されているが、データに関する仮定が作成されないような非依存の場合にはそうではない。 実際、最近になって、ほとんど落ち着いたarXiv:2503.09384の非依存的なブースティングのサンプル複雑性が発見されたが、この限界を達成する既知のアルゴリズムは指数関数的な実行時間を持っている。 そこで本研究では,問題の他のパラメータを考慮に入れた場合,サンプルサイズで時間多項式を動作させる,ほぼ最適なサンプル複雑性を持つ最初の非依存的ブースティングアルゴリズムを提案する。

関連論文リスト

• Revisiting Agnostic Boosting [15.705418399834278]
  提案手法は, 従来の計算方法と比較して, サンプルの複雑さを大幅に改善した新しい非依存的ブースティングアルゴリズムを提案する。 我々のアプローチは、実現可能なケースの削減と、それに続く高品質な仮説のマージンベースのフィルタリングに基づいている。
  論文  参考訳（メタデータ） (2025-03-12T13:29:33Z)
• Sample-Optimal Agnostic Boosting with Unlabeled Data [19.15484761265653]
  Boostingは、親指の不正確なルールから正確な学習アルゴリズムを構築するためのフレームワークを提供する。 本稿は、予期せぬ、これまで探索されなかった改善の道である未ラベルのサンプルを取り上げる。 我々は、最もよく知られたブースティングアルゴリズムにおいて、必要となるサンプルの総数は、ラベル付きおよびラベル付きで、それ以上ではないことを示した。
  論文  参考訳（メタデータ） (2025-03-06T18:54:42Z)
• Sample-Efficient Agnostic Boosting [19.15484761265653]
  経験的リスク最小化(Empirical Risk Minimization, ERM)は、既知のすべてのブースティングアルゴリズムよりも4次的に標本効率が高いという、不可知的なブースティング手法を超越している。 アルゴリズムの重要な特徴は、一様収束引数のブラックボックスアプリケーションで得られるものよりも厳密な一般化誤差を保証しつつ、複数ラウンドのブースティングのサンプルを再利用する能力を活用することである。
  論文  参考訳（メタデータ） (2024-10-31T04:50:29Z)
• The Many Faces of Optimal Weak-to-Strong Learning [10.985323882432086]
  提案手法は, サンプルの複雑さを証明し得る, 驚くほど単純なブースティングアルゴリズムである。 我々のパイロット実験研究は、我々の新しいアルゴリズムが大規模なデータセットで以前のアルゴリズムより優れていることを示唆している。
  論文  参考訳（メタデータ） (2024-08-30T09:38:51Z)
• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。 この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
  論文  参考訳（メタデータ） (2024-04-02T16:35:52Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。 提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
  バイレベル最適化は多くの応用のために機械学習への関心が高まっている。 制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
  論文  参考訳（メタデータ） (2021-06-21T20:16:40Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。 この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。 我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
  論文  参考訳（メタデータ） (2020-06-21T15:32:21Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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