CAREER: Foundations of Scalable Nonconvex Min-Max Optimization

该奖项全部或部分根据2021年美国救援计划法案（公法117-2）资助。机器学习和数据科学领域的最新进展受到强大计算工具和高效算法的发展的深刻影响。然而，不断训练最新的机器学习模型需要开发新的算法和技术，以解决更大规模的日益复杂的问题。该项目关注现代数据科学的许多重要应用中出现的特定类别的最小-最大优化问题，例如，训练不对具有某些敏感属性的个体有偏见的公平ML模型，设计可靠地执行输入数据变化的AI系统，以及训练用于生成人工音乐的ML模型。研究议程的重点是开发新的算法，以解决与此类最小-最大问题相关的各种计算问题;它将提供一个自然的工具来创建教育内容，并为本科生和研究生提供指导机会。一个核心组成部分是通过南加州大学社区学术倡议（NAI）和南加州大学维特比K-12 STEM中心向高中生推广;这些计划为南加州面临系统性不平等的K-12学校和教师提供服务。主要的技术目标是为（随机）非凸最小-最大优化问题开发理论基础和可扩展算法。这些努力将解决与这些非凸模型的鲁棒操作相关的几个长期存在的开放问题。将特别注意设计可证明有效的算法计算一阶固定的解决方案，某些结构化的非凸（随机）最小最大问题，目前没有算法与多项式迭代复杂性是已知的存在。设想的算法利用目标函数和约束集的结构，利用数值微分领域的最新进展，并探索计算平台提供的存储器和处理能力的权衡。寻找固定解决方案所需的基本最小计算工作量将在不同的场景下进行研究，这些场景由广泛的应用程序驱动，例如强大的机器学习，公平的统计推断和训练生成模型，该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准。

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 that face systemic inequities. 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.