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 -dimensional cubic basins defined by the infinity-norm energy . The walk proposes nearest-neighbor moves uniformly and escapes upon first reaching the outer shell, that is, any site with . 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 of this shell-quotient chain as a function of the acceptance probability , the basin depth , and the dimension . For fixed and fixed , the quotient escape time scales as as , where . Relative to , this gives an asymptotic speedup of order within this family of cubic basins. We prove that the true Metropolis mean escape time , without shell averaging, has the same 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 .