Black-box Acceleration of Las Vegas Algorithms and Algorithmic Reverse Jensen's Inequalities

Abstract

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 }_p^{\star }\log {\ell }_p^{\star })$, where ${\ell }_p^{\star }=\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\left({\inf }_{q\in (0,1]}\frac{Q_p(q)}{q}\psi \right(\log Q_p(q),\log (1/q)\left)\right)$ 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 ${\varphi }^{-1}(\mathbb{E}[\varphi (T)])$ for a large class of concave functions $\varphi$. 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{\varphi }^{\prime \prime }(t)}{{\varphi }^{\prime }(t)}$ at infinity controls the existence of reverse Jensen's inequalities by providing a necessary and a sufficient condition for these inequalities to hold.

arXiv comment13 pages, 0 figures