Logistic Regression: The Importance of Being Improper

Abstract

Learning linear predictors with the logistic loss---both in stochastic and online settings---is a fundamental task in machine learning and statistics, with direct connections to classification and boosting. Existing "fast rates" for this setting exhibit exponential dependence on the predictor norm, and Hazan et al. (2014) showed that this is unfortunately unimprovable. Starting with the simple observation that the logistic loss is $1$-mixable, we design a new efficient improper learning algorithm for online logistic regression that circumvents the aforementioned lower bound with a regret bound exhibiting a doubly-exponential improvement in dependence on the predictor norm. This provides a positive resolution to a variant of the COLT 2012 open problem of McMahan and Streeter (2012) when improper learning is allowed. This improvement is obtained both in the online setting and, with some extra work, in the batch statistical setting with high probability. We also show that the improved dependence on predictor norm is near-optimal. Leveraging this improved dependency on the predictor norm yields the following applications: (a) we give algorithms for online bandit multiclass learning with the logistic loss with an $\tilde{O}(\sqrt{n})$ relative mistake bound across essentially all parameter ranges, thus providing a solution to the COLT 2009 open problem of Abernethy and Rakhlin (2009), and (b) we give an adaptive algorithm for online multiclass boosting with optimal sample complexity, thus partially resolving an open problem of Beygelzimer et al. (2015) and Jung et al. (2017). Finally, we give information-theoretic bounds on the optimal rates for improper logistic regression with general function classes, thereby characterizing the extent to which our improvement for linear classes extends to other parametric and even nonparametric settings.

Appeared at COLT 2018. V2 changes: Updated to match conference version, added discussion of Bayesian model averaging

References in corpus (2)

• Logistic Regression: Tight Bounds for Stochastic and Online Optimization
• Sequential Probability Assignment with Binary Alphabets and Large Classes of Experts

Cited by in corpus (9)

• No-regret Exploration in Contextual Reinforcement Learning
• Efficient improper learning for online logistic regression
• Minimax Rates for Conditional Density Estimation via Empirical Entropy
• A Minimax Lower Bound for Low-Rank Matrix-Variate Logistic Regression
• Exploiting the Surrogate Gap in Online Multiclass Classification
• Online Sampling from Log-Concave Distributions
• SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memory
• Mixability made efficient: Fast online multiclass logistic regression
• Localization, Convexity, and Star Aggregation