  Selecting hyperparameters in deep learning greatly impacts its effectiveness
but requires manual effort and expertise. Recent works show that Bayesian model
selection with Laplace approximations can allow to optimize such
hyperparameters just like standard neural network parameters using gradients
and on the training data. However, estimating a single hyperparameter gradient
requires a pass through the entire dataset, limiting the scalability of such
algorithms. In this work, we overcome this issue by introducing lower bounds to
the linearized Laplace approximation of the marginal likelihood. In contrast to
previous estimators, these bounds are amenable to stochastic-gradient-based
optimization and allow to trade off estimation accuracy against computational
complexity. We derive them using the function-space form of the linearized
Laplace, which can be estimated using the neural tangent kernel.
Experimentally, we show that the estimators can significantly accelerate
gradient-based hyperparameter optimization.
