Adaptive Weighted Averaging
For researchers in stochastic optimization, this provides a no-compromise guarantee that improves upon standard random iterate selection without sacrificing worst-case performance.
The paper tackles the problem of selecting the largest among n unknown values given a single unbiased estimate each, proposing strategies that are admissible and never worse than uniform random selection. Applied to stochastic optimization, the methods achieve online-to-batch conversion bounds that are never worse than random iterate selection but can be significantly better in benign settings.
We study the problem of selecting the largest among $n$ unknown values $x_1,\dots,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.