On Approximation Guarantees for Greedy Low Rank Optimization

Rajiv Khanna, Ethan R. Elenberg, Alexandros G. Dimakis, Joydeep Ghosh, Sahand Negahban
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:1837-1846, 2017.

Abstract

We provide new approximation guarantees for greedy low rank matrix estimation under standard assumptions of restricted strong convexity and smoothness. Our novel analysis also uncovers previously unknown connections between the low rank estimation and combinatorial optimization, so much so that our bounds are reminiscent of corresponding approximation bounds in submodular maximization. Additionally, we provide also provide statistical recovery guarantees. Finally, we present empirical comparison of greedy estimation with established baselines on two important real-world problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-khanna17a, title = {On Approximation Guarantees for Greedy Low Rank Optimization}, author = {Rajiv Khanna and Ethan R. Elenberg and Alexandros G. Dimakis and Joydeep Ghosh and Sahand Negahban}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {1837--1846}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/khanna17a/khanna17a.pdf}, url = {https://proceedings.mlr.press/v70/khanna17a.html}, abstract = {We provide new approximation guarantees for greedy low rank matrix estimation under standard assumptions of restricted strong convexity and smoothness. Our novel analysis also uncovers previously unknown connections between the low rank estimation and combinatorial optimization, so much so that our bounds are reminiscent of corresponding approximation bounds in submodular maximization. Additionally, we provide also provide statistical recovery guarantees. Finally, we present empirical comparison of greedy estimation with established baselines on two important real-world problems.} }
Endnote
%0 Conference Paper %T On Approximation Guarantees for Greedy Low Rank Optimization %A Rajiv Khanna %A Ethan R. Elenberg %A Alexandros G. Dimakis %A Joydeep Ghosh %A Sahand Negahban %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-khanna17a %I PMLR %P 1837--1846 %U https://proceedings.mlr.press/v70/khanna17a.html %V 70 %X We provide new approximation guarantees for greedy low rank matrix estimation under standard assumptions of restricted strong convexity and smoothness. Our novel analysis also uncovers previously unknown connections between the low rank estimation and combinatorial optimization, so much so that our bounds are reminiscent of corresponding approximation bounds in submodular maximization. Additionally, we provide also provide statistical recovery guarantees. Finally, we present empirical comparison of greedy estimation with established baselines on two important real-world problems.
APA
Khanna, R., Elenberg, E.R., Dimakis, A.G., Ghosh, J. & Negahban, S.. (2017). On Approximation Guarantees for Greedy Low Rank Optimization. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:1837-1846 Available from https://proceedings.mlr.press/v70/khanna17a.html.

Related Material