DROPS

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.19

Greedy Minimization of Weakly Supermodular Set Functions

Authors: Edo Liberty and Maxim Sviridenko

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

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.

Cite as

Edo Liberty and Maxim Sviridenko. Greedy Minimization of Weakly Supermodular Set Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 19:1-19:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{liberty_et_al:LIPIcs.APPROX-RANDOM.2017.19,
  author =	{Liberty, Edo and Sviridenko, Maxim},
  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 =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.19},
  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}
}

Search Results

Documents authored by Liberty, Edo

Greedy Minimization of Weakly Supermodular Set Functions

Abstract

Cite as

Thanks for your feedback!

Could not send message