CAREER: Blessing of Nonconvexity in Machine Learning - Landscape Analysis and Efficient Algorithms

Regents Of The University Of Michigan - Ann Arbor, Ann Arbor MI

Investigators

Abstract

The tractability of an optimization problem is often assessed by whether it can be written as a convex program. Yet recent years have witnessed a shift in perspective on what is deemed tractable in optimization: with nonconvex models being used almost exclusively in modern machine learning (ML), it has become increasingly clear that convexity can be traded for representation or flexibility. However, harnessing this power comes at steep costs. First, classical optimization theory asserts that in the absence of convexity, efficient large-scale algorithms generate solutions that may not enjoy any optimality guarantee, which can be detrimental in safety-critical applications of ML. Second, many modern nonconvex optimization problems are overwhelmingly large with outrageously high computational costs. This voracious appetite for computing power makes it difficult to unlock the full representation power of nonconvex models, especially in domains that lack access to substantial computing resources. The goal of this project is to lower the above costs by designing reliable and efficient computational methods for training nonconvex models in ML. In particular, this project aims to uncover the distinct structures of the nonconvex problems in ML that make them tractable, ultimately transmuting nonconvexity from a curse to a blessing. The project will integrate a variety of educational programs for K-12, undergraduate, and graduate students. Notably, new partnerships will be forged with under-resourced schools to help introduce new college opportunities to students from low-income families. To broaden the impact of these programs, the experiences will be shared with different communities in the form of short articles. Furthermore, all the materials will be made available for public use. This project aims to bridge a longstanding gap between optimization and statistical learning. While modern statistical learning favors nonconvex models for their favorable generalization and representation properties, classical optimization theory argues that practical algorithms inevitably struggle to recover globally optimal solutions in nonconvex scenarios. This project challenges the conventional paradigm that evaluates the performance of optimization algorithms solely based on their ability to find global optima. In fact, this project will assert that numerous practical nonconvex models in ML, from low-rank matrix recovery to deep neural networks, possess local solutions that are not only more tractable to obtain than their global counterparts, but also closer to the true solutions, yielding smaller generalization errors. This project aims to formalize this fundamental insight by conducting a systematic analysis of the optimization landscape of nonconvex models around the true solutions, and designing reliable and efficient algorithms to solve them in meaningful settings and scales. 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.