# Proximal basin hopping: global optimization with guarantees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 49 references that are in the map.
- First posted on arXiv 18 May 2026.

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

- [Scaling Laws for Optimal Data Mixtures](https://mlsanity.com/paper/2507.09404/) (2025)
- [Understanding High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2502.09198/) (2025)
- [What is the long-run distribution of stochastic gradient descent? A large deviations analysis](https://mlsanity.com/paper/2406.09241/) (2024)
- [Consensus-Based Optimization Methods Converge Globally](https://mlsanity.com/paper/2103.15130/) (2021)
- [A Hamilton-Jacobi-based Proximal Operator](https://mlsanity.com/paper/2211.12997/) (2022)
- [Local Optima Networks: A New Model of Combinatorial Fitness Landscapes](https://mlsanity.com/paper/1402.2959/) (2014)
- [Regret analysis of the Piyavskii-Shubert algorithm for global Lipschitz optimization](https://mlsanity.com/paper/2002.02390/) (2020)
- [The global convergence time of stochastic gradient descent in non-convex landscapes: Sharp estimates via large deviations](https://mlsanity.com/paper/2503.16398/) (2025)
- [Efficient Multi-Start Strategies for Local Search Algorithms](https://mlsanity.com/paper/1401.3894/) (2014)
- [A Monte Carlo Approach for Nonsmooth Convex Optimization via Proximal Splitting Algorithms](https://mlsanity.com/paper/2509.07914/) (2025)
- [Characterizations of inexact proximal operators](https://mlsanity.com/paper/2602.02022/) (2026)
- [Hopping between distant basins](https://mlsanity.com/paper/2108.05229/) (2021)
- [A Local Optima Network View of Real Function Fitness Landscapes](https://mlsanity.com/paper/2212.10254/) (2022)
- [A Performance Analysis of Basin Hopping Compared to Established Metaheuristics for Global Optimization](https://mlsanity.com/paper/2403.05877/) (2024)
- [Inexact Proximal Point Algorithms for Zeroth-Order Global Optimization](https://mlsanity.com/paper/2412.11485/) (2024)
- [Convergence Rates for Stochastic Proximal and Projection Estimators](https://mlsanity.com/paper/2602.06750/) (2026)

## Abstract (arXiv)

Global optimization is a challenging problem, with plenty of algorithms displaying empirical success, but scarce theoretical backing. In this work, we propose a new theoretical framework called Proximal Basin Hopping (PBH), carefully tailored to combine proximal optimization and local minimization. We use it to construct a practical algorithm that converges to the global minimizer with high probability, when using a finite amount of samples. Proximal Basin Hopping outperforms well known algorithms with theoretical backing on standard synthetic hard functions, and real problems such as fitting scaling laws for deep learning. Furthermore, the higher the dimension, the better the performance gap.