論文の概要: Sharper Bounds for Chebyshev Moment Matching with Applications to Differential Privacy and Beyond
- arxiv url: http://arxiv.org/abs/2408.12385v1
- Date: Thu, 22 Aug 2024 13:26:41 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-23 13:53:43.090643
- Title: Sharper Bounds for Chebyshev Moment Matching with Applications to Differential Privacy and Beyond
- Title（参考訳）: Sharper、Chebyshev Momentと差別的プライバシおよびそれ以上のアプリケーションとのマッチングをサポート
- Authors: Cameron Musco, Christopher Musco, Lucas Rosenblatt, Apoorv Vikram Singh,
- Abstract要約: 我々は、ワッサーシュタイン距離の正確な回復が、以前よりも多くのノイズで可能であることを証明した。
主な応用として、微分プライベートな合成データ分布を構築するための単純な「線形クエリ」アルゴリズムが得られた。
数値線形代数における新たなモーメントベースリカバリの第二の応用について説明する。
- 参考スコア（独自算出の注目度）: 26.339024618084476
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of approximately recovering a probability distribution given noisy measurements of its Chebyshev polynomial moments. We sharpen prior work, proving that accurate recovery in the Wasserstein distance is possible with more noise than previously known. As a main application, our result yields a simple "linear query" algorithm for constructing a differentially private synthetic data distribution with Wasserstein-1 error $\tilde{O}(1/n)$ based on a dataset of $n$ points in $[-1,1]$. This bound is optimal up to log factors and matches a recent breakthrough of Boedihardjo, Strohmer, and Vershynin [Probab. Theory. Rel., 2024], which uses a more complex "superregular random walk" method to beat an $O(1/\sqrt{n})$ accuracy barrier inherent to earlier approaches. We illustrate a second application of our new moment-based recovery bound in numerical linear algebra: by improving an approach of Braverman, Krishnan, and Musco [STOC 2022], our result yields a faster algorithm for estimating the spectral density of a symmetric matrix up to small error in the Wasserstein distance.
- Abstract（参考訳）: 本研究では,チェビシェフ多項式モーメントの雑音測定により,確率分布をおよそ復元する問題について検討する。
我々は、ワッサーシュタイン距離の正確な回復が、以前よりも多くのノイズで可能であることを証明し、事前の作業を強化した。
メインアプリケーションとして,Wasserstein-1 エラー $\tilde{O}(1/n)$ で差分プライベートな合成データ分布を構築するための単純な "線形クエリ" アルゴリズムを作成した。
この境界はログファクタに最適であり、Boedihardjo, Strohmer, and Vershynin [Probab. Theory. Rel., 2024]の最近のブレークスルーと一致する。
ブレーバーマン、クリシュナン、マスコ(STOC 2022)のアプローチを改善することにより、我々の結果は、ワッサーシュタイン距離の小さな誤差まで対称行列のスペクトル密度を推定するより高速なアルゴリズムをもたらす。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy [23.12198546384976]
後方サンプリングは$varepsilon$-pure差分プライバシー保証を提供する。
これは、$(varepsilon,delta)$-approximate DPによって引き起こされた潜在的に束縛されていないプライバシー侵害に悩まされない。
しかし実際には、マルコフ連鎖モンテカルロのような近似的なサンプリング手法を適用する必要がある。
論文 参考訳（メタデータ） (2023-10-23T07:54:39Z) - Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
我々は、ワッサーシュタイン1距離において精度$epsilon$に近似できない$[-1,1]$に分布が存在することを示す。
正規化グラフ隣接行列のスペクトルに対する$epsilon$-accurate近似を一定の確率で計算することはできない。
論文 参考訳（メタデータ） (2023-07-02T05:03:38Z) - On the Linear Convergence of Policy Gradient under Hadamard
Parameterization [4.182089296199263]
本研究では,アダマールパラメータ化に基づく決定論的政策勾配の収束性について検討する。
すべてのイテレーションに対して$O(frac1k)$レートでエラーが減少することを示す。
論文 参考訳（メタデータ） (2023-05-31T05:51:15Z) - Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression [20.00109111254507]
この問題は、$frackSNR2$-to-$frack2SNR2$statistic-to-computational gapである。
また,この問題が困難な狭い状況以外では,関連する混合回帰検出問題を解くための簡単なしきい値決定アルゴリズムも分析する。
論文 参考訳（メタデータ） (2023-03-03T18:03:49Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。
純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。
平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
論文 参考訳（メタデータ） (2022-12-15T18:27:39Z) - Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy
Amplification by Shuffling [49.43288037509783]
ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。
私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
論文 参考訳（メタデータ） (2020-12-23T17:07:26Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。