Asymptotically Free Sketched Ridge Ensembles: Risks, Cross-Validation, and Tuning

Thank you for your constructive feedback and for acknowledging the strengths of our paper. We appreciate the opportunity to clarify aspects of our work further. We hope that these responses address your concerns and clarify the practical contributions of our work.

The authors failed to illustrate while tuning (ensembled) sketched ridge is preferred over tuning unsketched ridge regression.

We have now included a new Appendix H to clarify when one might prefer to tune ensembled sketched ridge regression over unsketched ridge regression from a computational perspective. As we show, the sketched ensemble trick for tuning unsketched ridge often always offers a computational advantage if $q < p/2$, and can sometimes be preferable more generally.

Moreover, from a statistical standpoint, GCV is preferable to traditional CV due to the absence of data splitting, which preserves the consistency of the risk estimator compared to CV.

Does this imply the larger the $K$ the faster the convergence and the better it is? Is there a downside if $K$ is too large?

While a larger $K$ indeed means being closer to equivalent unsketched ridge risk, there is a trade-off due to increased computational demands. In practice, we typically find a sweet spot where $K$ is large enough to yield a good approximation to the unsketched ridge (with a properly chosen sketch size), but not so large as to be computationally prohibitive. Our experiments suggest that $K$ between 10 and 50 is often sufficient, as long as the constant in the $1/K$ term is not excessively large. This ensures that any inflation due to the randomness of the sketch is controlled by the predictive power of the response.

Could the authors why the result that tuning (ensembled) sketched ridge is equivalent to tuning unsketched ridge regression is useful?

The theoretical equivalence between the space of sketched and unsketched ridge predictors is not only of theoretical interest but also has practical implications. It reassures practitioners that using a large enough ensemble of sketched predictors does not compromise statistical efficiency compared to unsketched ridge regression. This means that one can benefit from the computational efficiencies (especially parallelization and reduced memory footprint) of sketching without a loss in statistical performance, which is particularly relevant for large-scale problems where computational resources or time are at a premium.

Thanks for the comment! We have now squeezed in parts of the explanation above in the revised main paper. Please find pointers to Appendix H in Sections 2 and 5, and additional comments after Proposition 6. These are inked blue in the revision, as are all other changes indicated in the general response at the top.

Thank you for the thorough review and for the positive comments about our paper. We are pleased that you found our work to be well-written and the experimental results compelling.

We appreciate your insightful feedback, which has helped us improve the clarity and depth of our manuscript. Your input on the computational aspects has been particularly valuable, and we have made the appropriate enhancements to the text to better communicate these important details. Thank you once again for your review and the positive assessment of our work. Below we respond to some of your specific points.

Generally speaking, it would be helpful to provide more details regarding computational aspects.

We agree with you and the other reviewers regarding this point and have now added a new Appendix H providing a detailed computational comparison between unsketched GCV, $k$-fold CV, and the ensemble trick, clarifying that the computational demands decrease for smaller sketch sizes. Indeed, as you have written, it is not necessary to "broadcast" $\hat{\beta}_\lambda^{S_k}$ back to $p$-dimensional space, and all computation can (and should) be done only in the sketched domain; our presentation is simply made for mathematical convenience. In fact, for sketches based on hash functions such as CountSketch, computing the adjoint of the sketching operator is in general intractable, so this point is critical in sketched machine learning practice.

In figure 1, it would be good to indicate that SRDCT refers to subsampled randomized discrete cosine transform

We have revised the caption of Figure 1 to include a definition for SRDCT, ensuring that it is clear on its first appearance in the text.

In proposition 6, $S_k^\top S_k$ is assumed to be invertible. How strong is this assumption?

The invertibility assumption for $\mathbf{S}_k^\top \mathbf{S}_k$ is merely technical. If it is not invertible, it is straightforward to verify that the sketched ridge regression problem is unchanged if we replace $\mathbf{S}_k \in \mathbb{R}^{p \times q}$ by its projection $\widetilde{\mathbf{S}} \in \mathbb{R}^{p \times r}$ onto its right principal singular vectors, where $r = \mathrm{rank}(\mathbf{S}_k)$ takes the place of $q$. Thus, Proposition 7 holds for any sketch if we replace $\alpha$ by $r/p$, but we thought it would be better to tie into the same $\alpha$ used in the rest of the paper. Additionally, to use a rank-deficient sketch in practice would generally be wasteful, so we don't anticipate this to be a common case.

Is there a known S-transform for CountSketch?

The S-transform, or any other spectral properties as far as we are aware, for the CountSketch have not been studied in prior literature. One recent work [1] has considered a related sketch which they also call "CountSketch", but which uses only a single hash function, rather than standard CountSketch which uses a growing number of independent hash functions. As they show, it is straightforward to see that with a single hash function, the spectrum of the sketch should follow a Poisson distribution; however, even in that case the S-transform is still not known.

Thus, understanding the spectral properties (including the S-transform) of CountSketch is an interesting direction for future work. Based on our empirical observations (in Figure A.1 and the new Figure A.2) and the fact that it combines many independent hash functions, we strongly suspect that CountSketch has a Marchenko–Pastur spectrum like Gaussian sketches. We have added a new sentence in Appendix A.4 to re-emphasize this observation.

[1] Fan Yang, Sifan Liu, Edgar Dobriban, David P. Woodruff. How to reduce dimension with PCA and random projections? https://arxiv.org/abs/2005.00511

Thanks for the suggestion! We have discussed along these lines in the supplement but we agree that this point should be emphasized in the main paper also. We have now squeezed in a line in the main paper right after defining the ensemble estimator (2). It is inked blue, as are all other changes in the revision.

Thank you so much for responding to my previous comments and revising the paper accordingly. I very much appreciate the addition of the new appendix section for computational complexity, which is quite informative. I also fully agree regarding the response saying that "Indeed, as you have written, ....; our presentation is simply made for mathematical convenience. In fact, for sketches based on hash functions such as CountSketch, computing the adjoint of the sketching operator is in general intractable, so this point is critical in sketched machine learning practice." I am wondering whether you have emphasized this fact in the revised version of the paper. Although it is common knowledge for the experts, it might be helpful to emphasize this in order to avoid any confusion for future readers.

Thank you for your comprehensive review and the positive comments on our manuscript. We are delighted to hear that you found the paper to be informative and original.

Your insightful review has prompted us to refine our explanations and further clarify the assumptions and theorems within our paper. We appreciate your suggestions and hope that these revisions will make our paper even more clear and impactful.

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.

We acknowledge that Assumption 2 (now Assumption A after our revision) and Theorem 1 could benefit from additional intuition, especially concerning the S-transform and its role in our results. We have added a new footnote on page 4 to ground the assumption concretely with Gaussian and orthogonal sketches, which are commonly studied and proven to be asymptotically free. To clarify regarding freeness, the independence between $\mathbf{X}$ and $\mathbf{S}$ is not the only requirement; what is crucial is a form of incoherence, often achieved through rotational invariance of the sketching matrix. This incoherence is captured by the concept of asymptotic freeness in free probability theory.

The S-transform, another key concept from free probability theory, is indeed opaque and difficult to give intuition for. Despite this, it is a standard notion in free probability, and the main thing that matters for our results is that is a function only of the eigenvalue distribution of the sketching matrix $\mathbf{S} \mathbf{S}^\top$. We assume analyticity of the S-transform, which holds for both Gaussian and orthogonal sketches, but we do not know in general what requirements this places on sketching matrices.

Same thing for Theorem 1, describe the $\lambda^+$

As we define immediately before Theorem 1, $\lambda_{\min}^+$ is the minimum non-zero eigenvalue of the matrix. This arises because the multiplication by $\mathbf{X}$ effectively nullifies the zero eigenvalues, leaving only the non-zero spectrum relevant for determining singular inversion, and enabling us to consider zero and negative regularization.

A simple analysis of the complexity in time and memory for the full approach in contrast to other estimators (CV) would be welcome.

We have now included a new Appendix H performing such a comparison. In particular, we demonstrate that the ensemble trick is always competitive with unsketched GCV (which is in turn generally more efficient than $k$-fold CV) as long as $q < p / 2$, and can be competitive even more generally in the right circumstances.

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.

We agree that contrasting our approach with other risk estimators, such as the bootstrap, could be valuable. The bootstrap, however, does not provide an estimator for prediction risk directly and has its computational challenges when dealing with large datasets. Our approach offers both computational efficiency and statistical consistency, which are crucial for practical applications.

Thank you for the positive feedback. We appreciate it. We are also happy that you enjoyed the clarity and rigor in our presentation.

Although [asymptotic freeness] is experimentally supported by artificial datasets, I wonder if one can observe similar matching on real-world dataset.

Given the importance of the asymptotic freeness assumption, we agree that it is crucial to verify this assumption in realistic settings, such as with real-world data and practical sketches.

Recall that for Gaussian sketches and uniformly random orthogonal sketches, asymptotic freeness is theoretically guaranteed for any data matrix $X$ independent of $S$. For other types of sketches, such as CountSketch or SRDCT, the validation of the asymptotic freeness assumption is indeed more complex.

However, as you suggest, we can employ further empirical tests to support our claims on real-world data. We have added a new experiment in Figure A.2 in Section A.3.2, where we showcase empirical subordination relations on the real-world datasets we use in Figure 2 (RCV1 and RNA-Seq), similar to the previous experiment in Figure A.1 on artificial data. These results show that the resolvent relation given in Theorem 1, which underpins our theoretical results, holds with good accuracy on real datasets as well.

We hope that these empirical validations, along with the theoretical underpinnings for more readily analyzable Gaussian and orthogonal sketches, offer a compelling argument for the practical relevance of our theoretical contributions.