# Mixability made efficient: Fast online multiclass logistic regression

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 20 references that are in the map.
- First posted on arXiv 8 Oct 2021.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions](https://mlsanity.com/paper/1301.6677/) (2013)
- [Sampling from a log-concave distribution with Projected Langevin Monte Carlo](https://mlsanity.com/paper/1507.02564/) (2015)
- [Fast rates in statistical and online learning](https://mlsanity.com/paper/1507.02592/) (2015)
- [Logistic Regression: The Importance of Being Improper](https://mlsanity.com/paper/1803.09349/) (2018)
- [Logistic Regression: Tight Bounds for Stochastic and Online Optimization](https://mlsanity.com/paper/1405.3843/) (2014)
- [Finite-sample analysis of M-estimators using self-concordance](https://mlsanity.com/paper/1810.06838/) (2018)
- [Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance](https://mlsanity.com/paper/1902.03046/) (2019)
- [An improper estimator with optimal excess risk in misspecified density estimation and logistic regression](https://mlsanity.com/paper/1912.10784/) (2019)
- [Probabilistic Tools for the Analysis of Randomized Optimization Heuristics](https://mlsanity.com/paper/1801.06733/) (2018)
- [Efficient improper learning for online logistic regression](https://mlsanity.com/paper/2003.08109/) (2020)
- [Efficient online learning with kernels for adversarial large scale problems](https://mlsanity.com/paper/1902.09917/) (2019)

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

- [Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion](https://mlsanity.com/paper/2310.18554/) (2023)
- [Improved Online Confidence Bounds for Multinomial Logistic Bandits](https://mlsanity.com/paper/2502.10020/) (2025)
- [Scale-free Unconstrained Online Learning for Curved Losses](https://mlsanity.com/paper/2202.05630/) (2022)
- [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)
- [Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss](https://mlsanity.com/paper/2402.08180/) (2024)
- [Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability](https://mlsanity.com/paper/2506.10616/) (2025)
- [Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm](https://mlsanity.com/paper/2205.03728/) (2022)
- [Enjoying Non-linearity in Multinomial Logistic Bandits: A Minimax-Optimal Algorithm](https://mlsanity.com/paper/2507.05306/) (2025)
- [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)
- [Efficient Multinomial Logistic Bandit via Frequent Directions](https://mlsanity.com/paper/2606.11968/) (2026)

## Abstract (arXiv)

Mixability has been shown to be a powerful tool to obtain algorithms with optimal regret. However, the resulting methods often suffer from high computational complexity which has reduced their practical applicability. For example, in the case of multiclass logistic regression, the aggregating forecaster (Foster et al. (2018)) achieves a regret of O(log(Bn)) whereas Online Newton Step achieves O(eBlog(n)) obtaining a double exponential gain in B (a bound on the norm of comparative functions). However, this high statistical performance is at the price of a prohibitive computational complexity O(n37).