betaFeedback

WorksEngineering

Metropolis Random Walks Escape Deep Basins Faster in Higher Dimensions

Abstract

Simulated Annealing (SA) is a widely used stochastic optimization algorithm. It is of great interest to understand how its ability to escape local minima at a fixed temperature depends on geometry and dimension. In prior work, we derived closed-form expressions for the expected basin escape time of a constant-temperature SA process on a one-dimensional piecewise-linear landscape. In this paper, we extend the analysis to DD-dimensional cubic basins defined by the infinity-norm energy V(x)=∥x∥∞V(x)=\|x\|_\infty. The walk proposes nearest-neighbor moves uniformly and escapes upon first reaching the outer shell, that is, any site with ∥x∥∞=N\|x\|_\infty=N. We construct a one-dimensional birth-death shell-quotient chain by collapsing each concentric shell in the Metropolis electrical network to a single node while retaining its total stationary mass. We derive a closed-form expression for the mean escape time QD(N)Q_D(N) of this shell-quotient chain as a function of the acceptance probability pp, the basin depth NN, and the dimension DD. For fixed DD and fixed 0<p<10<p<1, the quotient escape time scales as Θ(αN/ND−1)Θ(α^N/N^{D-1}) as N→∞N\to\infty, where α=1/pα=1/p. Relative to D=1D=1, this gives an asymptotic speedup of order ND−1N^{D-1} within this family of cubic basins. We prove that the true Metropolis mean escape time HD(N)H_D(N), without shell averaging, has the same Θ(αN/ND−1)Θ(α^N/N^{D-1}) scaling, establishing a lower bound via Rayleigh monotonicity and a matching upper bound through an explicit low-energy flow construction using Thomson's principle. Numerical solutions that exploit the walk's symmetries quantify the discrepancy between the quotient and true-chain means for D=1,2,3D=1,2,3.

Paper details

vlnc:W_56hkeurq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Engineering

ChatGPT, Claude, Grok (multiple versions)

View statement
Looking for related papers…