Source-linked AI summary
Forward and Reverse Gradient-Based Hyperparameter Optimization
Luca Franceschi, Michele Donini, Paolo Frasconi, Massimiliano Pontil
TL;DR
The paper addresses the computational difficulty of optimizing hyperparameters through iterative learning dynamics. It develops reverse- and forward-mode gradient procedures, finding that forward mode supports real-time updates and can make large-scale hyperparameter tuning practical.
Problem
Grid search becomes impractical as hyperparameter dimensionality grows, motivating optimization of hyperparameters that influence an iterative learner's final validation error.
Method
The paper derives reverse- and forward-mode hyperparameter gradients, connecting them to recurrent-network gradient methods and handling the full parameter optimization dynamics.
Results
Forward-mode hyperparameter optimization efficiently enables real-time tuning of crucial hyperparameters in a deep learning model and substantially improves over the vanilla version within a 300-minute budget.
Takeaways & Limitations
For large models with few hyperparameters, forward mode may be preferable to reverse mode, especially when hyperparameters must be updated during training on large datasets.
Takeaways & Limitations
RTHO requires validation across diverse datasets, models, and settings to assess its robustness and ability to find good hyperparameter values.
Abstract
from arXiv · showhide
We study two procedures (reverse-mode and forward-mode) for computing the gradient of the validation error with respect to the hyperparameters of any iterative learning algorithm such as stochastic gradient descent. These procedures mirror two methods of computing gradients for recurrent neural networks and have different trade-offs in terms of running time and space requirements. Our formulation of the reverse-mode procedure is linked to previous work by Maclaurin et al. [2015] but does not require reversible dynamics. The forward-mode procedure is suitable for real-time hyperparameter updates, which may significantly speed up hyperparameter optimization on large datasets. We present experiments on data cleaning and on learning task interactions. We also present one large-scale experiment where the use of previous gradient-based methods would be prohibitive.
1. Introduction
The paper develops gradient-based hyperparameter optimization for iterative learning algorithms, contrasting reverse- and forward-mode hypergradient computation. Forward-mode supports real-time updates and can be advantageous when hyperparameters are few relative to model parameters.
- Motivation: Hyperparameter optimization uses validation performance to construct a response function and search for favorable hyperparameter values.The response function can be based on measures such as average validation loss or misclassification error.
- Motivation: Grid search becomes impractical as hyperparameter dimensionality grows, while Bayesian and sequential model-based methods address costly response evaluations.Random search can outperform grid search, and related methods scale to a few hundreds of hyperparameters.
- Approach: Gradient-based methods optimize validation performance with respect to hyperparameters while accounting for the iterative training procedure.The training objective is often minimized only approximately, so the algorithm’s finite trajectory becomes part of the computation.
- Approach: Reverse-mode requires storing the training trajectory, whereas forward-mode avoids this space cost and is efficient when hyperparameters are much fewer than parameters.The reverse formulation does not require reversible parameter optimization dynamics.
- Real-time updates: Forward-mode mirrors real-time recurrent learning and enables hyperparameter updates during training, potentially accelerating optimization on large datasets.Experiments include automatic tuning of crucial hyperparameters in a deep learning model.
2. Hyperparameter Optimization
The paper models iterative training as a dynamical system whose final state determines validation error, then optimizes constrained hyperparameters affecting the objective and update dynamics.
- Problem formulation: Training is represented as a dynamical system with state st containing weights and possible accessory variables such as velocities or accumulated squared gradients.The update procedure may be stochastic gradient descent, momentum, RMSProp, or Adam.
- Problem formulation: Each iteration applies a smooth update map st = Φt(st−1, λ), where λ contains the hyperparameters to tune.The map represents the operation performed on the t-th mini-batch.
- Example: With gradient descent and momentum, the state contains velocity and weights, while λ includes the learning-rate and momentum parameters.The update uses the objective associated with each mini-batch.
- Problem formulation: The goal is to optimize an error function evaluated at the final iterate sT over a constrained hyperparameter set Λ.The iterates implicitly depend on λ through the training dynamics.
- Scope: Hyperparameters may control the loss, regularization, iterative algorithm, or function class used to fit the training objective.Examples include multiple regularization parameters, learning-procedure settings, neural-network architecture, and kernel parameters.
3. Hypergradient Computation
The paper derives reverse- and forward-mode procedures for computing hypergradients through iterative training. Forward-mode additionally exposes intermediate hypergradients, enabling real-time updates during training.
- Reverse-mode: Reverse-HG propagates adjoint variables backward from the final validation error while accumulating sensitivities to the hyperparameters.The algorithm first runs the training dynamics, then performs a backward pass over iterations.
- Reverse-mode: Reverse-mode derives the hypergradient through a Lagrangian formulation with state-transition constraints.Its backward recursion is structurally identical to back-propagation through time and does not require invertible update maps.
- Forward-mode: Forward-mode propagates the Jacobian of the training state with respect to hyperparameters using the recurrence Zt = AtZt−1 + Bt.The final state Jacobian is combined with the validation-error gradient to obtain the hypergradient.
- Real-time forward-mode: Forward-mode corresponds to real-time recurrent learning and computes partial hypergradients at every training step rather than only at the end.This permits several hyperparameter updates within one optimization epoch or after a hyper-batch of data.
- Real-time forward-mode: The real-time procedure can operate on data streams or large finite datasets by updating hyperparameters periodically while reusing examples.The phone-recognition experiment uses updates after a chosen hyper-batch size.
4. Complexity Analysis
Forward- and reverse-mode hypergradient computation trade time against space. Forward-mode scales with the number of hyperparameters while retaining training-scale space, whereas reverse-mode has training-scale time and space.
- Automatic differentiation: Forward-mode computes a full Jacobian in time O(nc(n, p)) and space O(s(n, p)), while reverse-mode computes it in time O(pc(n, p)) and space O(c(n, p)).These bounds follow from applying forward- or reverse-mode automatic differentiation to unit vector or output-direction products.
- Complexity bounds: Forward-HG runs in time O(Tmg(d, m)) and space O(h(d, m)), where m is the number of hyperparameters.It computes Jacobian-vector products iteratively without retaining the full state trajectory.
- Assumption: The complexity analysis assumes validation-error computation does not affect the bound, which is realistic when validation sets are smaller than training iterations.The assumption is stated explicitly alongside the response-function cost analysis.
- Complexity bounds: Reverse-HG runs in time and space O(Tg(d, m)) because reverse-mode requires access to the full sequence of training states.The transposed-Jacobian-vector products have per-step time O(g(d, m)), but states cannot be overwritten.
- Neural-network example: For neural networks with k weights and O(1) hyperparameters, both methods take time O(Tk), but reverse-mode uses space O(Tk) versus forward-mode O(k).The resulting memory difference can be dramatic for long training trajectories.
5. Experiments
The experiments apply the proposed hypergradient framework to data hyper-cleaning, learning task interactions, and large-scale phone classification. Across these settings, the method identifies corrupted examples, learns task relationships, and enables effective hyperparameter optimization on a model where prior gradient-based methods would be prohibitive.
- 5.1. Data Hyper-cleaning: Data hyper-cleaning assigns one hyperparameter per training example and uses an L1 constraint to suppress the influence of noisy examples.The experiments use MNIST with 2,500 corrupted training labels and optimize example weights through reverse-mode hypergradients.
- 5.1. Data Hyper-cleaning: The hyper-cleaner identifies corrupted examples and reaches almost the same accuracy as an oracle across different L1-radius choices.The reported evaluation includes baseline, oracle, and DH-R test accuracies, plus F1 for detecting corrupted training examples.
- 5.1. Data Hyper-cleaning: Test accuracy continues improving even after the hyper-cleaner begins discarding some clean examples.Initially, discarded examples are mainly corrupted; later, a portion of clean examples is also removed.
- 5.2. Learning Task Interactions: In multitask learning, HMTL improves performance, while adding the L1 constraint on the task-interaction matrix further improves both datasets.The learned matrix can be interpreted as a graph adjacency matrix highlighting relationships between classes, although the result depends strongly on data representations.
- 5.3. Phone Classification: A fixed-epoch, non-real-time run of FORWARD-HG made no appreciable progress after 24 hours on a Titan X GPU.This result motivated evaluating the real-time RTHO setting for the large phone-recognition experiment.
- 5.3. Phone Classification: On TIMIT phone classification, RTHO-NT finds hyperparameters yielding a substantial improvement over the vanilla network within a 300-minute budget.The model has more than 15×10^6 parameters and more than 30×10^6 variables; reverse-mode and approximate prior methods had not been applied at this size.
6. Discussion
The paper presents forward-mode and Lagrangian reverse-mode hypergradient computation as complementary approaches, with forward-mode favored for large models with few hyperparameters and real-time updates. It also reports that RTHO can find good hyperparameters in a large-scale setting where other gradient-based methods were inapplicable, while identifying validation and extension needs.
- Forward-mode hypergradient computation may be preferable to reverse-mode for large models when the number of hyperparameters is small.
- Forward-mode supports real-time hyperparameter updates, which the experiments showed effective for large datasets.
- The Lagrangian reverse-mode derivation provides a general framework for response functions involving the whole parameter optimization dynamics.
- RTHO requires validation across diverse datasets, models, and settings, and extensions to integer or nominal hyperparameters require additional design effort.
- Studying the convergence properties of RTHO remains an important problem.
A. Empirical Validation Of Complexity Analysis
The empirical study compares Forward-HG and Reverse-HG time and space requirements. Forward-HG time grows with the number of hyperparameters while its space remains constant as model size grows; Reverse-HG shows the opposite scaling pattern in these experiments.
- Reverse-HG running time is essentially constant, whereas Forward-HG running time increases linearly when model size is fixed and the number of hyperparameters varies.The experiment used three-layer feed-forward networks on MNIST with T = 1000 iterations and 199210 weights fixed.
- Reverse-HG space complexity grows linearly with the number of parameters, while Forward-HG space complexity remains constant when the number of hyperparameters is fixed.The fixed hyperparameters were learning rate and momentum factor.
Learning Task Interactions
The CIFAR-10 experiment compares state-of-the-art multitask learning methods, with hyperparameters validated by grid search. Both compared methods outperform STL and NMTL but perform slightly worse than HMTL-S.
- Experimental comparison: Table 4 reports CIFAR-10 test accuracy with standard deviations for comparative multitask learning methods.The methods’ hyperparameters were validated by grid search under the same setting as Section 5.2.
- Results: Both compared methods improve over STL and NMTL but perform slightly worse than HMTL-S.
- Interpretation: The compared algorithms treat the task interaction matrix as a model parameter, which may lead to overfitting on the small training set.This contrasts with considering C as a hyperparameter.
- Scope: A complete analysis of multitask learning is beyond the scope of the paper.
Phone Classification
The phone-classification experiments include a sequential model-based hyperparameter optimization baseline using Gaussian processes and expected improvement.
- Optimization setup: Phone classification uses sequential model-based optimization with Gaussian processes and expected improvement as the acquisition function.The method is implemented with the BayesianOptimization Python package and initialized with 5 runs.
- Search space: The tested hyperparameter intervals are η ∈ [10^-5, 1], µ ∈ [0, 0.999], and ρ ∈ [0, 4].
C. On learning rate initialization in RTHO-NT
RTHO-NT initializes its hyperparameters at zero, avoiding prior task knowledge despite starting far from optimal in general. Its first learning-rate update is governed by alignment between validation and stochastic training gradients.
- Initialization: RTHO-NT initially sets its hyperparameters to zero, requiring no previous knowledge of the task.The paper notes that λ = 0 is generally far from optimal in hyperparameter space.
- First update: The first learning-rate update is proportional to the scalar product between the validation-error gradient and averaged stochastic training gradients.The average is taken over minibatches in the first hyper-batch.
- Gradient alignment: A smaller angle between validation and stochastic training-error gradients produces a larger learning-rate update.
- Initialization diagnostic: A negative angle can make the learning rate negative, suggesting that the initial parameter point may be poor.