Tight query complexity lower bounds for PCA via finite sample deformed Wigner law. (English) Zbl 1428.68168
Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 1249-1259 (2018).
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 15B52 | Random matrices (algebraic aspects) |
| 62H25 | Factor analysis and principal components; correspondence analysis |
Citations:
Zbl 1429.62046References:
| [1] | Alekh Agarwal and Leon Bottou. 2014. A lower bound for the optimization of finite sums. arXiv preprint arXiv:1410.0723 (2014). |
| [2] | Alekh Agarwal, Martin J Wainwright, Peter L Bartlett, and Pradeep K Ravikumar. 2009. Information-theoretic lower bounds on the oracle complexity of convex optimization. In Advances in Neural Information Processing Systems. 1-9. · Zbl 1365.94132 |
| [3] | Zeyuan Allen-Zhu and Yuanzhi Li. 2016. |
| [4] | First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate. arXiv preprint arXiv:1607.07837 (2016). |
| [5] | Zeyuan Allen-Zhu and Yuanzhi Li. 2016. LazySVD: Even faster SVD decomposition yet without agonizing pain. In Advances in Neural Information Processing Systems. 974-982. |
| [6] | Greg W Anderson, Alice Guionnet, and Ofer Zeitouni. 2010. |
| [7] | An introduction to random matrices. Vol. 118. Cambridge university press. · Zbl 1184.15023 |
| [8] | Anurag Anshu, Naresh B Goud, Rahul Jain, Srijita Kundu, and Priyanka Mukhopadhyay. 2017. |
| [9] | Lifting randomized query complexity to randomized communication complexity. arXiv preprint arXiv:1703.07521 (2017). |
| [10] | Ery Arias-Castro, Emmanuel J Candes, and Mark A Davenport. 2013. |
| [11] | On the fundamental limits of adaptive sensing. IEEE Transactions on Information Theory 59, 1 (2013), 472-481. Tight Query Complexity Lower Bounds for PCA STOC’18, June 25-29, 2018, Los Angeles, CA, USA 10.1109/TIT.2012.2215837 · Zbl 1364.94106 |
| [12] | Afonso S Bandeira, Ramon van Handel, et al. 2016. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. The Annals of Probability 44, 4 (2016), 2479-2506. · Zbl 1372.60004 |
| [13] | Florent Benaych-Georges and Raj Rao Nadakuditi. 2011. The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices. Advances in Mathematics 227, 1 (2011), 494-521. · Zbl 1226.15023 |
| [14] | Mireille Capitaine, Catherine Donati-Martin, and Delphine Féral. 2009. |
| [15] | The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations. Annals of Probability (2009), 1-47. · Zbl 1163.15026 |
| [16] | Rui M Castro et al. 2014. Adaptive sensing performance lower bounds for sparse signal detection and support estimation. Bernoulli 20, 4 (2014), 2217-2246. · Zbl 1357.94030 |
| [17] | Rui M Castro and Ervin Tánczos. 2017. Adaptive Compressed Sensing for Support Recovery of Structured Sparse Sets. IEEE Transactions on Information Theory 63, 3 (2017), 1535-1554. 10.1109/TIT.2017.2653802 · Zbl 1366.94088 |
| [18] | Xi Chen, Adityanand Guntuboyina, and Yuchen Zhang. 2016. |
| [19] | On Bayes Risk Lower Bounds. Journal of Machine Learning Research 17 (2016), 1-58. · Zbl 1429.62046 |
| [20] | Imre Csiszár. 1972. A class of measures of informativity of observation channels. Periodica Mathematica Hungarica 2, 1-4 (1972), 191-213. · Zbl 0247.94018 |
| [21] | James W Demmel. 1997. |
| [22] | Applied numerical linear algebra. SIAM. · Zbl 0665.65021 |
| [23] | Delphine Féral and Sandrine Péché. 2007. The largest eigenvalue of rank one deformation of large Wigner matrices. Communications in mathematical physics 272, 1 (2007), 185-228. · Zbl 1136.82016 |
| [24] | Dan Garber, Elad Hazan, Chi Jin, Sham M Kakade, Cameron Musco, Praneeth Netrapalli, and Aaron Sidford. 2016. Faster eigenvector computation via shift- and-invert preconditioning. In Proceedings of the 33nd International Conference on Machine Learning, ICML. 2626-2634. |
| [25] | Roger A Horn and Charles R Johnson. 2012. |
| [26] | Matrix analysis. Cambridge university press. · Zbl 0576.15001 |
| [27] | Kevin G Jamieson, Robert Nowak, and Ben Recht. 2012. |
| [28] | Query complexity of derivative-free optimization. In Advances in Neural Information Processing Systems. 2672-2680. · Zbl 0569.31001 |
| [29] | Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. 2017. How to Escape Saddle Points Efficiently. arXiv preprint arXiv:1703.00887 (2017). |
| [30] | Ian Jolliffe. 2002. |
| [31] | Principal component analysis. Wiley Online Library. · Zbl 0977.62063 |
| [32] | Olav Kallenberg. 2006. |
| [33] | Foundations of modern probability. Springer Science & Business Media. · Zbl 0996.60001 |
| [34] | Cameron Musco and Christopher Musco. 2015. Randomized block krylov methods for stronger and faster approximate singular value decomposition. In Advances in Neural Information Processing Systems. 1396-1404. |
| [35] | Jelani Nelson, Jakub Pachocki, and Zhengyu Wang. 2017. |
| [36] | Optimal lower bounds for universal relation, samplers, and finding duplicates. arXiv preprint arXiv:1703.08139 (2017). |
| [37] | Arkadii Nemirovskii, David Borisovich Yudin, and Edgar Ronald Dawson. 1983. |
| [38] | Problem complexity and method efficiency in optimization. (1983). · Zbl 0501.90062 |
| [39] | Andrew Y Ng, Michael I Jordan, et al. {n. d.}. On spectral clustering: Analysis and an algorithm. |
| [40] | Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. |
| [41] | The PageRank citation ranking: Bringing order to the web. Technical Report. Stanford InfoLab. |
| [42] | Eric Price and David P Woodruff. 2013. Lower bounds for adaptive sparse recovery. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 652-663. · Zbl 1423.94023 |
| [43] | Ohad Shamir. 2014. Fundamental limits of online and distributed algorithms for statistical learning and estimation. In Advances in Neural Information Processing Systems. 163-171. |
| [44] | Ohad Shamir. 2015. Fast stochastic algorithms for SVD and PCA: Convergence properties and convexity. arXiv preprint arXiv:1507.08788 (2015). |
| [45] | Max Simchowitz, Ahmed El Alaoui, and Benjamin Recht. 2018. |
| [46] | Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law. arXiv preprint (to appear) (2018). · Zbl 1428.68168 |
| [47] | Daniel A Spielman. 2007. Spectral graph theory and its applications. In Foundations of Computer Science, 2007. FOCS’07. 48th Annual IEEE Symposium on. IEEE, 29-38. 10.1109/FOCS.2007.66 |
| [48] | Jacob Steinhardt and John C Duchi. 2015. Minimax rates for memory-bounded sparse linear regression.. In COLT. 1564-1587. |
| [49] | Jacob Steinhardt, Gregory Valiant, and Stefan Wager. 2015. Memory, Communication, and Statistical Queries.. In Electronic Colloquium on Computational Complexity (ECCC), Vol. 22. 1-2. |
| [50] | Roman Vershynin. {n. d.}. High Dimensional Probability. ({n. d.}). · Zbl 1430.60005 |
| [51] | Blake E Woodworth and Nati Srebro. 2016. Tight complexity bounds for optimizing composite objectives. In Advances in neural information processing systems. 3639-3647. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
