The first term, which arises from the supremum of the localized multiplier process, shows the correlation between the noise \(\xi \)  and the statistical leverage score \(X^\mathsf {T}\widehat{\Sigma }_{0}^{-1}X\)  (let \(\mathbf {X} \in {\mathbb {R}}^{n \times d}\)  denote the matrix with the \(i\) -th row equal to \(X_{i}\) ; we may write \(X^\mathsf {T}\widehat{\Sigma }_{0}^{-1}X = H_{nn}\) , where \(H \in {\mathbb {R}}^{n \times n}\)  is the “hat matrix” defined as \(H = \mathbf {X}(\mathbf {X}^{\mathsf {T}}\mathbf {X})^{-1}\mathbf {X}^{\mathsf {T}}\) ). If \(d \le n\)  and the noise random variable \(\xi \)  is independent of \(X\) , then the first term in (REF ) corresponds essentially to the minimax optimal rate for unconstrained least squares regression [1]} and is hence unimprovable in general.
The second term in (REF ), which arises from the supremum of the localized quadratic process, intuitively captures the problem complexity in low-noise regimes, that is, when \(\xi \)  is relatively small. In Proposition REF , we demonstrate a noiseless problem such that for some constrained least squares solutions the second term in (REF ) is tight.
