The wrong direction of Jensen's inequality is algorithmically right

11/15/2022

∙

by   Or Zamir, et al.

∙

0

∙

share

Let 𝒜 be an algorithm with expected running time e^X, conditioned on the value of some random variable X. We construct an algorithm 𝒜' with expected running time O(e^E[X]), that fully executes 𝒜. In particular, an algorithm whose running time is a random variable T can be converted to one with expected running time O(e^E[ln T]), which is never worse than O(E[T]). No information about the distribution of X is required for the construction of 𝒜'.