Spectral Dependence of Convex Regularization: Fundamental Limits under Right-Rotationally Invariant Designs
Abstract
We study the fundamental limits of convex-regularized estimation in high-dimensional linear regression with right-rotationally invariant design matrices. We show that the asymptotic risks of convex-penalized least squares estimators are lower bounded by the risk of an approximate message passing algorithm known as Bayes VAMP, and we further characterize when the lower bound is attainable. As a technical ingredient in the proof of our lower bound theorem, we characterize the asymptotic performance of the ℓ2-perturbed convex estimator for every fixed perturbation strength λ>0. This closes a gap in the literature, in which λ was required to be sufficiently large or restrictions were imposed on the class of convex estimators. The benefit of our approach is that we can conduct a direct analysis of the spectrum's impact on the lower bound in the high-dimensional limit. In particular, we can show that the lower bound is monotone in an ordering on the limiting spectral distributions of the design matrix. These results isolate how the full singular-value distribution of the design---not merely the aspect ratio or average measurement strength---governs the limitations of convex regularization.
Related
- Spectral properties of deterministic matrices multiplied by rotationally invariant random non-Hermitian ensembles
- Finite-rank multiplicative perturbations of rotationally invariant non-Hermitian random matrices
- Variance lower bounds for geometric functionals of rotationally invariant log-concave random polytopes
- Repeated differentiation of random polynomials with i.i.d. rotationally invariant roots
- Fluctuation bounds for rotationally invariant first-passage percolation
BibTeX
@misc{tan2026spectral,
title = {{Spectral Dependence of Convex Regularization: Fundamental Limits under Right-Rotationally Invariant Designs}},
author = {Baichen Tan and Audrey Yang and Cynthia Rush},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.07432},
eprint = {2608.07432},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.07432},
}
RIS
TY - UNPB
TI - Spectral Dependence of Convex Regularization: Fundamental Limits under Right-Rotationally Invariant Designs
AU - Baichen Tan
AU - Audrey Yang
AU - Cynthia Rush
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2608.07432
UR - https://arxiv.org/abs/2608.07432
AB - We study the fundamental limits of convex-regularized estimation in high-dimensional linear regression with right-rotationally invariant design matrices. We show that the asymptotic risks of convex-penalized least squares estimators are lower bounded by the risk of an approximate message passing algorithm known as Bayes VAMP, and we further characterize when the lower bound is attainable. As a technical ingredient in the proof of our lower bound theorem, we characterize the asymptotic performance of the ℓ_2-perturbed convex estimator for every fixed perturbation strength λ>0. This closes a gap in the literature, in which λ was required to be sufficiently large or restrictions were imposed on the class of convex estimators. The benefit of our approach is that we can conduct a direct analysis of the spectrum's impact on the lower bound in the high-dimensional limit. In particular, we can show that the lower bound is monotone in an ordering on the limiting spectral distributions of the design matrix. These results isolate how the full singular-value distribution of the design---not merely the aspect ratio or average measurement strength---governs the limitations of convex regularization.
ER -