Asymptotics of Linear Regression with Linearly Dependent Data

Behrad Moniri, Hamed Hassani · 2024

Read Asymptotics of Linear Regression with Linearly Dependent Data by Behrad Moniri, Hamed Hassani (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-03702.txt.

Introduction

Behrad Moniri and Hamed Hassani present a study from twenty twenty-four on linear regression when the input traits lean on each other. Standard theory takes the traits as free of each other and bell curved. Real traits often link in space and time and break that mold. The pair model such traits as processes with a space time spread.

They study ridge regression when both sample count and trait count grow in step. A universality claim shows the long run acts the same if bell curved traits with the same spread stand in. That swap lets random matrix tools pin the error down in a fixed point form. Best penalty picks, overfit, and the double descent curve are read in this linked world.

Catalog record

CREATORBehrad Moniri, Hamed Hassani
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-03702

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Asymptotics of Linear Regression with Linearly Dependent Data Behrad Moniri, Hamed Hassani Abstract In this paper we study the asymptotics of linear regression in settings with non-Gaussian covariates where the covariates exhibit a linear dependency structure, departing from the standard assumption of independence. We model the covariates using stochastic processes with spatio-temporal covariance and analyze the performance of ridge regression in the high-dimensional proportional regime, where the number of samples and feature dimensions grow proportionally. A Gaussian universality theorem is proven, demonstrating that the asymptotics are invariant under replacing the non-Gaussian covariates with Gaussian vectors preserving mean and covariance, for which tools from random matrix theory can be used to derive precise characterizations of the estimation error. The estimation error is characterized by a fixed-point equation involving the spectral properties of the spatio-temporal covariance matrices, enabling efficient computation. We then study optimal regularization, overparameterization, and the double descent phenomenon in the context of dependent data. Simulations validate our theoretical predictions, shedding light on how dependencies influence estimation error and the choice of regularization parameters. \coltauthor University of Pennsylvania, Philadelphia, PA, USA. keywords statistics with dependent data, ridge regression, high-dimensional asymptotics. 1 Introduction Linear regression is one of the most widely used technique in machine learning and statistics. When given independent training samples, there are many tools available to study its performance under a set of relatively general conditions (see e.g., Hsu et al. 2012 ; Oliveira 2016 ; Mourtada 2022 , etc.). In particular, the asymptotic behavior of the estimation error in this case has been fully characterized in the high-dimensional proportional regime where the number of samples and the covariate dimension tend to infinity with a proportional rate (see e.g., Dobriban and Wager 2018 ; Wu and Xu 2020 ; Hastie et al. 2022 , etc.). In contrast, much less is known when the independence assumption on training samples is lifted. The problem of linear regression with dependent data has a wide range of applications from system identification in linear dynamical systems to time-series analysis (see e.g., Ljung 1999 ; Kailath et al. 2000 ; Verhaegen and Verdult 2007 ; Chiuso and Pillonetto 2019 ; Tsiamis et al. 2023 , etc.). Prior work has examined fairly general dependency structures, often providing finite-sample concentration inequalities on the estimation error of (ridgeless) linear regression without deriving precise formulas (see, e.g., Simchowitz et al. 2018 ; Faradonbeh et al. 2018 ; Sarkar and Rakhlin 2019 ; Nagaraj et al. 2020 ; Ziemann et al. 2024 ). Very recently, Luo et al. 2024 ; Atanasov et al. 2024 studied high-dimensional asymptotics of ridge regression with non-i.i.d. data under different assumptions for the covariates. Luo et al. 2024 studied the problem under the assumption that the covariates follow a right-rotationally invariant covariate distribution. Atanasov et al. 2024 assumed that the covariates are generated according a Gaussian stochastic process with spatio-temporal covariance . The authors derived precise formulas for the asymptotic training and test errors and used it to derive generalized cross validation estimators (GCV) to predict the test error. In this paper, we also assume that the covariates are generated according a general stochastic process with a spatio-temporal covariance; lifting the Gaussianity assumption of prior work. In this limit, we prove that in this dependent data setting, a Gaussian Universality property holds and the estimation error remains invariant under changing the covariates to Gaussian vectors while keeping their mean and covariance structure intact. Further, we provide novel precise formulas for the limiting estimation error. We then study the optimal ridge regularization, the effect of regularization and overparameterization, and also the double descent phenomenon in the setting with dependent data. In particular, we show that although the optimal ridge regularization is independent of the dependency structure, the dependence among covariates affects the degree of overparameterization in which the peak of the double descent and the phase transition from underparameterization to overparameterization happens. 2 Preliminaries In this paper, we also consider the study the problem of linear regression with linearly dependent data. We assume that we observe n samples of an input d -dimensional time-series \{x_{i}\}_{i=1}^{n} , and an output real-valued time-series \{y_{i}\}_{i=1}^{n} from the following linear model \displaystyle y_{i}=\langle x_{i},\beta_{\star}\rangle+\varepsilon_{i},\quad\text{for}\quad i=1,2,\dots,n, (1) where \beta_{\star}\in\mathbb{R}^{d} is an unknown linear map, and \{\varepsilon_{i}\}_{i=1}^{n} is an additive noise independent of the input time-series \{x_{i}\}_{i=1}^{n} with \varepsilon_{i}\overset{\mathrm{\rm i.i.d.}}{\sim}{\sf N}(0,\sigma_{\varepsilon}^{2}) . The goal is to use the samples \{(x_{i},y_{i})\}_{i\in[n]} to recover the unknown vector \beta_{\star} . To estimate \beta_{\star} , we will use the ridge estimator with parameter \lambda\in\mathbb{R} , given by \displaystyle\hat{\beta} \displaystyle:=\arg\min_{\beta\in\mathbb{R}^{d}}\frac{1}{n}\sum_{i=1}^{n}\left(y_{i}-\langle x_{i},\beta\rangle\right)^{2}+\lambda\|\beta\|_{2}^{2}. (2) We assume that \{x_{i}\}_{i=1}^{n} follows a stochastic process with Spatio-Temporal Covariance , with a temporal covariance structure that is the same in all dimensions. Such dependency structures has been previously been studied in the literature. See e.g., Nakakita and Imaizumi 2022 ; Chen et al. 2021 ; Kyriakidis and Journel 1999 . Formally, we let X:=\left[\,x_{1}\,|\,\cdots\,|\,x_{n}\,\right]^{\top}\in\mathbb{R}^{n\times d} and make the following assumption on X . Condition 1 (Covariate Structure) . We assume that X=AZB in which Z\in\mathbb{R}^{n\times d} is a random matrix with i.i.d. entries drawn from a distribution \mathcal{D}_{z} , and that A\in\mathbb{R}^{n\times n} and B\in\mathbb{R}^{d\times d} are deterministic matrices controlling the temporal and spatial dependencies of the covariates. This dependency structure is fairly general. We will present some examples of problems satisfying this condition in Section 4.1 . Defining the output vector y:=[\,y_{1},\dots,y_{n}\,]^{\top}\in\mathbb{R}^{n} and the noise vector \varepsilon=[\,\varepsilon_{1},\dots,\varepsilon_{n}\,]^{\top}\in\mathbb{R}^{n} , we can use equation 1 to write y=X\beta_{\star}+\varepsilon . With this matrix notation, the estimator \hat{\beta} is given by \hat{\beta}=(X^{\top}X+\lambda nI_{d})^{-1}X^{\top}y. We study this linear regression problem in the following asymptotic regime. The standard linear regression problem without dependencies has been studied extensively in the literature in a similar high-dimensional proportional regime (see e.g., Tulino and Verdú 2004 ; Dobriban and Wager 2018 ; Wu and Xu 2020 ; Hastie et al. 2022 , etc.). Condition 2 (High-Dimensional Asymptotics) . The sample size n and the dimension d tend to infinity at a proportional rate; i.e., d,n\to\infty,\text{ with }d/n\to\gamma, where \gamma>0 is a constant. Throughout the paper, we will denote this limit by \lim_{d/n\to\gamma} . Consistent with a line of prior work (e.g., Dobriban and Wager 2018 ; Adlam and Pennington 2020b ; Adlam and Pennington 2020a ; Lee et al. 2023 ), we further make the following random-coefficient assumption on the ground truth vector \beta_{\star} . We assume that the effect strength of each feature is drawn independently at random. Thus, our results can be viewed as an average-case analysis over parameters. Condition 3 (Random Coefficient) . The coefficient \beta_{\star}\in\mathbb{R}^{d} is random with \beta_{\star}\sim{\sf N}\left(0,\frac{\alpha^{2}}{d}I_{d}\right). Note that based on this assumption, the vector the covariates \{x_{i}\} do not carry any information about \beta_{\star} . Extending the results for the case where the regression coefficients are allowed to be anisotropic is an interesting problem, and we leave it as future work. See e.g., Mel and Pennington 2021 ; Wu and Xu 2020 ; Hastie et al. 2022 for work in this direction in the i.i.d. setting. To measure the performance of the ridge regularized linear regression estimator, in this paper we focus on the estimation error defined as \displaystyle R(\hat{\beta}):=\|\hat{\beta}-\beta_{\star}\|_{2}^{2}. (3) 2.1 Related Work The study of linear regression with dependent data has

Read the complete text