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

近年来，世界在新兴领域的优化方面取得了重大进展，包括元学习、微调、自动超参数选择、持续学习、公平批次选择、对抗性学习和人工智能(AI)感知的通信网络。由这些领域产生的问题往往表现出共同的嵌套优化结构，这推动了双层优化的研究。然而，在大规模的两层优化问题中，存在许多理论和计算挑战，例如，在具有多种约束的高维特征域中的大量数据上的机器学习所产生的挑战。该项目将对大规模问题的双层优化理论、算法和应用进行全面研究。该项目的成果将使学术界、政府实验室和行业的研究人员受益，这些研究人员旨在解决科学和工程中的大规模嵌套优化问题。将研究在信息科学、信号处理、通信、统计和机器学习方面的新应用。这个项目由三个相互交织的推力组成。第一个重点是开发具有收敛速度保证的快速、可伸缩的无黑森双层算法。具体地说，将使用完全单环动量、有限差分矩阵向量估计和剩余响应雅可比估计的方法来设计和分析几种无黑森方法。第二个重点是发展原始-对偶、原始和悲观两层方法，以及在不存在唯一低层解的困难情况下的收敛分析。在第三个推力中，研究人员将开发求解非线性流形上的双层问题的算法，并分析这些算法的相关收敛。开发的算法将在真实世界应用的背景下实施，包括公平感知的机器学习、持续学习、通信网络上的资源分配、主成分分析的超参数选择和字典学习模型。该奖项反映了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.