TL;DR
This paper introduces "reshaping" the search distribution for hyperparameter optimization, going beyond traditional space-filling methods. By either tightening the distribution around the optimum's known prior ($P_0$) or using a Cauchy distribution when $P_0$ is unknown, they achieve significant improvements over random search, especially in high-dimensional settings.
What Problem Does This Paper Address?
Finding the best hyperparameters for machine learning models is crucial but computationally expensive. Traditional methods like random search, grid search, and even more sophisticated space-filling designs (like Latin Hypercube Sampling or Scrambled Hammersley) offer only modest improvements over random search, especially when dealing with many hyperparameters (high dimensions). The paper argues that these methods, while better than pure random sampling, only provide a constant factor improvement. The core challenge is to develop hyperparameter search strategies that are more efficient and scale better with the number of hyperparameters, particularly in "fully parallel" settings where multiple trials can run simultaneously.
Methods
The paper proposes a novel approach called "reshaping" the search distribution. This means instead of sampling from the prior distribution of the optimum ($P_0$), they use a modified search distribution ($P_s$). They introduce two main flavors of reshaping:
- Recentering: When the prior distribution of the optimum ($P_0$) is known, they propose "Recentering." This method creates a new search distribution that is a modified version of $P_0$, tightened closer to the center of the search space. The degree of tightening is adapted based on the dimensionality of the problem and the available budget (number of trials). They also introduce "MetaRecentering," which uses a heuristic to automatically determine the optimal reshaping parameter.
- Cauchy Distribution: When the prior distribution of the optimum ($P_0$) is unknown, they advocate using a Cauchy distribution for sampling. This choice is motivated by two key properties:
- Heavier Tails: For unbounded hyperparameters, the Cauchy distribution's heavier tails allow exploration further away from the center, which can be beneficial.
- Closer to Boundaries: For bounded hyperparameters, the Cauchy distribution's shape naturally places more probability mass closer to the boundaries of the search space, addressing a limitation of some space-filling designs that tend to avoid corners.
Datasets
The paper evaluates their methods on a combination of artificial and real-world datasets/benchmarks:
- Artificial Objective Functions (Nevergrad): Used for experiments where the prior distribution ($P_0$) is known and unknown. These include Sphere, Rastrigin, and Cigar functions with varying proportions of critical variables.
- Attend, Infer, Repeat (AIR) model: An image generation task used to test the Cauchy distribution for an unknown $P_0$.
- Progressive Generative Adversarial Networks (GANs): Another real-world task to evaluate their methods.
- Nevergrad Real-World Experiments: A suite of experiments including Salmon mappings and clustering, used to test methods in more realistic, less controlled settings.
Key Insights and Ideas
- Space-filling designs have limited headroom: Despite their advantages over random search, traditional space-filling designs offer only a constant factor improvement, especially in high dimensions. This suggests a need for more fundamental changes in the search strategy.
- Reshaping is key for significant gains: The core idea of modifying the search distribution itself, rather than just how points are arranged, is what unlocks substantial performance improvements.
- Knowing $P_0$ allows for targeted optimization: When the prior distribution of the optimum is known, Recentering effectively focuses the search around the most probable regions, leading to better results.
- Cauchy is a robust choice for unknown $P_0$: The Cauchy distribution proves to be a versatile and effective choice when the optimum's distribution is unknown, balancing exploration in unbounded spaces and exploitation near boundaries in bounded spaces.
- High dimensionality amplifies the benefits: The advantages of reshaping become more pronounced as the number of hyperparameters (dimensions) increases.
Key Results
- Theoretical improvements: The paper provides theoretical backing for the limitations of space-filling designs and the potential of reshaping.
- Empirical validation: Across various artificial and real-world tasks, their proposed reshaping methods (Recentering and Cauchy) consistently outperform standard space-filling designs and random search.
- Significant gains in GANs and AIR: For tasks like progressive GANs and the Attend, Infer, Repeat model, their methods achieved better performance (lower loss/higher score) compared to baselines. For instance, in the GAN experiments, MetaCauchyRctg dominated.
- Cauchy excels in unknown $P_0$ settings: In real-world experiments where $P_0$ was unknown or poorly controlled, Cauchy variants consistently outperformed normal distribution-based samplers.
- Recentering is effective when $P_0$ is known: When $P_0$ was known (e.g., in artificial experiments with known priors), Recentering and its Meta version showed strong performance.
Limitations and Future Work
- "Wildly unknown $P_0$" is challenging: The paper notes that in scenarios where no rescaling effort is made and $P_0$ is truly unknown, finding the optimal reshaping constant can be difficult, though Cauchy variants still perform reasonably well.
- Hyperparameter tuning for reshaping: While MetaRecentering aims to automate parameter selection, the optimal parameters for Cauchy or specific Recentering configurations might still require some tuning or domain expertise.
- Future work: The paper suggests exploring more sophisticated ways to adapt the search distribution based on observed data and the problem's characteristics. Further investigation into the theoretical properties of these reshaped distributions in complex optimization landscapes could also be valuable.
Summary updated