Milestone map
Milestone map
3 milestones
Study PAC Learning and VC Dimension
12–20 weeks (includes prerequisites: probability theory and linear algebra)
Study the theoretical foundations of statistical learning: probably approximately correct (PAC) learning framework, VC dimension and its relationship to sample complexity, bias-variance tradeoff, and the bias-variance decomposition. Complete at least fifteen exercises from MIT OCW 18.657 or equivalent. Prove at least one VC dimension bound for a specific hypothesis class from scratch.
Proof required
Submit: a typed solution set for at least fifteen exercises on PAC learning, VC dimension, or sample complexity (with all derivation steps — not just final answers); a typed proof of the VC dimension for a specific hypothesis class (e.g. half-spaces in R^n, axis-aligned rectangles in R^2) with all proof steps; and a 200-word explanation of why VC dimension predicts generalisation error. An ML researcher or mathematician must confirm the solutions and proof are correct.
What gets checked
- At least fifteen exercise solutions with all derivation steps — not just final answers
- VC dimension proof is complete — not a sketch or reference to the standard result
- An ML researcher or mathematician has confirmed the solutions and proof are correct
Common mistakes
- Exercise solutions with only final answers — the proof requires showing all derivation steps
- VC dimension proof that cites the standard result without actually proving it for the specific hypothesis class
Resources
Foundationstart here
Depthgo deeper
What a verifier looks for
- Are at least fifteen exercise solutions shown with all derivation steps?
- Is the VC dimension proof complete for the specific hypothesis class — not a reference to the standard result?
- Ask: 'what does infinite VC dimension tell you about learnability?' — tests understanding of the learnability boundary
Derive Generalisation Bounds and Apply to Real Models
8–14 weeks (after milestone 1)
Study uniform convergence bounds (Hoeffding's inequality, Rademacher complexity). Derive the Rademacher complexity bound for a linear classifier. Apply the bound to a real model: train a linear classifier on a real dataset, compute the empirical Rademacher complexity, and compare the theoretical generalisation bound to the empirical train/test gap.
Proof required
Submit: a typed derivation of the Rademacher complexity bound for a linear classifier with all steps; a public GitHub repository (or Colab) containing the trained classifier on a real dataset, code computing the empirical Rademacher complexity, and a comparison showing the theoretical bound alongside the train and test accuracy; and a 200-word analysis explaining what the gap between the theoretical bound and the empirical gap tells you. An ML researcher must confirm the derivation is correct and the empirical computation is valid.
What gets checked
- Rademacher complexity derivation includes all proof steps — not a citation of the result
- Empirical Rademacher complexity is computed from the actual dataset — not a theoretical estimate
- An ML researcher has confirmed the derivation is correct and the empirical computation is valid
Common mistakes
- Derivation that cites the Rademacher bound without proving it for the linear classifier
- Empirical computation that estimates complexity theoretically rather than computing it from the actual dataset
Resources
Foundationstart here
Depthgo deeper
What a verifier looks for
- Does the derivation include all proof steps for the Rademacher bound?
- Is the empirical Rademacher complexity computed from the actual dataset — not estimated theoretically?
- Ask: 'why is the theoretical generalisation bound typically much looser than the empirical train/test gap?' — tests understanding of bound tightness
Present Statistical Learning Theory to an Expert Reviewer
4–8 weeks (after milestone 2)
Write a technical analysis (500 words) addressing the overparameterisation puzzle: why do neural networks with very high VC dimension generalise well despite classical theory predicting failure? Use at least two primary research papers (double descent, implicit regularisation, or similar). Present to an ML researcher who challenges your reasoning in at least two places.
Proof required
Submit: a technical analysis (at least 500 words) connecting classical statistical learning theory to the overparameterisation puzzle, citing at least two primary research papers; and a recording or transcript of a live review with an ML researcher who challenged your reasoning in at least two specific places.
What gets checked
- Analysis cites at least two primary research papers — not blog summaries of research
- Analysis engages specifically with why classical VC theory predicts poor generalisation for overparameterised models
- An ML researcher challenged the reasoning in at least two specific places in the documented live review
Common mistakes
- Analysis that describes neural network success without engaging with the specific prediction of classical VC theory
- Analysis drawn from blog summaries rather than primary papers
Resources
Foundationstart here
Depthgo deeper
What a verifier looks for
- Does the analysis cite primary papers — not blog summaries?
- Does the analysis engage specifically with why classical VC theory predicts poor generalisation?
- Were at least two specific reasoning steps challenged in the documented live review?