論文の概要: 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} と等価であり,教師付き学習における一様収束パラダイムの強い反感を与える。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。