### Optimization for Machine Learning

**Lecturer:**Dr. Bogdan Savchynskyy

**Assistant:**Alexander Kirillov

The
course consists of lectures and practical exercises
and concentrates on optimization techniques for machine learning tasks,
such as inference and learning for graphical models. The course
contains 3 parts: first, we briefly review basic convex optimization
techniques widely used in machine learning. The second part is
devoted to inference problem for graphical models: we consider a number
of existing algorithms, show their connection and their analysis from
optimization point of view. In the final third part we consider the
parameter's learning of graphical models, both probabilistic and
discriminative. |

News!

**- 8.06**Next Monday, June 13, the lecture will in the Room APB-E040 instead of E007! See the lecture plan below for details.

**-18.04**On April 18 there might be a lecture in the Room APB-E040 instead of exercises!

**-17.03**The first lecture will be held on April 4 in Room APB-E040 !

Lectures: Monday 13:00-14:30, Room APB-E007 (except the first lecture, which will be held in E040), Wednesday, 11:10 - 12:40, Room APB-E001, Start: April 4, 2016

Exercises: Monday 13:00-14:30, Room APB-E040, Start: April 18

Prerequisites: Good knowledge of mathematics (linear algebra, analysis)

Credits: 3/1/0, oral exam. Enrolment: jExam . Attendees: max. 60

Note: Lectures are given in English.

Script: PDF-Dowload

Software installation readme: Download

### Content:

L01. APB-E040**04.04**Introduction. Graphical models and their applications. Inference problem. Statistical and probabilistic meaning. [slides]

L02. APB-E001

**06.04**(Integer) Linear programs. Polyhedral viewpoint. Marginal polytope. [slides] [annotated slides]

L03. APB-E007

**11.04**Local polytope. ILP formulation, LP relaxation. [slides]

L04. APB-E001

**11.04**Dynamic programming for inference in graphical models [slides]

---

*E01. APB-E040*[exercise-sheet] [results-table] [supplement]

**18.04**Use of general LP and ILP solvers for inference in graphical models.L05. APB-E001

**20.04**Convex functions. Lagrange dual problem. [slides-1] [slides-2]

L06. APB-E007

**25.04**Lagrange dual for the local polytope relaxation. [slides-1] [slides-2]

L07. APB-E001

**27.04**KKT conditions, arc consistency, relaxation labeling algorithm [slides-1]

*---E02. APB-E040*[exercise-sheet] [results-table] [supplement]

**2.05**Lagrange Dual to the LP Relaxation. Dual LP (TRWS) vs. Naive SolverL08. APB-E001

**04.05**Basics of convex optimization: gradient and sub-gradient methods. [slides-1] [slides-2]

L09. APB-E007

**09.05**Basics of convex optimization: sub-gradient method and block-coordinate descent. Min-sum Diffusion. [slides-1]

L10. APB-E001

**11.05**ICM Algorithm. Lagrangian (Dual) Decomposition. Tree agreement. [slides-1] [slides-2]

---

*E03. APB-E040*[exercise-sheet] [results-table] [supplement]

**23.05**Coordinate descent/ascent and sub-gradient methods for energy minimization.L11. APB-E001

**25.05**General subgraph-wise decompositions. Relation to Lagrange dual. Equivalence of all acyclic decomposition. [slides]

L12. APB-E007

**30.05**Block-coordinate ascent for decomposition-based dual. TRW-S. [slides]

**1.06**Dies Academicus

---

*E04. APB-E040*[exercise-sheet] [supplement]

**06.06**Empirical comparison of algorithms based on different acyclic decompositionsL13. APB-E001

**8.06**Sub-modularity. Energy minimization as a min-cut problem. [slides] [annotated slides]

L13. APB-E040

**13.06**Min-cut based inference algorithms: alpha-expansion, alpha-beta-swap. Multilabel submodular problems. [slides]

L14. APB-E001

**15.06**Binary LP relaxation as min-cut. [slides]

L15. APB-E007

**20.06**Fusion Moves. Partial optimality. Inference algorithm selection. [slides] [ICCV2015-Tutorial]

L16. APB-E001

**22.06**Discriminative Learning. Structured SVM. Loss-augmented inference. [script]

---

*E05. APB-E040*[exercise-sheet] [results-table]

**27.06**Min-cut based algorithms**29.06**No lecture.

L17. APB-E007

**04.07**Algorithms for Struct-SVM. Subgradient-based methods. [script]

L18. APB-E001

**06.07**Algorithms for Struct-SVM. Stochastic subgradient and cutting plane methods. [script]

---

*E05. APB-E040*

**27.06**Use this time to finish your unfinished exercisesL18. APB-E001

**13.07**Outlook. What we have learned [slides]

image links: crops, lake, tsukubaR, tsukubaL, tsukubaTrueDisp