On Approximation Guarantees for Greedy Low Rank Optimization
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
Text
Khanna et al. "On Approximation Guarantees for Greedy Low Rank Optimization." International Conference on Machine Learning, 2017.Markdown
[Khanna et al. "On Approximation Guarantees for Greedy Low Rank Optimization." International Conference on Machine Learning, 2017.](https://mlanthology.org/icml/2017/khanna2017icml-approximation/)BibTeX
@inproceedings{khanna2017icml-approximation,
title = {{On Approximation Guarantees for Greedy Low Rank Optimization}},
author = {Khanna, Rajiv and Elenberg, Ethan R. and Dimakis, Alexandros G. and Ghosh, Joydeep and Negahban, Sahand},
booktitle = {International Conference on Machine Learning},
year = {2017},
pages = {1837-1846},
volume = {70},
url = {https://mlanthology.org/icml/2017/khanna2017icml-approximation/}
}