Tag: machine learning
All the articles with the tag "machine learning".
-
Shattering and the VC dimension
Posted on:The VC dimension of a class of yes/no rules is the largest set of points it can label in every way. Past it, the labelings stop doubling, and that single integer governs learnability.
-
The Hanson–Wright inequality
Posted on:A quadratic form in independent random variables concentrates around the trace: a Gaussian tail near the mean via the Frobenius norm, an exponential tail further out via the operator norm.
-
Covering the sphere with ε-nets
Posted on:An ε-net replaces the sphere by finitely many directions, so a supremum over all unit vectors reduces to a finite union bound. Worked out on the operator norm of a random matrix.
-
Sudakov minoration, or how big a maximum must be
Posted on:Sudakov minoration lower-bounds the expected maximum of many Gaussians: if no two are too alike, the maximum is at least of order ε√(log N). The engine behind many impossibility proofs.
-
Bias-variance is a Pythagorean decomposition
Posted on:MSE = bias² + variance is the Pythagorean theorem in L²: a constant bias and a mean-zero residual are orthogonal, so their squared lengths add.
-
Voronoi tessellations and Lloyd's algorithm
Posted on:Generators partition the plane into cells, each closer to its generator than to any other. Lloyd's algorithm moves each generator to its cell's centroid and converges to k-means.
-
Optimal message passing on sparse graphs
Posted on:Our NeurIPS 2023 paper: the asymptotically Bayes-optimal classifier for node classification on sparse contextual stochastic block models, and what it implies for graph neural networks.
-
Marchenko-Pastur and the Wigner semicircle
Posted on:The eigenvalue histogram of a large random matrix converges to a deterministic shape: Marchenko-Pastur for sample covariance matrices, the Wigner semicircle for symmetric i.i.d. entries.