Skip to content

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.

12 chapters · 25 sectionsEN · 繁 · 简
My course notes

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

None of these is on the timeline yet.

No concept lens from this course is recorded in the web yet.

Open this course in the knowledge map

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.

Open this course in the knowledge map

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.1

    PAC learning, finite classes and VC dimension

    Separate statistical guarantees from computational efficiency using consistent learning, Occam bounds and shattering.

  2. 1.2

    PAC learning monotone conjunctions

    Construct a deletion learner and prove its distribution-free realizable PAC guarantee.

  3. 1.3

    Learning axis-aligned boxes from positive examples

    Construct a consistent learner and prove a distribution-free PAC guarantee, including distributions with atoms.

  4. 1.4

    Learning signed-literal decision lists

    Construct a consistent decision-list learner and prove a finite-class PAC guarantee.

  5. 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

  1. 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.2

    VC dimension of halfspaces and axis-aligned boxes

    Prove geometric shattering bounds using affine dependence and coordinate extrema.

  3. 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.

  4. 2.4

    An agnostic lower bound from noisy labels

    Prove a dimension-over-accuracy-squared sample lower bound by reducing learning to binary tests.

  5. 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

  1. 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

  1. 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

  1. 5.1

    Online mistake bounds and weighted majority

    Prove realizable halving and weighted-majority guarantees, then connect sequential mistakes to expected population error.

  2. 5.2

    Perceptron updates and margin mistake bounds

    Prove a finite mistake bound from geometric separation and distinguish it from a statistical risk guarantee.

  3. 5.3

    Exponential weights and regret against experts

    Derive an additive regret bound for randomized full-information prediction with bounded losses.

  4. 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

  1. 6.1

    Boosting and statistical queries

    Analyze a weighted-vote training bound and learn what accuracy a statistical query can extract from random examples.

  2. 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

  1. 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.

  2. 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

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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.

Vercel visit statistics and public-page performance measurements each require separate consent. Neither is needed to use the website.

Website function storage (used when needed)

Security, sign-in and your chosen preferences use storage when needed. This is separate from optional statistics.

Withdrawing stops future statistics. The page reloads if analytics code needs unloading. It does not delete data already sent.

Read Cookie and storage details