OEUVRE: OnlinE Unbiased Variance-Reduced loss Estimation
This addresses the need for efficient and unbiased loss estimation in online learning algorithms, which is incremental as it builds on the prequential method with improved theoretical guarantees and adaptive tuning.
The paper tackled the problem of accurately estimating expected loss in online learning, introducing OEUVRE, an estimator that recursively updates loss estimates in constant time and memory, and demonstrated that it matches or outperforms other estimators even with oracle-tuned hyperparameters.
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.