Derivative-free tree optimization for complex systems

Ye Wei, Bo Peng, Ruiwen Xie, Yangtao Chen, Yu Qin, Peng Wen, Stefan Bauer, Po-Yen TungarXiv 2024 · arXiv

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.

Fig. 1. Principle of derivative-free stochastic tree search. (a) Feature engineering of com- plex systems. (b) Stochastic Expansion. (c) Conditional selection. (d) Stochastic rollout. (e) Dynamic confidence upper bound. (f and g) An autonomous virtual lab consisting of DOTS, neural network and simulators designed for various DFO applications in materials, instruments, physics, and biology.

DOTS relies on four core innovations:

  1. 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.
  2. 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.
  3. 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.
  4. 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 1 to 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

Abstract

A tremendous range of design tasks in materials, physics, and biology can be formulated as finding the optimum of an objective function depending on many parameters without knowing its closed-form expression or the derivative. Traditional derivative-free optimization techniques often rely on strong assumptions about objective functions, thereby failing at optimizing non-convex systems beyond 100 dimensions. Here, we present a tree search method for derivative-free optimization that enables accelerated optimal design of high-dimensional complex systems. Specifically, we introduce stochastic tree expansion, dynamic upper confidence bound, and short-range backpropagation mechanism to evade local optimum, iteratively approximating the global optimum using machine learning models. This development effectively confronts the dimensionally challenging problems, achieving convergence to global optima across various benchmark functions up to 2,000 dimensions, surpassing the existing methods by 10- to 20-fold. Our method demonstrates wide applicability to a wide range of real-world complex systems spanning materials, physics, and biology, considerably outperforming state-of-the-art algorithms. This enables efficient autonomous knowledge discovery and facilitates self-driving virtual laboratories. Although we focus on problems within the realm of natural science, the advancements in optimization techniques achieved herein are applicable to a broader spectrum of challenges across all quantitative disciplines.
BibTeX
@misc{wei2024derivative,
  author = {Ye Wei and Bo Peng and Ruiwen Xie and Yangtao Chen and Yu Qin and Peng Wen and Stefan Bauer and Po-Yen Tung},
  title = {{Derivative-free tree optimization for complex systems}},
  year = {2024},
  eprint = {2404.04062},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2404.04062},
}

Loading related content...

Figure