Bilevel Ridge Hypergradient

Hyperparameter optimization can be formulated as a bilevel optimization problem. The inner problem trains the model parameters (like weights) given fixed hyperparameters (like regularization penalty). The outer problem evaluates the trained model on a validation set. By differentiating through the exact inner solution, we can compute a hypergradient to tune the hyperparameters using gradient descent.

Worked Example: Overfit with Penalty λ = 1

Consider an inner scalar ridge regression with training inputs X = [1, 2] and targets Y = [2, 4] (the "Overfit" data). The regularization penalty is λ = 1. The validation target is Y_val = 1 at X_val = 1. We can calculate the exact inner optimum and the resulting validation hypergradient as follows:

1. Inner Training Data (Overfit):
   X = [1, 2]
   Y = [2, 4]
   Sxx = Σ(x_i²) = 1² + 2² = 5
   Sxy = Σ(x_i * y_i) = 1*2 + 2*4 = 2 + 8 = 10

2. Inner Optimum (θ*):
   Hessian (H) = Sxx + λ = 5 + 1 = 6
   θ* = Sxy / H = 10 / 6 = 1.6666666666666667

3. Coefficient Sensitivity (dθ/dλ):
   dθ/dλ = -Sxy / H² = -10 / 36 = -0.2777777777777778

4. Validation Loss (J):
   X_val = 1, Y_val = 1
   J = 0.5 * (θ* * X_val - Y_val)²
   J = 0.5 * (1.6666666666666667 - 1)² = 0.5 * (0.6666666666666667)² = 0.2222222222222222

5. Validation Hypergradient:
   dJ/dλ = (θ* * X_val - Y_val) * X_val * (dθ/dλ)
   dJ/dλ = (1.6666666666666667 - 1) * 1 * (-0.2777777777777778)
   dJ/dλ = 0.6666666666666667 * (-0.2777777777777778) = -0.18518518518518517

Experimenting with the Bilevel Optimization

You can interact with the Bilevel Ridge Hypergradient module to observe how hypergradients guide penalty selection.

Change the Data control to "Overfit". Observe that the validation loss curve J(λ) reaches a minimum at λ = 5, which is the "Best finite lambda".
Adjust the Penalty lambda control to 1, then to 5, then to 10. Notice how the "Optimal train coefficient" θ*(λ) decreases as the penalty increases.
Change the Data control to "Opposite validation". Notice that the validation loss strictly decreases as λ grows. The optimum is an "Infimum at infinity", because the validation loss cannot reach 0, but approaches 0.5 as θ* goes to 0.
Set the Data control to "Aligned" and the Penalty lambda to 0. The inner model perfectly fits the validation data, yielding a validation loss of 0 and a hypergradient of 0.

Limitations and Assumptions

The approach demonstrated here relies on several key assumptions:

Exact Attainability: We differentiate through the exact, closed-form optimum (θ*). In deep learning, models are rarely optimized to exact stationarity, meaning a finite optimizer path or approximation like Neumann series is required for large-scale problems.
No Grid Search Claim: This explicitly computes gradients of the validation objective. It does not perform grid-search or approximate the inverse-Hessian in a general way.
Finite vs. Asymptotic Optima: As shown in the "Opposite validation" and "Zero validation target" cases, the optimum hyperparameter may not be a finite endpoint. In these cases, the best validation loss (infimum) is only approached asymptotically as λ → ∞.

References

To learn more about modern techniques for differentiating through optimization and tuning millions of hyperparameters, refer to:

Lorraine, J., Maclaurin, D., & Duvenaud, D. (2020). Optimizing Millions of Hyperparameters by Implicit Differentiation. This paper explores computing hypergradients using the implicit function theorem, which extends the principles shown in this scalar ridge example to large neural networks.

Bilevel Ridge Hypergradient