Iterative Collaborative Filtering for Sparse Matrix Estimation

References

• Abbe E, Sandon C (2015a) Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. Proc. IEEE 56th Annual Sympos. on Foundations of Computer Science, vol. 56 (IEEE, New York), 670–688.Google Scholar
• Abbe E, Sandon C (2015b) Recovering communities in the general stochastic block model without knowing the parameters. Adv. Neural Inform. Processing Systems 28:676–684.Google Scholar
• Abbe E, Sandon C (2016) Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic bp, and the information-computation gap. Preprint, submitted December 30, 2015, revised on September 15, 2016, https://arxiv.org/abs/1512.09080.Google Scholar
• Abbe E, Fan J, Wang K, Zhong Y, et al. (2020) Entrywise eigenvector analysis of random matrices with low expected rank. Ann. Statist. 48(3):1452–1474.Crossref, Google Scholar
• Bordenave C, Lelarge M, Massoulié L (2015) Non-backtracking spectrum of random graphs: Community detection and non-regular Ramanujan graphs. Proc. IEEE 56th Annual Sympos. Foundations Computer Sci. (IEEE, New York), 1347–1357.Google Scholar
• Borgs C, Chayes J, Smith A (2015) Private graphon estimation for sparse graphs. Adv. Neural Inform. Processing Systems 28:1369–1377.Google Scholar
• Borgs C, Chayes JT, Cohn H, Ganguly S (2021) Consistent nonparametric estimation for heavy-tailed sparse graphs. Ann. Statist. 49(4):1904–1930.Google Scholar
• Borgs C, Chayes JT, Cohn H, Holden N (2017a) Sparse exchangeable graphs and their limits via graphon processes. J. Machine Learn. Res. 18(1):7740–7810.Google Scholar
• Borgs C, Chayes JT, Cohn H, Zhao Y (2018) An Lp theory of sparse graph convergence II: Ld convergence, quotients, and right convergence. Ann. Probab. 46(1):337–396.Google Scholar
• Borgs C, Chayes JT, Cohn H, Zhao Y (2019) An Lp theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions. Trans. Amer. Math. Soc. 372(5): 3019–3062.Google Scholar
• Borgs C, Chayes J, Lee CE, Shah D (2017b) Thy friend is my friend: Iterative collaborative filtering for sparse matrix estimation. Guyon I, Luxburg UV, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Advances in Neural Information Processing Systems (Curran Associates, Inc.), 4715–4726.Google Scholar
• Borgs C, Chayes JT, Lovász L, Sós VT, Vesztergombi K (2008) Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Adv. Math. 219(6):1801–1851.Crossref, Google Scholar
• Cai C, Li G, Chi Y, Poor HV, Chen Y (2021) Subspace estimation from unbalanced and incomplete data matrices: l2,∞ statistical guarantees. Ann. Statist. 49(2):944–967.Google Scholar
• Candes E, Recht B (2009) Exact matrix completion via convex optimization. Comm. ACM 55(6):111–119.Crossref, Google Scholar
• Candes EJ, Plan Y (2010) Matrix completion with noise. Proc. IEEE 98(6):925–936.Crossref, Google Scholar
• Candès EJ, Tao T (2010) The power of convex relaxation: Near-optimal matrix completion. IEEE Trans. Inform. Theory 56(5):2053–2080.Crossref, Google Scholar
• Chatterjee S (2015) Matrix estimation by universal singular value thresholding. Ann. Statist. 43(1):177–214.Crossref, Google Scholar
• Chen Y, Wainwright MJ (2015) Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. Preprint, submitted September 10, 2015, https://arxiv.org/abs/1509.03025.Google Scholar
• Chen Y, Fan J, Ma C, Wang K (2019) Spectral method and regularized MLE are both optimal for top-k ranking. Ann. Statist. 47(4):2204.Crossref, Google Scholar
• Davenport MA, Plan Y, van den Berg E, Wootters M (2014) 1-bit matrix completion. Inform. Inference 3(3):189–223.Crossref, Google Scholar
• Decelle A, Krzakala F, Moore C, Zdeborová L (2011) Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Phys. Rev. E 84:066106.Google Scholar
• Diaconis P, Janson S (2008) Graph limits and exchangeable random graphs. Rendiconti Matematica VII(28):33–61.Google Scholar
• Ding L, Chen Y (2020) Leave-one-out approach for matrix completion: Primal and dual analysis. IEEE Trans. Inform. Theory 66(11):7274–7301.Crossref, Google Scholar
• Gao C, Lu Y, Zhou HH (2015a) Rate-optimal graphon estimation. Ann. Statist. 43(6):2624–2652.Crossref, Google Scholar
• Gautschi W (1962) On inverses of Vandermonde and confluent Vandermonde matrices. Numerical Math. 4(1):117–123.Crossref, Google Scholar
• Goldberg D, Nichols D, Oki BM, Terry D (1992) Using collaborative filtering to weave an information tapestry. Comm. ACM 35(12): 61–70.Google Scholar
• Karrer B, Newman MEJ, Zdeborová L (2014) Percolation on sparse networks. Phys. Rev. Lett. 113:208702.Crossref, Google Scholar
• Keshavan RH, Montanari A, Oh S (2010a) Matrix completion from a few entries. IEEE Trans. Inform. Theory 56(6):2980–2998.Crossref, Google Scholar
• Keshavan RH, Montanari A, Oh S (2010b) Matrix completion from noisy entries. J. Machine Learning Res. 11(July):2057–2078.Google Scholar
• Klopp O, Tsybakov AB, Verzelen N (2015) Oracle inequalities for network models and sparse graphon estimation. Annals Statist.Google Scholar
• Klopp O, Tsybakov AB, Verzelen N (2017) Oracle inequalities for network models and sparse graphon estimation. Ann. Statist. 45(1):316–354.Crossref, Google Scholar
• Koren Y, Bell R (2011) Advances in Collaborative Filtering. Recommender Systems Handbook (Springer US, Boston).Google Scholar
• Krzakala F, Moore C, Mossel E, Neeman J, Sly A, Zdeborová L, Zhang P (2013) Spectral redemption in clustering sparse networks. Proc. National Acad. Sci USA 110(52):20935–20940.Google Scholar
• Lee CE, Li Y, Shah D, Song D (2016) Blind regression: Nonparametric regression for latent variable models via collaborative filtering. Adv. Neural Inform. Processing Systems 29:2155–2163.Google Scholar
• Li Y, Shah D, Song D, Yu CL (2020) Nearest neighbors for matrix estimation interpreted as blind regression for latent variable model. IEEE Trans. Inform. Theory 66(3):1760–1784.Crossref, Google Scholar
• Linden G, Smith B, York J (2003) Amazon.com recommendations: Item-to-item collaborative filtering. IEEE Internet Comput. 7(1):76–80.Crossref, Google Scholar
• Lovász L (2012) Large Networks and Graph Limits, vol. 60 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• Ma C, Wang K, Chi Y, Chen Y (2018) Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. Proc. 35th Internat. Conf. Machine Learn., vol. 80 (PMLR), 3345–3354.Google Scholar
• Massoulié L (2014) Community detection thresholds and the weak Ramanujan property. Proc. 46th Annual ACM Sympos. Theory Computing (ACM, New York), 694–703.Google Scholar
• Mossel E, Neeman J, Sly A (2018) A proof of the block model threshold conjecture. Combinatorica 38:665–708.Google Scholar
• Negahban S, Wainwright MJ (2011) Estimation of (near) low-rank matrices with noise and high-dimensional scaling. Ann. Statist. 39(2):1069–1097.Google Scholar
• Ning X, Desrosiers C, Karypis G (2015) A comprehensive survey of neighborhood-based recommendation methods. Recommender Systems Handbook (Springer US, Boston), 37–76.Crossref, Google Scholar
• Recht B (2011) A simpler approach to matrix completion. J. Machine Learn. Res. 12(December):3413–3430.Google Scholar
• Steurer D, Hopkins S (2017) Efficient Bayesian estimation from few samples: Community detection and related problems. IEEE 58th Annual Sympos. Foundations Comput. Sci. (FOCS, Berkeley, CA), 379–390.Google Scholar
• Udell M, Townsend A (2019) Why are big data matrices approximately low rank? SIAM J. Math. Data Sci. 1(1):144–160.Crossref, Google Scholar
• Veitch V, Roy DM (2015) The class of random graphs arising from exchangeable random measures. Preprint, submitted December 7, 2015, https://arxiv.org/abs/1512.03099.Google Scholar
• Wolfe PJ, Olhede SC (2013) Nonparametric graphon estimation. Preprint, submitted September 23, 2013, https://arxiv.org/abs/1309.5936.Google Scholar
• Xu J (2018) Rates of convergence of spectral methods for graphon estimation. Dy J, Krause A, eds. Proc. 35th Internat. Conf. Machine Learn., vol. 80 (PMLR, Stockholm, Sweden), 5433–5442.Google Scholar
• Xu J, Massoulié L, Lelarge M (2014) Edge label inference in generalized stochastic block models: From spectral theory to impossibility results. Proc. Conf. Learn. Theory, vol. 35 (PMLR), 903–920.Google Scholar
• Zhang Y, Levina E, Zhu J (2017) Estimating network edge probabilities by neighborhood smoothing. Biometrika 104(4):771–783.Google Scholar
• Zhong Y, Boumal N (2018) Near-optimal bounds for phase synchronization. SIAM J. Optim. 28(2):989–1016.Crossref, Google Scholar