TL;DR
The authors introduce DOTS (Derivative-free stOchastic Tree Search), a novel optimization method that successfully finds global optima in non-convex, black-box systems up to 2,000 dimensions. By redesigning traditional tree search mechanics, DOTS outperforms existing state-of-the-art methods by 10- to 20-fold and enables fully autonomous discovery in self-driving virtual laboratories across materials science, physics, and biology.
What Problem Does This Paper Address?
Many breakthroughs in the natural sciences depend on finding the absolute best configuration of a system—whether it's the optimal atomic ratio for a high-performance alloy or the perfect amino acid sequence for a synthetic protein. These tasks are typically formulated as Derivative-Free Optimization (DFO) problems because the underlying "ground truth" function is a complex black box with no known mathematical formula or gradient information.
While existing DFO methods (like Bayesian Optimization or standard Monte Carlo Tree Search) work well in low-dimensional spaces, they suffer from the curse of dimensionality. Once a problem exceeds 20 to 100 dimensions, the search space becomes too vast, landscapes become rugged with countless local minima, and algorithms get hopelessly trapped. This paper tackles the challenge of scaling black-box optimization to thousands of dimensions without getting stuck.
Methods
The authors propose DOTS (Derivative-free stOchastic Tree Search), which adapts classic tree search concepts (similar to those used in AlphaGo) to continuous and high-dimensional scientific optimization.
DOTS relies on four core innovations:
- Stochastic Tree Expansion: Instead of deterministically evaluating every possible branch, DOTS generates leaf nodes dynamically using three randomized action modes: one-step moves, single mutations, and scaled random mutations.
- Dynamic Upper Confidence Bound (DUCB): Standard UCB requires visiting every child node at least once to avoid infinite uncertainty values, creating an impossible computational burden in high dimensions. DUCB solves this by adding a constant to the denominator, ensuring finite values for unvisited nodes. It also introduces data-dependent, adaptive exploration weights that scale with the minimum of the observed data distribution.
- Local Backpropagation: Traditional backpropagation updates node values globally from the leaf back to the root. DOTS intentionally limits backpropagation to a short range (only updating visitation counts for immediate neighbors) and completely omits value updates. This "short-term memory" prevents the algorithm from being permanently biased by local minima.
- Top-Visit Sampling: To train the machine learning surrogate model effectively, DOTS samples a 5:1 ratio of top-scoring nodes to most-visited nodes. This ensures the model learns both the high-performing regions and the shapes of the deceptive local basins that trap the search.
Datasets
The authors evaluated DOTS using two distinct categories of problems:
- Synthetic Benchmarks: Six classic, notoriously difficult non-convex test functions, including Ackley, Rastrigin, Rosenbrock, Griewank, Schwefel, and Michalewicz, scaled up to 2,000 dimensions.
- Real-World Applications (Self-Driving Virtual Labs):
- Architected Materials: Optimizing a 27-subunit Gyroid scaffold structure for bone implants using finite element simulations.
- Compositionally Complex Alloys (CCAs): Searching a 27-element space to maximize electronic transport properties via density functional theory.
- Cyclic Peptide Binders: Designing therapeutic peptide sequences from scratch using AlphaFold2 and Rosetta.
- Electron Ptychography: Optimizing an 8-dimensional parameter space to improve sub-angstrom electron microscopy reconstructions.
Key Insights and Ideas
- Forgetting is a Feature, Not a Bug: In high-dimensional optimization, remembering the entire history of a trajectory actually hurts performance. By making backpropagation short-ranged and omitting global value updates, DOTS effectively "forgets" distant local minima, allowing it to escape flat or deceptive landscapes.
- Overcoming the Exhaustive Search Bottleneck: The simple mathematical trick of adding
1to the denominator in the UCB formula eliminates the need to evaluate every single branch of an immense tree, unlocking massive computational speedups. - Learning from Failures: Top-visit sampling recognizes that the most-visited nodes (even if they have poor scores) represent the "trap basins" of the landscape. Teaching the surrogate model about these traps prevents the algorithm from falling into them repeatedly.
Key Results
- Dimensionality Breakthrough: DOTS successfully converged to global optima in up to 2,000 dimensions for the Rastrigin function and 1,500 dimensions for the Ackley function. In comparison, baseline state-of-the-art methods failed to scale beyond 100 dimensions.
- Sample Efficiency: DOTS achieved a 100% convergence ratio on major test functions using as few as ~500 data points.
- Real-World Impact: When integrated into autonomous virtual laboratories, DOTS consistently discovered superior designs compared to domain-specific baselines:
- +9.4% increase in yield strength for architected materials.
- +28.5% improvement in electronic transport properties for complex alloys.
- +33.7% higher binding metrics for cyclic peptides compared to standard genetic/MCMC methods.
Limitations and Future Work
While DOTS shifts the bottleneck away from the search algorithm itself, the overall framework is now limited by the expressive power of the machine learning surrogate model and available computer memory. In extreme dimensions, neural networks struggle to accurately learn the underlying data distributions, leading to inaccurate node evaluations.
Currently executed on standard desktop setups, the authors note that pairing DOTS with more sophisticated deep learning architectures and larger computing clusters could push the boundaries well beyond 2,000 dimensions. Additionally, they envision merging DOTS directly with physical robotic platforms to enable fully automated, real-world material synthesis and discovery.
Summary updated