Fugu-MT 論文翻訳(概要): Faster Spectral Density Estimation and Sparsification in the Nuclear Norm

論文の概要: Faster Spectral Density Estimation and Sparsification in the Nuclear Norm

arxiv url: http://arxiv.org/abs/2406.07521v1
Date: Tue, 11 Jun 2024 17:50:20 GMT
ステータス: 処理完了
システム内更新日: 2024-06-12 14:36:00.935827
Title: Faster Spectral Density Estimation and Sparsification in the Nuclear Norm
Title（参考訳）: 核ノルムにおけるより高速なスペクトル密度推定とスパース化
Authors: Yujia Jin, Ishani Karmarkar, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh,
Abstract要約: 我々は,新しいグラフスペーシフィケーションの概念を導入し,これを核スペーシフィケーションと呼ぶ。また,本手法はスペクトル密度推定のための最初の決定論的アルゴリズムを導出することを示した。
参考スコア（独自算出の注目度）: 28.368253322669336
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We consider the problem of estimating the spectral density of the normalized adjacency matrix of an $n$-node undirected graph. We provide a randomized algorithm that, with $O(n\epsilon^{-2})$ queries to a degree and neighbor oracle and in $O(n\epsilon^{-3})$ time, estimates the spectrum up to $\epsilon$ accuracy in the Wasserstein-1 metric. This improves on previous state-of-the-art methods, including an $O(n\epsilon^{-7})$ time algorithm from [Braverman et al., STOC 2022] and, for sufficiently small $\epsilon$, a $2^{O(\epsilon^{-1})}$ time method from [Cohen-Steiner et al., KDD 2018]. To achieve this result, we introduce a new notion of graph sparsification, which we call nuclear sparsification. We provide an $O(n\epsilon^{-2})$-query and $O(n\epsilon^{-2})$-time algorithm for computing $O(n\epsilon^{-2})$-sparse nuclear sparsifiers. We show that this bound is optimal in both its sparsity and query complexity, and we separate our results from the related notion of additive spectral sparsification. Of independent interest, we show that our sparsification method also yields the first deterministic algorithm for spectral density estimation that scales linearly with $n$ (sublinear in the representation size of the graph).
Abstract（参考訳）: 我々は、$n$-node無向グラフの正規化隣接行列のスペクトル密度を推定する問題を考える。 We provide a randomized algorithm that with $O(n\epsilon^{-2})$ query to a degree and neighbor oracle and in $O(n\epsilon^{-3})$ time, estimates the spectrum to up $\epsilon$ accuracy in the Wasserstein-1 metric。これは、[Braverman et al , STOC 2022] の$O(n\epsilon^{-7})$タイムアルゴリズムや、[Cohen-Steiner et al , KDD 2018] の$$$$2^{O(\epsilon^{-1})} の$タイムメソッドなど、従来の最先端のメソッドを改善する。この結果を達成するために,我々は,核拡散と呼ばれる新しいグラフスパーシフィケーションの概念を導入する。我々は、$O(n\epsilon^{-2})$-queryと$O(n\epsilon^{-2})$-timeアルゴリズムを用いて、$O(n\epsilon^{-2})$-sparse核スペーサーを演算する。この境界は、その疎度と問合せの複雑さの両方において最適であることを示し、その結果を、付加スペクトルスペーシフィケーションという関連する概念から分離する。また,本手法は, スペクトル密度推定法として初めて, $n$(グラフの表現サイズはサブ線形)で線形にスケールする決定論的アルゴリズムを導出することを示した。

関連論文リスト

Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-07-04T11:03:48Z)
Quantum speedups for linear programming via interior point methods [1.8434042562191815]
本稿では,$d$変数上の不等式制約で線形プログラムを解く量子アルゴリズムについて述べる。我々のアルゴリズムは、リーとシドフォードの最先端インテリアポイント法におけるニュートンステップを高速化する。
論文参考訳（メタデータ） (2023-11-06T16:00:07Z)
Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
A Quantum Approximation Scheme for k-Means [0.16317061277457]
QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
論文参考訳（メタデータ） (2023-08-16T06:46:37Z)
Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
我々は、ワッサーシュタイン1距離において精度$epsilon$に近似できない$[-1,1]$に分布が存在することを示す。正規化グラフ隣接行列のスペクトルに対する$epsilon$-accurate近似を一定の確率で計算することはできない。
論文参考訳（メタデータ） (2023-07-02T05:03:38Z)
Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文参考訳（メタデータ） (2023-01-11T09:12:28Z)
ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文参考訳（メタデータ） (2023-01-01T18:51:29Z)
Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文参考訳（メタデータ） (2022-06-07T16:49:54Z)
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文参考訳（メタデータ） (2021-06-16T03:34:14Z)
Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文参考訳（メタデータ） (2020-07-16T06:44:44Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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