# Parameter-free online learning via model selection

arXiv: https://arxiv.org/abs/1801.00101 · HTML: https://mlsanity.com/paper/1801.00101/

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Dec 2017.

## Built on by (most cited first, 30 of 34)

- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [Cost-Effective Online Multi-LLM Selection with Versatile Reward Models](https://mlsanity.com/paper/2405.16587/) (2024)
- [Parameter-free Regret in High Probability with Heavy Tails](https://mlsanity.com/paper/2210.14355/) (2022)
- [Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits](https://mlsanity.com/paper/2403.07213/) (2024)
- [Normalized Gradients for All](https://mlsanity.com/paper/2308.05621/) (2023)
- [Fast TRAC: A Parameter-Free Optimizer for Lifelong Reinforcement Learning](https://mlsanity.com/paper/2405.16642/) (2024)
- [Pareto Optimal Model Selection in Linear Bandits](https://mlsanity.com/paper/2102.06593/) (2021)
- [Unconstrained Dynamic Regret via Sparse Coding](https://mlsanity.com/paper/2301.13349/) (2023)
- [Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning](https://mlsanity.com/paper/2205.11470/) (2022)
- [Personalized Federated Learning with Mixture of Models for Adaptive Prediction and Model Fine-Tuning](https://mlsanity.com/paper/2410.21547/) (2024)
- [Never Start from Scratch: Expediting On-Device LLM Personalization via Explainable Model Selection](https://mlsanity.com/paper/2504.13938/) (2025)
- [Anytime Model Selection in Linear Bandits](https://mlsanity.com/paper/2307.12897/) (2023)
- [Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback](https://mlsanity.com/paper/2310.14085/) (2023)
- [On the Necessity of Collaboration for Online Model Selection with Decentralized Data](https://mlsanity.com/paper/2404.09494/) (2024)
- [Universal Online Convex Optimization with 1 Projection per Round](https://mlsanity.com/paper/2405.19705/) (2024)
- [Distributed Online Learning for Joint Regret with Communication Constraints](https://mlsanity.com/paper/2102.07521/) (2021)
- [Universal Online Convex Optimization Meets Second-order Bounds](https://mlsanity.com/paper/2105.03681/) (2021)
- [ChaCha for Online AutoML](https://mlsanity.com/paper/2106.04815/) (2021)
- [Sparsity-Based Interpolation of External, Internal and Swap Regret](https://mlsanity.com/paper/2502.04543/) (2025)
- [Comparator-Adaptive Phi-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games](https://mlsanity.com/paper/2505.17277/) (2025)
- [On the Learnability of Test-Time Adaptation: A Recovery Complexity Perspective](https://mlsanity.com/paper/2605.28057/) (2026)
- [Improved Regret Bounds for Online Kernel Selection under Bandit Feedback](https://mlsanity.com/paper/2303.05018/) (2023)
- [Budgeted Online Model Selection and Fine-Tuning via Federated Learning](https://mlsanity.com/paper/2401.10478/) (2024)
- [Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games](https://mlsanity.com/paper/2411.06069/) (2024)
- [LightRouter: Towards Efficient LLM Collaboration with Minimal Overhead](https://mlsanity.com/paper/2505.16221/) (2025)
- [Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications](https://mlsanity.com/paper/2509.08911/) (2025)
- [Managing Self-Learning Experts under Per-Round Budget Constraints](https://mlsanity.com/paper/2510.22654/) (2025)
- [Nonstochastic Bandits with Infinitely Many Experts](https://mlsanity.com/paper/2102.05164/) (2021)
- [Locally Optimal Descent for Dynamic Stepsize Scheduling](https://mlsanity.com/paper/2311.13877/) (2023)
- [Learnability in Online Kernel Selection with Memory Constraint via Data-dependent Regret Analysis](https://mlsanity.com/paper/2407.00916/) (2024)

## Abstract (arXiv)

We introduce an efficient algorithmic framework for model selection in online learning, also known as parameter-free online learning. Departing from previous work, which has focused on highly structured function classes such as nested balls in Hilbert space, we propose a generic meta-algorithm framework that achieves online model selection oracle inequalities under minimal structural assumptions. We give the first computationally efficient parameter-free algorithms that work in arbitrary Banach spaces under mild smoothness assumptions; previous results applied only to Hilbert spaces. We further derive new oracle inequalities for matrix classes, non-nested convex sets, and ℝd with generic regularizers. Finally, we generalize these results by providing oracle inequalities for arbitrary non-linear classes in the online supervised learning model. These results are all derived through a unified meta-algorithm scheme using a novel "multi-scale" algorithm for prediction with expert advice based on random playout, which may be of independent interest.