Skip to main content Link Expand (external link) Document Search Copy Copied Apr 1 Introduction to class Slides 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] 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] 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 Lecture notes 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 Lecture notes Supplemental reading: Hutter, Frank, et al. “ParamILS: an automatic algorithm configuration framework.” Journal of Artificial Intelligence Research 36 (2009): 267-306. [link] May 20 Guarantees for algorithm configuration Lecture notes 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 Lecture notes Supplemental reading: Purohit, Manish, et al. “Improving online algorithms via ML predictions.” NeurIPS’18. [link] May 29 Transformers overview Lecture notes Supplemental reading: Chapter 12 of Bishop’s “Deep learning: foundations and concepts” [link 1] [link 2] June 3 Beyond discrete optimization: Transformers as algorithms Lecture notes Supplemental reading: Garg, Shivam, et al. “What can transformers learn in-context? A case study of simple function classes.” NeurIPS’22. [link] Akyürek, Ekin, et al. “What learning algorithm is in-context learning? Investigations with linear models.” ICLR’23. [link] Bai, Yu, et al. “Transformers as statisticians: Provable in-context learning with in-context algorithm selection.” NeurIPS’23. [link] June 5 Final project presentations