Publications
See also my Google Scholar profile.
conference papers
- A Black-Box Reduction from Regret to Multi-Level CoverageTuo Liu, Edgar Dobriban, and Francesco OrabonaIn The Fortieth Annual Conference on Neural Information Processing Systems (NeurIPS), 2026
Online Conformal Prediction (OCP) sequentially constructs prediction sets whose average empirical coverage converges to a target level over time, for arbitrary, potentially adversarial datasets. In the multi-level setting of OCP, prediction sets are produced at d coverage levels at once. Prior work showed that online gradient descent with lazy isotonic projections produces sets properly nested across levels, but with a √d dependence in the per-level coverage convergence rate. Here, we both generalize and improve prior work. First, we show that lazy isotonic projections can be safely used for the construction of multi-level online conformal prediction sets from any online learning algorithm. Then, through a black-box reduction, we show that the linearized regret of the online algorithm itself automatically gives control over both per-level calibration and distributional consistency of multi-level predictions via Fenchel duality. Finally, by using the Weighted Interval Score, the standard scoring rule for assessing multi-level interval forecasts, we prove that these projections reduce both the size of the sets and their under-coverage. We show two instantiations of our theory, p-norm Online Mirror Descent and coordinate-wise Universal-Portfolio, both improving the dependence on the number of levels to √(log d) for the multi-OCP problem. Experiments on stock prices, electricity demand, and synthetic streams confirm consistent gains in coverage-width trade-offs over existing baselines.
@inproceedings{liu2026blackbox, title = {A Black-Box Reduction from Regret to Multi-Level Coverage}, author = {Liu, Tuo and Dobriban, Edgar and Orabona, Francesco}, booktitle = {The Fortieth Annual Conference on Neural Information Processing Systems (NeurIPS)}, year = {2026}, } - Online Conformal Prediction via Universal Portfolio AlgorithmsTuo Liu, Edgar Dobriban, and Francesco OrabonaIn The Forty-Third International Conference on Machine Learning (ICML), 2026Spotlight (top 2.2%)
Online conformal prediction (OCP) seeks prediction intervals that achieve long-run 1−α coverage for arbitrary (possibly adversarial) data streams, while remaining as informative as possible. Existing OCP methods often require manual learning-rate tuning to work well, and may also require algorithm-specific analyses. Here, we develop a general regret-to-coverage theory for interval-valued OCP based on the (1−α)-pinball loss. Our first contribution is to identify linearized regret as a key notion, showing that controlling it implies coverage bounds for any online algorithm. This relies on a black-box reduction that depends only on the Fenchel conjugate of an upper bound on the linearized regret. Building on this theory, we propose UP-OCP, a parameter-free method for OCP, via a reduction to a two-asset portfolio selection problem, leveraging universal portfolio algorithms. We show strong finite-time bounds on the miscoverage of UP-OCP, even for polynomially growing predictions. Extensive experiments support that UP-OCP delivers consistently better size/coverage trade-offs than prior online conformal baselines.
@inproceedings{liu2026online, title = {Online Conformal Prediction via Universal Portfolio Algorithms}, author = {Liu, Tuo and Dobriban, Edgar and Orabona, Francesco}, booktitle = {The Forty-Third International Conference on Machine Learning (ICML)}, year = {2026}, } - Dual Averaging Converges for Nonconvex Smooth Stochastic OptimizationTuo Liu, El Mehdi Saad, Wojciech Kotłowski, and Francesco OrabonaIn The Twenty-Ninth Annual Conference on Artificial Intelligence and Statistics (AISTATS), 2026
Dual averaging and gradient descent with their stochastic variants stand as the two canonical recipe books for first-order optimization: Every modern variant can be viewed as a descendant of one or the other. In the convex regime, these algorithms have been deeply studied, and we know that they are essentially equivalent in terms of theoretical guarantees. On the other hand, in the non-convex setting, the situation is drastically different: While we know that SGD can minimize the gradient of non-convex smooth functions, no finite-time complexity guarantee for Stochastic Dual Averaging (SDA) was known in the same setting. In this paper, we close this gap by a reduction that views SDA as SGD applied to a sequence of implicitly regularized objectives. We show that a tuned SDA exhibits a rate of convergence O(1/T + σ log T/√T), similar to that of SGD under the same assumptions. To our best knowledge, this is the first complete convergence theory for dual averaging on non-convex smooth stochastic problems without restrictive assumptions, closing a long-standing open problem in the field. Beyond the base algorithm, we also discuss ADA-DA, a variant that marries SDA with AdaGrad’s auto-scaling, which achieves the same rate without requiring knowledge of the noise variance.
@inproceedings{liu2026dual, title = {Dual Averaging Converges for Nonconvex Smooth Stochastic Optimization}, author = {Liu, Tuo and Saad, El Mehdi and Kotłowski, Wojciech and Orabona, Francesco}, booktitle = {The Twenty-Ninth Annual Conference on Artificial Intelligence and Statistics (AISTATS)}, year = {2026}, }
preprints
- Monitoring for Shifts at Unknown Times: Parameter-Free Conditional Conformal MartingalesTuo Liu, Drew Prinster, and Francesco Orabona2026In submission
Conditional conformal test martingales provide sequential tests for detecting distribution shifts, using a fixed reference dataset to avoid contamination from test-time samples. Prior work used a penalized betting function via online optimization with smoothing, clipping, and other hyperparameters, which can adapt slowly when a shift occurs after a long stationary period. In this work, we introduce an approach that requires no hyperparameters and provably adapts quickly to shifts occurring at unknown times. Our key idea is to frame the penalized betting problem as portfolio selection in a three-asset market. Then, we use a restarting universal portfolio, with a heavy-tailed wealth allocation over time. We establish anytime false-alarm control and derive optimal finite-sample bounds on detection delay under detectable alternatives. We also develop an FFT-based implementation that computes the portfolio sequence over T rounds in O(T² ln T) time, instead of O(T³) of the naive implementation. Synthetic and real-world experiments suggest that the proposed approach adapts rapidly after long periods of null samples, with detection delays depending substantially less on shift time than prior baselines.
@misc{liu2026monitoring, title = {Monitoring for Shifts at Unknown Times: Parameter-Free Conditional Conformal Martingales}, author = {Liu, Tuo and Prinster, Drew and Orabona, Francesco}, year = {2026}, note = {In submission}, }