# Implicit Parameter-free Online Learning with Truncated Linear Models

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 42 references that are in the map.
- First posted on arXiv 19 Mar 2022.

## Builds on (most cited first, 19 of 19)

- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity](https://mlsanity.com/paper/1810.05633/) (2018)
- [Lipschitz and Comparator-Norm Adaptivity in Online Learning](https://mlsanity.com/paper/2002.12242/) (2020)
- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations](https://mlsanity.com/paper/1403.0628/) (2014)
- [Online Learning Without Prior Information](https://mlsanity.com/paper/1703.02629/) (2017)
- [Parameter-Free Online Convex Optimization with Sub-Exponential Noise](https://mlsanity.com/paper/1902.01500/) (2019)
- [Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning](https://mlsanity.com/paper/1406.3816/) (2014)
- [Parameter-free Stochastic Optimization of Variationally Coherent Functions](https://mlsanity.com/paper/2102.00236/) (2021)
- [Temporal Variability in Implicit Online Learning](https://mlsanity.com/paper/2006.07503/) (2020)
- [Adaptive scale-invariant online algorithms for learning linear models](https://mlsanity.com/paper/1902.07528/) (2019)
- [Better Parameter-free Stochastic Optimization with ODE Updates for Coin-Betting](https://mlsanity.com/paper/2006.07507/) (2020)
- [Online Learning: Sufficient Statistics and the Burkholder Method](https://mlsanity.com/paper/1803.07617/) (2018)
- [Scale-invariant unconstrained online learning](https://mlsanity.com/paper/1708.07042/) (2017)
- [Fully Implicit Online Learning](https://mlsanity.com/paper/1809.09350/) (2018)
- [Matrix-Free Preconditioning in Online Learning](https://mlsanity.com/paper/1905.12721/) (2019)

## Built on by (most cited first, 8 of 8)

- [An Exploration of Non-Euclidean Gradient Descent: Muon and its Many Variants](https://mlsanity.com/paper/2510.09827/) (2025)
- [MoMo: Momentum Models for Adaptive Learning Rates](https://mlsanity.com/paper/2305.07583/) (2023)
- [Normalized Gradients for All](https://mlsanity.com/paper/2308.05621/) (2023)
- [Tuning-Free Maximum Likelihood Training of Latent Variable Models via Coin Betting](https://mlsanity.com/paper/2305.14916/) (2023)
- [An Equivalence Between Static and Dynamic Regret Minimization](https://mlsanity.com/paper/2406.01577/) (2024)
- [Coin Sampling: Gradient-Based Bayesian Inference without Learning Rates](https://mlsanity.com/paper/2301.11294/) (2023)
- [Generalized Implicit Follow-The-Regularized-Leader](https://mlsanity.com/paper/2306.00201/) (2023)
- [Online Learning with Gradient-Variation Interval Regret](https://mlsanity.com/paper/2606.03831/) (2026)

## Abstract (arXiv)

Parameter-free algorithms are online learning algorithms that do not require setting learning rates. They achieve optimal regret with respect to the distance between the initial point and any competitor. Yet, parameter-free algorithms do not take into account the geometry of the losses. Recently, in the stochastic optimization literature, it has been proposed to instead use truncated linear lower bounds, which produce better performance by more closely modeling the losses. In particular, truncated linear models greatly reduce the problem of overshooting the minimum of the loss function. Unfortunately, truncated linear models cannot be used with parameter-free algorithms because the updates become very expensive to compute. In this paper, we propose new parameter-free algorithms that can take advantage of truncated linear models through a new update that has an "implicit" flavor. Based on a novel decomposition of the regret, the new update is efficient, requires only one gradient at each step, never overshoots the minimum of the truncated model, and retains the favorable parameter-free properties. We also conduct an empirical study demonstrating the practical utility of our algorithms.