where \( \ell _i( \theta ) = 2^{-1}(Y_i - X_i^\top \theta )^2 \)  is the loss evaluated on the \( i \) -th observation. We know that the solution to this problem is the classical ordinary least squares (OLS) estimator that has an explicit form as \( \widehat{\theta }_\text{ols} = \arg \min _{\theta } \mathcal {L}(\theta ) = \widehat{\Sigma }_{xx} ^{-1} \widehat{\Sigma }_{xy}\) , where \( \widehat{\Sigma }_{xx} = N^{-1} \sum _{i=1}^N X_i X_i^\top \in \mathbb {R}^{p\times p} \)  and \( \widehat{\Sigma }_{xy} = N^{-1} \sum _{i=1}^N X_i Y_i \in \mathbb {R}^p\) . Under some mild conditions, one can show that \( \sqrt{N} (\widehat{\theta }_\text{ols} - \theta _0) \rightarrow _d N(0, \sigma ^2 \Sigma _{xx}^{-1}) \) , where \( \Sigma _{xx} \)  is the covariance matrix of \( X_i \)  [1]}. To practically compute \( \widehat{\theta }_\text{ols} \) , the sample covariance matrix \( \widehat{\Sigma }_{xx} \)  needs to be calculated and inverted. This leads to a computational complexity of order \( O(Np^2 + p^3) \)  in general.
