Logistic Regression: Tight Bounds for Stochastic and Online Optimization

Elad Hazan, Tomer Koren, Kfir Y. Levy
Proceedings of The 27th Conference on Learning Theory, PMLR 35:197-209, 2014.

Abstract

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

Cite this Paper

BibTeX
@InProceedings{pmlr-v35-hazan14a, title = {Logistic Regression: Tight Bounds for Stochastic and Online Optimization}, author = {Hazan, Elad and Koren, Tomer and Levy, Kfir Y.}, booktitle = {Proceedings of The 27th Conference on Learning Theory}, pages = {197--209}, year = {2014}, editor = {Balcan, Maria Florina and Feldman, Vitaly and Szepesvári, Csaba}, volume = {35}, series = {Proceedings of Machine Learning Research}, address = {Barcelona, Spain}, month = {13--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v35/hazan14a.pdf}, url = {https://proceedings.mlr.press/v35/hazan14a.html}, abstract = {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).} }
Endnote
%0 Conference Paper %T Logistic Regression: Tight Bounds for Stochastic and Online Optimization %A Elad Hazan %A Tomer Koren %A Kfir Y. Levy %B Proceedings of The 27th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2014 %E Maria Florina Balcan %E Vitaly Feldman %E Csaba Szepesvári %F pmlr-v35-hazan14a %I PMLR %P 197--209 %U https://proceedings.mlr.press/v35/hazan14a.html %V 35 %X 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).
RIS
TY - CPAPER TI - Logistic Regression: Tight Bounds for Stochastic and Online Optimization AU - Elad Hazan AU - Tomer Koren AU - Kfir Y. Levy BT - Proceedings of The 27th Conference on Learning Theory DA - 2014/05/29 ED - Maria Florina Balcan ED - Vitaly Feldman ED - Csaba Szepesvári ID - pmlr-v35-hazan14a PB - PMLR DP - Proceedings of Machine Learning Research VL - 35 SP - 197 EP - 209 L1 - http://proceedings.mlr.press/v35/hazan14a.pdf UR - https://proceedings.mlr.press/v35/hazan14a.html AB - 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). ER -
APA
Hazan, E., Koren, T. & Levy, K.Y.. (2014). Logistic Regression: Tight Bounds for Stochastic and Online Optimization. Proceedings of The 27th Conference on Learning Theory, in Proceedings of Machine Learning Research 35:197-209 Available from https://proceedings.mlr.press/v35/hazan14a.html.

Related Material