CAREER: Foundations of Scalable Nonconvex Min-Max Optimization

University Of Southern California, Los Angeles CA

Investigators

Abstract

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2). Recent advances in the fields of Machine Learning and Data Science have been profoundly influenced by the development of powerful computational tools and efficient algorithms. However, training the latest Machine Learning models continuously necessitates that new algorithms and techniques be developed to solve increasingly complex problems at much larger scales. This project is concerned with particular classes of min-max optimization problems as they arise in many important applications of modern Data Science, e.g, training fair ML models that are not biased against individuals with certain sensitive attributes, designing AI systems that reliably perform against changes in the input data, and training ML models for generating artificial music. The research agenda focuses on developing new algorithms to solve various computational issues associated with such min-max problems; it will provide a natural vehicle to create educational content, and foster mentoring opportunities for undergraduate and graduate students. A central component is outreach to high school students via the USC Neighborhood Academic Initiative (NAI) and the USC Viterbi K-12 STEM Center; these programs serve K-12 schools and teachers in Southern California. The main technical aim is to develop both theoretical foundations and scalable algorithms for (stochastic) non-convex min-max optimization problems. The efforts will address several longstanding open questions related to the robust operation of these non-convex models. Special attention will be given to designing provably efficient algorithms for computing first-order stationary solutions of certain structured non-convex (stochastic) min-max problems for which currently no algorithm with polynomial iteration complexity is known to exist. The envisioned algorithms exploit the structure of the objective function and of the constraint sets, leverage recent advances in the field of numerical differentiation, and explore tradeoffs in memory and processing capabilities offered by computational platforms. The fundamental minimum computational efforts required for finding stationary solutions will be studied under different scenarios motivated by a wide range of applications such as robust machine learning, fair statistical inference, and training generative models, and the research outcomes are expected to have an impact on these applications. 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.