CIF: Small: Taming Nonconvexity in High-Dimensional Statistical Estimation

Princeton University, Princeton NJ

Investigators

Abstract

Many of today's applications in science and engineering require the efficient information processing of massive data sets in order to extract critical information and actionable insights for reliable decision making. Yet, even with the enormous power of cloud computing, it is computationally infeasible for classical statistical algorithms to process and analyze the massive amount of data generated daily. At the core of such challenges is the mathematical concept of 'non-convexity', that permeates contemporary information processing tasks. Due to the highly complex nature of data acquisition mechanisms, classical statistical estimators often require the solution of highly non-convex optimization problems. Current theory predicts that such tasks can be daunting to solve in the worst-case, yet simple iterative algorithms like gradient descent are used thousands of times every day to solve highly non-convex problems with remarkable empirical success. This huge gap between theory and practice needs to be bridged, and the goal of this project is to do so by developing new theory that better explains and predicts the performance of non-convex optimization algorithms. The impact of this new theory will be felt by virtue of creating a foundational understanding of non-convexity and will suggest novel ways to tackle some of the hard practical problems that feature non-convexity as well. This research project plans to address these pressing challenges by investigating low-complexity non-convex optimization methods that enable efficient statistical estimation. The main goal is to demystify the unreasonable effectiveness of simple optimization algorithms through a novel combination of ideas from statistics and optimization, offering scalable statistical estimation solutions that are of immediate value to guide scientific discovery. In particular, the objective of this research project is four-fold: (1) Understand why random initialization suffices for solving important non-convex statistical problems; (2) Understand why simple optimization algorithms are guaranteed to work even without sophisticated regularization; (3) Investigate how to reduce the undesired variability of optimization algorithms in the sample-starved regime; and (4) Study the effectiveness and benefits of simple spectral methods. The algorithms and techniques to be developed in this project will significantly enhance signal processing capabilities beyond the state-of-the-art methods. 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.