論文の概要: Do PAC-Learners Learn the Marginal Distribution?

• arxiv url: http://arxiv.org/abs/2302.06285v4
• Date: Mon, 03 Mar 2025 14:56:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:11:40.004931
• Title: Do PAC-Learners Learn the Marginal Distribution?
• Title（参考訳）: PAC-Learnersは配偶者の分布を学習しているか?
• Authors: Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan,
• Abstract要約: PAC Learning の基本定理は、概念クラス $H$ の学習可能性は$H$ における経験的エラーの $textituniform convergence$ と等価であると主張している。 この研究は、PAC学習、一様収束、分布自由設定を超えた密度推定の関連を再考する。
• 参考スコア（独自算出の注目度）: 19.54058590042626
• License:
• Abstract: The Fundamental Theorem of PAC Learning asserts that learnability of a concept class $H$ is equivalent to the $\textit{uniform convergence}$ of empirical error in $H$ to its mean, or equivalently, to the problem of $\textit{density estimation}$, learnability of the underlying marginal distribution with respect to events in $H$. This seminal equivalence relies strongly on PAC learning's `distribution-free' assumption, that the adversary may choose any marginal distribution over data. Unfortunately, the distribution-free model is known to be overly adversarial in practice, failing to predict the success of modern machine learning algorithms, but without the Fundamental Theorem our theoretical understanding of learning under distributional constraints remains highly limited. In this work, we revisit the connection between PAC learning, uniform convergence, and density estimation beyond the distribution-free setting when the adversary is restricted to choosing a marginal distribution from a known family $\mathscr{P}$. We prove that while the traditional Fundamental Theorem indeed fails, a finer-grained connection between the three fundamental notions continues to hold: 1. PAC-Learning is strictly sandwiched between two refined models of density estimation, differing only in whether the learner $\textit{knows}$ the set of well-estimated events in $H$. 2. Under reasonable assumptions on $H$ and $\mathscr{P}$, density estimation is equivalent to $\textit{uniform estimation}$, a relaxation of uniform convergence allowing non-empirical estimators. Together, our results give a clearer picture of how the Fundamental Theorem extends beyond the distribution-free setting and shed new light on the classically challenging problem of learning under arbitrary distributional assumptions.
• Abstract（参考訳）: PAC Learning の基本定理は、概念クラス $H$ の学習可能性は、$H$ における経験的誤差の $H$ と、その平均、または同等に、$\textit{density Estimation} の問題について、$H$ における事象に関する基礎となる余分分布の学習可能性と等価であると主張している。 このセミナル等価性はPAC学習の「配布不要」な仮定に強く依存しており、敵対者はデータよりも限界分布を選択することができる。 残念ながら、分布自由モデルは現実的には過度に敵対的であることが知られており、現代の機械学習アルゴリズムの成功を予測できないが、基本的な理論がなければ、分布制約下での学習に関する理論的理解は非常に限定的である。 本研究では,PAC学習,一様収束,および分布自由条件以外の密度推定の関連性を再検討し,敵が既知のファミリーの$\mathscr{P}$から限界分布を選択することを制限する。 1) PAC-ラーニングは密度推定の2つの洗練されたモデルの間で厳密にサンドイッチされ、学習者が$\textit{knows}$$H$でよく見積もられたイベントの集合が異なる。 2.$H$ および $\mathscr{P}$ 上の妥当な仮定の下で、密度推定は $\textit{uniform estimation}$ と同値であり、非経験的推定子を許容する一様収束の緩和である。 この結果から, 基本定理が分布自由条件を超えてどのように拡張されるかが明らかとなり, 任意の分布仮定の下での学習の古典的課題に新たな光を当てることができた。

関連論文リスト

• Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension [17.485243410774814]
  教師付き学習の伝統的なモデルでは、学習者の目標は、あるクラスから最も適した概念の競争的($epsilon$以内)な仮説を出力することである。 学習者が最高の無知としか競合しないスムーズな分析フレームワークを導入する。 時間内に$k$-halfspacesの交点を前向きに学習する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-07-01T04:58:36Z)
• Beyond Expectations: Learning with Stochastic Dominance Made Practical [88.06211893690964]
  支配は、不確実な結果で意思決定を行うためのリスク-逆の選好をモデル化する。 理論上は魅力的だが、機械学習における優位性の応用は乏しい。 まず支配の概念を一般化し、任意の確率変数の任意のペア間の比較を可能にする。 次に、優位性の観点から最適解を見つけるための単純で効率的なアプローチを開発する。
  論文  参考訳（メタデータ） (2024-02-05T03:21:23Z)
• Differentially-Private Bayes Consistency [70.92545332158217]
  差分プライバシー(DP)を満たすベイズ一貫した学習ルールを構築する。 ほぼ最適なサンプル複雑性を持つ半教師付き環境で,任意のVCクラスをプライベートに学習できることを実証する。
  論文  参考訳（メタデータ） (2022-12-08T11:57:30Z)
• Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
  非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。 本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
  論文  参考訳（メタデータ） (2022-10-26T03:19:24Z)
• When are Local Queries Useful for Robust Learning? [25.832511407411637]
  本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。 我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。 我々は、0,1n$でハーフスペースに対してロバストな学習アルゴリズムを与え、その後、精度に縛られた敵に対して$mathbbRn$でハーフスペースに対してロバスト性を保証する。
  論文  参考訳（メタデータ） (2022-10-12T11:04:22Z)
• Quantization for decentralized learning under subspace constraints [61.59416703323886]
  エージェントがサブスペース制約を最小化するために個々のコスト関数を持つ分散最適化問題を考察する。 本稿では,エージェントが確率化量子化器を用いて推定値を圧縮する適応分散型戦略を提案し,検討する。 この分析は、量子化ノイズのいくつかの一般的な条件下では、平均二乗誤差と平均ビットレートの両方で戦略が安定であることを示している。
  論文  参考訳（メタデータ） (2022-09-16T09:38:38Z)
• A Unified Framework for Multi-distribution Density Ratio Estimation [101.67420298343512]
  バイナリ密度比推定(DRE)は多くの最先端の機械学習アルゴリズムの基礎を提供する。 ブレグマン最小化の発散の観点から一般的な枠組みを開発する。 我々のフレームワークはバイナリDREでそれらのフレームワークを厳格に一般化する手法に導かれることを示す。
  論文  参考訳（メタデータ） (2021-12-07T01:23:20Z)
• Robust Learning of Optimal Auctions [84.13356290199603]
  本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。 我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-13T17:37:21Z)
• Measuring Model Fairness under Noisy Covariates: A Theoretical Perspective [26.704446184314506]
  本研究では,雑音情報に基づく機械学習モデルの公平性の測定問題について検討する。 本稿では, 精度の高い公平性評価が可能な弱い条件を特徴付けることを目的とした理論的解析を行う。
  論文  参考訳（メタデータ） (2021-05-20T18:36:28Z)
• Arbitrary Conditional Distributions with Energy [11.081460215563633]
  より一般的で有用な問題は任意の条件密度推定である。 本稿では, 分布$p(mathbfx_umid mathbfx_o)$を同時に推定できる新しい手法であるArbitrary Conditioning with Energy (ACE)を提案する。 また,1次元条件のみを学習することで学習問題を単純化し,推論中により複雑な分布を復元する。
  論文  参考訳（メタデータ） (2021-02-08T18:36:26Z)
• Beyond $\mathcal{H}$-Divergence: Domain Adaptation Theory With Jensen-Shannon Divergence [21.295136514836788]
  広範に評価された経験的ドメイン逆行訓練と,$mathcalH$-divergenceに基づく理論上の相似性を明らかにする。 我々は,Jensen-Shannon分散に基づく上層および下層ターゲットのリスク境界を直接証明することによって,新たな理論的枠組みを確立する。
  論文  参考訳（メタデータ） (2020-07-30T16:19:59Z)

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

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