Optimal link prediction with matrix logistic regression
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Link PredictionPredictionregressionSimilar Papers 제목 키워드 기반
High-dimensional logistic regression with missing data: Imputation, regularization, and universality
We study high-dimensional, ridge-regularized logistic regression in a setting in which the covariates may be missing or corrupted by additive noise. When both the covariates and the additive corruptions are independent a…
ImputationPredictionregressionA Minimax Lower Bound for Low-Rank Matrix-Variate Logistic Regression
This paper considers the problem of matrix-variate logistic regression. It derives the fundamental error threshold on estimating low-rank coefficient matrices in the logistic regression problem by obtaining a lower bound…
regressionRobust Logistic Regression and Classification
We consider logistic regression with arbitrary outliers in the covariate matrix. We propose a new robust logistic regression algorithm, called RoLR, that estimates the parameter through a simple linear programming proced…
Binary ClassificationClassificationGeneral ClassificationregressionImplicit Bias and Fast Convergence Rates for Self-attention
We study the fundamental optimization principles of self-attention, the defining mechanism of transformers, by analyzing the implicit bias of gradient-based optimizers in training a self-attention layer with a linear dec…
Binary ClassificationDecoderregressionMatrix Factorization for Inferring Associations and Missing Links
Missing link prediction is a method for network analysis, with applications in recommender systems, biology, social sciences, cybersecurity, information retrieval, and Artificial Intelligence (AI) reasoning in Knowledge …
Dimensionality ReductionInformation RetrievalKnowledge GraphsLink Prediction+3