CS449/CS549/MA449

CS449 Computational Learning (Fall 2026: 8/25 - 12/3)

Alternate listing: CS549/MA449

Prerequisites:
CS344 Data Structures and Algorithms.
CS345 Automata Theory and Formal Languages.
Other: Linear Algebra (MA339) and Statistics (STAT383).

Instructor: Christino Tamon
Lectures: TR 8-9:15, SC386
Office Hours: SC373, TR 11-1, W 12-2. (Distance section: please email to arrange a zoom meeting.)

Text

M. Mohri, A. Rostamizadeh, A. Talwalkar, "Foundations of Machine Learning," 2nd edition, MIT Press, 2018. (online copy)
Additional text: I. Goodfellow, Y. Bengio, A. Courville, "Deep Learning," MIT Press, 2016. (link)

Syllabus

Computational learning theory studies algorithmic problems for inferring patterns and relations from data. This course describes the mathematical foundations of learning and explores the important connections and applications to areas such as artificial intelligence, cryptography, statistics, and bioinformatics. A list of relevant topics may include perceptron and online learning, graphical models and probabilistic inference, decision tree induction and boosting, analysis of Boolean functions, sample complexity bounds, cryptographic and complexity hardness, and reinforcement learning. If time permits, an introductory coverage of quantum machine learning will be given. Basic ideas from computer science and mathematics are employed to describe the main ideas and major developments in computational learning theory.

Objectives and Outcomes

The objective of the course is to cover fundamental topics of machine learning (such as perceptrons, neural networks, support vector machines, decision trees, boosting, hidden markov models, reinforcement learning).

(Course outcomes) Upon the completion of this course, students will be able to:

employ standard algorithms such as perceptron, neural networks, support vector machines, decision trees, and boosting, for solving machine learning problems.
use techniques such as gradient descent, backpropagation, kernel methods, and probabilistic analysis, to analyze the complexity of learning algorithms.
recognize incorrect analyses and construct counterexamples to false claims about learning algorithms.
explain the concept of NP-hardness and VC dimension to show the limits of designing efficient algorithms.

Requirements and Policies

Although attendance is not mandatory, students are responsible for all course materials covered in lectures. All students must submit their own work; the exchange of ideas are encouraged but ultimately the submitted work must be the student's own. Please refer to the Clarkson University Regulations for more guidelines on academic integrity and related matters.

Grading

Assignments and quizzes: 30%
Project: 10%
Midterm test: 20%
Final exam: 40%

Schedule (tentative)

Week 1:
Perceptron algorithm.
Week 2:
PAC learning: consistent algorithm, Occam's razor, Vapnik-Chervonenkis dimension.
Week 3-4:
Neural networks: sigmoided linear classifiers. Gradient descent. Backpropagation algorithm.
Week 5:
Online learning: Weighted Majority.
Week 6:
Boosting.
Week 7-8:
Markov models: MDP.
Week 9-10:
Markov models: POMDP.
Week 11-13:
Quantum machine learning.

Some brief/compressed lecture notes.

Aug 25
Perceptron.
Linearly separable data.
Reading: Freund-Schapire (1999). Chapter 5 (Section 5.1-5.2), Chapter 8 (Section 8.3).
Aug 27
Perceptron.
Mistake bound via margin.
Reading: Chapter 5 (Section 5.1-5.2), Chapter 8 (Section 8.3).
Sep 1
Softer perceptron: gradient descent with square loss.
How to smooth out the learning feedback.
Reading: Section 5.1-5.2, 8.3.
Sep 3
Neural networks: multilayer perceptron.
Backpropagation: gradient descent (calculus to the rescue).
Reading: see extra notes.
Sep 8
PAC learning.
When it is sufficient to be consistent.
Reading: Valiant (1984).
Sep 10
PAC learning.
Provable sample bounds: rays, finite class.
Reading: Chapter 1 (Kearns-Vazirani).
Sep 15
Sample complexity.
Vapnik-Chervonenkis (VC) dimension.
Reading: see Chapter 3 (section 3).
Sep 17
Occam's Razor.

Sep 22
Online learning model: Weighted Majority.
How to predict as well as the best expert.
Reading: Littlestone (1988). Littlestone-Warmuth (1994).
Sep 24
Drifting Weighted Majority.
How to predict with a switching expert.

Sep 30
Randomized Weighted Majority.

Reading: Blum (1998)
Oct 1
Boosting.
How to convert a weak to a strong learner: AdaBoost.
Reading: Schapire-Singer (1998).
Oct 6
Adaptive game-playing.

Source: Freund-Schapire (1999).
Oct 8

Oct 13
Short break. Oct 15
Guest lecture: Ola Ogunleye.
Exact learning model: learning DFA (Angluin's L* algorithm)
Reading: see class notes, Chapter 16. Angluin (1987).
Oct 20
Exact learning finite automata (DFA).
Angluin's L* algorithm.
Reading: see class notes.

Oct 22
Bandit problems.
EXP3: back to Randomized Weighted Majority.
Reading: Auer-CesaBianchi-Freund-Schapire (2002).
Oct 27
Support Vector Machines.
Kernel trick. Dual Perceptron algorithm. Oct 29
Midterm.
Nov 3
Markov decision process (MDP):
introduction.
Reading: Chapter 17.
Nov 5
Markov decision process (MDP):
Value function. Optimal policy.
Reading: Chapter 17.
Nov 10
Markov decision process (MDP):
Fixed-point iterator. Convergence.
Reading: Chapter 17.
Nov 12
Deep learning
Nov 17
Deep learning Nov 19
Deep learning
Nov 24
Nov 26
Thanksgiving break.
Dec 1
Statistical query model.
Reading: notes by Balcan.
Dec 3
Hardness of learning: Blum-Rivest.

Reading: Blum-Rivest (1992).

Assignments

Links

Software: scikit-learn, TensorFlow.
Others: C4.5, SVMlight, MLPack, RLtoolkit, WEKA, Vowpal Wabbit.
Repositories: ML, preflib, kaggle.

PROJECT

Choose a project topic of interest; you may work in groups of up to three or four.
Submit a final report (hardcopy, 5-10 pages) that contains at minimum the following separate sections:
- Abstract (What/Why/How).
  Provide this on a separate page.
- Background information and literature: what has been done, what is the state-of-the-art ideas or methods in the area.
  Include proper and complete bibliography (at the end of the document) for your sources; see examples of some journal papers listed below.
- Identify at least two possible ideas that can be done but has not been addressed in the literature.
  This can be either an improvement on implementation or on a mathematical idea.
Prepare a 5-10 minute (lightning) talk to be delivered during Dead Week (in class) or Finals week.
Submit by email your talk slides (PDF).
Submit any other items, if any, related to your project (code, etc) by email.

Miscellany

Beyond automata: Castro-Gavalda. Balle-Carreras-Luque-Quattoni. Nitay-Fisman-Ziv-Ukelson. Mohri-Yang.
Undecidability in ML: EMX. POMDP.
Multiplicative weights: portfolio selection: [newton], [original]. Kalai: stock.
Boosting: Schapire, pruning, imbalanced data.
Compression and learning: amnesia, anomaly detection, pattern detection.
Reinforcement learning: spectral, PAC-RL. hunch.
Information theory in learning: deep learning, etc.
Manifold learning. Belkin-Niyogi.
Perceptrons: margin-based, noisy (see Cohen).
PAC-Bayes: workshop, Guedj.
No Free Lunch theorems: free matrix lunch (Warmuth).
Differential privacy: primer, DL, axiomatics, applications, Smith, Balcan.
Fairness: book (fairness in ML), Dwork et al.. Kearns, Kleinberg.

Aug 25 Perceptron. Linearly separable data. Reading: Freund-Schapire (1999). Chapter 5 (Section 5.1-5.2), Chapter 8 (Section 8.3).	Aug 27 Perceptron. Mistake bound via margin. Reading: Chapter 5 (Section 5.1-5.2), Chapter 8 (Section 8.3).
Sep 1 Softer perceptron: gradient descent with square loss. How to smooth out the learning feedback. Reading: Section 5.1-5.2, 8.3.	Sep 3 Neural networks: multilayer perceptron. Backpropagation: gradient descent (calculus to the rescue). Reading: see extra notes.
Sep 8 PAC learning. When it is sufficient to be consistent. Reading: Valiant (1984).	Sep 10 PAC learning. Provable sample bounds: rays, finite class. Reading: Chapter 1 (Kearns-Vazirani).
Sep 15 Sample complexity. Vapnik-Chervonenkis (VC) dimension. Reading: see Chapter 3 (section 3).	Sep 17 Occam's Razor.
Sep 22 Online learning model: Weighted Majority. How to predict as well as the best expert. Reading: Littlestone (1988). Littlestone-Warmuth (1994).	Sep 24 Drifting Weighted Majority. How to predict with a switching expert.
Sep 30 Randomized Weighted Majority. Reading: Blum (1998)	Oct 1 Boosting. How to convert a weak to a strong learner: AdaBoost. Reading: Schapire-Singer (1998).
Oct 6 Adaptive game-playing. Source: Freund-Schapire (1999).	Oct 8
Oct 13 Short break.	Oct 15 Guest lecture: Ola Ogunleye. Exact learning model: learning DFA (Angluin's L* algorithm) Reading: see class notes, Chapter 16. Angluin (1987).
Oct 20 Exact learning finite automata (DFA). Angluin's L* algorithm. Reading: see class notes.	Oct 22 Bandit problems. EXP3: back to Randomized Weighted Majority. Reading: Auer-CesaBianchi-Freund-Schapire (2002).
Oct 27 Support Vector Machines. Kernel trick. Dual Perceptron algorithm.	Oct 29 Midterm.
Nov 3 Markov decision process (MDP): introduction. Reading: Chapter 17.	Nov 5 Markov decision process (MDP): Value function. Optimal policy. Reading: Chapter 17.
Nov 10 Markov decision process (MDP): Fixed-point iterator. Convergence. Reading: Chapter 17.	Nov 12 Deep learning
Nov 17 Deep learning	Nov 19 Deep learning
Nov 24	Nov 26 Thanksgiving break.
Dec 1 Statistical query model. Reading: notes by Balcan.	Dec 3 Hardness of learning: Blum-Rivest. Reading: Blum-Rivest (1992).