論文の概要: Do PAC-Learners Learn the Marginal Distribution?
- arxiv url: http://arxiv.org/abs/2302.06285v1
- Date: Mon, 13 Feb 2023 11:42:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2023-02-14 15:47:15.200597
- Title: Do PAC-Learners Learn the Marginal Distribution?
- Title（参考訳）: PAC-Learnerは配偶者の分布を学習しているか?
- Authors: Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
- Abstract要約: 我々はPAC-Learningの変種について検討し、この変種は敵が既知の限界分布の族に制限される。
テレビ学習はPAC学習と等価であることを示す。
- 参考スコア（独自算出の注目度）: 24.80812483480747
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study a foundational variant of Valiant and Vapnik and Chervonenkis'
Probably Approximately Correct (PAC)-Learning in which the adversary is
restricted to a known family of marginal distributions $\mathscr{P}$. In
particular, we study how the PAC-learnability of a triple $(\mathscr{P},X,H)$
relates to the learners ability to infer \emph{distributional} information
about the adversary's choice of $D \in \mathscr{P}$. To this end, we introduce
the `unsupervised' notion of \emph{TV-Learning}, which, given a class
$(\mathscr{P},X,H)$, asks the learner to approximate $D$ from unlabeled samples
with respect to a natural class-conditional total variation metric.
In the classical distribution-free setting, we show that TV-learning is
\emph{equivalent} to PAC-Learning: in other words, any learner must infer
near-maximal information about $D$. On the other hand, we show this
characterization breaks down for general $\mathscr{P}$, where PAC-Learning is
strictly sandwiched between two approximate variants we call `Strong' and
`Weak' TV-learning, roughly corresponding to unsupervised learners that
estimate most relevant distances in $D$ with respect to $H$, but differ in
whether the learner \emph{knows} the set of well-estimated events. Finally, we
observe that TV-learning is in fact equivalent to the classical notion of
\emph{uniform estimation}, and thereby give a strong refutation of the uniform
convergence paradigm in supervised learning.
- Abstract（参考訳）: 本稿では,Valiant と Vapnik と Chervonenkis' Probably Aough Correct (PAC)-Learning の基本的な変種について検討する。
特に、3倍の $(\mathscr{p},x,h)$ のpac-learnability が、敵の$d \in \mathscr{p}$ の選択に関する \emph{distributional} 情報を推測する学習者能力とどのように関係しているかを考察する。
この目的のために、"unsupervised" の概念である \emph{tv-learning} を導入し、クラス $(\mathscr{p},x,h)$ が与えられたとき、学習者に、自然なクラス条件の全変動メトリックに関してラベルなしサンプルから$d$を近似するよう求める。
古典的な配布のない環境では、テレビラーニングはパックラーニングと同値であることを示す: つまり、どんな学習者も$d$の最大値に近い情報を推測しなければならない。
一方、この特徴は一般に$\mathscr{P}$に対して分解され、PAC-Learningは「Strong」と「Weak」テレビ学習と呼ばれる2つの近似変種に厳密に挟まれており、大まかに言えば、$D$の最も関連する距離を$H$に対して推定する教師なし学習者に対応するが、学習者 \emph{knows} がよく推定された事象の集合であるかどうかが異なる。
最後に,テレビ学習は古典的な概念である 'emph{uniform Estimation} と等価であり,教師付き学習における一様収束パラダイムの強い反感を与える。
関連論文リスト
- On Characterizing and Mitigating Imbalances in Multi-Instance Partial Label Learning [57.18649648182171]
我々は、MI-PLLの文脈において、これまで研究されていない問題に対処するためのコントリビューションを行っている。
最小限の仮定をしながら、クラス固有のMI-PLLのリスク境界を導出する。
我々の理論は、$sigma$が学習の不均衡に大きな影響を及ぼすというユニークな現象を明らかにしている。
論文 参考訳（メタデータ） (2024-07-13T20:56:34Z) - Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension [17.485243410774814]
教師付き学習の伝統的なモデルでは、学習者の目標は、あるクラスから最も適した概念の競争的($epsilon$以内)な仮説を出力することである。
学習者が最高の無知としか競合しないスムーズな分析フレームワークを導入する。
時間内に$k$-halfspacesの交点を前向きに学習する最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-07-01T04:58:36Z) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Loss [33.18537822803389]
L2$ と $Psi_p$ の位相が我々の仮説クラス $mathscrF$, $mathscrF$ に同値であるときにいつでも、$mathscrF$ は弱準ガウス類であることを示す。
以上の結果から, 混合への直接的な依存は高次項に還元されるため, この問題は実現可能か否かを判断できる。
論文 参考訳（メタデータ） (2024-02-08T18:57:42Z) - Beyond Expectations: Learning with Stochastic Dominance Made Practical [88.06211893690964]
支配は、不確実な結果で意思決定を行うためのリスク-逆の選好をモデル化する。
理論上は魅力的だが、機械学習における優位性の応用は乏しい。
まず支配の概念を一般化し、任意の確率変数の任意のペア間の比較を可能にする。
次に、優位性の観点から最適解を見つけるための単純で効率的なアプローチを開発する。
論文 参考訳（メタデータ） (2024-02-05T03:21:23Z) - The Sample Complexity of Multi-Distribution Learning for VC Classes [25.73730126599202]
マルチディストリビューション学習は、PAC学習を複数のデータ分布を持つ設定に一般化したものである。
PAC学習クラスでは, 既知の上層境界と下層境界との間に大きなギャップが残っている。
本稿では,この問題の最近の進展と,統計学習におけるゲームダイナミクスの利用の基礎となるいくつかのハードルについて論じる。
論文 参考訳（メタデータ） (2023-07-22T18:02:53Z) - 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) - On Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
本研究は,学習者によって達成可能な最小のエラー$epsilon=epsilon(eta)$を,そのような敵の存在下で特徴付けることを目的とする。
注目すべきは,上界が決定論的学習者によって達成できることである。
論文 参考訳（メタデータ） (2022-10-06T06:49:48Z) - Quantization for decentralized learning under subspace constraints [61.59416703323886]
エージェントがサブスペース制約を最小化するために個々のコスト関数を持つ分散最適化問題を考察する。
本稿では,エージェントが確率化量子化器を用いて推定値を圧縮する適応分散型戦略を提案し,検討する。
この分析は、量子化ノイズのいくつかの一般的な条件下では、平均二乗誤差と平均ビットレートの両方で戦略が安定であることを示している。
論文 参考訳（メタデータ） (2022-09-16T09:38:38Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - 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) - Provable Robustness of Adversarial Training for Learning Halfspaces with
Noise [95.84614821570283]
ラベル雑音の存在下での敵対的ロバストなハーフスペースの特性を分析する。
我々の知る限りでは、これは敵の訓練がノイズの分類子を与えることを示す最初の研究である。
論文 参考訳（メタデータ） (2021-04-19T16:35:38Z) - On Agnostic PAC Learning using $\mathcal{L}_2$-polynomial Regression and
Fourier-based Algorithms [10.66048003460524]
構造的性質を持つPAC学習問題を解析するためのプロキシとしてヒルベルト空間を用いたフレームワークを開発する。
0-1の損失を持つPAC学習はヒルベルト空間領域における最適化と同値であることを示す。
論文 参考訳（メタデータ） (2021-02-11T21:28:55Z) - Arbitrary Conditional Distributions with Energy [11.081460215563633]
より一般的で有用な問題は任意の条件密度推定である。
本稿では, 分布$p(mathbfx_umid mathbfx_o)$を同時に推定できる新しい手法であるArbitrary Conditioning with Energy (ACE)を提案する。
また,1次元条件のみを学習することで学習問題を単純化し,推論中により複雑な分布を復元する。
論文 参考訳（メタデータ） (2021-02-08T18:36:26Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - Reducing Adversarially Robust Learning to Non-Robust PAC Learning [39.51923275855131]
非ロマンスな学習者を用いて、仮説クラスを頑健に学習できる還元を与える。
$mathcalA$への呼び出しの数は、例ごとに許容される逆の摂動の数に対数的に依存する。
論文 参考訳（メタデータ） (2020-10-22T20:28:35Z) - Beyond $\mathcal{H}$-Divergence: Domain Adaptation Theory With
Jensen-Shannon Divergence [21.295136514836788]
広範に評価された経験的ドメイン逆行訓練と,$mathcalH$-divergenceに基づく理論上の相似性を明らかにする。
我々は,Jensen-Shannon分散に基づく上層および下層ターゲットのリスク境界を直接証明することによって,新たな理論的枠組みを確立する。
論文 参考訳（メタデータ） (2020-07-30T16:19:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。