Greedy Column Subset Selection: New Bounds and Distributed Algorithms

Jason Altschuler, Aditya Bhaskara, Gang Fu, Vahab Mirrokni, Afshin Rostamizadeh, Morteza Zadimoghaddam
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2539-2548, 2016.

Abstract

The problem of 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, theoretical guarantees on its performance have not been explored thoroughly, especially in a distributed setting. 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 particular, we provide an improved approximation guarantee for the greedy algorithm which we show is tight up to a constant factor, and present the first distributed implementation with provable approximation factors. We use the idea of randomized composable core-sets, developed recently in the context of submodular maximization. Finally, we validate the effectiveness of this distributed algorithm via an empirical study.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-altschuler16, title = {Greedy Column Subset Selection: New Bounds and Distributed Algorithms}, author = {Altschuler, Jason and Bhaskara, Aditya and Fu, Gang and Mirrokni, Vahab and Rostamizadeh, Afshin and Zadimoghaddam, Morteza}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2539--2548}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/altschuler16.pdf}, url = {https://proceedings.mlr.press/v48/altschuler16.html}, abstract = {The problem of 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, theoretical guarantees on its performance have not been explored thoroughly, especially in a distributed setting. 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 particular, we provide an improved approximation guarantee for the greedy algorithm which we show is tight up to a constant factor, and present the first distributed implementation with provable approximation factors. We use the idea of randomized composable core-sets, developed recently in the context of submodular maximization. Finally, we validate the effectiveness of this distributed algorithm via an empirical study.} }
Endnote
%0 Conference Paper %T Greedy Column Subset Selection: New Bounds and Distributed Algorithms %A Jason Altschuler %A Aditya Bhaskara %A Gang Fu %A Vahab Mirrokni %A Afshin Rostamizadeh %A Morteza Zadimoghaddam %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-altschuler16 %I PMLR %P 2539--2548 %U https://proceedings.mlr.press/v48/altschuler16.html %V 48 %X The problem of 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, theoretical guarantees on its performance have not been explored thoroughly, especially in a distributed setting. 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 particular, we provide an improved approximation guarantee for the greedy algorithm which we show is tight up to a constant factor, and present the first distributed implementation with provable approximation factors. We use the idea of randomized composable core-sets, developed recently in the context of submodular maximization. Finally, we validate the effectiveness of this distributed algorithm via an empirical study.
RIS
TY - CPAPER TI - Greedy Column Subset Selection: New Bounds and Distributed Algorithms AU - Jason Altschuler AU - Aditya Bhaskara AU - Gang Fu AU - Vahab Mirrokni AU - Afshin Rostamizadeh AU - Morteza Zadimoghaddam BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-altschuler16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2539 EP - 2548 L1 - http://proceedings.mlr.press/v48/altschuler16.pdf UR - https://proceedings.mlr.press/v48/altschuler16.html AB - The problem of 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, theoretical guarantees on its performance have not been explored thoroughly, especially in a distributed setting. 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 particular, we provide an improved approximation guarantee for the greedy algorithm which we show is tight up to a constant factor, and present the first distributed implementation with provable approximation factors. We use the idea of randomized composable core-sets, developed recently in the context of submodular maximization. Finally, we validate the effectiveness of this distributed algorithm via an empirical study. ER -
APA
Altschuler, J., Bhaskara, A., Fu, G., Mirrokni, V., Rostamizadeh, A. & Zadimoghaddam, M.. (2016). Greedy Column Subset Selection: New Bounds and Distributed Algorithms. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:2539-2548 Available from https://proceedings.mlr.press/v48/altschuler16.html.

Related Material