Algorithm Configuration
Let \(\mathcal{I}\) be the set of problem instances, \(\mathcal{D}\) be the probability distribution over \(\mathcal{I}\). Let \(p_1, p_2, \ldots, p_k\) be the parameters of an algorithm. The domain of each parameter \(p_i\) is denoted as \(\Theta_i\), and the parameter space is defined as \(\Theta = \Theta_1 \times \Theta_2 \times \ldots \times \Theta_k\). Note that the the domain of each parameter can be continuous, discrete, or categorical. The parameter configuration of the algorithm is denoted as \(\theta = (p_1, p_2, \ldots, p_k) \in \Theta\).
The objective of algorithm configuration is to find the optimal parameter configuration \(\theta^* \in \Theta\) that minimizes the expected cost of the algorithm over the distribution of problem instances:
\[ \theta^* \in \arg\min_{\theta \in \Theta} \mathbb{E}_{i \sim \mathcal{D}}[c(\theta, i)] \]
where \(c(\theta, i)\) is the cost of the algorithm parameter configuration \(\theta\) on problem instance \(i\).
Normally, the distribution \(\mathcal{D}\) is unknown. Thus, arithmetic mean is often used as an estimator of the expected cost. The problem is then formulated as follows:
\[ \theta^* \in \arg\min_{\theta \in \Theta} \frac{1}{|\mathcal{I}|} \sum_{i \in \mathcal{I}} c(\theta, i) \]
AutoML
Neural Architecture Search
Hyperparameter Optimization
Hyperparameter optimization (HPO) is a special case of algorithm configuration.
Dynamic Algorithm Configuration
- SMAC3 (Lindauer et al. 2021)
- Population-based training (PBT) (Jaderberg et al. 2017)
- Optuna (Akiba et al. 2019)