Stochastic Lanczos estimation of genomic variance components for linear mixed-effects models

Richard Border, Stephen Becker

TL;DR

This paper introduces two novel algorithms, SLDF_REML and L_FOMC_REML, that significantly speed up the computationally intensive estimation of variance components in linear mixed-effects models (LMMs). These methods leverage the structure of the problem using Lanczos methods and Krylov subspace shift-invariance, allowing for much faster calculations, especially for large genomic datasets, while maintaining high accuracy.

What Problem Does This Paper Address?

Genome-wide association studies (GWAS) frequently use linear mixed-effects models (LMMs) to identify genetic variants associated with complex traits. A critical step in LMM analysis is estimating "variance components" using a method called residual maximum likelihood (REML). However, standard REML estimation involves computationally expensive matrix operations, often with cubic time complexity (O(n³)), making it infeasible for the massive datasets now common in genomics (e.g., hundreds of thousands of individuals). Previous attempts to speed this up involved either reducing the number of these expensive operations or replacing them with iterative/stochastic methods. This paper addresses the need for even faster and more accurate REML estimation methods that can handle large-scale genomic data without sacrificing precision.

Methods

The core innovation lies in two new algorithms: Stochastic Lanczos Derivative-Free REML (SLDF_REML) and Lanczos First-Order Monte Carlo REML (L_FOMC_REML). These methods build upon the idea of Krylov subspace shift-invariance.

Here's a breakdown of the key techniques:

  • Lanczos Procedure: This is an iterative method for approximating the solution to linear systems involving large, symmetric, positive-definite matrices. It generates a sequence of orthogonal polynomials and tridiagonal matrices that can be used to efficiently solve related problems.
  • Krylov Subspace Shift-Invariance: This principle states that the Krylov subspace generated by a matrix A applied to a vector b is the same as the subspace generated by A + σI (where σ is a scalar and I is the identity matrix) applied to b. This is crucial because the REML problem can be reformulated as a series of "shifted linear systems."
  • Exploiting Problem Structure: The authors cleverly reformulate the REML criterion to involve terms that can be efficiently computed using the Lanczos procedure and the shift-invariance property. This means the most computationally intensive operations (like forming certain matrix decompositions) only need to be done once. Subsequent evaluations of the REML criterion can then be performed using much faster vector operations.
  • Stochastic Trace Estimation (SLQ): For estimating certain matrix quantities (like the log-determinant term in REML), the paper employs Stochastic Lanczos Quadrature (SLQ), which combines Lanczos methods with Hutchinson-type stochastic trace estimators. This allows for efficient approximation of these terms without explicit matrix inversion.
  • SLDF_REML: This algorithm is "derivative-free," meaning it doesn't require calculating the derivatives of the REML criterion. It's particularly efficient when a precomputed Genomic Relatedness Matrix (GRM) is available, as it can directly leverage this matrix.
  • L_FOMC_REML: This algorithm is a "first-order Monte Carlo" method. It's more general and can work directly with the genotype matrix (without needing a precomputed GRM), but it requires solving more linear systems per iteration. It's designed to be an extension of existing efficient methods like BOLT-LMM.

Datasets

The primary dataset used for evaluation is the UK Biobank. The authors analyzed nested random subsets of this dataset, ranging from 16,000 to 256,000 unrelated European-ancestry individuals. These subsets were augmented with 24 covariates (age, sex, testing center) and genotypes from 330,723 array SNPs (after filtering for minor allele frequency). The paper does not introduce new benchmark datasets but uses existing large-scale genomic data for rigorous comparison.

Key Insights and Ideas

  • The "Compute Once, Evaluate Many" Paradigm: The most significant insight is how the authors exploit the structure of the REML problem to perform the most expensive computations only once. This drastically reduces the computational burden for subsequent REML evaluations during optimization.
  • Krylov Subspace Shift-Invariance as a Unifying Principle: The paper demonstrates how this mathematical property can bridge the gap between direct matrix methods and iterative/stochastic methods, leading to algorithms that combine the best of both worlds.
  • Flexibility in Input: The two proposed algorithms offer flexibility: SLDF_REML excels when a GRM is precomputed, while L_FOMC_REML is more versatile as it can work directly with genotype matrices. This allows researchers to choose the best method based on their available resources and data format.
  • Interpreted vs. Compiled Language Performance: The results show that their Python implementations of SLDF_REML and L_FOMC_REML can match or even outperform existing compiled (C++) software packages in speed and accuracy, highlighting the efficiency of their algorithmic approach.

Key Results

  • Speed: SLDF_REML, especially when using a precomputed GRM, dramatically outperforms other methods. For example, at n=256,000, SLDF_REML with a precomputed GRM took only 38.60 minutes, while BOLT-LMM v2.3.2 took 91.09 minutes. Even L_FOMC_REML (using the genotype matrix) was competitive, with a per-iteration evaluation time of just 2.06 minutes compared to 20.07 minutes for BOLT-LMM v2.3.2.
  • Accuracy: Both SLDF_REML and L_FOMC_REML produced heritability estimates consistent with the gold-standard GCTA software. For large sample sizes (n=256,000), the novel algorithms achieved higher accuracy (lower mean-squared error) than BOLT-LMM.
  • Scalability: The methods are designed for and demonstrated to be effective on very large sample sizes (up to 256,000 individuals).
  • Implementation: The authors provide Python implementations, demonstrating that interpreted languages can achieve competitive performance with optimized compiled code for these algorithms.

Limitations and Future Work

  • Memory Complexity: The algorithms do not fundamentally reduce the O(mn) or O(n²) memory requirements for storing matrices, meaning researchers still need access to high-memory compute nodes for large datasets.
  • Two-Component Model: The current algorithms are limited to the standard two-component genomic variance model (heritable and residual effects). They do not extend to models with more than two variance components, which are often needed for more complex traits.
  • Future Work: The authors suggest extending these methods to handle multivariate phenotypes (multiple traits simultaneously) and exploring their application to non-infinitesimal models (where genetic effects are not limited to single loci). They also believe the underlying stochastic trace estimation and Lanczos quadrature techniques could find use in REML estimation for other types of models.

Summary updated

Abstract

Background Linear mixed-effects models (LMM) are a leading method in conducting genome-wide association studies (GWAS) but require residual maximum likelihood (REML) estimation of variance components, which is computationally demanding. Previous work has reduced the computational burden of variance component estimation by replacing direct matrix operations with iterative and stochastic methods and by employing loose tolerances to limit the number of iterations in the REML optimization procedure. Here, we introduce two novel algorithms, stochastic Lanczos derivative-free REML (SLDF_REML) and Lanczos first-order Monte Carlo REML (L_FOMC_REML), that exploit problem structure via the principle of Krylov subspace shift-invariance to speed computation beyond existing methods. Both novel algorithms only require a single round of computation involving iterative matrix operations, after which their respective objectives can be repeatedly evaluated using vector operations. Further, in contrast to existing stochastic methods, SLDF_REML can exploit precomputed genomic relatedness matrices (GRMs), when available, to further speed computation. Results Results of numerical experiments are congruent with theory and demonstrate that interpreted-language implementations of both algorithms match or exceed existing compiled-language software packages in speed, accuracy, and flexibility. Conclusions Both the SLDF_REML and L_FOMC_REML algorithms outperform existing methods for REML estimation of variance components for LMM and are suitable for incorporation into existing GWAS LMM software implementations.
BibTeX
@article{border2019stochastic,
  author = {Richard Border and Stephen Becker},
  title = {{Stochastic Lanczos estimation of genomic variance components for linear mixed-effects models}},
  journal = {BMC Bioinformatics},
  year = {2019},
  doi = {10.1186/s12859-019-2978-z},
}
Figure