TY - JOUR

T1 - Adaptive Power Method

T2 - 34th International Conference onAlgorithmic Learning Theory, ALT 2023

AU - Shin, Seiyun

AU - Zhao, Han

AU - Shomorony, Ilan

N1 - Funding Information:
We would like to thank the anonymous reviewers for their helpful comments. The work of I.S. was supported in part by the National Science Foundation (NSF) under Grant CCF-2046991. H.Z. would like to thank the support from a Facebook Research Award and Amazon AWS Cloud Credit.
Publisher Copyright:
© 2023 S. Shin, H. Zhao & I. Shomorony.

PY - 2023

Y1 - 2023

N2 - Computing the dominant eigenvectors of a matrix A has many applications, such as principal component analysis, spectral embedding, and PageRank. However, in general, this task relies on the complete knowledge of the matrix A, which can be too large to store or even infeasible to observe in many applications, e.g., large-scale social networks. Thus, a natural question is how to accurately estimate the eigenvectors of A when only partial observations can be made by sampling entries from A. To this end, we propose the Adaptive Power Method (APM), a variant of the well-known power method. At each power iteration, APM adaptively selects a subset of the entries of A to observe based on the current estimate of the top eigenvector. We show that APM can estimate the dominant eigenvector(s) of A with squared error at most ϵ by observing roughly O(nϵ−2 log2(n/ϵ)) entries of an n × n matrix. We present empirical results for the problem of eigenvector centrality computation on two real-world graphs and show that APM significantly outperforms a non-adaptive estimation algorithm using the same number of observations. Furthermore, in the context of eigenvector centrality, APM can also adaptively allocate the observation budget to selectively refine the estimate of nodes with high centrality scores in the graph.

AB - Computing the dominant eigenvectors of a matrix A has many applications, such as principal component analysis, spectral embedding, and PageRank. However, in general, this task relies on the complete knowledge of the matrix A, which can be too large to store or even infeasible to observe in many applications, e.g., large-scale social networks. Thus, a natural question is how to accurately estimate the eigenvectors of A when only partial observations can be made by sampling entries from A. To this end, we propose the Adaptive Power Method (APM), a variant of the well-known power method. At each power iteration, APM adaptively selects a subset of the entries of A to observe based on the current estimate of the top eigenvector. We show that APM can estimate the dominant eigenvector(s) of A with squared error at most ϵ by observing roughly O(nϵ−2 log2(n/ϵ)) entries of an n × n matrix. We present empirical results for the problem of eigenvector centrality computation on two real-world graphs and show that APM significantly outperforms a non-adaptive estimation algorithm using the same number of observations. Furthermore, in the context of eigenvector centrality, APM can also adaptively allocate the observation budget to selectively refine the estimate of nodes with high centrality scores in the graph.

KW - Adaptive sampling

KW - Eigenvector estimation

KW - Noisy power method

UR - http://www.scopus.com/inward/record.url?scp=85164592714&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85164592714&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85164592714

SN - 2640-3498

VL - 201

SP - 1387

EP - 1410

JO - Proceedings of Machine Learning Research

JF - Proceedings of Machine Learning Research

Y2 - 20 February 2023 through 23 February 2023

ER -