論文の概要: Cryptographic Hardness of Score Estimation
- arxiv url: http://arxiv.org/abs/2404.03272v1
- Date: Thu, 4 Apr 2024 07:49:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-05 15:24:04.222912
- Title: Cryptographic Hardness of Score Estimation
- Title(参考訳): スコア推定の暗号ハードネス
- Authors: Min Jae Song,
- Abstract要約: L2$-accurate score Estimation, in without the strong assumptions on the data distribution, is calculatedly hard in if the sample complexity is in the relevant problem parameters。
我々の難しい推定分布は「ガウシアン・パンケーキ」分布であり、もともとはダイアコニコラス等が原因である。
- 参考スコア(独自算出の注目度): 4.115525455536377
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show that $L^2$-accurate score estimation, in the absence of strong assumptions on the data distribution, is computationally hard even when sample complexity is polynomial in the relevant problem parameters. Our reduction builds on the result of Chen et al. (ICLR 2023), who showed that the problem of generating samples from an unknown data distribution reduces to $L^2$-accurate score estimation. Our hard-to-estimate distributions are the "Gaussian pancakes" distributions, originally due to Diakonikolas et al. (FOCS 2017), which have been shown to be computationally indistinguishable from the standard Gaussian under widely believed hardness assumptions from lattice-based cryptography (Bruna et al., STOC 2021; Gupte et al., FOCS 2022).
- Abstract(参考訳): L^2$-accurate score Estimation, in without the strong assumptions on the data distribution, is calculatedly hard in if sample complexity is polynomial in the relevant problem parameters。
削減はChen et al (ICLR 2023)の結果に基づいており、未知のデータ分布からサンプルを生成する問題は、$L^2$-精度のスコア推定に還元されることを示した。
この分布は、格子ベースの暗号(Bruna et al , STOC 2021; Gupte et al , FOCS 2022)から広く信じられている硬さ仮定の下で、標準ガウスと計算的に区別できないことが示されている。
関連論文リスト
- Optimal score estimation via empirical Bayes smoothing [15.381519485167313]
未知確率分布$rho*$のスコア関数を$n$独立分布および$d$次元における同一分布観測から推定する問題について検討する。
ガウスカーネルに基づく正規化スコア推定器は、一致するミニマックス下界によって最適に示され、この値が得られることを示す。
論文 参考訳(メタデータ) (2024-02-12T16:17:40Z) - Sample-Efficient Training for Diffusion [6.778168189732909]
多くの理論的な研究により、拡散モデルが効率よくサンプリングできることが示されており、$L2$-精度のスコア推定を仮定している。
多対数的なサンプル数を用いて、スコアマッチング対象のバウンダリは、真の分布の確率$delta$分数を除いて、すべてで$L2$精度であることを示す。
論文 参考訳(メタデータ) (2023-11-23T00:27:13Z) - Sample Complexity Bounds for Score-Matching: Causal Discovery and
Generative Modeling [82.36856860383291]
我々は,標準深部ReLUニューラルネットワークをトレーニングすることにより,スコア関数の正確な推定が可能であることを実証した。
スコアマッチングに基づく因果発見手法を用いて因果関係の回復の誤差率の限界を確立する。
論文 参考訳(メタデータ) (2023-10-27T13:09:56Z) - Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples [9.649879910148854]
差分プライバシー(DP)制約下におけるガウシアン混合量の推定問題について検討する。
主な結果は、$textpoly(k,d,1/alpha,1/varepsilon,log (1/delta))$サンプルが$k$ Gaussians in $mathbbRd$から$alpha$までを推定するのに十分であることです。
これは GMM の構造的仮定を一切含まない問題に対する最初の有限標本複雑性上界である。
論文 参考訳(メタデータ) (2023-09-07T17:02:32Z) - Computational Lower Bounds for Graphon Estimation via Low-degree
Polynomials [17.611893473432133]
低次推定器の場合、その推定誤差は幅広いパラメータの下でUSVTの推定値よりも著しく優れていることが示される。
また,コミュニティ数の増加に伴い,SBMにおけるコミュニティ検出誤差の計算下限も提供する。
論文 参考訳(メタデータ) (2023-08-30T03:11:42Z) - Robust Estimation for Nonparametric Families via Generative Adversarial
Networks [92.64483100338724]
我々は,高次元ロバストな統計問題を解くためにGAN(Generative Adversarial Networks)を設計するためのフレームワークを提供する。
我々の研究は、これらをロバスト平均推定、第二モーメント推定、ロバスト線形回帰に拡張する。
技術面では、提案したGAN損失は、スムーズで一般化されたコルモゴロフ-スミルノフ距離と見なすことができる。
論文 参考訳(メタデータ) (2022-02-02T20:11:33Z) - A Robust and Flexible EM Algorithm for Mixtures of Elliptical
Distributions with Missing Data [71.9573352891936]
本稿では、ノイズや非ガウス的なデータに対するデータ計算の欠如に対処する。
楕円分布と潜在的な欠落データを扱う特性を混合した新しいEMアルゴリズムについて検討した。
合成データの実験的結果は,提案アルゴリズムが外れ値に対して頑健であり,非ガウスデータで使用可能であることを示す。
論文 参考訳(メタデータ) (2022-01-28T10:01:37Z) - Non-Gaussian Component Analysis via Lattice Basis Reduction [56.98280399449707]
非ガウス成分分析(NGCA)は分布学習問題である。
我々は,NGCA に対して,$A$ が離散的あるいはほぼ離散的であるような効率的なアルゴリズムを提供する。
論文 参考訳(メタデータ) (2021-12-16T18:38:02Z) - From Optimality to Robustness: Dirichlet Sampling Strategies in
Stochastic Bandits [0.0]
本研究では、腕の観察を再サンプリングした経験的指標のペア比較に基づいて、ジェネリックディリクレサンプリング(DS)アルゴリズムについて検討する。
この戦略の異なる変種は、分布が有界であるときに証明可能な最適後悔保証と、半有界分布に対して軽度量子状態の対数後悔を実現することを示す。
論文 参考訳(メタデータ) (2021-11-18T14:34:21Z) - Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。
テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。
以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
論文 参考訳(メタデータ) (2020-06-22T21:12:31Z) - Generative Modeling with Denoising Auto-Encoders and Langevin Sampling [88.83704353627554]
DAEとDSMの両方がスムーズな人口密度のスコアを推定することを示した。
次に、この結果をarXiv:1907.05600のホモトピー法に適用し、その経験的成功を理論的に正当化する。
論文 参考訳(メタデータ) (2020-01-31T23:50:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。