Suboptimality of Penalized Empirical Risk Minimization in Classification

2007/03/27 by Lecué, Guillaume
#62G05 #FOS: Economics and business #FOS: Mathematics #Risk Management (q-fin.RM) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.math/0703811

Abstract

Let \cF be a set of M classification procedures with values in [-1,1]. Given a loss function, we want to construct a procedure which mimics at the best possible rate the best procedure in \cF. This fastest rate is called optimal rate of aggregation. Considering a continuous scale of loss functions with various types of convexity, we prove that optimal rates of aggregation can be either ((log M)/n)^1/2 or (log M)/n. We prove that, if all the M classifiers are binary, the (penalized) Empirical Risk Minimization procedures are suboptimal (even under the margin/low noise condition) when the loss function is somewhat more than convex, whereas, in that case, aggregation procedures with exponential weights achieve the optimal rate of aggregation.

Related

• Optimal Binary Classifier Aggregation for General Losses
• On optimality of empirical risk minimization in linear aggregation
• Fast learning rates in statistical inference through aggregation
• On aggregation for heavy-tailed classes
• Optimal oracle inequality for aggregation of classifiers under low noise condition