Scalable Estimation of Large Generalized Additive Models
M. Zimmermann${}^a$, C. Collarin${}^b$, S. N. Wood${}^b$, F. Ziel${}^a$
${}^a$Data Science in Energy and Environment, University of Duisburg-Essen, Germany, ${}^b$School of Mathematics, University of Edinburgh, United Kingdom
Generalized Additive Models (GAM) relate a univariate exponential family response $y_i$ to a linear predictor $g({\mu }_i)={\eta }_i={𝐀}_i\gamma +{\sum }_j{f}_j(x_{ij})$, where smooths $f_j$s are represented in terms of basis functions. As a consequence, the model can be expressed as $\eta =𝐗\beta$. The $p$ regression coefficients, $\beta =({\beta }_1,\mathrm{\dots },{\beta }_p)$, are estimated by penalized maximum likelihood: $\widehat{\beta }=argma{x}_{\beta }[\mathrm{\ell }(\beta )-{(2\varphi )}^{-1}{\sum }_j{\lambda }_j{\beta }^{\top }{𝐒}_j\beta ],$ where each ${\lambda }_j$ controls the smoothness measured by ${𝐒}_j$. The ${\lambda }_j$s can be estimated by Laplace approximate marginal likelihood (LAML) maximization. However, LAML requires forming and decomposing the Hessian matrix of the penalized log-likelihood. This generally precludes reducing the computational cost below $O(n{p}^2)$, thereby making model estimation unfeasible for high-dimensional predictors. Here we propose a way around this bottleneck. We combine the generalized Fellner–Schal smoothing parameter update with stochastic trace estimation (e.g., Hutch++, [1]) and preconditioned conjugate gradients, thus avoiding the formation or Cholesky factorisation of the GAM penalized Hessian. The resulting procedure relies only on matrix–vector products, enables low memory-bandwidth parallelization, exploits model term sparsity with minimal fill-in, and achieves an $O(np)$ computational cost. The performance of the approach is demonstrated on the NMMAPS respiratory mortality data with over one million observations and more than 20,000 coefficients, fitted in just over half an hour. Keywords: Generalized Additive Models; Preconditioned Conjugate Gradient; Stochastic Trace Estimation