ON SURROGATE LOSS FUNCTIONS AND f-DIVERGENCES
Published 3 December 2008
Xuanlong Nguyen, Martin J. Wainwright, Michael I. Jordan
Citations98
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
The goal in the binary classification problem is to estimate a discriminant function γ from observations of covariate vectors and corresponding binary labels. We consider an elaboration of this problem in which the covariates are not available directly, but are transformed by a dimensionality-reducing quantizer Q. We present conditions on loss functions such that empirical risk minimization yields Bayes consistency when both the discriminant function and the quantizer are estimated. These conditions are stated in terms of a general correspondence between loss functions and a class of functionals known as Ali-Silvey or f-divergence functionals. For the 0-1 loss, this correspondence was established by Blackwell [3]; we extend the correspondence to the broader class of surrogate loss functions that play a key role in the general theory of Bayes consistency for binary classification. Our result makes it possible to pick out the (strict) subset of surrogate loss functions that yield Bayes consistency for joint estimation of the discriminant function and the quantizer.
Keywords
MathematicsDecision Sciences
Machine LearningSupport-vector networks
40,463 Citations1995Corinna Cortes, Vladimir Vapnik
High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated and the performance of the support- vector network is compared to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.
Elements of Information Theory
37,533 Citations2001Thomas M. Cover, Joy A. Thomas
Machine LearningSupport-Vector Networks
33,035 Citations1995Corinna Cortes, Vladimir Vapnik
High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated and the performance of the support- vector network is compared to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.
Journal of Computer and System SciencesA Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
20,320 Citations1997Yoav Freund, Robert E. Schapire
The Annals of StatisticsAdditive logistic regression: a statistical view of boosting (With discussion and a rejoinder by the authors)
6,842 Citations2000Jerome H. Friedman, Trevor Hastie +1 more
This work shows that this seemingly mysterious phenomenon of boosting can be understood in terms of well-known statistical principles, namely additive modeling and maximum likelihood, and develops more direct approximations and shows that they exhibit nearly identical results to boosting.
Transactions of the American Mathematical SocietyTheory of reproducing kernels
5,435 Citations1950N. Aronszajn
Springer series in statisticsWeak Convergence and Empirical Processes
5,037 Citations1996Aad van der Vaart, Jon A. Wellner
This chapter discusses Convergence: Weak, Almost Uniform, and in Probability, which focuses on the part of Convergence of the Donsker Property which is concerned with Uniformity and Metrization.
Proceedings of the IEEESensor networks: Evolution, opportunities, and challenges
3,061 Citations2003Chee-Yee Chong, Sanjeev Kumar
The history of research in sensor networks over the past three decades is traced, including two important programs of the Defense Advanced Research Projects Agency (DARPA) spanning this period: the Distributed Sensor Networks (DSN) and the Sensor Information Technology (SensIT) programs.
IRE Transactions on Communications SystemsThe Divergence and Bhattacharyya Distance Measures in Signal Selection
1,844 Citations1967T. Kailath
This partly tutorial paper compares the properties of an often used measure, the divergence, with a new measure that is often easier to evaluate, called the Bhattacharyya distance, which gives results that are at least as good and often better than those given by the divergence.
The Annals of Mathematical StatisticsEquivalent Comparisons of Experiments
1,451 Citations1953David Blackwell
Cambridge University Press eBooksOn the method of bounded differences
1,428 Citations1989Colin McDiarmid
Fundamentals of Convex Analysis
1,412 Citations2001Jean‐Baptiste Hiriart‐Urruty, Claude Lemaréchal
Journal of the Royal Statistical Society Series B (Statistical Methodology)A General Class of Coefficients of Divergence of One Distribution from Another
1,230 Citations1966Syed Mustafa Ali, S. D. Silvey
Comparison of Experiments
1,031 Citations1951David Blackwell
Lecture notes in mathematicsConvex Functions, Monotone Operators and Differentiability
1,019 Citations1989R. R. Phelps
Journal of the American Statistical AssociationConvexity, Classification, and Risk Bounds
1,019 Citations2006Peter L. Bartlett, Michael I. Jordan +1 more
A general quantitative relationship between the risk as assessed using the 0–1 loss and the riskAs assessed using any nonnegative surrogate loss function is provided, and it is shown that this relationship gives nontrivial upper bounds on excess risk under the weakest possible condition on the loss function.
Proceedings of the IEEEDistributed detection with multiple sensors I. Advanced topics
743 Citations1997Rick S. Blum, S.A. Kassam +1 more
Signal detection has developed many useful and interesting extensions of the basic concepts, resulting in new ideas of asymptotically optimum nonparametric, robust, and sequential centralized detection.
The Annals of StatisticsStatistical behavior and consistency of classification methods based on convex risk minimization
709 Citations2004Tong Zhang
This study sheds light on the good performance of some recently proposed linear classification methods including boosting and support vector machines and shows their limitations and suggests possible improvements.
IEEE Transactions on Signal ProcessingDecentralized detection in sensor networks
558 Citations2003Jean‐François Chamberland, Venugopal V. Veeravalli
A binary decentralized detection problem in which a network of wireless sensors provides relevant information about the state of nature to a fusion center, and it is shown that having a set of identical binary sensors is asymptotically optimal, as the number of observations per sensor goes to infinity.
IEEE Transactions on Information TheorySome inequalities for information divergence and related measures of discrimination
324 Citations2000Flemming Topsøe
This study depends on two measures of discrimination, called capacitory discrimination and triangular discrimination, and obtains certain improvements of the well-known Pinsker inequality.
Lecture notes in mathematicsConvex Functions, Monotone Operators and Differentiability
252 Citations1993R. R. Phelps
IEEE Transactions on Information TheoryConsistency of Support Vector Machines and Other Regularized Kernel Classifiers
224 Citations2005Ingo Steinwart
It is shown that various classifiers that are based on minimization of a regularized risk are universally consistent, i.e., they can asymptotically learn in every classification task.
The Annals of StatisticsOn the Bayes-risk consistency of regularized boosting methods
188 Citations2004Gábor Lugosi, Nicolas Vayatis
The main result of the paper is that certain regularized boosting algorithms provide Bayes-risk consistent classifiers under the sole assumption that the Bayes classifier may be approximated by a convex combination of the base classifiers.
IEEE Transactions on Information TheoryQuantization for decentralized hypothesis testing under communication constraints
179 Citations1990M. Longo, T. Lookabaugh +1 more
The following problem is addressed: given that the peripheral encoders that satisfy capacity constraints are scalar quantizers, how should they be designed in order that the central test to be performed on their output indices is most powerful?
IRE Transactions on Communications SystemsApplications of Ali-Silvey Distance Measures in the Design Generalized Quantizers for Binary Decision Systems
150 Citations1977H. Vincent Poor, John B. Thomas
The Ali-Silvey class of distance measures is applied to the problem of designing quantizers for use in binary detection systems, and necessary conditions are established for the selection of quantizer parameters in this context.
IEEE Transactions on CommunicationsExtremal properties of likelihood-ratio quantizers
135 Citations1993John N. Tsitsiklis
The Annals of StatisticsProcess consistency for AdaBoost
131 Citations2004Wenxin Jiang
It is shown under general regularity conditions that during the process of AdaBoost a consistent prediction is generated, which has the prediction error approximating the optimal Bayes error as the sample size increases.
IEEE Transactions on Signal ProcessingNonparametric decentralized detection using kernel methods
77 Citations2005XuanLong Nguyen, Martin J. Wainwright +1 more
This work proposes a novel algorithm using the framework of empirical risk minimization and marginalized kernels and analyzes its computational and statistical properties both theoretically and empirically.
The Annals of Mathematical StatisticsOn the Design and Comparison of Certain Dichotomous Experiments
47 Citations1956R. N. Bradt, Samuel Karlin
Applied Physics Letters10.1162/153244304773936108
41 Citations2000
This work constructs a fully adaptive procedure, which, without knowing the smoothness parameter of the decision boundary, converges at the same rate as if the smoothness parameter were known, and proves consistency of the approach under rather general conditions.