Optimal link prediction with matrix logistic regression
arXiv:1803.07054
Abstract
We consider the problem of link prediction, based on partial observation of a large network, and on side information associated to its vertices. The generative model is formulated as a matrix logistic regression. The performance of the model is analysed in a high-dimensional regime under a structural assumption. The minimax rate for the Frobenius-norm risk is established and a combinatorial estimator based on the penalised maximum likelihood approach is shown to achieve it. Furthermore, it is shown that this rate cannot be attained by any (randomised) algorithm computable in polynomial time under a computational complexity assumption.
References in corpus (19)
- Simultaneous analysis of Lasso and Dantzig selector
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- A Survey on Metric Learning for Feature Vectors and Structured Data
- Estimation of high-dimensional low-rank matrices
- SLOPE - Adaptive variable selection via convex optimization
- Optimal detection of sparse principal components in high dimension
- Rate-optimal graphon estimation
- Incoherence-Optimal Matrix Completion
- Computational and Statistical Tradeoffs via Convex Relaxation
- Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
- Nonparametric graphon estimation
- Computational barriers in minimax submatrix detection
- Sparse CCA: Adaptive Estimation and Computational Barriers
- Information-theoretic thresholds for community detection in sparse networks
- Information-theoretic thresholds for community detection in sparse networks
- A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recovery
- Estimating network edge probabilities by neighborhood smoothing
- Generalized High-Dimensional Trace Regression via Nuclear Norm Regularization
- Tensor SVD: Statistical and Computational Limits