Abstract Two-level stochastic optimization formulations have become instrumental in a number of machine learning contexts such as continual learning, neural architecture search, adversarial learning, and hyperparameter tuning. Practical stochastic bilevel optimization problems become challenging in optimization or learning scenarios where the number of variables is high or there are constraints. In this paper, we introduce a bilevel stochastic gradient method for bilevel problems with nonlinear and possibly nonconvex lower-level constraints. We also present a comprehensive convergence theory that addresses both the lower-level unconstrained and constrained cases and covers all inexact calculations of the adjoint gradient (also called hypergradient), such as the inexact solution of the lower-level problem, inexact computation of the adjoint formula (due to the inexact solution of the adjoint equation or use of a truncated Neumann series), and noisy estimates of the gradients, Hessians, and Jacobians involved. To promote the use of bilevel optimization in large-scale learning, we have developed new low-rank practical bilevel stochastic gradient methods (BSG-N-FD and BSG-1) that do not require second-order derivatives and, in the lower-level unconstrained case, dismiss any matrix–vector products.

An interface between the application problem and the nonlinear optimization algorithm is proposed for the numerical solution of distributed optimal control problems. By using this interface, numerical optimization algorithms can be designed to take advantage of inherent problem features like the splitting of the variables into states and controls and the scaling inherited from the functional scalar products. Further, the interface allows the optimization algorithm to make efficient use of user-provided function evaluations and derivative calculations.

This paper describes a technique for generating sparse or dense quadratic bilevel programming problems with a selectable number of known global and local solutions. The technique described here does not require the solution of any subproblems. In addition, since most techniques for solving these problems begin by solving the corresponding relaxed quadratic program, the global solutions are constructed to be different than the global solution of this relaxed problem in a selectable number of upper- and lower-level variables. Finally, the problems that are generated satisfy the requirements imposed by all of the solution techniques known to the authors.

This paper describes software for generating test problems for quadratic bilevel programming. The algorithm constructs problems with a number of favorable properties that can be selected and controlled by the user. The intention is to provide a set of FORTRAN 77 routines that can be used for testing, verifying, and comparing solution techniques for these problems.