論文の概要: The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem

• arxiv url: http://arxiv.org/abs/2409.11597v1
• Date: Tue, 17 Sep 2024 23:09:25 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-19 19:39:45.310625
• Title: The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
• Title（参考訳）: スムーズブースティングのサンプル複雑さとハードコア理論の厚さ
• Authors: Guy Blanc, Alexandre Hayderi, Caleb Koch, Li-Yang Tan,
• Abstract要約: スムースブースターは任意の例にあまり重みを付けない分布を生成する。 もともとは耐雑音性のために導入されたが、そのようなブースターは微分プライバシー、軽度、量子学習理論にも応用されている。
• 参考スコア（独自算出の注目度）: 53.446980306786095
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Smooth boosters generate distributions that do not place too much weight on any given example. Originally introduced for their noise-tolerant properties, such boosters have also found applications in differential privacy, reproducibility, and quantum learning theory. We study and settle the sample complexity of smooth boosting: we exhibit a class that can be weak learned to $\gamma$-advantage over smooth distributions with $m$ samples, for which strong learning over the uniform distribution requires $\tilde{\Omega}(1/\gamma^2)\cdot m$ samples. This matches the overhead of existing smooth boosters and provides the first separation from the setting of distribution-independent boosting, for which the corresponding overhead is $O(1/\gamma)$. Our work also sheds new light on Impagliazzo's hardcore theorem from complexity theory, all known proofs of which can be cast in the framework of smooth boosting. For a function $f$ that is mildly hard against size-$s$ circuits, the hardcore theorem provides a set of inputs on which $f$ is extremely hard against size-$s'$ circuits. A downside of this important result is the loss in circuit size, i.e. that $s' \ll s$. Answering a question of Trevisan, we show that this size loss is necessary and in fact, the parameters achieved by known proofs are the best possible.
• Abstract（参考訳）: スムースブースターは任意の例にあまり重みを付けない分布を生成する。 もともとは耐雑音性のために導入されたが、そのようなブースターは微分プライバシー、再現性、量子学習理論にも応用されている。 均一分布に対する強い学習には$\tilde{\Omega}(1/\gamma^2)\cdot m$サンプルが必要である。 これは既存の滑らかなブースターのオーバーヘッドと一致し、分布に依存しないブースターの設定から最初の分離を提供し、対応するオーバーヘッドは$O(1/\gamma)$である。 私たちの研究は、Impagliazzoのハードコア定理に、複雑性理論から新たな光を当てています。 関数 $f$ は、サイズに対してわずかに難しい-$s$ 回路に対して、ハードコアの定理は、$f$ がサイズに対して非常に難しい入力セットを提供する-$s'$ 回路である。 この重要な結果の欠点は、回路サイズの損失、すなわち、その$s' \ll s$である。 Trevisan の質問に答えると、このサイズ損失は必要であり、事実、既知の証明によって達成されたパラメータが最善であることを示す。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• The Cost of Parallelizing Boosting [1.9235143628887907]
  本研究は,学習用弱強化アルゴリズムの並列化コストについて検討する。 ブースティングの"軽い"並列化でさえ、トレーニングの複雑さが指数関数的に爆発的に大きくなる必要があることを示す。
  論文  参考訳（メタデータ） (2024-02-23T07:03:52Z)
• A Finite Sample Complexity Bound for Distributionally Robust Q-learning [17.96094201655567]
  我々は,展開環境が訓練環境と異なる強化学習環境を考える。 ロバストなマルコフ決定プロセスの定式化を適用することで、Liuらで研究されている分布的にロバストな$Q$ラーニングフレームワークを拡張します。 これはモデルのないロバストなRL問題に対する最初のサンプル複雑性結果である。
  論文  参考訳（メタデータ） (2023-02-26T01:15:32Z)
• Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes [5.526935605535376]
  ノイズの多いサンプルから単純さを学習するために、サンプルの複雑さが結びついているのがわかります。 我々は、$mathrmSNRgeOmegaleft(K1/2right)$ である限り、ノイズのないシステムのサンプルの複雑さは、ノイズのないケースのそれと同じ順序であることを示す。
  論文  参考訳（メタデータ） (2022-09-09T23:35:25Z)
• Settling the Sample Complexity of Model-Based Offline Reinforcement Learning [50.5790774201146]
  オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。 事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。 モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
  論文  参考訳（メタデータ） (2022-04-11T17:26:19Z)
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
  有限混合系における非パラメトリック分布の学習問題について検討する。 このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
  論文  参考訳（メタデータ） (2022-03-28T23:53:48Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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