CAREER: Embracing Local Minima and Nonsmoothness in Nonconvex Statistical Estimation: From Structures to Algorithms

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

Optimization plays a crucial role in modern data analysis. Accurate modeling and robust analysis of complex datasets often require solving a class of optimization problems that are not smooth and may possess many low-quality solutions. These problems are challenging to solve, and there is limited understanding of the properties of solutions returned by standard algorithms. Existing approaches typically steer away from such problems or restrict to a small subset of them. This project aims to substantially broaden the class of problems for which efficient algorithms exist, and for which performance guarantees can be obtained. The project will develop new algorithms and analytical tools that are applicable in a broad range of engineering and science applications. Furthermore, the project will support an education plan that centers around the goal of bridging the disciplines of optimization and statistics at both undergraduate and graduate levels. The technical approaches of this project are based on the general principles of decoupling nonsmoothness and nonconvexity, and identifying the characteristic structures of locally optimal solutions. The research program consists of two main thrusts: (1) study a class of nonsmooth composite optimization problems and develop a framework for quantifying the average-case conditioning of the problems and the convergence rates of low-complexity algorithms; (2) consider a class of problems with coupled components, characterize the hidden structures of the local minima, and exploit these structural results to design and analyze efficient algorithms in settings where existing results fail to apply. The research in this project will cover a diverse set of important statistical and machine learning problems. The techniques developed will provide a refined analysis of the algorithmic performance for average-case problems in statistical settings. 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.