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

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.