Optimization for Machine Learning

Dr. Bogdan Savchynskyy, WiSe 2020/21


The lecture and exercises will be held online! See the information about registration below.


This lecture belongs to the Master in Physics (specialisation Computational Physics, code "MVSpec"), Master of Applied Informatics (code "IOML") as well as Master Mathematics programs, but is also open for students of Scientific Computing and anyone interested.

The course presents various existing optimization techniques for such important machine learning tasks, as inference and learning for graphical models and neural networks. In particular, it addresses such topics as combinatorial algorithms, integer linear programs, scalable convex and non-convex optimization and convex duality theory. Graphical models and neural networks play a role of working examples along the course. The goal of the course is to give a strong background for analysis of existing, and development of new scalable optimization techniques for machine learning problems.

Schedule and Information

The lectures and exercises will be given in English.
The lecture will be given synchron online via MS Teams, the link to join the lecture Team will be send via email.
Attention: To be able to join the lecture you must enable MS Teams here. Please do it ASAP, your request may take several days.

  • Lecture: Tue, 14:00 – 16:00, the first lecture will be given on November 3
  • Lecture: Wed, 14:00 – 16:00
  • Exercises: Wed, 09:00 – 11:00, the first exercise will take place on November 11

Contact for lectures: Dr. Bogdan Savchynskyy
Contact for exercises: Stefan Haller

The seminar Combinatorial Optimization in Computer Vision and Machine Learning complements this lecture by taking a closer look at recent results and developments. We highly recommend it to all students interested in the topic.


Please register for the course in Müsli. The link to join the lecture will be send via email to the registered students only.
To be able to join the lecture you must enable MS Teams here. Please do it ASAP, your request may take several days.

Course Material and Exercises

Will be uploaded here. The password was sent via email.

Please submit your assignments to the tutor via e-mail. You can use the online checker to verify the programming tasks of your assignments before submitting.

Table of Contents

I Inference in Graphical Models

  • Acyclic Graphical Models. Dynamic Programming
  • Background: Basics of Linear Programs and Their Geometry
  • Inference in Graphical Models as Integer Linear Program
  • Background: Basics of Convex Analysis and Convex Duality
  • Duality of the LP Relaxation of Inference Problem
  • Background: Basics of Convex Optimization
  • Sub-Gradient and Block-Coordinate Ascent for Inference in Graphical Models
  • Lagrangian (Dual) Decomposition
  • Min-Cut/Max-Flow Based Inference
  • LP Relaxation of Inference Problem as st-Min-Cut Problem
  • Summary: Inference Algorithm Selection

II Joint Learning of Graphical Models and Neural Networks

  • Structured Risk Minimization for Graphical Models
  • CRF+CNN Models: Joint Training of Graphical Models and Neural Networks.


Text-book: B. Savchynskyy. Discrete Graphical Models - An Optimization Perspective