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 = {Matus Telgarsky and Miroslav Dudík and Robert Schapire}, booktitle = {Proceedings of The 28th Conference on Learning Theory}, pages = {1629--1682}, year = {2015}, editor = {Peter Grünwald and Elad Hazan and Satyen Kale}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 1629--1682 %U http://proceedings.mlr.press %V 40 %W PMLR %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 PY - 2015/06/26 DA - 2015/06/26 ED - Peter Grünwald ED - Elad Hazan ED - Satyen Kale ID - pmlr-v40-Telgarsky15 PB - PMLR SP - 1629 DP - PMLR EP - 1682 L1 - http://proceedings.mlr.press/v40/Telgarsky15.pdf UR - http://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 PMLR 40:1629-1682

Related Material