Lasso and Partially-Rotated Designs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909612534398976 |
|---|---|
| author | Buhai, Rares-Darius |
| author_facet | Buhai, Rares-Darius |
| contents | We consider the sparse linear regression model $\mathbf{y} = X β+\mathbf{w}$, where $X \in \mathbb{R}^{n \times d}$ is the design, $β\in \mathbb{R}^{d}$ is a $k$-sparse secret, and $\mathbf{w} \sim N(0, I_n)$ is the noise. Given input $X$ and $\mathbf{y}$, the goal is to estimate $β$. In this setting, the Lasso estimate achieves prediction error $O(k \log d / γn)$, where $γ$ is the restricted eigenvalue (RE) constant of $X$ with respect to $\mathrm{support}(β)$. In this paper, we introduce a new $\textit{semirandom}$ family of designs -- which we call $\textit{partially-rotated}$ designs -- for which the RE constant with respect to the secret is bounded away from zero even when a subset of the design columns are arbitrarily correlated among themselves.
As an example of such a design, suppose we start with some arbitrary $X$, and then apply a random rotation to the columns of $X$ indexed by $\mathrm{support}(β)$. Let $λ_{\min}$ be the smallest eigenvalue of $\frac{1}{n} X_{\mathrm{support}(β)}^\top X_{\mathrm{support}(β)}$, where $X_{\mathrm{support}(β)}$ is the restriction of $X$ to the columns indexed by $\mathrm{support}(β)$. In this setting, our results imply that Lasso achieves prediction error $O(k \log d / λ_{\min} n)$ with high probability. This prediction error bound is independent of the arbitrary columns of $X$ not indexed by $\mathrm{support}(β)$, and is as good as if all of these columns were perfectly well-conditioned.
Technically, our proof reduces to showing that matrices with a certain deterministic property -- which we call $\textit{restricted normalized orthogonality}$ (RNO) -- lead to RE constants that are independent of a subset of the matrix columns. This property is similar but incomparable with the restricted orthogonality condition of [CT05]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_11093 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Lasso and Partially-Rotated Designs Buhai, Rares-Darius Statistics Theory Data Structures and Algorithms Machine Learning We consider the sparse linear regression model $\mathbf{y} = X β+\mathbf{w}$, where $X \in \mathbb{R}^{n \times d}$ is the design, $β\in \mathbb{R}^{d}$ is a $k$-sparse secret, and $\mathbf{w} \sim N(0, I_n)$ is the noise. Given input $X$ and $\mathbf{y}$, the goal is to estimate $β$. In this setting, the Lasso estimate achieves prediction error $O(k \log d / γn)$, where $γ$ is the restricted eigenvalue (RE) constant of $X$ with respect to $\mathrm{support}(β)$. In this paper, we introduce a new $\textit{semirandom}$ family of designs -- which we call $\textit{partially-rotated}$ designs -- for which the RE constant with respect to the secret is bounded away from zero even when a subset of the design columns are arbitrarily correlated among themselves. As an example of such a design, suppose we start with some arbitrary $X$, and then apply a random rotation to the columns of $X$ indexed by $\mathrm{support}(β)$. Let $λ_{\min}$ be the smallest eigenvalue of $\frac{1}{n} X_{\mathrm{support}(β)}^\top X_{\mathrm{support}(β)}$, where $X_{\mathrm{support}(β)}$ is the restriction of $X$ to the columns indexed by $\mathrm{support}(β)$. In this setting, our results imply that Lasso achieves prediction error $O(k \log d / λ_{\min} n)$ with high probability. This prediction error bound is independent of the arbitrary columns of $X$ not indexed by $\mathrm{support}(β)$, and is as good as if all of these columns were perfectly well-conditioned. Technically, our proof reduces to showing that matrices with a certain deterministic property -- which we call $\textit{restricted normalized orthogonality}$ (RNO) -- lead to RE constants that are independent of a subset of the matrix columns. This property is similar but incomparable with the restricted orthogonality condition of [CT05]. |
| title | Lasso and Partially-Rotated Designs |
| topic | Statistics Theory Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2505.11093 |