Statistical and Computational Rates in Graph Logistic Regression

Quentin Berthet, Nicolai Baldin
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:2719-2730, 2020.

Abstract

We consider the problem of graph logistic regression, 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 analyzed in a high-dimensional regime under a structural assumption. The optimal statistical rates are derived, and an estimator based on penalized maximum likelihood is shown to attain it. The algorithmic aspects of this problem are also studied, and optimal rates under computational constraints are derived, and shown to differ from the information-theoretic rates - under a complexity assumption.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-berthet20a, title = {Statistical and Computational Rates in Graph Logistic Regression}, author = {Berthet, Quentin and Baldin, Nicolai}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {2719--2730}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/berthet20a/berthet20a.pdf}, url = {https://proceedings.mlr.press/v108/berthet20a.html}, abstract = {We consider the problem of graph logistic regression, 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 analyzed in a high-dimensional regime under a structural assumption. The optimal statistical rates are derived, and an estimator based on penalized maximum likelihood is shown to attain it. The algorithmic aspects of this problem are also studied, and optimal rates under computational constraints are derived, and shown to differ from the information-theoretic rates - under a complexity assumption.} }
Endnote
%0 Conference Paper %T Statistical and Computational Rates in Graph Logistic Regression %A Quentin Berthet %A Nicolai Baldin %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-berthet20a %I PMLR %P 2719--2730 %U https://proceedings.mlr.press/v108/berthet20a.html %V 108 %X We consider the problem of graph logistic regression, 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 analyzed in a high-dimensional regime under a structural assumption. The optimal statistical rates are derived, and an estimator based on penalized maximum likelihood is shown to attain it. The algorithmic aspects of this problem are also studied, and optimal rates under computational constraints are derived, and shown to differ from the information-theoretic rates - under a complexity assumption.
APA
Berthet, Q. & Baldin, N.. (2020). Statistical and Computational Rates in Graph Logistic Regression. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:2719-2730 Available from https://proceedings.mlr.press/v108/berthet20a.html.

Related Material