Engineering a Generic Solver for Convex Optimization Problems

• Applicant: Professor Dr.-Ing. Sören Laue
• Subject Area: Theoretical Computer Science
• Term: from 2014 to 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 253965656

• Final Report Year: 2020

Final Report Abstract

Ziel dieses Projekts war es einen Solver Generator zu entwickeln, der basierend auf der mathematischen Beschreibung eines Optmierungsproblems, automatisch einen Solver für diese Klasse von Optimierungsproblemen erzeugt. Dafür haben wir eine einfache und allgemeine Theorie für das Berechnen von Ableitungen für Matrix- und Tensorfunktionen entwickelt, die darüber hinaus auch noch praktisch nutzbar ist. Obwohl dieses ein sehr fundamentales Problem ist, existierte eine solche Theorie bisher nicht. Der sich daraus ergebende Algorithmus ist zentraler Bestandteil dieses Projekts. Da wir der Meinung waren, dass diese Methode auch für andere Wissenschaftler von Interesse ist, haben wir sie unter www.MatrixCalculus.org als ein Webtool öffentlich zugänglich gemacht. Die Ausdrücke für Ableitungen von vektor- und matrixwertigen Funktionen, die unser Ansatz erzeugt, können im Vergleich zu anderen aktuellen Methoden bis zu drei Größenordnungen schneller ausgewertet werden. Mit diesem Ansatz kann das von uns in diesem Projekt entwickelte Modellierungsmodul kompakte Ausdrücke für Gradienten, Jacobi- und Hesse-Matrizen generieren, die von generischen Solvern für Optimierungsprobleme genutzt werden können. In einem Proof of Concept konnten wir den Solver Generator GENO (GENeric Optimization) entwickeln. Die automatisch erzeugten Solver zeigen großes Potential für erhebliche Effizienzsteigerungen im Vergleich zum aktuellen Stand der Forschung. Eine online Version ist unter www.geno-project.org nutzbar.

Publications

• Deducing individual driving preferences for user-aware navigation. International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL), 2016
  Stefan Funke, Sören Laue, Sabine Storandt
  (See online at https://doi.org/10.1145/2996913.2997004)
• Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees. Symposium on Experimental Algorithms (SEA), 2017
  Stefan Funke, Sören Laue, Sabine Storandt
  (See online at https://doi.org/10.4230/LIPIcs.SEA.2017.18)
• Computing Higher Order Derivatives of Matrix and Tensor Expressions. Advances in Neural Information Processing Systems (NeurIPS), 2018
  Sören Laue, Matthias Mitterreiter, Joachim Giesen
  
• Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. IEEE/ACM Trans. Netw. 26(2): 920-933, 2018
  Thomas Bläsius, Tobias Friedrich, Anton Krohmer, Sören Laue
  (See online at https://doi.org/10.1109/TNET.2018.2810186)
• Dynamic pseudo-time warping of complex single-cell trajectories. International Conference on Research in Computational Molecular Biology (RECOMB), 2019
  Van Hoan Do, Mislav Blazevic, Pablo Monteagudo, Luka Borozan, Khaled Elbassioni, Sören Laue, Francisca Rojas Ringeling, Domagoj Matijevic and Stefan Canzar
  (See online at https://doi.org/10.1101/522672)
• GENO – GENeric Optimization for Classical Machine Learning. Advances in Neural Information Processing Systems (NeurIPS), 2019
  Sören Laue, Matthias Mitterreiter, Joaching Giesen
  
• MatrixCalculus.org – Computing Derivatives of Matrix and Tensor Expressions. European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML), 2019
  Sören Laue, Matthias Mitterreiter, Joaching Giesen
  (See online at https://doi.org/10.1007/978-3-030-46133-1_48)
• On the Equivalence of Forward Mode Automatic Differentiation and Symbolic Differentiation. arXiv, 2019
  Sören Laue
  
• Using Benson’s Algorithm for Regularization Parameter Tracking. Conference on Artificial Intelligence (AAAI), 2019
  Joachim Giesen, Sören Laue, Andreas Löhne, Christopher Schneider
  (See online at https://doi.org/10.1609/aaai.v33i01.33013689)
• Visualization Support for Developing a Matrix Calculus Algorithm: A Case Study. EG/VGTC Conference on Visualization (EUROVIS), 2019
  Joachim Giesen, Julien Klaus, Sören Laue, Ferdinand Schreck
  (See online at https://doi.org/10.1111/cgf.13694)
• A Simple and Efficient Tensor Calculus. Conference on Artificial Intelligence (AAAI), 2020
  Sören Laue, Matthias Mitterreiter, Joaching Giesen
  (See online at https://doi.org/10.1609/aaai.v34i04.5881)
• GENO – Optimization for Classical Machine Learning Made Fast and Easy. Conference on Artificial Intelligence (AAAI), 2020
  Sören Laue, Matthias Mitterreiter, Joaching Giesen
  (See online at https://doi.org/10.1609/aaai.v34i09.7097)