Asymptotically Free Sketched Ridge Ensembles: Risks, Cross-Validation, and Tuning
Authors: Pratik Patil
Daniel LeJeune
Venue: ICLR 2024 spotlight (2024)
Keywords: asymptotic freeness
sketching
ensembles
ridge regression
generalized cross-validation
tuning
Primary area: learning theory
TL;DR: We show consistency of generalized cross-validation for tuning asymptotically free sketched ridge ensembles under mild data assumptions.

Abstract: We employ random matrix theory to establish consistency of generalized cross validation (GCV) for estimating prediction risks of sketched ridge regression ensembles, enabling efficient and consistent tuning of regularization and sketching parameters. Our results hold for a broad class of asymptotically free sketches under very mild data assumptions. For squared prediction risk, we provide a decomposition into an unsketched equivalent implicit ridge bias and a sketching-based variance, and prove that the risk can be globally optimized by only tuning sketch size in infinite ensembles. For general subquadratic prediction risk functionals, we extend GCV to construct consistent risk estimators, and thereby obtain distributional convergence of the GCV-corrected predictions in Wasserstein-2 metric. This in particular allows construction of prediction intervals with asymptotically correct coverage conditional on the training data. We also propose an "ensemble trick" whereby the risk for unsketched ridge regression can be efficiently estimated via GCV using small sketched ridge ensembles. We empirically validate our theoretical results using both synthetic and real large-scale datasets with practical sketches including CountSketch and subsampled randomized discrete cosine transforms.

Published as a conference paper at ICLR 2024
ASYMPTOTICALLY FREE SKETCHED RIDGE ENSEMBLES: RISKS, M AND TUNING
Pratik Patil
Daniel LeJeune
Department of Statistics
Department of Statistics Stanford University California, CA 94305, USA daniel8 @dlej net
University of California, Berkeley
California, CA 94720, USA
pratikpat www.eeeeeeeeeeeeeeee.eeeeeeeeeee beetikketBbeerreee....... edu
ABSTRACT
We employ random matrix theory to establish consistency of generalized cross validation (GCV) for estimating prediction risks of sketched ridge regression en- sembles, enabling efficient and consistent tuning of regularization and sketching parameters. Our results hold for a broad class of asymptotically free sketches under very mild data assumptions. For squared prediction risk, we provide decom- position into an unsketched equivalent implicit ridge bias and a sketching- bbased variance, and prove that the risk be globally optimized by only tuning sketch size in infinite ensembles. For general subquadratic prediction risk functionals, we extend GCV construct consistent risk estimators, and thereby obtain distribu- tional convergence of the GCV-corrected predictions in Wasserstein-2 metric. This in particular allows construction of prediction intervals with asymptotically correct coverage conditional on the training data. We also propose an "ensemble trick" whereby the risk for unsketched ridge regression can be efficiently estimated via GCV using small sketched ridge ensembles. We empirically validate our theoretical results using both synthetic and real large-scale datasets with practical sketches including CountSketch and subsampled randomized discrete cosine transforms.
INTRODUCTION
Random sketching a powerful tool for reducing the computational complexity associated with large- scale datasets by projecting them to lower-dimensional space for efficient computations. Sketching has been a remarkable success both in practical applications and from a theoretical standpoint: has enabled application of statistical techniques to problem scales that were formerly unimaginable (Aghazadeh et al.) 2018 Murray et al.) 2023), while enjoying rigorous technical guarantees that ensure the underlying learning problem essentially remains unchanged provided the sketch dimension is not too small (e.g., above the rank of the full data matrix) (Tropp) 2011 Woodruff, 2014).
However, real-world data scenarios often deviate from these ideal conditions for which the problem remains unchanged. For one, real data often has a tail of non-vanishing eigenvalues and is not truly low rank. For another, our available resources may impose constraints on sketch sizes, forcing them to fall below the critical threshold. When the sketch size is critically low, the learning problem can change significantly. In particular, when reducing the dimensionality below the threshold to solve the original problem, the problem becomes implicitly regularized (Mahoney) 2011 Thanei et al. 2017)) Recent work has precisely characterized this problem change linear regression (LeJeune al. 2022), being exactly equal to ridge regression in infinite ensemble of sketched predictors (LeJeune) et al. 2020), with the size of the sketch acting as an additional hyperparameter that affects the implicit regularization.
the underlying problem changes with sketching, key question arises: can we reliably and efficiently tune hyperparameters of sketched prediction models, such the sketch size? While cross- validation (CV) is the classical way to tune hyperparameters, standard k-fold CV (with small or moderate values, such as 5 or 10) is not statistically consistent for nigh-dimensional data (Xu et al. 2019). and saave-one-or CV (LOOCV) is often computationally infeasible. Generalized cross-valdation (GCV), the other hand, is extremely efficient method for estimating generalization using

---

Published as a conference paper at ICLR 2024
Sqgaadd stde mi
Sqguoeed risk HiGrnn
Unthegonal Lountttetth
3.5
SaICTT Fall ridel
1.80
3.0
2.0
1.80
10
15t1
30
10"1 307 30"
0.2
0.4
10.5
0.5
Reguliatiatton strength A
Statedl size ratio
Figure I: GCV provides consistent risk estimation for sketched ridge regression. We show squared risk (solid) and GCV estimates (dashed) for sketched regression ensembles of = predictors on synthetic data with n = 500 ohservations and 600 features. Left: Each sketch induces its own risk curve in regularization strength X, but across all sketches GCV is consistent. Middle: Minimizers and minimum values can vary by sketching type. Right: Each sketch also induces risk curve in sketch size q/p, sketch size can be tuned to optimize risk. Error bars denote standard erorr the mean over 100 trials. Here, SRDCT refers to a subsampled randomized discrete cosine transform (sec Appendix G for further details).
only training data (Craven & Wahba 1979: Hastie et al., 2009), providing asymptotically exact error estimators in high dimensions with similar computational cost to fitting the model (Patil et al., 2021; Wei et al. 2022). However, since the consistency of GCV is due to certain concentration of measure phenomena of data, it is unclear whether GCV should also provide consistent error estimator for predictors with sketched data, in particular when combining several sketched predictors in ensemble, such in distributed optimization settings.
In this work, we prove that efficient consistent tuning of hyperparameters sketched ridge regression ensembles is achievable with GCV (see Figure for an illustration). Furthermore, we state our results for a very broad class of asymptotically free sketching matrices, notion from free probability theory (Voiculescu) 1997, Mingo & Speicher 2017) generalizing rotational invariance. Below we present summary of our main results in this paper and provide an outline of the paper.
Squared risk asymptotics. We provide precise asymptotics of squared risk and its GCV estimator for sketched ridge ensembles in Theorem for the class of asymptotically free sketches applied to features. We give this result in terms an exact birinvariance decomposition into an equivalent implicit unsketched ridge regression risk and an inflation term due to randomness of the sketch that is controlled by ensemble size.
2. Distributional and functional consistencies. We prove consistency of GCV risk estimators for broad class of subquadratic risk functionals in Theorems 3 and To the best of our knowledge, this the first extension of GCV beyond residual-based risk functionals in any setting. In doing so, we also prove the consistency of estimating the joint response ppredictio distribution using GCV in Wasserstein W22 metric in Corollary [ enabling the use of GCV for also evaluating classification error and constructing prediction intervals with valid asymptotic conditional coverage.
3. Tuning applications. Exploiting the special form of the risk decomposition, we propose a method in the form of an "ensemble trick" to tune unsketched ridge regression using only sketched ensembles. We also prove that large unregularized sketched ensembles with tuned sketch size can achieve the optimal unsketched ridge regression risk in Proposition 6
Throughout all of our results, we impose very weak assumptions: we require no model on the relationship between response variables and features; we allow for arbitrary feature covariance with random matrix structure; we allow any sketch that satisfies asymptotic freeness, which we empirically verify for CountSketch (Charikar et al. 20004) and subsampled randomized discrete cosine transforms (SRDCT); and we allow for the consideration of zero even negative regularization. All proofs and details of experiments and additional numerical illustrations are deferred to the appendices.
Related work. For context, we briefly discuss related work on sketching, ridge regression, and CV.
Sketching and implicit regularization. The implicit regularization effect of sketching has been known for some time (Mahoney) 2011 Thanei et al., 2017). This effect is strongly related to inversion bias, and has been precisely characterized in a number settings in recent years (Mutny et al.) 2020 Dereziński et al. a Most recently, LeJeune al. (2022) showed that sketched matrix inversions are asymptotically equivalent to unsketched implicitly regularized inversions, and that this holds not only for i.i.d. random sketches but also for asymptotically free sketches. This result is crucial component of our bias-variance decomposition of GCV risk. By allowing free sketches, we can apply our results to many sketches used in practice with limited prior theoretical understanding.
2

---

Published as a conference paper at ICLR 2024
High-dimeent dimensionn ridge and sketching. Ridge regression, particularly "ridgeless" regression where the regularization level approaches zero, has recently attracted great attention. In the overparameterized regime, where the number of features exceeds the number of observations, the ridgeless estimator interpolates the training data and exhibits a peculiar generalization behaviour (Belkin et al. 2020
Bartlett al., 2020; Hastie al. )022). Different sketching variants and their risks for single sketched ridge estimator under positive regularization are analyzed in Liu & Dobriban (2020). Very recently, Bach| (2024) considers the effect random sketching that includes ridgeless regression. Our work broadens the scope of these works by considering all asymptotically free sketched ensembles and accommodating zero (and negative) regularization. Complementary to feature sketching, there an emerging interest in subsampling and observation sketching. The statistical properties of various subsampled predictors are analyzed by Patil et al. (2023); Du et al. (2023); Patil & Du (022)); Chen
et al. ) Ando & Komaki (2023). At high level, this work acts as "dual" to this literature.
Cross-valiclatinn and tuning. CV is a prevalent method for model assessment and selection (Hastie ct al., 2009), For surveys on CV variants, we refer readers to Arlot & Celisse (2010); Zhang & Yang
(2013). Initially proposed for linear smoothers in the fixed-X design settings, GCV provides an extremely efficient alternative to traditional CV methods like LOOCV (Golub et al.
1979; Craven
& Wahba 1979). It approximates the so-called "shortcut" LOOCV formula (Hastie et al. 2009).
More recently, there has been growing interest in GCV in the random-X design settings. Consistency
properties of GCV have been investigated: for ridge regression under various scenarios (Adlam &
Pennington 2020 Patil et al., |021 2022 Wei et al., 2022 Han & Xu 2023), for the lasso (Bayati & Montanari 2011 Celentano et al. 2023), and for general regularized M -estimaators (Bellec) 2023
Bellec & Shen (022), among others. Our work adds to this literature by analyzing GCV for Ireely
sketched ridge ensembles and establishing its consistency across a broad class of risk functionals.
2 SKETCHED ENSEMBLES
Let ((x,, (;); be i.i.d. observations in R R. We denote by X Raxp the data matrix whose i-th row contains x! and by y E R the associated response vector whose i-th entry contains y:-
Sketched ensembles and risk functionals. Consider collection of K independent sketching matrices S& E Roxq for le [K]. We consider sketched ridge regression where we apply the sketching matrix S₁ to the features (columns) of the data X only. We denote the sketching solution as
X = Sx for 3 arg min A XS X||B1k
(I)
BER
where À is the ridge regularization level. We obtain the final ensemble estimator as a simple un- weighted average of K independently sketched predictors, each of which admits a simple expression:
Eque
3 >
where x - S ( XS + -
It is worth mentioning that, in practice, it is not necessary to "broadcast" 3 back to p-dimensional space to realize 3*. and all computation can (and should) be done in the sketched domain. Note also that we allow for X to be possibly negative in when writing (2) (see Theorem I for details). Let (Xo, yn) be test point drawn independently from the same distribution as the traming data. Risk functionals of the ensemble estimator are properties of the joint distribution of (wo. x (e Letting Peus denote this distribution, we are interested in estimating linear functionals of pens, That is, let IR be error function. Define the corresponding conditional prediction risk functional as
t 2
T(
f(y, 2) (dpp"(( (v. 2) = Ex (( x T Gena)
X, y. (5w)
(3)
special case is the squared risk when (y, 2) = (y - 2)², denoted by R((āqu)) in the sequel.
Proposed GCV plug-in estimators. Note that each individual estimator a of the ensemble is linear smoother with smoothing matrix L
S X XS + ) - in the sense that the training data predictions are given by 3 L y. This motivates our consideration of estimators based on generalized cross-validation (GCV) (Hastie et al. 2009 Chapter 7). Given any linear smoother of the responses with smoothing matrix L, the GCV estimator of the squared prediction risk is 1 ly Ly 1/(1 1 tr GCV enjoys certain consistency properties in the fixed-X - setting (Li 1985 1986) and has recently been shown to also be consistent under various
XSS
"
v.
random-X settings for ridge regression (Patil al. 2021
Wei et al. 2022
Han & Xu 2023
3

---

Published as a conference paper at ICLR 2024
We extend the GCV estimator to general functionals by considering GCV as a plug-in estimator of squared risk of the form 1 Dd (3/ 2 Determining the 2, that correspond to GCV, we obtain the empirical distribution of GCV correeeee predictions as follows:
Pens
8
Uh
1 tr LT 1/
L )
where 2
1 K
K
L
72
Here ō(a} denotes a Dirac measure located at an atom E R2. To give some intuition as to why this is a reasonable choice, consider that when fitting a model, the predictions on training points will be excessively correlated with the training responses. In order to match the test distribution, need to cancel this increased correlation, which we accomplish by subtracting an appropriately scaled yi-
Using this empirical distribution, we form the plug-in GCV risk functional estimators
22 gens
1 b x 12
T(
Ui+ 1 1 [r[
and R(
(1 (1- tr
(5)
In the case where À - 0 but ridgeless regression is well-defined, the denominator may tend to zero However, the numerator will also tend to zero, and therefore one should interpret this quantity as its analytic continuation, which is also well-defined. In practice, if so desired, one can choose very small (positive and negative) À near zero and interpolate for a first-order approximation.
We emphasize that the GCV-corrected predictions are "free lunch" in most circumstances. For example, when tuning over X, it is common precompute decomposition of XS2 such that subsequent matrix inversions for each À are very inexpensive, and the same decomposition can be used evaluate [ Leus] exactly. Otherwise, Monte-Carlo trace estimation is common strategy for GCV (Girard 1989 Hutchinson 1989) that yields consistent estimators using very few (even single) samples, such that the additional computational cost is essentially the same as fitting the model. See Appendix Horor computational complexity comparisons of various cross-vale validation methods.
SQUARED RISK ASYMPTOTICS AND CONSISTENCY
We now derive the asymptotics of squared risk and its GCV estimator for the finite ensemble sketched estimator. The special structure of the squared risk allows us to obtain explicit forms of the asymptoties that shed light on the dependence of both the ensemble risk and GCV on K, the size of the ensemble. We then show consistency of GCV for squared risk using these asymptoties.
We express our asymptotic results using the asymptotic equivalence notation An = B,, which means that for any sequence of O, having |6xll tr (O,,, O ) uniformly bounded in lim,--z tr [O, (An B = 0 almost surely. In the case that A,, and B, are scalars a, and by such as risk estimators, this reduces to lim,- (a, b.,) O. Our forthcoming results apply to a sequence of problems of increasing dimensionality proportional to n, and we omit the explicit dependence on in our statements.
For our theoretical analysis, sketch should preserve much of the essential structure of the data, even through (regularized) matrix inversion. A sufficient yet quite general condition for this is freeness (Voiculescu 1997 Mingo & Speicher 2017).
we need our sketching matrix S to have favorable properties. The
Assumption A (Sketch structure). Let SS and 1 X X converge almost surely to bounded oper- n ators infinitesimally free with respect to tr ti (-1) for any independent of S with O I uniformly bounded, and let SST have limiting S-transform SST analytic on C-
We give a background on freeness including infintesimal freeness (Shlyakhtenko 2018) in Ap- pendix A Intuitively, freeness of a pair of operators A and means that the eigenvectors of one are completely unaligned or incoherent with the eigenvectors of the other. For example, if A UDUT for a uniformly random unitary matrix drawn independently of positive semidefinite B and D, then A and B are almost surely asymptotically infinitesimally free (Cébron et al. 2022 For this reason, we expect any sketch that is rotationally invariant, a desired property of sketches in practice as we do not wish the sketch to prefer any particular dimensions of our data, to satisfy Assumption
NNte that this includes the two sketches most commonly studied theoretically: those with i.i.d. Gaussian entries, and random orthogonal projections, which hoth have analytic S-transforms (see Appendix A.4p.
4

---

Published as a conference paper at ICLR 2024
The property that the sketch preserves the structure of the data is captured in the notion of sub- ordination and conditional expectation in free probability (Biane] 1998). closely related to the deterministic equivalents (Dobriban & Sheng 2020: 202T used in random matrix theory. LeJeune at 2022) recently extended such results to infinitesimally free operators in the context of sketching, which will form the basis of our analysis
For the statements follow, define Σ _ X and Ao = lim p Aii (S) ΣS). Here Amnn(A denotes the minimum nonzero eigenvalue of symmetric matrix A. In addition, define the population covariance matrix Σ = [[[xox]].
Theorem (Free sketching equivalence:
LeJeune et al. (2022), Theorem 7.2). Under Assumption A
for all X > Ao.
S(S ΣS + SS = (É + ndp) where μ >- -A (E) is increasing
(6)
Xn and satisfies
a SS (- t ES(S ES AI,)- sST (- 1 (l,)
Put another way, when we sketch Σ and compute regularized inverse, it is (in a first-order sense) as we had computed an unsketched regularized inverse of Σ, potentially with a different "implicit" regularization strength y instead of X. Since the result holds for free sketching matrices,
expect
this to include fast practical sketches such as CountSketch (Charikar et al. (004) and subsampled randomized Fourier and Hadamard transforms (SRFT/SRHT) (Tropp] [01 I Lacotte al. 2020))
which were demonstrated empirically to satisfy the same relationship by LeJeune et al. (2022). and
for which we also provide further empirical support in this work in Appendices A.2 and A.3
While the form of the relationship between the original and implicit regularization parameters À and y in Theorem I may seem complicated, the remarkable fact is that our GCV consistency results in the next section are agnostic to the specific form of any of the quantities involved (such as SS and jt). That is, GCV is able to make the appropriate correction in a way that adapts to the specific choice of sketch, such that the statistician need not worry. Nevertheless, for the interested reader we provide a listing of known examples of sketches satisfying Assumption A and their corresponding S-transforms in Table 4 in Appendix A.4 parameterized by q/p.
We first state a result on the decomposition of squared risk and the GCV estimator. Here we let Bridge denote the ridge estimator fit on unsketched data at the implicit regularization parameter jr. Theorem 2 (Risk and GCV asymptotics). Suppose Assumption holls, and that the operator norm of E and second moment of yo are uniformly bounded in P. Then, for X > do and all K,
A
R(3que) ~ ((3ridgge)
and R( = ((3rrdgge) +
(8)
K
K
where ps is as given in Theorem A = ( non-negutive inflation factor in the risk that only depends on SSsT, E, and E, while μ² 3 is certain non-negative inflation factor in the risk estimator that only depends on ISST and Σ.
- 3 O. and μí 2 0 is certain
In other words, this result gives bias-variance decompositions for both squared risk and its GCV estimator for sketched ensembles. The result says that the risk of the sketched predictor is equal to the risk of the unsketched equivalent implicit ridge regressor (bias) plus a term due to the randomness of the sketching that depends on the inflation factor μí' or !1" (variance), which controlled by the ensemble size at a rate of I/K (see Figure G.1 for numerical verification of this rate).
We refer the reader to Theorem 16 in Appendix C for precise expressions for p' and n², and to LeJeune et al. (202)) for illustrations of their relationship of these parameters with and X in the case of i.i.d. sketching. For expressions of limiting non-sketched risk and GCV for ridge regression, we also refer to Patil al. (2021), which could be combined with (8) to obtain exact formulas for asymptotic risk and GCV for sketched ridge regression, or to Bach (2024) for exact squared risk expressions in the i.i.d. sketching case for K
For our consistency result, we impose certain mild random matrix assumptions on the feature vectors and assume mild bounded moment condition on the response variable. Notably, we do not require any specific model assumption on the response variable y in the way that it relates to the feature vector Thus, all of our results are applicable in model-free setting.
"The original theorem in Leleune al. 2022 was given for complex À and μr, but the stated version follows by analytic continuation the real line.
5

---

Published as a conference paper at ICLR 2024
RCVI
RKA-Sen
0.6
0.00
R2
+
GUV
Test
0.3
Squared risk. Rt
0.00
0.005
Closdiiion doociioooo CITSC
-0.000
Clocelicatoon
0.08
0.004
0.00
0.2
0.01
0.0
0.0
0.00
10
10
30
100
1000
50 100 1000
Regularization strength
Regulatization strengeh
Figure 2: GCV provides very accurate risk estimates for real-world data. We fit ridge regression ensembles of size K 5 using CountSketch (Charikar et al.] 2004) on binary +1 labels from RCVI (Lewis et al. 2004)
(n 20000. p 30617, q 515) (left) and RNA-Seq [Weinstein et al. 2013) (n 356, p 20223, 4 99) (right). GCV (dashed, circles) matches test risk (solid, diamonds) and improves upon 2-fold CV (dotted) for both squared error (blue, green) and classification error (orange, red). CV provides poorer estimates for less positive X, heavily exaggerated when n is small such as in RNA-Scq. Error bars denote std. dev. over 10 trials.
Assumption B (Data structure). The feature vector decomposes as Σ1/2z, where z E TRP contains i.i.d. entries with mean O, variance 1, bounded moments of order 4 4 5 for some å >> 0, and Σ _2xp a symmetric matrix with eigenvalues uniformly bounded between Tmin > 0 and Fmax < 00. The response has mean O and bounded moment of order 4 + 8 for some 8 > 0.
The assumption of zero mean in the features and response is only done for mathematical simplicity. To deal with non-zero mean, one can add (unregularized) intercept to the predictor, and all of our results can be suitably adapted. We apply such an intercept in our experiments on real-world data.
It has been recently shown that GCV for unsketched ridge regression is an asymptotically consistent estimator of risk (Patil et al. 2021), so given our viriiner decomposition in (8), the only question is whether the variance term from GCV is a consistent estimator of the variance term of risk. This indeed turns out to be the case, as we state in the following theorem for squared risk.
Theorem (GCV consistency). Under Assumptions A and B for X do and all K, holds that pl n", and therefore (( ((33))).
The remarkableness of this result is its generality: we have made no assumption on a particular choice of sketching matrix (see Figure I or the size K of the ensemble. We also make assumption other than boundedness on the covariance Σ, and we do not require any model on the relation of the response the data. Furthermore, this result is not marginal but rather conditional on X, y, (Sx) meaning that we can trust GCV to be consistent for tuning on a single learning problem. We also emphasize that our results holds for positive, zero, and even negative À generally speaking. This is important, as negative regularization can be optimal in ridge regression in certain circumstances (Kobak et al.) 2020 Wu & Xu 2020 Richards al. 202T) and even more commonly in sketched ridge ensembles (LeJeune et al. 2022). as we demonstrate in Figure 2
Observe that for K 1, that is, sketched ridge regression, one can absorb the sketching matrix into the data matrix X such that the transformed data X XS satisfies Assumption B We therefore directly obtain the consistency of GCV in this case using results of Patil et al. (2021), The novel aspect of Theorem 3 is thus that the consistency of GCV holds for ensembles of any K, which is not obvious, due to the interactions across predictors in squared error. The non non-triviat triviality of this result is perhaps subtle: one may wonder whether GCV is always consistent under any sketching setting. However, as we discuss later in Proposition 7 when sketching observations, GCV fails to be consistent, and so we cannot blindly assert that sketching and GCV are always compatible.
4 GENERAL FUNCTIONAL CONSISTENCY
In the previous section, we obtained elegant decomposition for squared risk and the GCV esti- mator that cleanly captures the effect of ensembling as controlling the variance from an equivalent unsketched implicit ridge regression risk at rate of 1/K. However, are also interested in using GCV for evaluating other risk functionals, which do not yield bias variince decompositions.
leverage the close connection between GCV and LOOCV to prove the consistency for a broad class of subquadratic risk functionals. As a result, we also certify that the distribution of the GCV-corrected predictions converges to the test distribution. We show convergence
Fortunately, however,

---

Published as a conference paper at ICLR 2024
Convistent coweagg
Tining Internal widsh
Joint cistribution Pen 50%
GCV retimate Pens
Intervel coverage
Interral width
5.0
Trae resprroseee
98% P3
WA PI 9G% P1
0:90
2.0
1.5
0.9-
0.225
0.50
0.75
1.00
0.25
0.50
0.75
1.00
-0.5
1.0
-1.0
-0.5
0.0
0.5
Stetch
size ratio
Sketch size ratão
Test predictions
GCV-corrected predictions
Figure 3: GCV provides consistent prediction intervals (PIs) and distribution estimates. Left: We construct GCV prediction intervals for SRDCT ensembles of size K = 5 to synthetic data (n = 1500, p 1000) with nonlinear responses y soft threshold(x (b). Mid-left: We use GCV to tune model to optimize
prediction interval width. Right: The empirical GCV estimate Pxmm (here for 0.68) closely matches the true joint response-predicee prediction distribution Pa Error bars denote standard deviation over 30 trials.
for all error functions t in 3 satisfying the following subquadratic growth condition, commonly used in the approximate message passing (AMP) literature (see, e.g., [ayati & Montanari, 2011).
Assumption C (Test error structure). The error function t: R² - R is Lipushhtt of order That is, there exists constant L > 0 such that for all u, v E R.? the following bound holds true: [t(u) - t[v)] & L(1 + |ull2 + 2 -12
The growth condition on i. in the assumption above is ultimately tied to assumptions the bounded moment of order 4 + 8 for some 5 > 0 on the entries of the feature vector and the response variable. By imposing stronger the moment assumptions, one can generalize these results for error functions with higher growth rates at the expense of less data generality.
We remark that this extends the class of functionals previously shown be consistent for GCV in ridge regression (Patil et al. 2022),, which were of the residual form t(y z). While the tools needed for this extension are not drastically different, nonetheless conceptually important extension. In particular, this is useful for classification problems where metrics do not have residual structure and for adaptive prediction interval construction. We now state our main consistency result.
Theorem 4 (Functional consistency). Under Assumptions A to for À >> do and all K, f( T(
(10)
Since t(y, 2) = (y - 2)² satisfies Assumption C this result is strict generalization of Theorem 3 This class of risk functionals is very broad: it includes for example robust risks such as the mean absolute error or Huber loss, and even classification risks such as hinge loss and logistic loss.
Furthermore, this class of error functions is sufficiently rich as guarantee that not only do risk functionals converge, but in fact the GCV-corrected predictions also converge in distribution to the predictions of test data. This simple corollary captures the fact that empirical convergence of pseudo-Lipschie functionals of order 2, being equivalent to weak convergence plus convergence in second moment, equivalent Wasserstein convergence (Villani 2008 Chapter 6).
Corollary 5 (Distributional consistency). Under Assumptions and B for X > do and all K, it
holds that Pans 3 Pane, where 3 denotes convergence Wasserstein W2 metric.
Distributional convergence further enriches our choices of consistent estimators that we can construct with GCV, in that we can now construct estimators of sets and their probabilities. One example is classification error E[1 {yo * [xg ",] which can be expressed in terms of conditional probability over discrete yo- our real data experiments in Figure 2 we also compute classification error using GCV and find it yields highly consistent estimates, which is useful as squared error (and
hence ridge) is known to competitive loss function for classification (Hui & Belkin| 2021).
Of statistical interest, we can also do things such as construct prediction intervals using the GCV- corrected empirical distribution. For example, for 7 (0, 1), consider the level-7 quantile Q(T) inf(: F(2) > т) and prediction interval I [ 3 + ((T).. Xp Foms + Q( where F the cumulative distribution function (CDF) of the GCV residuals (y 2): (g.2) ~ pens Then I is prediction interval for yo built only from training data that has the right coverage Tu 7, conditional on the training data, asymptotically almost surely. Furthermore, we can tune our model based on prediction interval metrics such as interval width. We demonstrate this idea in the experiment in Figure 3 This idea could be further extended to produce tighter locally adaptive prediction intervals by leveraging the entire joint distribution Peus rather than only the residuals.
7

---

Published as a conference paper at ICLR 2024
5 TUNING APPLICATIONS AND THEORETICAL IMPLICATIONS
The obvious implication of the consistency results for GCV stated above is that we can also consis- tently tune sketched ridge regression: for any finite collection of hyperparameters (A, o, sketching family, K) over which we tune, consistency at each individual choice of hyperparameters implies that optimization over the hyperparameter set is also consistent. Thus if the predictor that we want to fit to our data is a sketched ridge regression ensemble, direct GCV enables us to efficiently tune it.
However, suppose we have the computational budget to fit a single large predictor, such as unsketched ridge regression or a large ensemble. Due to the large cost of refitting, tuning this predictor directly might be unfeasible. Fortunately, thanks to the bias-variance decomposition in Theorem 2 use small sketched ridge ensembles to tune such large predictors.
we can
The key idea is to recall that asymptotically, the sketched risk is simply a linear combination of the equivalent ridge risk and a variance term, and that we can control the mixing of these terms by choice of the ensemble size K. This means that by choosing multiple distinct values of K. we can solve for the equivalent ridge risk. As concrete example, suppose we have an ensemble of size K = 2 with corresponding risk R₂ R(@que), and let R₃ be the risk corresponding the individual members of the ensemble. Then we can eliminate the variance term and obtain the equivalent risk as
(11) Subsequently using the subordination relation μ = SS (- - Hrr(S ESSS ES +1 from Theorem I we can map our choice of X and S to the equivalent μ.. By Theorem 3 we can the GCV risk estimators for R1 and Rg and have a consistent estimator for ridge risk at μ.. In this way, obtain consistent estimator of risk that can be computed entirely using only the g-dimensional sketched data rather than the full p-dimensional data, which can be computed in less time with a smaller memory footprint. See Appendix H for a detailed comparison of computational complexity.
R(3rldee) = 2R² R1.
We demonstrate this "ensemble trick" for estimating ridge risk in Figure which is accurate even where the variance component of sketched ridge risk is large. Furthermore, even though GCV is not consistent for sketched observations instead of features (see Section the ensemble trick still provides a consistent estimator for ridge risk since the bias term unchanged. One limitation of this method when considering fixed sketch S. varying only A, is that this limits the minimum value of ju that can be considered (see discussion by LeJeune et al. 2022). solution to this is to consider varying sketch sizes, allowing the full range of J > O, as captured by the following result.
Proposition 6 (Optimized GCV versus optimized ridge). Under Assumptions and if ST Sy is invertible, then for any μ 0, if X 0 and K it holds that
R( R( R(@ridde) for a + xI,))=111 1.
(12)
That is, for any desired level of equivalent regularization we can obtain a sketched ridge regressor with the same bias (equivalently, the same large ensemble risk as K .0) by changing only the sketch size and fixing À = 0. A narrower result was shown for subsampled ensembles by LeJeune jet al. (020),, but our generalization provides equivalences for all μ > 0 and holds for any full-rank sketching matrix, establishing that freely sketched predictors indeed cover the same predictive space as their unsketched counterparts. The result also has practical merit. It guarantees that, with a sufficiently large sketched ensemble, retain the statistical properties of the unsketched ridge regression. Thus, practitioners can harness the computational benefits of sketching, such as reduced memory usage and enhanced parallelization capabilities, without loss in statistical performance.
6 DISCUSSION
This paper establishes the consistency of GCV-based estimators of risk functionals. We show that GCV provides a method for consistent fast tuning of sketched ridge ensemble parameters. However, taking step back, given the connection between the sketched pseudoinverse and implicit ridge regularization in the unsketched inverse (Assumption A) and the fact that GCV "works" " for ridge regression (Patil et al. 2021 Wei al. 2022), one might wonder if the results in this paper were "expected"? The introduction of the ensemble required additional analysis of course, but perhaps the results seem intuitively natural.
8

---

Published as a conference paper at ICLR 2024
[K 1)
GCV
Enoemble 2)
Skotching Searre (o 100)
Skonching cherrent-on (m = 100).
Tuning slrishh wise (A =
Squared
3.0
5.0
10F 10 102
100 101 102
10 10" 10'
102
Equivsient regulaticoaionn g
Figure 4: GCV combined with sketching yields a fast method for tuning ridge. We fit SRDCT ensembles on synthetic data (n 600, p 800), sketching features (left and right) or observations (middle). GCV (dashed) provides consistent estimates of test risk (solid) for feature sketching but not for observation sketching. However, the ensemble trick in (IT) does not depend on the variance and thus works for both. For À - 0, each equivalent j > 0 can be achieved by an appropriate choice of a. Error bars denote standard deviation over 50 trials.
Surprisingly (even to the authors), if one changes the strategy from sketching features to sketching observations, we no longer have GCV consisteney for finite ensembles! Consider a formulation where we now sketch observations with K independent sketching matrices Ta E R u2 for k E [K]
x arg min 2/2 T (y- x30] + 2|ll ( T + XI) X T... BERr
(13)
Let the ensemble estimator 3 be defined analogously to ble estimator 3xms is linear smoother with smoothing matrix L K Ek=1 Iz where
Note again that the ensem-
Σ = x the squared risk analogous to 5 The following result shows that R is inconsistent for any K. Proposition 7 (GCV inconsistency
XI) T We can then define the GCV estimator R(3 of
for observation sketch), Suppose assumptions of Theorem 2 hold
for TT. Then, for >> λo lim infp-co
p-20 [i] Amina( ( T,T,, and all K, V" and R(335T)) = (33rdda)) K where v= > - - C T and satisfies V = X. TTT 1- (AXXT + vII)) and K- X2XXXX vI,,)= 3 O, and V, V 3 O are certain non-negative inflation factors. Furthermore, under Assumption B in general we have v' & v", and therefore R( 4 R(33x)).
v'À
R(3xTt) R (3rrizee)
(14)
K
For precise expressions of v' and v", we defer readers to Proposition 19in Appendix F Note that as K- oc, the variance terms vanish and we get back consistency; for this reason, the "ensemble trick" in I still works. This negative result highlights the subtleties in the results in this paper, and that the GCV consistency for sketched ensembles of finite K is far from obvious and needs careful analysis to check whether it is consistent. This result is similar in spirit to the GCV inconsistency results of Bellec al. (2023) and Patil et al, (2024) in subsampling and early stopping contexts, respectively.
is still possible to correct GCV in our case, as we detail in Appendix F2 using unsketched data.
While our results are quite general in terms of being applicable to a wide variety of data and sketches, they are limited in that they apply only to ridge regression with isotropic regularization. However, we believe that the tools used in this work are useful in extending GCV consistency and the understanding of sketching to many other linear learning settings. It is straightforward to extend our results beyond isotropic ridge regularization. We might want to apply generalized anisotropic ridge regularization in real-world scenarios: generalized ridge achieves Bayes-optimal regression when the ground truth coefficients in a linear model come from an anisotropic prior. We can cover this case with a simple extension of our results; see Appendix F3
Going beyond ridge regression, we anticipate that GCV for sketched ensembles should also be consistent for generalized linear models with arbitrary convex regularizers, as was recently shown in the unsketched setting for Gaussian data (Bellec 2023). The key difficulty in applying the analysis based on Theorem to the general setting is that we can only characterize the effect of sketching as additional ridge regularization. One promising path forward is via viewing the optimization as iteratively reweighted least squares (IRLS). On the regularization side, IRLS can achieve many types of peccuure-promoting regularizers (see LeJeune et al. 202T and references therein) via successive generalized ridge, and so we might expect GCV to also be consistent in this case. Furthermore, for general training losses, we believe that GCV can be extended appropriately to handle reweighting of observations and leverage the classical connection between IRLS and maximum likelihood estimation in generalized linear models. Furthermore, to slightly relax data assumptions, the closely related approximate leave-one-out (ALO) risk estimation (Xu et al. 2019 Rad & Maleki 2020), which relies on fewer concentration assumptions for consistency.
extend GCV to

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We are grateful Ryan J. Tibshirani for helpful feedback on this work. We warmly thank Benson Au, Roland Speicher, Dimitri Shlyakhtenko for insightful discussions related to free probability theory and infinitesimal freeness. We also warmly thank Arun Kumar Kuchibhotla, Alessandro Rinaldo, Yuting Wei, Jin-Hong Du, Alex Wei for many useful discussions regrading the "dual" aspects of observation subsampling in the context of risk monotonization. As the nature of direction reversing and side flipping dualities in general, the insights and perspectives gained from that observation side are naturally "mirrored" and "transposed" onto this feature side (with some important caveats)! Finally, we sincerely thank the anonymous reviewers for their insightful and constructive feedback, which improved the manuscript, particularly with the addition of Appendix H
This collaboration partially supported by Office of Naval Research MURI grant N00014-20-1 2787. DL was supported by Army Research Office grant 2003514594.
REFERENCES
Ben Adlam and Jeffrey Pennington. The neural tangent kernel in high dimensions: Triple descent and a multi-scale theory of generalization. In International Conference on Machine Learning, 2020.
Amirali Aghazadeh, Ryan Spring, Daniel Leleune, Gautam Dasarathy, Anshumali Shrivastava, and Richard G. Baraniuk. MISSION: Ultra large-scale feature selection using count-sketches. In International Conference Machine Learning, 2018.
Ryo Ando and Fumiyasu Komaki. On high-dimensional asymptotic properties of model averaging estimators. arXiv preprint arXiv:2308.094700 2023.
Sylvain Arlot and Alain Celisse. A survey of cross-validation procedures for model selection.
Statistics surveys, 4:40-79, 2010.
Francis Bach. High-dimensional analysis of double descent for linear regression with random projections. SIAM Journal on Mathematics of Data Science, 6(1):26-50, 2024.
Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(49):30633-30077 2020.
Mohsen Bayati and Andrea Montanari. The dynamics of message passing on dense graphs, with applications to compressed sensing. IEEE Transactions on Information Theory, 57(2):764-785. 2011.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4):1167-11800 2020.
Pierre Bellec, Jin-Hong Du, Takuya Koriyama, Pratik Patil, and Kai Tan. Corrected generalized cross-validation for finite ensembles of penalized estimators. arXiv preprint arXiv:2310001374. 2023.
Pierre C. Bellec. Out-of-sample error estimation for M-estimators with convex penalty. Information and Inference: A Journal of the IMA, 12(4):2782-2817, 2023.
Pierre C. Bellec and Yiwei Shen. Derivatives and residual distribution of regularized M-estimators with application to adaptive tuning. In Conference on Learning Theory, 2022.
Philippe Biane. Processes with free increments. Mathematische Zeitschrift, 144411444,, 1998.
Arup Bose. Random Matrices and Non-commutative Probability. CRC Press, 2021.
Lars Buitinck, Gilles Louppe, Mathieu Blondel, Fabian Pedregosa, Andreas Mueller, Olivier Grisel, Vlad Niculae, Peter Prettenhofer, Alexandre Gramfort, Jaques Grobler, Robert Layton, Jake VanderPlas, Arnau Joly, Brian Holt, and Gaël Varoquaux. API design for machine learning software: experiences from the seikit-learn project. In ECML PKDD Workshop: Languages for Data Mining and Machine Learning, 2013.
10

---

Published as a conference paper at ICLR 2024
Guillaume Cébron, Antoine Dahlqvist, and Franck Gabriel. Freeness of type B and conditional freeness for random matrices. arXiv preprint OrXiv:2205.01922 2022.
Michael Celentano, Andrea Montanari, and Yuting Wei. The Lasso with general Gaussian designs with applications hypothesis testing. The Annals of Statistics, 51(5):2194 2220, 2023.
Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items data streams. Theoretical Computer Science, 3 312(1)33-15, 2004. ISSN 0304-3975.
Xin Chen, Yicheng Zeng. Siyue Yang, and Qiang Sun. Sketched ridgeless linear regression: The role of downsampling. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pp. 5296-5326. PMLR, 2023.
Shabarish Chenakkod, Michal Derezinski, Xiaoyu Dong, and Mark Rudelson. Optimal embedding dimension for sparse subspace embeddings. arXiv preprint arXiv:2311.10680, 2023.
Peter Craven and Grace Wahba. Estimating the correct degree of smoothing by the method of generalized cross- volidaaali, Numerische Mathematik, 31:377-403, 1979.
Michat Dereziński, Jonathan Lacotte, Mert Pilanci, and Michael W Mahoney. Newton-LESS: Sparsi- fication without trade-off's for the sketched Newton update. In Advances in Neural Information Processing Systems, 2021a.
Michat Dereziáski, Zhenyu Liao, Edgar Dobriban, and Michael Mahoney. Sparse sketches with small inversion bias. In Proceedings of Conference on Learning Theory, 2021b.
Edgar Dobriban and Yue Sheng. WONDER: Weighted one-shot distributed ridge regression in high dimensions. Journal of Machine Learning Research, 21(66): 2020.
Edgar Dobriban and Yue Sheng. Distributed linear regression by averaging. The Annals of Statistics, 49(2):918 1-9933,89--99999 2021.
Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-279, 2018.
Jin-Hong Du, Pratik Patil, and Arun Kumar Kuchibhotla. Subsample ridge ensembles: Equivalences and generalized cross-validation. International Conference on Machine Learning, 2023.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL attp:://rcchiv
ics. www.cciiio edu/ml
A. Girard. A fast Monte-Carlo cross cooss-vlliattinn procedure for large least squares problems with noisy data. Numerische Mathematik, 56(1):1-23, 1989.
Gene H. Golub, Michael Heath, and Grace Wahba. Generalized cross-validation as a method for choosing good ridge parameter. Technometrics, 21(2):215-223, 1979.
Qiyang Han and Xiaocong Xu. The distribution of ridgeless least squares interpolators. arXiv preprint arXiv:2307.02044: 2023.
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning. Springer Series in Statistics, 2009. Second edition.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949 9866 2022.
Like Hui and Mikhail Belkin. Evaluation of neural architectures trained with square loss vs cross- entropy classification tasks. In International Conference on Learning Representations, 2021.
M. F. Hutchinson. stochastic estimator of the trace of the influence matrix for laplacian smoothing splines. Communications in Statistics Simulation and Computation, 18(3):1059-1076 1989.
Dmitry Kobak, Jonathan Lomond, and Benoit Sanchez. The optimal ridge penalty for real-world high-dimentn dimeessonnii data can be zero or negative due to the implicit ridge regularization. Journal of Machine Learning Research, 21: 21:169-1, 2020.
11

---

Published as a conference paper at ICLR 2024
Jonathan Lacotte, Sifan Liu, Edgar Dobriban, and Mert Pilanci. Optimal iterative sketching methods with the subsampled randomized Hadamard transform. In Advances in Neural Information Processing Systems, 2020.
Daniel LeJeune, Hamid Javadi, and Richard Baraniuk. The implicit regularization of ordinary least squares ensembles. In International Conference on Artificial Intelligence and Statistics, 2020.
Daniel LeJeune, Hamid Javadi, and Richard G. Baraniuk. The flip side of the reweighted coin: Duality of adaptive dropout and regularization. In Advances in Neural Information Processing Systems, 2021.
Daniel LeJeune, Pratik Patil, Hamid Javadi, Richard G. Baraniuk, and Ryan J. Tibshirani. Asymptotics of the sketched pseudoinverse. arXiv preprint arXiv:221 1.0222211.037,,, 2022.
David Lewis, Yiming Yang. Tony Russell-Rosse Rose,, and Fan Li. RCVI: A new benchmark collection for text categorization research. Journal of Machine Learning Research, 5:361-397, 2004.
Ker-Chau Li. From Stein's unbiased risk estimates the method of generalized cross validation. The Annals of Statistics, 1985.
Ker-Chau Li. Asymptotic optimality of Cr. and generalized cross-validation ridge regression with application to spline smoothing. The Annals of Statisties, 14(3):1101-1112, 1986.
Sifan Liu and Edgar Dobriban. Ridge regression: Structure, cross-validation, and sketching. In International Conference Learning Representations, 2020.
Michael W. Mahoney. Randomized algorithms for matrices and data. Foundations and Trends in Machine Learning, 3(2):123-22))) 224,, 2011.
James A. Mingo and Roland Speicher. Free Probability and Random Matrices. Springer, 2017.
Riley Murray, James Demmel, Michael W. Mahoney, N. Benjamin Erichson, Maksim Melnichenko, Osman Asif Malik, Laura Grigori, Piotr Luszezek, Michal Dereziński, Miles E. Lopes, Tianyu Liang, Hengrui Luo, and Jack Dongarra. Randomized numerical linear algebra: A perspective on the field with an eye to software. arXiv preprint arXiv:2302.1 /474, 2023.
Mojmir Mutny, Michal Dereziński, and Andreas Krause. Convergence analysis of block coordinate algorithms with determinantal sampling. In International Conference on Artificial Intelligence and Statistics, 2020.
Pratik Patil and Jin-Hong Du Generalized equivalences between subsampling and ridge regularization. Advances in Neural Information Processing Systems, 36, 2024.
Pratik Patil, Yuting Wei, Alessandro Rinaldo, and Ryan Tibshirani. Uniform consistency of cross- validation estimators for high-dimensional ridge regression. In International Conference on Artificial Intelligence and Statistics, 2021.
Pratik Patil, Alessandro Rinaldo, and Ryan Tibshirani. Estimating functionals of the out-of-sample error distribution in high- nigh-dimensional ridge regression. In International Conference on Artificial Intelligence and Statistics, 2022.
Pratik Patil, Jin-Hong Du, and Arun Kumar Kuchibhotla. Bagging in overparameteriize learning: Risk characterization and risk monotonization. Journal of Machine Learning Research, 24(319); 1-113, 2023.
Pratik Patil, Yuchen Wu, and Ryan Tibshirani. Failures and successes of cross- vross-validation for early- stopped gradient descent. In International Conference Artificial Intelligence and Statistics, 2024.
Kamiar Rahnama Rad and Arian Maleki. A scalable estimate of the out-of-sample prediction error via approximate leave-one-out cross- moos-vvaliation. Journal of the Royal Statistical Society: Series (Statistical Methodology), 82(4):965-996, 2020.
12

---

Published as a conference paper at ICLR 2024
Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. Asymptotics of ridge (less) regression under general source condition. In International Conference on Artificial Intelligence and Statistics, pp. 3889-3897, PMLR, 2021.
Dimitri Shlyakhtenko. Free probability of type-B and asymptotics of finite-rank perturbations of random matrices. Indiana University Mathematics Journal, 67(2):971-991, 2018.
Terence Tao. Topics in Random Matrix Theory, volume 132. American Mathematical Society, 2023.
Gian-Andrea Thanci, Christina Heinze, and Nicolai Meinshausen. Random projections for large-scale regression. In Big and Complex Data Analysis, Contributions to Statistics. Springer, 2017.
Joel A. Tropp. Improved analysis of the subsampled randomized Hadamard transform. Advances in Adaptive Data Analysis, 03:1 15-126, 2011.
Antonia M Tulino and Sergio Verdú. Random matrix theory and wireless communications, Founda- tions and Trends in Communications and Information Theory, 1(1):1-182, 2004.
Cédric Villani. Optimal Transport: Old and New. Springer, 2008
Dan V. Voieulescu. Free Probability Theory. American Mathematical Society, 1997.
Alexander Wei, Wei Hu, and Jacob Steinhardt. More than toy: Random matrix models predict how real-world neural representations generalize. arXiv preprini arXiv:2203.06/76, 2022.
John N Weinstein, Eric A Collisson, Gordon B Mills, Kenna R Mills Shaw, Brad A Ozenberger, Kyle Ellrott, Ilya Shmulevich, Chris Sander, and Joshua M Stuart. The Cancer Genome Atlas Pan-Cancer analysis project. Nature Genetics, 45(10): 113-1112111100 2013.
David P. Woodruff. Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-157, 2014.
Denny Wu and Ji Xu. On the optimal weighted l regularization in overparameterized linear regression. Advances in Neural Information Processing Systems, 33:101 12-1012, 2020.
Xu, Arian Maleki, and Kamiar Rahnama Rad. Consistent risk estimation in high dibbeemmeniinall linear regression. arXiv preprint arXiv: 1902.0//3, 2019.
Yongli Zhang and Yuhong Yang. Cross-validation for selecting model selection procedure. Journal of Econometrics, 187(1):95-11) 1122, 2015.
13

---

Published as a conference paper at ICLR 2024
SUPPLEMENTARY MATERIAL
This serves supplement to the paper " "Asymptotically Free Sketched Ridge Ensembles: Risks, Cross- Validation, and Tuning." " Below we first provide an outline for the supplement in Table Then we list some of the general and specific notations used throughout the main paper and the supplement Tables and respectively.
OUTLINE
Appendix
Content
Appendix A
Background asymptotic freeness and empirical support for sketching freeness
Appendix B
Asymptotic equivalents for freely sketched resolvents used in the proofs throughout
Appendix
C
Proofs of Theorem and Theorem (from Section
Appendix D
Proofs of Theorem and Corollary 5 (from Section
Appendix
Proof of Proposition 6 from Section
Proof of Proposition 7 and statements and other details for anisotropic sketching,
Appendix
F
generalized ridge regression, and observation sketch (from Section 6
Appendix G
Additional experimental illustrations and setup details for Figures to
Appendix
H
Comprehensive complexity comparisons of various cross methods
Table I: Roadmap of supplement.
GENERAL NOTATION
Notation
Description
Non-bold Lowercase bold
Denotes scalars, functions, distributions etc. (e.g.. h. f, P) Denotes vectors (e.g., x. Denotes matrices (e.g., S, M)
Uppercase bold
R. R
Set real and non-negative real numbers
C, CCCCC. C-
Set of complex numbers, and upper and lower complex half-planes Set (I...., n for natural number Indicator random variable associated with an event
[n]
{(A)
ulpp |//l
The C, norm of vector and the I, norm of function f for p 3 1 Operator (or spectral) and trace (or nuclear) norm of a rectangular matrix X Raxp
Xloo [
tr[A], A
Trace and inverse (if invertible) of square matrix A E Rexp Rank, transpose and Moore-Penrose inverse of a rectangular matrix B E R"xp Principal square root of a positive semidefinite matrix C C Roxp The identity matrix
rank(B) BB, B B²
C
I, I
O,0
Deterministic big-O and little-o notation Lexicographic ordering for real vectors u and v Loewner ordering for symmetric matrices A and B
u & v
A B
Op pi Op
Probabilistic big-O and little-o notation
B
Asymptotic equivalence of matrices and (see Appendix B for details)
Almost sure convergence, convergence in probability, and weak convergence Convergence in Wasserstein W2, metric
3
Table 2: Summary of the general notation used throughout the paper and the supplement.
14

---

Published as a conference paper at ICLR 2024
SPECIFIC NOTATION
Symbol
Meaning
((x;, ())
Train dataset containing n. i..dd observations in RP R
(X, y)
Train data matrix (X1,..., .1,. in x and response vector = (y1,... Un) in TR"
(Xo, y0)
Test point in Rº R drawn independently from the train data distribution Population covariance matrix in RP*P; E[xox,]
Σ
30
Coefficients of population linear projection of yo onto Xn in R Σ [
Σ
Sample covariance matrix in RexP: n _
@ridge
Ridge estimator on full data (X,y) y) at regularization level A: ( - Ensemble size
K
k=
Sketching matrices in RPx* (for feature sketch) Sketching aspect ratio
k-th component estimator in the sketched ensemble R (sketch space) regularization level X
k-th component estimator in the sketched ensemble in R (feature space)
L
Smoothing matrix of the k-th component estimator in the sketched ensemble in RRxx
8xm
Final sketched ensemble estimator in IRP: * >>> 1
Smoothing matrix of the sketched ensemble estimator in RaXX; Σ X
Joint distribution of test response and test predicted values of the sketched ensemble estimator (for feature sketch) at regularization level À
Peus
R(Gens)
Squared risk of the sketched ensemble estimator
T(Ggua)
General linear risk functional of the sketched ensemble estimator
Estimated joint distribution of test response and test predicted values of the sketched ensemble (for feature sketch) at regularization level À using GCV residuals Estimated squared risk of the sketched ensemble estimator
Pans
((
Estimated general linear functional of the sketched ensemble estimator
Effective induced regularization level of the sketched ensemble estimator (for feature sketch) with original regularization level X Inflation factor the squared risk decomposition of the sketched ensemble estimator Inflation factor in the GCV decomposition for the sketched ensemble estimator
a"
(T
Sketching matrices m*xm (for observation sketch)
17
Sketching aspect ratio 7) m
k-th component estimator in the sketched ensemble in RP (feature space) at regularization level
3
LA
Smoothing matrix of the k-th component estimator the sketched ensemble Raxx
gous
Final sketched ensemble estimator in IRP: * Σ
Σk=1 3
Smoothing matrix of the sketched ensemble estimator paxn,
1
Σ Σ
K
Squared risk of the sketched ensemble estimator (for observation sketch) regularization level X
R( ((3x))))
R ((,3gmm))
Estimated squared risk of the sketched ensemble estimator using GCV
Effective induced regularization level of the sketched ensemble estimator (for observation sketch) with original regularization level À
v'
Inflation factor in the squared risk decomposition of the sketched ensemble estimator Inflation factor in the GCV decomposition for the sketched ensemble estimator
"
SSST -TTT
S S-transform of the spectrum of SST RPxP (for feature sketch)
S S-transform of the spectrum of TTT Raxn (for observation sketch)
Table 3: Summary of the specific notation used throughout the paper and the supplement.
15

---

Published as a conference paper at ICLR 2024
A BACKGROUND ON ASYMPTOTIC FREENESS AND FREE SKETCHING SUPPORT
Free probability (Voiculescu 1997> is a mathematical framework that deals with non-commutative random variables. One of the key concepts in free probability is asymptotie freeness, which studies the behavior of random matrices in the limit as their dimension tends to infinity. This notion enables us understand how independent random matrices become uncorrelated and behave as if they were freely independent in the sigh-dimensional limit. Good full-length references on free probability theory include: Mingo Speicher (2017), Bose (202T). Chapters 2.4 and 2.5 from Tulino & Verdu (2004) and Tao (023), respectively, are enjoyable introductions.
A.1 FREE PROBABILITY THEORY
We begin with few definitions from Mingo Speicher (017).
Definition (C*- -C*-probability space and state). A pair (A, is called non-commutative C*- probability space if A is a unital C* -algebar and the linear functional yp: A - Cs a unital state: ie., (1() and ((a*a) > for all A.
Definition 9 (Freeness). Let (A, .p) be C**-probaiility space and let (Ai,..., As) be unital subalgebras A. Then (AI..... are free with respect to yp if, for any r > 2 and aj...., a, E A such that (p(a.) 0 for all < & and a; Aj, for j: Ji-1 for all 1 i & cp(a ... a,) = 0. Furthermore, we say that elements (1,,..., E A are free with respect to y if the corresponding generated unital algebras AI....,AA Ag free.
have
That is. we say that elements of the algebra are free if any alternating product of centered polynomials also centered.
In this work, we will consider yp to be the normalized trace that is, the generalization of } tr[ A] for A CP to elements C** -algebra A. Specifically, for any self-adjoint E A and any polynomial p.
p(p(a)) p(2) (o(=)ddp) (=).
where Pa is the probability measure characterizing the spectral distribution of a. spectral distribution). Let (A, sp) be C* c*-ppobbbbility space. We say
Definition 10 (Convergence that Ai..., Am E CP converge in spectral distribution to elements al...., am E A if for all 1 & l d and & iz & m for j & we have
1 tr A,, -p(at, ... a.,).
One limitation of standard free probability theory is that it does not allow consider general expressions of the form tr [A] when @ has bounded trace norm, as this would require us to use an unbounded operator θ pO to evaluate [tr[ but such an unbounded θ cannot be element of a -llabgebr.. However, evaluation of such expressions is possible with an extension called infinitesinal free probability (Shlyakhtenko) 2018). which is used in Theorem from LeJeune eet al. (2022) that our results build upon.
Definition 11 (Infinitesimal freeness). Unital subalgebras A1, A2 A are infinitesimally free with respect to (sp, sp') if, for any > 2 and 01....,a, Or e A where a, E Aj. for js Ji+1 for all 1 i r 1, we have
ppl(a] (a(()) ... (a, (=())))) = o(l),
where it 40 + tip'.
We lastly introduce series of invertible transformations for element of a C* -probabibiiy space:
G=(z) = (([== - ([([=a)--)
Ma = -G_ (
- ( -1 -a(a) = 1 + 2 M (x))
which are the Cauchy transform (negative of the Stieltjes transform), moment generating series M2(2) = Ei )a*, and S-transform of a, respectively. Here M denotes inverse under composition of M..
16

---

Published as a conference paper at ICLR 2024
Asymptotic freeness
Empirical matching of Iss
A
tt/ppoyyAA Ss ]]
10-1
XXX00X
Skethh
0O000
SRDCT
10a
Gaussian
10"2
Orthogonal
10
10a
10
10-3
1/p
10
Sketch
10-22
SRDCT
10"
500
750
1000
1500
2000
3000
A(A (I,)
Figure A.1: Empirical support for asymptotic freeness and subordination relation. Left: plot absolute value the average of the normalized traces of polynomials, which converge to zero. We also plot best fit lines on the log-log scale (dashed). Error bars denote one standard deviation over 10 trials, collected over both polynomials. Right: We numerically compute μ and plot the empirical subordination relation, which are decreasing continuous functions that closely match the thcoretical S- S-transforms of Gaussian (dashed) for CountSketch (x) and orthogonal (dash-dac dot) for SRDCT (o). Each mark in the seatter plots corresponds to a single (A, A) pair, and we solve for the corresponding
A.2 ASYMPTOTIC FREENESS
Freeness characterized by certain non-commutative centered alternating product condition (see Definition (9) with respect to a state function. With some slight abuse of notation, we consider the state function p -tr[-]. Then two matrices A, RR* would said to be free if
fir II poly (A)poly? B (B) = O,
for all L > 1 and all centered polynomials-ice tr (A)] O. The reason this is an abuse of notation that finite matrices cannot satisfy this condition; however, they can satisfy asymptotically as p - s0, and in this case we say that A and B are asymptotically free.
We this property for CountSketch and SRDCT for polynomials of the form
poly, A ]
Specifically, we arbitrarily pick two choices
poly A, B) poly, (B)poly
and
poly A, B) poly; (A)poly (oly (A)
and evaluate " (ir[poly(A,))) J]] for increasing over trials, where A a diagonal matrix with values linearly interpolating between 0.5 and 1.5 along the diagonal. As we see in Figure/A.T] for both sketches, this normalized trace is quite small and tending to zero. This strongly supports the assumption that CountSketch and SRDCT are both asymptotically free from diagonal matrices, and we expect the same to hold is rotated to be non-diagonal independently of the sampling of the sketching matrix S.
A.3 EMPIRICAL SUBORDINATION RELATIONS
A.3.1 EXPERIMENTS SYNTHETIC DATASETS
Suppose & and T are free and Theorem holds. This means that a subordination relation via Isss should characterize the implicit regularization, we test this implication empirically well. Specifically, without using any known form for SSST, we empirically verify that this mapping does not depend on X and compare to known S-transforms.
17

---

Published as a conference paper at ICLR 2024
RCV1 (p 30617)
R.N.A -Se (p 20223)
10a
10"
515
495
1030
x
990
1957
3 X 10
1980
10a
4944
4950
9991
2 10"
9999
109
0.3
-0.2
-0.1
0.0
00011-0.000--0 001.00111000000000000 0.000
(E [
tr 3 إ
CkentSketch
SRDCT
Gaussian
Orthogonal
Figure A.2: Empirical support for subordination relation with real data. We numerically compute and plot the empirical subordination relation for sketches of real data (RCVI (left) and RNA-Seq (right)) using CountSketch (black, solid) SRDCT (black, dotted), which almost exactly match theoretical S-transforms for Gaussian (dashed) and orthogonal (dash-dot) sketching, shown here for a single trial of random sketching for each value of As g/p tends to zero, the subordination relation of all four sketches becomes indistinguishable
As in the previous section, we will simplify our tests by considering diagonal A instead of E. We generate a family of diag (a) parameterized by ag. Su > O, and to [0, 1] as
ag
i i-1
where t,
1 e- (1: to)/s0
p
This family spans variety of spectral distributions and provides rich class of matrices over which Theorem must hold simultaneously. For a fixed 700 x 585 sketching matrix that we sample for CountSketch and for SRDCT, we sampled A over 5 x 5 grid of ag and so logarithmically spaced between 0.1 and 10 and ln linearly spaced between and 1. For each A, we used numerical root finding determine μ such that
tr AS(S AS + AI,) AL,)''' ST ST
1tr AAA+ p
for each E (0.01, 1, 1, 10, 100). Then we construct a scatter plot of p/a and tr + + in Figure A. (right), which should match 'ss and be decreasing continuous function. We that this is indeed the case, and furthermore by also plotting the known S-transform for Gaussian and orthogonal sketches from Table see that CountSketch matches the Gaussian function and SRDCT matches the orthogonal function.
A.3.2 EXPERIMENTS ON REAL DATASETS
We repeat the experiment in Figure A.1 for real data in Figure A.2
using X X instead of A. For RCV1, since _X X is very high dimensional and matrix inversion is costly, we perform randomized trace estimation using the formula
1 tr 1 X kI,
1z ( (1X mII - Xz.
where z RP an i.i.d. Rademacher vector and the inversion computed using the conjugate gradient method. Additionally, due to the size of RCV1, we only evaluate the subordination relation for CountSketch which can be efficiently applied due to the sparsity of the data, and do not evaluate the SRDCT. We precompute the traces for both sketched and unsketched sides of the subordination relation for a range of values of and μ and then construct the mapping via linear interpolation. Since p for RNA-Seq (see Appendix G.2 the normalized traces upper bounded by n/p 446/20223 s 0.022, which limits the operating range of the subordination relation and therefore the r-axis of the plot from 0.022
18

---

Published as a conference paper at ICLR 2024
A.4 KNOWN S-TRANSFORMS
We state some known S-transforms in the following table, where we let a = q/p. We also assume that S is normalized such that SS p. following LeJeune et al. (2022). For the i.i.d. sketch, this is simply the S-transform of the Marchenko-Pastie distribution, and for the orthogonal sketch, it is the S-transform of binary distribution on {0. 1. The identity sketch refers simply S = Ip. There is currently no known S S-transform for CountSketch, although our experiments in the previous sections suggest it similar for i.i.d. sketches
Sketching family:
IID
Orthogonal, SRFT
Identity
SST (w):
(1+
1
a+w
a++
Table 4: Known S-transforms for normalized sketches
B ASYMPTOTIC EQUIVALENTS FOR FREELY SKETCHED RESOLVENTS
In this section, we provide brief background on the language of asymptotic equivalents used in the proofs throughout the paper. We will state the definition of asymptotic equivalents and point to useful calculus rules. For more details, sobribban & Wager (2018) Dobriban & Sheng (2021 LeJeune iet al. 2022).
We the language of asymptotic equivalents throughout the paper, defined formally as follows. Definition 12 (Asymptotic equivalence). Consider sequences (Ap)pæ1 and (Bp) of (random or deterministic) matrices of growing dimension. We say that Ap and B, are equivalent and write Ap B, if limp-on [tr[ Cp Ap BB)]] 0 almost surely for any sequence Cp matrices with bounded trace norm such that lim sup Cp tr < as - 00.
The notion of deterministic equivalents obeys various calculus rules such sum, product, differ- entiation, conditioning, substitution, among others. We refer readers to Patil et al. (2023) for a comprehensive list of these calculus rules, their proofs, and other related details.
B. KNOWN ASYMPTOTIC EQUIVALENTS FOR ORDINARY RIDGE RESOLVENTS
In this section, we collect known asymptotic equivalents for the first- and second-order ordinary ridge resolvents. See Hastie et al. (2022) Patil et al. (2023) for more details.
Lemma 13 (Deterministic equivalents for first-order and second-order ordinary ridge resolvents). Suppose Assumption B holds. Then, for μ
-X+ min [ X), the following statements hold:
1. First-order ordinary ridge resolvent:
E plp (+++1,)+
(B.1)
where -1 is the most positive solution to
== ,= 1 I,
(B.2)
2. Second-order ordinary ridge resolvent (population version):
1² + p 2SS + udp) -1 = (1 (v) + I
(B.3)
where defined in B.2). and To is defined in terms of v by the equation
7 t 1 I,)+I
Ü v 2ー -ーーー
(B.4)
2 1 (1)+ "
3. Second-order ordinary ridge resolvent (empirical version):
E + nTlp) S + _ T. (vE + I,)) EiEE+ -
(B.5)
where v is as defined in (.2).. and U. is defined in terms of a by the equation
v-2 y ! X + +1))
(B.6)
See also the recent work Chenakkod al. 2023 that show certain Gaussian universality results for sparse sketches like CountSketch.
19

---

Published as a conference paper at ICLR 2024
B.2 NEW ASYMPTOTIC EQUIVALENTS FOR FREELY SKETCHED RIDGE RESOLVENTS
In this section, we derive first- and second-order equivalences for (both feature and observation) sketched resolvents. Their proof's are provided just after the statements.
Lemma 14 (General first order equivalence for freely sketched ridge resolvents). The following statements hold:
1. First-order sketched ridge resolvent (for feature sketch): Suppose Assumption SST Then, for all À > Ao.
holds for
S(S X XS 1
x X pklp))
(B.7)
where solves
1 == b
x #lz) I)
(B.8)
2. First-order sketched ridge resolvent (for observation sketch): Suppose Assumption holds for TT Then, for all > Ao.
X
TT X + X
X X + +IN))
(B.9)
where v solves
== (- x + +I)
(B.10)
Lemma 15 (General second order equivalence for freely sketched ridge resolvents). Under the settings of Lemmal 14 for any positive semidefinite & with uniformly bounded operator norm, the following statements hold:
1. Second-order sketched ridge resolvent (for feature sketch); For all X > do.
XS AL))
S VSSS
X
XS
ST SSTT
L x
( = (B.11)
where U'z >> 0 is given by:
2p
p/y =
2 2
x X
(-
X kI,) x
0x SS
( +
lmIp)) 31
(B.12)
2. Second-order sketched ridge resolvent (for observation sketch): For all X > No.
TT X X + AI)) T ( X + AII -xx""""""
" TT [XXT +Im) ( 2 (n) vIn)
(B.13)
where v/g is given by:
V/
dx TT (- f (XxX] vIn)==1)
+ vIn) -1..
(B.14)
Proof of Lemma 14 There are two cases two show.
1. The statement for the feature sketch follows from Theorem 11
2. For the statement for the observation sketch, the Woodbury matrix identity write
(x X - -x TT x XxT T AIm) TTT
Now we can use the result from feature sketch with T playing the role of and X playing the role of X.
20

---

Published as a conference paper at ICLR 2024
This completes the two cases and finishes the proof.
Proof of Lemma
15 There are again two cases to prove.
1.
We begin with feature sketch. Let A,
x + with corresponding μ4; from Assump-
tion A Following the same strategy as the proof of (eeleune et al. 2022 Theorem 4.8), the two sides (B.11) are equal to
S(S A, AI) 02
S
(A, + p2lp) -1
δz
at 2 = 0, and therefore μ' = 0u,2d2 d2 at = 0. Letting
= P -- tr x X ( X + μlIp)) /<Ip)/'] '1)
p
for brevity, and noting that
A. (A, 1z1p)=
μ1 (A, + p=1p)) 1,
we differentiate 66 to obtain for z =
= A9 (1I)t((( xIp) - -
trr + mIp) 3 ( n'Tp)l)
Solving for y', we get
A (r X mllp)
( -
wLم IJ+
Meanwhile, if we take partial derivatives with respect to À (after dividing by on both sides),
+ -
Ōp 1 x =
( +IIp) 9)
yx X2
ax
Combining these two equations gives the stated result for the feature sketch.
2. For the observation sketch, we once again use the Woodbury matrix identity to write
TT x
x TTTX X + AI,) [XXTTT x + AI,) XTTT
" T XX + AL T TETTXXTTTTTTTTTT XX AIm)
The equivalence in B.13) and the inflation parameter in (B.14) now follow from the second- order result for feature sketch by substituting T for S, X for XT, and XXVXX for W in B.11
n
This finishes the two cases and concludes the proof.
C PROOFS IN SECTION 3
C. PROOF OF THEOREM 2
Below first provide the complete statement of Theorem which includes expressions for p' and μ1" that are excluded from the main paper.
Theorem 16 (Squared risk and GCV asymptotics for feature sketch), Suppose Assumption hold. ( (S&) and all K,
Then, for all X > Xn lim inf p- minke[K] A (S]
R(G R(3ridge)
A'A and A(3que) ((Gridge)
4
A
(C.1)
K
K
where y is an implicit regularization parameter that solves B. Ly
(1XXT
+
and pd 3 O an inflation factor in the risk decomposition given by:
ōp x² S ( (- 30r 1 1
/l = ax
x
uI, -1,
(C.2)
21

---

Published as a conference paper at ICLR 2024
while μ² > O is an infiation in the GCV decomposition given by:
0/ X SST (-
x (= + ) " 1 x + xm)p²
μ² 27
(C.3)
tr X X x X j(lp)) (1)
We shall break down the proof into two parts: risk asymptotics and GCV asymptotics. Before proceeding, let us introduce some essential notation first.
Proof. The core component of the proof is Lemma 17
Notation: We decompose the unknown response yo into its linear predictor and residual. Specifically, let By be the optimal projection parameter given by Go Σ E-'E[xo3d Then, can express the response as a sum of its best linear predictor, x Bu. and the residual, you x Bu. Denote the variance of this residual by 2 B[[yo x (b)
Part 1: Risk asymptotics. It is easy to see that the risk decomposes as follows:
R(
E[ x, 3 y. [1 (ō 3b) E(B Bo) + o².
Here, we used the fact that (yo xB Bu) uncorrelated with xe, that E[xo(yo x, Op. We note that 1,oll2 < 00 and E has uniformly bounded operator norm from Assumption B Applying
Lemma thth yields:
R(3 = (3yuss - (B0) 300)))((3 1 u - -Bo) + 0²
= (Gridge - Bo0 T E3iiule - -30) + 02 0²+ 4AA
K
R(Brid +
K
where ye is as defined in C.2 This completes the first part of the proof for the risk asymptotics decomposition.
Part 2: GCV asymptotics. We will work on the numerator and denominator asymptotics separately, and combine them to get the final expression for the GCV asymptotics.
Numerator: We start with the numerator. Similar decomposition the risk yields
1 yy x1 n
A |/30 (qu5) + (y x,30112
7 [ - Br ) + +llly - x,3o) . -x-,)))))
T X(3o - 33 ).
From Lemma 14 note that
[ X.3o)
X(B0 (
) ( -x,,) X(10 - Briido
Next we expand
1 X( 33 (3xms -Bo) 1 x
X( -Bu)
@grid -Bo) 1 x X (3ridoo - -Bo)
K
where /luum is given by:
"mmm ēp x2 I (- |rr [ X (+ T x + =lI)) (1) xx x + u'I)) - -2.
2x
Now appealing to Lemma we have
1 Ily -
1y-3x x
2 ~ (Bridee Bo) T 1 x X
x(@ridge - BB) + + -x,30) X(Bo - 3ridge)
+ All - x,3 4
(C.4)
K
22

---

Published as a conference paper at ICLR 2024
Note also that
1 y X 3
= + - X,30 + ((3 3rldge)
alyy X,3o (y X.3.)
X(3
+ 1 x
/
)
(C.5)
n.
Combining C.4) and (C.5) we arrive at the following asymptotic decomposition for the numerator:
X T
Hlyy
(C.6)
K
Denominator: Next work on the denominator. For the ensemble smoothing matrix, observe that
1
[ + x _ + pkpp) -
where we used Lemma
14 to write the asymptotic equivalence in the last line. Thus, have
tr| [
tr[( X + - tr r[...d
(C.7)
Therefore, combining C.6 and C.7 for the GCV estimator, we obtain
n ly x 13
1
(1 tr L
1 Hum A
yy x,3 3ride
K Ir [L
Huum A
y gridge
1 [r[ [r ridgoj)
R( Gridgee
+
K
where μ² is defined in C.3 This finishes the second part of the proof for the GCV asymptotics decomposition and concludes the proof.
HELPER LEMMA FOR THE PROOF OF THEOREM 2
Lemma 17 (Quadratic risk decomposition for the ensemble estimator for feature sketch). Assume the conditions of Lemma 15 Let y be any positive semidefinite matrix with uniformly bounded operator
norm, that independent of (Sx) k- Let Bo E IRP be any vector with uniformly bounded Euclidean
norm, that is independent of (Sx) R-11 Then, under Assumptions and B for X > to and all K,
BB) + P'g A
(
Bo) T ( Bo) ~ (@uidee (Bo)
Ap (pridge
K
where y is as defined in
B.8 ply is defied in B.12 and A is as defined in Theorem 16
Proof.
We start with a decomposition. Observe that
(Gaus
Bb)
T (
3b)
K
1
30
V
Σ
30)
K
K
k-1
1
Σ
K
(Bt)
3
2
3o "2335 3u E
K2
K
K
K
Σ
(B
1 33 - (Brider) T v gridge (Gridge) v Bridge
Σ Bu
3 + B0
4 3B.
K2
K --
23

---

Published as a conference paper at ICLR 2024
By Lemma 14
note that
K 1
Σ K
3
Bridgo |
Similarly, by two applications of Lemma we know that (3x) T - (Bridge) when & 5e since S₁ and Sş are independent. The remaining K terms where k { converge identically, so
Toaadee)Tppp Typ 1/gridge -s,
(3xTs - B0) (3 - Bn)
- (1 Bo) T 1 (Bridge Ba) + K
(3) 18,
-33rider) T ( 3ridde)))
Thus, it suffices to evaluate the difference 3 1 (3ildeee T 1/rridee, which we will do next. By linearity of the trace, we have
3 33.
(
1/ Briddeee
tr [X} vX x X
where
= - XS ss, and x J ( 11
The result now follows by evaluating the second-order asymptotic equivalences from Lemma 15 This concludes the proof.
C.2 PROOF OF THEOREM 3
The main ingredient of the proof will be Lemma suffices to show the following equivalence:
18
Comparing the expressions of μ and p², it
+ t x
X + pllp) -21
t X + pIp)
91 =
(1 tt X
X + mIp) 11))
We show this equivalence Lemma
18 to finish the proof.
A side remark that is worth stressing about the proof of Theorem 3 The inflation in both the test error and train errors are such that the same GCV denominator cancels them appropriately! Thus, while one may expect that the GCV for infinite ensemble may work given the equivalence to the ridge regression, the fact that GCV works for a single instance sketch (even to the authors) quite remarkable!
HELPER LEMMA FOR THE PROOF OF THEOREM 3
Lemma 18 (Equivalence risk and GCV inflation factors for feature sketch). Under Assumption B
x nu _I) x L X
+ pIp)) -1
x X + mI,
(C.8)
Ltr x X
Proof. We will first derive asymptotic equivalents for both the left-hand and right-hand sides of (C.8. We will then show that the asymptotic equivalents match appropriately.
Asymptotic equivalent for left-hand side. From the second part of Lemma 13 we have
x x + x4p))
L X X + مو,) ~ +1+ +b) + 1,) - + 1,
where the parameter Go from B.4 is given by:
1,) -1
0
th I,) -2)
24

---

Published as a conference paper at ICLR 2024
Now, note that
1 0b
2- 2 + 7 tr (2 + 1p) 2
which leads to
1 + ib
1
wー
42
p²
v
2 12
Thus, we have that
1 x + plp))
E _ x X + plpp)
f+E ++E+ +
D
Ip)
(C.9)
2 v 2
1p)-2
Asymptotic equivalent for right-hand side. From the third part of Lemma 13
we have
( x X 1 X
X X + pdl)) = -
(C.10)
where the parameter T. from B.6 is given by:
00
(C.11)
wー
7 tr
2 (1E 11) 1p)
From the first of Lemma 13
we have
1
1
tr|
X
x
pIp
11 1- - n 1 - +
1 - - -1- (
2 - -1 -1- I1)
= - 7 + 2 11
(C.12)
Combining (C.10.
C.11 and C2.22 obtain
x X + μI,
x -1
u 1 X
X
L X + (
(+ + 1 +,)
(C.13)
ビー tr Σ 3 -
(1 - 7 + tr 1,) 11)
Matching of asymptotic equivalents. Note from the fixed-point equation (B.2 that
# --- v-
u [ I.
Multiplying by both sides yields
pv
1 =
(C.14)
Thus, combining
C.9
and C.13
have
x x + μI,p)
2
1E 100
122 0-2 + y tr D" (+E I,p)
1 I,) E1 II,) I,)
(mm)² 6-2 2 +
Σd
[ (
+ I,)
1x + -
+ I1,
(1 33
+
Ed (1E 1,)
( x pl,))
(1
In the chain above, the first equivalence follows from C.9.. the penultimate equality follows from (C.14) and the final equivalence follows from 13 This finishes the proof.
25

---

T Published as a conference paper at ICLR 2024
D PROOFS IN SECTION
D.1 PROOF OF THEOREM
As mentioned in the main paper, the idea of the proof is to exploit the close connection between GCV and LOOCV to prove the consistency for general functionals. In particular, we will consider an intermediate functional, constructed based on LO0-reweighted residuals. We will then connect the functional constructed based on GCV-reweighted residuals to that based on LOO-reweighted residuals.
Step 1: LOOCV consistency. Let X-; denote the the feature matrix obtained by removing the i-th row from X, and y-v is the response vector obtained by removing the i-th entry from y. Let 3 denote the LOO ensemble estimator. It is defined using K constituent sketched LOO estimators 3 -i, for lt [K] as follows:
1 K
M
3
where
The LOOCV functional is the defined using the predictions of the LOO ensemble estimator as:
1 n Σ tlyi x B (11)))
1
(D.1)
It follows from the proof of Theorem of Patil et al. (002)) that [_(3xTM)) will show that
Aloo as 0. Next we
TAl
u.s. 0, where T3 is the GCV functional.
Step 2: From LOOCV to GCV consistency. To go from LOOCV to GCV, we first rewrite the LOO errors. From Woodbury matrix identity, observe that
yi x 3
x
1 L
This is the so-called exact shortcut for LOO errors for ridge regression, that also works for sketched ridge regression. In other words, we have
x 3
x 3
y:
1
y/
1
This implies that
K
x 3
x
ens =
1 91
K
1
L
k-1
Thus, we can write the LOO function (.Il in the shortcut form as follows:
1 n
Ui - x 3
T00
Dir U/
71
1 Lg
We will now bound the difference:
Tal
1
Σ
K
- X, Tg
y1 x.
Fans
t
Y:
K
1 1-
1
f [
1=1
k=1
12
1
Σ
K
9 - 3
K
y/4 - 3
t
Vi. Yi
K
1
[g
K
cms
k=1
k=
The final equality follows from using the definition of the ensemble estimator 2 For notational simplicity, denote by:
26

---

Published as a conference paper at ICLR 2024
r Y1 x 3 for & [K] and e [n]:
dh 1- | for E [K] and e [n], and and d = 1 - 2t 1
u, (yt, y/
- 3 v; (yi. ye # 2k-11 2
K
Now, consider the desired difference:
To Txl
Σ ((,)) - t(v:))
72
1
L + ||u/|2 + (Ivil2)( vill2)
1-1
L(1 + | + l[vele)
(D.2)
K
d
Æ-1
Above, we used Assumption C in the inequality. Using Hölder's inequality, we can bound
max 1ske
d
K
di d
r, max
(D.3)
df where we denote by r; (r...... r for i E [n]. In the second inequality, we used the fact that [ralla & 1r1l2.. Combining (.22 with D.3) yields
k
[T tAl
L(1 + || [mell2)
VR (r:12 (r1l))
max ISkE
1
71
dh
d
L
(1+ + |1 + Ivoll2)
VR |mille) [
Isten
max
max LEkS
d d
Further denote by:
u1 (|ui 2, 2,....
|n, 22;
. (1vi122....,
Vn l2);
r (1r122,....
||r 12):
6 maxi s [1/ 1/d for i [m]. and 8 (.1,...,55) 8x).
Continuing from above, using the Cauchy-Schhie Schwartz inequality on the first term and triangle inequality, we obtain
|ull vn
||v|2
||||
TA L.
I+
+
& C1
nn
nn
From a short calculations, follows that bounded. We will next show that |o]|oo 0. Sup-norm concentration: We will show that
Julla.
Jal
|/22,
I
||||| are all eventually almost surely
1
n.S. 0.
max I
K
1- [
From Lemma 14
observe that
1
1
K
LA
K
XS (LS) X XS, + -
k=1
n
1
ridge 1
ii
1
I
ridge
27

---

Published as a conference paper at ICLR 2024
Similarly, using Lemma 14 again, also have
-k=1 tr L
>
- # X & X XS, + - XT]
Σ
L
ridge
L
ridge
K
Thus, we have the desired difference be
max ISEE
K
tr
L
eus
max 18
[L
ridge
86
ridge
From the proof Theorem 3 of Patil et al. 2022 the right-hand side of the display above almost surely vanishes. This completes the proof.
D.2 PROOF OF COROLLARY
This is simple consequence of Theorem 4 using the definition of convergence in Wasserstein W2 metric. See, e.g., Chapter 6 of Villani 2008
E PROOFS IN SECTION 5
PROOF OF PROPOSITION
We begin by noting that when X 0, it suffices to prove the result for i.i.d. Gaussian sketches only. Consider first any sketch = UDV where U is uniformly distributed unitary matrix and D is invertible. Then
S(S) ES) ST U(U ŠU) -UT,
and the result does depend and V. and as in i.i.d. Gaussian sketching. For general free sketching, S may not have U uniformly distributed in finite dimensions, but the subordination relations Theorem depend only on the spectrum of SS so we can without loss of generality assume that U are uniformly distributed and obtain the exact same equivalence relationship.
choose them have the same distribution
The subordination relation
p = A ( 1 μI,) "I)
for μ >> 0 and À 0 requires that the the S-transform must go xo. From Table we know
I ssT (w)
a + w
for i.i.d. sketching, which means that we must send the denominator to 0. Thus we obtain the condition
E + ,TI))
tr
By letting K - 00, the variance term vanishes, and only the bias term remains, proving the result.
F PROOFS IN SECTION 6
F.1 PROOF OF PROPOSITION 7
We provide below the complete statement Proposition which includes expressions for // and y/" These excluded from the main paper.
28

---

Published as a conference paper at ICLR 2024
Proposition 19 (Squared risk and GCV asymptotics and GCV inconsistency for observation sketch). Suppose Assumption A holds for TTT, and that the operator norm of Σ and second moment of yo are uniformly bounded in p. Then, for X > Xo and any K,
v'À
v²
R( R(3
+
and R( R(3rddke) +
(F.1)
K
where v is an implicit regularization parameter that solves (B.00) == Ly T XXX 1/In))23)
and v' z 0 is an inflation factor in the risk decomposition given by:
8u x2 X
22 TT (-
1 + II, "DD (AXXT + =In) -9. (F22
while v" 3 0 is an inflation the GCV decomposition given by:
v"
0h
TTT
Hrrl [Xx + x + vIn) +In)) -1
(1- Xx ( + =I)
(F.3
Furthermore, under Assumption B in general we have v' 4 v", and therefore R(3 + R$ ((33))))
Proof. The proof for the decomposition in F.1 is similar to the proof of Theorem 16 Our main workforce will be Lemma 20
Notation: We will use the same strategy and notation as in the proof of Theorem 16
We will
decompose the unknown response yo into the linear predictor corresponding best linear projection
parameter and the residual. Let Gn denote the best projection parameter: Bu = Σ -E[x ]. We
decompose the response into the best linear predictor x Bo and the residual error yo xg 3o. We will denote by o² = [y - x [.
Part 1: Risk asymptotics. As done in the proof of Theorem 16 we have
R(B (3xT) Bb) >> Bo) + o² (Bridge Bo)
(3ridgg
0²
+
K
where vf is defined in F222 In the second step, we now instead used Lemma 20 to obtaín the desired equivalence. This completes the proof for the risk asymptotics decomposition.
Part 2: GCV asymptotics. We will obtain asymptotic equivalents for the numerator and denominator of GCV separately below.
Numerator: Similar to the proof of Theorem 16 we first decompose
X eus
1 X(3 )
>l
Ellly x,b) + 3 x,3)) T X(Bo -3xus)
An application of Lemma 14 yields
( X,3)) X(Bo M 2 X,3o) T X(Bo Bridde
Notice that
|( ]qus) (,ggns - 300) T 1 1x X(Ggns - BB)
(gridro BB) Ti X X(Gridzo - -Bo) + 2 A
K
where Vilu is expressed as:
pp 2 S ( 1
/umm= = 2x
-ttrlXXX ( (1xXT + +wIn)=11
29

---

Published as a conference paper at ICLR 2024
Using Lemma 17 get
ly X 12 ~ (Briigg [o) "x( - Bo) + 1 X,30) X(ob) - 3ridgo)
1" À
+ + - xBb)l2+ +
(F.4)
K
On the other hand, we also have
1 y X 1
= 1 - X,30) + ((3 Bridge) 1
lly X,Bol 2 (y X(3b))
X(33 Brldge + x
3rides
>|2
(F.5)
Combining
and (F.5). we deduce that
V A K
y
x
flyy
X Brdg
(F.6)
Denominator: We will now derive asymptotic equivalent for the GCV denominator. By repeated applications of the Woodbury matrix identity along with the first-order equivalence for observation sketch from Lemma
14. we get
K
L ens
(1,) - XX
K
k=1
K
XX T2 + AIm)
K
xx = X x
+
In the chain above, we used the Woodbury matrix identity for equality in the second and forth lines, and Lemma 14 for the equivalence in the third line. Hence, we get
tr ا tr| x + vIp)
= x + +I,) x x tr dd (F.7)
Therefore, combining (.6)) and F..
for the GCV estimator, obtain
Ily 13
R(
(1 1 tr )uu
A
y X x
num K
L tr 100
" num A
lly X x
K
(1 1 tr (
Bridde) +
K
where v" is as defined in FF3) This finishes the proof of the GCV asymptotics decomposition.
Part 3: GCV inconsistency. The inconsistency follows from the asymptotic mismatch of '/' and v/
To show the mismatch, it suffices to show that
Air LX x)X (XXXT + vIn) -2
Jo Xxx XXXxx
vI.)) = 2
xx [Xx xI,))))
This is shown in Lemma 21
This concludes all the three parts and finishes the proof.
30

---

Published as a conference paper at ICLR 2024
HELPER LEMMAS FOR THE PROOF OF PROPOSITION
Lemma 20 (Quadratic risk decomposition for the ensemble estimator for observation sketch). Assume the conditions of Lemma [5] Let V be any positive semidefinite matrix with uniformly bounded operator norm, that is independent of (Tx) )
k-1- Let 30 E IR? be any vector with uniformly bounded
Euclidean norm, that is independent of k- Consider the ensemble estimator obtuined with observation sketch as defined in
13 Then, under Assumptions A and B for X= do and all K,
(6 3o) T (3 Bu) (Bridgo BB) T (Bridge Gu) +
K
where v is as defined in (BI00, vi is as defined in (.14). À is as defined in Proposition 19
Proof. The proof follows analogously the proof Lemma 17 except now we use the first- and second-order equivalences from Lemmas 14 and [5 for observation sketch (instead of feature sketch). We omit the details.
Lemma 21 (Asymptotic non-equivalence of risk and GCV inflation factors for observation sketch). Under Assumption
B
XX +vln) ( ( + +vI,)
+ 1 (XXX + vI, =
xX + [
(F88
(1 Lur Σ E -1I)
Proof. We will first derive asymptotic equivalents for both the left- and right-hand sides of F.8) Then we will show that the difference in their asymptotic equivalents is non-zero.
Asymptotic equivalent for left-hand side. Using Woodbury matrix identity, we can write
(x,
+ =
= tr(( + - 1 vI [1
-tr =r[( - - - +IIp)
Asymptotic equivalent for right-hand side. Similarly, the numerator of GCV can be expressed as
ur[( + - ( =I,
= =
S
E xI - + -1 -1
From Lemma 18
we have that
utr(($] 1II - vI,) '1]
vtr + -'
-1
(1 - 1t E + vI,)) -1)
31

---

Published as a conference paper at ICLR 2024
Mismatching of asymptotic equivalents.
Observe that
1 [tr[( n XXT II, (
[ xx + ( X )
+ [
1 E x1ppp 11)=
1 tr E vIp 1ppp--11]]]
Hir((
(Ip)
(1- / + -Ip)-11)² "12
1
1tr + -
1 tr EEE v1 11
(1 n (1=+ -1)
n tt + /11pp -
1 t + x1pp -
The last line is in general not equal to 0. proving the desired asymptotic mismatch. This finishes the proof.
F.2 CORRECTION USING ENSEMBLE TRICK FOR GCV WITH OBSERVATION SKETCH
Below we outline method that corrects GCV for the sketched ensemble estimator with observation sketch. The idea of the method is to estimate the error term in the mismatch in Lemma 21 using a combination the ensemble trick and our second-ordes sketched equivalences. The correction takes complicated form involving both the unsketched and sketched data. We are not aware of any method that uses only sketched data.
1. Estimate y from the data and sketch using the subordination relation (B.10).
2. Estimate the following two quantities that appear in the inflation of the GCV decomposition:
(
v -,,,)
Ä XX +uIn) and Ci
(1 1r Σ + -1)
with K 1 and 3. Use ensemble trick explained in Section 5 on R(( = (ि + =
K
= 2 to estimate R((3ridze) first and then estimate the following component:
δu x2 FTr (- tr ( Xx + vI,) "JGA.
C=v = ex
4. Eliminate À from C' to get an estimate for the following component:
dv x2
C₂ = - 21 TT
(- n -=++ ( (+xXT vIn) -I,)='1).
5. Then the following equivalence estimate:
C =
=I,
1xx T + vI,) -1
1 [ + vI,)) -I
XXT -I
(1 1 Σ +I,)) 11))
! |r vI,) -1
1 1 11,)
6. Finally, obtain the corrected estimate for risk using the GCV asymptotics decomposition from Proposition 19
Cocy
( +
K
32

---

Published as a conference paper at ICLR 2024
F.3 ANISOTROPIC SKETCHING AND GENERALIZED RIDGE REGRESSION
Using structural equivalences anisotropic sketching matrices and generalized ridge regression, one can extend our results to anisotropic sketching and generalized ridge regression. Specifically, let R e RPxP be an invertible positive semidefinite matrix with bounded operator norm. Consider generalized ridge regression with a anisotropic sketching matrices Sa = R for l E [K]]
3 = SS where
3
arg min b BER
XS
(F.9)
where G RPP is a positive definite matrix with bounded operator norm. Let B be the ensemble estimator defined analogously as in (2) and GCV defined analogously as in (5). Using Corollary 7.1
of LeJeune al. (2022), all of our results carry in this case in a straightforward manner.
G EXPERIMENTAL DETAILS
All experiments were run in less than hour on a Macbook Air (M1, 2020) and coded in Python using standard scientific computing packages. CountSketch (Charikar al. 2004) implemented by generating a sparse matrix corresponding to the hash function, and due to rounding of the size parameters to match theoretical rates. we cannot choose arbitrary sketch sizes and are often restricted to non-standard sequences. Instead of the SRHT, which requires an implementation of the fast malsh-Hadamart transform not readily available and iefffomminddeeendent also suffers statistically from zero-padding issues as described by [LeJeune et al. (2022). we use subsampled randomized discrete cosine transform (SRDCT), which is fast, widely available, and does not suffer the statistical drawbacks. All sketches are normalized such that SS Ip and therefore
Python (and
|ISTx
x 2
2 1 p |x
G.1 GCV PATHS IN FIGURE
For this experiment, over 100 trials, we sampled X with each row x ~ I,),,,,) and generated = x B + { for 3 ~ NO0, [ppp) and independent noise & ~ (N(,,),, 1). We have = 500 and 600, and our sketching ensembles have K = 5. For the left plot, we fix g 441, which is an allowed sketch size for CountSketch. For the right plot, fix À = 0.2 and sweep through the choices of q which are allowed by CountSketch, which are q (63, 126, 189, 252, 315, 378, 441, 504, 567).
G.2 REAL DATA IN FIGURE
For both real data datasets, we fit our sketched ridge regressors on centered sketched data and responses and then added the mean of the training responses any outputs. For both datasets, sketched using CountSketch, which is among the most computationally efficient sketches, especially for sparse data as RCVI. We plot risk on symlog scale of À with linear region from - to 10.
For RCVI (Lewis et al. 2004), we downloaded the data from scikit -eiitnleern (Buitinck et al. 2013). We discarded all labels except for GCAT and CCAT and then discarded all examples that did not uniquely fall into one of these categories. These became our binary class labels. We then randomly subsampled 20000 training points and 5000 test points, and discarded any features that took value 0 for all train and test points. This left 30617 features, and we used q = 515 for CountSketch.
We normalized each data vector such that [x] [x| vp. preserving sparsity. We then fit ensembles of size K 5, reporting eтror over 10 random trials.
For RNA-Seq (Weinstein et al. 2013), we downloaded the data from the UCI Machine Learning repos- itory (Dua & Graff] 2017) at: https://archive.ii ics.
Seq We discarded all examples that were labeled neither BRCA nor KIRC, the most common classes, leaving 446 observations, which were split into training set of 356 and test set of 90. We then z-scored each of the 20223 features using the training data statistics. We fit ensembles of size K = 5, reporting error over 10 random trials.
33

---

Published as a conference paper at ICLR 2024
G.3 PREDICTION INTERVALS FIGURE
For this experiment, we use SRDCT sketches. For each choice of
q E {80, 180, 280, 380, 480, 580, 680, 780, 880, 980), we generated data over 30 trials in similar manner to the experiment in Figure ! for n = 1500 and p 1000 we sampled X with each row x ~ (O Ip), but we generated y g(x (3) for No. p Ip) and g the soft-thresooding operator:
if u
g(u)
- 1
u u++1
fu---
We compute the 95% and 99% prediction intervals by identifying the 2.5% and 0.1% tail intervals of the GCV corrected residuals (y - =): (y. 2) Pxns and evaluate coverage on 1500 test residuals yo X A We plot 2D histograms of px (empirical using test points) and Pens (using training points) on a logarithmic color scale.
G.4 DETAILS FOR FIGURE
For this experiment, Gaussian data with Σ = diag(a), (a). where a; = 2/(1 + 30f,), where 1; are linearly spaced values from 0 to 1. We generate y
SRDCT sketches. For 600 and p 800, for each trial, we generate
& for 31:80 (O, su Iso) and Ast 0 and & (0, 4).
We evaluate the mapping from ~ for feature sketching by inverting the subordination relation ttr[ TESSSSSSTT ES AL,) 'I)
/ s.S SST
p
for single random generation of data and sketch. For observation sketching, we do the same but the relation
== x ( XI,)
We evaluate the mapping from ~ a using the same method as in feature sketching, except we take q as 20 values logarithmically spaced between 1 and 800, rounded down to the nearest integer. For computing the curves where we vary a, we pre-sketch using p and then subsample and normalize to obtain the sketched data for each desired y.
G.5 VERIFICATION OF CONVERGENCE RATE FOR SKETCHED ENSEMBLES
We demonstrate that both GCV and risk for sketched ensembles converge at rate 1/K to the equivalent
ridge for sketched ensembles in Figure G.I For 140 and p 200, for single trial, we generate Gaussian data with Σ Ip and y = x 3 + & for 3 ~ No 1 sketched predictors for À = 0.1 for each sketch using 9 = 156, and then successively build ensembles of size K by taking the first K predictors. We then subtract the risk of the unsketched predictor the equivalent μa, determined numerically to be 0.283 for Gaussian sketching, 0.157 for orthogonal sketching, 0.281 for CountSketch, and 0.157 for SRDCT.
p Ip) and { ~ [N0 1). We fit 1000
H COMPLEXITY COMPARISONS
If the sketch size is sufficiently small, the ensemble trick in (TT) can be more computationally efficient than computing GCV directly on the unsketched data or using k-fold CV. Memory savings are straightforward, as we only need to work with the n x (feature sketching) or m p (observation sketching) data matrix, so we focus here on computation time complexity. For concreteness, we consider dense X. With additional care this could be extended to sparse X and XS, although computation time improvements are harder to obtain with sketching when comparing to iterative solvers on very sparse data.
Letting X # denote the unsketched, sketched, or k-fold training data depending context, and similarly ÿ and X. the computations are dominated by computing the following two quantities:
3 = x
T and
x XI -
34

---

Published as a conference paper at ICLR 2024
GCV: mR R(G
Risk: R
R R(3
10a
10
10
Gaussian
Orthogonal
CountSketch
SRDCT
10
1/K
10-3
10
10'
10
10a
100
10
10a
10
K
K
Figure G.I: Both GCV and risk converge at rate 1/K to the equivalent ridge for sketched ensembles. See Appendix G.5 for the setup details.
For the ensemble trick, we must know which value of μ corresponds the value of À we use, but this can be computed using the subordination relation in Theorem and tr[[_x] In high dimensions, this trace is well approximated (Hutchinson 1989) by:
[r[[ ~ 1 ( 11
-
where z TRxP has i.i.d. Rademacher (+ entries (or if 7 < P. we could use z E RRa)) Thus, the computations are dominated by solving linear system with the matrix x (or X Al dimensions are preferable). We now specialize to couple of different solvers that could be used to solve these systems, assuming that the cost of sketching is amortized or otherwise negligible compared to solving. what follows, when we use big notation, we mean that the rates scale with universal constants independent of n. P., m, q, X.
H.1 DIRECT SOLVER
A direct exact solve of this system has cost O min p)). For unsketched GCV (ñ nn p). we must solve two of these systems, one for the parameter estimator and the other for the randomized trace, giving total cost of (22pp min {n,p)). p}). For unsketched k-fold CV, there is only the cost of computing the parameter estimator the π k-In data points of dimension P p, which is then evaluated on the left-out fold, which is comparatively inexpensive. Since this must be done times, the total cost is O(kk 1)mp min { ( n,,))) For the ensemble trick, must evaluate GCV two separate parameter estimators (n. m, ②). for a total cost of O (4mq min {m, q3).
H.2 ITERATIVE SOLVER
An approximate solution is generally acceptable for risk estimate. Thus, a direct solve is often unnec- essary, and iterative solver such Krylov subspace method can offer considerable computational gains. In particular, instead of a cost of Onñ min {ñ. P)) the cost becomes (nā R3 log ) to
reach an e-accurate solution, where Rx is the condition number X
X + ÅIg.
We can update the computations for the dense solve accordingly, except that for each case (unsketched GCV, unsketched k-fold CV, ensemble trick) the matrix will have a different condition number, which denote Kes Ky,ke and Kx.m.g. respectively.
H.3 COMPARING COMPLEXITIES
We list the computational complexities of the various methods for both direct and iterative solvers.
For the direct solver, the ensemble trick is always beneficial over unsketched GCV as long as q < p/2 (for feature sketching) n/2 (for observation sketching), regardless of the relative sizes of
35

---

Published as a conference paper at ICLR 2024
Method (regime)
Unsketched GCV
Unsketched k-fold CV
Ensemble trick
Direct solver
(2mp min (n. O /2mpyTy Fiy log :)
O((k 1)mp min { K p))
O (Amq min {m, q)
Iterative solver
O((k m /Ep, log ))
O (Ammy/ F.mmm log :)
Table 5: Complexity comparison for risk estimation in ridge regression.
and p. If we also know that p n, then the ensemble trick with feature sketching is beneficial as long as q p/v2,, and analogous result holds for observation sketching were to sketch both observations and features by factor of a, suffices Meanwhile, k-fold CV is never competitive for k = 5 or 10.
n/v2.. If one 2- 1/3 0.78.
For the iterative solver, in order to compare the complexity, we need to know how the condition numbers change with sketching, which is not obvious. We can gain some insight, however, by considering very small sketches. As we observed in Appendix [A.3.2] sketch types seem have similar subordination relations for small sketches, so we can specialize to Gaussian sketches for simplicity. As the sketch size decreases, all eigenvalues of S ES concentrate around single value, in the extreme limit of 1 converging of S ES + AI, tends toward as sketches get smaller, meaning that sketching better conditions the system such that Ky.m.g & Kyp We then again have the same conclusion in the direct solver case, that as long as m < n/2 or q < 2/2, then using the ensemble trick is beneficial over unsketched GCV. And similarly, k-fold CV is not competitive.
Σs ir[E]. This means that the condition number
36


Reviews:
[{"review_id": "tjVM4Bjk8B", "reviewer": "Reviewer_t4Ef", "summary": "This paper is about the (asymptotic) consistency of generalized cross validation (GCV) for estimating prediction risks of sketched ridge regression ensembles using tools from random matrix theory. \n\nFor general subquadratic prediction risk functionals, they extend GCV to construct consistent risk estimators, and obtain distributional convergence of the GCV-corrected predictions in Wasserstein-2 metric.\n\nAlthough the consistency result seems intuitive and natural, they point out that GCV of the observation sketched ridge regression, is inconsistent, highlighting the subtlety of this subject.", "questions": "Asymtpotic freeness seems to be an essential assumption in the paper. Although this assumption is experimentally supported by artifical datasets, I wonder if one can observe similar matching on real-world dataset.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper presents the theorems in a clear and rigorous way. All notations are presented again on a table in appendix. Theoretical result is supported by experimental result.", "weaknesses": "No major weakness is spotted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yeBUuaY2Nv", "reviewer": "Reviewer_qfu6", "summary": "Motivating by hyparameter tuning (size of the ensemble, size of the sketches), this paper studies the statistical properties of Generalized-Cross-Validation applied on an ensemble of sketched ridge regressors with skecthing applied to the feature space. First, the authors develop squared risk asymptotics and provide consistency results (Thoerem 2) and then, extend these results to subquadratic error functionals (Theorem 3). These findings hold for the general class of asymptotically free sketching matrices. At the origin of the study, is a key theorem (LeJeune et al. 2022), that states that the sketched inversion of a sketched regularized matrix corresponds to the inversion of the initial regularized matrix with another hyperparameter. This gives rise to Theorem 2 that nicely relates the quadratic risk of the ensemble-based estimator to the risk of the rigde estimator plus a randomness term depending on the sketch via Theorem 1 and the so-cllaed S-transform. Moreover, functional and distribution consistency for general error functional are also proved. Simulations on toy and real data shown in the main paper and appendix confirm the interest of the approach for tuning both the regularization level (or sketch size in fine) and the size of the ensemble.", "questions": "See my previous comments.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "First of all, I would like to say that this is a very nice paper, very well written, solid and with a strong and insightful content. I have learned a lot when reading it.\nThe main strengths of the paper is its depth of view not only about GCV (which has a simple form) but also about the link between sketched ridge regression and regualrization in ridge regression, and the role of the ensemble trick. \nI appreciated the richness of the discussion and the comments all along the paper.\nOriginality is also present here, with the exploitation of very recent results (LeJeune et al. 2022) but with a special angle here (GCV).", "weaknesses": "* Improvment of clarity in Assumption 2 statement and explanation. \nThe paper has the merit to introduce elements of free probability theory useful in Assumption 2. I regret not to have more intuition here: I can easily imagine that a form of independence (I've read the appendix) between $X^TX$ and $SS^T$ is useful but the notion of limiting S-transform is not at all discussed at this stage (page 4) and Assumption 2 remains not clear at all when beginning to read what follows. Same thing for Theorem 1, describe the $|ambda^+$ function.\n* A simple analysis of the complexity in time and memory for the full aproach in constrat to other estimators (CV) would be welcome.\n* Bonus: Is it interesting to come back on other risk estimators (Bootstrap) and clearly identify what could be done with this estimator or not with ensemble of sketched ridge regression.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "E24jvCTIxO", "reviewer": "Reviewer_WHDZ", "summary": "The current paper considers generalized cross validation (GCV) for sketched ridge regression ensembles. Specifically, sketching is done across different features and ensembles are based on finite sketches. The paper first derives the asymptotics of squared risk and its GCV estimator (section 2) and then extends to more general subquadratic prediction risk functionals (section 3). The paper also proposes a method for estimating the risk of unsketched ridge regression using sketched ridge ensembles (section 4). All the theoretical results are illustrated using both synthetic and real datasets with CountSketch and subsampled randomized discrete cosine transforms.", "questions": "1. In figure 1, it would be good to indicate that SRDCT refers to subsampled randomized discrete cosine transform because SRDCT first appears toward the end of page 2.\n\n2. In proposition 6, $S_k^T S_k$ is assumed to be invertible. How strong is this assumption? Some further remarks might be helpful.\n\n3. The ensemble trick in section 5 seems very useful. However, there is no explicit discussion of computational gains over unsketched GCV. Especially, when $K$ is large as in proposition 6, one might need to rely on parallel computing to fully speed up computations. More discussions might be desirable in terms of computational complexity. \n\n4. Is there a known S-transform for CountSketch? Table 4 in the appendix does not include CountSketch.\n\n[Update after the discussion period] The author(s) responded well with my questions. I am satisfied with their replies. This is indeed a good paper.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Overall the paper is very well written and persuasive. The experimental results are very well summarized in the figures.\n\n2. It is impressive that the current paper considers all asymptotically free sketched ensembles and allows for zero or negative penalty \n in ridge regularization.\n\n3. Distributional consistency in Corollary 5 is nice: this allows for classification errors and construction of prediction intervals among other things.\n\n4. It is interesting to know that the finite ensembles by sketching observations do not have GCV consistency, as given in Proposition 7.", "weaknesses": "It would be beneficial to provide more details regarding computational aspects in the main text. For example, I presume that it is not necessary to compute $\\hat{\\beta}_{\\lambda}^k$ alone in equation (1). \n\nIn other words,  it is only necessary to compute the predicted values \n$X \\hat{\\beta}_{\\lambda}^k$. \n\nThis seems important because it is not necessary to explicitly premultiply $S_k$ to $\\hat{\\beta}_{\\lambda}^{S_k}$ in equation (1). If I am correct, this point can be emphasized at the end of section 2 when it is discussed that matrix inversions are inexpensive after precomputing $X S_k$.\n\nGenerally speaking, it would be helpful to provide more details regarding computational aspects.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IQBL6hJy7N", "reviewer": "Reviewer_GR2e", "summary": "This paper established consistency of generalized cross validation for estimating prediction risks of sketched ridge regression that enables it to fast tune ensemble parameters. The authors further proposed an resembling trick so that the risk for unsketched ridge regression can be estimated through GCV using small sketched ridge ensembles. Simulations are conducted to validate the theoretical results.", "questions": "Because GCV and risk for sketched ensembles converge at rate 1/K to the equivalent ridge for sketched ensembles, does this imply the larger the K the faster the convergence and the better it is? It there a downside if K is too large?\nCould the authors why the result that tuning (ensembled) sketched ridge is equivalent to tuning unsketched ridge regression is useful?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper gives asymptotic of squared risk and its GCF estimator for sketched ridge regression so that an it is intuitively understandable as the implicit unsketched ridge regression risk and an inflation term due to randomness of the sketch that is controlled by ensemble size. And this is exploited to provide a method to tune unsketched ridge regression using only sketched ensembles. None of the assumptions are very strong for these theoretical results.", "weaknesses": "While the results in this paper is interesting, the authors failed to illustrate while tuning (ensembled) sketched ridge is preferred over tuning unsketched ridge regression. It would be better if they provide some intuition and explanation to the results, especially for readers who are not that familiar with sketching.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)