Reconciling Universal and Uniform Learning with Q-Aggregation
Abstract
We study regression under bounded responses in terms of excess mean squared error. When the comparator class is finite, this setting is known as model selection aggregation, and achieving minimax excess risk requires improper learning algorithms. Contrary to this, in the universal learning framework no improperness is needed, as simple empirical risk minimization achieves the best-possible exponential learning rate. Hence, the two frameworks suggest different optimal algorithmic principles. This poses the question of best-of-both-worlds guarantees: Are minimax and universal exponential rates achievable by the same algorithm? For finite hypothesis classes, we answer this question in the affirmative by showing that the Q-aggregation estimator - which is known to achieve minimax optimal tails - achieves exponential universal rates. A wide range of other estimators and algorithmic principles (ERM, sequential averaging, pruning, and star estimation) do not achieve both. For countably infinite hypothesis classes, we answer the question in the negative by showing that there is an inherent trade-off between achieving exponential universal and minimax uniform rates. This trade-off is exactly traced by combining optimal algorithms from each world using Q-aggregation. Besides these results, we prove several additional structural results about universal rates in learning with squared loss.
Related
- Recurrent Neural Networks and (Time-Uniform) Universal Approximation of Bayesian Filters
- Three Routes to One Answer: Reconciling AIPW, TMLE, and Double Machine Learning for Applied Researchers
- Progressive-Resolution Secure Aggregation for Federated Learning
- Online Line Aggregation with Deadlines: Randomized Guarantees and Learning-Augmented Tradeoffs
- Graph Representation Learning via Adaptive Expectile Aggregation
BibTeX
@misc{hogsgaard2026reconciling,
title = {{Reconciling Universal and Uniform Learning with $Q$-Aggregation}},
author = {Mikael Møller Høgsgaard and Patrick Rebeschini and Tobias Wegel},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05041},
eprint = {2609.05041},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05041},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Reconciling Universal and Uniform Learning with Q-Aggregation
AU - Mikael Møller Høgsgaard
AU - Patrick Rebeschini
AU - Tobias Wegel
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.05041
UR - https://arxiv.org/abs/2609.05041
AB - We study regression under bounded responses in terms of excess mean squared error. When the comparator class is finite, this setting is known as model selection aggregation, and achieving minimax excess risk requires improper learning algorithms. Contrary to this, in the universal learning framework no improperness is needed, as simple empirical risk minimization achieves the best-possible exponential learning rate. Hence, the two frameworks suggest different optimal algorithmic principles. This poses the question of best-of-both-worlds guarantees: Are minimax and universal exponential rates achievable by the same algorithm? For finite hypothesis classes, we answer this question in the affirmative by showing that the Q-aggregation estimator - which is known to achieve minimax optimal tails - achieves exponential universal rates. A wide range of other estimators and algorithmic principles (ERM, sequential averaging, pruning, and star estimation) do not achieve both. For countably infinite hypothesis classes, we answer the question in the negative by showing that there is an inherent trade-off between achieving exponential universal and minimax uniform rates. This trade-off is exactly traced by combining optimal algorithms from each world using Q-aggregation. Besides these results, we prove several additional structural results about universal rates in learning with squared loss.
ER -