論文の概要: Metric Entropy Duality and the Sample Complexity of Outcome
Indistinguishability
- arxiv url: http://arxiv.org/abs/2203.04536v1
- Date: Wed, 9 Mar 2022 06:02:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-10 14:49:10.910372
- Title: Metric Entropy Duality and the Sample Complexity of Outcome
Indistinguishability
- Title（参考訳）: 計量エントロピー双対性と結果の不一致性のサンプル複雑性
- Authors: Lunjia Hu, Charlotte Peale, Omer Reingold
- Abstract要約: 結果の不一致性において、目標は、ターゲット予測子と区別できない予測子を出力することである。
結果の不一致性のサンプル複雑性は、$P$ w.r.tの計量エントロピーによって特徴づけられる。
この同値性は凸幾何学における長年の計量エントロピー双対性予想と興味深い関係を持つ。
- 参考スコア（独自算出の注目度）: 7.727052811126007
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give the first sample complexity characterizations for outcome
indistinguishability, a theoretical framework of machine learning recently
introduced by Dwork, Kim, Reingold, Rothblum, and Yona (STOC 2021). In outcome
indistinguishability, the goal of the learner is to output a predictor that
cannot be distinguished from the target predictor by a class $D$ of
distinguishers examining the outcomes generated according to the predictors'
predictions.
In the distribution-specific and realizable setting where the learner is
given the data distribution together with a predictor class $P$ containing the
target predictor, we show that the sample complexity of outcome
indistinguishability is characterized by the metric entropy of $P$ w.r.t. the
dual Minkowski norm defined by $D$, and equivalently by the metric entropy of
$D$ w.r.t. the dual Minkowski norm defined by $P$. This equivalence makes an
intriguing connection to the long-standing metric entropy duality conjecture in
convex geometry. Our sample complexity characterization implies a variant of
metric entropy duality, which we show is nearly tight. In the distribution-free
setting, we focus on the case considered by Dwork et al. where $P$ contains all
possible predictors, hence the sample complexity only depends on $D$. In this
setting, we show that the sample complexity of outcome indistinguishability is
characterized by the fat-shattering dimension of $D$.
We also show a strong sample complexity separation between realizable and
agnostic outcome indistinguishability in both the distribution-free and the
distribution-specific settings. This is in contrast to distribution-free (resp.
distribution-specific) PAC learning where the sample complexity in both the
realizable and the agnostic settings can be characterized by the VC dimension
(resp. metric entropy).
- Abstract（参考訳）: 本稿では,dwork,kim,reingold,rothblum,yona (stoc 2021) が最近導入した機械学習の理論的枠組みである,アウトカムの識別可能性に関する最初のサンプル複雑性特性を示す。
結果が識別不能の場合、学習者の目標は、予測者の予測に基づいて生成された結果を調べる識別者のクラス$d$によって目標予測者と区別できない予測者を出力することである。
学習者が予測器を含む予測器クラス$P$と共にデータ分布を与えられる分布特異かつ実現可能な設定において、結果の不一致性のサンプル複雑性は、$D$で定義される2つのミンコフスキーノルムの計量エントロピーと、$D$で定義される2つのミンコフスキーノルムの計量エントロピーと、$P$で定義される2つのミンコフスキーノルムの計量エントロピーによって特徴づけられることを示す。
この同値性は凸幾何学における長年の計量エントロピー双対性予想と興味深い関係を持つ。
我々のサンプルの複雑性の特徴は計量エントロピー双対性の変種を示唆しており、これはほぼ緊密であることを示している。
分布のない環境では、Dworkらによって考慮されたケースに焦点をあてる。$P$はすべての予測子を含むので、サンプルの複雑さは$D$にのみ依存する。
この設定では, 結果の不一致性のサンプル複雑性は, 脂肪破砕寸法が$D$であるのが特徴である。
また,分布自由設定と分布固有設定の両方において,実現可能かつ不可知な結果の区別が困難であることを示す。
これは分布のない(分布特異的な)pac学習とは対照的で、実現可能設定と不可知設定の両方におけるサンプル複雑性はvc次元(計量エントロピー)によって特徴づけられる。
関連論文リスト
- Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Sample Complexity of Variance-reduced Distributionally Robust Q-learning [17.96094201655567]
本稿では,分散性に頑健なQ-ラーニングアルゴリズムと,分散性に欠けるロバストなポリシーを効果的に学習できる分散性のあるQ-ラーニングアルゴリズムを2つ提案する。
一連の数値実験により、分布シフトの処理におけるアルゴリズムの理論的発見と効率性が確認された。
論文 参考訳（メタデータ） (2023-05-28T19:40:46Z) - Differentially-Private Bayes Consistency [70.92545332158217]
差分プライバシー(DP)を満たすベイズ一貫した学習ルールを構築する。
ほぼ最適なサンプル複雑性を持つ半教師付き環境で,任意のVCクラスをプライベートに学習できることを実証する。
論文 参考訳（メタデータ） (2022-12-08T11:57:30Z) - On counterfactual inference with unobserved confounding [36.18241676876348]
独立だが不均一な単位を持つ観測的研究を前提として、各単位の反実分布を学習することが目的である。
我々は、すべての$n$サンプルをプールして、すべての$n$パラメータベクトルを共同で学習する凸目的を導入する。
対数的ソボレフ不等式を満たすためにコンパクトに支持された分布に対して十分な条件を導出する。
論文 参考訳（メタデータ） (2022-11-14T04:14:37Z) - Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。
本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
論文 参考訳（メタデータ） (2022-10-26T03:19:24Z) - On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。
これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文 参考訳（メタデータ） (2022-10-22T19:07:26Z) - Sample Complexity of Forecast Aggregation [9.122524488932573]
ベイズ予測集計モデルでは、未知のバイナリイベントに関するプライベートシグナルを観測した後、その事象に関する過去の信念をプリンシパルに報告する。
プリンシパルは、レポートをイベントの1つの予測に集約する。
この問題のサンプル複雑性は、任意の離散分布に対して少なくとも$tilde (mn-2 / varepsilon)$であることが示される。
論文 参考訳（メタデータ） (2022-07-26T18:12:53Z) - $k$-Variance: A Clustered Notion of Variance [23.57925128327]
我々は,ランダム二成分マッチングの機構に基づく分散の一般化である $k$-variance を導入する。
1次元測度、クラスター測度、低次元部分集合に集中した測度など、いくつかの重要な場合において、この量の詳細分析を行う。
論文 参考訳（メタデータ） (2020-12-13T04:25:32Z) - $(f,\Gamma)$-Divergences: Interpolating between $f$-Divergences and
Integral Probability Metrics [6.221019624345409]
我々は、$f$-divergences と積分確率メトリクス(IPMs)の両方を仮定する情報理論の分岐を構築するためのフレームワークを開発する。
2段階の質量再分配/物質輸送プロセスとして表現できることが示される。
統計的学習を例として,重み付き,絶対連続的なサンプル分布に対するGAN(generative adversarial network)の訓練において,その優位性を示す。
論文 参考訳（メタデータ） (2020-11-11T18:17:09Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。