On Bilevel Optimization without Full Unrolls: Methods and Applications

Bilevel optimization (BLO) problems are nested optimization problems where an outer objective must be minimized subject to the optimality of an inner objective. This nested structure poses several challenges, including the cost of running full unrolls of the inner problem for each outer parameter update. We discuss several approaches which allow for efficient bilevel optimization, that do not require full inner unrolls. 1. Challenge: Inner optimization is expensive and needs to be re-run for each outer parameter update. We introduce Self-Tuning Networks (STNs), an approach that learns a parametric approximation to the best-response function online, amortizing the inner loop optimization. STNs address the two main challenges to fitting a best-response approximation: 1) STNs fit the approximation locally around the current outer parameters, and alternate between updating the outer parameters and updating the best-response approximation, and 2) STNs use a structured hypernetwork to represent the best-response, that scales to large neural networks. 2. Challenge: Long unrolls of the inner optimization can lead to chaotic meta-loss landscapes; short unrolls can lead to truncation bias. To address both of these issues, we introduce Persistent Evolution Strategies (PES), an approach for computing unbiased gradient estimates of parameters that govern a dynamical system, using only partial unrolls of the system. PES estimates the gradient of a Gaussian-smoothed objective, allowing for optimization over chaotic landscapes. 3. Challenge: Most research in BLO assumes that the solutions to the inner and outer problems are unique, but in practice typically either the inner or outer problems are underspecified. In this case, there are many ways to choose among equivalent optima, potentially leading to different results. In this part, we investigate the implicit bias of commonly-used algorithms in overparameterized bilevel optimization. 4. Finally, we introduce Amortized Proximal Optimization (APO), a framework for online meta-optimization of a parametric update rule which governs optimization. APO is based on a 1-step lookahead meta-objective. Under appropriate assumptions, APO can recover existing optimization algorithms such as natural gradient descent. We present two use-cases of APO: 1) tuning a structured preconditioning matrix; and 2) tuning the global learning rate of several base optimizers.

Department dc:contributor.department

Computer Science

Year dc:date.issued

2023

Author dc:creator

• Vicol, Paul Adrian

Advisor dc:contributor.advisor

• Grosse, Roger B

• bilevel optimization
• hyperparameter optimization
• machine learning

Statement dc:rights

• Attribution 4.0 International

Licence dc:rights.uri

• http://creativecommons.org/licenses/by/4.0/

Handle dc:identifier.uri

http://hdl.handle.net/1807/126835

OAI identifier oai:identifier

oai:utoronto.scholaris.ca:1807/126835