Summary
The course presents various existing optimization techniques for energy minimization for discrete graphical models. In particular, it addresses such topics as combinatorial algorithms, integer linear programs, scalable convex and non-convex optimization and convex duality theory. Graphical models play a role of working examples along the course. The goal of the course is to give a background for analysis of existing, and development of new scalable combinatorial optimization.
Schedule and Information
Venue: Kyiv, Peremogy ave. 37, Building 11 of the NTUU “KPI” Campus, Room 214
Time: 23-27.09.2019:
- 08-30 – 10-05
- 10-25 – 12-00
- 13:30 – 15-50
Table of Contents
- 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 Decomposition Technique
- Min-Cut/Max-Flow Based Inference
- LP Relaxation of Inference Problem as st-Min-Cut Problem
Literature
Text-book: B. Savchynskyy. Discrete Graphical Models – An Optimization Perspective
Video of Lectures: Winter Term 2018/19, Heidelberg University
Thanks to Bálint Csanády, for the video recordings. Use the username “optml” when prompted.
- 2018-10-17: Acyclic Graphical Models, Dynamic Programming
- 2018-10-23: Optimization problems, Relaxations, Polytopes
- 2018-10-24: Convexity, Linear Programs
- 2018-10-30: Integer Linear Programs, Integer Hull, LP relaxation
- 2018-10-31: MAP-inference as ILP
- 2018-11-06: Convex Analysis: extended value functions, convex functions
- 2018-11-07: Convex Analysis: subgradient and piecewise linear functions
- 2018-11-13: Lagrange duality
- 2018-11-14: Lagrange relaxation of ILPs, reparametrization, optimality conditions
- 2018-11-20: Lagrange duality for MAP-inference: reparametrization, dual rounding
- 2018-11-27: Arc-consistency, relaxation labeling, arc-consistency for acyclic graphs
- 2018-11-28: Basics of convex optimization
- 2018-12-05: ICM, block ICM, dual subgradient methods
- 2018-12-11: Min-sum diffusion. Empirical comparison of algorithms
- 2018-12-12 (01): Dynamic programming as anisotropic diffusion, TRW-S
- 2018-12-12 (02): Lagrange decomposition: grid-graph, general graphs, primal problem
- 2018-12-18: Equivalence of all acyclic decompositions. Maximization of decomposition-based dual: sub-gradient and subproblem averaging.
- 2018-12-19: TRW-S/SRMP Algorithm derivation. Comparison of algorithms based on different decompositions
- 2019-01-08: Sub-modularity. Submodular energy minimization
- 2019-01-09: Binary and multilabel submodular energy minimization as min-cut
- 2019-01-15: Move-making algorithms
- 2019-01-16: Binary LP relaxation as min-cut
- 2019-01-22: Persistency, Fusion Moves. Comparison to dual algorithms