Skip to main content
Calendar
Introductory lectures
- Apr 4
-
- Introduction to class
- Lecture
-
- Apr 6
-
- Machine learning crash-course
- Lecture
-
- Apr 11
-
- Integer programming and SAT
- Lecture
-
Graph neural networks
- Apr 13
-
- Graph neural networks (GNNs)
- Lecture
-
- Apr 18
-
- GNNs for graph algorithms
- Discussion
-
-
- Reading: Veličković, Petar, et al. “Neural execution of graph algorithms.” ICLR’20. [link]
- Apr 20
-
- Survey of GNNs for combinatorial optimization
- Discussion
-
-
- Reading: Section 3.3 of Cappart, Quentin, et al. “Combinatorial optimization and reasoning with graph neural networks.” arXiv’21 [link]
Integer programming (IP) and SAT
- Apr 25
-
- Algorithm configuration for IP and SAT
- Discussion
-
-
- Reading: Sections 1-3.2, 4.1, 5.1.1, 5.1.3, 5.2-6.2 of Hutter, Frank, et al. “ParamILS: an automatic algorithm configuration framework.” JAIR 36 (2009): 267-306. [link]
- Apr 27
-
- Portfolio-based algorithm selection for SAT
- Discussion
-
-
- Reading: Sections 1-3.3, 4.1, 4.3 of Xu, Lin, et al. “SATzilla: portfolio-based algorithm selection for SAT.” JAIR 32 (2008): 565-606. [link]
Markov decision processes (MDPs) and reinforcement learning (RL)
- May 2
-
- MDPs and RL
- Lecture
-
- May 4
-
- MDPs, GNNs, and integer programming
- Discussion
-
-
- Reading: Gasse, Maxime, et al. “Exact combinatorial optimization with graph convolutional neural networks.” NeurIPS’19. [link]
- May 9
-
- RL for combinatorial optimization
- Discussion
-
-
- Reading: Dai, Hanjun, et al. “Learning combinatorial optimization algorithms over graphs.” NeurIPS’17. [link]
Midterm presentations
- May 11
-
- Midterm project presentations
- Project
- Students will give short presentations on papers related to their final projects.
- May 16
- No class
Statistical guarantees and online learning
- May 18
-
- Theoretical machine learning
- Lecture
-
- May 23
-
- Statistical guarantees and online algorithm configuration
- Discussion
-
-
- Reading: Sections 1-3.3.3, 4-5 of Gupta, Rishi, and Tim Roughgarden. “A PAC approach to application-specific algorithm selection.” ITCS’16. [link]
Algorithms with predictions
- May 25
-
- Algorithms with predictions 1
- Discussion
-
-
- Reading: Purohit, Manish, Zoya Svitkina, and Ravi Kumar. “Improving online algorithms via ML predictions.” NeurIPS’18. [link]
- May 30
-
- Algorithms with predictions 2
- Discussion
-
-
- Reading: Hsu, Chen-Yu, et al. “Learning-Based Frequency Estimation Algorithms.”
ICLR’19. [link]
Learned data structures
- June 1
-
- Learned data structures
- Discussion
-
-
- Reading: Sections 1-3.7.1 and 5 of Kraska, Tim, et al. “The case for learned index structures.” SIGMOD’18. [link]
-
- Optional reading: Mitzenmacher, Michael. “A model for learned bloom filters and optimizing by sandwiching.” NeurIPS’18. [link]
Final project presentations
- June 6
-
- Final project presentations
- Project