On Approximation Guarantees for Greedy Low Rank Optimization
arXiv:1703.02721
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 also provide statistical recovery guarantees. Finally, we present empirical comparison of greedy estimation with established baselines on two important real-world problems.
References in corpus (6)
- Distributed Representations of Words and Phrases and their Compositionality
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Estimation of high-dimensional low-rank matrices
- Approximation and learning by greedy algorithms
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
- Forward - Backward Greedy Algorithms for Atomic Norm Regularization
Cited by in corpus (8)
- Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning
- Batch greedy maximization of non-submodular functions: Guarantees and applications to experimental design
- Multi-objective Evolutionary Algorithms are Still Good: Maximizing Monotone Approximately Submodular Minus Modular Functions
- Robust Principal Component Analysis with Non-Sparse Errors
- On Maximization of Weakly Modular Functions: Guarantees of Multi-stage Algorithms, Tractability, and Hardness
- Guarantees of Stochastic Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraint
- Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression
- Sparse Optimization on General Atomic Sets: Greedy and Forward-Backward Algorithms