Hyperparameter optimization for randomized algorithms: a case study on random features

Oliver R. A. Dunbar, Nicholas H. Nelsen, Maya Mutic

TL;DR

This paper introduces a novel, gradient-free method for optimizing hyperparameters in randomized machine learning algorithms, specifically focusing on Random Feature Regression (RFR). By framing hyperparameter tuning as a Bayesian inverse problem and employing Ensemble Kalman Inversion (EKI), the authors demonstrate robust and efficient optimization for complex tasks like function emulation and scientific model integration, outperforming traditional methods in certain scenarios.

What Problem Does This Paper Address?

Many powerful machine learning algorithms, such as Random Feature Regression (RFR), rely on randomized components. These algorithms approximate complex functions by sampling from probability distributions, and the characteristics of these distributions (defined by hyperparameters) significantly impact performance. However, these hyperparameters are not directly observable from data, making standard gradient-based optimization techniques inapplicable. This leads practitioners to resort to manual tuning or grid searches, which are inefficient, prone to bias, and don't scale well. The paper addresses this challenge by proposing a systematic, automated method for optimizing these "black-box" hyperparameters.

Methods

The core of the paper's contribution lies in its novel methodology for hyperparameter optimization. The authors adapt ideas from Gaussian Process Regression (GPR) and Bayesian inference to create a "random objective function" specifically for tuning RFR hyperparameters. This objective function is then minimized using Ensemble Kalman Inversion (EKI). EKI is a derivative-free, particle-based optimization algorithm that is well-suited for problems with stochastic or noisy objective functions and scales effectively to high dimensions. The authors also propose specific structures for the random feature distributions themselves, allowing for efficient learning of these complex hyperparameters.

Datasets

The paper does not introduce new benchmark datasets. Instead, it utilizes existing, scientifically relevant problems for evaluation:

  • Global Sensitivity Analysis: Two standard functions from the sensitivity analysis literature (Ishigami function and Sobol G function) are used.
  • Lorenz 63 Integrator: Data is generated from a trajectory of the Lorenz 63 dynamical system.
  • Uncertainty Quantification of a Cloud Model: Data is generated from a geophysical inverse problem simulating atmospheric processes.

Key Insights and Ideas

  • Hyperparameter Optimization as a Bayesian Inverse Problem: Framing the hyperparameter tuning problem as an inverse problem, solvable by EKI, is a key conceptual shift that allows for gradient-free optimization of complex, stochastic objectives.
  • EKI's Suitability for Randomized Algorithms: EKI's ability to handle noisy and stochastic objective functions makes it a natural fit for optimizing hyperparameters in randomized machine learning models.
  • Decoupling Feature Count for Tuning vs. Prediction: The proposed method allows for using a different number of random features for hyperparameter tuning than for downstream prediction tasks, offering flexibility.
  • Feature Distribution Structure Matters: The choice of how to parametrize the random feature distribution (e.g., rank, separability) significantly impacts performance, and this structure can be learned.
  • Untuned vs. Tuned Performance: The paper consistently shows that tuned hyperparameters lead to significantly better performance across various applications compared to untuned or standard GP models.

Key Results

The paper demonstrates the effectiveness of their EKI-based hyperparameter optimization framework across several challenging applications:

  • Global Sensitivity Analysis: Tuned RF emulators achieved results comparable to tuned GP emulators, with RF showing better robustness to increasing input dimensions.
  • Lorenz 63 Integrator: Tuned RF and GP emulators successfully learned the chaotic dynamics and reproduced the attractor and marginal probability density functions, outperforming untuned RF.
  • Uncertainty Quantification: The RF-CES algorithm produced smoother posterior distributions compared to GP-CES, with comparable qualitative agreement, and showed better computational efficiency.
  • Computational Efficiency: RFR with optimized hyperparameters offers significant computational advantages over traditional GPR, especially in high-dimensional settings, by reducing the complexity from Np to M (where M << Np).

Limitations and Future Work

  • Gaussian Assumption: The current formulation of EKI relies on Gaussian priors and likelihoods, which may not always be appropriate. Future work could explore extensions to non-Gaussian distributions.
  • Computational Cost of Objective Function: While EKI is efficient, the objective function itself can still scale quadratically with the number of data points and output dimensions (Np)². The paper suggests approximations like using validation partitions to mitigate this.
  • Prior Selection: The choice of prior distributions for hyperparameters is crucial for EKI's performance, and the paper acknowledges that finding optimal priors, especially in high dimensions, remains an open question.
  • Feature Distribution Structure: While the paper proposes flexible feature distribution structures, selecting the optimal rank and structure still requires some offline analysis or careful consideration.
  • Future Directions: The authors suggest exploring alternative objective functions, learning from indirect data, and systematically comparing EKI with other Bayesian optimization and evolutionary algorithms. They also highlight the potential for applying this framework to other randomized machine learning methods beyond RFR.

Summary updated

Abstract

Randomized algorithms exploit stochasticity to reduce computational complexity. One important example is random feature regression (RFR) that accelerates Gaussian process regression (GPR). RFR approximates an unknown function with a random neural network whose hidden weights and biases are sampled from a probability distribution. Only the final output layer is fit to data. In randomized algorithms like RFR, the hyperparameters that characterize the sampling distribution greatly impact performance, yet are not directly accessible from samples. This makes optimization of hyperparameters via standard (gradient-based) optimization tools inapplicable. Inspired by Bayesian ideas from GPR, this paper introduces a random objective function that is tailored for hyperparameter tuning of vector-valued random features. The objective is minimized with ensemble Kalman inversion (EKI). EKI is a gradient-free particle-based optimizer that is scalable to high-dimensions and robust to randomness in objective functions. A numerical study showcases the new black-box methodology to learn hyperparameter distributions in several problems that are sensitive to the hyperparameter selection: two global sensitivity analyses, integrating a chaotic dynamical system, and solving a Bayesian inverse problem from atmospheric dynamics. The success of the proposed EKI-based algorithm for RFR suggests its potential for automated optimization of hyperparameters arising in other randomized algorithms.
BibTeX
@inproceedings{dunbar2025hyperparameter,
  author = {Oliver R. A. Dunbar and Nicholas H. Nelsen and Maya Mutic},
  title = {{Hyperparameter optimization for randomized algorithms: a case study on random features}},
  booktitle = {Stat. Comput},
  year = {2025},
  url = {https://openreview.net/forum?id=slaCJMvz21},
}
Figure