論文の概要: Moments, Random Walks, and Limits for Spectrum Approximation
- arxiv url: http://arxiv.org/abs/2307.00474v1
- Date: Sun, 2 Jul 2023 05:03:38 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-05 15:57:17.182380
- Title: Moments, Random Walks, and Limits for Spectrum Approximation
- Title（参考訳）: スペクトル近似におけるモーメント, ランダムウォーク, 限界
- Authors: Yujia Jin and Christopher Musco and Aaron Sidford and Apoorv Vikram
Singh
- Abstract要約: 我々は、ワッサーシュタイン1距離において精度$epsilon$に近似できない$[-1,1]$に分布が存在することを示す。
正規化グラフ隣接行列のスペクトルに対する$epsilon$-accurate近似を一定の確率で計算することはできない。
- 参考スコア（独自算出の注目度）: 40.43008834125277
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study lower bounds for the problem of approximating a one dimensional
distribution given (noisy) measurements of its moments. We show that there are
distributions on $[-1,1]$ that cannot be approximated to accuracy $\epsilon$ in
Wasserstein-1 distance even if we know \emph{all} of their moments to
multiplicative accuracy $(1\pm2^{-\Omega(1/\epsilon)})$; this result matches an
upper bound of Kong and Valiant [Annals of Statistics, 2017]. To obtain our
result, we provide a hard instance involving distributions induced by the
eigenvalue spectra of carefully constructed graph adjacency matrices.
Efficiently approximating such spectra in Wasserstein-1 distance is a
well-studied algorithmic problem, and a recent result of Cohen-Steiner et al.
[KDD 2018] gives a method based on accurately approximating spectral moments
using $2^{O(1/\epsilon)}$ random walks initiated at uniformly random nodes in
the graph.
As a strengthening of our main result, we show that improving the dependence
on $1/\epsilon$ in this result would require a new algorithmic approach.
Specifically, no algorithm can compute an $\epsilon$-accurate approximation to
the spectrum of a normalized graph adjacency matrix with constant probability,
even when given the transcript of $2^{\Omega(1/\epsilon)}$ random walks of
length $2^{\Omega(1/\epsilon)}$ started at random nodes.
- Abstract（参考訳）: モーメント(モーメント)の1次元分布を近似する問題に対する下限について検討する。
それらのモーメントの \emph{all} を乗法精度 $(1\pm2^{-\Omega(1/\epsilon)})$ であるとしても、精度に近似できない$[-1,1]$ 上の分布は、Kong と Valiant [Annals of Statistics, 2017] の上限と一致する。
この結果を得るために,注意深いグラフ隣接行列の固有値スペクトルによって引き起こされる分布を含むハードインスタンスを提案する。
そのようなスペクトルをwasserstein-1距離で効率的に近似することはよく研究されたアルゴリズムの問題であり、cohen-steinerらによる最近の結果である。
[kdd 2018]は、グラフ内の一様ランダムノードから開始される2^{o(1/\epsilon)}$ランダムウォークを使用して、スペクトルモーメントを正確に近似する手法を提供する。
この結果から,1/\epsilon$への依存度の向上には新たなアルゴリズム的アプローチが必要であることが示唆された。
特に、2^{\omega(1/\epsilon)$ ランダムウォークの長さ 2^{\omega(1/\epsilon)}$ ランダムノードで開始されたランダムウォークが与えられたとしても、一定の確率で正規化されたグラフ隣接行列のスペクトルに対する$\epsilon$-accurateの近似を計算できない。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。
本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文 参考訳（メタデータ） (2024-08-10T04:26:19Z) - Faster Spectral Density Estimation and Sparsification in the Nuclear Norm [28.368253322669336]
我々は,新しいグラフスペーシフィケーションの概念を導入し,これを核スペーシフィケーションと呼ぶ。
また,本手法はスペクトル密度推定のための最初の決定論的アルゴリズムを導出することを示した。
論文 参考訳（メタデータ） (2024-06-11T17:50:20Z) - Better and Simpler Lower Bounds for Differentially Private Statistical
Estimation [7.693388437377614]
任意の$alpha le O(1)$に対して、ガウスの共分散をスペクトル誤差まで推定するには$tildeOmegaleft(fracd3/2alpha varepsilon + fracdalpha2right)$サンプルが必要である。
次に、有界な$k$thモーメントで重み付き分布の平均を推定するには$tildeOmegaleft(fracdalphak/(k-1) varepsilon +
論文 参考訳（メタデータ） (2023-10-10T04:02:43Z) - A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation [13.810917492304565]
離散確率分布の特性を推定するための統一量子アルゴリズムフレームワークを提案する。
我々のフレームワークは、$alpha$-R'enyi entropy $H_alpha(p)$を、少なくとも2/3$の確率で加算エラー$epsilon$内で推定する。
論文 参考訳（メタデータ） (2022-12-03T08:01:55Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Robust Estimation for Random Graphs [47.07886511972046]
我々は、$n$ノード上のErdHos-R'enyiランダムグラフのパラメータ$p$を頑健に推定する問題について検討する。
情報理論の限界であるすべての$gamma 1/2$に対して、同様の精度で非効率なアルゴリズムを与える。
論文 参考訳（メタデータ） (2021-11-09T18:43:25Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。