On Approximation Guarantees for Greedy Low Rank Optimization
This work addresses matrix estimation for researchers in optimization and machine learning, offering incremental improvements through novel analysis.
The paper tackles the problem of greedy low rank matrix estimation by providing new approximation guarantees under restricted strong convexity and smoothness assumptions, and it shows empirical comparisons with baselines on real-world problems.
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 also provide statistical recovery guarantees. Finally, we present empirical comparison of greedy estimation with established baselines on two important real-world problems.