Discrete Optimization and Machine Learning

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

1. Taylan Cemgil, Sumedh Ghaisas, Krishnamurthy Dvijotham & Pushmeet Kohli. “Adversarially Robust Representations with Smooth Encoders”, ICLR 2020 Conference Blind Submission (link) (2/2)

Bandits

1. 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

1. 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

1. Allen-Zhu, Zeyuan and Orecchia, Lorenzo. "Nearly linear-time packing and covering LP solvers" Mathematical Programming Volume 175,307–353(2019) (link)

2. Francis Bach. On the Effectiveness of Richardson Extrapolation in Machine Learning. 2020. hal-02470950 (link)

Deep Learning

1. Wagner, A.Z., 2021. Constructions in combinatorics via neural networks. arXiv preprint arXiv:2104.14516. (link)  (2/2)

Dynamic Programming

1. 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

1. 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

1. 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

1. Bertsimas, Dimitris, and Bart Van Parys. “Bootstrap robust prescriptive analytics.” Mathematical Programming (2021): 1-40. (link) (2/2)

Semidefinite Programming

1. Alp Yurtsever, Joel A Tropp, Olivier Fercoq, Madeleine Udell, Volkan Cevher. “Scalable Semidefinite Programming” SIAM Journal on Mathematics of Data Science, 2021 (link)