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

On 2019-10-23 15:00: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.
Responsible person: Petr Pošík