# Stein Variational Black-Box Combinatorial Optimization

arXiv: https://arxiv.org/abs/2604.15837 · HTML: https://mlsanity.com/paper/2604.15837/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 25 references that are in the map.
- First posted on arXiv 17 Apr 2026.

## Builds on (most cited first, 7 of 7)

- [Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm](https://mlsanity.com/paper/1608.04471/) (2016)
- [Self-Adjusting Mutation Rates with Provably Optimal Success Rules](https://mlsanity.com/paper/1902.02588/) (2019)
- [Automated Configuration of Genetic Algorithms by Tuning for Anytime Performance](https://mlsanity.com/paper/2106.06304/) (2021)
- [Benchmarking a (μ+λ) Genetic Algorithm with Configurable Crossover Probability](https://mlsanity.com/paper/2006.05889/) (2020)
- [The Paradox of Success in Evolutionary and Bioinspired Optimization: Revisiting Critical Issues, Key Studies, and Methodological Pathways](https://mlsanity.com/paper/2501.07515/) (2025)
- [Stein Variational Evolution Strategies](https://mlsanity.com/paper/2410.10390/) (2024)
- [Black-Box Combinatorial Optimization with Order-Invariant Reinforcement Learning](https://mlsanity.com/paper/2510.01824/) (2025)

## Abstract (arXiv)

Combinatorial black-box optimization in high-dimensional settings demands a careful trade-off between exploiting promising regions of the search space and preserving sufficient exploration to identify multiple optima. Although Estimation-of-Distribution Algorithms (EDAs) provide a powerful model-based framework, they often concentrate on a single region of interest, which may result in premature convergence when facing complex or multimodal objective landscapes. In this work, we incorporate the Stein operator to introduce a repulsive mechanism among particles in the parameter space, thereby encouraging the population to disperse and jointly explore several modes of the fitness landscape. Empirical evaluations across diverse benchmark problems show that the proposed method achieves performance competitive with, and in several cases superior to, leading state-of-the-art approaches, particularly on large-scale instances. These findings highlight the potential of Stein variational gradient descent as a promising direction for addressing large, computationally expensive, discrete black-box optimization problems.