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 Elias Wirth

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: 

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

• 15.11.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.)

• 13.12.2022, 10:00 a.m. (Berlin time): 5-minute presentations in room MA 608

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

• 30.01.2023, 10:00 a.m. (Berlin time): Final presentations in room MA 608

• 31.01.2023, 10:00 a.m. (Berlin time): Final presentations in room MA 608

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

Algorithm Configuration

1. Balcan, Sandholm, Vitercik, 2020. "Learning to Optimize Computational Resources: Frugal Training with Generalization Guarantees" (https://arxiv.org/abs/1905.10819)

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. (http://sbubeck.com/SurveyBCB12.pdf) (1/2)

(Convex) Optimization

1. Simon Lacoste-Julien, Martin Jaggi, Mark Schmidt, Patrick Pletscher, 2013.  Block-Coordinate Frank-Wolfe Optimization for Structural SVMs. http://proceedings.mlr.press/v28/lacoste-julien13.pdf (2/2)

2. Bolte, J., Le, T., and Silveti-Falls, T. 2021. Nonsmooth Implicit Differentiation for Machine-Learning and Optimization. In NeurIPS 2021 (pp. 13537-13549) (https://proceedings.neurips.cc/paper/2021/hash/70afbf2259b4449d8ae1429e054df1b1-Abstract.html) (1/2)

3. M. Reuther and T. Schlechte, “Optimization of rolling stock rotations,” in Handbook of Optimization in the Railway Industry, pp. 213–241, Springer, 2018. (https://link.springer.com/book/10.1007/978-3-319-72153-8) (1/2)

4. Allen-Zhu, Zeyuan, and Lorenzo Orecchia. "Linear coupling: An ultimate unification of gradient and mirror descent." (https://arxiv.org/abs/1407.1537) (1/2)

Computer Vision

1. Alaifari et al., 2022. “Localized adversarial artifacts for compressed sensing MRI.” arXiv pre-print. (https://arxiv.org/pdf/2206.05289.pdf) (1/2)

Deep Learning

1. Hooker et al. (2019): What Do Compressed Deep Neural Networks Forget? (https://arxiv.org/abs/1911.05248) (2/2)

Distributionally Robust Optimization

1. Tay et al. (2022): Efficient Distributionally Robust Bayesian Optimization with Worst-case Sensitivity (https://proceedings.mlr.press/v162/tay22a/tay22a.pdf)

Feature Transformation And Extraction

1. Roi Livni, David Lehavi, Sagi Schein, Hila Nachliely, Shai Shalev-Shwartz, Amir Globerson Proceedings of the 30th International Conference on Machine Learning, PMLR 28(1):597-605, 2013. (http://proceedings.mlr.press/v28/livni13.html) (2/2)

Integer Programming

1. Zeren Huang et al. "Learning to Select Cuts for Efficient Mixed-Integer Programming" (https://arxiv.org/abs/2105.13645) (2/2)

2. D-optimal Data Fusion: Exact and Approximation Algorithms (https://arxiv.org/abs/2208.03589) (1/2)

Optimal Transport

1. Optimal Tensor Transport (https://www.aaai.org/AAAI22Papers/AAAI-12812.KerdoncuffT.pdf) (2/2)

Quantum Physics And Data Science

1. Koopman analysis of quantum systems (https://arxiv.org/abs/2201.12062) (0/2)