Dr. Bogdan Savchynskyy, Prof. Dr. Carsten Rother, WiSe 2021/22
Attention! The first seminar will take place on Wednesday, October 27 and NOT October 20. Please make sure to participate!
This seminar belongs to the Master in Physics (specialization Computational Physics, code "MVJC"), Master of Applied Informatics (code "IS") as well as Master Mathematics (code "MS") programs, but is also open for students of Scientific Computing and anyone interested.Credits: 2 / 4 / 6 CP depending on course of study
Summary
Machine learning techniques are tightly coupled with optimization methods. Many techniques become practical only if there exists a supporting optimization tool.
In the seminar we will discuss a number of recent articles on combinatorial optimization with applications in computer vision and machine learning.
The topic of this semester is again
Neural Networks meet Combinatorial Optimization
In particular, we will consider methods for
- training parameters of combinatorial optimization algorithms with the machine learning techniques,
- combinatorial optimization based loss-functions for deep learning
General Information
Please register for the seminar in Müsli. The seminar will be held online in MS Teams . The seminar will take place in presence, the preparation discussion - over MS Teams. All links will be send per email via Müsli.
The first seminar will take place on Wednesday, October 20 October 27 at 16:00. Please make sure to participate!
- Seminar: Wed, 16:00 – 18:00 in Mathematikon B (Berliner Str. 43), SR B128
Ring the door bell labelled "HCI am IWR" to be let in. The seminar room is on the 3rd floor. - Credits: 2 / 4 / 6 CP depending on course of study, see LSF
Seminar Repository:
Here. Password will be sent by email via Muesli.Papers to Choose from:
See overwiew slides for the papers here. See also the presentation video.
For a quick overview of the general problem these slides could be also helpful. A large collection of slides for the leading black-box differentiation method can be found here.
[1] M. Vlastelica, A. Paulus, V. Musil, G. Martius, M. Rolínek, Differentiation of Blackbox Combinatorial Solvers, ICLR 2020 (see also slides here).
[3] M. Rolínek, P. Swoboda, D. Zietlow, V. Musil, A. Paulus, G. Martius, Deep Graph Matching via Blackbox Differentiation, ECCV 2020
[4] A. Paulus, M. Rolínek, V. Musil, B. Amos, G. Martius, Fit the right NP-Hard Problem: End-to-end Learning of Integer Programming Constraints, NeurIPS 2020, LMCA
[6] A. Ferber, B. Wilder, B. Dilkina, M. Tambe, MIPaaL: Mixed Integer Program as a Layer, AAAI 2020
[7] Q. Berthet, M. Blondel, O. Teboul, M. Cuturi, J. Vert, F. Bach, Learning with Differentiable Perturbed Optimizers, NeurIPS 2020
[8] X. Gao, H. Zhang, A. Panahi, T. Arodz, Differentiable Combinatorial Losses through Generalized Gradients of Linear Programs, ArXiv 2020
[10] J. Mandi, E. Demirovic, P. Stuckey, T. Guns, Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems, AAAI 2020
[12] T. Gal, Rim Multiparametric Linear Programming, J. Management Science, 1975
[13] R. Freund, Postoptimal Analysis of a Linear Program Under Simultaneous Changes in Matrix Coefficients, 1984
[14] D. De Wolf,, Generalized Derivatives of the Optimal Value of a Linear Program with Respect to Matrix Coefficients, European J. of Operational Research, 2000
[16] A. Agrawal, B. Amos, S. Barratt, Differentiable Convex Optimization Layers, NeurIPS 2019
[17] M. Blondel, O. Teboul, Q. Berthet, J. Djolonga, Fast Differentiable Sorting and Ranking, ICML 2020
[18] R. Kleiman, D. Page AUC_\mu: A Performance Metric for Multi-Class Machine Learning Models, NeurIPS, 2019
[19] K. Ataman, W. Street, Y. Zhang, Learning to Rank by Maximizing AUC with Linear Programming, IJCNNP, 2006
[20] I. Tsochantaridis, T. Joachims, T. Hofmann, Y. Altun, Large Margin Methods for Structured and Interdependent Output Variables, JMLR, 2005
[21] A. Sadat, M. Ren, A. Pokrovsky, Y. Lin, E. Yumer, R. Urtasun, Jointly Learnable Behavior and Trajectory Planning for Self-Driving Vehicles, IROS 2019
[24] X. Chen, Y. Zhang, C. Reisinger, L. Song, Understanding Deep Architecture with Reasoning Layer, NeurIPS 2020
[25] P. Wang, P. Donti, B. Wilder, Z. Kolter, SATNet: Bridging Deep Learning and Logical Reasoning Using a Differentiable Satisfiability Solver, ICML, 2019
[27] P. Swoboda, C. Rother, H.A. Alhaija, D. Kainmuller, B. Savchynskyy, A Study of Langrangean Decompositions and Dual Ascent Solvers for Graph Matching, CVPR, 2016
[28] A. Hornakova, R. Henschel, B. Rosenhahn, P. Swoboda, Lifted Disjoint Paths with Application in Multiple Object Tracking, ICML 2020
[29] J. Thapper, S. Živný, The Complexity of finite-valued CSPs, J ACM, 2016
[31] Knöbelreiter, P., Reinbacher, C., Shekhovtsov, A., and Pock, T. End-to-end training of hybrid CNN-CRF models for stereo. CVPR 2017
[32] Paulus, A., Rolínek, M., Musil, V., Amos, B., Martius, G. CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints. ICML 2021