Name
Abstract | ||
|---|---|---|
This paper defines weak-$\alpha$-supermodularity for set functions. Many optimization objectives in machine learning and data mining seek to minimize such functions under cardinality constrains. We prove that such problems benefit from a greedy extension phase. Explicitly, let $S^*$ be the optimal set of cardinality $k$ that minimizes $f$ and let $S_0$ be an initial solution such that $f(S_0)/f(S^*) \le \rho$. Then, a greedy extension $S \supset S_0$ of size $|S| \le |S_0| + \lceil \alpha k \ln(\rho/\varepsilon) \rceil$ yields $f(S)/f(S^*) \le 1+\varepsilon$. As example usages of this framework we give new bicriteria results for $k$-means, sparse regression, and columns subset selection. |
Year | Venue | Field |
|---|---|---|
2015 | CoRR | Set function,Discrete mathematics,Combinatorics,Cardinality,Minification,Sparse regression,Mathematics |
DocType | Volume | Citations |
Journal | abs/1502.06528 | 5 |
PageRank | References | Authors |
0.44 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christos Boutsidis | 1 | 610 | 33.37 |
| Edo Liberty | 2 | 5 | 1.12 |
| Maxim Sviridenko | 3 | 5 | 3.82 |