Test Before You Trust: Verifying Predictions in Online Allocation and Learning

Abstract: Learning-augmented algorithms aim to combine predictive advice with worst-case guarantees: they achieve near-optimal performance when predictions are accurate, while remaining robust when predictions are unreliable. A central challenge, however, is determining when predictions should actually be trusted—especially when their quality is unknown a priori.

In this talk, I present a principled “test-before-trust” paradigm for both online allocation and distribution learning. The key idea is to statistically validate predictions using a small testing phase before committing to prediction-driven decisions. Leveraging tools from distribution property testing, we design algorithms whose performance smoothly interpolates between classical worst-case guarantees and improved bounds when advice is accurate.

I will illustrate this framework in three settings. In online bipartite matching with imperfect advice, we establish tight impossibility results under adversarial arrivals and give testing-based algorithms under random order that adapt to advice quality. In high-dimensional Gaussian learning with predicted parameters, we show that advice can reduce the classical Õ(d²/ε²) sample complexity when sufficiently accurate, while retaining worst-case guarantees otherwise. Finally, for product distributions over {0,1}^d, we prove that although Ω(d/ε²) samples are necessary in the worst case, advice that is close in ℓ₁-distance enables learning with Õ(d^{1−η}/ε²) samples—without knowing the advice error in advance.

Together, these results demonstrate that statistical validation provides a unifying mechanism for controlling the robustness–consistency tradeoff across online allocation and high-dimensional learning.

Bio: Themis Gouleakis is an Assistant Professor in the College of Computing and Data Science at Nanyang Technological University. Prior to this, he was a postdoctoral researcher at the University of Southern California, supervised by Ilias Diakonikolas, and a postdoctoral fellow in the Algorithms and Complexity Department at the Max Planck Institute for Informatics. He also served as a Senior Research Fellow at the National University of Singapore, where he was supervised by Arnab Bhattacharyya and Vincent Y. F. Tan.
He received his Ph.D. from MIT, where he was affiliated with the Theory of Computation group in CSAIL and advised by Ronitt Rubinfeld.

He received the Outstanding Paper Award at the 33rd Annual Conference on Neural Information Processing Systems (NeurIPS 2019).

Website: Themis Gouleakis