2018

High-dimensional estimation via sum-of-squares proofs

Raghavendra, Prasad, Schramm, Tselil, Steurer, David

Understand

Estimation is the computational task of recovering a hidden parameter $x$ associated with a distribution $D_x$, given a measurement $y$ sampled from the distribution.

High dimensional estimation problems arise naturally in statistics, machine learning, and complexity theory.
Many high dimensional estimation problems can be formulated as systems of polynomial equations and inequalities, and thus give rise to natural probability distributions over polynomial systems.
Sum-of-squares proofs provide a powerful framework to reason about polynomial systems, and further there exist efficient algorithms to search for low-degree sum-of-squares proofs.

Built on

Jean-Louis Krivine, Anneaux préordonnés , Journal d’analyse mathématique 12
1964
Earlier work this paper cites.
Gilbert Stengle, A nullstellensatz and a positivstellensatz in semialgebraic geometry , Mathematische Annalen 207
1974
Earlier work this paper cites.
G. R. Grimmett and C. J. H. McDiarmid, On colouring random graphs , Mathematical Proceedings of the Cambridge Philosophical Society 77
1975
Earlier work this paper cites.
Mark Jerrum, Large cliques elude the metropolis process , Random Struct. Algorithms 3
1992
Earlier work this paper cites.
S. E. Leurgans, R. T. Ross, and R. B. Abel, A decomposition for three-way arrays , SIAM J. Matrix Anal. Appl. 14
1993
Earlier work this paper cites.
Michel X. Goemans and David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming , J. Assoc. Comput. Mach. 42
1995
Earlier work this paper cites.
Noga Alon, Michael Krivelevich, and Benny Sudakov, Finding a large hidden clique in a random graph , Random Struct. Algorithms 13
1998
Earlier work this paper cites.
Noga Alon, Michael Krivelevich, and Benny Sudakov, Finding a large hidden clique in a random graph , Proceedings of the Eighth International Conference “Random Structures and Algorithms” (Poznan, 1997), vol. 13, 1998, pp. 457–466. MR 1662795
1998
Earlier work this paper cites.
Sanjoy Dasgupta, Learning mixtures of gaussians , FOCS, IEEE Computer Society, 1999, pp. 634–644
1999
Earlier work this paper cites.
Uriel Feige and Robert Krauthgamer, Finding and certifying a large hidden clique in a semirandom graph , Random Structures Algorithms 16
2000
Earlier work this paper cites.
Jean B. Lasserre, Global optimization with polynomials and the problem of moments , SIAM J. Optim. 11
2000
Earlier work this paper cites.
Pablo A Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization , Ph.D. thesis, California Institute of Technology, 2000
2000
Earlier work this paper cites.
Bruce Reznick, Some concrete aspects of Hilbert’s 17th Problem , Real algebraic geometry and ordered structures (Baton Rouge, LA, 1996), Contemp. Math., vol. 253, Amer. Math. Soc., Providence, RI, 2000, pp. 251–272. MR 1747589
2000
Earlier work this paper cites.
Sanjeev Arora and Ravi Kannan, Learning mixtures of arbitrary gaussians , STOC, ACM, 2001, pp. 247–257
2001
Earlier work this paper cites.
Dima Grigoriev, Complexity of positivstellensatz proofs for the knapsack , Computational Complexity 10
2001
Earlier work this paper cites.
Eli Ben-Sasson and Yonatan Bilu, A gap in average proof complexity , Electronic Colloquium on Computational Complexity (ECCC) (2002), no. 003
2002
Earlier work this paper cites.
Andrea Crisanti, Luca Leuzzi, and Giorgio Parisi, The 3-SAT problem with large number of clauses in the ∞ \infty -replica symmetry breaking scheme , Journal of Physics A: Mathematical and General 35
2002
Earlier work this paper cites.
Uriel Feige, Relations between average case complexity and approximation complexity , Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, ACM, New York, 2002, pp. 534–543. MR 2121179
2002
Earlier work this paper cites.
Uriel Feige and Gideon Schechtman, On the optimality of the random hyperplane rounding technique for MAX CUT , Random Structures Algorithms 20
2002
Earlier work this paper cites.
Leonid Gurvits, Classical deterministic complexity of edmonds’ problem and quantum entanglement , Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, ACM, 2003, pp. 10–19
2003
Earlier work this paper cites.
Santosh Vempala and Grant Wang, A spectral algorithm for learning mixture models , J. Comput. Syst. Sci. 68
2004
Earlier work this paper cites.
Dimitris Achlioptas and Frank McSherry, On spectral learning of mixtures of distributions , COLT, Lecture Notes in Computer Science, vol. 3559, Springer, 2005, pp. 458–469
2005
Earlier work this paper cites.
Elchanan Mossel and Sébastien Roch, Learning nonsingular phylogenies and hidden markov models , STOC, ACM, 2005, pp. 366–375
2005
Earlier work this paper cites.
Lieven De Lathauwer, Joséphine Castaing, and Jean-François Cardoso, Fourth-order cumulant-based blind identification of underdetermined mixtures , IEEE Trans. Signal Processing 55
2007
Earlier work this paper cites.

Similar

Grant Schoenebeck, Linear level lasserre lower bounds for certain k-csps , FOCS, IEEE Computer Society, 2008, pp. 593–602
2008
Cited alongside, same era.
Emmanuel J. Candès and Benjamin Recht, Exact matrix completion via convex optimization , Foundations of Computational Mathematics 9
2009
Cited alongside, same era.
Madhur Tulsiani, CSP gaps and reductions in the lasserre hierarchy , STOC, ACM, 2009, pp. 303–312
2009
Cited alongside, same era.
Mikhail Belkin and Kaushik Sinha, Toward learning gaussian mixtures with arbitrary separation , COLT, Omnipress, 2010, pp. 407–419
2010
Cited alongside, same era.
Sevag Gharibian, Strong np-hardness of the quantum separability problem , Quantum Information & Computation 10
2010
Cited alongside, same era.
Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant, Efficiently learning mixtures of two gaussians , STOC, ACM, 2010, pp. 553–562
2010
Cited alongside, same era.
Ankur Moitra and Gregory Valiant, Settling the polynomial learnability of mixtures of gaussians , FOCS, IEEE Computer Society, 2010, pp. 93–102
2010
Cited alongside, same era.
David Gross, Recovering low-rank matrices from few coefficients in any basis , IEEE Trans. Information Theory 57
2011
Cited alongside, same era.
Benjamin Recht, A simpler approach to matrix completion , Journal of Machine Learning Research 12
2011
Cited alongside, same era.
Anima Anandkumar, Dean P. Foster, Daniel J. Hsu, Sham Kakade, and Yi-Kai Liu, A spectral algorithm for latent dirichlet allocation , NIPS, 2012, pp. 926–934
2012
Cited alongside, same era.
Boaz Barak, Fernando G. S. L. Brandão, Aram Wettroth Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou, Hypercontractivity, sum-of-squares proofs, and their applications , STOC, ACM, 2012, pp. 307–326
2012
Cited alongside, same era.
Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, and Yuan Zhou, Polynomial integrality gaps for strong SDP relaxations of densest k -subgraph , SODA, SIAM, 2012, pp. 388–405
2012
Cited alongside, same era.

Then

Boaz Barak, Siu On Chan, and Pravesh K. Kothari, Sum of squares lower bounds from pairwise independence [extended abstract] , STOC’15—Proceedings of the 2015 ACM Symposium on Theory of Computing, ACM, New York, 2015, pp. 97–106. MR 3388187
2015
Later among the works it cites.
Yudong Chen, Incoherence-optimal matrix completion , IEEE Trans. Information Theory 61
2015
Later among the works it cites.
Yash Deshpande and Andrea Montanari, Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems , COLT, JMLR Workshop and Conference Proceedings, vol. 40, JMLR.org, 2015, pp. 523–562
2015
Later among the works it cites.
Rong Ge and Tengyu Ma, Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms , APPROX-RANDOM, LIPIcs, vol. 40, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015, pp. 829–849
2015
Later among the works it cites.
Samuel B. Hopkins, Jonathan Shi, and David Steurer, Tensor principal component analysis via sum-of-square proofs , COLT, JMLR Workshop and Conference Proceedings, vol. 40, JMLR.org, 2015, pp. 956–1006
2015
Later among the works it cites.
Subhash A. Khot and Nisheeth K. Vishnoi, The unique games conjecture, integrability gap for cut problems and embeddability of negative-type metrics into ℓ 1 \ell_{1} , J. ACM 62
2015
Later among the works it cites.
Raghu Meka, Aaron Potechin, and Avi Wigderson, Sum-of-squares lower bounds for planted clique , STOC, ACM, 2015, pp. 87–96
2015
Later among the works it cites.
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, and Aaron Potechin, A nearly tight sum-of-squares lower bound for the planted clique problem , FOCS, IEEE Computer Society, 2016, pp. 428–437
2016
Later among the works it cites.
Boaz Barak and Ankur Moitra, Noisy tensor completion via the sum-of-squares hierarchy , COLT, JMLR Workshop and Conference Proceedings, vol. 49, JMLR.org, 2016, pp. 417–445
2016
Later among the works it cites.
Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, and Tselil Schramm, On the integrality gap of degree-4 sum of squares for planted clique , SODA, SIAM, 2016, pp. 1079–1095
2016
Later among the works it cites.
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer, Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors , STOC, ACM, 2016, pp. 178–191
2016
Later among the works it cites.
Dhruv Medarametla and Aaron Potechin, Bounds on the norms of uniform low degree graph matrices , Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France (Klaus Jansen, Claire Mathieu, José D. P. Rolim, and Chris Umans, eds.), LIPIcs, vol. 60, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016, pp. 40:1–40:26
2016
Later among the works it cites.
Tengyu Ma, Jonathan Shi, and David Steurer, Polynomial-time tensor decompositions with sum-of-squares , FOCS, IEEE Computer Society, 2016, pp. 438–446
2016
Later among the works it cites.
Sanjeev Arora, Rong Ge, Tengyu Ma, and Andrej Risteski, Provable learning of noisy-or networks , Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017 (Hamed Hatami, Pierre McKenzie, and Valerie King, eds.), ACM, 2017, pp. 1057–1066
2017
Later among the works it cites.
Vijay Bhattiprolu, Venkatesan Guruswami, and Euiwoong Lee, Sum-of-squares certificates for maxima of random tensors on the sphere , APPROX-RANDOM, LIPIcs, vol. 81, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017, pp. 31:1–31:20
2017
Later among the works it cites.
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Srinivas Vempala, and Ying Xiao, Statistical algorithms and a lower bound for detecting planted cliques , J. ACM 64
2017
Later among the works it cites.
Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer, The power of sum-of-squares for detecting hidden structures , FOCS, IEEE Computer Society, 2017, pp. 720–731
2017
Later among the works it cites.
Pravesh K. Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer, Sum of squares lower bounds for refuting any CSP , STOC, ACM, 2017, pp. 132–145
2017
Later among the works it cites.
Aaron Potechin and David Steurer, Exact tensor completion with sum-of-squares , COLT, Proceedings of Machine Learning Research, vol. 65, PMLR, 2017, pp. 1619–1673
2017
Later among the works it cites.
Prasad Raghavendra, Satish Rao, and Tselil Schramm, Strongly refuting random csps below the spectral threshold , STOC, ACM, 2017, pp. 121–131
2017
Later among the works it cites.
Tselil Schramm and David Steurer, Fast and robust tensor decomposition with applications to dictionary learning , COLT, Proceedings of Machine Learning Research, vol. 65, PMLR, 2017, pp. 1760–1793
2017
Later among the works it cites.
Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart, List-decodable robust mean estimation and learning mixtures of spherical gaussians mixture models, robustness, and sum of squares proofs , STOC, ACM, 2018, p. (to appear)
2018
Closest in time.
Sam B. Hopkins and Jerry Li, Mixture models, robustness, and sum of squares proofs , STOC, ACM, 2018, p. (to appear)
2018
Closest in time.
Pravesh K. Kothari, Jacob Steinhardt, and David Steurer, Robust moment estimation and improved clustering via sum-of-squares , STOC, ACM, 2018, p. (to appear)
2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…