Two key tasks in high-dimensional regularized regression are tuning the regularization strength for accurate predictions and estimating the out-of-sample risk. It is known that the standard approach — $k$-fold cross-validation — is inconsistent in modern high-dimensional settings. While leave-one-out and generalized cross-validation remain consistent in some high-dimensional cases, they become inconsistent when samples are dependent or contain heavy-tailed covariates. As a first step towards modeling structured sample dependence and heavy tails, we use right-rotationally invariant covariate distributions — a crucial concept from compressed sensing. In the proportional asymptotics regime where the number of features and samples grow comparably, which is known to better reflect the empirical behavior in moderately sized datasets, we introduce a new framework, ROTI-GCV, for reliably performing cross-validation under these challenging conditions. Along the way, we propose new estimators for the signal-to-noise ratio and noise variance. We conduct experiments that demonstrate the accuracy of our approach in a variety of synthetic and semi-synthetic settings.

We study the fundamental problem of calibrating a linear binary classifier of the form \(\sigma(\hat{w}^\top x)\), where the feature vector \(x\) is Gaussian, \(\sigma\) is a link function, and \(\hat{w}\) is an estimator of the true linear weight $w^\star$. By interpolating with a noninformative \emph{chance classifier}, we construct a well-calibrated predictor whose interpolation weight depends on the angle \(\angle(\hat{w}, w_\star)\) between the estimator \(\hat{w}\) and the true linear weight \(w_\star\). We establish that this angular calibration approach is provably well-calibrated in a high-dimensional regime where the number of samples and features both diverge, at a comparable rate. The angle \(\angle(\hat{w}, w_\star)\) can be consistently estimated. Furthermore, the resulting predictor is uniquely \emph{Bregman-optimal}, minimizing the Bregman divergence to the true label distribution within a suitable class of calibrated predictors. Our work is the first to provide a calibration strategy that satisfies both calibration and optimality properties provably in high dimensions. Additionally, we identify conditions under which a classical Platt-scaling predictor converges to our Bregman-optimal calibrated solution. Thus, Platt-scaling also inherits these desirable properties provably in high dimensions.

Over the past decade, characterizing the precise asymptotic risk of regularized estimators in high-dimensional regression has emerged as a prominent research area. This literature focuses on the proportional asymptotics regime, where the number of features and samples diverge proportionally. Much of this work assumes i.i.d. Gaussian entries in the design. Concurrently, researchers have explored the universality of these findings, discovering that results based on the i.i.d. Gaussian assumption extend to other settings, including i.i.d. sub-Gaussian designs. However, universality results examining dependent covariates have predominanatly focused on correlation-based dependence or structured forms of dependence allowed by right-rotationally-invariant designs. In this paper, we challenge this limitation by investigating dependence structures beyond these established classes. We identify a class of designs characterized by a block dependence structure where results based on i.i.d. Gaussian designs persist. Formally, we establish that the optimal values of regularized empirical risk and the risk associated with convex regularized estimators, such as the Lasso and the ridge, converge to the same limit under block-dependent designs as for i.i.d. Gaussian entry designs. Our dependence structure differs significantly from correlation-based dependence and enables, for the first time, asymptotically exact risk characterization in prevalent high-dimensional nonlinear regression problems.

We prove a new generalization bound that shows for any class of linear predictors in Gaussian space, the Rademacher complexity of the class and the training error under any continuous loss $\ell$ can control the test error under all Moreau envelopes of the loss $\ell$ . We use our finite-sample bound to directly recover the “optimistic rate” of Zhou et al. (2021) for linear regression with the square loss, which is known to be tight for minimal $\ell_2$-norm interpolation, but we also handle more general settings where the label is generated by a potentially misspecified multi-index model. The same argument can analyze noisy interpolation of max-margin classifiers through the squared hinge loss, and establishes consistency results in spiked-covariance settings. More generally, when the loss is only assumed to be Lipschitz, our bound effectively improves Talagrand’s well-known contraction lemma by a factor of two, and we prove uniform convergence of interpolators (Koehler et al. 2021) for all smooth, non-negative losses. Finally, we show that application of our generalization bound using localized Gaussian width will generally be sharp for empirical risk minimizers, establishing a non-asymptotic Moreau envelope theory for generalization that applies outside of proportional scaling regimes, handles model misspecification, and complements existing asymptotic Moreau envelope theories for M-estimation.