Discrete Optimization and Machine Learning
Sebastian Pokutta (WiSe 2021 / Seminar)
Both Machine Learning methods as well as Discrete Optimization methods are important tools in many real-world applications. In this course we will primarily study the interplay of integer programming and, more broadly, discrete optimization methods and machine learning.The format of the course is strongly research-oriented requiring active participation of the students. The course will be a mix of traditional lectures, student presentation, discussions, and project work. In the first few weeks in-class projects will be defined.
Prerequisites: Linear Algebra, Analysis, and Discrete Optimization (ADM I/ADM II)
Registration: via email to Antje Schulz
Office hours: by appointment
Organization & Requirements:
Students choose one of the papers below to work on. Up to 2 students can work on the same paper. Students are expected to individually
Write a report (5 page minimum in Latex) about the paper and the contribution from the students themselves.
During the semester, present their plans for the final report and presentation in a shorter 5 minute presentation.
Give a final presentation to present their findings (details discussed in the first meeting).
Timeline:
04.11.2021, 10:00 a.m. (Berlin time): Seminar outline and start of paper selection time period
12.11.2021, 11:59 p.m. (Berlin time): Paper selection deadline (send your desired paper to Elias Wirth. Assignment is first come, first served. Papers that are no longer available are crossed out.)
16.12.2021, 10:00 a.m. (Berlin time): 5 minute presentations
09.02.2022, 11:59 p.m. (Berlin time): Report submission deadline (send your reports to Elias Wirth)
10.02.2022, 08:00 a.m. (Berlin time): Final presentations
11.02.2022, 08:00 a.m. (Berlin time): Final presentations
Reading material by topic (crossed out papers are no longer available):
Adversarial Learning
Taylan Cemgil, Sumedh Ghaisas, Krishnamurthy Dvijotham & Pushmeet Kohli. “Adversarially Robust Representations with Smooth Encoders”, ICLR 2020 Conference Blind Submission (link) (2/2)
Bandits
Sébastien Bubeck and Nicolò Cesa-Bianchi (2012), "Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems", Foundations and Trends® in Machine Learning: Vol. 5: No. 1, pp 1-122. Online Learning (link) (1/2)
Boosting
Peter Bartlett.Yoav Freund.Wee Sun Lee.Robert E. Schapire."Boosting the margin: a new explanation for the effectiveness of voting methods."Ann. Statist.26(5) 1651 - 1686, 1998. (link) ((1/2)
Convex Optimization
Allen-Zhu, Zeyuan and Orecchia, Lorenzo. "Nearly linear-time packing and covering LP solvers" Mathematical Programming Volume 175,307–353(2019) (link)
Francis Bach. On the Effectiveness of Richardson Extrapolation in Machine Learning. 2020. hal-02470950 (link)
Deep Learning
Wagner, A.Z., 2021. Constructions in combinatorics via neural networks. arXiv preprint arXiv:2104.14516. (link) (2/2)
Dynamic Programming
Fang He, Jie Yang, Meng Li, "Vehicle scheduling under stochastic trip times: An approximate dynamic programming approach", Transportation Research Part C: Emerging Technologies, Volume 96, 2018, Pages 144-159 (link) (2/2)
Parallel Numerical Linear Algebra
J. L. Greathouse and M. Daga, "Efficient Sparse Matrix-Vector Multiplication on GPUs Using the CSR Storage Format," SC '14: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2014, pp. 769-780, doi: 10.1109/SC.2014.68. (link) (1/2)
Reinforcement Learning
Etheve, M., Alès, Z., Bissuel, C., Juan, O. and Kedad-Sidhoum, S., 2020, September. Reinforcement learning for variable selection in a branch and bound algorithm. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research (pp. 176-185). Springer, Cham. (link) (2/2)
Robust Optimization
Bertsimas, Dimitris, and Bart Van Parys. “Bootstrap robust prescriptive analytics.” Mathematical Programming (2021): 1-40. (link) (2/2)
Semidefinite Programming
Alp Yurtsever, Joel A Tropp, Olivier Fercoq, Madeleine Udell, Volkan Cevher. “Scalable Semidefinite Programming” SIAM Journal on Mathematics of Data Science, 2021 (link)