Logistic Regression: The Importance of Being Improper

Understand

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.