Special joint LIG-VERIMAG Seminar - Prof. Seffi Naor and Prof. Monaldo Mastrolilli

Prof. Seffi Naor - Multi-label Classification with Pairwise Relations

Motivated by applications in multi-label learning, we introduce the metric multi-labeling problem. The objective here is to classify objects by labels while optimizing a linear cost function of both assignment costs and separation costs, which are deduced from pairwise relations between objects. Each object can be classified by multiple labels, which may have either positive or negative costs, thus departing from previous works, e.g., metric labeling.. The metric multi-labeling problem is NP-hard, and we tackle it by formulating an integer program capturing the deviation from a benchmark representing an "ideal" labeling. This approach, reminiscent of the notion of regret in online learning, allows us to cope with the possible negativity of the labeling costs. We develop a tight 2-approximation algorithm for metric multi-labeling by using an approach that distorts the optimal likelihood values computed by our linear programming relaxation. We extend the results to settings where the number of labels that can be given to an object is bounded.

Joint work with Shahar Chen, Dotan Di Castro, Zohar Karnin, Liane Lewin-Eytan, and Roy Schwartz.

---

Prof. Monaldo Mastrolilli - High Degree Sum of Squares Proofs/Hierarchy for 0/1 Problems

The Lasserre/Sum-of-Squares (SOS) hierarchy is a systematic procedure for constructing a sequence of increasingly tight semidefinite relaxations. It is known that the hierarchy converges to the 0/1 polytope in n levels and captures the convex relaxations used in the best available approximation algorithms for a wide variety of optimization problems. In this talk I will give a gentle introduction of the SOS framework for 0/1 problems from a more general point of view. I will point it out that this more general definition is needed for certain class of problems, it removes some of the weakness of the standard SOS approach.