CS36: Probabilistic graphical models

date: 7/15/2025, time: 16:00-17:30, room: ICS 105

Organizer: Malgorzata Bogdan (University of Wroclaw)

Chair: Malgorzata Bogdan (University of Wroclaw)

High-dimensional learning on concentration matrix pattern with atomic regularizers

PIOTR GRACZYK (POLITECHNIKA WROCŁAWSKA and UNIVERSITE D’ANGERS)

This is a joint research with B. Kołodziejek(Politechnika Warsaw), H. Nakashima(Tokai) and M. Wilczyński (Politechnika Wroclaw)

Estimating high-dimensional concentration (inverse covariance, precision) matrices is a central problem in modern statistics. Graphical models provide a powerful framework for uncovering conditional‐independence structures. Wainwright et al. \([1,2]\) made seminal contributions by analyzing the graphical lasso (GLASSO) estimator, focusing on its ability to recover both the support and the sign pattern of the true precision matrix. The GLASSO employs an L1-penalty (regularizer) and is tailored to exploit sparsity.

However, many statistical models exhibit richer structure, eg. affine relations among precision‐matrix entries (in particular equality constraints among them), maximal terms positions, hierarchy of coefficients, ...

Colored Gaussian graphical models, introduced by Højsgaard and Lauritzen \([3]\), combine two complementary forms of parsimony: sparsity induced by conditional independence zeros and symmetry imposed via equality constraints on entries.

Recovering richer structures requires regularizers beyond the L1 one.

A powerful conceptual framework for designing such regularizers comes from the theory of atomic norms (Chandrasekaran et al. \([4]\)) which posits that many simple models can be expressed as a combination of a few elementary "atoms" from a predefined set. The corresponding atomic norm, whose unit ball is the convex hull of this atomic set, then serves as a natural regularizer. This general approach provides a unified way to convert notions of simplicity into convex penalty functions, leading to convex optimization solutions for recovering structured models.

In this research, we focus on the subclass of atomic norms whose unit ball is a polytope.

The supremum norm as penalty, can isolate a cluster of entries with the largest magnitudes.

The sorted L1 norms(SLOPE) allow more sophisticated learning, interpolating between L1 and supremum norm properties and they are well-suited for recovering the patterns inherent in colored graphical models.

Consequently, atomic norms as penalties provide a huge potential of recovering structured models. Despite this potential, theoretical guarantees of pattern recovery with atomic norms in the context of precision matrix estimation, remained unknown. In our research presented in this talk we fill in this gap.

Bibliography

\([1]\) Pradeep Ravikumar, Martin J. Wainwright, Garvesh Raskutti, and Bin Yu. High-dimensional covariance estimation by minimizing ℓ1-penalized log-determinant divergence. Electronic Journal of Statistics, 5, 935 – 980, 2011.

\([2]\) Martin J. Wainwright, High-Dimensional Statistics, Cambridge University Press, 2019

\([3]\) Søren Højsgaard and Steffen L. Lauritzen. Graphical Gaussian models with edge and vertex symmetries. J. R. Stat. Soc. Ser. B Stat. Methodol., 70(5):1005–1027, 2008.

\([4]\) Venkat Chandrasekaran, Benjamin Recht, Pablo A. Parrilo, and Alan S. Willsky. The convex geometry of linear inverse problems. Found. Comput. Math., 12(6):805–849, 2012.

Gaussian Whittle–Matern fields on metric graphs

Jonas Wallin (Lund university)

Random fields are popular models in statistics and machine learning for spatially dependent data on Euclidian domains. However, in many applications, data is observed on non-Euclidian domains such as street networks, or river networks. In this case, it is much more difficult to construct valid random field models. In this talk, we discuss some recent approaches to modeling data in this setting, and in particular define a new class of Gaussian processes on compact metric graphs. The proposed models, the Whittle-Matérn fields, are defined via a stochastic partial differential equation on the compact metric graph and are a natural extension of Gaussian fields with Matérn covariance functions on Euclidean domains to the non-Euclidean metric graph setting.

Property testing in graphical models: testing small separation numbers

Piotr Zwiernik (Universitat Pompeu Fabra)

In many statistical applications, the dimension is too large to handle for standard high-dimensional machine learning procedures. This is particularly true for graphical models, where the interpretation of a large graph is difficult and learning its structure is often computationally impossible either because the underlying graph is not sufficiently sparse or the number of vertices is too large. To partially address this issue, we develop a procedure to test a property of a graph underlying a graphical model that requires only a subquadratic number of correlation queries (i.e., we require that the algorithm only can access a tiny fraction of the covariance matrix). This provides a conceptually simple test to determine whether the underlying graph is a tree or, more generally, if it has a small separation number, a quantity closely related to the treewidth of the graph. The proposed method is a divide-and-conquer algorithm that can be applied quite generally.