CSCI4230
Computational Learning Theory
PAC learning and VC theory, sample compression, online learning, boosting and statistical queries, active learning, learning with noise, cryptographic hardness and conformal prediction.
Your progress
0/ 25 sections marked complete
Next section: PAC learning, finite classes and VC dimension
Completion marks are saved in this browser.
This course in the web
In the CSCI4230 notes
- Theorem cards
- 50
- Definitions
- 34
- Counterexamples
- 26
- Concept lenses
- 8
- Histories of ideas
- 2
- Proof X-rays
- 27
Sections with a history of an idea
- Boosting and statistical queries6.1
- Pseudorandom functions and the limits of efficient PAC learning10.1
None of these is on the timeline yet.
No concept lens from this course is recorded in the web yet.
Counts cover the 25 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 50 · Definitions 34 · Counterexamples 26 · Concept lenses 8 · Histories of ideas 2 · Proof X-rays 27
None of these is on the timeline yet.
No concept lens from this course is recorded in the web yet.
Counts cover the 25 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 · 5 sections
PAC learning
PAC learning
Theorems 10 · Definitions 6Counterexamples 5Lenses 2Proof X-rays 6
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 1.1
PAC learning, finite classes and VC dimension
Separate statistical guarantees from computational efficiency using consistent learning, Occam bounds and shattering.
- 1.2
PAC learning monotone conjunctions
Construct a deletion learner and prove its distribution-free realizable PAC guarantee.
- 1.3
Learning axis-aligned boxes from positive examples
Construct a consistent learner and prove a distribution-free PAC guarantee, including distributions with atoms.
- 1.4
Learning signed-literal decision lists
Construct a consistent decision-list learner and prove a finite-class PAC guarantee.
- 1.5
PAC learning bounded-width DNF
Learn fixed-width Boolean disjunctions of conjunctions by a consistent deletion algorithm, and separate sample and running-time guarantees.
Chapter 2 · 5 sections
VC theory
VC theory
Theorems 10 · Definitions 5Counterexamples 5Lenses 1Proof X-rays 5
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 2.1
Growth functions, VC dimension and uniform convergence
Prove the Sauer–Shelah counting bound and use symmetrization to control empirical and population errors uniformly.
- 2.2
VC dimension of halfspaces and axis-aligned boxes
Prove geometric shattering bounds using affine dependence and coordinate extrema.
- 2.3
Unseen points and lower bounds for PAC learning
Use random labels on a shattered set and a rare event to prove sample lower bounds.
- 2.4
An agnostic lower bound from noisy labels
Prove a dimension-over-accuracy-squared sample lower bound by reducing learning to binary tests.
- 2.5
Rademacher complexity and uniform generalization
Use random signs, symmetrization and bounded differences to control a function class.
Chapter 3 · 1 section
Model selection
Model selection
Theorems 1 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 3.1
Structural risk minimization with class weights
Build simultaneous bounds for countably many finite classes and prove an oracle inequality for data-dependent model selection.
Chapter 4 · 1 section
Sample compression
Sample compression
Theorems 2 · Definitions 1Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 4.1
Sample compression and generalization
Prove a consistent compression bound, account for index and side-information costs, and construct a threshold learner.
Chapter 5 · 4 sections
Online learning
Online learning
Theorems 6 · Definitions 6Counterexamples 4Proof X-rays 5
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 5.1
Online mistake bounds and weighted majority
Prove realizable halving and weighted-majority guarantees, then connect sequential mistakes to expected population error.
- 5.2
Perceptron updates and margin mistake bounds
Prove a finite mistake bound from geometric separation and distinguish it from a statistical risk guarantee.
- 5.3
Exponential weights and regret against experts
Derive an additive regret bound for randomized full-information prediction with bounded losses.
- 5.4
High-probability online-to-batch conversion
Turn a sequential mistake bound into risk guarantees for a randomized mixture of stored predictors.
Chapter 6 · 2 sections
Boosting and statistical queries
Boosting and statistical queries
Theorems 5 · Definitions 3Counterexamples 3History 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 6.1
Boosting and statistical queries
Analyze a weighted-vote training bound and learn what accuracy a statistical query can extract from random examples.
- 6.2
From weak to strong learning by reweighting
Prove a population-level boosting guarantee and simulate adaptive reweighted distributions from fresh examples.
Chapter 7 · 2 sections
Statistical queries
Statistical queries
Theorems 5 · Definitions 4Counterexamples 2Lenses 2Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 7.1
Why statistical queries struggle with parity
Use orthogonality to prove a finite statistical-query lower bound and compare it with learning from individual labeled examples.
- 7.2
Statistical queries under classification noise
Simulate adaptive clean statistical queries from independently flipped labels and quantify the noise penalty.
Chapter 8 · 1 section
Active learning
Active learning
Theorems 3 · Definitions 2Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 8.1
Active learning: queries and label complexity
Analyze adaptive label requests for thresholds, compare them with passive samples, and identify when the comparison breaks down.
Chapter 9 · 1 section
Learning with noise
Learning with noise
Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 9.1
Learning with random classification noise
Derive the effect of independent label flips, prove a finite-class learning guarantee, and identify where the noise model matters.
Chapter 10 · 1 section
Cryptographic hardness
Cryptographic hardness
Theorems 2 · Definitions 2Counterexamples 1History 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 10.1
Pseudorandom functions and the limits of efficient PAC learning
Reduce a hypothetical PAC learner to an oracle distinguisher, accounting for repeated inputs on a finite domain.
Chapter 11 · 1 section
Conformal prediction
Finite-sample prediction sets and marginal coverage.
Theorems 2 · Definitions 2Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 11.1
Split conformal prediction and marginal coverage
Prove a finite-sample rank guarantee and distinguish marginal from group coverage.
Chapter 12 · 1 section
AdaBoost
Derive adaptive votes and training-error bounds on a fixed sample.
Theorems 2 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 12.1
AdaBoost: adaptive weights, margins and training-error bounds
Derive adaptive votes and normalization, prove a conditional finite-training bound, and work exact rounds.