# Efficient improper learning for online logistic regression

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Mar 2020.

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

- [Jointly Efficient and Optimal Algorithms for Logistic Bandits](https://mlsanity.com/paper/2201.01985/) (2022)
- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion](https://mlsanity.com/paper/2310.18554/) (2023)
- [Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update](https://mlsanity.com/paper/2507.11847/) (2025)
- [Scale-free Unconstrained Online Learning for Curved Losses](https://mlsanity.com/paper/2202.05630/) (2022)
- [Mixability made efficient: Fast online multiclass logistic regression](https://mlsanity.com/paper/2110.03960/) (2021)
- [Efficient Methods for Online Multiclass Logistic Regression](https://mlsanity.com/paper/2110.03020/) (2021)
- [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023)
- [Online Platt Scaling with Calibeating](https://mlsanity.com/paper/2305.00070/) (2023)
- [Localization, Convexity, and Star Aggregation](https://mlsanity.com/paper/2105.08866/) (2021)
- [Second Order Path Variationals in Non-Stationary Online Learning](https://mlsanity.com/paper/2205.01921/) (2022)
- [Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizer](https://mlsanity.com/paper/2602.08372/) (2026)
- [On Misspecification in Prediction Problems and Robustness via Improper Learning](https://mlsanity.com/paper/2101.05234/) (2021)
- [Low Complexity Approximate Bayesian Logistic Regression for Sparse Online Learning](https://mlsanity.com/paper/2101.12113/) (2021)
- [Online Learning-to-Defer with Varying Experts](https://mlsanity.com/paper/2605.12340/) (2026)
- [Efficient Logistic Regression with Mixture of Sigmoids](https://mlsanity.com/paper/2604.02920/) (2026)

## Abstract (arXiv)

We consider the setting of online logistic regression and consider the regret with respect to the 2-ball of radius B. It is known (see [Hazan et al., 2014]) that any proper algorithm which has logarithmic regret in the number of samples (denoted n) necessarily suffers an exponential multiplicative constant in B. In this work, we design an efficient improper algorithm that avoids this exponential constant while preserving a logarithmic regret. Indeed, [Foster et al., 2018] showed that the lower bound does not apply to improper algorithms and proposed a strategy based on exponential weights with prohibitive computational complexity. Our new algorithm based on regularized empirical risk minimization with surrogate losses satisfies a regret scaling as O(B log(Bn)) with a per-round time-complexity of order O(d^2).