Adaptive Weighted Averaging

Abstract

We study the problem of selecting the largest among n unknown values x_1,…,x_n given only a single unbiased estimate y_i for each x_i. We design strategies that are simultaneously admissible (not uniformly dominated by any other strategy) and also never worse than a given baseline such as uniform random selection. We provide an application to stochastic optimization, where we obtain online-to-batch conversion bounds with a desirable “no-compromise” guarantee: they are never worse than standard random iterate selection, and yet can be significantly better in benign settings.