mlsanityData to 14 Oct 2026

Mixability made efficient: Fast online multiclass logistic regression

arXiv 2110.03960 ↗First posted 8 Oct 2021cs.LG math.ST stat.MLcited by 12

Not on the map. Why?

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).

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

12 of 20 references.

References · 12

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2013Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributionscited by 60
  3. 2015Sampling from a log-concave distribution with Projected Langevin Monte Carlocited by 52
  4. 2015Fast rates in statistical and online learningcited by 47
  5. 2018Logistic Regression: The Importance of Being Impropercited by 41
  6. 2014Logistic Regression: Tight Bounds for Stochastic and Online Optimizationcited by 31
  7. 2018Finite-sample analysis of M-estimators using self-concordancecited by 30
  8. 2019Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordancecited by 28
  9. 2019An improper estimator with optimal excess risk in misspecified density estimation and logistic regressioncited by 25
  10. 2018Probabilistic Tools for the Analysis of Randomized Optimization Heuristicscited by 24
  11. 2020Efficient improper learning for online logistic regressioncited by 16
  12. 2019Efficient online learning with kernels for adversarial large scale problemscited by 12

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 3; 2024: 1; 2025: 3; 2026: 3.

12 papers.

  1. 2023Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversioncited by 24
  2. 2025Improved Online Confidence Bounds for Multinomial Logistic Banditscited by 15
  3. 2022Scale-free Unconstrained Online Learning for Curved Lossescited by 13
  4. 2023High-Probability Risk Bounds via Sequential Predictorscited by 10
  5. 2023Online Platt Scaling with Calibeatingcited by 8
  6. 2024Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Losscited by 7
  7. 2025Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixabilitycited by 7
  8. 2022Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithmcited by 5
  9. 2025Enjoying Non-linearity in Multinomial Logistic Bandits: A Minimax-Optimal Algorithmcited by 3
  10. 2026Online Learning-to-Defer with Varying Expertscited by 1
  11. 2026Efficient Logistic Regression with Mixture of Sigmoidscited by 0
  12. 2026Efficient Multinomial Logistic Bandit via Frequent Directionscited by 0