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
 Learning Finite Automata
 Cell Assemblies: Hebb, D. O. 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.

Oct 2, 11. Random Graphs Notes, Notes.

Oct 4. Midterm I.

Oct 16, 18. Fixed Point Iterations and Nash Equilibrium Notes.

Oct 23. Regularity Lemmas Notes.

Oct 25, 30. Assemblies of Neurons. slides, simulations: small and large.

Nov 1. Angluin's algorithm for learning a Finite Automaton Notes.

Nov 6, 8. Neural Networks: Architecture, Optimization, Generalization Notes.

Nov 13. Rademacher Complexity Notes.

Nov 15. Midterm II

Nov 20. The Complexity of Human Cognitive Processing.

Nov 27, 29. Language

Dec 4. Language models and Nextword Prediction