Source-linked AI summary
Hyperparameter optimization with approximate gradient
Fabian Pedregosa
TL;DR
Choosing hyperparameters is important for model accuracy but computationally difficult, especially when gradient-based methods require costly exact computations. The paper proposes HOAG, which optimizes continuous hyperparameters using approximate gradients before inner model parameters fully converge, and establishes convergence conditions while reporting competitive empirical benchmarks.
Problem
Hyperparameter selection must optimize a model-quality criterion different from the fitting cost, while existing searches can scale poorly and exact hyperparameter gradients are computationally demanding.
Method
HOAG uses approximate gradient information from inexact inner optimization and linear-system solutions to update continuous hyperparameters by projected gradient descent.
Results
The method is compared with state-of-the-art methods for estimating regularization and kernel parameters on two models and three datasets.
Takeaways & Limitations
Approximate-gradient updates provide a gradient-based route to hyperparameter optimization while avoiding the requirement that model parameters and derivative computations be fully exact at every iteration.
Takeaways & Limitations
HOAG is not guaranteed to decrease monotonically, may oscillate when tolerance decreases mismatch convergence rates, and can get stuck in flat regions.
Abstract
from arXiv · showhide
Most models in machine learning contain at least one hyperparameter to control for model complexity. Choosing an appropriate set of hyperparameters is both crucial in terms of model accuracy and computationally challenging. In this work we propose an algorithm for the optimization of continuous hyperparameters using inexact gradient information. An advantage of this method is that hyperparameters can be updated before model parameters have fully converged. We also give sufficient conditions for the global convergence of this method, based on regularity conditions of the involved functions and summability of errors. Finally, we validate the empirical performance of this method on the estimation of regularization constants of L2-regularized logistic regression and kernel Ridge regression. Empirical benchmarks indicate that our approach is highly competitive with respect to state of the art methods.
1. Introduction
Hyperparameter optimization selects continuous controls for model complexity using a criterion distinct from the model-fitting cost, but gradient computation can be a major bottleneck. The paper formulates this as a bilevel problem and proposes approximate-gradient optimization with convergence conditions.
- Hyperparameters control model complexity, and this work focuses on continuous choices such as regularization parameters and RBF-kernel widths.
- Hyperparameter optimization uses model-quality criteria such as cross-validation loss rather than the cost function used to fit model parameters.Optimizing the fitting loss directly would favor excessive model complexity, including models with no regularization.
- Grid search scales poorly and fits models at unpromising hyperparameter values, while random search explores faster but does not use previous evaluations.
- Gradient-based methods exploit local objective information, but computing hyperparameter gradients is a major bottleneck.
- The paper proposes approximate-gradient hyperparameter optimization and gives sufficient conditions for convergence to a stationary point.The bilevel formulation represents model parameters as minimizers of an inner cost function and differentiates its optimality conditions implicitly.
- Experiments compare the approach with state-of-the-art methods for estimating regularization and kernel parameters across two models and three datasets.
2. HOAG: Hyperparameter optimization with approximate gradient
HOAG balances speed and accuracy by replacing exact hyperparameter gradients with approximations controlled by a tolerance sequence. It computes inexact inner solutions and linear-system solves, then uses the resulting noisy gradient in projected descent.
- HOAG uses a tolerance εk to trade faster approximate-gradient computation against possible slow convergence or divergence.
- At each iteration, HOAG approximately solves the inner optimization problem and a linear system, computes a noisy gradient, and updates hyperparameters by projected gradient descent.
- The algorithm requires an εk-optimal inner solution, first-order derivatives of g, and an εk-optimal solution to a linear system involving ∇2h.
- The linear system can be solved with conjugate gradients using Hessian matrix-vector products, with efficient schemes available for least squares and logistic regression.
- HOAG belongs to implicit differentiation methods while approximating hyperparameter gradients similarly to iterative differentiation methods.
- Unlike sequential model-based approaches that may require strong assumptions about training-curve shapes, HOAG uses gradient-based local information.
3. Analysis
The analysis establishes convergence of HOAG under regularity assumptions and a summable tolerance sequence controlling approximate-gradient errors. It also distinguishes convergence of the gradient mapping from convergence of the hyperparameter iterates themselves.
- Convergence: A summable tolerance sequence is sufficient for HOAG to converge to a stationary point of the hyperparameter objective.The convergence criterion uses the norm of a scaled gradient mapping.
- Assumptions: The analysis assumes smooth derivatives, an invertible inner Hessian at solution points, and a convex compact hyperparameter domain.These conditions cover twice-differentiable losses, strongly convex penalties such as squared ℓ2 regularization, and interval domains.
- Gradient error: The true and approximate hyperparameter gradients differ by O(ε), where ε is the tolerance controlling inner optimization and linear-system errors.This bound is the first step in the convergence proof.
- Scope of the result: The revised analysis establishes convergence of the gradient mapping, not convergence of the hyperparameter iterates λ_k to a limit.The original proof incorrectly claimed iterate convergence, and the statement was edited in 2022.11.
- Convergence: Quadratic tolerances ε_k = k^-2 and exponential tolerances ε_k = ρ^k, with 0 < ρ < 1, are proposed as summable candidates for empirical evaluation.The paper evaluates different tolerance sequences on different problems and datasets.
Experiments
The experiments evaluate HOAG's implementation, tolerance schedules, and comparisons with other hyperparameter optimization methods on regularized logistic regression and kernel Ridge regression. HOAG converges quickly in time because approximate gradients reduce iteration cost, though tolerance mismatch can cause oscillations.
- Implementation: The implementation uses L-BFGS for logistic regression, linear conjugate descent for Ridge regression, and restricts hyperparameters to [−12, 12]^s.The experiments also use an adaptive step-size procedure without a formal analysis for that choice.
- Experimental setup: Experiments evaluate HOAG on ℓ2-regularized logistic regression and kernel Ridge regression across four datasets, including high-dimensional MNIST experiments.20news and real-sim use one hyperparameter, Parkinson uses two, and MNIST uses a high-dimensional hyperparameter space.
- Tolerance decrease strategies: Non-exact methods converge faster overall because their iterations cost less than exact-gradient iterations.Figure 2 compares suboptimality over time for quadratic, cubic, exponential, and exact gradients.
- Tolerance decrease strategies: HOAG is not guaranteed to decrease monotonically, and quadratic and cubic tolerance schedules show oscillations when tolerance reduction mismatches convergence.The experiments also report difficulty progressing beyond the 10^-2 suboptimality level in some methods.
- Comparison with other hyperparameter optimization methods: HOAG and Iterdiff behave similarly in suboptimality, but HOAG has lower per-iteration cost by warm-starting each inner optimization from the previous solution.Iterdiff requires sufficient inner iterations to compute its gradient, whereas HOAG reuses the previous inner solution.
- Comparison with other hyperparameter optimization methods: Fast but noisy HOAG iterations achieve the fastest convergence in two of three datasets on validation loss, while improvements beyond 10^-2 relative suboptimality are not reflected.The validation metric is measured on a third dataset split distinct from the train and test sets.
4. Discussion and future work
The discussion identifies unresolved theoretical and practical issues for HOAG, including solution structure, stochastic extensions, convergence-rate analysis, and flat-region behavior. These limitations define directions for extending the method and its guarantees.
- Open theoretical questions: A stochastic HOAG variant is a natural direction, but the inner Hessian dependence in the implicit equation makes sample-size-independent updates non-trivial.The proposed extension targets stochastic inner and outer updates whose costs do not depend on the number of samples.
- Open theoretical questions: The structure of solutions to the hyperparameter optimization problem remains poorly understood, and current assumption (A3) is used mainly to guarantee solution existence.Characterizing solutions could potentially simplify the paper's assumptions.
- Analysis limitations: The convergence analysis covers constant step sizes rather than the adaptive step-size strategy used in the experiments.The paper also proves asymptotic convergence but does not analyze convergence rates or the optimal tolerance schedule.
- Practical limitations: HOAG can become stuck in flat regions when an initially oversized step reaches a region with nearly zero curvature.The paper points to escaping flat regions and enabling larger early steps as future work.
A. Analysis
The analysis bounds errors introduced by inexact inner solutions and linear-system approximations, then uses summable tolerances to establish convergence of HOAG toward stationary points.
- Gradient error: The gradient error is O(εk) for sufficiently large k, linking the accuracy of the hypergradient to the inner-solver tolerance.This bound is the key ingredient used in the convergence proof.
- Error analysis: The proof compares ideal quantities with their inexact counterparts, including Hessians, outer gradients, and cross derivatives evaluated at approximate inner solutions.The hatted quantities are produced by HOAG, while unhatted quantities represent the zero-tolerance idealization.
- Error analysis: The relevant sequences and inverse Hessian norms are shown to be bounded under the stated regularity, compactness, and domain assumptions.Boundedness supports the subsequent perturbation estimates for the linear systems and gradient approximation.
- Gradient error: The approximate linear-system solution differs from the full-precision solution by a quantity controlled by the tolerance εk.The algorithm solves an approximate system satisfying a residual tolerance rather than computing the exact solution.
- Global convergence: If the tolerance sequence is summable, the HOAG iterates satisfy the stationary-point condition; when they remain in the domain, the gradient norm converges to zero.The proof obtains vanishing step differences and then transfers the result from the approximate gradient to the true gradient mapping.
- Global convergence: The revised theorem establishes convergence of the gradient mapping, not convergence of the hyperparameter iterates themselves.A 2022 update removed the original, incorrect claim that the iterates converge to a limit.
Stopping criterion
The stopping-criterion analysis uses strong convexity and smoothness to control inner-solution accuracy, while the cost-function illustrations show the optimization landscapes considered.
- Tolerance control: The tolerance bound is derived using a lemma for functions that are μ-strongly convex and L-smooth.The lemma relates the function properties to the distance from an arbitrary point to the minimizer.
- Cost functions: Figure 4 plots the cost function f against hyperparameters λ for three problems considered in the experiments.The first two plots use an ℓ2 regularization parameter, while the third varies kernel width and ℓ2 regularization.
- Cost functions: The first two cost-function plots have a unique minimum, whereas the third is a two-hyperparameter surface involving kernel width and ℓ2 regularization.The figure therefore includes both one-dimensional and two-dimensional hyperparameter landscapes.
Adaptive step size
The adaptive step-size procedure combines smoothness with the approximate-gradient error bound and replaces unavailable exact outer-loss values with computable approximate quantities.
- Derivation: The procedure starts from the L-smooth upper-bound inequality and substitutes consecutive hyperparameter iterates λk−1 and λk.The resulting relation involves the step magnitude Δk.
- Derivation: The approximate-gradient estimate ∥∇f(λk)−pk∥< Mεk incorporates the inexact-gradient error into the step-size inequality.The constant M comes from the gradient-error bound.
- Computable quantities: Because exact f(λk) depends on exact model parameters, the procedure substitutes g evaluated at approximate inner solutions and bounds the discrepancy by Cεk.Lipschitz continuity of g supplies the approximation bounds at consecutive iterates.
Datasets
The experiments cover text classification, kernel Ridge regression, and a high-dimensional multinomial logistic-regression problem with 1,440 hyperparameters.
- Datasets: The 20news dataset contains 18,000 posts across 20 topics, converted to binary classification using tf-idf features and random group splits.The task predicts the appropriate binary category for each post.
- Datasets: The real-sim dataset contains 73,218 Usenet articles from four discussion groups for a binary real-versus-simulated categorization task.The groups cover simulated auto racing, simulated aviation, real autos, and real aviation.
- Datasets: The Parkinson dataset contains 5,875 samples with 26 voice-measurement features from 42 people with early-stage Parkinson’s disease.It is used for the kernel Ridge regression problem.
- Datasets: MNIST contains 60,000 samples of images subsampled to 12 × 12 pixels for multinomial logistic regression.The replicated model uses one regularization parameter per feature and class, totaling 12 × 12 × 10 = 1,440 hyperparameters.
Further experimental validation
On MNIST, HOAG outperformed the other methods in a very high-dimensional hyperparameter problem, while validation loss increased as test loss decreased, indicating overfitting.
- HOAG yielded much better results than the other methods on MNIST.
- Only gradient-based hyperparameter optimization methods provided satisfactory results on this very high-dimensional problem.Grid search was excluded because of the hyperparameter space's very high dimensionality.
- Validation loss increased as test loss decreased, providing a clear sign of overfit in the model design.The experiment retained this setting to compare methods similarly to Maclaurin et al. (2015).
- Figure 5 compares methods using test-loss suboptimality in the top row and validation-set loss in the bottom row.