Fugu-MT 論文翻訳(概要): Sample Amplification: Increasing Dataset Size even when Learning is Impossible

論文の概要: Sample Amplification: Increasing Dataset Size even when Learning is Impossible

arxiv url: http://arxiv.org/abs/1904.12053v3
Date: Sun, 25 Aug 2024 23:38:40 GMT
ステータス: 処理完了
システム内更新日: 2024-08-28 20:36:52.074212
Title: Sample Amplification: Increasing Dataset Size even when Learning is Impossible
Title（参考訳）: サンプル増幅:学習が不可能な場合でもデータセットのサイズが大きくなる
Authors: Brian Axelrod, Shivam Garg, Vatsal Sharan, Gregory Valiant,
Abstract要約: 未知のディストリビューションから引き出されたデータである$D$が、このデータセットを増幅し、さらに大きなサンプルセットを$D$から抽出したように見えるように出力することは、どの程度まで可能か? この問題は次のように定式化する: $left(n, n + Theta(fracnsqrtk)right)$アンプが存在するが、小さな定数全変動距離への分布を学習するには$Theta(d)$サンプルが必要である。
参考スコア（独自算出の注目度）: 15.864702679819544
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Given data drawn from an unknown distribution, $D$, to what extent is it possible to ``amplify'' this dataset and output an even larger set of samples that appear to have been drawn from $D$? We formalize this question as follows: an $(n,m)$ $\text{amplification procedure}$ takes as input $n$ independent draws from an unknown distribution $D$, and outputs a set of $m > n$ ``samples''. An amplification procedure is valid if no algorithm can distinguish the set of $m$ samples produced by the amplifier from a set of $m$ independent draws from $D$, with probability greater than $2/3$. Perhaps surprisingly, in many settings, a valid amplification procedure exists, even when the size of the input dataset, $n$, is significantly less than what would be necessary to learn $D$ to non-trivial accuracy. Specifically we consider two fundamental settings: the case where $D$ is an arbitrary discrete distribution supported on $\le k$ elements, and the case where $D$ is a $d$-dimensional Gaussian with unknown mean, and fixed covariance. In the first case, we show that an $\left(n, n + \Theta(\frac{n}{\sqrt{k}})\right)$ amplifier exists. In particular, given $n=O(\sqrt{k})$ samples from $D$, one can output a set of $m=n+1$ datapoints, whose total variation distance from the distribution of $m$ i.i.d. draws from $D$ is a small constant, despite the fact that one would need quadratically more data, $n=\Theta(k)$, to learn $D$ up to small constant total variation distance. In the Gaussian case, we show that an $\left(n,n+\Theta(\frac{n}{\sqrt{d}} )\right)$ amplifier exists, even though learning the distribution to small constant total variation distance requires $\Theta(d)$ samples. In both the discrete and Gaussian settings, we show that these results are tight, to constant factors. Beyond these results, we formalize a number of curious directions for future research along this vein.
Abstract（参考訳）: 未知のディストリビューションから引き出されたデータである$D$が、このデータセットを ‘amplify’ して、$D$から引き出されたと思われるさらに大きなサンプルセットを出力することは、どの程度まで可能か? a $(n,m)$ $\text{amplification procedure}$は、未知の分布の$D$からの独立な引き数として$n$とされ、$m > n$ `samples'' の集合を出力する。増幅手順は、アルゴリズムが増幅器が生成した$m$サンプルのセットと$m$独立引き分けのセットを$D$と区別することができなければ有効であり、確率は2/3$を超える。おそらく、多くの設定において有効な増幅手順が存在し、入力データセットのサイズが$n$である場合でも、非自明な精度で$D$を学ぶのに必要なものよりもはるかに少ない。具体的には、$D$が$\le k$元でサポートされている任意の離散分布である場合と、$D$が未知の平均を持つ$d$次元ガウス多様体である場合、固定共分散である。まず、$\left(n, n + \Theta(\frac{n}{\sqrt{k}})\right)$アンプが存在することを示す。特に$D$から$n=O(\sqrt{k})$サンプルが与えられた場合、$m=n+1$のデータポイントの集合を出力することができ、$m=i.d.の分布から$D$の総変動距離は小さい定数である。ガウスの場合、小さな定数全変動距離への分布を学習しても、$\left(n,n+\Theta(\frac{n}{\sqrt{d}} )\right)$アンプが存在することを示す。離散的条件とガウス的条件の両方において、これらの結果は定数因子に対して厳密であることを示す。これらの結果以外にも、今後の研究の好奇心をそそる方向を定式化している。

関連論文リスト

Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文参考訳（メタデータ） (2024-11-01T17:59:53Z)
Outlier Robust Multivariate Polynomial Regression [27.03423421704806]
1,1]n 回 mathbbR$ は $(mathbfx_i,p(mathbfx_i)$ のうるさいバージョンである。目標は、$hatp$を$ell_in$-distanceの$O(sigma)$を$p$から出力することである。
論文参考訳（メタデータ） (2024-03-14T15:04:45Z)
TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。本稿では,この数値をほぼ最適に推定する手法を提案する。
論文参考訳（メタデータ） (2022-02-15T03:49:28Z)
Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文参考訳（メタデータ） (2021-10-05T09:33:49Z)
The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文参考訳（メタデータ） (2020-12-31T18:24:41Z)
Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文参考訳（メタデータ） (2020-11-21T01:33:15Z)
The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
論文参考訳（メタデータ） (2020-07-16T04:23:57Z)
Learning Entangled Single-Sample Gaussians in the Subset-of-Signals Model [28.839136703139225]
本研究は, 共通平均と異なる未知の分散を持つ絡み合った単一サンプルガウスの平均推定について検討する。誤差が$O left(fracsqrtnln nmright)$m=Omega(sqrtnlnn)$の場合に高い確率でエラーを発生させることを示す。さらに下限を証明し、エラーが$Omegaleft(left(fracnm4right)1/6right)$であることを示す。
論文参考訳（メタデータ） (2020-07-10T18:25:38Z)
Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
論文参考訳（メタデータ） (2020-06-17T09:21:00Z)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)
Learning Mixtures of Spherical Gaussians via Fourier Analysis [0.5381004207943596]
標本と計算複雑性の有界性は、$omega(1) leq d leq O(log k)$のとき以前には分かっていなかった。これらの著者はまた、半径$d$ in $d$ dimensions, if $d$ is $Theta(sqrtd)$ in $d$ dimensions, if $d$が少なくとも$poly(k, frac1delta)$であるとき、ガウスのランダム混合の複雑さのサンプルを示す。
論文参考訳（メタデータ） (2020-04-13T08:06:29Z)

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

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