Search Space

The dimensionality of a search space refers to the number of independent hyperparameters or architectural decisions that can be varied. High-dimensional spaces are exponentially larger and suffer from the curse of dimensionality, making exhaustive search impossible and requiring sophisticated optimization strategies like Bayesian Optimization. For example, a search space defining a neural network's layer count, neuron count per layer, activation function, and learning rate is a multi-dimensional space where each dimension can be continuous, integer, or categorical.

The structure defines the relationships and dependencies between parameters. A flat search space treats all parameters as independent, while a conditional or hierarchical space introduces dependencies. For instance, the number of layers (an integer) conditions which specific layer hyperparameters (like dropout rates for each layer) are active. This structure is often represented as a directed acyclic graph (DAG) and is critical for algorithms like Sequential Model-Based Optimization (SMBO) to correctly model the space.

Search spaces contain parameters of distinct data types, each requiring specialized handling:

• Continuous: Real-valued parameters (e.g., learning rate from 0.0001 to 0.1). Optimized with methods like gradient-based search.
• Integer: Discrete numerical values (e.g., number of layers from 1 to 10).
• Categorical: Unordered choices (e.g., optimizer type: Adam, SGD, RMSprop).
• Ordinal: Ordered categorical choices where distance matters. Mixed-type spaces are common and handled by surrogate models that can encode each type appropriately.

Constraints are rules that define valid regions within the broader combinatorial space. They enforce physical, logical, or resource limits. Examples include:

• A model's total parameter count must be < 100M.
• Total training latency must be < 2 hours.
• Architectural choices must result in a valid computational graph (no dangling connections). Infeasible regions are often pruned or penalized. Hardware-aware NAS explicitly encodes constraints like FLOPs or on-device latency into the search objective, shaping the feasible region.

The cardinality is the total number of unique configurations within the space. For discrete spaces, it can be calculated; for continuous spaces, it is infinite. A modest space with 10 categorical parameters, each with 5 options, has a cardinality of 5^10 (~9.7 million). This size dictates the search strategy: Random Search can be effective in large spaces, but Evolutionary Algorithms or Bayesian Optimization are required for efficient navigation. The concept of coverage—the fraction of the space an algorithm can practically explore—is key.

This characteristic describes how the performance metric (e.g., validation accuracy) changes as parameters vary. A smooth space implies small parameter changes lead to small, predictable performance changes, enabling gradient-based optimization. A rugged or noisy space has many local optima and sharp performance cliffs, making optimization difficult. The smoothness is an inherent property of the model and task; algorithms like Bayesian Optimization use kernel functions in their surrogate models to assume and exploit an underlying smoothness.

When training a convolutional neural network (CNN) for image classification, the search space defines all tunable configurations. A typical space includes:

• Architectural parameters: Number of convolutional layers (e.g., 3 to 10), filter sizes (e.g., 3x3, 5x5), and number of filters per layer (e.g., 32 to 512).
• Optimization parameters: Learning rate (e.g., a log-uniform range from 1e-5 to 1e-1), optimizer type (e.g., {Adam, SGD, RMSprop}), and batch size (e.g., 16, 32, 64, 128).
• Regularization parameters: Dropout rate (e.g., 0.0 to 0.7) and weight decay coefficient. An algorithm like Bayesian Optimization or Hyperband explores this multi-dimensional space to find the configuration that maximizes validation accuracy.

In Hardware-Aware NAS, the search space is constrained by on-device deployment targets. For a mobile image segmentation model, the space is defined by a set of parameterized building blocks (e.g., MBConv, inverted residuals) and rules for connecting them. Key dimensions include:

• Block choices: Which type of mobile-optimized block to use at each network stage.
• Kernel sizes: 3x3 or 5x5 convolutions within blocks.
• Expansion ratios: The factor by which channels are expanded within a block (e.g., 3, 6).
• Number of channels per layer. The search algorithm evaluates candidates not just on accuracy, but on real measured latency on a target smartphone chipset, finding architectures on the Pareto front of the accuracy-latency trade-off.

For a gradient boosting model predicting customer churn, the search space can extend beyond model hyperparameters to include feature transformations. This composite space may include:

• Model hyperparameters: Number of trees, tree depth, and learning rate for an XGBoost model.
• Feature generation: Boolean flags for applying transformations like log(x+1), polynomial features (x², x³), or binning of continuous variables.
• Feature selection: A binary mask vector where each element indicates whether to include an original or transformed feature in the final training set. A Combined Algorithm Selection and Hyperparameter optimization (CASH) approach searches this joint space to find the optimal pipeline that transforms raw data into the most predictive feature set for the model.

In training a robotic arm policy via deep reinforcement learning (RL), the search space can define the policy network architecture. This is crucial as the network must process high-dimensional sensor data (e.g., joint angles, camera images) and output precise motor torques. The space may specify:

• Input processing modules: Type of visual encoder (e.g., small CNN vs. ViT patch size).
• Core network topology: Number and width of fully-connected layers between encoder and output.
• Activation functions: Choices like ReLU, Tanh, or Swish.
• Output layer parameterization: For continuous control, this defines how the network outputs mean and variance for a Gaussian action distribution. Population-Based Training (PBT) is often used here, as it can simultaneously evolve a population of policies and their hyperparameters (like learning rate and entropy coefficient) within this architectural space.

For a natural language processing model, the search space can define a data augmentation policy. Instead of manually designing text perturbations, an algorithm searches a space of possible transformations and their application probabilities. The space includes operations such as:

• Synonym replacement: Using a thesaurus to swap words, with a searchable parameter for the percentage of words to replace.
• Random insertion/deletion/swapping of words.
• Back-translation: Parameters defining which intermediate languages to use for the round-trip translation. Each candidate 'policy' is a sequence or probability distribution over these operations. The search algorithm (often reinforcement learning or gradient-based) evaluates policies by training a model with the augmented data and measuring validation performance, seeking the augmentation strategy that best improves generalization.

Differentiable Architecture Search (DARTS)** formulates the search space as a continuous relaxation. For a vision cell in a CNN, the space defines a set of possible operations (e.g., 3x3 sep. conv, 5x5 dil. conv, max pooling, identity, zero) that could be applied to connect two nodes in a computational graph.

• In the continuous relaxation, a categorical choice between operations is replaced with a softmax over continuous architecture weights (alpha parameters) for all possible operations on every edge.
• The search space is thus encoded in these alpha parameters. The search becomes a bi-level optimization problem: simultaneously training standard model weights (with gradient descent) and architecture weights (with gradient descent on a validation loss).
• After search, a discrete architecture is derived by retaining the operation with the highest learned alpha weight on each edge. This method allows efficient gradient-based exploration of a vast combinatorial space.

Hyperparameter optimization (HPO) is the automated process of searching a defined search space of hyperparameters (e.g., learning rate, batch size) to find the configuration that maximizes a model's performance on a validation set. It is the primary application for a hyperparameter search space.

• Core Mechanism: Uses algorithms like Bayesian Optimization, Random Search, or Grid Search to navigate the space.
• Objective: Minimize a black-box function (validation loss) where each evaluation is expensive.
• Example: Searching over {'learning_rate': [1e-4, 1e-3, 1e-2], 'dropout': [0.1, 0.3, 0.5]}.

Neural Architecture Search (NAS) is a subfield of AutoML where the search space consists of architectural components (e.g., operation types, connection patterns, number of layers). The goal is to algorithmically discover high-performing network designs.

• Search Space Types: Can be cell-based (searching for repeating motifs) or macro (searching the overall network skeleton).
• Search Strategies: Includes Reinforcement Learning, Evolutionary Algorithms, and Differentiable Search (DARTS).
• Key Challenge: The search space is combinatorially vast, making efficiency via weight sharing or one-shot NAS critical.

Bayesian optimization is a sequential, model-based strategy for optimizing expensive black-box functions, such as the validation loss across a search space. It is the gold-standard algorithm for HPO in medium-dimensional spaces.

• Two Components: A surrogate model (typically a Gaussian Process) to model the objective function, and an acquisition function (e.g., Expected Improvement) to decide the next point to evaluate.

• Process: Iteratively builds a probabilistic model of the performance landscape and uses it to intelligently sample promising, uncertain regions.

• Advantage: More sample-efficient than random or grid search, making it ideal when evaluations are costly.

In Bayesian optimization, the acquisition function is the analytic criterion that determines the next hyperparameter configuration to evaluate from the search space. It balances exploration (probing uncertain regions) and exploitation (refining known good areas).

• Common Functions: Expected Improvement (EI), Upper Confidence Bound (UCB), and Probability of Improvement.
• Role: After the surrogate model predicts a mean and variance for all points in the space, the acquisition function computes a single score for each point. The point with the maximum score is selected for the expensive true evaluation.
• Impact: The choice of acquisition function directly controls the efficiency and convergence of the optimization loop.

Multi-fidelity optimization is a strategy that uses cheaper, lower-fidelity approximations to efficiently explore a search space before committing resources to high-fidelity evaluation. It dramatically reduces total compute cost.

• Low-Fidelity Proxies: Training on a subset of data, for fewer epochs, or at lower resolution.
• Algorithms: Hyperband and Successive Halving are canonical multi-fidelity methods. They dynamically allocate training resources (budget) to promising configurations and quickly discard poor ones.
• Use Case: Essential for large search spaces where full training of every candidate is computationally prohibitive.

In multi-objective optimization—common in hardware-aware NAS—the Pareto front represents the set of optimal trade-offs between competing objectives within a search space. A configuration is "Pareto optimal" if no other configuration is better in all objectives.

• Objectives: Often include accuracy, model latency, memory footprint, and energy consumption.
• Visualization: A plot where each axis is an objective; the front is the curve of non-dominated points.
• Search Goal: To discover and return this front, allowing a practitioner to choose a model based on their specific deployment constraints (e.g., highest accuracy under 100ms latency).