Source-linked AI summary
Time Varying Undirected Graphs
Shuheng Zhou, John Lafferty, Larry Wasserman
TL;DR
Existing graph-estimation methods assume stable graphical structure and identically distributed data, whereas the paper addresses distributions and graphs that evolve over time. It develops a nonparametric ℓ1-regularized estimator using time-smoothed covariance estimates and establishes theoretical guarantees under smooth covariance changes, with simulation evidence for graph recovery.
Problem
Existing methods assume stable graphical structure and identically distributed data, although distributions and graphs may evolve over time.
Method
The paper develops a nonparametric ℓ1-regularized estimator for time-varying Gaussian graphical structure using kernel-smoothed covariance estimates.
Results
The paper establishes predictive-risk consistency and convergence results for covariance and inverse covariance estimates under smoothly changing covariances, with simulation evidence for graph recovery.
Takeaways & Limitations
The method provides a feasible high-dimensional approach for estimating time-varying graphical structure from non-identically distributed observations.
Takeaways & Limitations
The analysis assumes independent observations and uses a simple time-series model, while extensions to dependent models and changepoints remain future work.
Abstract
from arXiv · showhide
Undirected graphs are often used to describe high dimensional distributions. Under sparsity conditions, the graph can be estimated using $\ell_1$ penalization methods. However, current methods assume that the data are independent and identically distributed. If the distribution, and hence the graph, evolves over time then the data are not longer identically distributed. In this paper, we show how to estimate the sequence of graphs for non-identically distributed data, where the distribution evolves over time.
1 Introduction
Existing graph-estimation methods assume stable graphical structure and identically distributed data, but applications such as stock prices and gene expression can have conditional independences that change over time.
- Graphical models represent conditional independences through missing edges, which correspond to zero entries in Σ−1 for Gaussian data.
- Existing methods assume that the graphical structure is stable over time.
- Conditional independence between stocks can change as a large stock-price vector evolves over time.
- The paper develops a nonparametric ℓ1-regularized method for estimating time-varying graphical structure in multivariate Gaussian distributions.
2 The Model and Method
The method estimates time-indexed covariance matrices from independent, non-identically distributed Gaussian observations by smoothing observations over time, then uses inverse-covariance structure to obtain graphs.
- Independent Gaussian vectors Zt are indexed over t = 0, 1/n, …, 1, with each time point associated with graph G(t).
- Graph G(t) is determined by the zeroes of Σ(t)−1.
- For simplicity, the paper assumes independent observations while allowing the graphs to change over time.
- The method uses ℓ1 regularization and can leverage existing covariance-estimation software developed for the iid setting.
- The non-iid approach estimates Σ(t) using a kernel estimator of the covariance at time t.
3 Risk Consistency
The paper formulates covariance and inverse-covariance estimation through risk minimization with sparsity constraints or convex ℓ1 relaxations, establishing consistency and convergence results under smoothness and sparsity conditions.
- The method defines risk functions for covariance estimates and graph estimates, including a symmetric-difference measure for edge sets.
- In the iid case, ℓ1 regularization yields a persistent estimator relative to a class of positive definite matrices.
- The unconstrained empirical-risk minimizer is the sample covariance, while imposing an inverse-covariance sparsity constraint yields a nonconvex problem addressed by convex relaxation.
- Under smoothness and regularity conditions, the paper states consistency and convergence results for the covariance and inverse covariance estimators.
- The non-iid estimator defines bΣn(t) as the minimizer of empirical risk over a constrained set using a kernel-smoothed covariance estimate.
- A local linear smoother can improve the rate from n1/3 to n2/5 by reducing the smoothing bias to O(h2).
- The persistency guarantee can include connected graphs when p = nξ with ξ < 1/3, despite sparsity.
4 Frobenius Norm Consistency
The paper estimates the time-varying inverse covariance matrix with an ℓ1-regularized smoothed likelihood and establishes Frobenius-norm consistency under smooth covariance evolution. The proof controls the objective locally and extends the result globally over positive definite matrices.
- Estimator: The estimator minimizes an ℓ1-regularized negative smoothed log-likelihood to estimate Θ(t)=Σ^-1(t) at each time.The smoothed sample covariance bS_n(t) supplies the time-local covariance estimate, while the optimization ranges over positive definite matrices.
- Consistency result: The analysis targets an explicit Frobenius-norm convergence rate when p and the number of edges grow with n, provided covariances change smoothly over time.The graph support is represented through the nonzero off-diagonal entries of Θ(t0), with |S| equal to twice the number of graph edges.
- Proof strategy: With probability 1−1/n^c for some c≥2, the local objective satisfies G(∆)>0 throughout the prescribed neighborhood T_n.This positivity result is the central local step in controlling deviations from the true inverse covariance matrix.
- Proof strategy: Convexity extends objective positivity from T_n to larger deviations in V_n, covering positive definite candidates outside the local Frobenius neighborhood.The argument uses a line segment between a large deviation and a boundary point in T_n.
- Consistency result: Consequently, the estimated inverse covariance satisfies ∥bΘ_n−Θ0∥F<Mr_n whenever the local positivity event holds.The bound follows because the minimizer cannot lie in T_n∪V_n when G(b∆_n)≤G(0)=0.
5 Large Deviation Inequalities
The paper derives concentration bounds for kernel-smoothed covariance estimates from independent but non-identically distributed Gaussian observations. The analysis separates smoothing bias from stochastic deviation and extends the bounds from a boxcar to general compactly supported kernels.
- Setup: The observations are independently sampled Gaussian vectors with time-varying covariances, so the covariance estimator must handle non-identically distributed data.The analysis uses a product measure and compares the smoothed estimate with the covariance at the target time.
- Kernel smoothing: The smoothed empirical covariance uses a kernel K with bounded support [−1,1], enabling local time-window analysis.For the general-kernel analysis, K is symmetric, nonnegative, and compactly supported.
- Kernel smoothing: Kernel weighting assigns larger weights to observations closer to the target time, replacing an unweighted average over the last n samples.The target is denoted x0=t0, and the smoothing bandwidth controls the temporal neighborhood used for estimation.
- Deviation analysis: The analysis derives a large-deviation bound for the maximum entrywise deviation of the smoothed empirical covariance matrix.Independence across observations supports the concentration argument, and the rate is developed for all covariance entries simultaneously.
- Deviation analysis: The covariance-estimation error is decomposed into a bias term and a stochastic deviation term before each component is bounded.Taylor expansion approximates the time-varying covariance around x0, while moment-generating-function arguments control random fluctuations.
- Deviation analysis: The bandwidth h=n^-ε is used in the concentration analysis for some 0<ε<1, with auxiliary bounds controlling the resulting terms.The derivation also evaluates moment-generating functions for products of Gaussian coordinates.
6 Smoothness and Sparsity of Σt via Σ−1
This section relates smoothness of the inverse covariance matrix Θ(x) to smoothness of the covariance matrix Σ(x). Under differentiability and nonsingularity assumptions, matrix-analysis lemmas provide the needed transfer.
- Matrix smoothness: If Θ(t) has differentiable entries and remains nonsingular, matrix-inverse differentiation yields regularity for its inverse.The paper states this relationship through a standard matrix-analysis lemma.
- Matrix smoothness: When Θ(t) has twice differentiable entries and is always nonsingular, the inverse covariance inherits second-order differentiability.The existence of second derivatives for Σ(t) follows from differentiability of Σ(t) and d/dt[Θ(t)].
- Implication: The resulting smoothness theorem applies to covariance columns and supports bounds for the entries of Σ(x).The section writes Σ(x) by columns before invoking the inverse-matrix smoothness result.
7 Some Implications of a Very Sparse Θ
Under a very sparse inverse covariance matrix, derivatives preserve sparsity almost everywhere, yielding bounds used to control covariance-related quantities.
- The section derives its results using Lebesgue integration and statements valid for L1-almost-every x in [0, 1].L1 denotes Lebesgue measure on R.
- Under A5, the support sizes of Θ, Θ′, and Θ′′ are each bounded by s + p for almost every x.The theorem applies outside a measure-zero set.
- The sparsity bounds imply finite upper bounds for quantities involving derivatives of the covariance and inverse covariance matrices.The resulting bounds depend on sparsity and constants S4 and S5.
- On the exceptional null set E, the derivative-based quantities can only be bounded more loosely, by O(p^2) and O(p^4).These weaker bounds apply because sparsity control may fail on E.
- The argument uses the fact that entries of Θ that are zero have zero first and second derivatives almost everywhere.This is established through auxiliary lemmas excluding measure-zero exceptional sets.
8 Examples
Simulations evaluate graph estimation as regularization and sample size vary, and examine how the estimator tracks edges that appear or disappear over time.
- Simulation setup: The simulation increases sample size from n = 200 to 800 and evaluates model consistency and predictive risks as ρ varies.A Gaussian kernel with bandwidth h = 5.848 n^1/3 is used.
- Risk evaluation: Predictive-risk curves compare oracle and empirical estimators at matched vectorized ℓ1 norms, while estimator norms decrease as ρ increases.The oracle and empirical risks are plotted for each sample size n.
- Regularization effects: As ρ increases, precision initially rises and then falls when no edges are predicted, while recall decreases as more edges are omitted.The oracle performs best at matched ℓ1 norm.
- Chasing the changes: Figure 3 tracks when newly added edges enter the estimate and when replaced edges are removed across 400 time steps.The replaced-edge weights decrease from [0.1, 0.3] to zero over [0, 0.5].
9 Conclusions and Extensions
The paper concludes that an ℓ1-penalized kernel-risk approach estimates smoothly time-varying covariance structure and supports graph estimation in high dimensions. It identifies sparsistency, discontinuous changes, and richer time-series dependence as extensions.
- Smooth covariance changes make minimizing an ℓ1-penalized kernel risk effective for estimating covariance matrices and time-varying graphical structure.The authors state that the method is feasible in high dimensions.
- The authors expect stronger conditions could establish sparsistency, meaning edge recovery with probability approaching one.This is presented as an ongoing extension.
- The smoothness assumption may be relaxed using nonparametric changepoint methods that allow jumps.This is identified as a future extension rather than a result established here.
- The paper uses a simple time-series model, while extensions to more general time-series models remain open.The authors describe such extensions as feasible.
A Large Deviation Inequalities for Boxcar Kernel Function
This section establishes large-deviation results for boxcar-kernel covariance estimates from independent Gaussian observations whose distributions vary over time, with the i.i.d. case as a corollary.
- Lemma 35 gives a large-deviation bound for uniformly weighted covariance estimation from independent but non-identically distributed Gaussian samples.The i.i.d. result follows as a corollary.
- The proof decomposes the covariance bound into diagonal and non-diagonal entry results.Lemmas 37 and 38 provide the two components.
- The graph comparison uses estimated edges, extra edges, and missing edges relative to the true graph.These sets are displayed in the associated figure.
- The boxcar kernel assigns equal weights to the samples in the estimation window.In the stated context, h = 1 and the weights are uniform over n samples.
B Proofs for Large Deviation Inequalities
The proof establishes one inequality and bounds the analogous inequality similarly. It uses Taylor expansions, Riemann-integral replacement, and selected constants to complete the argument.
- The proof compares corresponding kth elements, Φ2,k and Φ4,k, in the sums for Φ2 and Φ4.
- Taylor expansions are used as an initial step to obtain the required bounds.
- The argument applies under the condition ak < 1/2 and treats the analogous inequality similarly.
- The sum is replaced by a Riemann integral, followed by Taylor expansions of σi(xk), σj(xk), and σij(xk).
- Constants C1 and C2 are chosen so that the equalities hold, completing the proof.