CS4540/CS8803: (Is there) A(n Algorithmic) Theory of (Artificial) Intelligence(?)
Fall 2023. MW: 9:3010:45, Mason 5134
Santosh Vempala, Klaus 2222, Office hour: Mon 1:303pm (or by appt)
TAs: Xinyuan Cao OH: Tue 24pm, Klaus 3100. Mirabel Reid OH: Wed 122pm, Klaus 2100
What is the basis of intelligence? How can neural networks, artificial or natural, provably lead to perception, learning and cognition? We'll begin by studying a few classics, highlight the gaps and challenges posed by modern artificial models and the brain, and then discuss more recent rigorous proposals. Note that this is a mathematically rigorous course and the focus is on what is provably true related to this topic. Students interested in the latest developments in empirical AI should take other courses.
Prerequisites: algorithms, linear algebra.
Grading:
HW (40%): 46 Problem sets.
Exams (40%): Two inclass exams. No final. No exams for 8803 students.
Project (20%): Each team can choose one of the following options: (a) read a paper and provide an insightful explanation/simpler proof/ generalization (b) prove a conjecture (c) formulate a precise conjecture supported by experimental or theoretical evidence. A list of candidate projects will be provided.
Candidate Project topics are available here.
Readings (under construction!)
 The McCullochPitts Neuron
 PAC Learning
 Winnow and Weighted Majority
 VC dimension
 Support Vector Machines
 Random Projection for Learning
 Boosting
 Random Graphs
 The Regularity Lemma
 Dynamics and Equilibria: the BrouwerKakutani Fixed Point Theorems
 Cell Assemblies: Hebb, D. O. (2005). The organization of behavior: A neuropsychological theory. Psychology press.
 The Assembly Hypothesis
 Generalization in Deep Learning
 Recurrent Neural Networks
 LLMs??!
Schedule

Aug 21, 23. Course overview. The Perceptron Algorithm Notes.

Aug 28, 30. Weighted Majority and Winnow Notes.

Sep 6, 11, 13. PAC learning, Sample Complexity, VC dimension Notes.

Sep 18, 20. Support Vector Machines Notes. Random Projection for Learning Notes.

Sep 25, 27. Boosting, Concentration Inequalities Notes. Random Graphs.

Oct 2. The Regularity Lemma.

Oct 4. Midterm I.

Oct 11. Learning and Games.

Oct 16, 18. Fixed Point Iterations.

Oct 23, 25. Assemblies of Neurons.

Oct 30, Nov 1. Generalization in Neural Networks.

Nov 6, 8. Convolution and Recurrence in Neural Networks.

Nov 13, 15.

Nov 20.

Nov 27. Midterm II.
Nov 29. Language.

Dec 4. Language models and Nextword Prediction.