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

优化在现代数据分析中起着至关重要的作用。对复杂数据集的精确建模和稳健分析通常需要解决一类不光滑的优化问题，并且可能具有许多低质量的解。这些问题很难解决，而且对标准算法返回的解的性质的了解有限。现有的方法通常会避开此类问题，或者将其局限于其中的一小部分。这个项目的目的是大大拓宽问题的类别，对于这些问题，存在有效的算法，并且可以获得性能保证。该项目将开发适用于广泛的工程和科学应用的新算法和分析工具。此外，该项目将支持一项教育计划，其中心目标是在本科生和研究生水平上连接优化和统计学学科，该项目的技术方法基于非光滑和非凸性脱钩的一般原则，并确定局部最优解的特征结构。该研究计划包括两个主要方面：(1)研究一类非光滑复合优化问题，建立一个量化问题的平均条件和低复杂度算法收敛速度的框架；(2)考虑一类具有耦合分量的问题，刻画局部极小点的隐含结构，并利用这些结构结果来设计和分析在现有结果不适用的情况下的有效算法。这个项目的研究将涵盖一系列重要的统计和机器学习问题。开发的技术将为统计环境中的平均案例问题提供算法性能的精细分析。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.