Improving the Default Optimization Algorithm in Optuna v5
In Optuna v5, we have updated the default sampler for the first time in several years. This article outlines the discussions and development process that the development team undertook to bring about this update.
This update was made possible by the discussions, implementation improvements, and bug fixes from numerous contributors over the past several years. We would like to take this opportunity to express our gratitude.
Requirements for the Optuna Default Sampler
Optuna is not only the de facto standard library for hyperparameter optimization but is also utilized across diverse domains beyond machine learning, such as materials science and structural design. To support such a wide range of use cases, the default sampler is required to offer not only optimization performance but also usability in various respects. In this update, we considered the following points:
Define-by-Run API
Optuna employs a Define-by-Run style API, where the search space is defined during execution. While this API allows users to write code in a simple and intuitive manner, it requires careful implementation in the sampler. For algorithms that consider relationships between parameters, the search space must be inferred from past history, and it is desirable to maintain a certain level of optimization performance even if that inference is incorrect.
Discrete and Conditional Search Spaces
Optuna also supports integer and categorical search spaces. It also handles complex search spaces where hyperparameters may or may not exist depending on certain conditions. The default sampler must be able to handle not only continuous search spaces but also such spaces.
Asynchronous Optimization
Optuna enables multiple workers to process Trials asynchronously. In asynchronous optimization, the sampler must handle situations where some Trials have not yet returned results, or where the results arrive out of order.
Pruning and Constraint-Based Optimization
Optuna must also be able to handle more advanced optimization problems, such as cases where Trials are pruned by the Pruner mid-evaluation or cannot be evaluated because they do not satisfy constraints.
Dependency Libraries
Since Optuna is used in various environments, it is necessary to minimize the number of dependency libraries to improve convenience. For example, if a heavy library like PyTorch is included as a dependency, some users may encounter version conflicts or memory limitations.
Speed
Hyperparameter optimization for machine learning rarely involves a large number of Trials, but since Optuna is used across a wide range of fields, use cases with several thousand Trials or more are not uncommon. The default sampler must run sufficiently fast even in such settings.
To meet these various needs, a default sampler that simply has high optimization performance is not enough. TPE, adopted as the default in Optuna, is an algorithm that is well suited to implementations that satisfy these conditions. Roughly speaking, TPE is an algorithm that partitions past Trials into “good” and “bad” and uses the resulting probability distributions to propose promising points next. In other words, as long as the conditions of “being able to partition” and “being able to derive a probability distribution” are met, it can flexibly handle various problems. Considering this advantage, we examined whether improvements could be made specifically for TPE during the v5 update.
Below, we introduce the efforts we undertook to update the default sampler.
Efforts Toward the Update
This is not the first time we have worked on updating the default sampler; we also attempted improvements during the v3 major release. Unfortunately, this did not result in an update to the default sampler at the time, but we learned the following lessons:
- In benchmarks, there must be clear improvements significant enough for developers to reach a consensus.
- Implementation bugs that affect performance must be eliminated in advance.
The second point is particularly important. Since Optuna solves various optimization problems across diverse environments, users may actually encounter bugs even if they occur only in rare cases. Furthermore, if benchmarks are conducted while these issues remain, it becomes difficult to interpret the resulting performance changes.
Get Naoto Mizuno’s stories in your inbox
Join Medium for free to get updates from this writer.
From v3 through v5, we have resolved various issues. Additionally, since the sampler execution speed had been a problem in multi-objective optimization, steady improvements have been accumulated. Below, we introduce some of these.
Bug Fixes and Optimization Performance Improvements
- #4073 (v3.1): Trials currently running end up on the “below” side in constant_liar
- #4462 (v3.2): Bug when combining multivariate and constant_liar
- #6189 (v4.5): Optimization performance may degrade when combining multivariate and constant_liar
- #6258 (v4.7): Issue related to log-density calculation
- #6574 (v4.9): Prior distribution is mixed into bandwidth calculation
Speed Improvements
- #5303 (v4.0): Vectorization of 2D hypervolume calculation
- #5346 (v4.0): Improvement of HSSP computational complexity
- #5355 (v4.0): Lazy evaluation of HSSP
- #5424, #5591 (v4.0): WFG speed optimization
- #6112 (v4.4): Dedicated 3D implementation
- #6194 (v4.5): Speed optimization for ndtri_exp
- #6200 (v4.5): Speed optimization for the error function
Changes in v5
The following changes were made in v5. All of these were either shown to improve optimization performance in published papers or were previously expected by the development team to yield performance gains.
Changed the default sampler for multi-objective optimization to TPESampler
While multi-objective TPE was reported in the paper [1] to outperform NSGA-II, its execution speed was initially a bottleneck that prevented it from being adopted as the default. This issue has been resolved through years of speed optimization; therefore, in v5, TPESampler is now the default for both single- and multi-objective optimization.
Multivariate TPE enabled by default
Multivariate TPE captures interactions between variables by modeling their joint distribution, rather than treating each variable independently. [2] reports that it performs better when combined with Optuna’s bandwidth selection, and since our replication studies confirmed a similar trend, we have enabled this feature by default. Note that for multi-objective optimization, no performance improvement was observed in benchmarks, so independent TPE will be used.
Constant Liar enabled by default
In TPE, performing parallel optimization without specific adjustments can lead to a problem where each worker references the same completed Trials, resulting in the proposal of nearly identical parameters. With Constant Liar enabled, the proposal of candidate points close to currently running Trials is suppressed, which is expected to improve performance in parallel optimization.
Optimization Performance
The changes in v5 were guided by papers and our past experiments, and we proceeded while verifying that their findings could be reproduced. The figures shown below illustrate the win rates for each benchmark problem set under the default settings of v4.9 and v5.0, with the number of Trials plotted on the x-axis.
For single-objective optimization, we referred to the recommended settings in [2] and confirmed that the performance trends were reproduced. The figures show the performance improvement achieved by Multivariate TPE (1-a), in addition to the performance improvement in batch optimization via Constant Liar (1-b). On the other hand, as also reported in [2], a performance degradation due to Multivariate TPE was observed in HPOBench (1-c). Whether performance improves depends on the problem, which is to some extent unavoidable considering the No Free Lunch theorem; therefore, we implemented this change after determining that improvements are expected for many of Optuna’s use cases.
For multi-objective optimization, we confirmed that the change from NSGA-II to TPE led to significant improvements, particularly around 100 Trials. Furthermore, since experiments revealed that Multivariate TPE tends to degrade performance in multi-objective optimization, we decided against adopting it, unlike for single-objective optimization.
That said, benchmarks alone cannot account for workloads across various fields. However, since many users were already using these three options, we determined that while not all workloads would necessarily improve, there was likely no significant risk, and thus decided to adopt them.
Looking Ahead
In this major release, we have updated the default sampler for the first time in a while, but we believe there is still room for improvement. While we focused the discussion on TPE this time, we would like to explore other samplers such as GPSampler and CmaEsSampler, as well as the wide variety of algorithms registered on OptunaHub.
At the same time, as evidenced by the fact that this was the first update in several years, determining what the default for Optuna should be has been a very difficult problem, and that will remain the case. It is no longer possible to fully grasp exactly what kinds of problems users are solving and with which algorithms. If you have examples of “this worked well/didn’t work” or “this algorithm was effective,” we would greatly appreciate it if you could publish and share them, as it will aid future development. We look forward to your continued contributions to Optuna in various ways.
References
[1] Ozaki, Y., Tanigaki, Y., Watanabe, S., Nomura, M., & Onishi, M. (2022). Multiobjective Tree-Structured Parzen Estimator. Journal of Artificial Intelligence Research, 73, 1209–1250.
[2] Watanabe, S. (2023). Tree-Structured Parzen Estimator: Understanding Its Algorithm Components and Their Roles for Better Empirical Performance. arXiv preprint arXiv:2304.11127.
