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: 

• 28.04.2022, 11:00 a.m. (Berlin time) in Room MA 608: Seminar outline

• 09.05.2022, 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.)

• 24.05.2022, 11:00 a.m. (Berlin time): 5 minute presentations in room MA 608

• 05.07.2022, 11:59 p.m. (Berlin time): Report submission deadline (send your reports to Elias Wirth)

• 06.07.2022, 10:00 a.m. (Berlin time): Final presentations

• 07.07.2022, 10:00 a.m. (Berlin time): Final presentations

Reading material by topic (crossed out papers are no longer available):

Adversarial Bandits

1. Sébastien Bubeck and Nicolò Cesa-Bianchi (2012), "Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems" (Only Chapter 3), Foundations and Trends® in Machine Learning: Vol. 5: No. 1, pp 1-122  (Link) (2/2)

Combinatorial Optimization

1. Razborov, 2007, Flag Algebras. In The Journal of Symbolic Logic. (Link) (0/2)

Computer Vision:

1. Awasthi et al., 2021, Adversarial Robustness Across Representation Spaces. In CVPR. (Link) (2/2)

Constrained Optimization

1. Kotary et al., 2021, Learning Hard Optimization Problems: A Data Generation Perspective in NeurIPS Proceedings. (Link) (2/2)

Convex Optimization

1. Adil, M., Madani, R., Tavakkol, S. and Davoudi, A., 2022. A First-Order Numerical Algorithm without Matrix Operations. (Link) (1/2)

2. Allen-Zhu, Zeyuan, and Lorenzo Orecchia. "Nearly linear-time packing and covering LP solvers." Mathematical Programming 175.1 (2019): 307-353. (Link) (0/2)

3. Duchi, J.C., Jordan, M.I., Wainwright, M.J. and Wibisono, A., 2013. Optimal rates for zero-order convex optimization: the power of two function evaluations. (Link) (0/2)

4. Jambulapati, Sidford, and Tian. 2019, June A Direct \tilde{O}(1/epsilon) Iteration Parallel Algorithm for Optimal Transport. In NeurIPS 2019  (Link) (1/2)

5. J. Bolte and E. Pauwels (2021): Curiosities and counterexamples in smooth convex optimization. in Mathematical Programming, series A.  (Link) (0/2)

Distributionally Robust Optimization

1. Residuals-based distributionally robust optimization with covariate information by Rohit Kannan, Güzin Bayraksan, James R. Luedtke (Link)  (0/2)

Integer Programming

1. Wang et al. (2019): Optimization models for high-speed train unit routing problems (Link) (2/2)

Neural Networks

1. Hooker et al. (2019): What Do Compressed Deep Neural Networks Forget? (Link) (2/2)