Liberty, Edo ;
Sviridenko, Maxim
Greedy Minimization of Weakly Supermodular Set Functions
Abstract
Many problems in data mining and unsupervised machine learning take the form of minimizing a set function with cardinality constraints. More explicitly, denote by [n] the set {1,...,n} and let f(S) be a function from 2^[n] to R+. Our goal is to minimize f(S) subject to S <= k. These problems include clustering and covering problems as well as sparse regression, matrix approximation problems and many others. These combinatorial problems are hard to minimize in general. Finding good (e.g. constant factor) approximate solutions for them requires significant sophistication and highly specialized algorithms.
In this paper we analyze the behavior of the greedy algorithm to all of these problems. We start by claiming that the functions above are special. A trivial observation is that they are nonnegative and nonincreasing, that is, f(S) >= f(union(S,T)) >= 0 for any S and T. This immediately shows that expanding solution sets is (at least potentially) beneficial in terms of reducing the function value. But, monotonicity is not sufficient to ensure that any number of greedy extensions of a given solution would significantly reduce the objective function.
BibTeX  Entry
@InProceedings{liberty_et_al:LIPIcs:2017:7568,
author = {Edo Liberty and Maxim Sviridenko},
title = {{Greedy Minimization of Weakly Supermodular Set Functions}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {19:119:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770446},
ISSN = {18688969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7568},
URN = {urn:nbn:de:0030drops75682},
doi = {10.4230/LIPIcs.APPROXRANDOM.2017.19},
annote = {Keywords: Weak Supermodularity, Greedy Algorithms, Machine Learning, Data Mining}
}
11.08.2017
Keywords: 

Weak Supermodularity, Greedy Algorithms, Machine Learning, Data Mining 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Issue date: 

2017 
Date of publication: 

11.08.2017 