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

• URL: http://arxiv.org/abs/2609.06196v1
• Date: Sat, 05 Sep 2026 17:36:18 GMT
• Title: Fast PAC Global Optimization via Restarted Langevin: Exploration, Exploitation, and Degenerate Cooling
• Abstract summary: Algorithm design and analysis are in continuous time.<n>Global exploration is decoupled from exploitation.<n>Experiments on the six camel and Rastrigin objectives illustrate the benefits of warmer exploration.
• Score: 7.018547803286913
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the computational effort required for global optimization of a smooth, possibly nonconvex objective $Γ:\mathbb{R}^d\to\mathbb{R}$. An algorithm satisfies the $(\varepsilon,δ)$-PAC performance requirement if its output $\widehat X$ obeys $\mathbb{P}\{Γ(\widehat X)-Γ^\star>\varepsilon\}\leqδ$. Algorithm design and analysis are in continuous time. We compare classical simulated annealing and fixed-temperature Langevin diffusion with two approaches introduced and analyzed here: parallel-restart Langevin and a Langevin--gradient scheme using stochastic dynamics for global exploration and gradient flow for local exploitation. Let $L=\log(1/δ)$ and let $E_*$ denote the dominant energy barrier. At logarithmic precision in the low-temperature regime, the first two approaches require simulation time exponential in $L/\varepsilon$. For parallel fixed-temperature Langevin, an appropriate number of independent trials gives $ C_3=L^{1+o(1)}/\varepsilon$ as $δ\downarrow0$, for each fixed $\varepsilon>0$. The most substantial improvement comes from separating exploration from exploitation. If $η$ is the attraction margin of a target region containing the global minimizers, a sufficient low-temperature estimate for total simulation time in the best-state Langevin--gradient variant is $ C_4^{(c)}\approx N\exp\{EL/(Nη)\} +O(\log(1/\varepsilon))$, with $E>E_*$. Thus global exploration is decoupled from the requested accuracy. Analysis beyond logarithmic precision reveals dimension-dependent prefactors, while experiments on the six-hump camel and Rastrigin objectives illustrate the benefits of warmer exploration and the usefulness of spectral information for understanding exploration time.

Related papers

• Sequential Physics-Constrained Neural Operator Forward Modeling for the $\textit{Norne}$ Reservoir System [3.175986877079391]
  We develop a comprehensive framework for sequential surrogate modeling of black-oil reservoir dynamics using neural operators.<n>The application focus is the Norne benchmark reservoir, defined on a heterogeneous $46times112times22$ grid.<n>A 1000-member ensemble runs in under one minute on a single B200 GPU, giving a $sim104times$ wall-clock speedup over the OPM finite-volume simulator.
  arXiv  Detail & Related papers  (2026-05-27T17:18:39Z)
• PAC global optimization for VQE in low-curvature geometric regimes [0.3553493344868413]
  Noise-robust guarantees of global $varepsilon$-optimality for the Variational Quantum Eigensolver.<n>A Morse--Bott submanifold satisfies fiber regularity with respect to coordinate-aligned, embedded flats.
  arXiv  Detail & Related papers  (2025-11-18T16:18:26Z)
• Faster Spectral Density Estimation and Sparsification in the Nuclear Norm [28.368253322669336]
  We introduce a new notion of graph sparsification, which we call nuclear sparsification. We show that our sparsification method also yields the first deterministic algorithm for spectral density estimation.
  arXiv  Detail & Related papers  (2024-06-11T17:50:20Z)
• Fast Rates for Maximum Entropy Exploration [52.946307632704645]
  We address the challenge of exploration in reinforcement learning (RL) when the agent operates in an unknown environment with sparse or no rewards. We study the maximum entropy exploration problem two different types. For visitation entropy, we propose a game-theoretic algorithm that has $widetildemathcalO(H3S2A/varepsilon2)$ sample complexity. For the trajectory entropy, we propose a simple algorithm that has a sample of complexity of order $widetildemathcalO(mathrmpoly(S,
  arXiv  Detail & Related papers  (2023-03-14T16:51:14Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  We introduce a new tool for BFG convex optimization (SCO): a Reweighted Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probability density. We develop algorithms achieving state-of-the-art complexities for SCO in parallel and private settings.
  arXiv  Detail & Related papers  (2023-01-01T18:51:29Z)
• Penalized Overdamped and Underdamped Langevin Monte Carlo Algorithms for Constrained Sampling [17.832449046193933]
  We consider the constrained sampling problem where the goal is to sample from a target distribution of $pi(x)prop ef(x)$ when $x$ is constrained. Motivated by penalty methods, we convert the constrained problem into an unconstrained sampling problem by introducing a penalty function for constraint violations. For PSGLD and PSGULMC, when $tildemathcalO(d/varepsilon18)$ is strongly convex and smooth, we obtain $tildemathcalO(d/varepsilon
  arXiv  Detail & Related papers  (2022-11-29T18:43:22Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  We learn the set of $epsilon$-optimal goal-conditioned policies attaining all states that are incrementally reachable within $L$ steps. DisCo is the first algorithm that can return an $epsilon/c_min$-optimal policy for any cost-sensitive shortest-path problem.
  arXiv  Detail & Related papers  (2020-12-29T14:06:09Z)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  We provide a new convergence analysis of gradient Langevin dynamics (SGLD) for sampling from a class of distributions that can be non-log-concave. At the core of our approach is a novel conductance analysis of SGLD using an auxiliary time-reversible Markov Chain.
  arXiv  Detail & Related papers  (2020-10-19T15:23:18Z)
• Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence [8.873449722727026]
  We show that the rate estimate $widetildemathcalO(depsilon-1)$ improves the previously known rates in both of these metrics. In particular, for convex and firstorder smooth potentials, we show that LMC algorithm achieves the rate estimate $widetildemathcalO(depsilon-1)$ which improves the previously known rates in both of these metrics.
  arXiv  Detail & Related papers  (2020-07-22T18:18:28Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.