# Hyperparameter Optimization: A Spectral Approach

arXiv: https://arxiv.org/abs/1706.00764 · HTML: https://mlsanity.com/paper/1706.00764/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jun 2017.

## Built on by (most cited first, 24 of 24)

- [Properly learning decision trees in almost polynomial time](https://mlsanity.com/paper/2109.00637/) (2021)
- [Highlighting the Importance of Reducing Research Bias and Carbon Emissions in CNNs](https://mlsanity.com/paper/2106.03242/) (2021)
- [Superpolynomial Lower Bounds for Decision Tree Learning and Testing](https://mlsanity.com/paper/2210.06375/) (2022)
- [Adaptive Gradient Methods with Local Guarantees](https://mlsanity.com/paper/2203.01400/) (2022)
- [Decision tree heuristics can fail, even in the smoothed setting](https://mlsanity.com/paper/2107.00819/) (2021)
- [Global Optimization with Parametric Function Approximation](https://mlsanity.com/paper/2211.09100/) (2022)
- [Trade-off Between Efficiency and Consistency for Removal-based Explanations](https://mlsanity.com/paper/2210.17426/) (2022)
- [A Nonstochastic Control Approach to Optimization](https://mlsanity.com/paper/2301.07902/) (2023)
- [Popular decision tree algorithms are provably noise tolerant](https://mlsanity.com/paper/2206.08899/) (2022)
- [Machine learning for sports betting: should model selection be based on accuracy or calibration?](https://mlsanity.com/paper/2303.06021/) (2023)
- [Superconstant Inapproximability of Decision Tree Learning](https://mlsanity.com/paper/2407.01402/) (2024)
- [Provably Data-driven Multiple Hyper-parameter Tuning with Structured Loss Function](https://mlsanity.com/paper/2602.02406/) (2026)
- [Convolution Neural Network Hyperparameter Optimization Using Simplified Swarm Optimization](https://mlsanity.com/paper/2103.03995/) (2021)
- [Learning stochastic decision trees](https://mlsanity.com/paper/2105.03594/) (2021)
- [Communication-Efficient Federated Non-Linear Bandit Optimization](https://mlsanity.com/paper/2311.01695/) (2023)
- [Training neural networks faster with minimal tuning using pre-computed lists of hyperparameters for NAdamW](https://mlsanity.com/paper/2503.03986/) (2025)
- [A hyperparameter-tuning approach to automated inverse planning](https://mlsanity.com/paper/2105.07024/) (2021)
- [Neighbor Regularized Bayesian Optimization for Hyperparameter Optimization](https://mlsanity.com/paper/2210.03481/) (2022)
- [Early Diagnosis of Retinal Blood Vessel Damage via Deep Learning-Powered Collective Intelligence Models](https://mlsanity.com/paper/2210.09449/) (2022)
- [ALT: An Automatic System for Long Tail Scenario Modeling](https://mlsanity.com/paper/2305.11390/) (2023)
- [Beyond Trend Following: Deep Learning for Market Trend Prediction](https://mlsanity.com/paper/2407.13685/) (2024)
- [Privacy-Computation trade-offs in Private Repetition and Metaselection](https://mlsanity.com/paper/2410.19012/) (2024)
- [T-TAMER: Provably Taming Trade-offs in ML Serving](https://mlsanity.com/paper/2509.22992/) (2025)
- [Which Hyperparameters Matter? A Game-Theoretic Framework for Interpretable Hyperparameter Sensitivity Analysis](https://mlsanity.com/paper/2607.15884/) (2026)

## Abstract (arXiv)

We give a simple, fast algorithm for hyperparameter optimization inspired by techniques from the analysis of Boolean functions. We focus on the high-dimensional regime where the canonical example is training a neural network with a large number of hyperparameters. The algorithm --- an iterative application of compressed sensing techniques for orthogonal polynomials --- requires only uniform sampling of the hyperparameters and is thus easily parallelizable. Experiments for training deep neural networks on Cifar-10 show that compared to state-of-the-art tools (e.g., Hyperband and Spearmint), our algorithm finds significantly improved solutions, in some cases better than what is attainable by hand-tuning. In terms of overall running time (i.e., time required to sample various settings of hyperparameters plus additional computation time), we are at least an order of magnitude faster than Hyperband and Bayesian Optimization. We also outperform Random Search 8x. Additionally, our method comes with provable guarantees and yields the first improvements on the sample complexity of learning decision trees in over two decades. In particular, we obtain the first quasi-polynomial time algorithm for learning noisy decision trees with polynomial sample complexity.