CAREER: Optimal High-Dimensional Estimators Using Sum-of-Squares Proof Systems

Stanford University, Stanford CA

Investigators

Abstract

Statistical estimation problems are ubiquitous in the modern world. A multitude of important machine-learning tasks fall under the umbrella of estimation, including regression, principal components analysis, and clustering. In the sciences more broadly, estimating parameters from data is crucial to the pursuit of knowledge: in Biology, estimating protein network structure; in Astronomy and Physics, estimating the spatial locations of stellar objects from diffraction patters; in Biochemistry, estimating the three-dimensional structure of a protein from spectroscopy and imaging data; and so on. In high-dimensional settings, where the quantities to be estimated describe large, complicated systems, the role of efficient computation is crucial. Despite the ubiquity of high-dimensional statistical estimation problems, understanding of their computational landscape remains primitive. The goal of this project is to develop and characterize optimal estimation algorithms through the lens of the sum-of-squares (SoS) algorithm and proof system. The sum-of-squares algorithm is a powerful class of semidefinite programming algorithms which are among the most powerful known algorithms (empirically and in a precise sense), while their relationship to the sum-of-squares proof system also allows for a systematic approach to algorithm design. The project is organized into three primary thrusts: (i) predicting the computational limits of statistical estimation with SoS, giving a unified theory for automatically predicting the computational limits of our most powerful algorithms; (ii) giving optimal algorithms for estimation via SoS for important problems such as clustering, graphical models, and block models; (iii) making sum-of-squares algorithms practical, replacing optimization over SoS programs with lightweight algorithms. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.