Random Search Baselines for Evaluating Optimization Algorithms

64 concepts43 papers

Machine learning research has seen an explosion of highly sophisticated optimization techniques. From reinforcement learning controllers and evolutionary strategies in Neural Architecture Search (NAS) to dynamic task-balancing schemes in multi-task learning, the trend favors algorithmic complexity.

However, a sobering empirical pattern has emerged across these domains: when these complex methods are evaluated against a simple, properly tuned random search baseline, the performance gap often vanishes entirely. To understand why a "dumb" strategy of uniform random sampling can match or even exceed state-of-the-art optimization, we must look closely at the interplay between search algorithms, search space design, and evaluation noise.

Search Space Dominance and the Illusion of Algorithmic Success

The primary reason random search performs exceptionally well in automated architecture discovery is that human experts heavily engineer the boundaries of the search space itself. When designing a search space, researchers typically include only high-quality operations (such as depthwise separable convolutions or residual connections) and enforce strict structural constraints.

As a result, the search space becomes a highly concentrated neighborhood of excellent models. Work by Liang-Chieh Chen et al. in Searching for Efficient Multi-Scale Architectures for Dense Image Prediction and Hanxiao Liu et al. in Hierarchical Representations for Efficient Architecture Search demonstrated that a well-constrained hierarchical space allows random sampling to achieve results nearly identical to sophisticated evolutionary or reinforcement learning strategies.

This phenomenon shifts the credit for performance from the exploration algorithm to the search space design. As Renato Negrinho et al. argue in Towards modular and programmable architecture search, a well-designed search space paired with simple random search routinely outperforms a poorly structured space explored by advanced optimization techniques.

To formalize this insight, Ilija Radosavovic et al. introduced a paradigm shift in On Network Design Spaces for Visual Recognition: instead of comparing individual "best" models found by algorithms, researchers should compare the statistical error distributions of the design spaces themselves. When the structural rules of a space are highly optimized—or even automatically evolved, as shown by Daquan Zhou et al. in AutoSpace: Neural Architecture Search with Less Human Interference—the choice of search algorithm becomes secondary.

Highly Engineered Space:  [ Good Model -> Great Model -> Good Model ]  --> Random search succeeds easily
Unconstrained Space:      [ Bad Model  -> Garbage     -> Great Model ]  --> Requires guided optimization

Low Effective Dimensionality and High Solution Density

From a mathematical perspective, random search exploits the underlying geometry of hyperparameter and architectural landscapes. In their foundational paper Random Search for Hyper-Parameter Optimization, James Bergstra et al. demonstrated that most machine learning models exhibit a "low effective dimensionality." This means that while a search space may have dozens of parameters, performance is typically dictated by only a small subset of vital dimensions. Random search naturally exploits this by sampling unique values along every dimension simultaneously, whereas structured grid searches waste evaluations repeating identical values across uninformative dimensions.

In architecture search, this principle manifests as a high density of high-performing solutions within tabular benchmarks. When researchers mapped out entire discrete search spaces in benchmarks like NAS-Bench-101 (by Chris Ying et al.) and NAS-Bench-201 (by Barry Dong et al.), they revealed that the variance between a large portion of candidate models is remarkably narrow.

When a search space is saturated with strong candidates, a random sampler will quickly hit a high-performing model. Consequently, sophisticated search controllers struggle to demonstrate any statistically significant marginal gains over random selection.

Overfitting to Evaluation Noise and Local Optima

Why do complex optimization algorithms sometimes perform worse than random search? The answer lies in how algorithms handle evaluation noise and non-linear landscapes.

In practical settings, evaluating a model's quality is highly noisy due to stochastic training dynamics, varying random seeds, and data sparsity. In Exploring the loss landscape in neural architecture search, Colin White demonstrates that many sophisticated NAS algorithms are essentially over-engineered to compensate for this noisy evaluation pipeline rather than the actual topology of the search space. When evaluation noise is minimized, basic local hill-climbing or random exploration can easily match or exceed state-of-the-art techniques. Guided optimization methods (like Bayesian optimization or greedy gradient steps) often mistake evaluation noise for a true performance signal, leading them to overfit to poor regions of the space.

Furthermore, directed algorithms are highly susceptible to getting trapped in local optima when navigating highly non-linear, discrete landscapes. By contrast, uniform random search maintains a broad, global exploration policy. The authors of Automated Side-Channel Attacks using Black-Box Neural Architecture Search (Pritha Gupta et al.) and A Systematic Comparison Study on Hyperparameter Optimisation of Graph Neural Networks for Molecular Property Prediction (Yingfang Yuan et al.) observed that in highly complex or data-sparse domains, the overhead of building surrogate models or following gradients is rarely justified; broad stochastic sampling avoids local traps and provides a far more resilient baseline.

The Random Baseline as a Cross-Domain Litmus Test

The necessity of random baselines extends far beyond standard computer vision tasks. Across diverse domains, random sampling acts as a vital sanity check to determine whether algorithmic complexity translates to real-world utility:

  • Multi-Task Learning (MTL): In Reasonable Effectiveness of Random Weighting: A Litmus Test for Multi-Task Learning, Baijiong Lin et al. introduced a baseline that randomly samples task weights at each iteration. They showed that this simple, noise-driven approach frequently matches or beats complex dynamic weighting schemes, exposing a lack of rigorous benchmarking in the field.
  • Logic Synthesis: In navigating massive discrete circuit optimization spaces, Antoine Grosnit et al. showed in BOiLS: Bayesian Optimisation for Logic Synthesis that deep reinforcement learning methods often fail to outperform basic stochastic baselines, indicating a lack of specialized priors in the complex models.
  • Optimization Heuristics: A large-scale evaluation by Diederick Vermetten et al. in Large-scale Benchmarking of Metaphor-based Optimization Heuristics revealed that a staggering number of novel, metaphor-based optimization algorithms (e.g., swarm or nature-inspired heuristics) actually perform worse than basic random search as problem complexity increases.
  • Domain Generalization: When algorithms are forced out of standard benchmarks into novel environments—such as the diverse tasks in NAS-Bench-360 by Misha Khodak or the unseen datasets in Insights from the Use of Previously Unseen Neural Architecture Search Datasets (Rob Geada et al.)—complex search controllers frequently break down, occasionally losing to a simple uniform random sampler.

Restoring Scientific Rigor through Null Models

The persistent strength of random search has forced a methodological reckoning. In NAS evaluation is frustratingly hard, Antoine Yang et al. demonstrated that many performance gains attributed to novel search algorithms disappear when training tricks are standardized. Similarly, Kaicheng Yu et al. in Evaluating The Search Phase of Neural Architecture Search found that common efficiency shortcuts like weight-sharing degrade architecture rankings so severely that the resulting search phase becomes indistinguishable from random sampling.

To isolate whether an optimization strategy provides genuine value beyond the inherent quality of its search space, it must be compared against a random sampling baseline under identical conditions. This requirement forms the backbone of modern best practices outlined by Marius Lindauer et al. in Best Practices for Scientific Research on Neural Architecture Search.

As argued by Stella Biderman et al. in Pitfalls in Machine Learning Research: Reexamining the Development Cycle, comparing complex systems against simple null models is a fundamental requirement of the scientific method. Without a rigorous random search baseline, researchers cannot determine if they have engineered a superior optimization algorithm, or simply a highly restrictive search space.

Key Foundational Work

Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA (1993) — contributed 1 concept elements to this direction.
On the Hardness of Offline Multi-objective Optimization (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_random_search_baseline_38e10cf9,
  title = {random search baseline},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/random-search-baseline/rdr_38e10cf92afc42d199fdeb953d3ac775},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_random_search_baseline_38e10cf9_v1,
  title = {random search baseline},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/random-search-baseline/rdr_38e10cf92afc42d199fdeb953d3ac775/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake