2025/05/16 by Rares-Darius Buhai, Buhai, Rares-Darius
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Machine Learning (stat.ML) #Machine Learning and Algorithms #Statistical Methods and Inference #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2505.11093
openalex publication_date 2025/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the sparse linear regression model y = X β+w, where X ∈ ℝn × d is the design, β∈ ℝd is a k-sparse secret, and w ∼ N(0, In) is the noise. Given input X and 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 support(β). In this paper, we introduce a new semirandom family of designs -- which we call 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 support(β). Let λmin be the smallest eigenvalue of (1)/(n) Xsupport(β)^\top Xsupport(β), where Xsupport(β) is the restriction of X to the columns indexed by 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 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 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].