High-Dimensional Inference with Heterogeneous Data

Abstract

Modern large-scale data offers the exciting prospect of advancing our understanding of many scientific phenomena, but also presents significant computational and statistical challenges for traditional inference methods. A core assumption that underpins much of statistical theory and modelling is that the data are realisations of exchangeable random variables. While important, this limited setting falls short of capturing the complexities inherent to real-world data such as temporal dependence and heterogeneity. This thesis makes progress in this direction by investigating computational barriers and statistical methods for inference in high-dimensional, heterogeneous generalized linear models (GLMs). In a canonical model of heterogeneous regression known as 'Mixed Sparse Linear Regression', we bring novel evidence towards the existence of a statistical price to pay for computational efficiency. In the high-dimensional setting where the sample size $n$ and signal sparsity $k$ are allowed to be sublinear in the covariate dimension $p$, we prove via the low-degree method that a very narrow parameter regime only admits efficient solutions in the case where the sample size is at least an order $k$ greater than optimal. Outside of this narrow parameter regime, however, we prove that a simple thresholding algorithm succeeds. We translate our findings to bring positive evidence towards a conjectured $k$-to-$k^2$ statistical-computational gap in the related problem of 'Sparse Phase Retrieval' [Liu et al. (2021), Wu and Rebeschini (2021)], and provide novel evidence for computational hardness in the special case of 'Sparse Linear Regression'. We then turn our attention to the more structured setting of GLMs with change points. We develop a novel Approximate Message Passing (AMP) algorithm for inference in this setting, and characterize its performance in the high-dimensional regime where the number of samples $n$ and the covariate dimension $p$ grow proportionally. Under the assumption of isotropic Gaussian covariates, we show that the asymptotic estimation performance of our method can be characterized via a succinct low-dimensional matrix recursion called 'state evolution', and demonstrate how one can apply this characterization to construct Bayesian posterior distributions over change point configurations. We demonstrate the favorable estimation performance and the posterior inference capabilities of our method on synthetic and real data. We then propose a sample-weighted empirical risk minimization method for inferring change points in GLMs which we call Weighted ERM. We prove that our previous AMP algorithm can be tailored to mimic Weighted ERM, allowing us to obtain precise guarantees on the performance of Weighted ERM in the high-dimensional regime under mild assumptions on the underlying model and on the specifics of the empirical risk minimization objective. Importantly, our Weighted ERM method is simple to implement, is proven to succeed under general Gaussian covariates with unknown covariance, and incorporates the design flexibility associated with general convex risk minimizers. Using this asymptotic characterization, we propose a method for constructing Bayesian posterior distributions over change point configurations using only observed data and a postulated noise distribution. We demonstrate the favorable performance of our method on both synthetic and real data.