Published on Tue Sep 06 2011

On Partial Opimality by Auxiliary Submodular Problems

Alexander Shekhovtsov, Vaclav Hlavac

In this work, we prove several relations between three different energy minimizing techniques. We show that methods of Ivan Kovtun, which build auxiliary submodular problems, fulfill this sufficient condition. In the case of two labels, LP relaxation provides optimal partial.assignment, known as persistency.

0
0
0
Abstract

In this work, we prove several relations between three different energy minimization techniques. A recently proposed methods for determining a provably optimal partial assignment of variables by Ivan Kovtun (IK), the linear programming relaxation approach (LP) and the popular expansion move algorithm by Yuri Boykov. We propose a novel sufficient condition of optimal partial assignment, which is based on LP relaxation and called LP-autarky. We show that methods of Kovtun, which build auxiliary submodular problems, fulfill this sufficient condition. The following link is thus established: LP relaxation cannot be tightened by IK. For non-submodular problems this is a non-trivial result. In the case of two labels, LP relaxation provides optimal partial assignment, known as persistency, which, as we show, dominates IK. Relating IK with expansion move, we show that the set of fixed points of expansion move with any "truncation" rule for the initial problem and the problem restricted by one-vs-all method of IK would coincide -- i.e. expansion move cannot be improved by this method. In the case of two labels, expansion move with a particular truncation rule coincide with one-vs-all method.

Mon Jun 01 2020
Machine Learning
From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models
Submodular functions have been studied extensively in machine learning and data mining. The use of these functions for probabilistic modeling has received surprisingly little attention so far. We firstly propose the Generalized Multilinear Extension. Then, we introduce a block-coordinate ascent algorithm.
0
0
0
Tue Dec 31 2019
Machine Learning
Submodular Function Minimization and Polarity
Using polarity, we give an outer polyhedral approximation for the epigraph of set functions. Computational experiments show that the outer approximations can be effective as cutting planes for submodular as well as non-submodular set function minimization problems.
0
0
0
Fri Apr 19 2019
Machine Learning
Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications
It is generally believed that submodular functions may only be optimized under the non-negativity assumption . In this paper, we show that once , where is monotone and is non-negative modular, strong approximation guarantees may be obtained.
0
0
0
Thu Jul 13 2017
Artificial Intelligence
Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy?
A randomized version of the greedy algorithm achieves an approximation ratio of Extra open brace or missing close brace1 + 1/\gamma)^{-2 for the maximization of a weakly submodular function subject to a general matroid constraint. To the best of our knowledge, this is the first algorithm with a.non-trivial approximation guarantee for maximizing aweakly sub modular function.
0
0
0
Tue Sep 29 2020
Machine Learning
Simultaneous Greedys: A Swiss Army Knife for Constrained Submodular Maximization
SimultaneousGreedys is a deterministic algorithm for submodular maximization. It maintains solutions and greedily updates them in a simultaneous fashion, rather than a sequential one. The technique is flexible enough to incorporate the intersections of additional knapsack constraints, while retaining similar guarantees.
0
0
0
Tue Sep 10 2013
Machine Learning
Maximizing submodular functions using probabilistic graphical models
The problem of maximizing submodular functions is known to be NP-hard. Several numerically efficient local search techniques with approximation guarantees are available. We propose a novel convex relaxation which is based on the relationship between sub modular functions, entropies and probabilistic graphical models.
0
0
0