English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $\mathcal{A}$ be a Las Vegas algorithm, i.e. an algorithm whose runningtime $T$ is a random variable drawn according to a certain probabilitydistribution $p$. In 1993, Luby, Sinclair and Zuckerman [LSZ93] proved that asimple 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 withfull prior knowledge of the probability distribution $p$, and $Q_p(q)$ is the$q$-quantile of $p$. Moreover, the authors showed that the logarithmic termcould not be removed for universal restart strategies and was, in a certainsense, optimal. In this work, we show that, quite surprisingly, the logarithmicterm can be replaced by a smaller quantity, thus reducing the expected runningtime in practical settings of interest. More precisely, we propose a novelrestart 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^2b\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 algorithmicreverse Jensen's inequalities. Finally, we show that the behavior of$\frac{t\phi''(t)}{\phi'(t)}$ at infinity controls the existence of reverseJensen's inequalities by providing a necessary and a sufficient condition forthese inequalities to hold.

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