Core-Sets, Sparse Greedy Approximation, and the Frank-Wolfe Algorithm

The problem of maximizing a concave function f(x) in a simplex S can be solved approximately by a simple greedy algorithm, that for given k can find a point x sub (k) on a k-dimensional face such that f(x sub (k)) >- f(x sub *) - O (1/k), where f(x sub *) is the maximum value of f in S. This algorithm and analysis were known before, and related to problems of statistics and m achine learning , such as boosting, regression, and density mixture estimation. In other work, the existence of epsilon-core-sets was shown for the minimum enclosing ball problem, by means of a simple greedy algorithm, and similar greedy algorithms were described for other enclosure problems. Here these results are unified in a common framework of convex optimization, stronger convergence results are reviewed, and several core-set bounds are generalized or strengthened.