Papers
The notes link these works where their ideas arise. This index collects the original papers and principal analyses, grouped by the chapters that use them; surveys that make good follow-up reading are marked.
Prediction, nearest neighbors, and linear methods
| Work | Idea developed in the module |
|---|---|
| Cover and Hart, Nearest Neighbor Pattern Classification (1967) | The asymptotic 1-NN error lies between \(R^*\) and \(2R^*(1-R^*)\) (chapter 1). |
| Stone, Consistent Nonparametric Regression (1977) | Conditions under which local averaging rules, including \(k\)-NN, are universally consistent (chapter 1). |
| Stone, Optimal Global Rates of Convergence for Nonparametric Regression (1982) | The minimax rate \(n^{-2/(d+2)}\) for Lipschitz regression functions and its dependence on dimension (chapter 1). |
| Beyer, Goldstein, Ramakrishnan, and Shaft, When Is “Nearest Neighbor” Meaningful? (1999) | Concentration of distances in high dimension (chapter 1). |
| Kpotufe, k-NN Regression Adapts to Local Intrinsic Dimension (2011) | Why nearest neighbors can work on high-dimensional data of low intrinsic dimension (chapter 1). |
| Rosenblatt, The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (1958) | The perceptron (chapter 2). |
| Freund and Schapire, Large Margin Classification Using the Perceptron Algorithm (1999) | Mistake bounds without separability, voted and averaged perceptrons, and kernelization (chapters 2 and 8). |
| Hoerl and Kennard, Ridge Regression: Biased Estimation for Nonorthogonal Problems (1970) | Ridge regression (chapter 3). |
| Tibshirani, Regression Shrinkage and Selection via the Lasso (1996) | The lasso (chapter 3). |
| Efron, Hastie, Johnstone, and Tibshirani, Least Angle Regression (2004) | The piecewise-linear lasso path (chapter 3). |
| Zou and Hastie, Regularization and Variable Selection via the Elastic Net (2005) | The elastic net and grouped selection of correlated features (chapter 3). |
| Friedman, Hastie, and Tibshirani, Regularization Paths for Generalized Linear Models via Coordinate Descent (2010) | Coordinate descent with warm starts along a penalty path (chapter 3). |
| Fisher, The Use of Multiple Measurements in Taxonomic Problems (1936) | Fisher’s linear discriminant (chapter 4). |
| Domingos and Pazzani, On the Optimality of the Simple Bayesian Classifier under Zero-One Loss (1997) | Why naive Bayes can classify well with poor probability estimates (chapter 4). |
| McCallum and Nigam, A Comparison of Event Models for Naive Bayes Text Classification (1998) | Bernoulli and multinomial event models (chapter 4). |
| Friedman, Regularized Discriminant Analysis (1989) | Shrinking between QDA, LDA, and a scaled identity (chapter 4). |
| Ng and Jordan, On Discriminative vs. Generative Classifiers: A Comparison of Logistic Regression and Naive Bayes (2001) | Generative estimates converge faster to a worse asymptote (chapters 4–5). |
| Efron, The Efficiency of Logistic Regression Compared to Normal Discriminant Analysis (1975) | The statistical cost of discriminative estimation when the Gaussian model is true (chapter 5). |
| Albert and Anderson, On the Existence of Maximum Likelihood Estimates in Logistic Regression Models (1984) | Separation and the nonexistence of the MLE (chapter 5). |
| Soudry, Hoffer, Nacson, Gunasekar, and Srebro, The Implicit Bias of Gradient Descent on Separable Data (2018) | Gradient descent on separable data converges in direction to the maximum-margin separator (chapter 5). |
| Gneiting and Raftery, Strictly Proper Scoring Rules, Prediction, and Estimation (2007) | Proper scoring rules (chapter 5). |
| Niculescu-Mizil and Caruana, Predicting Good Probabilities with Supervised Learning (2005) | Calibration of common classifiers, Platt scaling, and isotonic regression (chapter 5). |
| Guo, Pleiss, Sun, and Weinberger, On Calibration of Modern Neural Networks (2017) | Temperature scaling and the miscalibration of large models (chapter 5). |
Model assessment and learning theory
| Work | Idea developed in the module |
|---|---|
| Zhang, Statistical Behavior and Consistency of Classification Methods Based on Convex Risk Minimization (2004) | What each convex surrogate estimates (chapter 6). |
| Bartlett, Jordan, and McAuliffe, Convexity, Classification, and Risk Bounds (2006) | Classification calibration of surrogate losses (chapter 6). |
| Belkin, Hsu, Ma, and Mandal, Reconciling Modern Machine-Learning Practice and the Classical Bias–Variance Trade-off (2019) | Double descent (chapter 6). |
| Hastie, Montanari, Rosset, and Tibshirani, Surprises in High-Dimensional Ridgeless Least Squares Interpolation (2022) | Exact risk of minimum-norm interpolation (chapter 6). |
| Efron, The Estimation of Prediction Error: Covariance Penalties and Cross-Validation (2004) | Optimism and covariance penalties (chapter 6). |
| Bates, Hastie, and Tibshirani, Cross-Validation: What Does It Estimate and How Well Does It Do It? (2023) | What the cross-validation estimate targets, why its naive standard error is too small, and nested cross-validation for honest intervals (chapter 6). |
| Cawley and Talbot, On Over-fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation (2010) | Selection bias and nested cross-validation (chapter 6). |
| Kaufman, Rosset, Perlich, and Stitelman, Leakage in Data Mining: Formulation, Detection, and Avoidance (2012) | Data leakage (chapter 6). |
| Fawcett, An Introduction to ROC Analysis (2006) | ROC curves and AUC (chapter 6). |
| Dietterich, Approximate Statistical Tests for Comparing Supervised Classification Learning Algorithms (1998) | McNemar’s test and the pitfalls of resampled \(t\) tests (chapter 6). |
| Nadeau and Bengio, Inference for the Generalization Error (2003) | The corrected resampled \(t\) test (chapter 6). |
| Blumer, Ehrenfeucht, Haussler, and Warmuth, Learnability and the Vapnik–Chervonenkis Dimension (1989) | Finite VC dimension characterizes PAC learnability (chapter 7). |
| Sauer, On the Density of Families of Sets (1972) | Sauer’s lemma (chapter 7). |
| Ehrenfeucht, Haussler, Kearns, and Valiant, A General Lower Bound on the Number of Examples Needed for Learning (1989) | The \(\Omega(v/\varepsilon)\) realizable lower bound for VC dimension \(v\) (chapter 7). |
| Hanneke, The Optimal Sample Complexity of PAC Learning (2016) | Removing the \(\log(1/\varepsilon)\) factor from the realizable upper bound (chapter 7). |
| Pitt and Valiant, Computational Limitations on Learning from Examples (1988) | Representation-dependent hardness of learning (chapter 7). |
| Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm (1988) | The mistake-bound model and the Littlestone dimension (chapter 7). |
| Littlestone and Warmuth, The Weighted Majority Algorithm (1994) | Learning from expert advice (chapter 7). |
Kernels, trees, and ensembles
| Work | Idea developed in the module |
|---|---|
| Boser, Guyon, and Vapnik, A Training Algorithm for Optimal Margin Classifiers (1992) | The kernelized maximum-margin classifier (chapter 8). |
| Cortes and Vapnik, Support-Vector Networks (1995) | The soft-margin SVM (chapter 8). |
| Platt, Sequential Minimal Optimization (1998) | Solving the SVM dual two variables at a time (chapter 8). |
| Aronszajn, Theory of Reproducing Kernels (1950) | Reproducing kernel Hilbert spaces (chapter 8). |
| Schölkopf, Herbrich, and Smola, A Generalized Representer Theorem (2001) | The representer theorem (chapter 8). |
| Williams and Seeger, Using the Nyström Method to Speed Up Kernel Machines (2000) | Low-rank kernel approximation (chapter 8). |
| Rahimi and Recht, Random Features for Large-Scale Kernel Machines (2007) | Random Fourier features (chapter 8). |
| Crammer and Singer, On the Algorithmic Implementation of Multiclass Kernel-Based Vector Machines (2001) | The multiclass SVM (chapter 8). |
| Hyafil and Rivest, Constructing Optimal Binary Decision Trees Is NP-Complete (1976) | Why trees are grown greedily (chapter 9). |
| Quinlan, Induction of Decision Trees (1986) | ID3 and information gain (chapter 9). |
| Loh, Fifty Years of Classification and Regression Trees (2014) | Survey of tree algorithms and their selection biases (chapter 9). |
| Breiman, Bagging Predictors (1996) | Bootstrap aggregation of unstable learners (chapter 10). |
| Krogh and Vedelsby, Neural Network Ensembles, Cross Validation, and Active Learning (1994) | The ambiguity decomposition (chapter 10). |
| Breiman, Random Forests (2001) | Random forests, strength and correlation, and out-of-bag estimates (chapter 10). |
| Geurts, Ernst, and Wehenkel, Extremely Randomized Trees (2006) | Random thresholds as further decorrelation (chapter 10). |
| Lin and Jeon, Random Forests and Adaptive Nearest Neighbors (2006) | Forests as adaptive weighted neighbors (chapter 10). |
| Biau and Scornet, A Random Forest Guided Tour (2016) | Survey of the theory of random forests (chapter 10). |
| Strobl, Boulesteix, Zeileis, and Hothorn, Bias in Random Forest Variable Importance Measures (2007) | The bias of impurity importance toward features with many split points (chapter 10). |
| Schapire, The Strength of Weak Learnability (1990) | Weak learning implies strong learning (chapter 11). |
| Freund and Schapire, A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting (1997) | AdaBoost and its training-error bound (chapter 11). |
| Schapire, Freund, Bartlett, and Lee, Boosting the Margin (1998) | Margin-based generalization bounds for voting classifiers (chapter 11). |
| Friedman, Hastie, and Tibshirani, Additive Logistic Regression: A Statistical View of Boosting (2000) | AdaBoost as stagewise minimization of the exponential loss (chapter 11). |
| Friedman, Greedy Function Approximation: A Gradient Boosting Machine (2001) | Gradient boosting (chapter 11). |
| Friedman, Stochastic Gradient Boosting (2002) | Subsampling in gradient boosting (chapter 11). |
| Chen and Guestrin, XGBoost: A Scalable Tree Boosting System (2016) | Newton steps and regularized tree objectives (chapter 11). |
| Grinsztajn, Oyallon, and Varoquaux, Why Do Tree-Based Models Still Outperform Deep Learning on Typical Tabular Data? (2022) | The practical standing of boosted trees on tabular data (chapter 11). |
Unsupervised learning and probabilistic models
| Work | Idea developed in the module |
|---|---|
| Pearson, On Lines and Planes of Closest Fit to Systems of Points in Space (1901) | PCA as best low-dimensional fit (chapter 12). |
| Hotelling, Analysis of a Complex of Statistical Variables into Principal Components (1933) | PCA as variance maximization (chapter 12). |
| Johnstone, On the Distribution of the Largest Eigenvalue in Principal Components Analysis (2001) | The spiked covariance model and the largest noise eigenvalue (chapter 12). |
| Baik, Ben Arous, and Péché, Phase Transition of the Largest Eigenvalue for Nonnull Complex Sample Covariance Matrices (2005) | The detection threshold for a spike (chapter 12). |
| Tipping and Bishop, Probabilistic Principal Component Analysis (1999) | PCA as a latent-variable model (chapter 12). |
| Minka, Automatic Choice of Dimensionality for PCA (2000) | A Bayesian choice of the number of components (chapter 12). |
| Schölkopf, Smola, and Müller, Nonlinear Component Analysis as a Kernel Eigenvalue Problem (1998) | Kernel PCA (chapter 12). |
| Jolliffe and Cadima, Principal Component Analysis: A Review and Recent Developments (2016) | Survey (chapter 12). |
| Kleinberg, An Impossibility Theorem for Clustering (2002) | No clustering function satisfies three natural axioms (chapter 13). |
| Lloyd, Least Squares Quantization in PCM (1982) | Lloyd’s algorithm (chapter 13). |
| Arthur and Vassilvitskii, k-means++: The Advantages of Careful Seeding (2007) | \(k\)-means++ and its \(O(\log k)\) guarantee (chapter 13). |
| Ward, Hierarchical Grouping to Optimize an Objective Function (1963) | Ward linkage (chapter 13). |
| Tibshirani, Walther, and Hastie, Estimating the Number of Clusters in a Data Set via the Gap Statistic (2001) | The gap statistic (chapter 13). |
| Rousseeuw, Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis (1987) | Silhouette widths (chapter 13). |
| Hubert and Arabie, Comparing Partitions (1985) | The adjusted Rand index (chapter 13). |
| von Luxburg, A Tutorial on Spectral Clustering (2007) | Spectral clustering and graph Laplacians (chapter 13). |
| Dempster, Laird, and Rubin, Maximum Likelihood from Incomplete Data via the EM Algorithm (1977) | The EM algorithm (chapter 14). |
| Wu, On the Convergence Properties of the EM Algorithm (1983) | What EM’s monotonicity does and does not imply about convergence (chapter 14). |
| Neal and Hinton, A View of the EM Algorithm That Justifies Incremental, Sparse, and Other Variants (1998) | EM as coordinate ascent on a lower bound (chapter 14). |
| Kanagawa, Hennig, Sejdinovic, and Sriperumbudur, Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences (2018) | Gaussian-process regression and kernel ridge regression (chapter 15). |
| Jones, Schonlau, and Welch, Efficient Global Optimization of Expensive Black-Box Functions (1998) | Expected improvement (chapter 15). |
| Srinivas, Krause, Kakade, and Seeger, Gaussian Process Optimization in the Bandit Setting (2010) | GP-UCB and regret bounds (chapter 15). |
| Snoek, Larochelle, and Adams, Practical Bayesian Optimization of Machine Learning Algorithms (2012) | Bayesian optimization for hyperparameter tuning (chapter 15). |
Optional chapters
| Work | Idea developed in the module |
|---|---|
| Schölkopf, Janzing, Peters, Sgouritsa, Zhang, and Mooij, On Causal and Anticausal Learning (2012) | When unlabeled inputs carry information about the labels (chapter 16). |
| Nigam, McCallum, Thrun, and Mitchell, Text Classification from Labeled and Unlabeled Documents Using EM (2000) | Semi-supervised naive Bayes with EM (chapter 16). |
| Blum and Mitchell, Combining Labeled and Unlabeled Data with Co-Training (1998) | Co-training (chapter 16). |
| Zhu, Ghahramani, and Lafferty, Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions (2003) | Harmonic label propagation (chapter 16). |
| Oliver, Odena, Raffel, Cubuk, and Goodfellow, Realistic Evaluation of Deep Semi-Supervised Learning Algorithms (2018) | Evaluation pitfalls for semi-supervised methods (chapter 16). |
| Zhu, Semi-Supervised Learning | Survey (chapter 16). |
| Lewis and Gale, A Sequential Algorithm for Training Text Classifiers (1994) | Uncertainty sampling (chapter 16). |
| Dasgupta, Two Faces of Active Learning (2011) | Label complexity and exploiting cluster structure (chapter 16). |
| Beygelzimer, Dasgupta, and Langford, Importance Weighted Active Learning (2009) | Correcting the sampling bias of active queries (chapter 16). |
| Settles, Active Learning Literature Survey (2009) | Survey (chapter 16). |
| Cleveland, Robust Locally Weighted Regression and Smoothing Scatterplots (1979) | LOESS (chapter 17). |
| Hastie and Tibshirani, Generalized Additive Models (1986) | Additive models and backfitting (chapter 17). |
| Friedman, Bentley, and Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time (1977) | \(k\)-d tree search (chapter 17). |
| Malkov and Yashunin, Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016) | Graph-based approximate search (chapter 17). |