License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.19
URN: urn:nbn:de:0030-drops-75682
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7568/
Go to the corresponding LIPIcs Volume Portal

Liberty, Edo ; Sviridenko, Maxim

Greedy Minimization of Weakly Supermodular Set Functions

pdf-format:
LIPIcs-APPROX-RANDOM-2017-19.pdf (0.4 MB)

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 non-negative and non-increasing, 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:1--19:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7568},
  URN =		{urn:nbn:de:0030-drops-75682},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.19},
  annote =	{Keywords: Weak Supermodularity, Greedy Algorithms, Machine Learning, Data Mining}
}

Keywords: Weak Supermodularity, Greedy Algorithms, Machine Learning, Data Mining
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Issue Date: 2017
Date of publication: 11.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI