# Fast PAC Global Optimization via Restarted Langevin: Exploration, Exploitation, and Degenerate Cooling

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 41 references that are in the map.
- First posted on arXiv 5 Sep 2026.

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

- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Anticorrelated Noise Injection for Improved Generalization](https://mlsanity.com/paper/2202.02831/) (2022)
- [State-Dependent Temperature Control for Langevin Diffusions](https://mlsanity.com/paper/2011.07456/) (2020)
- [Replica Exchange for Non-Convex Optimization](https://mlsanity.com/paper/2001.08356/) (2020)
- [Constrained Exploration via Reflected Replica Exchange Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2405.07839/) (2024)
- [Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastability](https://mlsanity.com/paper/1802.06439/) (2018)
- [Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation](https://mlsanity.com/paper/2410.05106/) (2024)
- [Improving exploration strategies in large dimensions and rate of convergence of global random search algorithms](https://mlsanity.com/paper/2208.11542/) (2022)
- [Curse of scale-freeness: Intractability of large-scale optimization with multi-start methods](https://mlsanity.com/paper/2210.16678/) (2022)
- [Global Convergence and Acceleration for Single Observation Gradient Free Optimization](https://mlsanity.com/paper/2509.04424/) (2025)

## Abstract (arXiv)

This paper addresses a fundamental question in non-convex optimization: textitHow should a stochastic optimizer allocate computation between global exploration and local exploitation? We study this question in continuous time, using Langevin dynamics for global exploration and deterministic gradient flow for local exploitation. The simplest algorithm in this class is the best-state Langevin--gradient method: several Langevin trajectories explore the objective landscape, the best state encountered is retained, and a single gradient trajectory then refines this state to high terminal accuracy. Our main objective is to characterize the computational work required to achieve a prescribed accuracy with prescribed confidence. We develop low-temperature approximations for this probably approximately correct (PAC) work--accuracy tradeoff, both for the best-state method and for related Langevin schemes. Global exploration is governed by energy barriers, through spectral-gap and Eyring--Kramers asymptotics. The resulting approximations expose the competing effects of temperature, computational budget, and the number of exploratory trajectories, and quantify their dependence on the confidence parameter. In contrast, terminal accuracy is largely separated from global exploration: once a suitable region of attraction has been reached, gradient flow requires only O(log(1/varepsilon)) additional work to reach accuracy at least varepsilon. Numerical experiments on challenging objectives serve to compare algorithms and to test the quantitative predictions of the asymptotic theory. They identify regimes in which the low-temperature approximations provide useful guidance, as well as regimes exhibiting substantial temperature sensitivity and potentially significant high-dimensional limitations.