# Universal performance bounds of restart

Dmitry Starkov1,2 and Sergey Belan1,3<EMAIL_ADDRESS>1Landau Institute for
Theoretical Physics, Russian Academy of Sciences, 1-A Akademika Semenova av.,
142432 Chernogolovka, Russia  2National Research University Higher School of
Economics, Faculty of Mathematics, Usacheva 6, 119048 Moscow, Russia
3National Research University Higher School of Economics, Faculty of Physics,
Myasnitskaya 20, 101000 Moscow, Russia

###### Abstract

As has long been known to computer scientists, the performance of
probabilistic algorithms characterized by relatively large runtime
fluctuations can be improved by applying a restart, i.e., episodic
interruption of a randomized computational procedure followed by
initialization of its new statistically independent realization. A similar
effect of restart-induced process acceleration could potentially be possible
in the context of enzymatic reactions, where dissociation of the enzyme-
substrate intermediate corresponds to restarting the catalytic step of the
reaction. To date, a significant number of analytical results have been
obtained in physics and computer science regarding the effect of restart on
the completion time statistics in various model problems, however, the
fundamental limits of restart efficiency remain unknown. Here we derive a
range of universal statistical inequalities that offer constraints on the
effect that restart could impose on the completion time of a generic
stochastic process. The corresponding bounds are expressed via simple
statistical metrics of the original process such as harmonic mean $h$, median
value $m$ and mode $M$, and, thus, are remarkably practical. We test our
analytical predictions with multiple numerical examples, discuss implications
arising from them and important avenues of future work.

Introduction. Restarting was first proposed as a promising optimization tool
of probabilistic algorithms in the early 1990s (Alt_1991, ; Luby_1993, ). The
restart-induced speed up may seem counterintuitive at first glance, but the
basic idea behind this technique is quite transparent: if the current
realization of the randomized algorithm takes too long, it may be faster (on
average) to retry attempt with a new random seed to avoid prolonged wandering
in the region of the configuration space far from the actual solution. Since
then, restarting has become a routine procedure used to hasten computational
tasks whose run-time exhibits significant fluctuations Lorenz_2018 ;
Lorenz_2019 ; Lorenz_2021 ; Montanari_2002 ; Moorsel_2004 ; Wu_2006 ;
Gagliolo_2007 ; Wu_2007 ; Streeter_2007 ; Wedge_2008 ; Roulet_2017 ;
Gomes_1997 ; Biere_2009 ; Huang_2007 ; Wolter_thesis . In particular, the
option of restart is built into state-of-art constraint satisfaction problem
solvers Schulte_2010 ; Cire_2014 ; Amadini_2018 ; Wallace_2020  (see also
Schroeder_2001 ; Moorsel_2006  for other computer science applications).

A current wave of interest to this topic from the statistical physics
community has been sparked by the work of Evans and Majumdar EM_2011  who
showed that stochastic (Poisson) restart expedites diffusion-mediated search.
After that it has been demonstrated on a number of different examples that a
specially selected restart frequency makes it possible to minimize the average
time for completing random search tasks Evans_2011 ; Whitehouse_2013 ;
Evans_2014 ; Kusmierz_2014 ; Kusmierz_2015 ; Pal_2016 ; Eule_2016 ; Nagar_2016
; Kusmierz_2019 ; Ray_2020 ; Singh_2020 ; Ahmad_2020 ; Radice_2021 ;
Faisant_2021 ; Calvert_2021 ; Mercado_2021 ; Bonomo_2021 ; Tucci_2022 ;
Ahmad_2022 ; Chen_2022 ; Abdoli_2021 ; Ray_2019a ; Santra_2020a ; Evans_2016c
; Evans_review_2020 ; Chechkin_2018b . Also, recent development of a model-
independent renewal approach, originally proposed for the purposes of
describing the single enzyme kinetics Reuveni_2014 , has provided a shortcut
to the exact completion time statistics of an arbitrary stochastic process
under an arbitrary restart protocol Rotbart_2015 ; Reuveni_PRL_2016 ;
Reuveni_PRL_2017 . This fruitful approach helped to reveal unexpected
universality in statistics of optimally restarted processes Reuveni_PRL_2016 ,
to establish remarkably simple sufficient conditions for when restart is
beneficial Reuveni_PRL_2016 ; Pal_JPA_2022 ; Eliazar_JPA_2021  and to
rigorously quantify impact of restart on various statistical characteristics
of random processes Belan_PRL_2018 ; Belan_PRR_2020 ; Eliazar_arxiv_2022 ;
Eliazar_arxiv_2022b .

The natural course of development of the research field poses the following
question to us: What, if any, are the fundamental limitations of the
optimization via restart? The knowledge of the exact completion time
distribution allows to determine the optimal restart strategy (which may be to
not restart at all) and the corresponding best possible performance for a
given stochastic process. In practice, however, the complete statistics of the
completion time is usually unavailable, see, e.g., Luby_1993 ; Gagliolo_2007 ;
Reuveni_2014 ; Lorenz_2018 ; Lorenz_2021 ; Wu_2007 ; Streeter_2007 . The
existing literature lacks understanding of how to evaluate the potential
performance of restart based on some limited set of statistical
characteristics of an observable process. In this Letter we fill this gap by
exploring how much restart can lower the expected completion time of a
stochastic process with partially specified properties. More specifically, we
present the universal lower bound on the mean completion time respected by any
stochastic process under an arbitrary restart protocol. Besides, we construct
the universal upper bound on the mean completion time of generic stochastic
process at optimal restart conditions. Both types of probabilistic
inequalities are generalized to the high order statistical moments of random
completion time. Being formulated in terms of easily interpreted statistical
characteristics of an unperturbed stochastic process, the resulting bounds
provide valuable insight into what restart can and cannot do. As a useful
corollary, our analysis provides a novel sufficient condition for restart to
be beneficial which requires very little information on the statistics of the
random process of interest. Finally, we propose a broad generalization of the
well-known inequality offering constraint on the relative fluctuation of the
expected completion time of optimally restarted processes.

Model formulation. Consider a generic stochastic process which ends after a
random time $T$ if allowed to take place without interruptions. Statistical
properties of the variable $T$ are described by the probability density $P(T)$
with a proper normalization $\int_{0}^{\infty}dTP(T)=1$. This implies that the
process terminates in finite time with probability 1. As discussed below, our
key results remain unchanged or require a trivial modification when one
introduces the non-zero probability of never stopping.

The restart protocol ${\cal R}$ is characterised by a (possibly infinite)
sequence of inter-restarts time intervals $\tau_{1},\tau_{2},\dots$. If the
process is completed prior to the first restart event, the story ends there.
Otherwise, the process will start from scratch and begin anew. Next, the
process may either complete prior to the second restart or not, with the same
rules. This procedure repeats until the process finally reaches completion.
Importantly, we assume that protocol ${\cal R}$ is uncoupled from the process
internal dynamics: the restart decisions do not use information on the current
internal state of the process.

In the simplest case of strictly periodic protocol, which is of particular
methodological importance as explained below, the process is restarted
whenever $\tau$ units of time pass. The expected value of the random
completion time $T_{\tau}$ of the process subject to such a restart procedure
can be obtained by averaging of an appropriate renewal equation. The result is
given the following expression

$\langle
T_{\tau}\rangle=\frac{\int_{0}^{\tau}P(T)TdT+\tau\int_{\tau}^{\infty}P(T)dT}{\int_{0}^{\tau}P(T)dT},$
(1)

which, thus, relates the expectation of the random completion time in the
presence of periodic restart to the statistics of the ”bare” (i.e. restart-
free) process.

Restart performance is limited to a quarter of the harmonic mean completion
time. First of all, we seek to derive inequality of the form $\langle T_{\cal
R}\rangle\geq C{\cal T}$, where $T_{\cal R}$ denotes the random completion
time of the generic stochastic process under arbitrary restart protocol ${\cal
R}$, ${\cal T}$ is expressed through some simple statistical characteristics
of the original process (such as statistical moments, quantiles or mode of the
probability density $P(T)$), and $C$ is the universal positive constant which
depends neither on specific form of $P(T)$ nor on the particular restart
schedule ${\cal R}$.

Previous works have shown the importance of relative fluctuation $\sigma/\mu$,
where $\mu=\langle T\rangle$ and $\sigma=\sqrt{\langle T^{2}\rangle-\langle
T\rangle^{2}}$, for the analysis of the potential response of stochastic
process to restart. Namely, the inequality $\sigma/\mu>1$ represents a
sufficient condition for the existence of a restart protocol that reduces the
expected completion time Rotbart_2015 ; Reuveni_PRL_2016 ; Pal_JPA_2022 .
Given this result, let us first find out if knowledge of the mean value $\mu$
and the standard deviation $\sigma$ allows one to write a lower bound on the
average performance of restart. Consider, probability density
$P(T)=p\delta(T-t_{1})+(1-p)\delta(T-t_{2})$, where $0\leq t_{1}\leq t_{2}$
and $0\leq p\leq 1$. Putting $t_{2}=\frac{\mu^{2}+\sigma^{2}}{\mu}$,
$p=\frac{\sigma^{2}}{\mu^{2}+\sigma^{2}}$, $\tau=t_{1}+0$ and $t_{1}\to 0$,
one immediately obtains From Eq. (1) $\langle T_{\tau}\rangle=t_{1}/p\to 0$.
We see that for the fixed values of $\mu$ and $\sigma$, the completion time
$\langle T_{\tau}\rangle$ can be arbitrarily small. Therefore, the pair
$(\mu$,$\sigma)$ does not produce any non-trivial lower bound.

Our derivation of the desired lower bound limit is based on the special
properties of the periodic restart strategy. As shown by Luby et al. Luby_1993
for discrete time case and generalized to continuous settings by Lorenz
Lorenz_2021  (see also SM  for simpler and even more general proof), if you
found a value $\tau_{\ast}\geq 0$ (probably $\tau_{\ast}=+\infty$) such that
$\langle T_{\tau_{\ast}}\rangle\leq\langle T_{\tau}\rangle$ for any $\tau\geq
0$, then $\langle T_{\tau_{\ast}}\rangle\leq\langle T_{\cal R}\rangle$ for all
${\cal R}$. In other words, optimally tuned periodic restart beats any other
restart strategy. In addition, the same authors have proved (see also SM )
that the mean performance of an optimal periodic restart obeys the condition

$\langle
T_{\tau_{\ast}}\rangle\geq\frac{1}{4}\min_{\tau}\frac{\tau}{Pr[T\leq\tau]}.$
(2)

Figure 1:  Diagram in the $x-y$ plane, where $x=h/(4\langle
T_{\tau_{\ast}}\rangle)$ and $y=\langle T_{\tau_{\ast}}\rangle/(2m)$,
depicting relationship between mean completion time of an optimally restarted
process $\langle T_{\tau_{\ast}}\rangle$, the median $m$ and the harmonic mean
$h$ of the original process. As indicated in a legend, each point in these
diagrams corresponds to a specified completion time distribution $P(T)$. In
accordance with Eqs. (3) and (5) and probabilistic inequality $h\leq 2m$ all
points belong to the light orange region determined by the conditions $0\leq
x\leq 1$, $0\leq y\leq 1$, $y\leq 1/(4x)$.

Let us show that using Eq. (2) together with the optimal property of the
periodic restart strategy leads to a simple performance bound of restart.
Namely, applying Markov’s inequality Gallager_2013  to the variable
$\omega=1/T$ we find
$\text{Pr}[T\leq\tau]=\text{Pr}[\omega\geq\frac{1}{\tau}]\leq\tau\langle\omega\rangle=\tau\langle\frac{1}{T}\rangle$.
Next, taking into account Eq. (2) one obtains $\langle
T_{\tau_{\ast}}\rangle\geq\frac{1}{4}h$, where $h=\langle T^{-1}\rangle^{-1}$
is the harmonic mean completion time of the original process. And finally,
since $\langle T_{\cal R}\rangle\geq\langle T_{\tau_{\ast}}\rangle$ for any
${\cal R}$, this yields

$\langle T_{\cal R}\rangle\geq\frac{1}{4}h.$ (3)

No constraints have been imposed on the form of $P(T)$, and, therefore, Eq.
(3) is universally valid for any setting. What is more, this estimate remains
valid also when stochastic process may have non-zero probability of never
ending, if $h$ is always understood as the harmonic mean completion time of
the halting trials note0 .

Particular case of smooth unimodal distribution. Somewhat less general, but
still informative, result can be obtained if we assume that the completion
time distribution $P(T)$ is smooth and exhibits single local maximum at some
non-zero value of $T$. This class of probability densities covers, in
particular, vast number of random search models, see, e.g., Refs. EM_2011 ;
Evans_2014 ; Evans_review_2020 ; Kusmierz_2014 ; Kusmierz_2015 ; Singh_2020 ;
Abdoli_2021 ; Tucci_2022 ; Ray_2019a ; Santra_2020a ; Evans_2016c . The
efficiency of any restart protocol in this case satisfies the inequality

$\langle T_{{\cal R}}\rangle\geq\frac{1}{4}M,$ (4)

where $M=\text{argmax}_{T}P(T)>0$ is the mode of the probability distribution
$P(T)$, i.e. the value of the random completion time $T$ that occurs most
frequently. To prove this result let us introduce
$\tau_{0}\equiv\text{argmin}_{\tau}\frac{\tau}{\text{Pr}[T\leq\tau]}$.
Clearly, assumption $M>0$ implies that $\tau_{0}>0$. Since the smooth function
$f(\tau)=\frac{\tau}{\text{Pr}[T\leq\tau]}$ attains its minimal value at
$\tau=\tau_{0}$, one obtains $df(\tau_{0})/d\tau=0$ or, equivalently,
$P(\tau_{0})\tau_{0}=\int_{0}^{\tau_{0}}P(T)dT$. Next, as the unimodal
function $P(T)$ is non-decreasing on the interval form $0$ to $M$, this
extrema condition implies the inequality $\tau_{0}\geq M$ and, therefore,
$\frac{\tau_{0}}{\text{Pr}[T\leq\tau_{0}]}\geq\frac{M}{\text{Pr}[T\leq\tau_{0}]}\geq
M$. Together with Eq. (2) this yields inequality $\langle
T_{\tau_{\ast}}\rangle\geq\frac{1}{4}M$. Recalling that $\langle T_{\cal
R}\rangle\geq\langle T_{\tau_{\ast}}\rangle$ for all ${\cal R}$, we then
obtain Eq. (4). Note also, that if the probability distribution $P(T)$ has
multiple local maxima, then $\langle T_{{\cal
R}}\rangle\geq\frac{1}{4}M^{min}$, where $M^{min}$ is the leftmost mode.
Moreover, similarly to Eq. (3), inequality (4) holds even for potentially non-
stopping processes, with the obvious caveat that $M$ should now be considered
as the most frequent completion time of halting trials.

The twice median sets upper bound on the optimized mean completion time.
Having considered the lower bounds, we now turn to the opposite question. How
good is the best restart strategy? In other words, we wish to construct an
inequality of the form $\langle T_{\tau_{\ast}}\rangle\leq C{\cal T}$, where
the time scale ${\cal T}$ is determined by the properties of the original
stochastic process, and $C$ is the universal positive constant which depends
neither on specific form of $P(T)$ nor on the optimal restart period
$\tau_{\ast}$.

It is easy to understand that the upper bound limit on optimal performance
cannot be expressed via the harmonic mean $h$ or the mode $M$. Indeed, for the
half-normal distribution
$P(T)=\sqrt{\frac{2}{\pi\sigma^{2}}}e^{-\frac{T^{2}}{2\sigma^{2}}}$ one has
$\tau_{\ast}=+\infty$, so that $\langle T_{\tau_{\ast}}\rangle=\langle
T\rangle>0$, whereas $h=M=0$. Therefore, inequalities of the form $\langle
T_{\tau_{\ast}}\rangle\leq C_{1}h$ and $\langle T_{\tau_{\ast}}\rangle\leq
C_{2}M$, where $C_{1}$ and $C_{2}$ are positive constants, cannot be
universally valid.

The desired universal upper bound can be expressed in terms of the median
completion time $m$ of the original process obeying by definition the equation
$Pr[T\leq m]=1/2$. Indeed, taking into account that $\langle
T_{\tau_{\ast}}\rangle\leq\langle T_{\tau}\rangle$ for any $\tau\geq 0$
together with the inequality $\langle
T_{\tau}\rangle\leq\frac{\tau}{Pr[T\leq\tau]}$, which straightforwardly
follows from Eq. (1), we find $\langle
T_{\tau_{\ast}}\rangle\leq\frac{\tau}{Pr[T\leq\tau]}$. Substituting $m$ for
$\tau$ in the last inequality one obtains

$\langle T_{\tau_{\ast}}\rangle\leq 2m.$ (5)

Thus, no matter how heavy the tails of $P(T)$ are, in the presence of an
optimally tuned periodic restart, the average completion time does not exceed
twice the median of the unperturbed process. More generally, if the process
has non-zero probability of never halting, we arrive at the estimate $\langle
T_{\tau_{\ast}}\rangle\leq 2m_{s}/q$, where $m_{s}$ denotes the median
completion times of the halting trials, whereas $q$ is the probability that
process ends for a finite time SM .

Importantly, the bound dictated by Eq. (5) is sharp. Indeed, for
$P(T)=\frac{1}{2}\delta(T-t)+\frac{1}{2}\delta(T-3t)$ one obtains $m=t$ and
$\langle{T_{\tau_{\ast}}\rangle}=2t$, where $\tau_{\ast}=t$. Note also that
Eqs. (3) and (5) do not contradict each other since the relation $h\leq 2m$ is
always valid as shown in SM . Also, Eq. (4) is in accord with Eq. (5) since
$M\leq 2m$ for any continuous unimodal probability distribution (see SM ).

Given this result, it is natural to ask if the median value can be used to
construct the bottom bound of restart performance in the spirit of Eqs. (3)
and (4). The answer is no. A simple counterexample demonstrating that the
inequality $\langle T_{{\cal R}}\rangle\geq Cm$, where $C$ is universal non-
zero constant, cannot be valid is given by the Weibull distribution
$P(T)=\frac{k}{\lambda^{k}}T^{k-1}e^{-(\frac{T}{\lambda})^{k}}$ with $0<k<1$
for which $\langle T_{\tau_{\ast}}\rangle=0$, where $\tau_{\ast}\to 0$, and
$m>0$.

Figure 2: A diagram of restart efficiency for the random process with
completion time probability density
$P(T)=p\cdot\delta(T-t_{1})+(1-p)\cdot\delta(T-t_{2})$ in the plane of
dimensionless parameters $p$ and $a=t_{2}/t_{1}$. Black area corresponds to
the case when restart is not efficient. For the purple area of the diagram
restart is efficient and both criteria, $\sigma>\mu$ and $\mu>2m$, are
fulfilled. The region in blue corresponds to the scenario when restart
efficiency is captured only by the inequality $\sigma>\mu$, while the region
in red – to the scenario when only the condition $\mu>2m$ is satisfied.
Finally, neither of the two sufficient conditions is met for the orange area
of the diagram, but restart is useful nevertheless.

Beyond the mean performance. Inequality constraints given by Eqs. (3), (4) and
(5) can be generalized to higher order statistical moments of random
completion time. First of all, since $\sqrt[k]{\langle T_{{\cal
R}}^{k}\rangle}\geq\langle T_{{\cal R}}\rangle$ for any natural $k$ due to
Jensen’s inequality Gallager_2013 , we immediately find from Eq. (3) that
$\sqrt[k]{\langle T_{{\cal R}}^{k}\rangle}\geq\frac{1}{4}h$ for a generic
stochastic process under an arbitrary restart protocol. Likewise, Eq. (4)
trivially entails inequality $\sqrt[k]{\langle T_{{\cal
R}}^{k}\rangle}\geq\frac{1}{4}M$ which is valid in the case of unimodal
completion time distribution.

A similar extension of Eq.(5) is more tricky. It turns out that the
statistical moments of the optimal completion time $T_{\tau_{\ast}}$ satisfy
the inequality

$\sqrt[k]{\langle T_{\tau_{\ast}}^{k}\rangle}\leq 2\sqrt[k]{k!}m.$ (6)

To prove Eq. (6) let us assume that the process, which is being restarted
periodically in an optimal way, becomes subject to an additional restart
protocol ${\cal R}_{\Gamma}$ characterized by random restart-intervals
$\tau_{1},\tau_{2},\dots$ independently sampled from Gamma distribution
$\rho(\tau)=\frac{\beta^{k}}{\Gamma(k)}\tau^{k-1}e^{-\beta\tau}$ with shape
parameter $k$ and infinitesimally small rate parameter $\beta$. In SM  we show
that this produces a deferential correction $\langle T_{\tau_{\ast}+{\cal
R}_{\Gamma}}\rangle-\langle
T_{\tau_{\ast}}\rangle\approx\frac{1}{k!}\left(\langle
T_{\tau_{\ast}}\rangle\langle T^{k}_{\tau_{\ast}}\rangle-\frac{1}{k+1}\langle
T^{k+1}_{\tau_{\ast}}\rangle\right)\beta^{k}$ to the mean completion time
attained by the optimal periodic restart. Because of the dominance of a
periodic restart over other restart strategies, one can be sure that this
difference is positive, and therefore

$\frac{\langle T_{\tau_{\ast}}^{k}\rangle}{\langle
T_{\tau_{\ast}}\rangle^{k}}\leq k!,$ (7)

Together with Eq. (5) this yields Eq. (6).

Numerical examples. For the sake of illustration we explored several
probability distributions $P(T)$, whose response to restart has been
extensively discussed in the physical and computer science literature: first-
passage time densities for one-dimensional EM_2011 ; Evans_review_2020  and
two-dimensional Evans_2014 ; Evans_review_2020 ; Faisant_2021  diffusion
processes, first-passage time density for one-dimensional drift-diffusion
process Ray_2019a , first-passage time density for one-dimensional diffusion
in logarithmic potential Ray_2020 , log-normal distribution Schroeder_2001 ;
Reuveni_2014 ; Lorenz_2018 ; Lorenz_2021 ; Eliazar_JPA_2021 , hyper-Erlang
distribution Moorsel_2004 ; Moorsel_2006 ; Rotbart_2015 ; Pal_2019c , hyper-
exponential distribution Moorsel_2004 ; Moorsel_2006 ; Rotbart_2015 , and
Pareto distribution Wu_2006 ; Lorenz_2018 ; Lorenz_2021 . The numerical
parameters associated with the distributions are given in SM . Numerical data
for the average completion time at the optimally chosen frequency of periodic
restart are summarized in the diagrams presented in Fig. 1. We see that all
points fall into the region determined by Eqs. (3), (4) and (5) together with
the inequalities $h\leq 2m$ and $M\leq 2m$.

Importantly, theoretical analyses presented above does not answer the question
of whether the bounds determined by Eqs. (3) and (4) are sharp. Thus, one may
expect, that the constant $1/4$ entering the right-hand sides of these
equations can potentially be replaced by one larger. Numerical data presented
in Fig. 1 allow us to argue that the unknown best possible constants $C_{1}$
and $C_{2}$ in the inequality constraints $\langle T_{{\cal R}}\rangle\leq
C_{1}h$ and $\langle T_{{\cal R}}\rangle\leq C_{2}M$ representing the exact
lower bounds on $\langle T_{{\cal R}}\rangle$ lie in the ranges $1/4\leq
C_{1}<5/4$ and $1/4\leq C_{2}<5/3$.

Corollary 1: Novel criterion of restart efficiency. A notable implication of
the upper bound dictated by Eq. (5) is a previously unknown sufficient
condition of when restart is helpful in facilitating the process completion.
Namely, as follows from Eq. (5), inequality $\mu/m>2$, where $\mu=\langle
T\rangle$, guarantees that there exists finite restart period decreasing the
expected completion time. What is particularly interesting is that this simple
inequality makes it possible to capture the benefit of restarting in those
cases when analysis of the relative fluctuation cannot. In Fig. 2 we compare
the applicability of two criteria, $\mu/m>2$ and $\sigma/\mu>1$, using the mix
of two delta-functions as a model distribution. Clearly, there is a region of
parameters, where the relative fluctuation is less than unity, $\sigma/\mu<1$,
while $\mu/m>2$. More generally, exploiting the well-known probabilistic
inequality $|\mu-m|\leq\sigma$ Hotelling_1932 ; Ocinneide_1990 ; Mallows_1991
, it is easy to see that the condition $\mu/m>2$ implies that
$\sigma/\mu>1/2$. What is more, the numerical constant $1/2$ cannot be
replaced by a larger one: in SM  we construct an example of probability
density $P(T)$ with $\sigma/\mu\to 1/2$ and $\mu/m>2$.

At the same time it should be noted that the opposite scenario, i.e.
$\sigma/\mu>1$ and $\mu/m<2$ is also possible (see Fig. 2). These observations
suggest that, since both conditions, $\sigma/\mu>1$ and $\mu/m>2$, are
sufficient, but by no means necessary, in practice they should be used
together to compensate (at least partially) each other’s shortcomings.

Corollary 2: Generalized fluctuation relation for optimal restart. Let us also
note that Eq. (7), which we have derived for auxiliary purposes, is
interesting in itself as it represents a higher-order generalization of the
well-known inequality constraint $\langle T_{\tau_{\ast}}^{2}\rangle/\langle
T_{\tau_{\ast}}\rangle^{2}\leq 2$ first derived by Pal and Reuveni
Reuveni_PRL_2017 . Interestingly, for $k=3$, we find from Eq. (7) an estimate
$\langle T_{\tau_{\ast}}^{3}\rangle/\langle T_{\tau_{\ast}}\rangle^{3}\leq 6$
emphasizing the contrast between best periodic protocol and optimally tuned
Poisson restart for which one has opposite inequality $\langle
T_{r_{\ast}}^{3}\rangle/\langle T_{r_{\ast}}\rangle^{3}\geq 6$ provided
$0<r_{\ast}<+\infty$, where $r_{\ast}$ is the optimal restart rate SM .

Conclusion and outlook. Revealing explicit performance bounds is crucial in
many areas of science and engineering. Say, establishment of the Carnot cycle
efficiency Carnot_1824  played a fundamental role for the development of
combustion engines and thermal power plants as it sets a bound on the
efficiency of any thermodynamic heat engine. Similarly, Shannon’s limit of
information capacity Shannon_1959  has become a guiding principle in the
design of communication systems. Although optimization via restart is widely
used in the practice of computer programming and represents active field of
academic research in physics, the question of performance limits of this
control tool has not been addressed thus far. In this study, we expressed
these limits in terms of simple statistical metrics that can be easily
estimated based on finite samples of the process completion time.

Importantly, the presented analysis was grounded on the assumption of
instantaneous restart events. Although this scenario covers overwhelming
majority of the model problems considered in the literature, it should be kept
in mind that in real-life settings restart may be accompanied by some time
penalty Evans_2018b ; Ahmad_2019a ; Pal_2019a ; Bodrova_2020a ; Bodrova_2020b
; Pal_JPA_2022 ; Robin_2018a ; Reuveni_2014 ; Reuveni_PRL_2016 ;
Friedman_2020a . Say, in the context of single molecule enzyme kinetics, where
restart occurs naturally by virtue of intermediate dissociation, some time is
required to enzyme which unbinds from its substrate to find a new one in
surrounding solution Reuveni_2014 ; Reuveni_PRL_2016 ; Robin_2018a .
Similarly, restart of computer program typically involves a time overhead.
Also, models with noninstantaneous restarts provide more realistic pictures of
colloidal particle diffusion with resetting Friedman_2020a . How does
accounting for delays modifies the bounds constructed here? The
straightforward generalization of arguments leading to Eq. (5) brings us to
the following simple result (see SM ): $\langle T_{\tau_{\ast}}\rangle\leq
2m+2\langle T_{on}\rangle$, where $\langle T_{on}\rangle$ is the expectation
of generally distributed time penalty which collectively accounts for any
delays that may arise prior to completion attempt. A similar generalization of
the lower bounds given by Eqs. (3) and (4) is an important (and apparently
sophisticated) task for future research.

###### Acknowledgements.

The work was supported by the Russian Science Foundation, project no.
22-72-10052. Supplementary Material

##  I I. Derivation of Eq. (1) in the main text

Let us consider a more general situation than the one described in the main
text. Namely, we assume that process initiation and each restart event entail
time delays representing statistically independent realizations of some
generally distributed random variable $T_{on}$. Then, the random completion
time $T_{\tau}$ in the presence of regular restart with period $\tau$ obeys
the stochastic renewal equation Reuveni_PRL_2017

$\displaystyle
T_{\tau}=T_{on}+TI(T<\tau)+(\tau+T_{\tau}^{\prime})I(T\geq\tau),$ (8)

where $T_{\tau}^{\prime}$ is a statistically independent copy of $T_{\tau}$,
and $I(...)$ denotes the indicator random variable which is equal to unity
when the inequality in its argument is justified and is zero otherwise.
Performing averaging over the statistics of $T$ and $T_{on}$ we obtain

$\displaystyle\langle T_{\tau}\rangle=\langle T_{on}\rangle+\langle
TI(T<\tau)\rangle+\tau\langle I(T\geq\tau)\rangle+\langle
T_{\tau}^{\prime}I(T\geq\tau)\rangle.$ (9)

Since random variables $T$, $T_{\tau}^{\prime}$ and $T_{on}$ are statistically
independent we can rewritte

$\displaystyle\langle T_{\tau}\rangle=\langle T_{on}\rangle+\langle
TI(T<\tau)\rangle+\tau\langle I(T\geq\tau)\rangle+\langle
T_{\tau}^{\prime}\rangle\langle I(T\geq\tau)\rangle.$ (10)

Next, taking into account that $\langle T_{\tau}^{\prime}\rangle=\langle
T_{\tau}\rangle$ one obtains

$\langle T_{\tau}\rangle=\frac{\langle T_{on}\rangle+\langle
TI(T<\tau)\rangle+\tau\langle I(T\geq\tau)\rangle}{\langle I(T<\tau)\rangle}.$
(11)

If the original stochastic process halts with unit probability, then the
random variable $T$ is described by probability density $P(T)$ with standard
normalization $\int_{0}^{\infty}dTP(T)=1$ and we find $\langle
TI(T<\tau)\rangle=\int_{0}^{\tau}P(T)TdT$, $\langle
I(T\geq\tau)\rangle=\int_{\tau}^{\infty}P(T)dT$, and $1-\langle
I(T\geq\tau)\rangle=\int_{0}^{\tau}P(T)dT$. Substituting these expressions
into Eq. (11) gives

$\langle T_{\tau}\rangle=\frac{\langle
T_{on}\rangle+\int_{0}^{\tau}P(T)TdT+\tau\int_{\tau}^{\infty}P(T)dT}{\int_{0}^{\tau}P(T)dT}.$
(12)

At $T_{on}=0$ this result coincides with Eq. (1) in the main text.

##  II II. Simple proof of global dominance of strictly regular restart

Luby et al. Luby_1993  showed that strictly periodic restart strategy is
universally optimal for discrete completion time distributions. Pal and
Reuveni Reuveni_PRL_2017  proved dominance of strictly periodic restart over
any stochastic restart protocol with independent and identically distributed
inter-restarts intervals in a continuous setting. Finally, the global
dominance of strictly periodic restart in the space of all possible restart
protocols for continuous case follows from Lemma 3 in Lorenz’s paper
Lorenz_2021 . In order to make the presentation of our results complete and
intuitively clear, here we developed a more simple line of arguments in
support of the optimality of periodic restart. Noteworthy, our proof is not
only simpler, but also more general than the previous ones, since we take into
account a non-zero delay $T_{on}$ before starting/restarting.

Let $\tau_{\ast}$ be the best period of regular restart protocol for a given
stochastic process, i.e.

$\langle T_{\tau_{\ast}}\rangle\leq\langle T_{\tau}\rangle$ (13)

for any $\tau\geq 0$. Also, let ${\cal
R}_{\ast}=\\{\tau_{1}^{\ast},\tau_{2}^{\ast},...\\}$ be an optimal restart
protocol for the same process. By the definition of optimal protocol this
means that

$\langle T_{{\cal R}_{\ast}}\rangle\leq\langle T_{{\cal R}}\rangle$ (14)

for any ${\cal R}$. Below we show that $\langle T_{\tau_{\ast}}\rangle=\langle
T_{{\cal R}_{\ast}}\rangle$.

The random completion time in the presence of restart events scheduled
accordingly to the protocol ${\cal R}_{\ast}$ can be represented as

$T_{{\cal R}_{\ast}}=T_{on}+TI(T<\tau_{1}^{\ast})+(\tau_{1}^{\ast}+T_{{\cal
R}_{\ast}^{\prime}})I(T\geq\tau_{1}^{\ast})$ (15)

where ${\cal R}_{\ast}^{\prime}=\\{\tau_{2}^{\ast},\tau_{3}^{\ast},...\\}$.
Averaging over the statistics of original process yields

$\langle T_{{\cal R}_{\ast}}\rangle=\langle T_{on}\rangle+\langle
TI(T<\tau_{1}^{\ast})\rangle+\tau_{1}^{\ast}\langle
I(T\geq\tau_{1}^{\ast})\rangle+\langle T_{{\cal
R}_{\ast}^{\prime}}\rangle\langle I(T\geq\tau_{1}^{\ast})\rangle,$ (16)

where we exploited statistical independence of $T$ and $T_{{\cal
R}_{\ast}^{\prime}}$. Since ${\cal R}_{\ast}$ is optimal, then $\langle
T_{{\cal R}_{\ast}^{\prime}}\rangle\geq\langle T_{{\cal R}_{\ast}}\rangle$,
and, therefore,

$\langle T_{{\cal R}_{\ast}}\rangle\geq\langle T_{on}\rangle+\langle
TI(T<\tau_{1}^{\ast})\rangle+\tau_{1}^{\ast}\langle
I(T\geq\tau_{1}^{\ast})\rangle+\langle T_{{\cal R}_{\ast}}\rangle\langle
I(T\geq\tau_{1}^{\ast})\rangle,$ (17)

and

$\langle T_{{\cal R}_{\ast}}\rangle\geq\frac{\langle T_{on}\rangle+\langle
TI(T<\tau_{1}^{\ast})\rangle+\tau_{1}^{\ast}\langle
I(T\geq\tau_{1}^{\ast})\rangle}{\langle I(T<\tau_{1}^{\ast})\rangle}$ (18)

Comparing right-hand sides of Eq. (18) and Eq. (11), one obtains

$\langle T_{{\cal R}_{\ast}}\rangle\geq\langle T_{\tau_{1}^{\ast}}\rangle.$
(19)

From Eqs. (13), (14) and (19) we may conclude that $\langle T_{{\cal
R}_{\ast}}\rangle=\langle T_{\tau_{\ast}}\rangle$, and, therefore, $\langle
T_{\tau_{\ast}}\rangle\leq\langle T_{{\cal R}}\rangle$ for any ${\cal R}$.

##  III III. Derivation of Eq. (2) in main text

Luby et al. Luby_1993  stated Eq. (2) from the main text for discrete
probability distributions. More recently, Lorenz Lorenz_2021  rigorously
showed this property for continuous distributions. Here we briefly remind the
arguments presented in Lorenz_2021 . Note that in this part of analysis we
adopt $T_{on}=0$.

If $\langle
T_{\tau_{\ast}}\rangle\geq\frac{\tau_{\ast}}{2Pr[T\leq\tau_{\ast}]}$, then the
inequality $\langle
T_{\tau_{\ast}}\rangle\geq\frac{1}{4}\min_{\tau}\frac{\tau}{Pr[T\leq\tau]}$ is
evident.

Next, we assume that $\langle
T_{\tau_{\ast}}\rangle<\frac{\tau_{\ast}}{2Pr[T\leq\tau_{\ast}]}$. Let us
introduce a variable $\tilde{T}\equiv\min(T,\tau_{\ast})$. It follows from Eq.
(11) that $\langle
T_{\tau}\rangle=\frac{\langle\min(T,\tau)\rangle}{Pr[T\leq\tau_{\ast}]}$, and,
therefore, $\langle\tilde{T}\rangle=\langle T_{\tau_{\ast}}\rangle
Pr[T\leq\tau_{\ast}]$. Next, due to the assumption $\tau_{\ast}>2\langle
T_{\tau_{\ast}}\rangle Pr[T\leq\tau_{\ast}]$ and the Markov’s inequality
$Pr[\tilde{T}>2\langle\tilde{T}\rangle]\leq\frac{1}{2}$ we find $Pr[T>2\langle
T_{\tau_{\ast}}\rangle Pr[T\leq\tau_{\ast}]]=Pr[\tilde{T}>2\langle
T_{\tau_{\ast}}\rangle
Pr[T\leq\tau_{\ast}]]=Pr[\tilde{T}>2\langle\tilde{T}\rangle]\leq\frac{1}{2}$.
Therefore

$Pr[T\leq 2\langle T_{\tau_{\ast}}\rangle
Pr[T\leq\tau_{\ast}]]\geq\frac{1}{2}.$ (20)

Now, let us denote $t\equiv 2\langle T_{\tau_{\ast}}\rangle
Pr[T\leq\tau_{\ast}]$. It follows from the inequalities (20) and
$Pr[T\leq\tau]\leq 1$ that

$\displaystyle\min_{\tau}\frac{\tau}{Pr[T\leq\tau]}\leq\frac{t}{Pr[T\leq
t]}=\frac{2\langle T_{\tau_{\ast}}\rangle Pr[T\leq\tau_{\ast}]}{Pr[T\leq
2\langle T_{\tau_{\ast}}\rangle Pr[T\leq\tau_{\ast}]]}\leq 4\langle
T_{\tau_{\ast}}\rangle.$ (21)

This completes the proof.

##  IV IV. Checking consistency of Eqs. (3), (4) and (5) in main text

Equations (3) and (5) do not contradict each other since $h\leq 2m$ for any
probability density $P(T)$. Indeed, applying Markov’s inequality we find
$1/2=\text{Pr}[T\leq
m]=\text{Pr}[\omega\geq\frac{1}{m}]\leq\langle\omega\rangle m=T_{1/2}/h$,
where $\omega=1/T$.

Also, Eq. (4) does not contradict Eq. (5) since $M\leq 2m$ for any continuous
unimodal probability density $P(T)$. To prove this, assume the contrary, that
is, let $M>2m$ be true for some non-negative random variable $T$. By the
virtue of definition we have
$\int_{0}^{m}P(T)dT=\int_{m}^{+\infty}P(T)dT=1/2$. Further, it follows from
the definition of the mode that the function $P(T)$ is non-decreasing on the
interval $[0,M]$. Then, on the one hand
$\int_{m}^{M}P(T)dT>\int_{m}^{2m}P(T)dT\geq\int_{0}^{m}P(T)dT=1/2$, and on the
other $\int_{m}^{M}P(T)dT\leq\int_{m}^{+\infty}P(T)dT=1/2$. We got a
contradiction.

One may expect that this is not the first time the simple relations $h\leq 2m$
and $M\leq 2m$ have been proven, but we have not found an appropriate
reference.

##  V V. Derivation of Eq. (6) in main text

Assume that a stochastic process with finite mean completion time $\langle
T\rangle$ becomes subject to the stochastic restart protocol ${\cal
R}_{\Gamma}=\tau_{1},\tau_{2},\dots$, where random intervals between
instantaneous restarts are independently sampled from the Gamma distribution
$\rho(\tau)=\frac{\beta^{k}}{\Gamma(k)}\tau^{k-1}e^{-\beta\tau}$ with
differentially small rate parameter $\beta$. Let us investigate how this
modifies the average completion time.

In the presence of the stochastic restart, the random completion time
$T_{{\cal R}_{\Gamma}}$ obeys the following renewal equation

$\displaystyle T_{{\cal R}_{\Gamma}}=TI(T<\tau)+(\tau+T_{{\cal
R}_{\Gamma}}^{\prime})I(T\geq\tau),$ (22)

where $T_{{\cal R}_{\Gamma}}^{\prime}$ is a statistically independent replica
of $T_{{\cal R}_{\Gamma}}$. Let us average this relation over the statistics
of original process and of the inter-restart intervals. This gives

$\langle T_{{\cal R}_{\Gamma}}\rangle=\langle TI(T<\tau)\rangle+\langle\tau
I(T\geq\tau)\rangle+\langle T_{{\cal
R}_{\Gamma}}^{\prime}I(T\geq\tau)\rangle.$ (23)

Since $\langle
TI(T<\tau)\rangle=\int_{0}^{\infty}dTP(T)T\int_{T}^{\infty}d\tau\rho(\tau)$,
$\langle\tau
I(T\geq\tau)\rangle=\int_{0}^{\infty}dTP(T)\int_{0}^{T}d\tau\rho(\tau)\tau$,
$\langle T_{{\cal R}_{\Gamma}}^{\prime}I(T\geq\tau)\rangle=\langle T_{{\cal
R}_{\Gamma}}^{\prime}\rangle\langle I(T\geq\tau)\rangle$, $1-\langle
I(T\geq\tau)\rangle=\int_{0}^{\infty}dTP(T)\int_{T}^{\infty}d\tau\rho(\tau)$
and $\langle T_{{\cal R}_{\Gamma}}^{\prime}\rangle=\langle T_{{\cal
R}_{\Gamma}}\rangle$, we find the closed-form expression for the expected
completion time

$\langle T_{{\cal
R}_{\Gamma}}\rangle=\frac{\int_{0}^{\infty}dTP(T)T\int_{T}^{\infty}d\tau\rho(\tau)+\int_{0}^{\infty}dTP(T)\int_{0}^{T}d\tau\rho(\tau)\tau}{\int_{0}^{\infty}dTP(T)\int_{T}^{\infty}d\tau\rho(\tau)}.$
(24)

In leading order in the small parameter $\beta$ we obtain

$\displaystyle\int_{0}^{\infty}dTP(T)T\int_{T}^{\infty}d\tau\rho(\tau)=\langle
T\rangle-\int_{0}^{\infty}dTP(T)T\int_{0}^{T}d\tau\rho(\tau)\approx$ (25)
$\displaystyle\approx\langle
T\rangle-\frac{\beta^{k}}{(k-1)!}\int_{0}^{\infty}dTP(T)T\int_{0}^{T}d\tau\tau^{k-1}=\langle
T\rangle-\frac{\beta^{k}}{k!}\langle T^{k+1}\rangle,$ (26)
$\displaystyle\int_{0}^{\infty}dTP(T)\int_{0}^{T}d\tau\rho(\tau)\tau\approx\frac{\beta^{k}}{(k-1)!}\int_{0}^{\infty}dTP(T)\int_{0}^{T}d\tau\tau^{k}=\frac{k\beta^{k}}{(k+1)!}\langle
T^{k+1}\rangle,$ (27)
$\displaystyle\int_{0}^{\infty}dTP(T)\int_{T}^{\infty}d\tau\rho(\tau)=1-\int_{0}^{\infty}dTP(T)\int_{0}^{T}d\tau\rho(\tau)\approx$
(28) $\displaystyle\approx
1-\frac{\beta^{k}}{(k-1)!}\int_{0}^{\infty}dTP(T)\int_{0}^{T}d\tau\tau^{k-1}=1-\frac{\beta^{k}}{k!}\langle
T^{k}\rangle,$ (29)

and, therefore,

$\langle T_{{\cal R}_{\Gamma}}\rangle\approx\langle
T\rangle+\frac{1}{k!}\left(\langle T\rangle\langle
T^{k}\rangle-\frac{1}{k+1}\langle T^{k+1}\rangle\right)\beta^{k}.$ (30)

Now suppose that the stochastic restart protocol is applied to a process that
is already subject to optimal periodic restart. Equation (30) tells us that
the resulting mean completion time is given by $\langle T_{\tau_{\ast}+{\cal
R}_{\Gamma}}\rangle=\langle T_{\tau_{\ast}}\rangle+\frac{1}{k!}\left(\langle
T_{\tau_{\ast}}\rangle\langle T^{k}_{\tau_{\ast}}\rangle-\frac{1}{k+1}\langle
T^{k+1}_{\tau_{\ast}}\rangle\right)\beta^{k}$. Because of the dominance of a
periodic restart over other restart strategies, one can be sure that $\langle
T_{\tau_{\ast}+{\cal R}_{\Gamma}}\rangle\geq\langle T_{t_{\ast}}\rangle$, and
therefore $\langle T^{k+1}_{\tau_{\ast}}\rangle\leq(k+1)\langle
T_{\tau_{\ast}}\rangle\langle T^{k}_{\tau_{\ast}}\rangle$ for any natural $k$.
This immediately implies Eq. (6).

##  VI VI. Example of distribution with $\sigma/\mu=1/2$ and $\mu/m>2$

Consider a distribution of the form

$P(T)=\left(\frac{1}{2}+\varepsilon\right)\cdot\delta(T-t_{1})+\left(\frac{1}{2}-\varepsilon\right)\cdot\delta(T-(3+6\varepsilon)\cdot
t_{1}),$ (31)

where $0<\varepsilon\ll 1$ and $t_{1}>0$. Its median completion time $m$ is
equal to $t_{1}$, and its mean is given by

$\mu\equiv\langle T\rangle=\left(\frac{1}{2}+\varepsilon\right)\cdot
t_{1}+\left(\frac{1}{2}-\varepsilon\right)\cdot
t_{1}\cdot(3+6\varepsilon)=t_{1}\cdot\left(2+\varepsilon-6\varepsilon^{2}\right)>2m,$
(32)

where the last inequality is fulfilled due to positivity and infinitesimality
of $\varepsilon$. Ratio of standard deviation to the mean is thus given by

$\frac{\sigma}{\mu}=\frac{(1+3\varepsilon)\cdot\sqrt{1-4\varepsilon^{2}}}{2+\varepsilon-6\varepsilon^{2}}=\frac{1+3\varepsilon}{2}\cdot\left(1-2\varepsilon^{2}+O(\varepsilon^{4})\right)\cdot\left(1-\frac{\varepsilon}{2}+\frac{13}{4}\varepsilon^{2}+O(\varepsilon^{3})\right)=\frac{1}{2}+\frac{5\varepsilon}{4}+O(\varepsilon^{2})\rightarrow\frac{1}{2}.$
(33)

##  VII VII. Details of distributions used in numerical simulations

Probability distributions, considered in Fig. 1 in main text, and their
corresponding numerical parameters are as follows. In all investigated cases
restart is beneficial, i.e. there exists $\tau_{\ast}$ such that $\langle
T_{\tau_{\ast}}\rangle<\langle T\rangle$.

1)First-passage-time distribution for 1d-diffusion process (Lévi-Smirnov
distribution) EM_2011 :

$P(T)=\frac{L}{2\sqrt{\pi D}T^{3/2}}\exp\left(-\frac{L^{2}}{4DT}\right),$ (34)

calculated for $L^{2}/D=1$, where $D$ is the diffusion coefficient, and $L$ is
the initial distance to the target.

2) First-passage-time distribution for 2d-diffusion process Faisant_2021 :

$P(T)=\frac{2}{\pi}\int_{0}^{\infty}\frac{dx}{R^{2}}e^{-DTx^{2}/R^{2}}\cdot
x\cdot\frac{Y_{0}(\frac{x\cdot r}{R})\cdot J_{0}(x)-J_{0}(\frac{x\cdot
r}{R})\cdot Y_{0}(x)}{J_{0}^{2}(x)+Y_{0}^{2}(x)},$ (35)

where $J_{0}(x)$ and $Y_{0}(x)$ are the Bessel functions of the first and the
second kind respectively. Calculated for $D=1$ and $R/r=0.4$, where $D$ is the
diffusion coefficient, $r$ \- is the radius of absorbing disk and $R$ \-
distance between starting position of the particle and centre of the disk.

3) First-passage time distribution for 1d-diffusion in logarithmic potential
Ray_2020 :

$P(T)=\frac{T^{-(v+1)}}{\Gamma(v)}\left(\frac{x_{0}^{2}}{4D}\right)^{v}\exp\left(-\frac{x_{0}^{2}}{4DT}\right),$
(36)

calculated for $\nu=3$, $x_{0}=1$, $D=1$.

4) First-passage time distribution for drift-diffusion process to an absorbing
boundary Ray_2019a :

$P(T)=\frac{L}{\sqrt{4\pi DT^{3}}}\exp\left[-\frac{(L-VT)^{2}}{4DT}\right]$
(37)

calculated for $L=2$, $V=0.5$, $D=1$.

5) Mix of two exponential distributions (double exponential distribution):

$P(T)=pk_{1}e^{-k_{1}T}+(1-p)k_{2}e^{-k_{2}T},$ (38)

calculated for ($k_{1}=0.5$, $k_{2}=2$, $p=1/3$), and ($k_{1}=1$,
$k_{2}=10.25$, $p=0.1025$).

6) Mix of three exponential distributions (triple exponential distribution):

$P(T)=p_{1}k_{1}e^{-k_{1}T}+p_{2}k_{2}e^{-k_{2}T}+(1-p_{1}-p_{2})k_{3}e^{-k3T},$
(39)

calculated for $k_{1}=1$, $p_{1}=0.5$, $k_{2}=6$, $p_{2}=0.2$, $k_{3}=15$.

7) Mix of two Erlang distributions (double Erlang distribution):

$P(T)=pk_{1}^{2}Te^{-k_{1}T}+(1-p)k_{2}^{2}Te^{-k_{2}T},$ (40)

calculated for ($k_{1}=22.88$, $k_{2}=1.42$, $p=0.31$), and ($k_{1}=1.42$,
$k_{2}=22.88$, $p=0.31$),

8) Log-Normal distribution:

$P(T)=\frac{1}{T\sigma\sqrt{2\pi}}\exp\left(-\frac{(\ln(T)-\mu)^{2}}{2\sigma^{2}}\right),$
(41)

calculated for ($\mu=0$, $\sigma=1$) and ($\mu=0$, $\sigma=0.75$).

9) Pareto distribution:

$P(T)=\left\\{\begin{array}[]{ll}\alpha k^{\alpha}T^{-1-\alpha}&T\geq k,\\\
0&T<k,\end{array}\right.$ (42)

calculated for ($k=1$, $\alpha=1$) and ($k=1$, $\alpha=3$).

10) Sum of two delta functions:

$P(T)=\frac{1}{2}\delta(T-t)+\frac{1}{2}\delta(T-3t).$ (43)

##  VIII VIII. Generalization of Eq. (5) to the case of non-instantaneous
restarts and non-zero probability of non-stopping

Here we generalize Eq. (5) from the main text assuming that (a) the original
stochastic process ends for finite time with probability $0<q\leq 1$, and (b)
any start/restart event is accompanied by a random time penalty $T_{on}$.

Obviously, Eq. (11) can be rewritten as

$\langle T_{\tau}\rangle=\frac{\langle
T_{on}\rangle+min(T,\tau)}{Pr[T<\tau]},$ (44)

where $min(T,\tau)$ is the minimum of $T$ and $\tau$ and we used the identity
$\langle I(T<\tau)\rangle=Pr[T<\tau]$. Next, since $\langle
T_{\tau_{\ast}}\rangle\leq\langle T_{\tau}\rangle$ and $min(T,\tau)\leq\tau$,
one immediately obtains an estimate

$\langle T_{\tau_{\ast}}\rangle\leq\frac{\tau+\langle
T_{on}\rangle}{Pr[T<\tau]}.$ (45)

Let us denote as $m_{s}$ the median completion time of the halting
realizations. Substituting $m_{s}$ for $\tau$ in the last inequality yields

$\langle T_{\tau_{\ast}}\rangle\leq\frac{2(m_{s}+\langle T_{on}\rangle)}{q},$
(46)

where we took into account that $Pr[T<m_{s}]=\frac{1}{2}\times q$.

At $q=1$ and $T_{on}=0$, Eq. (46) reduces to Eq. (5) in the main text. The
special cases $q<1$, $T_{on}=0$ and $q=1$, $T_{on}>0$ enter the main text as
the inline formulas.

##  IX IX. Derivation of inequality $\langle T_{r_{\ast}}^{3}\rangle\geq
6\langle T_{r_{\ast}}\rangle^{3}$ for optimally tuned Poisson restart

The mean completion time of the process subject to Poisson restart at rate $r$
is equal to (see Reuveni_PRL_2016 )

$\langle T_{r}\rangle=\frac{1-\tilde{P}(r)}{r\tilde{P}(r)},$ (47)

where $\tilde{P}(r)=\int_{0}^{\infty}dTP(T)e^{-rT}$ – is the Laplace transform
of the probability density $P(T)$ .

Let $r_{\ast}$ be the optimal restart rate bringing $\langle T_{r}\rangle$ to
a minimum so that

$\displaystyle\frac{d\langle T_{r_{\ast}}\rangle}{dr}=0,$ (48)

and

$\displaystyle\frac{d^{2}\langle T_{r_{\ast}}\rangle}{dr^{2}}\geq 0.$ (49)

Let us assume that the process, which is being restarted at rate $r_{\ast}$,
becomes subject to additional stochastic (Poisson) restart events with
infinitesimally small rate $\delta r$. Due to the additive property of Poisson
events the resulting performance is given by

$\langle T_{r_{\ast}+\delta r}\rangle=\langle T_{r_{\ast}}\rangle+\delta
r\frac{d\langle T_{r_{\ast}}\rangle}{dr}+\delta r^{2}\frac{d^{2}\langle
T_{r_{\ast}}\rangle}{dr^{2}}+o(\delta r^{2}).$ (50)

At the same time, using Eq. (47) we obtain

$\displaystyle\langle T_{r_{\ast}+\delta
r}\rangle=\frac{1-\tilde{P}_{r_{\ast}}(\delta r)}{\delta
r\tilde{P}_{r_{\ast}}(\delta r)}=\frac{1-\int_{0}^{\infty}e^{-\delta
rT_{r_{\ast}}}P_{r_{\ast}}(T_{r_{\ast}})dT_{r_{\ast}}}{\delta
r\int_{0}^{\infty}e^{-\delta
rT_{r_{\ast}}}P_{r_{\ast}}(T_{r_{\ast}})dT_{r_{\ast}}}=$ (51)
$\displaystyle=\langle T_{r_{\ast}}\rangle+\delta r\left(\langle
T_{r_{\ast}}\rangle^{2}-\frac{1}{2}\langle
T_{r_{\ast}}^{2}\rangle\right)+\delta r^{2}\left(\frac{1}{6}\langle
T_{r_{\ast}}^{3}\rangle-\langle T_{r_{\ast}}^{2}\rangle\langle
T_{r_{\ast}}\rangle+\langle T_{r_{\ast}}\rangle^{3}\right)+o(\delta r^{2}),$
(52)

where $P_{r_{\ast}}(T_{r_{\ast}})$ denotes the probability density of the
random completion time under optimal Poisson restart. and
$\tilde{P}_{r_{\ast}}(r)=\int_{0}^{\infty}e^{-rT_{r_{\ast}}}P_{r_{\ast}}(T_{r_{\ast}})dT_{r_{\ast}}$
is its Laplace transform.

Comparing Eqs. (50) and (52) one obtains $\frac{d\langle
T_{r_{\ast}}\rangle}{dr}=\langle T_{r_{\ast}}\rangle^{2}-\frac{1}{2}\langle
T_{r_{\ast}}^{2}\rangle$ and $\frac{d^{2}\langle
T_{r_{\ast}}\rangle}{dr^{2}}=\frac{1}{6}\langle
T_{r_{\ast}}^{3}\rangle-\langle T_{r_{\ast}}^{2}\rangle\langle
T_{r_{\ast}}\rangle+\langle T_{r_{\ast}}\rangle^{3}$. Substituting these
relations into Eqs. (48) and (49) yields

$\langle T_{r_{\ast}}^{3}\rangle\geq 6\langle T_{r_{\ast}}\rangle^{3}.$ (53)

## References

  * (1) H. Alt, L. Guibas, K. Mehlhorn, R. Karp, and A. Wigderson, A method for obtaining randomized algorithms with small tail probabilities. Technical Report TR- 91-057, International Computer Science Institute, Berkeley, September 1991.
  * (2) M. Luby, A. Sinclair, and D. Zuckerman, Optimal speedup of Las Vegas algorithms, Inf. Proc. Lett. 47(4), 173-180 (1993).
  * (3) Gomes, C. P., Selman, B., and Crato, N. (1997, October). Heavy-tailed distributions in combinatorial search. In International Conference on Principles and Practice of Constraint Programming (pp. 121-135). Springer, Berlin, Heidelberg.
  * (4) Montanari, A., and Zecchina, R. (2002). Optimizing searches via rare events. Physical review letters, 88(17), 178701.
  * (5) Van Moorsel, A. P., and Wolter, K. (2004, September). Analysis and algorithms for restart. In First International Conference on the Quantitative Evaluation of Systems, 2004. QEST 2004. Proceedings. (pp. 195-204). IEEE.
  * (6) H. Wu, (2006). Randomization and restart strategies (Master’s thesis, University of Waterloo).
  * (7) Wu, H., and Beek, P. V. (2007, September). On universal restart strategies for backtracking search. In International Conference on Principles and Practice of Constraint Programming (pp. 681-695). Springer, Berlin, Heidelberg.
  * (8) Huang, J. (2007, January). The Effect of Restarts on the Efficiency of Clause Learning. In IJCAI (Vol. 7, pp. 2318-2323).
  * (9) Streeter, M., Golovin, D., and Smith, S. F. (2007, January). Restart schedules for ensembles of problem instances. In AAAI (pp. 1204-1210).
  * (10) Gagliolo, M., and Schmidhuber, J. (2007, January). Learning Restart Strategies. In IJCAI (pp. 792-797).
  * (11) Wolter, K. (2008). Stochastic models for restart, rejuvenation and checkpointing. Technical report, Habilitation Thesis, Humboldt-University, Institut Informatik, Berlin.
  * (12) Wedge, N. A., and Branicky, M. S. (2008, July). On heavy-tailed runtimes and restarts in rapidly-exploring random trees. In Twenty-third AAAI conference on artificial intelligence (pp. 127-133).
  * (13) Biere, A., Heule, M., van Maaren, H.: Handbook of Satisfiability. IOS Press (2009)
  * (14) Roulet, V., and d’Aspremont, A. (2017). Sharpness, restart and acceleration. Advances in Neural Information Processing Systems, 30.
  * (15) Lorenz, J. H. (2018, January). Runtime distributions and criteria for restarts. In International Conference on Current Trends in Theory and Practice of Informatics (pp. 493-507). Edizioni della Normale, Cham.
  * (16) Lorenz, J. H., and Nickerl, J. (2019). The Potential of Restarts for ProbSAT. arXiv preprint arXiv:1904.11757.
  * (17) Lorenz, J. H. (2021). Restart Strategies in a Continuous Setting. Theory of Computing Systems, 1-22.
  * (18) Schulte, C., Tack, G., and Lagerkvist, M. Z. (2010). Modeling and programming with gecode. Schulte, Christian and Tack, Guido and Lagerkvist, Mikael, 1.
  * (19) Cire, A., Kadioglu, S., and Sellmann, M. (2014, June). Parallel restarted search. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 28, No. 1).
  * (20) Amadini, R., Gabbrielli, M., and Mauro, J. (2018). SUNNY-CP and the MiniZinc challenge. Theory and Practice of Logic Programming, 18(1), 81-96.
  * (21) Wallace, M. (2020). Search Control in MiniZinc. In Building Decision Support Systems (pp. 165-175). Springer, Cham.
  * (22) Schroeder, M., and Buro, L. (2001). Does the restart method work? Preliminary Results on Efficiency Improvements for Interactions of Web-agents. In Proceedings of the Workshop on Infrastructure for Agents, MAS, and Scalable MAS at the Conference Autonomous Agents.
  * (23) Van Moorsel, A. P., and Wolter, K. (2006). Analysis of restart mechanisms in software systems. IEEE Transactions on Software Engineering, 32(8), 547-558.
  * (24) M.R. Evans and S.N. Majumdar, Diffusion with stochastic resetting, Phys. Rev. Lett. 106, 160601 (2011).
  * (25) M. R. Evans and S. N. Majumdar, Diffusion with optimal resetting, J. Phys. A 44(43), 435001 (2011).
  * (26) J. Whitehouse, M. R. Evans, and S. N. Majumdar, Effect of partial absorption on diffusion with resetting, Phys. Rev. E 87(2), 022118 (2013).
  * (27) M. R. Evans and S. N. Majumdar, Diffusion with resetting in arbitrary spatial dimension, J. Phys. A 47(28), 285001 (2014).
  * (28) Ł. Kuśmierz, S. N. Majumdar, S. Sabhapandit, and G. Schehr, First order transition for the optimal search time of Lévy flights with resetting, Phys. Rev. Lett. 113(22), 220602 (2014).
  * (29) Ł. Kuśmierz and E. Gudowska-Nowak, Optimal first-arrival times in Lévy flights with resetting, Phys. Rev. E 92(5), 052127 (2015).
  * (30) A. Pal, A. Kundu, and M.R. Evans, Diffusion under time-dependent resetting, J. Phys. A 49(22), 225001 (2016).
  * (31) S. Eule, and J. J. Metzger, Non-equilibrium steady states of stochastic processes with intermittent resetting, New Journal of Physics 18(3), 033006 (2016).
  * (32) A. Nagar and S. Gupta, Diffusion with stochastic resetting at power-law times, Phys. Rev. E 93(6), 060102 (2016).
  * (33) Evans, M. R., and Majumdar, S. N. (2018). Run and tumble particle under resetting: a renewal approach. Journal of Physics A: Mathematical and Theoretical, 51(47), 475003.
  * (34) Chechkin, A., and Sokolov, I. (2018). Random search with resetting: a unified renewal approach. Physical review letters, 121(5), 050601.
  * (35) Ł. Kuśmierz, and Toyoizumi, T. (2019). Robust random search with scale-free stochastic resetting. Physical Review E, 100(3), 032110.
  * (36) Ray, S., Mondal, D., and Reuveni, S. (2019). Péclet number governs transition to acceleratory restart in drift-diffusion. Journal of Physics A: Mathematical and Theoretical, 52(25), 255002.
  * (37) Ray, S., and Reuveni, S. (2020). Diffusion with resetting in a logarithmic potential. The Journal of chemical physics, 152(23), 234110.
  * (38) Singh, P. (2020). Random acceleration process under stochastic resetting. Journal of Physics A: Mathematical and Theoretical, 53(40), 405005.
  * (39) Ahmad, S., and Das, D. (2020). Role of dimensions in first passage of a diffusing particle under stochastic resetting and attractive bias. Physical Review E, 102(3), 032145.
  * (40) Radice, M. (2021). One-dimensional telegraphic process with noninstantaneous stochastic resetting. Physical Review E, 104(4), 044126.
  * (41) Faisant, F., Besga, B., Petrosyan, A., Ciliberto, S., and Majumdar, S. N. (2021). Optimal mean first-passage time of a Brownian searcher with resetting in one and two dimensions: experiments, theory and numerical tests. Journal of Statistical Mechanics: Theory and Experiment, 2021(11), 113203.
  * (42) Abdoli, I., and Sharma, A. (2021). Stochastic resetting of active Brownian particles with Lorentz force. Soft Matter, 17(5), 1307-1316.
  * (43) Evans, M. R., Majumdar, S. N., and Schehr, G. (2020). Stochastic resetting and applications. Journal of Physics A: Mathematical and Theoretical, 53(19), 193001.
  * (44) Santra, I., Basu, U., and Sabhapandit, S. (2020). Run-and-tumble particles in two dimensions under stochastic resetting conditions. Journal of Statistical Mechanics: Theory and Experiment, 2020(11), 113206.
  * (45) Calvert, G. R., and Evans, M. R. (2021). Searching for clusters of targets under stochastic resetting. The European Physical Journal B, 94(11), 1-9.
  * (46) Mercado-Vásquez, G., and Boyer, D. (2021). Search of stochastically gated targets with diffusive particles under resetting. Journal of Physics A: Mathematical and Theoretical, 54(44), 444002.
  * (47) Bonomo, O. L., and Pal, A. (2021). First passage under restart for discrete space and time: Application to one-dimensional confined lattice random walks. Physical Review E, 103(5), 052129.
  * (48) Tucci, G., Gambassi, A., Majumdar, S. N., and Schehr, G. (2022). First-passage time of run-and-tumble particles with non-instantaneous resetting. arXiv preprint arXiv:2203.16066.
  * (49) Chen, H., and Huang, F. (2022). First passage of a diffusing particle under stochastic resetting in bounded domains with spherical symmetry. Physical Review E, 105(3), 034109.
  * (50) Ahmad, S., Rijal, K., and Das, D. (2022). First passage in the presence of stochastic resetting and a potential barrier. Physical Review E, 105(4), 044134.
  * (51) Reuveni, S., Urbakh, M., and Klafter, J. (2014). Role of substrate unbinding in Michaelis-Menten enzymatic reactions. Proceedings of the National Academy of Sciences, 111(12), 4391-4396.
  * (52) T. Rotbart, S. Reuveni, and M. Urbakh, Michaelis-Menten reaction scheme as a unified approach towards the optimal restart problem, Phys. Rev. E  92(6), 060101(R) (2015).
  * (53) S. Reuveni, Optimal stochastic restart renders fluctuations in first passage times universal, Phys. Rev. Let. 116(17), 170601 (2016).
  * (54) A. Pal, and S. Reuveni, First Passage under Restart, Phys. Rev. Lett. 118(3), 030603 (2017).
  * (55) Eliazar, I., and Reuveni, S. (2021). Mean-performance of sharp restart: II. Inequality roadmap. Journal of Physics A: Mathematical and Theoretical, 54(35), 355001.
  * (56) Pal, A., Kostinski, S., and Reuveni, S. (2022). The inspection paradox in stochastic resetting. Journal of Physics A: Mathematical and Theoretical, 55(2), 021001.
  * (57) Belan, S. (2018). Restart could optimize the probability of success in a Bernoulli trial. Physical review letters, 120(8), 080601.
  * (58) Belan, S. (2020). Median and mode in first passage under restart. Physical Review Research, 2(1), 013243.
  * (59) Eliazar, I., and Reuveni, S. (2022). Entropy of Sharp Restart. arXiv preprint arXiv:2207.02085.
  * (60) Eliazar, I., and Reuveni, S. (2022). Diversity of Sharp Restart. arXiv preprint arXiv:2207.09200.
  * (61) See Supplemental Material, which includes derivation of Eq. (1), proof of global dominance of strictly regular restart, derivation of Eqs. (2) and (7), details of distributions used to generate Fig. 1, checking the consistency of Eqs. (4-5), generalization of Eq. (5) accounting non-instantaneous restarts and non-zero probability of non-halting, example of probability density $P(T)$ with $\sigma/\mu=1/2$ and $\mu/m>2$, and analysis of completion time fluctuations under optimally tuned Poisson restart.
  * (62) Gallager, R. G. (2013). Stochastic processes: theory for applications. Cambridge University Press.
  * (63) Noteworthy, once the probability $q=Pr[T<+\infty]$ of halting for a given stochastic process is known, one can improve the estimate given by Eqs. (3) as follows: $\langle T_{\cal R}\rangle\geq\frac{1}{4}h/q$.
  * (64) Pal, A., and Prasad, V. V. (2019). Landau-like expansion for phase transitions in stochastic resetting. Physical Review Research, 1(3), 032001.
  * (65) Hotelling, H., and Solomons, L. M. (1932). The limits of a measure of skewness. The Annals of Mathematical Statistics, 3(2), 141-142.
  * (66) O’cinneide, C. A. (1990). The mean is within one standard deviation of any median. The American Statistician, 44(4), 292-293.
  * (67) Mallows, C. (1991). Another comment on O’Cinneide. The American Statistician, 45(3), 257.
  * (68) Carnot, S. (1824). Reflections on the motive power of fire, and on machines fitted to develop that power. Paris: Bachelier, 108.
  * (69) Shannon, C. E. (1959). Coding theorems for a discrete source with a fidelity criterion. IRE Nat. Conv. Rec, 4(142-163), 1.
  * (70) Evans, M. R., and Majumdar, S. N. (2018). Effects of refractory period on stochastic resetting. Journal of Physics A: Mathematical and Theoretical, 52(1), 01LT01.
  * (71) Robin, T., Reuveni, S., and Urbakh, M. (2018). Single-molecule theory of enzymatic inhibition. Nature communications, 9(1), 1-9.
  * (72) Ahmad, S., Nayak, I., Bansal, A., Nandi, A., and Das, D. (2019). First passage of a particle in a potential under stochastic resetting: A vanishing transition of optimal resetting rate. Physical Review E, 99(2), 022130.
  * (73) Pal, A., Kuśmierz Ł., and Reuveni, S. (2019). Time-dependent density of diffusion with stochastic resetting is invariant to return speed. Physical Review E, 100(4), 040101.
  * (74) Bodrova, A. S., and Sokolov, I. M. (2020). Resetting processes with noninstantaneous return. Physical Review E, 101(5), 052130.
  * (75) Bodrova, A. S., and Sokolov, I. M. (2020). Brownian motion under noninstantaneous resetting in higher dimensions. Physical Review E, 102(3), 032129.
  * (76) Tal-Friedman, O., Pal, A., Sekhon, A., Reuveni, S., and Roichman, Y. (2020). Experimental realization of diffusion with stochastic resetting. The journal of physical chemistry letters, 11(17), 7350-7355.