2024-06-30-jin24a.md

note	title	section	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Full version available at https://arxiv.org/abs/2406.07521	Faster Spectral Density Estimation and Sparsification in the Nuclear Norm (Extended Abstract)	Original Papers	We consider the problem of estimating the spectral density of a normalized graph adjacency matrix. Concretely, given an undirected graph $G = (V, E, w)$ with $n$ nodes and positive edge weights $w \in \mathbb{R}^{E}_{> 0}$, the goal is to return eigenvalue estimates $\widehat{\lambda}_1 \le \cdots\le \widehat{\lambda}_n$ such that \begin{align*} \frac{1}{n} \sum_{i\in\{1,\ldots, n\}}|\widehat{\lambda}_i-\lambda_i(N_G)|\le \varepsilon, \end{align*} where ${\lambda}_1(N_G)\le \cdots\le{\lambda}_n(N_G)$ are the eigenvalues of $G$’s normalized adjacency matrix, $N_G$. This goal is equivalent to requiring that the Wasserstein-1 distance between the uniform distribution on $\lambda_1, \ldots, \lambda_n$ and the uniform distribution on $\widehat{\lambda}_1, \ldots, \widehat{\lambda}_n$ is less than $\varepsilon$. We provide a randomized algorithm that achieves the guarantee above with $O(n\varepsilon^{-2})$ queries to a degree and neighbor oracle and in $O(n\varepsilon^{-3})$ time. This improves on previous state-of-the-art methods, including an $O(n\varepsilon^{-7})$ time algorithm from [Braverman et al., STOC 2022] and, for sufficiently small $\varepsilon$, a $2^{O(\varepsilon^{-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 \emph{nuclear sparsification}. We provide an $O(n\varepsilon^{-2})$-query and $O(n\varepsilon^{-2})$-time algorithm for computing $O(n\varepsilon^{-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 \emph{deterministic} algorithm for spectral density estimation that scales linearly with $n$ (sublinear in the representation size of the graph).	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	jin24a	0	Faster Spectral Density Estimation and Sparsification in the Nuclear Norm (Extended Abstract)	2722	2722	2722-2722	2722	false	Jin, Yujia and Karmarkar, Ishani and Musco, Christopher and Sidford, Aaron and Singh, Apoorv Vikram	given family Yujia Jin given family Ishani Karmarkar given family Christopher Musco given family Aaron Sidford given family Apoorv Vikram Singh	2024-06-30		Proceedings of Thirty Seventh Conference on Learning Theory	247	inproceedings	date-parts 2024 6 30	https://proceedings.mlr.press/v247/jin24a/jin24a.pdf