CS4540/CS8803: (Is there) A(n Algorithmic) Theory of (Artificial) Intelligence(?)

Fall 2023. MW: 9:30-10:45, Mason 5134

Santosh Vempala, Klaus 2222, Office hour: Mon 1:30-3pm (or by appt)
TAs: Xinyuan Cao OH: Tue 2-4pm, Klaus 3100. Mirabel Reid OH: Wed 12-2pm, 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%): 4-6 Problem sets.
Exams (40%): Two in-class 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!)
  1. The McCulloch-Pitts Neuron
  2. PAC Learning
  3. Winnow and Weighted Majority
  4. VC dimension
  5. Support Vector Machines
  6. Random Projection for Learning
  7. Boosting
  8. Random Graphs
  9. The Regularity Lemma
  10. Dynamics and Equilibria: the Brouwer-Kakutani Fixed Point Theorems
  11. Learning Finite Automata
  12. Cell Assemblies: Hebb, D. O. The organization of behavior: A neuropsychological theory. Psychology press.
  13. The Assembly Hypothesis
  14. Generalization in Deep Learning
  15. Recurrent Neural Networks
  16. LLMs??!
Schedule