Collaborative Research: CIF: Small: New Theory, Algorithms and Applications for Large-Scale Bilevel Optimization

近年来，世界在新兴领域的优化方面取得了重大进展，包括元学习、微调、自动超参数选择、持续学习、公平批量选择、对抗性学习和人工智能（AI）感知通信网络。这些领域的问题往往表现出一个共同的嵌套优化结构，这激发了双层优化的研究。然而，在大规模双层优化问题中存在许多理论和计算挑战，例如，那些由机器学习产生的大量数据在高维特征域具有多种约束。这个项目将提供一个全面的研究双层优化理论，算法和应用程序的大规模问题。该项目的成果将使学术界，政府实验室和工业界的研究人员受益，旨在解决科学和工程中的大规模嵌套优化问题。将研究信息科学，信号处理，通信，统计和机器学习的新应用。该项目由三个相互交织的重点组成。第一个推力的重点是开发快速和可扩展的Hessian免费的双层算法的收敛速度保证。具体而言，几个海森自由的方法将设计和分析使用的方法，完全单回路的动量，有限差分矩阵矢量估计，和剩余响应雅可比估计。第二个推力的目的是开发原始-对偶，原始和悲观的双层方法，除了在困难的情况下，没有唯一的低层次的解决方案存在的收敛性分析。在第三个推力，研究人员将开发解决非线性流形上的双层问题的算法，并分析这些算法的相关收敛性。开发的算法将在真实世界的应用环境中实施，包括公平意识机器学习，持续学习，通信网络上的资源分配，主成分分析的超参数选择和字典学习模型。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

In recent years, the world has witnessed significant progress in optimization for emerging fields, including meta-learning, fine-tuning, automated hyperparameter selection, continual learning, fair batch selection, adversarial learning, and artificial intelligence (AI)-aware communication networks. Problems arising from these fields often exhibit a common nested optimization structure, which has motivated the study of bilevel optimization. However, there are many theoretical and computational challenges in large-scale bilevel optimization problems, e.g., those arising from machine learning on massive amounts of data in high-dimensional feature domains that have manifold constraints. This project will provide a comprehensive study of bilevel optimization theory, algorithms, and applications for large-scale problems. The outcomes of this project will benefit researchers in academia, government labs, and industry aiming to solve large-scale nested optimization problems in science and engineering. New applications in information science, signal processing, communications, statistics, and machine learning will be studied. This project consists of three intertwined thrusts. The first thrust focuses on developing fast and scalable Hessian-free bilevel algorithms with convergence rate guarantees. Specifically, several Hessian-free approaches will be designed and analyzed using methods of fully single-loop momentum, finite-difference matrix-vector estimation, and residual response Jacobian estimation. The second thrust aims to develop primal-dual, primal, and pessimistic bilevel methods, in addition to the analysis of convergence in the difficult case where no unique lower-level solution exists. In the third thrust, the investigators will develop algorithms for solving bilevel problems on non-linear manifolds and analyze the associated convergence of these algorithms. The developed algorithms will be implemented in the context of real-world applications, including fairness-aware machine learning, continual learning, resource allocation over communication networks, hyperparameter selection of principal component analysis, and dictionary learning models.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.