# Bogdan Savchynskyy presents Overview of first-order optimization methods for the LP relaxation of discrete energy minimization

On 2019-10-23 15:00
at G205, Karlovo náměstí 13, Praha 2

We will review a majority of existing solvers for the local polytope relaxation

of the discrete energy minimization problem. The problem is also known as

maximum a posteriori/maximum probable explanation inference in undirected

graphical models. The relaxation is often referred to as " linear programming

(LP) relaxation". We will consider several dual formulations of the relaxation

and treat them as unconstrained large-scale concave problems. The core of our

talk is a comparison of approximate solvers for this problem. These solvers are

based on subgradient, proximal point, smoothing and block-coordinate descent

techniques. Based on the comparison, we will conclude about key properties of

an "ideal" (so far non-existing) solver. We assume that our comparison and

conclusions can be useful for developing efficient optimization techniques for

convex relaxations of other large-scale optimization problems.

of the discrete energy minimization problem. The problem is also known as

maximum a posteriori/maximum probable explanation inference in undirected

graphical models. The relaxation is often referred to as " linear programming

(LP) relaxation". We will consider several dual formulations of the relaxation

and treat them as unconstrained large-scale concave problems. The core of our

talk is a comparison of approximate solvers for this problem. These solvers are

based on subgradient, proximal point, smoothing and block-coordinate descent

techniques. Based on the comparison, we will conclude about key properties of

an "ideal" (so far non-existing) solver. We assume that our comparison and

conclusions can be useful for developing efficient optimization techniques for

convex relaxations of other large-scale optimization problems.