Expanding the Reach of Efficient Algorithms

One of the greatest difficulties in modern data analysis is optimization—arriving at the very best of many possible solutions. Accurate modeling and robust analysis of complex data sets often require solving optimization problems that present a particular challenge: They are not smooth, and they may possess many low-quality solutions. Data scientists have a limited understanding of the properties of solutions that standard algorithms return for this class of problems. Existing approaches typically steer away from nonsmooth, nonconvex problems, or they restrict to a small subset these problems.

With this CAREER award, Yudong Chen, Operations Research and Information Engineering, aims to substantially broaden the class of nonconvex problems for which efficient algorithms exist and for which performance guarantees can be obtained. Two general principles guide Chen’s technical approach: 1) decoupling nonsmoothness and nonconvexity and 2) identifying the characteristic structures of locally optimal solutions. First, Chen is studying a class of nonsmooth composite optimization problems and developing a framework for quantifying the average-case conditioning of the problems and the convergence rates of low-complexity algorithms. Second, he is considering a class of nonconvex problems with coupled components, characterizing the hidden structures of the local minima, and exploiting these structural results to design and analyze efficient algorithms in settings for which existing results fail to apply.

This project will address a diverse set of important statistical and machine-learning problems, developing new algorithms and analytical tools that are applicable in a broad range of engineering and science applications. It will also develop techniques that provide a refined analysis of algorithmic performance for average-case problems in statistical settings.

Cornell Researchers

Funding Received

$542 Thousand spanning 5 years