OEUVRE: OnlinE Unbiased Variance-Reduced Loss Estimation

Kanad Shrikar Pardeshi, Bryan Wilder, Aarti Singh
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:4267-4275, 2026.

Abstract

Online learning algorithms continually update their models as data arrive, making it essential to accurately estimate the expected loss at the current time step. The prequential method is an effective estimation approach which can be practically deployed in various ways. However, theoretical guarantees have previously been established under strong conditions on the algorithm, and practical algorithms have hyperparameters which require careful tuning. We introduce OEUVRE, an estimator that evaluates each incoming sample on the function learned at the current and previous time steps, recursively updating the loss estimate in constant time and memory. We use algorithmic stability, a property satisfied by many popular online learners, for optimal updates and prove consistency, convergence rates, and concentration bounds for our estimator. We design a method to adaptively tune OEUVRE’s hyperparameters and test it across diverse online and stochastic tasks. We observe that OEUVRE matches or outperforms other estimators even when their hyperparameters are tuned with oracle access to ground truth.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-pardeshi26a, title = { OEUVRE: OnlinE Unbiased Variance-Reduced Loss Estimation }, author = {Pardeshi, Kanad Shrikar and Wilder, Bryan and Singh, Aarti}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {4267--4275}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/pardeshi26a/pardeshi26a.pdf}, url = {https://proceedings.mlr.press/v300/pardeshi26a.html}, abstract = { Online learning algorithms continually update their models as data arrive, making it essential to accurately estimate the expected loss at the current time step. The prequential method is an effective estimation approach which can be practically deployed in various ways. However, theoretical guarantees have previously been established under strong conditions on the algorithm, and practical algorithms have hyperparameters which require careful tuning. We introduce OEUVRE, an estimator that evaluates each incoming sample on the function learned at the current and previous time steps, recursively updating the loss estimate in constant time and memory. We use algorithmic stability, a property satisfied by many popular online learners, for optimal updates and prove consistency, convergence rates, and concentration bounds for our estimator. We design a method to adaptively tune OEUVRE’s hyperparameters and test it across diverse online and stochastic tasks. We observe that OEUVRE matches or outperforms other estimators even when their hyperparameters are tuned with oracle access to ground truth. } }
Endnote
%0 Conference Paper %T OEUVRE: OnlinE Unbiased Variance-Reduced Loss Estimation %A Kanad Shrikar Pardeshi %A Bryan Wilder %A Aarti Singh %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-pardeshi26a %I PMLR %P 4267--4275 %U https://proceedings.mlr.press/v300/pardeshi26a.html %V 300 %X Online learning algorithms continually update their models as data arrive, making it essential to accurately estimate the expected loss at the current time step. The prequential method is an effective estimation approach which can be practically deployed in various ways. However, theoretical guarantees have previously been established under strong conditions on the algorithm, and practical algorithms have hyperparameters which require careful tuning. We introduce OEUVRE, an estimator that evaluates each incoming sample on the function learned at the current and previous time steps, recursively updating the loss estimate in constant time and memory. We use algorithmic stability, a property satisfied by many popular online learners, for optimal updates and prove consistency, convergence rates, and concentration bounds for our estimator. We design a method to adaptively tune OEUVRE’s hyperparameters and test it across diverse online and stochastic tasks. We observe that OEUVRE matches or outperforms other estimators even when their hyperparameters are tuned with oracle access to ground truth.
APA
Pardeshi, K.S., Wilder, B. & Singh, A.. (2026). OEUVRE: OnlinE Unbiased Variance-Reduced Loss Estimation . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:4267-4275 Available from https://proceedings.mlr.press/v300/pardeshi26a.html.

Related Material