Schedule

Introduction

Apr 1
Introduction to class
Slides

Pointer networks for the traveling salesman problem (TSP)

Apr 3
TSP and recurrent neural networks (RNNs)
Lecture notes
Supplemental reading:
  • CS244N notes on sequence-to-sequence models and attention mechanisms [link]
Apr 8
Pointer networks for TSP
Lecture notes
Supplemental reading:
  • Chapter 17 of CS229 notes on policy gradient [link]
  • Vinyals, Oriol, et al. “Pointer networks.” NeurIPS’15. [link]
  • Bello, Irwan, et al. “Neural combinatorial optimization with reinforcement learning.” Workshop track of ICLR’17. [link]
Apr 10
Pointer networks for TSP, continued
Lecture notes
Supplemental reading:
  • Chapter 2.2.2 of CS261 notes on TSP approximation algorithms [link]
  • Bello, Irwan, et al. “Neural combinatorial optimization with reinforcement learning.” Workshop track of ICLR’17. [link]

Graph neural networks (GNNs)

Apr 15
Graphs and graph algorithms
Lecture notes
Supplemental reading:
  • Section 1.1 of CS161 notes on graphs [link]
  • Chapter 35.1 of Cormen, Thomas H., et al.’s “Introduction to algorithms” on minimum vertex cover [link]
  • Section 2.1.1 of Anupam Gupta’s lecture notes on maximum cut [link]
Apr 17
GNNs
Lecture notes
Supplemental reading:
  • Chapter 13 of Bishop’s “Deep learning: foundations and concepts” [link 1] [link 2]
Apr 22
Reinforcement learning (Q-learning)
Lecture notes
Supplemental reading:
  • Lecture notes from UC Berkeley on MDPs [link]
  • Lecture notes from UC Berkeley on reinforcement learning [link]
Apr 24
GNNs as greedy heuristics
Lecture notes
Supplemental reading:
  • Dai, Hanjun, et al. “Learning combinatorial optimization algorithms over graphs.” NeurIPS’17. [link]
  • Ahn, Sungsoo, Younggyo Seo, and Jinwoo Shin. “Learning what to defer for maximum independent sets.” ICML’20. [link]
Apr 29
Neural algorithmic reasoning
Lecture notes
Supplemental reading:
  • Veličković, Petar, et al. “Neural execution of graph algorithms.” ICLR’20. [link]
  • Ibarz, Borja, et al. “A generalist neural algorithmic learner.” LoG’22. [link]

Integer programming (IP)

May 1
IP formulations
Lecture notes
May 6
IP solvers
Lecture notes
May 8
Guest lecture by Madeleine Udell
Supplemental reading:
  • AhmadiTeshnizi, Ali, Wenzhi Gao, and Madeleine Udell. “OptiMUS: Optimization modeling using MIP solvers and large language models.” arXiv’23. [link]
May 13
GNNs for IP
Supplemental reading:
  • Gasse, Maxime, et al. “Exact combinatorial optimization with graph convolutional neural networks.” NeurIPS’19. [link]
  • Selsam, Daniel, et al. “Learning a SAT solver from single-bit supervision.” ICLR’19. [link]
May 15
Algorithm configuration
Supplemental reading:
  • Hutter, Frank, et al. “ParamILS: an automatic algorithm configuration framework.” Journal of Artificial Intelligence Research 36 (2009): 267-306. [link]

Theoretical guarantees

May 20
Guarantees for algorithm configuration
Supplemental reading:
  • Gupta, Rishi, and Tim Roughgarden. “A PAC approach to application-specific algorithm selection.” ITCS’16. [link]
  • Balcan, Maria-Florina. “Data-driven algorithm design.” In Beyond the worst-case analysis of algorithms, edited by Tim Roughgarden. Cambridge University Press, ‘21. [link]
May 22
Algorithms with predictions
Supplemental reading:
  • Purohit, Manish, et al. “Improving online algorithms via ML predictions.” NeurIPS’18. [link]

Transformers

May 29
Transformers overview
June 3
Transformers as algorithms
Supplemental reading:
  • Garg, Shivam, et al. “What can transformers learn in-context? a case study of simple function classes.” NeurIPS’22. [link]

Final project presentations

June 5
Final project presentations