Computational Learning Theory

CS 4713 / CS 5713 · University of Oklahoma · Fall 2026

Overview

This course develops the mathematical foundations of machine learning from a computational and statistical perspective. We study what it means to learn from data — when it is possible, how many examples it requires, and at what computational cost.

Topics include the Probably Approximately Correct (PAC) model, sample complexity bounds, the VC dimension and its role in generalization, uniform convergence, bias-complexity tradeoffs, online learning and mistake bounds, boosting, and Rademacher complexity. Each topic concludes with an explicit bridge to modern AI: how classical learnability results shape — or break down for — large neural networks and language models.

CS 5713 students complete additional problems engaging with the primary research literature and deeper theoretical extensions.

Prerequisites: CS 4413 or DSA 4413 (Analysis of Algorithms), or permission of instructor.

Instructor: Jie Cao · jie.cao@ou.edu

Textbooks (all open-access):

Mitchell, Machine Learning (1997) — Mitchell
Shalev-Shwartz & Ben-David, Understanding Machine Learning (2014) — UML
Mohri, Rostamizadeh & Talwalkar, Foundations of Machine Learning (2nd ed.) — FoML

Tentative Schedule

Dates marked HW indicate a homework deadline (Thursday 11:59 pm). The schedule may shift; consult Canvas for the authoritative version.

Week	Dates	Topic	Notes
1	Aug 25 & 27	Course Introduction & Foundations of Machine Learning
2	Sep 1 & 3	Concept Learning & the Inductive Learning Hypothesis
3	Sep 8 & 10	PAC Learning I — The Basic Model & Consistent Learners	HW 1 due Sep 10
4	Sep 15 & 17	PAC Learning II — Sample Complexity for Finite Hypothesis Classes
5	Sep 22 & 24	PAC Learning III — Agnostic Learning & Inconsistent Learners	HW 2 due Sep 24
6	Sep 29 & Oct 1	No-Free-Lunch Theorems & Error Decomposition
7	Oct 6 & 8	VC Dimension I — Shattering, Definition & Examples	HW 3 due Oct 8
8	Oct 13 & 15	VC Dimension II — Sauer-Shelah Lemma & Fundamental Theorem of SL
9	Oct 20 & 22	Nonuniform Learnability & Structural Risk Minimization
10	Oct 27 & 29	Rademacher Complexity & Uniform Convergence	HW 4 due Oct 29
11	Nov 3 & 5	Mistake-Bound Learning — Halving Algorithm & Perceptron
12	Nov 10 & 12	Online Learning — Multiplicative Weights & Regret Analysis	HW 5 due Nov 12
13	Nov 17 & 19	Boosting — AdaBoost & Margin-Based Generalization
14	Nov 24	Review & Project Workshop (Nov 26: Thanksgiving — no class)
15	Dec 1 & 3	Capstone — Theory Meets Deep Learning & Large Language Models
16	Dec 8 & 10	Project Presentations