CAREER: Foundations of Scalable Nonconvex Min-Max Optimization

该奖项的全部或部分资金来自《2021年美国救援计划法案》(公法117-2)。强大的计算工具和高效算法的发展对机器学习和数据科学领域的最新进展产生了深远的影响。然而，不断地训练最新的机器学习模型需要开发新的算法和技术来在更大的范围内解决日益复杂的问题。该项目涉及在现代数据科学的许多重要应用中出现的特定类别的最小-最大优化问题，例如，训练对具有某些敏感属性的个人没有偏见的公平的ML模型，设计针对输入数据的变化而可靠地执行的人工智能系统，以及训练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.