Source-linked AI summary
Bilevel Programming for Hyperparameter Optimization and Meta-Learning
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, Massimilano Pontil
TL;DR
The paper addresses the gap between hyperparameter optimization and meta-learning by formulating both as bilevel programs. It solves an approximate bilevel problem by unrolling inner optimization dynamics, establishes convergence conditions, and reports effective few-shot meta-learning results with shared learned representations.
Problem
Hyperparameter optimization and meta-learning use related nested searches but have historically been treated as largely separate frameworks.
Method
The paper formulates both settings as bilevel programs and approximates inner optimization by explicitly unrolling its iterative dynamics.
Results
The iterative approach has convergence guarantees under a unique inner solution, and the meta-learning instantiation is experimentally effective.
Takeaways & Limitations
Shared representation parameters can serve as outer variables while task-specific classifiers are optimized inside each episode.
Takeaways & Limitations
The convergence assumptions may not hold for some inner learning algorithms, motivating further theoretical investigation.
Abstract
from arXiv · showhide
We introduce a framework based on bilevel programming that unifies gradient-based hyperparameter optimization and meta-learning. We show that an approximate version of the bilevel problem can be solved by taking into explicit account the optimization dynamics for the inner objective. Depending on the specific setting, the outer variables take either the meaning of hyperparameters in a supervised learning problem or parameters of a meta-learner. We provide sufficient conditions under which solutions of the approximate problem converge to those of the exact problem. We instantiate our approach for meta-learning in the case of deep learning where representation layers are treated as hyperparameters shared across a set of training episodes. In experiments, we confirm our theoretical findings, present encouraging results for few-shot learning and contrast the bilevel approach against classical approaches for learning-to-learn.
1. Introduction
The paper presents hyperparameter optimization and meta-learning as closely related nested search problems, then unifies them through bilevel programming. It also introduces an iterative approximation with theoretical guarantees and demonstrates a deep-learning meta-learning instantiation.
- Motivation: Hyperparameter optimization and meta-learning both seek configurations that make an optimized learning algorithm generalize well to new data.Meta-learning additionally searches choices associated with the hypothesis space and learning algorithm itself.
- Motivation: Hyperparameter optimization typically uses one task with training and validation splits, whereas meta-learning samples few-shot episodes from a distribution over tasks.This distinction is primarily experimental; both settings retain a nested optimization structure.
- Contribution: The paper unifies hyperparameter optimization and meta-learning as bilevel programs, with outer variables controlling hyperparameters or shared representations and inner variables solving task-level learning problems.The framework also encompasses existing initialization- and optimization-based meta-learning strategies.
- Contribution: The authors provide sufficient conditions for the iterative bilevel approximation to have good approximation properties when inner solutions are obtained numerically.The paper states that these conditions are reasonable and apply to concrete application problems.
- Contribution: For deep-learning meta-learning, representation weights are treated as outer variables and last-layer weights as inner variables, yielding strong MiniImagenet performance against most existing strategies.This instantiation follows representation-learning ideas from multi-task and meta-learning.
2. A bilevel optimization framework
The framework defines hyperparameter optimization and meta-learning as bilevel problems whose outer objective evaluates models produced by an inner optimization. It approximates the inner solution by unrolling optimization dynamics, enabling hypergradient-based optimization of large hyperparameter spaces.
- Bilevel formulation: Bilevel programming minimizes an outer objective subject to the optimality of an inner objective parameterized by outer variables.The paper denotes these as E for the outer objective and L_λ for the inner objective.
- Hyperparameter Optimization: In hyperparameter optimization, hyperparameters control the model or regularization while the inner problem minimizes empirical loss and the outer problem minimizes validation error.For ridge regression, the bilevel problem optimizes the regularization parameter using validation error.
- Meta-Learning: In meta-learning, task-specific parameters solve inner training objectives while shared hyperparameters are selected using validation errors averaged across tasks.Training and validation splits are distinct within each task, and the goal is performance on novel tasks.
- Gradient-Based Approach: The approximate procedure unrolls T optimization steps, with each update represented by a smooth mapping such as gradient descent.The initialization and update mappings define the optimization trajectory used by the outer objective.
- Approximation quality: The approximation can fail to track the exact bilevel solution when inner optimization converges to a minimizer that does not minimize the outer objective; uniqueness of the inner minimizer restores convergence guarantees.The procedure's quality therefore depends on the inner problem and its optimization dynamics.
- Gradient-Based Approach: Unrolled dynamics allow hypergradients to be computed through reverse- or forward-mode differentiation, supporting hyperparameter counts comparable to model-parameter counts.The outer variables may also include optimization choices such as step sizes or momentum factors.
3. Exact and Approximate Bilevel Programming
The paper establishes existence and convergence results for approximate bilevel optimization, while identifying when finite optimization dynamics may fail to approximate the exact problem. Under stronger conditions such as unique inner minimizers or uniform convergence, approximate minimizers converge appropriately.
- Approximation limits: The approximate procedure may fail because optimization dynamics can converge to an inner minimizer that does not minimize the outer objective.With nonunique inner solutions, the limiting approximate objective can exceed the exact bilevel objective.
- Convergence: Approximate problems converge variationally toward the exact bilevel problem, including their minima and sets of minimizers.Because the objectives are nonconvex, minimizer sets may be nonsingleton and require an appropriate notion of set convergence.
- Existence: Problem (7) admits solutions under Assumptions (i)–(iv).
- Convergence: Under the convergence assumptions, argmin fT converges to argmin f.
- Conditions: The assumptions used for the theoretical results are described as natural and satisfied by many practically relevant problems.
- Convergence: Strong convexity enables linear convergence of many gradient-based inner solvers and uniform convergence of wT,λ to wλ.A uniform rate follows when the gradient Lipschitz constants are uniformly bounded and strong-convexity moduli are uniformly positive.
4. Learning Hyper-Representations
The paper applies bilevel programming to few-shot meta-learning by learning a shared representation across episodes while training task-specific models in an inner loop. It computes approximate outer gradients through the inner optimization dynamics and compares this approach with alternative learning-to-learn strategies.
- Bilevel formulation: Each episode is split into training and validation sets so representation parameters are optimized through a bilevel meta-learning problem.
- Shared representations: The method learns a cross-task representation hλ and trains task-specific models gj on top of it.The final model for task j is formed by composing the task-specific model with the shared representation.
- Optimization: Task-specific weights are learned for T gradient-descent iterations, and an extended reverse-hypergradient procedure computes the approximate outer gradient.
- Optimization: A stochastic outer-gradient approximation is obtained by sampling mini-batches of episodes from the meta-training set.
- Comparison with prior strategies: Unlike memorization and metric strategies, the method does not require support-set lookups and focuses on the hypothesis space rather than tuning the optimization algorithm.
5. Experiments
Experiments examine approximate bilevel optimization, few-shot learning, and representation-learning variants. They show that inner optimization length affects approximation, generalization, convergence, and runtime, while learned shared representations perform competitively on benchmark tasks.
- The Effect of T: Small T can improve generalization despite yielding a less accurate approximation of the inner solution.As T increases, approximate solutions approach the true bilevel solution, but smaller T can act as an implicit regularizer and improve test performance.
- The Effect of T: The hypergradient algorithm has runtime linear in T and the size of w, independent of the size of H.This scaling makes reducing the number of inner optimization steps particularly attractive when the outer variable is large.
- Few-shot Learning: The experiments evaluate the method on Omniglot and MiniImagenet using episodic meta-training, validation, and test splits.Episodes contain training examples for fitting task-specific classifiers and validation examples for computing the outer objective or estimating generalization.
- Few-shot Learning: The method learns a shared representation and trains multinomial logistic classifiers with few examples per task.Representation mappings use convolutional or residual architectures, while the inner task losses are cross-entropy and the number of gradient steps T is validated.
- Few-shot Learning: RN improves over C4L by 6.5% on one-shot and 4.2% on five-shot MiniImagenet learning.The results associate more expressive residual representations with competitive performance without the overfitting reported for other methods.
- On Variants of Representation Learning Methods: Training/validation splitting and full hypergradient computation are key factors for learning a good representation in the reported variants.The comparison also finds pretrained representations, particularly in low-dimensional spaces, to be an effective baseline.
6. Conclusions
The paper formulates hyperparameter optimization and meta-learning as bilevel problems solved by iterative methods. Under a unique-inner-solution condition, the approach has convergence guarantees and yields an experimentally effective method for learning hyper-representations.
- Both hyperparameter optimization and meta-learning can be formulated as bilevel programs and solved with an iterative approach.
- When the inner problem has a unique solution, such as under strong convexity, the iterative approach has convergence guarantees.
- For meta-learning, the framework adapts training/validation splitting to learn hyper-representations, producing an experimentally effective method supported by the theoretical guarantees.
- The framework suggests new inner-learning design patterns, but some resulting inner problems may violate the assumptions required by the convergence analysis.
- Future work includes studying the statistical properties of bilevel strategies whose outer objectives measure generalization on validation data.
A. Proofs of the Results in Sec. 3
The proofs establish convergence of approximate bilevel objectives and their minimizers under compactness, continuity, uniform convergence, and related regularity conditions.
- For continuity of the exact outer objective, boundedness of inner solutions provides a convergent subsequence whose limit minimizes the limiting inner objective.
- Uniform convergence of lower-semicontinuous approximate objectives on a compact domain yields convergent minimizing subsequences and convergence of their objective values.
- Under the stated assumptions, the infima of the approximate objectives converge to the infimum of the exact objective.
- The proof uses compactness to obtain convergent subsequences and uniform convergence to show that their limits minimize the exact objective.
- Uniform Lipschitz continuity and assumption (vi) imply that fT converges uniformly to f, after which the convergence theorem supplies the result.
B. Cross-validation and Bilevel Programming
The approximate bilevel framework extends to cross-validation by treating cross-validation error as the outer objective and fold-specific training problems as inner objectives.
- K-fold cross-validation can be represented within the approximate bilevel framework, including leave-one-out cross-validation.
- The cross-validation error serves as the outer objective, while regularized empirical errors over folds define the inner objectives.
- In this formulation, the meta-distribution collapses to the ground-data distribution, with episodes sampled from the same dataset.
- The procedure trains K models for T optimization steps and computes a hypergradient using forward or reverse differentiation.
- Models may be fitted sequentially, in parallel, or stochastically by sampling folds or mini-batches of folds for stochastic hypergradients.
C. The Effect of T: Ridge Regression
The ridge-regression experiment examines how the number of inner optimization iterations T affects validation and test performance. Increasing T improves outer-objective optimization, but the test-optimal value is problem dependent.
- Increasing T improves optimization of the outer objective because the approximations fT converge uniformly to f.
- Overfitting can make larger T fail to improve test scores, and a small T produced the best test accuracy in the linear hyper-representation experiment.
- The experiment uses 90 noisy synthetic points with 30 features, only 5 informative, split equally into training, validation, and test sets.
- The outer objective is validation mean squared error, while the optimized outer variables are an L2 vector of regularization coefficients equivalent to a diagonal Tikhonov matrix.
- 250 inner iterations yield the best test result in the ridge-regression setting, where overfitting is not an issue.
- Table 5 reports validation and test mean absolute percentage error for various values of T.
D. Further Details on Few-shot Experiments
The few-shot experiments use specified optimization settings and distinct representation mappings for Omniglot and Mini-imagenet. The appendix details Adam optimization, episode batch sizes, classifier learning rates, and the architectures used.
- Representation mappings are optimized with Adam at learning rate 10^-3 and decay-rate 10^-5, using Glorot and Bengio initialization for representation weights λ.
- Omniglot: Omniglot uses meta-batches of 32 episodes for five-way and 16 episodes for 20-way experiments, with episode-specific classifier learning rate 0.1.
- Mini-imagenet: One Mini-imagenet setup uses C4L, a four-layer convolutional hyper-representation with 32 filters per layer, batch normalization, ReLU, and 2x2 max-pooling.
- Mini-imagenet: The C4L Mini-imagenet classifiers use batches of 4 episodes for one-shot and 2 episodes for five-shot, with learning rate 0.01.
- Mini-imagenet: A second Mini-imagenet setup uses a Residual Network with four residual blocks containing 64, 96, 128, and 256 filters.