# Logistic Regression Regret: What's the Catch?

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Feb 2020.

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

- [Scale-free Unconstrained Online Learning for Curved Losses](https://mlsanity.com/paper/2202.05630/) (2022)
- [Expected Worst Case Regret via Stochastic Sequential Covering](https://mlsanity.com/paper/2209.04417/) (2022)
- [Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm](https://mlsanity.com/paper/2205.03728/) (2022)
- [Bayesian logistic regression for online recalibration and revision of risk prediction models with performance guarantees](https://mlsanity.com/paper/2110.06866/) (2021)
- [Low Complexity Approximate Bayesian Logistic Regression for Sparse Online Learning](https://mlsanity.com/paper/2101.12113/) (2021)
- [Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood](https://mlsanity.com/paper/2410.03849/) (2024)
- [Hard labels sampled from sparse targets mislead rotation invariant algorithms](https://mlsanity.com/paper/2603.20967/) (2026)
- [Efficient Logistic Regression with Mixture of Sigmoids](https://mlsanity.com/paper/2604.02920/) (2026)
- [Sharp Minimax Regret for Infinite-Memory Logistic Prediction](https://mlsanity.com/paper/2608.26515/) (2026)
- [Beyond Second-Order Information: Paid Logistic Regression with Noisy Features](https://mlsanity.com/paper/2610.12919/) (2026)

## Abstract (arXiv)

We address the problem of the achievable regret rates with online logistic regression. We derive lower bounds with logarithmic regret under L1, L2, and L_∞ constraints on the parameter values. The bounds are dominated by d/2 log T, where T is the horizon and d is the dimensionality of the parameter space. We show their achievability for d=o(T1/3) in all these cases with Bayesian methods, that achieve them up to a d/2 log d term. Interesting different behaviors are shown for larger dimensionality. Specifically, on the negative side, if d = Omega(√T), any algorithm is guaranteed regret of Omega(d log T) (greater than Omega(√T)) under L_∞ constraints on the parameters (and the example features). On the positive side, under L1 constraints on the parameters, there exist algorithms that can achieve regret that is sub-linear in d for the asymptotically larger values of d. For L2 constraints, it is shown that for large enough d, the regret remains linear in d but no longer logarithmic in T. Adapting the redundancy-capacity theorem from information theory, we demonstrate a principled methodology based on grids of parameters to derive lower bounds. Grids are also utilized to derive some upper bounds. Our results strengthen results by Kakade and Ng (2005) and Foster et al. (2018) for upper bounds for this problem, introduce novel lower bounds, and adapt a methodology that can be used to obtain such bounds for other related problems. They also give a novel characterization of the asymptotic behavior when the dimension of the parameter space is allowed to grow with T. They additionally establish connections to the information theory literature, demonstrating that the actual regret for logistic regression depends on the richness of the parameter class, where even within this problem, richer classes lead to greater regret.