論文の概要: Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbations

• arxiv url: http://arxiv.org/abs/2506.06613v1
• Date: Sat, 07 Jun 2025 01:11:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-10 16:33:10.361668
• Title: Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbations
• Title（参考訳）: 雑音・対向摂動下におけるサンプル圧縮性分布のロバスト学習性
• Authors: Arefe Boushehrian, Amir Najafi,
• Abstract要約: 2018年、アシュティアーニらは、分布クラスの構造的性質として、元々リトルストーンとウォーマス (1986) によるエンハンブル圧縮性を再編成した。 我々は、必要かつ十分な条件のセットを条件として、摂動サンプルからでも、サンプル圧縮可能なファミリーが学習可能であることを確証する。
• 参考スコア（独自算出の注目度）: 0.723486289593299
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning distribution families over $\mathbb{R}^d$ is a fundamental problem in unsupervised learning and statistics. A central question in this setting is whether a given family of distributions possesses sufficient structure to be (at least) information-theoretically learnable and, if so, to characterize its sample complexity. In 2018, Ashtiani et al. reframed \emph{sample compressibility}, originally due to Littlestone and Warmuth (1986), as a structural property of distribution classes, proving that it guarantees PAC-learnability. This discovery subsequently enabled a series of recent advancements in deriving nearly tight sample complexity bounds for various high-dimensional open problems. It has been further conjectured that the converse also holds: every learnable class admits a tight sample compression scheme. In this work, we establish that sample compressible families remain learnable even from perturbed samples, subject to a set of necessary and sufficient conditions. We analyze two models of data perturbation: (i) an additive independent noise model, and (ii) an adversarial corruption model, where an adversary manipulates a limited subset of the samples unknown to the learner. Our results are general and rely on as minimal assumptions as possible. We develop a perturbation-quantization framework that interfaces naturally with the compression scheme and leads to sample complexity bounds that scale gracefully with the noise level and corruption budget. As concrete applications, we establish new sample complexity bounds for learning finite mixtures of high-dimensional uniform distributions under both noise and adversarial perturbations, as well as for learning Gaussian mixture models from adversarially corrupted samples, resolving two open problems in the literature.
• Abstract（参考訳）: $\mathbb{R}^d$ 上の分布族を学習することは教師なし学習と統計学の基本的な問題である。 この設定における中心的な問題は、ある分布の族が(少なくとも)情報理論的に学習可能であり、もしそうであれば、そのサンプルの複雑さを特徴づけるだけの十分な構造を持っているかどうかである。 2018年、アシュティアーニらは、もともとLittlestone and Warmuth (1986) が分散クラスの構造的性質として、PAC-学習性を保証することを証明したことから、emph{sample compressibility} を再構成した。 この発見はその後、様々な高次元開問題に対して、ほぼ密なサンプル複雑性境界を導出する一連の最近の進歩を可能にした。 すべての学習可能なクラスは、厳密なサンプル圧縮スキームを許容する。 本研究は, 摂動サンプルにおいても, 必要かつ十分な条件を条件として, サンプル圧縮可能なファミリーが学習可能であることを確かめるものである。 データ摂動の2つのモデルを分析する。 (i)付加的な独立ノイズモデル、及び (2) 学習者に未知のサンプルの限られたサブセットを敵が操作する逆汚職モデル。 私たちの結果は概ね一般的であり、可能な限り最小限の仮定に依存します。 我々は,自然に圧縮スキームと相互作用する摂動量子化フレームワークを開発し,ノイズレベルや汚職予算に優しくスケールするサンプル複雑性境界を導出する。 具体的応用として,高次元一様分布の有限混合をノイズと対向的摂動の両方の下で学習し,また,逆向きに崩壊したサンプルからガウス混合モデルを学習し,文献における2つの未解決問題を解くために,新しいサンプル複雑性境界を確立する。

関連論文リスト

• Transductive Learning Is Compact [10.168670899305232]
  一般の損失関数を用いた教師あり学習において, 広範に保持されるコンパクト性結果を示す。 不適切な計量損失を伴う実現可能な学習のために、サンプルの複雑さの正確なコンパクトさは失敗する可能性があることを示す。 我々は、無知の場合においてより大きなギャップが可能であると推測する。
  論文  参考訳（メタデータ） (2024-02-15T23:10:45Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability [57.502573663108535]
  本研究では、半教師付きPACモデルにおいて、時間攻撃をテストするために、逆向きに頑健な予測器を学習する問題について検討する。 最悪の分布自由モデルにおいても,半教師付き頑健な学習には大きなメリットがあることが示されている。
  論文  参考訳（メタデータ） (2022-02-11T03:01:45Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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