Greedy Column Subset Selection: New Bounds and Distributed Algorithms
Venue
ICML (2016) (to appear)
Publication Year
2016
Authors
Aditya Bhaskara, Afshin Rostamizadeh, Jason Altschuler, Morteza Zadimoghaddam, Thomas Fu, Vahab Mirrokni
BibTeX
Abstract
The problem of matrix column subset selection has recently attracted a large body
of research, with feature selection serving as one obvious and important
application. Among the techniques that have been applied to solve this problem, the
greedy algorithm has been shown to be quite effective in practice. However, our
theoretical guarantees on its performance have not been ex- plored thoroughly,
especially in a distributed set- ting. In this paper, we study the greedy algorithm
for the column subset selection problem from a theoretical and empirical
perspective and show its effectiveness in a distributed setting. In par- ticular,
we provide an improved approximation guarantee for the greedy algorithm, and
present the first distributed implementation of this algo- rithm with provable
approximation factors. We use the idea of randomized composable core- sets,
developed recently in the context of sub- modular maximization. Finally, we
validate the effectiveness of this distributed algorithm via an empirical study.
