Stochastic restarting with multiple restart conditions
Johannes Aspman, Daniel Mastropietro, Jakub Mareček · 2025
Read Stochastic restarting with multiple restart conditions by Johannes Aspman, Daniel Mastropietro, Jakub Mareček (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-11809.txt.
Introduction
Johannes Aspman, Daniel Mastropietro, and Jakub Marecek ask how resetting a wandering particle changes its arrival time. This 2025 statistical physics paper treats a diffusing particle of Langevin type. The particle is teleported back to its start at some rate. The question is the mean first passage time to a target. The reset rate may vary with position.
Quadratic and piecewise-quadratic potentials are studied. The benefit of resetting hinges on the drift-to-noise ratio. It grows as drift weakens against noise. When the target sits at a local optimum of the potential, a spatial strategy wins. Reset less often near the target. Reset more often far away. The folklore that resetting always helps gets refined.
Catalog record
| CREATOR | Johannes Aspman, Daniel Mastropietro, Jakub Mareček |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 21 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-11809
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stochastic restarting with multiple restart conditions Johannes Aspman, Daniel Mastropietro, Jakub Mareček Abstract We consider the mean first passage time (MFPT) for a diffusive particle in a potential landscape with the extra condition that the particle is reset to its original position with some rate r r . We study non-smooth and non-convex potentials and focus on the case where the restart rate depends on the space coordinate. There, we show that it is beneficial to restart at a lower rate once you are closer to your intended target. I Introduction Searching for a given target is something we do every day, and it is a ubiqituous problem in modern technology and research. For example, enzymes searching for a target site in a DNA strand eliazar2007searching , neural network training algorithms searching for an optima lecun2015deep , or simply when we are looking for our keys in the morning. Restarting strategies for searching are built on the simple idea that after performing the search for some amount of time a natural step might be to return to a given point and start your search again. A natural question is to ask whether restarting provably speeds up the search. In their seminal papers evans2011diffusion ; evans2011diffusionA ; evans2014diffusion , Evans and Majumdar answer the question in a model, where a diffusion process has a non-zero probability rate of restarting to a given point. Similar models have also been proposed by other authors benichou2007intermittent ; gelenbe2010search ; janson2012hitting , and many extensions of Evans and Majumdars approach have been studied pal2017first ; roldan2017path ; evans2020stochastic ; ahmad2019first ; pal2019landau ; ray2019peclet ; ray2020diffusion ; bonomo2021first ; ahmad2022first recently, largely within statistical mechanics. Restarting has also been studied in mathematical optimization for many years as a way of speeding up algorithms luby1993optimal ; alt1996method . In AI and computer science, there is a long history of engineering local-search algorithms with restarts kautz2002dynamic ; tong2008random ; Shylo2018 ; yu2019parallel ; loshchilov2022sgdr ; bae2024stochastic . In particular, much of the literature gagliolo2007learning ; wedge2008heavy ; roulet2017sharpness ; lorenz2021restart ; renegar2022simple ; starkov2023universal focuses on convex, smooth cases. For example, roulet2017sharpness ; renegar2022simple studies various first-order methods and show that restarting can be used to accelerate these. lorenz2021restart discusses Luby’s luby1993optimal restart strategy in a continuous setting and starkov2023universal derives universal performance bounds on general restarting strategies for stochastic processes. The non-smooth non-convex setting davis2020stochastic ; berner2021modern , while clearly relevant in AI and machine learning, has not been given much attention in the restarting literature. The noteable exception is Ahmad et al. ahmad2022first , who study piecewise-linear potentials as well as smooth, but non-convex, potentials. In this paper, we extend the work of Evans and Majumdar evans2011diffusion ; evans2020stochastic ; ahmad2022first to non-smooth, non-convex potentials and restart rates conditional on the objective-function value. In the case where the optimum is known, it may seem intuitive to restart less often, once a threshold close to the optimum is reached, for instance. Notice that this is an important special case, considering that empirical risk is bounded from below by 0 in most machine learning applications, but the optimum is also bounded from above by 0 in the overparametrized regime lecun2015deep . Specifically, we consider a piecewise quadratic potential for the diffusion process. We also introduce a piecewise-constant restart rate, depending on the objective-function value. We show that the mean first passage time (MFPT) can be reduced when one considers the piecewise-constant restart rate, conditional on the objective-function value, rather than any single restart rate, or no restart at all. II Problem statement and background As mentioned in the introduction, we will consider not pure diffusion but rather diffusion with drift, or diffusion in a potential landscape. In other words, we are considering a process \dot{x}=\mu F(x)+\eta(t), (1) where F(x)=-\partial_{x}V(x) for some potential V(x) , \mu is a parameter that measures the mobility of the particle (we will set \mu=1 for brevity in the rest of the paper), and \eta(t) is a Gaussian white noise with the properties \langle\eta(t)\rangle=0,\quad\langle\eta(t)\eta(t^{\prime})\rangle=2D\delta(t-t^{\prime}), (2) where D>0 is the diffusion constant and \delta(t) the Dirac delta function pal2015diffusion . We will focus our analysis on the mean first passage time (MFPT) T(x) for the particle to reach a target L from the point x . It is well-known, redner2001guide , that the MFPT is infinite for a pure diffusive particle (or random search), while evans2011diffusion showed that in the presence of restarting it becomes finite. The standard starting point for MFPT analysis is the backward Chapman-Kolmogorov equation, which governs the probabilty, Q(x,t) , that the particle has not reached the desired target up to time t , starting from position x . The equation reads \frac{\partial Q(x,t)}{\partial t}=D\frac{\partial^{2}Q(x,t)}{\partial x^{2}}-V^{\prime}(x)\frac{\partial Q(x,t)}{\partial x}-r(x)Q(x,t)+r(x)Q(x_{0},t), (3) where we for brevity have set \mu=1 and we have the boundary conditions Q(L,t)=0 , Q(x,0)=1 , and x_{0} is the initial point as well as the point which the process restart to. We note that -\tfrac{\partial Q(x,t)}{\partial t}\mathrm{d}t measures the probabilty that the particle hits the target in the time t\to t+\mathrm{d}t , we find the MFPT by integrating T(x)=-\int_{0}^{\infty}t\frac{\partial Q(x,t)}{\partial t}\mathrm{d}t=\int_{0}^{\infty}Q(x,t)\mathrm{d}t, (4) and we have the equation -1=D\frac{\partial^{2}T(x)}{\partial x^{2}}-V^{\prime}(x)\frac{\partial T(x)}{\partial x}-r(x)T(x)+r(x)T(x_{0}), (5) for the MFPT, with boundary conditions T(L)=0 and T(x) remains finite as x\to\infty evans2011diffusionA ; evans2020stochastic . Ahmad et al., ahmad2019first , studies the situation where the potential is a polynomial, V(x)=kx^{n} with k,n>0 , and where the restarting rate is constant. See also ray2019peclet , for the linear case and ray2020diffusion for the case of a logarithmic potential, V(x)=V_{0}\log(|x|) . We will expand on this in two ways. Firstly, instead of a constant restart rate we will consider having a piecewise constant restart rate, i.e., where the restart rate is allowed to change when we move around in space. Secondly, rather than smooth polynomial potentials we will consider piecewise polynomial potentials. A piecewise linear potential was studied in ahmad2022first , while we focus on piecewise quadratic. For us, the initial motivation for studying the piecewise polynomial potential comes from modern machine learning applications where this is the predominant structure of the training landscape berner2021modern . The inspiration of studying the effect of having a piecewise-constant restart rate comes from different types of informed restarting strategies such as gradient-informed restart Mastropietro:2023vcm which have been shown to be beneficial in many situations. Let us review quickly some of the previous results from ahmad2019first . For brevity, and as above, we will assume that the particle will restart from the initial position x=x_{0} . In general, Equation ( 5 ) is very difficult to solve, but when r(x) and V(x) take some simple forms we can solve it analytically. When we have a constant restart rate r(x)=r and polynomial potential V(x)=kx^{n} we get the equation -1=D\frac{\partial^{2}T(x)}{\partial x^{2}}-knx^{n-1}\frac{\partial T(x)}{\partial x}-rT(x)+rT_{0}, (6) where we introduced the notation T(x_{0})\coloneqq T_{0} . Analytic solutions does not exist for n>3 , so we focus on the case of n=2 . This was studied in ahmad2019first . The general solutions are now T(x)=AH_{-\tfrac{r}{2k}}\left(\sqrt{\tfrac{k}{D}}x\right)+B\,{}_{1}F_{1}\left[\tfrac{r}{4k},\tfrac{1}{2};\tfrac{k}{D}x^{2}\right]+\tfrac{1}{r}+T_{0}, (7) where H_{n}(x) are the Hermite polynomials and {}_{1}F_{1}[a,b;x] the Kummer confluent hypergeometric function. The boundary conditions are that this should be finite for x\to\infty and that T(L)=0 , for some target