JMLR: Asymptotics in Empirical Risk Minimization

[[Redistributed from JMLR announce]]

~From: elm@xxxxxxxxxxxx
~Date: Thu, 15 Dec 2005 22:31:29 -0500
~Subject: [Jmlr-announce] Asymptotics in Empirical Risk Minimization

The Journal of Machine Learning Research (www.jmlr.org) is pleased to
announce publication of a new paper:
------------------------------------------------------------------------
-------
Asymptotics in Empirical Risk Minimization
Leila Mohammadi, Sara van de Geer
JMLR 6(Dec): 2027--2047, 2005.

Abstract

In this paper, we study a two-category classification problem. We
indicate the categories by labels Y=1 and Y=-1. We observe a covariate,
or feature, X \elem \mathcal{X} \subset R^d. Consider a collection
{h_a} of classifiers indexed by a finite-dimensional parameter a, and
the classifier h_{a*} that minimizes the prediction error over this
class. The parameter a* is estimated by the empirical risk minimizer ^an
over the class, where the empirical risk is calculated on a training
sample of size n. We apply the Kim Pollard Theorem to show that under
certain differentiability assumptions, ^an converges to a* with rate
n^{-1/3}, and also present the asymptotic distribution of the
renormalized estimator.

For example, let V_0 denote the set of x on which, given X=x, the label
Y=1 is more likely (than the label Y=-1). If X is one-dimensional, the
set V_0 is the union of disjoint intervals. The problem is then to
estimate the thresholds of the intervals. We obtain the asymptotic
distribution of the empirical risk minimizer when the classifiers have
K thresholds, where K is fixed. We furthermore consider an extension to
higher-dimensional X, assuming basically that V_0 has a smooth boundary
in some given parametric class.

We also discuss various rates of convergence when the differentiability
conditions are possibly violated. Here, we again restrict ourselves to
one-dimensional X. We show that the rate is n^{-1} in certain cases,
and then also obtain the asymptotic distribution for the empirical
prediction error.
------------------------------------------------------------------------
------
This paper and previous papers are available electronically at
http://www.jmlr.org in PDF format. The papers of Volumes 1-4 were also
published in hardcopy by MIT Press; please see
http://mitpress.mit.edu/JMLR for details. Volume 5 and subsequent
volumes will be printed in hardcopy by Microtome Publishing. Please see
http://www.mtome.com/Publications/jmlr.html for details and ordering
information.

-Erik G. Learned-Miller
elm@xxxxxxxxxxxx

[ comp.ai is moderated. To submit, just post and be patient, or if ]
[ that fails mail your article to <comp-ai@xxxxxxxxxxxxxxxxxx>, and ]
[ ask your news administrator to fix the problems with your system. ]
.