  Let $\mathcal{A}$ be a Las Vegas algorithm, i.e. an algorithm whose running
time $T$ is a random variable drawn according to a certain probability
distribution $p$. In 1993, Luby, Sinclair and Zuckerman [LSZ93] proved that a
simple universal restart strategy can, for any probability distribution $p$,
provide an algorithm executing $\mathcal{A}$ and whose expected running time is
$O(\ell^\star_p\log\ell^\star_p)$, where $\ell^\star_p=\Theta\left(\inf_{q\in
(0,1]}Q_p(q)/q\right)$ is the minimum expected running time achievable with
full prior knowledge of the probability distribution $p$, and $Q_p(q)$ is the
$q$-quantile of $p$. Moreover, the authors showed that the logarithmic term
could not be removed for universal restart strategies and was, in a certain
sense, optimal. In this work, we show that, quite surprisingly, the logarithmic
term can be replaced by a smaller quantity, thus reducing the expected running
time in practical settings of interest. More precisely, we propose a novel
restart strategy that executes $\mathcal{A}$ and whose expected running time is
$O\big(\inf_{q\in (0,1]}\frac{Q_p(q)}{q}\,\psi\big(\log Q_p(q),\,\log
(1/q)\big)\big)$ where $\psi(a,b)=1+\min\left\{a+b,a\log^2 a,\,b\log^2
b\right\}$. This quantity is, up to a multiplicative factor, better than: 1)
the universal restart strategy of [LSZ93], 2) any $q$-quantile of $p$ for
$q\in(0,1]$, 3) the original algorithm, and 4) any quantity of the form
$\phi^{-1}(\mathbb{E}[\phi(T)])$ for a large class of concave functions $\phi$.
The latter extends the recent restart strategy of [Zam22] achieving
$O\left(e^{\mathbb{E}[\ln(T)]}\right)$, and can be thought of as algorithmic
reverse Jensen's inequalities. Finally, we show that the behavior of
$\frac{t\phi''(t)}{\phi'(t)}$ at infinity controls the existence of reverse
Jensen's inequalities by providing a necessary and a sufficient condition for
these inequalities to hold.
