Adaptive Weighted Averaging

We study the problem of selecting the largest among n unknown values x1,dots,xn given only a single unbiased estimate yi for each xi. 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.