A new analytical approach to consistency and overfitting in regularized empirical risk minimization

DOI10.1017/S0956792517000201zbMATH Open1383.49029arXiv1607.00274OpenAlexW2963466282MaRDI QIDQ3133606FDOQ3133606

Authors: Nicolás García Trillos, Ryan W. Murray 

Publication date: 5 February 2018

Published in: European Journal of Applied Mathematics (Search for Journal in Brave)

Abstract: This work considers the problem of binary classification: given training data $x_1,dots,x_n$ from a certain population, together with associated labels $y_1,dots,y_{n}inleft0,1ight$, determine the best label for an element $x$ not among the training data. More specifically, this work considers a variant of the regularized empirical risk functional which is defined intrinsically to the observed data and does not depend on the underlying population. Tools from modern analysis are used to obtain a concise proof of asymptotic consistency as regularization parameters are taken to zero at rates related to the size of the sample. These analytical tools give a new framework for understanding overfitting and underfitting, and rigorously connect the notion of overfitting with a loss of compactness.

Full work available at URL: https://arxiv.org/abs/1607.00274

Recommendations

• Efficiency of classification methods based on empirical risk minimization
• Error analysis on regularized learning
• Consistency of Support Vector Machines and Other Regularized Kernel Classifiers
• Iterative regularization for learning with convex loss functions
• Consistency analysis of spectral regularization algorithms

zbMATH Keywords

classificationempirical risk minimizationoverfittingdiscrete to continuumgraph total variation

Mathematics Subject Classification ID

Asymptotic properties of nonparametric inference (62G20) Graph theory (including graph drawing) in computer science (68R10) Methods involving semicontinuity and convergence; relaxation (49J45) Existence of optimal solutions to problems involving randomness (49J55)

Cites Work

• Title not available (Why is that?)
• Gradient flows in metric spaces and in the space of probability measures
• Convergence rates of posterior distributions.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An introduction to \(\Gamma\)-convergence
• Posterior contraction rates for the Bayesian approach to linear ill-posed inverse problems
• Modern methods in the calculus of variations. \(L^p\) spaces
• Title not available (Why is that?)
• Hitchhiker's guide to the fractional Sobolev spaces
• Title not available (Why is that?)
• A first course in Sobolev spaces
• Parametrized measures and variational principles
• Continuum limit of total variation on point clouds
• On the Rate of Convergence of Empirical Measures in ∞-transportation Distance
• Iterative Methods for Total Variation Denoising
• A variational approach to remove outliers and impulse noise
• Theoretical foundations and numerical methods for sparse recovery. Papers based on the presentations of the summer school ``Theoretical foundations and numerical methods for sparse recovery, Vienna, Austria, August 31 -- September 4, 2009.
• Title not available (Why is that?)
• Statistical learning theory: models, concepts, and results
• Consistency of Cheeger and ratio graph cuts

Cited In (11)

• Variational Limits of $k$-NN Graph-Based Functionals on Data Clouds
• Introduction: Big data and partial differential equations
• Consistency of fractional graph-Laplacian regularization in semisupervised learning with finite labels
• Mumford–Shah functionals on graphs and their asymptotics
• Eikonal depth: an optimal control approach to statistical depths
• Title not available (Why is that?)
• Title not available (Why is that?)
• Analysis of $p$-Laplacian Regularization in Semisupervised Learning
• A Maximum Principle Argument for the Uniform Convergence of Graph Laplacian Regressors
• Large data limit for a phase transition model with the p-Laplacian on point clouds
• Partial differential equations and variational methods for geometric processing of images

This page was built for publication: A new analytical approach to consistency and overfitting in regularized empirical risk minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3133606)