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. We will cover, among other things:

1. Submodular function optimization

2. Combinatorial Bandits

3. Linear Programming based first-order methods (e.g., Frank-Wolfe)

4. Feature selection and sparse regression methods

5. Boosting techniques

6. Using ML methods to improve discrete optimization algorithms

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.

Coordinates: The seminar is organized as a block seminar. Usual meeting time is Tuesday from 13.45 to 14.15. First meeting is on 11/3. The other dates will be decided upon later.

Time: Blockseminar

Room: TBA at TU Berlin / potentially online via zoom

Prerequisites: Linear Algebra, Analysis, and Discrete Optimization (ADM I/ADM II)

Registration: via email to Antje Schulz

Office hours: by appointment

Reading material by topic:

Boosting and LP-Boost:

1. Arora, Sanjeev, Elad Hazan, and Satyen Kale. "The Multiplicative Weights Update Method: a Meta-Algorithm and Applications." Theory of Computing 8.1 (2012): 121-164. (Note: a CS overview of multiplicative weights and the regret bound used to derive the simple boosting algorithm)

2. Freund, Yoav, and Robert E. Schapire. "A desicion-theoretic generalization of on-line learning and an application to boosting." European conference on computational learning theory. Springer, Berlin, Heidelberg, 1995. (Note: the original boosting paper)

3. Freund, Yoav, Robert Schapire, and Naoki Abe. "A short introduction to boosting." Journal-Japanese Society For Artificial Intelligence 14.771-780 (1999): 1612. (Note: quick overview of boosting)

4. Demiriz, Ayhan, Kristin P. Bennett, and John Shawe-Taylor. "Linear programming boosting via column generation." Machine Learning 46.1 (2002): 225-254. (Note: the LP boost paper)

5. Goldberg, Noam, and Jonathan Eckstein. "Boosting classifiers with tightened l0-relaxation penalties." Proceedings of the 27th International Conference on Machine Learning (ICML-10). 2010.

6. Benjamin, Arthur T. "Sensible rules for remembering duals—the SOB method." SIAM review 37.1 (1995): 85-87. (Note: great read for a simple rule how to dualize an LP)

Reinforcement Learning:

1. Sutton, Richard S, and Barto, Andrew G. "Introduction to reinforcement learning." Cambridge: MIT Press, 1998. (Note: The new 2017 version is available online here)

2. Mnih, Volodymyr, et al. “Human-level control through deep reinforcement learning.” Nature 518.7540 (2015): 529-533. (Note: The original DQN paper)

3. Ng, Andrew Y., Daishi Harada, and Stuart Russell. "Policy invariance under reward transformations: Theory and application to reward shaping." ICML. Vol. 99. 1999. (Note: Reward Shaping)

4. Dayan, Peter, and Yael Niv. "Reinforcement learning: the good, the bad and the ugly." Current opinion in neurobiology 18.2 (2008): 185-196.

5. Jaakkola, Tommi, Michael I. Jordan, and Satinder P. Singh. "Convergence of stochastic iterative dynamic programming algorithms." Advances in neural information processing systems. 1994. (Note: Proof of Q-learning convergence)

Online Convex Optimization:

1. Hazan, Elad. "Introduction to online convex optimization." Foundations and Trends® in Optimization 2.3-4 (2016): 157-325. (online version)

2. Nemirovski, Arkadi, et al. "Robust stochastic approximation approach to stochastic programming." SIAM Journal on optimization 19.4 (2009): 1574-1609.

3. Ho-Nguyen, Nam, and Fatma Kılınç-Karzan. The role of flexibility in structure-based acceleration for online convex optimization. Technical report, August 2016. (online version)

Submodular Function Maximization:

1. Krause, Andreas, and Daniel Golovin. "Submodular function maximization." (2014): 71-104. (online version)

2. Minoux, Michel. "Accelerated greedy algorithms for maximizing submodular set functions." Optimization techniques. Springer, Berlin, Heidelberg, 1978. 234-243.

3. Badanidiyuru, Ashwinkumar, and Jan Vondrák. "Fast algorithms for maximizing submodular functions." Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2014. (online version)

4. Mirzasoleiman, Baharan, et al. "Lazier Than Lazy Greedy." AAAI. 2015. (online version)

Machine Learning for solving Integer Programs:

1. He He, Hal Daume III, Jason Eisner. "Learning to Search in Branch-and-Bound Algorithms", Advances in neural information processing systems, 3293-3301, 2014. (online version)

2. Elias B. Khalil, Pierre Le Bodic, Le Song, George Nemhauser, Bistra Dilkina. "Learning to Branch in Mixed Integer Programming", Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, 2016. (online version)

3. Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, Le Song, "Learning Combinatorial Optimization Algorithms over Graphs ", Advances in Neural Information Processing Systems, 6351-6361, 2017. (online version)

Online Submodular Function Maximization:

1. Streeter, Matthew, and Daniel Golovin. "An online algorithm for maximizing submodular functions." Carnegie Mellon University Technical report, 2009. (online version)

2. Krause, Andreas, and Daniel Golovin. "Submodular function maximization." (2014): 71-104. (online version)

3. Golovin, Daniel, Andreas Krause, and Matthew Streeter. "Online submodular maximization under a matroid constraint with application to learning assignments." arXiv preprint arXiv:1407.1082 (2014). (online version)

Online Learning:

1. Arora, Sanjeev, Elad Hazan, and Satyen Kale. "The Multiplicative Weights Update Method: a Meta-Algorithm and Applications." Theory of Computing 8.1 (2012): 121-164. (online version)

2. Neu, Gergely. "Explore no more: Improved high-probability regret bounds for non-stochastic bandits." Advances in Neural Information Processing Systems. 2015. (online version)

Sparse Regression:

1. Almuallim, Hussein, and Thomas G. Dietterich. "Learning With Many Irrelevant Features." AAAI. Vol. 91. 1991. (subset selection via FOCUS algorithm) (online version)

2. Chen, Scott Shaobing, David L. Donoho, and Michael A. Saunders. "Atomic decomposition by basis pursuit." SIAM review 43.1 (2001): 129-159. (online version)

3. Tibshirani, Robert. "Regression shrinkage and selection via the lasso." Journal of the Royal Statistical Society. Series B (Methodological) (1996): 267-288. (online version)

4. Candes, Emmanuel J., Michael B. Wakin, and Stephen P. Boyd. "Enhancing sparsity by reweighted ℓ-1 minimization." Journal of Fourier analysis and applications 14.5-6 (2008): 877-905. (online version)

Inverse Reinforcement Learning:

1. Ng, Andrew Y., and Stuart J. Russell. "Algorithms for inverse reinforcement learning." Icml. 2000. (online version)

2. Abbeel, Pieter, and Andrew Y. Ng. "Apprenticeship learning via inverse reinforcement learning." Proceedings of the twenty-first international conference on Machine learning. ACM, 2004. (online version)

3. Ratliff, Nathan D., J. Andrew Bagnell, and Martin A. Zinkevich. "Maximum margin planning." Proceedings of the 23rd international conference on Machine learning. ACM, 2006. (online version)

Experience Relay:

1. Schaul, Tom, et al. "Prioritized experience replay." arXiv preprint arXiv:1511.05952 (2015). (online version)

2. Lin, Long-Ji. "Self-improving reactive agents based on reinforcement learning, planning and teaching." Machine learning 8.3-4 (1992): 293-321. (online version)

3. Tsitsiklis, J. N., and B. Van Roy. An analysis of temporal-difference learning with function approximationTechnical. Report LIDS-P-2322). Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, 1996. (online version)

Conditional Gradients:

1. Jaggi, Martin. "Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization." ICML (1). 2013. (online version)

2. Lacoste-Julien, Simon, and Martin Jaggi. "On the global linear convergence of Frank-Wolfe optimization variants." Advances in Neural Information Processing Systems. 2015. (online version)

3. Braun, Gábor, Sebastian Pokutta, and Daniel Zink. "Lazifying Conditional Gradient Algorithms." ICML (2017). (online version)

Adversarial Learning:

1. Goodfellow, Ian J., Jonathon Shlens, and Christian Szegedy. "Explaining and harnessing adversarial examples." arXiv preprint arXiv:1412.6572 (2014). (online version)

2. Kurakin, Alexey, Ian Goodfellow, and Samy Bengio. "Adversarial machine learning at scale." arXiv preprint arXiv:1611.01236 (2016). (online version)

3. Papernot, Nicolas, et al. "Practical black-box attacks against machine learning." Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security. ACM, 2017

4. Elsayed, Gamaleldin F., et al. "Adversarial Examples that Fool both Human and Computer Vision." arXiv preprint arXiv:1802.08195 (2018). (online version)

5. Madry, Aleksander, et al. "Towards deep learning models resistant to adversarial attacks." arXiv preprint arXiv:1706.06083 (2017). (online version)

6. Kolter, J. Zico, and Eric Wong. "Provable defenses against adversarial examples via the convex outer adversarial polytope." arXiv preprint arXiv:1711.00851 (2017). (online version)

7. Raghunathan, Aditi, Jacob Steinhardt, and Percy Liang. "Certified defenses against adversarial examples." arXiv preprint arXiv:1801.09344 (2018). (online version)

8. Sinha, Aman, Hongseok Namkoong, and John Duchi. "Certifiable Distributional Robustness with Principled Adversarial Training." arXiv preprint arXiv:1710.10571 (2017). (online version)

9. Tjeng, Vincent, and Russ Tedrake. "Verifying Neural Networks with Mixed Integer Programming." arXiv preprint arXiv:1711.07356 (2017). (online version)

10. Fischetti, Matteo, and Jason Jo. "Deep Neural Networks as 0-1 Mixed Integer Linear Programs: A Feasibility Study." arXiv preprint arXiv:1712.06174 (2017). (online version)