PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Ioannis Kontoyiannis, Sean Meyn

arXiv:2609.06196v2math.OCcs.LG

TL;DR

Non-convex optimization poses a tradeoff: stochastic exploration can escape poor basins but impedes accurate local convergence, while gradient methods work rapidly only from favorable regions. The paper analyzes restarted Langevin exploration followed by gradient-flow exploitation, finding that exploration and terminal accuracy can be separated, with gradient flow adding O(log(1/ε)) work.

  • Problem

    Non-convex optimization requires allocating computation between exploration that can move between attraction regions and gradient methods that converge rapidly only from favorable regions.

    Source: §1 · p. 3

  • Method

    The paper analyzes Langevin exploration followed by deterministic gradient-flow exploitation, including a best-state method that retains a favorable state for one gradient trajectory.

    Source: §5 · p. 39

  • Results

    Independent restart can reduce high-confidence exploration cost, while gradient flow supplies terminal accuracy at cost O(log(1/ε)) after a suitable attraction region is reached.

    Source: §1 · p. 3, §5 · p. 39

  • Takeaways & Limitations

    Exploration need only continue until a trajectory reaches a region where deterministic dynamics are reliable; further stochastic exploration is wasteful for terminal accuracy.

    Source: §5 · p. 39

    The analysis is not a uniform-in-d complexity estimate, and dimension-dependent prefactors can be hidden by logarithmic approximations.

    Source: §2.5 · pp. 15, 17

Abstract

from arXiv · show

This paper addresses a fundamental question in non-convex optimization: \textit{How 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.

1 Introduction

The introduction frames non-convex optimization as an allocation problem: stochastic perturbations can move between attraction regions but hinder accurate local convergence, while gradient methods exploit favorable starts. It proposes separating the phases and analyzing their PAC work and landscape-dependent design.

1 Introduction

  • Stochastic exploration locates a suitable attraction region, after which gradient flow reaches accuracy ε with only O(log(1/ε)) additional cost.The paper presents this separation as improving on the complexity bound in (3).Source: §1 · p. 3

1.1 Assumptions

  • The objective assumptions define a target set for reliable gradient exploitation, but the algorithm need not test membership online.The attraction margin and other structural quantities enter the complexity bounds, not the implementation's prior information requirements.Source: §1.1 · p. 4

1.2 Complexity

  • The low-temperature work bound separates exploration from exploitation: restart changes the exploration term, while terminal accuracy enters through the gradient term.The approximation is developed in a regime including N/L → 0, with L = log(1/δ); its temperature and horizon balance concentration governed by η against exploration governed by E•.Source: §1.2 · pp. 5–6

1.3 Contributions

  • For Langevin–gradient schemes, PAC work quantifies how independent restarts alter the confidence–work tradeoff, reaching exploration complexity L^(1+o(1)) when N grows sufficiently slowly with L.The stated regime maintains N/L → 0.Source: §1.3 · p. 7
  • The best-state method retains the lowest-cost state across exploratory trajectories and times, then starts one gradient trajectory from it.The analysis uses attraction margin η and dominant barrier E• to derive scaling rules for temperature, run length, confidence, and trajectory count.Source: §1.3 · p. 7
  • For each fixed d > 2, accuracy-dependent Gibbs temperature changes the ε^(-d/2) sample-complexity dependence to ε^(-1), but the prefactor grows rapidly with dimension.Experiments on six-hump camel, Rastrigin, and Griewank objectives test predictions and identify both useful and unreliable regimes for low-temperature theory.Source: §1.3 · p. 7

1.4 Related work

  • Unlike Dong and Tong, this analysis ties exploration to PAC work and uses spectral-gap asymptotics to connect convergence rates with the dominant energy barrier.It builds from a multiplicative drift condition, spectral discreteness, reversibility, and transition-probability bounds.Source: §1.4 · pp. 7–8
  • Related approaches make temperature or restart design choices explicit: temperature trades landscape movement against concentration, while independent trajectories alter the temperature–confidence tradeoff.The paper contrasts this exploration-allocation question with classical simulated annealing's use of landscape information to schedule cooling for terminal accuracy.Source: §1.4 · p. 8

2 Langevin–gradient methods

This section studies Langevin–gradient methods that divide computation between finite-time Langevin exploration and gradient-flow refinement, with variants in switching rules, retained states, and temperature design. It also examines how fixed- and accuracy-adapted temperatures affect exploration in high dimensions, noting that the asymptotic gains do not include the cost of producing Gibbs samples.

2.1 Exploration and exploitation

  • First-entry switching halts exploration once a trajectory enters S, avoiding continued simulation of unsuccessful runs; with N = 1 and no horizon, hitting is almost surely finite and post-switch convergence is exponential.The hitting time has finite moments of every order.Source: §2.1 · pp. 9–10
  • Best-state switching retains the lowest-objective state observed during exploration, avoids an online test for S, and requires only one gradient-flow trajectory, making exploitation work independent of N.For a sublevel target Sη, reaching it ensures the best observed state is also in Sη, so the same low-temperature switching bound applies, possibly conservatively.Source: §2.1 · p. 10

2.2 A menu of temperatures

  • Because LGRM performance can be temperature-sensitive, the authors allow different temperatures across exploratory runs and consider state-dependent Langevin variants, whose low-temperature theory is weaker.The state-dependent approaches retain enough structure to guide design.Source: §2.2 · p. 11

2.3 Complexity comparisons

  • Choosing many independent runs while preserving low-temperature conditions dramatically reduces complexity versus simulated annealing or fixed-temperature Langevin; approaches 1 and 2 otherwise share essentially the same exponential dependence on confidence and accuracy.The approximation is stated to become tight as N/L → 0 and temperature vanishes.Source: §2.3 · pp. 11–12

2.4 Prior knowledge required for implementation

  • LGRM avoids online membership tests by retaining the best observed state, though S and η remain PAC-analysis inputs; its global information needs are essentially those of classical simulated annealing.By contrast, first-entry switching requires an online test for membership in S.Source: §2.4 · pp. 13–14

2.5 Challenges in high dimensions

  • In restart, best-of-N success follows an order statistic, with geometric decay of exceedance, but high-dimensional near-optimal mass may shrink rapidly; Langevin adds temperature as a design variable.The analysis distinguishes fixed-temperature restart from accuracy-dependent temperature selection.Source: §2.5 · p. 14
  • O(n^-2/d) convergence of the running minimum exhibits a curse of dimensionality; for quadratic objectives, α = d/2, so large dimensions can make convergence very slow.The geometric exceedance-probability rate has an exponent determined by the objective-energy CDF near zero.Source: §2.5 · pp. 14–15
  • n^(1/α)M_n converges in distribution to M with CDF 1 − exp(−ct^α), and the mean of M_n also vanishes at rate O(n^-2/d).The limit law applies when F(x) ∼ cx^α as x ↓ 0.Source: §2.5 · p. 15
  • ε^-d/2 dependence at fixed temperature improves to ε^-1 with accuracy-dependent temperature for every fixed d > 2, but the result is not uniform in dimension.Dimension-dependent prefactors can still be substantial, and the proposition is asymptotic for each fixed dimension.Source: §2.5 · pp. 16–17
  • The accuracy-dependent temperature result counts independent Gibbs samples but assigns no cost to generating them; low temperature generally lengthens Langevin mixing time.Thus its sample-count improvement does not by itself characterize the simulation work needed to produce those samples.Source: §2.5 · p. 17

3 Numerical Results

The numerical studies compare PAC work across Langevin–gradient schemes and simulated annealing, and test how parameter choices and spectral barriers shape exploration. They find both useful low-temperature predictions and substantial temperature sensitivity in the six-hump camel experiments.

3.1.1 Computational work

  • Work is a calibrated sum of measured primitive-operation costs, expressed in seconds rather than the vectorized MATLAB implementation’s wall-clock running time.The implementation approximates diffusion and gradient flow recursively using an Euler scheme or another discrete-time approximation.Source: §3.1.1 · p. 17, §3 · p. 17

3.1.2 Choice of parameters

  • E=2E• predicts some low-dimensional experiments well, but the theory only requires E to exceed E•; E=4E• halves predicted temperature and fits less well.The theory is not intended to prescribe universal N or temperature values; estimated local accuracy η informs both parallel exploration N and ρ.Source: §3.1.2 · p. 18

3.2 Six hump camel function

  • The six-hump camel has two global minima and a dominant barrier near 1.032, but violates the global Lipschitz-gradient assumption unless modified outside a large compact set.The modified objective is required to be C2 and satisfy the remaining assumptions.Source: §3.2 · p. 18

3.2.1 Comparison with simulated annealing

  • In the LGRM example, exploration continues after the best state is retained at σ0RM, then gradient descent starts from that state and exhibits exponential convergence.The illustrated horizons are t≤2 for LGRMρ,N and t≤50 for simulated annealing.Source: §3.2.1 · p. 19
  • 0.0529 seconds for LGRMρ,N versus 2.22 seconds for simulated annealing in the six-hump camel PAC work estimates.The simulated-annealing temperature was selected as best among a large grid; Figure 2 plots LGRM failure probability against work.Source: §3.2.1 · p. 19, Figure 2 · p. 19

3.2.2 Spectral analysis

  • The zero set of h2 is a stochastic barrier: from the specified initial condition, reaching the optimizer in the opposite nodal domain occurs on the spectral-gap slow time scale.The second eigenvalue λ2=−rρ is not repeated, with |λi|>rρ for i≥3.Source: §3.2.2 · pp. 20–22
  • Raising ρ from 0.2 to 10 significantly reduces switching time on average; at ρ=10 one successful run entered S at τη<0.1.At ρ=0.2, the spectral gap is approximately 0.01858; at ρ=10 it is approximately 5.2908.Source: §3.2.2 · pp. 21–22, Figure 6 · p. 22
  • Across a substantial temperature range, log(rρ) is approximately affine in 1/ρ with slope close to −E•, where E•≈1.03162845.The paper also presents a sharper approximation under additional assumptions using an Eyring–Kramers prefactor.Source: §3.2.2 · p. 23, Figure 8 · p. 23

3.3 Objective with many local minima

The Rastrigin objective has a unique minimizer at zero, while its many local minima make performance sensitive to both temperature and dimension. The experiments examine spectral-gap structure, finite-temperature design, and the resulting PAC work.

3.3.1 Spectral analysis

  • The dominant energy barrier is E• = 19.2563… and independent of dimension; the d-dimensional spectral gap equals the one-dimensional gap, with λ2 = −rρ having multiplicity d.For d = 2, the spectral-gap plots show λ2 = λ3 = −rρ and an associated two-dimensional eigenspace.Source: §3.3.1 · p. 24
  • In a representative d = 2 run at ρ = 50, Langevin exploration traversed many local wells before entering the target set, after which gradient flow approached the minimizer exponentially.Noise is removed at the entrance time to the target set S = {x : Γ(x) − Γ⋆ < 0.5}.Source: §3.3.1 · p. 24
  • With N = 300, the best observed performance was similar to N = 24, but the acceptable temperature range improved.For N = 24, the maximal-temperature prediction substantially underestimated the best temperature in the example.Source: §3.3.1 · p. 24
  • In 200 trials, simulated annealing had zero successes across the tested K values; its gradual cooling spent substantial work approaching temperatures already effective for LGRM.LGRM instead explores directly at ρ = 4, retains the best state, and then switches to deterministic gradient descent.Source: §3.3.1 · p. 27

3.3.2 Dimension dependency and finite-temperature design

  • For d = 5, the minimum work to meet the PAC criterion rose from a fraction of a second to about one minute.The d = 5 results were qualitatively consistent with d = 2.Source: §3.3.2 · p. 27, Figure 15 · p. 28
  • In d = 10, the empirical PAC boundary was U-shaped and minimized near ρ ≈ 2.2, far below the low-temperature rule’s nominal ρmax ≈ 23.The nominal temperature lies outside the low-temperature regime, so that approximation is not expected to provide useful finite-temperature tuning here.Source: §3.3.2 · pp. 27–28
  • At ρ = 2.2, the setting with smallest empirical work had observed failure probability 0.04 and calibrated work 8.69 hours, in 100 independent trials using several exploration horizons.Source: §3.3.2 · p. 28
  • The section’s experiments underscore that computational complexity is highly temperature-sensitive and rises dramatically with dimension.The d = 10 objective has approximately 10^18 local minima and only one global minimizer.Source: §3.3.2 · pp. 27, 29

3.4 Griewank

On the two-dimensional Griewank objective, the experiments compare LGRM with simulated annealing. LGRM meets the PAC criterion at much lower reported work, while simulated annealing misses the target confidence in the tested budget.

3.4 Griewank

  • The two-dimensional Griewank objective has a unique minimizer at zero and an energy barrier of approximately 0.997, but meeting the assumptions requires η < 0.0074.The small η motivates using a large number of LGRM trajectories.Source: §3.4 · p. 29, §3.4.1 · p. 30

3.4.1 Comparisons

  • The simulated-annealing experiment reached the target set in 63.5% of trials, leaving its observed miss probability well above δ = 0.05.The authors therefore expect the work needed for simulated annealing to satisfy the PAC criterion to be substantially more than 446 seconds.Source: §3.4.1 · p. 29
  • The paper reports that required computational work falls below 10 seconds when using LGRM.The experiment concerns the two-dimensional Griewank objective.Source: §3.4.1 · p. 30
  • LGRM achieved the PAC constraint with 1 second of work over a broad temperature range, whereas simulated annealing’s empirical failure probability remained about 0.76 at 89.2 seconds.For simulated annealing, 63.5% of 1,000 trials reached the target set, below the required 95% success rate.Source: §3.4.1 · pp. 29–30

4 Low Temperature Approximations

This section develops low-temperature approximations for spectral gaps and Gibbs probabilities and applies them to PAC run-time analyses of simulated annealing and Langevin variants as ρ decreases to zero. For parallel Langevin–gradient exploration with fixed N, it also describes how the spectral gap governs the logarithmic-scale approximation of required exploration time.

4.1.1 Spectral theory

  • The spectral gap is identified with the negative second eigenvalue, and the diffusion has a discrete spectrum and exponential ergodicity under Assumption 1.1.The L2 spectral gap coincides with the gap defined through the extended generator.Source: §4.1.1 · pp. 31–32

4.1.2 Low temperature approximations

  • For isolated, non-degenerate global minima, sharper Laplace approximations yield a Gaussian approximation; the section also gives logarithmic spectral-gap asymptotics.The logarithmic Laplace principle determines set probabilities at exponential scale from the minimum objective value over each set.Source: §4.1.2 · pp. 34–35

4.2 Simulated annealing

  • T1 ≈ exp(E L/ε) when ε is fixed and E > E• + 2ε in the logarithmic cooling schedule.Here L = log(1/δ), and T1 is the time to achieve the PAC requirement.Source: §4.2 · p. 36

4.3 Fixed-temperature Langevin

  • For fixed-temperature Langevin, Proposition 4.7 optimizes run time over ρ subject to the PAC requirement, with fixed E > E• and ρ2 given by (29).The approximation is considered for fixed ε as δ decreases to zero.Source: §4.3 · p. 37

4.4 Parallel Langevin

  • Parallel Langevin uses N independent copies and chooses the run length so that the one-run failure probability QT(ρ) raised to N is at most δ.Proposition 4.8 treats fixed E > E• and ρ3 given by (29).Source: §4.4 · p. 38

4.5 Parallel Langevin–gradient

  • Parallel Langevin–gradient first seeks at least one terminal point in S, then uses deterministic gradient descent after the switching time to supply final accuracy.Proposition 4.9 specifies conditions on temperature scaling and fixed N for its approximation as δ decreases to zero.Source: §4.5 · p. 38
  • With fixed N, the O(L) logarithmic term is negligible on the logarithmic scale because the spectral gap rρ grows exponentially with L.Thus only the spectral gap is significant in the approximation of required exploration time.Source: §4.5 · p. 39

5 Conclusions

The conclusions argue for separating stochastic exploration from deterministic exploitation in PAC global optimization. Independent restarts can reduce high-confidence exploration cost, while gradient flow supplies terminal accuracy; the analysis is primarily based on low-temperature approximations.

5 Conclusions

  • Independent restart can greatly reduce high-confidence global-exploration cost, and separating exploration from exploitation further improves the Langevin-based schemes.Exploration locates a region of attraction, after which gradient flow supplies final accuracy at cost O(log(1/ε)).Source: §5 · p. 39
  • Exploration should stop once a trajectory reaches a region where deterministic dynamics are reliable; further stochastic exploration is described as wasteful.The conclusion links this allocation to using sufficiently high temperature for exploration and then exploiting the favorable region.Source: §5 · p. 39
  • The analysis relies primarily on low-temperature approximations involving the dominant barrier E•, attraction margin η, and confidence parameter L = log(1/δ).The authors identify moderate-temperature theory as a future direction, noting that low-temperature methods carry additional computational cost.Source: §5 · p. 39

A Rastrigin objective

The Rastrigin objective has a global minimum at the origin and neighboring nonglobal wells separated by local maxima. Its spectral gap is independent of dimension but has multiplicity d, so in dimensions above one it does not determine a unique nodal partition.

A Rastrigin objective

  • The function g is even, nonnegative, and has its unique global minimum at the origin.The one-dimensional potential is given as g(z) = 10 + z2 − 10 cos(2πz).Source: A Rastrigin objective · p. 43, Figure 19 · p. 44
  • The global minimum is at z = 0, the first neighboring local minima are at z = ±m, and the intervening local maxima are at z = ±s.The barrier supremum is attained for the pair (0, m), or symmetrically (0, −m).Source: A Rastrigin objective · pp. 43–44
  • The d-dimensional spectral gap is independent of dimension and has multiplicity d.For d > 1, the associated eigenspace has no distinguished eigenfunction, so its members can have different zero sets.Source: A Rastrigin objective · p. 45
  • When the spectral gap is simple, its eigenfunction is unique up to a nonzero scalar, fixing the zero set and nodal domains up to interchange.In contrast, for Rastrigin in d > 1, the gap eigenvalue has multiplicity d and does not determine a unique two-way partition.Source: A Rastrigin objective · p. 45

B Impact of dimension

The dimension-dependent derivation invokes the small-target conclusion with rρ = ε. It expresses the probability that the minimum among n samples exceeds ε in terms of the target probability pε.

B Impact of dimension

C Calibrated computational-work model

The computational-work model uses measured primitive-operation costs and defines plotted work from the discrete run length. State-copy cost is tracked separately as a diagnostic and excluded from that work.

C Calibrated computational-work model

C.1 One Langevin exploration path

The work model accounts for the cost of one exploratory Langevin trajectory at design (ρ, a). Each Euler step includes objective-gradient evaluation, Gaussian sampling, and comparison with the running minimum.

C.1 One Langevin exploration path

  • The one-path work expression is defined for an exploratory Langevin trajectory at design (ρ, a).An initial cΓ,∇ term accounts for evaluating the objective and gradient at the initial state.Source: §C.1 · p. 46
  • Each Euler step requires one joint objective–gradient evaluation, one Gaussian vector, and one comparison with the running minimum.Source: §C.1 · p. 46

C.2 Gradient descent

The section introduces the computational work associated with the single exploitation phase.

C.2 Gradient descent

  • The section introduces the computational work of the single exploitation phase.Source: §C.2 · p. 46

C.3 Total Langevin–gradient work

With a fixed stochastic step size, temperature primarily changes success probability rather than work; the code also charges for selecting the best retained exploratory state, a negligible term in these experiments.

C.3 Total Langevin–gradient work

  • The extra ccmp(N −1) charged for selecting the best retained state among N exploratory trajectories is negligible in these experiments.Source: §C.3 · p. 47
  • With a fixed stochastic step size, fixing a essentially fixes W RM, so temperature primarily affects performance through success probability rather than work.Source: §C.3 · p. 47
Loading 2609.06196v2…