Convex Risk Minimization and Conditional Probability Estimation

Matus Telgarsky, Miroslav Dudík, Robert Schapire
Proceedings of The 28th Conference on Learning Theory, PMLR 40:1629-1682, 2015.

Abstract

This paper proves, in very general settings, that convex risk minimization is a procedure to select a unique conditional probability model determined by the classification problem. Unlike most previous work, we give results that are general enough to include cases in which no minimum exists, as occurs typically, for instance, with standard boosting algorithms. Concretely, we first show that any sequence of predictors minimizing convex risk over the source distribution will converge to this unique model when the class of predictors is linear (but potentially of infinite dimension). Secondly, we show the same result holds for \emphempirical risk minimization whenever this class of predictors is finite dimensional, where the essential technical contribution is a norm-free generalization bound.

Cite this Paper

BibTeX
@InProceedings{pmlr-v40-Telgarsky15, title = {Convex Risk Minimization and Conditional Probability Estimation}, author = {Telgarsky, Matus and Dudík, Miroslav and Schapire, Robert}, booktitle = {Proceedings of The 28th Conference on Learning Theory}, pages = {1629--1682}, year = {2015}, editor = {Grünwald, Peter and Hazan, Elad and Kale, Satyen}, volume = {40}, series = {Proceedings of Machine Learning Research}, address = {Paris, France}, month = {03--06 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v40/Telgarsky15.pdf}, url = {https://proceedings.mlr.press/v40/Telgarsky15.html}, abstract = {This paper proves, in very general settings, that convex risk minimization is a procedure to select a unique conditional probability model determined by the classification problem. Unlike most previous work, we give results that are general enough to include cases in which no minimum exists, as occurs typically, for instance, with standard boosting algorithms. Concretely, we first show that any sequence of predictors minimizing convex risk over the source distribution will converge to this unique model when the class of predictors is linear (but potentially of infinite dimension). Secondly, we show the same result holds for \emphempirical risk minimization whenever this class of predictors is finite dimensional, where the essential technical contribution is a norm-free generalization bound. } }
Endnote
%0 Conference Paper %T Convex Risk Minimization and Conditional Probability Estimation %A Matus Telgarsky %A Miroslav Dudík %A Robert Schapire %B Proceedings of The 28th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2015 %E Peter Grünwald %E Elad Hazan %E Satyen Kale %F pmlr-v40-Telgarsky15 %I PMLR %P 1629--1682 %U https://proceedings.mlr.press/v40/Telgarsky15.html %V 40 %X This paper proves, in very general settings, that convex risk minimization is a procedure to select a unique conditional probability model determined by the classification problem. Unlike most previous work, we give results that are general enough to include cases in which no minimum exists, as occurs typically, for instance, with standard boosting algorithms. Concretely, we first show that any sequence of predictors minimizing convex risk over the source distribution will converge to this unique model when the class of predictors is linear (but potentially of infinite dimension). Secondly, we show the same result holds for \emphempirical risk minimization whenever this class of predictors is finite dimensional, where the essential technical contribution is a norm-free generalization bound.
RIS
TY - CPAPER TI - Convex Risk Minimization and Conditional Probability Estimation AU - Matus Telgarsky AU - Miroslav Dudík AU - Robert Schapire BT - Proceedings of The 28th Conference on Learning Theory DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Telgarsky15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 40 SP - 1629 EP - 1682 L1 - http://proceedings.mlr.press/v40/Telgarsky15.pdf UR - https://proceedings.mlr.press/v40/Telgarsky15.html AB - This paper proves, in very general settings, that convex risk minimization is a procedure to select a unique conditional probability model determined by the classification problem. Unlike most previous work, we give results that are general enough to include cases in which no minimum exists, as occurs typically, for instance, with standard boosting algorithms. Concretely, we first show that any sequence of predictors minimizing convex risk over the source distribution will converge to this unique model when the class of predictors is linear (but potentially of infinite dimension). Secondly, we show the same result holds for \emphempirical risk minimization whenever this class of predictors is finite dimensional, where the essential technical contribution is a norm-free generalization bound. ER -
APA
Telgarsky, M., Dudík, M. & Schapire, R.. (2015). Convex Risk Minimization and Conditional Probability Estimation. Proceedings of The 28th Conference on Learning Theory, in Proceedings of Machine Learning Research 40:1629-1682 Available from https://proceedings.mlr.press/v40/Telgarsky15.html.

Related Material