keyword
VC dimension
The Vapnik-Chervonenkis dimension, commonly abbreviated as VC dimension, is a mathematical measure of the capacity or expressive complexity of a hypothesis class in statistical learning theory. It is formally defined as the cardinality of the largest set of data points that the hypothesis class can shatter, meaning that the functions within the class can realize every possible binary labeling of those points. If a hypothesis class can shatter arbitrarily large finite sets of points, its VC dimension is defined to be infinite. In computational and statistical learning theory, this concept is central to characterizing learnability and sample complexity, providing distribution-free theoretical bounds on the generalization error of classification models trained via empirical risk minimization.
4 items
Mean Absolute Percentage Error for regression models
Arnaud de Myttenaere, Boris Golden, Bénédicte Le Grand, Fabrice Rossi
Why you should read this
Establishes theoretical foundations for Mean Absolute Percentage Error regression by proving the universal consistency of empirical risk minimization and demonstrating that training optimal MAPE models is equivalent to weighted Mean Absolute Error regression.
We study in this paper the consequences of using the Mean Absolute Percentage Error (MAPE) as a measure of quality for regression models. We prove the existence of an optimal MAPE model and we show the universal consistency of Empirical Risk Minimization based on the MAPE. We also show that finding the best model under the MAPE is equivalent to doing weighted Mean Absolute Error (MAE) regression, and we apply this weighting strategy to kernel regression. The behavior of the MAPE kernel regression is illustrated on simulated data.
Added
2026-09-25
Spectrally-normalized margin bounds for neural networks
Peter Bartlett, Dylan J. Foster, Matus Telgarsky
Why you should read this
Establishes margin-based generalization bounds for deep neural networks based on weight matrix spectral norms, offering theoretical and empirical evidence for why stochastic gradient descent achieves low generalization error.
This paper presents a margin-based multiclass generalization bound for neural networks that scales with their margin-normalized "spectral complexity": their Lipschitz constant, meaning the product of the spectral norms of the weight matrices, times a certain correction factor. This bound is empirically investigated for a standard AlexNet network trained with SGD on the mnist and cifar10 datasets, with both original and random labels; the bound, the Lipschitz constants, and the excess risks are all in direct correlation, suggesting both that SGD selects predictors whose complexity scales with the difficulty of the learning task, and secondly that the presented bound is sensitive to this complexity.
Added
2026-09-25
Feature selection, L1 vs. L2 regularization, and rotational invariance
Andrew Y. Ng
Why you should read this
Proves that L1-regularized logistic regression requires only logarithmically many training examples in the number of irrelevant features, whereas rotationally invariant methods like L2 regularization and SVMs suffer from sample complexity that scales at least linearly.
This document is a presentation slide deck and does not contain an abstract.
Added
2026-09-16
On Discriminative vs. Generative Classifiers: A comparison of logistic regression and naive Bayes
A. Ng, Michael I. Jordan
Why you should read this
Demonstrates that while discriminative classifiers achieve lower asymptotic error, generative models require only logarithmic sample complexity to approach their asymptotic performance, explaining why naive Bayes frequently outperforms logistic regression on smaller training sets.
We compare discriminative and generative learning as typified by logistic regression and naive Bayes. We show, contrary to a widely-held belief that discriminative classifiers are almost always to be preferred, that there can often be two distinct regimes of performance as the training set size is increased, one in which each algorithm does better. This stems from the observation—which is borne out in repeated experiments—that while discriminative learning has lower asymptotic error, a generative classifier may also approach its (higher) asymptotic error much faster.
Added
2026-09-14