The Optimal Sample Complexity of Matrix Completion with Hierarchical Similarity Graphs.
Adel M. ElmahdyJunhyung AhnSoheil MohajerChangho SuhPublished in: ISIT (2022)
Keyphrases
- sample complexity
- matrix completion
- theoretical analysis
- learning problems
- upper bound
- low rank
- learning algorithm
- generalization error
- active learning
- similarity measure
- supervised learning
- optimal solution
- lower bound
- dynamic programming
- sample size
- training examples
- singular values
- machine learning
- machine learning algorithms
- cross validation
- missing values
- matrix factorization
- special case
- unsupervised learning
- graph mining
- protein interaction networks