Learning partial correlation graphs and graphical models by covariance queries

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Lugosi, Gábor
• dc.contributor.author Truszkowski, Jakub
• dc.contributor.author Velona, Vasiliki
• dc.contributor.author Zwiernik, Piotr
• dc.date.accessioned 2025-11-28T15:26:58Z
• dc.date.available 2025-11-28T15:26:58Z
• dc.date.issued 2021
• dc.date.updated 2025-11-28T15:26:58Z
• dc.description.abstract We study the problem of recovering the structure underlying large Gaussian graphical models or, more generally, partial correlation graphs. In high-dimensional problems it is often too costly to store the entire sample covariance matrix. We propose a new input model in which one can query single entries of the covariance matrix. We prove that it is possible to recover the support of the inverse covariance matrix with low query and computational complexity. Our algorithms work in a regime when this support is represented by tree-like graphs and, more generally, for graphs of small treewidth. Our results demonstrate that for large classes of graphs, the structure of the corresponding partial correlation graphs can be determined much faster than even computing the empirical covariance matrix.
• dc.description.sponsorship GL, VV, and PZ were supported by the Spanish Ministry of Economy and Competitiveness, Grant PGC2018-101643-B-I00 and FEDER, EU. GL and PZ acknowledge the support of "High-dimensional problems in structured probabilistic models - Ayudas Fundación BBVA a Equipos de Investigación Cientifica 2017". GL was supported by "Google Focused Award Algorithms and Learning for AI" and PZ by Beatriu de Pinós grant (BP-2016-00002) and Ramón y Cajal (RYC-2017-22544).
• dc.format.mimetype application/pdf
• dc.identifier.citation Lugosi G, Truszkowski J, Velona V, Zwiernik P. Learning partial correlation graphs and graphical models by covariance queries. J Mach Learn Res. 2021;22(203):1-41
• dc.identifier.issn 1532-4435
• dc.identifier.uri http://hdl.handle.net/10230/72058
• dc.language.iso eng
• dc.publisher MIT Press
• dc.relation.ispartof Journal of Machine Learning Research. 2021;22(203):1-41
• dc.relation.projectID info:eu-repo/grantAgreement/ES/2PE/PGC2018-101643-B-I00
• dc.rights CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.rights.uri http://creativecommons.org/licenses/by/4.0/
• dc.subject.keyword Gaussian graphical models
• dc.subject.keyword Partial correlation graphs
• dc.subject.keyword Structure learning
• dc.subject.keyword High-dimensional structures
• dc.title Learning partial correlation graphs and graphical models by covariance queries
• dc.type info:eu-repo/semantics/article
• dc.type.version info:eu-repo/semantics/publishedVersion