Generalization Error Bounds for Collaborative Prediction with Low-Rank Matrices

By Nati Srebro, Noga Alon, Tommi S. Jaakkola. 2004

135 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Spectral Regularization Algorithms for Learning Large Incomplete Matrices (2010, background): “Recently [CR08, CT09, KOM09] showed theoretically that under certain assumptions on the entries of the matrix, locations, and proportion of unobserved entries, the true underlying matrix can be recovered within very high accuracy.”
Implicit Regularization in Matrix Factorization (2017, background): “When d < m/n, we understand how the low-rank structure can guarantee generalization [16] and reconstruction [10, 3, 7].”
PAC-Bayesian Analysis of Co-clustering and Beyond (2010, background): “…value decomposition (SVD) (Strang, 2009; Golub and Loan, 1996), non-negative matrix factorization (Lee and Seung, 1999, 2001), low-rank matrix factorization (Srebro t al., 2005a), and maximum margin matrix factorization (Srebro et al., 2005b; Srebro, 2004), thatsatisfy only parts of the list: 5.”
Rank, Trace-Norm and Max-Norm (2005, background): “1, repeating a previous analysis [2]), trace-norm or max-norm (Sections 3.”
Fast global convergence rates of gradient methods for high-dimensional statistical recovery (2010, methodology): “[40, 13, 44, 26, 7]), second-order cone programs (SOCP) for the group Lasso (e.”
NBER WORKING PAPER SERIES MATRIX COMPLETION METHODS FOR CAUSAL PANEL DATA MODELS (2018, unknown): “Independently, a closely related literature has emerged in machine learning and statistics on matrix completion (Srebro et al. (2005); Candès and Recht (2009); Candès and Tao (2010); Keshavan et al. (2010a,b); Gross (2011); Recht (2011); Rohde et al. (2011); Negahban and Wainwright (2011, 2012);…”
Characterizing Implicit Bias in Terms of Optimization Geometry (2018, background): “In particular, gradient descent on U, V is observed to be biased towards low nuclear norm solutions, which in turns ensures generalization (Srebro et al., 2005) and low rank matrix recovery ( ?”
Maximum-Margin Matrix Factorization (2004, background): “Although this is the best (up to log factors) that can be expected from scale-sensitive bounds4, taking a combinatorial approach, the dependence on the magnitude of the entries in X (and the margin) can be avoided [9].”
Proposal Scaling Distributed Machine Learning with System and Algorithm Co-design (2016, unknown): “It is well known that adaptively penalizing terms occurring at different frequency can lead to improved generalization performance [128].”
1-Bit Matrix Completion (2012, background): “For example, in [63], agreement is roughly measured via the fraction of predicted signs that are correct, but this can also be extended to other notions of agreement [62].”
DiFacto: Distributed Factorization Machines (2016, background): “It is well known that penalizing terms occurring at different frequency adaptively can lead to improved generalization performance [18].”
A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers (2009, background): “here are a number of eﬃcient algorithms for solving it (e.g., [9, 41, 45, 55, 56]). Let us consider some examples to illustrate applications covered by the model (51). Example 5.(a) Matrix completion [19, 52, 65, 68, 70]: Suppose that one observes a relatively small subset of the entries of a matrix”