Adaptive Weighted Averaging

Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish Purohit
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:684-707, 2026.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-bhaskara26a, title = {Adaptive Weighted Averaging}, author = {Bhaskara, Aditya and Cutkosky, Ashok and Kumar, Ravi and Purohit, Manish}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {684--707}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/bhaskara26a/bhaskara26a.pdf}, url = {https://proceedings.mlr.press/v336/bhaskara26a.html}, 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.} }
Endnote
%0 Conference Paper %T Adaptive Weighted Averaging %A Aditya Bhaskara %A Ashok Cutkosky %A Ravi Kumar %A Manish Purohit %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-bhaskara26a %I PMLR %P 684--707 %U https://proceedings.mlr.press/v336/bhaskara26a.html %V 336 %X 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.
APA
Bhaskara, A., Cutkosky, A., Kumar, R. & Purohit, M.. (2026). Adaptive Weighted Averaging. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:684-707 Available from https://proceedings.mlr.press/v336/bhaskara26a.html.

Related Material