Gradient-Based Optimization Mathematics for Hyperparameters

Learn about gradient-based optimization mathematics for hyperparameters. Understand hypergradients, bilevel optimization, and implicit differentiation.

▶ Open the simulation

Introduction

Gradient-based optimization for hyperparameters requires computing gradients through the training process. This involves bilevel optimization, implicit differentiation, and hypergradient computation.

Bilevel Optimization

Mathematical Formulation

Hyperparameter optimization as bilevel problem:

min_λ L_val(θ*(λ), λ)

Subject to:

θ*(λ) = argmin_θ L_train(θ, λ)

Inner and Outer Optimization

Inner: Model training with fixed λ
Outer: Hyperparameter optimization
Nested optimization structure

Hypergradients

Gradient with Respect to Hyperparameters

∇_λ L_val = ∂L_val/∂λ + (∂L_val/∂θ*) (∂θ*/∂λ)

Computing ∂θ*/∂λ

Key challenge: derivative of optimal parameters:

Implicit function theorem
Chain rule through optimization
Approximation methods

Implicit Differentiation

Implicit Function Theorem

If ∇_θ L_train(θ*, λ) = 0, then:

∂θ*/∂λ = -(∇²_θ L_train)⁻¹ ∇²_θλ L_train

Computational Methods

Forward-mode: Automatic differentiation
Reverse-mode: Backpropagation
Finite differences: Approximation

Hypergradient Descent

Update Rule

λ_{t+1} = λ_t - η ∇_λ L_val(θ*(λ_t))

Challenges

Computational cost
Second-order derivatives
Convergence stability

Approximation Methods

Finite Differences

∂L/∂λ ≈ (L(λ+ε) - L(λ-ε)) / (2ε)

Truncated Backpropagation

Approximate through limited training steps:

Fewer inner iterations
Reduced computation
Approximation error

Key Insight

Gradient-based hyperparameter optimization requires differentiating through training, which is computationally expensive. Implicit differentiation and approximations enable practical methods.

Convergence Analysis

Bilevel Convergence

Requires:

Inner optimization convergence
Stability of hypergradients
Appropriate step sizes

Convergence Rates

Can achieve:

Linear convergence
Faster than gradient-free
Requires differentiability

Frequently Asked Questions

What is bilevel optimization?

Bilevel optimization involves nested problems: outer optimization (hyperparameters) depends on inner optimization (model training). It's formally: min_λ L_val(θ*(λ)) where θ*(λ) = argmin_θ L_train(θ,λ).

What are hypergradients?

Hypergradients are gradients of objective with respect to hyperparameters: ∇_λ L_val. They require computing ∂θ*/∂λ, the derivative of optimal parameters with respect to hyperparameters.

How do I compute hypergradients?

Use implicit differentiation: ∂θ*/∂λ = -(∇²_θ L_train)⁻¹ ∇²_θλ L_train. Or use automatic differentiation through training, finite differences, or approximations.

What is implicit differentiation?

Implicit differentiation computes derivatives when relationship is implicit. For hyperparameters, it uses implicit function theorem to compute ∂θ*/∂λ from optimality condition ∇_θ L_train = 0.

What's the computational cost of hypergradients?

Hypergradients require second-order derivatives and matrix inverses, making them expensive. Approximations and truncated methods reduce cost but introduce approximation error.