Optimization for Machine Learning

Dr. Bogdan Savchynskyy, SoSe 2018

Summary

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.
Venue: Mathematikon B (not A!), Berliner Str. 43, 3rd floor, seminar room B128. Simply ring the bell "HCI am IWR" to open the front door.

• Lecture: Tue, 14:00 – 15:30, Mathematikon B, Berliner Str. 43, SR B128
• Lecture: Wed, 11:00 – 12:30, Mathematikon B, Berliner Str. 43, SR B128
• Exercises: Wed, 09:00 – 10:30, Raum: Mathematikon B, Berliner Str. 43, SR B128

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

The seminar Optimization for 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.

Oral Examinations

To get an appointment for the oral examination contact Dr. Bogdan Savchynskyy directly via e-mail.

Exercises

Deadlines for handing in the solutions for the practical exercises.

• deadline 1st exercise sheet: 25.05.2018
• deadline 2nd exercise sheet: 15.06.2018 20.06.2018
• deadline 3rd exercise sheet: 20.07.2018 03.08.2018

Submit your solution via e-mail to stefan.haller(at)iwr.uni-heidelberg(dot)de.

Registration

Please register for the course in Müsli.

Course Material

Lecture notes, slides and exercise sheets are available for download. The download page is regularly kept up to date.

Table of Contents

I 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 Neural Networks

• Overview of Architectures
• Backpropagation Algorithm
• Background: Stochastic Gradient Optimization and its Variants
• Stochastic Gradient for Training Neural Networks

III Structured Learning of Graphical Models

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