MATH3340
Mathematics of Machine Learning
Generalization and VC dimension, algorithmic stability, convex and stochastic optimization, kernels and random features, neural network approximation and training, and model selection.
Your progress
0/ 21 sections marked complete
Next section: 1.1 Empirical risk and the size of a hypothesis class
Completion marks are saved in this browser.
This course in the web
In the MATH3340 notes
- Theorem cards
- 42
- Definitions
- 23
- Counterexamples
- 25
- Concept lenses
- 11
- Histories of ideas
- 3
- Proof X-rays
- 24
Sections with a history of an idea
- Kernel classification: hinge loss, duality, and support vectors11.1
- Random features: finite Gram approximation and ridge perturbation12.1
- Nyström approximation: landmark spans and PSD residuals14.1
None of these is on the timeline yet.
No concept lens from this course is recorded in the web yet.
Counts cover the 21 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
In the webTheorem cards 42 · Definitions 23 · Counterexamples 25 · Concept lenses 11 · Histories of ideas 3 · Proof X-rays 24
None of these is on the timeline yet.
No concept lens from this course is recorded in the web yet.
Counts cover the 21 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
Chapter 1 · 1 section
Generalization and complexity
Separate fitting from generalization, prove finite-class and Rademacher bounds, and see how covering numbers approximate an infinite class.
Theorems 3 · Definitions 1Counterexamples 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 1.1
Empirical risk and the size of a hypothesis class
Separate fitting from generalization, prove finite-class and Rademacher bounds, and see how covering numbers approximate an infinite class.
Chapter 2 · 1 section
Optimization for learning
Prove smooth gradient descent and projected stochastic-gradient bounds, calculate curvature and noise effects, and separate optimization from generalization.
Theorems 2 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 2.1
Descent, stochastic gradients, and optimization error
Prove smooth gradient descent and projected stochastic-gradient bounds, calculate curvature and noise effects, and separate optimization from generalization.
Chapter 3 · 1 section
Representation and selection
Derive kernel ridge regression, construct univariate ReLU approximants, and analyze what gradient descent selects in an overparameterized linear model.
Theorems 3 · Definitions 1Counterexamples 2Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 3.1
Kernels, ReLU approximation, and minimum-norm fitting
Derive kernel ridge regression, construct univariate ReLU approximants, and analyze what gradient descent selects in an overparameterized linear model.
Chapter 4 · 1 section
4.1 Concentration, contraction, and chaining
Turn absolute Rademacher averages into high-probability guarantees, prove loss contraction, and build a finite-scale entropy chain with explicit constants.
Theorems 2 · Definitions 1Counterexamples 2Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 4.1
Concentration, contraction, and chaining
Turn absolute Rademacher averages into high-probability guarantees, prove loss contraction, and build a finite-scale entropy chain with explicit constants.
Chapter 5 · 1 section
5.1 Constructing a reproducing-kernel Hilbert space
Build a function Hilbert space from a positive semidefinite kernel, prove the completion and reproducing steps, and derive interpolation and normalized ridge learning.
Theorems 2 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 5.1
Constructing a reproducing-kernel Hilbert space
Build a function Hilbert space from a positive semidefinite kernel, prove the completion and reproducing steps, and derive interpolation and normalized ridge learning.
Chapter 6 · 1 section
6.1 Constructive multivariate neural approximation
Build multivariate approximants from tensor hats and ReLU multiplication, track error and network size, and prove a finite-region limitation.
Theorems 2 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 6.1
Constructive multivariate neural approximation
Build multivariate approximants from tensor hats and ReLU multiplication, track error and network size, and prove a finite-region limitation.
Chapter 7 · 1 section
7.1 Jacobian stability and nonlinear training
Prove local-to-global fitting guarantees for smooth nonlinear least squares using Jacobian stability, path-length bounds, gradient flow and discrete descent.
Theorems 2 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 7.1
Jacobian stability and nonlinear training
Prove local-to-global fitting guarantees for smooth nonlinear least squares using Jacobian stability, path-length bounds, gradient flow and discrete descent.
Chapter 8 · 1 section
8. Logistic classification
Study empirical logistic loss, convexity and separation.
Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 8.1
Logistic loss, convexity and separation
Derive logistic gradients and curvature, and distinguish convexity from attainment.
Chapter 10 · 1 section
Algorithmic stability
Prove expected generalization through a replace-one identity, control regularized minimizers and coupled gradient iterates, and separate optimization error from statistical and penalty terms.
Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 10.1
Replace-one stability and regularized learning
Prove expected generalization through a replace-one identity, control regularized minimizers and coupled gradient iterates, and separate optimization error from statistical and penalty terms.
Chapter 11 · 1 section
Kernel classification
Derive hinge-loss representers, soft-margin duality and support-vector certificates with explicit intercept conventions.
Theorems 2 · Definitions 1Counterexamples 1Lenses 1History 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 11.1
Kernel classification: hinge loss, duality, and support vectors
Prove existence and a hinge-loss representer theorem, derive the soft-margin dual and strong duality, and interpret singular Gram matrices through exact examples.
Chapter 12 · 1 section
Random-feature kernel approximation
Prove unbiased PSD Gram approximation, finite-data concentration and ridge perturbation bounds, keeping computational and statistical error distinct.
Theorems 2 · Definitions 1Counterexamples 1Lenses 2History 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 12.1
Random features: finite Gram approximation and ridge perturbation
Build unbiased positive semidefinite random-feature Gram matrices, prove a finite-data concentration bound, and quantify its effect on ridge predictions with explicit failure cases.
Chapter 14 · 1 section
Landmark kernel approximation
Explain finite Nyström approximation through feature projection, singular block matrices and verifiable residual certificates.
Theorems 2 · Definitions 1Counterexamples 1Lenses 1History 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 14.1
Nyström approximation: landmark spans and PSD residuals
Derive finite Nyström approximation as feature projection, handle singular landmarks with a pseudoinverse, and prove residual and Schur-complement statements with explicit failure cases.
Chapter 15 · 1 section
Surrogate risk and classification
Connect conditional Bayes decisions to hinge and logistic risk, then track approximation, estimation and optimization errors.
Theorems 2 · Definitions 2Counterexamples 2Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 15.1
From surrogate loss to Bayes classification
Prove Bayes excess-risk and hinge/logistic calibration inequalities, then separate statistical, optimization and approximation errors in a classifier's guarantee.
Chapter 16 · 1 section
Leverage sampling for kernels
Prove a finite ridge-leverage landmark sampling guarantee and understand its limits.
Theorems 1 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 16.1
Ridge leverage sampling for landmark approximation
Prove an elementary finite-sample landmark guarantee using ridge leverage scores and a second-moment argument.
Chapter 17 · 1 section
VC dimension and learning
Count classifier patterns and connect shattering to uniform learning.
Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 17.1
Shattering, growth functions, and uniform learning
Count label patterns by the Sauer–Shelah lemma and derive a finite-class uniform convergence bound.
Chapter 18 · 1 section
Stochastic convex optimization
Track conditional noise through projection, prove convex averaging bounds, and obtain a strong-convexity rate with a fully telescoping weighted average.
Theorems 2 · Definitions 2Counterexamples 2Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 18.1
Projected stochastic gradients and weighted convex rates
Track conditional noise through projection, prove convex averaging bounds, and obtain a strong-convexity rate with a fully telescoping weighted average.
Chapter 19 · 1 section
Early stopping and risk
Analyze spectral filtering and the fixed-design bias–variance tradeoff.
Theorems 1 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 19.1
Early stopping, spectral filters, and prediction risk
Derive the fixed-design bias–variance tradeoff of gradient descent and compare its spectral filter with ridge regression.
Chapter 20 · 1 section
Validation and model selection
Select among independently trained predictors and understand the limits of a holdout guarantee.
Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 20.1
Selecting a predictor with independent validation data
Prove a finite holdout selection bound and examine data leakage and test reuse.
Chapter 21 · 1 section
Conditioning and descent
Analyze gradient descent under strong convexity and smoothness.
Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 21.1
Strong convexity, conditioning, and gradient descent
Prove a linear convergence rate for smooth strongly convex objectives and understand how curvature controls the step size.
Chapter 22 · 1 section
Backpropagation
Use the chain rule to differentiate a neural network.
Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 22.1
Backpropagation as the chain rule
Derive and calculate gradients in a two-layer neural network, including the limits of the derivative at a ReLU kink.
Chapter 23 · 1 section
Stochastic gradient convergence
Study diminishing-step stochastic gradient iterates over an infinite horizon.
Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 23.1
Diminishing steps and almost-sure convergence
Explain how accumulated progress and square-summable noise lead projected stochastic gradient descent to a strongly convex minimizer.