CAREER: Foundations of Scalable Nonconvex Min-Max Optimization

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

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.