# Logistic Regression: Tight Bounds for Stochastic and Online Optimization

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2014.

## Built on by (most cited first, 30 of 31)

- [Multinomial Logit Contextual Bandits: Provable Optimality and Practicality](https://mlsanity.com/paper/2103.13929/) (2021)
- [Sketchy: Memory-efficient Adaptive Regularization with Frequent Directions](https://mlsanity.com/paper/2302.03764/) (2023)
- [Analyzing and Improving the Optimization Landscape of Noise-Contrastive Estimation](https://mlsanity.com/paper/2110.11271/) (2021)
- [To SMOTE, or not to SMOTE?](https://mlsanity.com/paper/2201.08528/) (2022)
- [Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution](https://mlsanity.com/paper/2103.06263/) (2021)
- [On the sample complexity of parameter estimation in logistic regression with normal design](https://mlsanity.com/paper/2307.04191/) (2023)
- [Mixability made efficient: Fast online multiclass logistic regression](https://mlsanity.com/paper/2110.03960/) (2021)
- [Convergence and concentration properties of constant step-size SGD through Markov chains](https://mlsanity.com/paper/2306.11497/) (2023)
- [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)
- [Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation](https://mlsanity.com/paper/2405.17061/) (2024)
- [Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition](https://mlsanity.com/paper/2202.11461/) (2022)
- [Localization, Convexity, and Star Aggregation](https://mlsanity.com/paper/2105.08866/) (2021)
- [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)
- [Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation](https://mlsanity.com/paper/2405.20165/) (2024)
- [Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback](https://mlsanity.com/paper/2310.14085/) (2023)
- [Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm](https://mlsanity.com/paper/2205.03728/) (2022)
- [Second Order Methods for Bandit Optimization and Control](https://mlsanity.com/paper/2402.08929/) (2024)
- [Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizer](https://mlsanity.com/paper/2602.08372/) (2026)
- [A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization](https://mlsanity.com/paper/2512.23190/) (2025)
- [Exploring Local Norms in Exp-concave Statistical Learning](https://mlsanity.com/paper/2302.10726/) (2023)
- [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)
- [Hebbian learning inspired estimation of the linear regression parameters from queries](https://mlsanity.com/paper/2311.03483/) (2023)
- [Classification as Direction Recovery: Improved Guarantees via Scale Invariance](https://mlsanity.com/paper/2205.08633/) (2022)
- [Supervised Learning for Table Tennis Match Prediction](https://mlsanity.com/paper/2303.16776/) (2023)
- [Online Learning Approach for Survival Analysis](https://mlsanity.com/paper/2402.05145/) (2024)
- [Eigen-Value: Efficient Domain-Robust Data Valuation via Eigenvalue-Based Approach](https://mlsanity.com/paper/2510.23409/) (2025)
- [OLC-WA: Drift Aware Tuning-Free Online Classification with Weighted Average](https://mlsanity.com/paper/2512.12785/) (2025)
- [Efficient Logistic Regression with Mixture of Sigmoids](https://mlsanity.com/paper/2604.02920/) (2026)

## Abstract (arXiv)

The logistic loss function is often advocated in machine learning and statistics as a smooth and strictly convex surrogate for the 0-1 loss. In this paper we investigate the question of whether these smoothness and convexity properties make the logistic loss preferable to other widely considered options such as the hinge loss. We show that in contrast to known asymptotic bounds, as long as the number of prediction/optimization iterations is sub exponential, the logistic loss provides no improvement over a generic non-smooth loss function such as the hinge loss. In particular we show that the convergence rate of stochastic logistic optimization is bounded from below by a polynomial in the diameter of the decision set and the number of prediction iterations, and provide a matching tight upper bound. This resolves the COLT open problem of McMahan and Streeter (2012).