acceptodds
Under review as a conference paper at ICLR 2027

The Advantages of Fresh Sketching for Ridge Regression

Abstract

Over the past 25 years, sketching and sampling have become widely used tools for accelerating large-scale regression. In iterative randomized solvers, a basic design choice is whether to the same sketch or draw randomness at every step. For (under-constrained) iterative ridge regression with column sampling, whether fresh sketches offer provable advantages has remained open: Fresh sketching lets us analyze error only along the current residual solution, rather than uniformly over the entire Gram matrix. This directional view yields sharper convergence guarantees for leverage score and ridge leverage score sampling and, more importantly, leads to residual-aware sampling rules. By minimizing the variance of the relevant sketched matrix-vector product, we derive an oracle distribution and practical approximations to the oracle distribution, including a mixture sampling distribution with (somewhat weaker) convergence guarantees. Experiments on synthetic and real data, including ridge probes on Qwen2.5 representations, support our theory, showing substantially faster convergence.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
ridge regression, randomized numerical linear algebra, sketching, probing

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_77U1OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the benefits of fresh sketching over fixed sketching in iterative ridge regression with column sampling. The authors develop a directional error analysis that yields sharper convergence guarantees and motivates residual-aware sampling strategies, including an oracle distribution and practical approximations. Experiments on synthetic and real-world datasets demonstrate improved convergence efficiency, supporting the theoretical findings.

Critical strengths

The paper establishes sharper convergence guarantees within the iterative column-sampling framework of Chowdhury et al. for ridge regression.

Critical weaknesses

See Questions.

Questions for authors
  1. Could the authors discuss the relationship between their approach and existing deterministic sketching methods for ridge regression [1], particularly in terms of theoretical guarantees and computational efficiency?

  2. Could the authors clarify the main technical challenges in establishing sharper convergence guarantees for fresh sketching? In particular, how does the analysis differ from that of Chowdhury et al. (2018)?

  3. What motivates the experiments on Qwen2.5 representations? Do these results suggest potential applications of sketch-based ridge regression to LLMs?

I am open to raising my score based on the responses to these concerns.

[1] Shi, B., and Phillips, J. A Deterministic Streaming Sketch for Ridge Regression. AISTATS 2021.

2 comments

Thank you for recognizing the sharper convergence guarantees and for these constructive questions.

Q1: Relationship to deterministic sketching.

Shi and Phillips [1] study deterministic streaming ridge regression in the n>dn>d regime, compressing A⊤AA^\top A using Frequent Directions as observations arrive. Our work considers the non-streaming, high-dimensional regime n≪dn\ll d, using repeated column sampling to approximate the Gram matrix AA⊤AA^\top and correct residuals. Their streaming time–space guarantees and our iterative convergence guarantees therefore address different computational settings.

Their Theorem 4 guarantees ∣x^−x⋆∣2≤ε∣x⋆∣2\\|\widehat x-x^\star\\|_2\le\varepsilon\\|x^\star\\|_2 when ℓ≥k+∣A−Ak∣F2/(λε)\ell\ge k+\\|A-A_k\\|_F^2/(\lambda\varepsilon), with time O(ndℓ)O(nd\ell) and space O(dℓ)O(d\ell). Our fresh LS/RLS solver costs O(t(nnz(A)+n2s+n3))O(t(\mathrm{nnz}(A)+n^2s+n^3)) assuming sampling scores are provided (Appendix B), and requires repeated data access and new update factorizations. These are distinct resource models; we do not establish a general runtime advantage over their method. We have added a citation to their work in the related work section of the updated draft.

Q2: Technical challenges and comparison with Chowdhury et al.

For fresh sketches, a good matrix–vector approximation along the current residual direction suffices. Chowdhury et al. [2] use a uniform matrix–matrix approximation and bound the errors recursively. Our Lemma 3.1 instead expresses the final error exactly as a product of sketch-dependent matrices, enabling sharper bounds that retain directional information. Conditioning on past sketches fixes this direction zz. For leverage score sampling, with E^j=V⊤SjSj⊤V−I\widehat E_j=V^\top S_jS_j^\top V-I,

=\frac{n-1}{s}\lVert z\rVert_2^2.$$ Regularization deterministically bounds the inverse factor multiplying this matrix–vector error: its norm is at most $\sigma_{\max}^2/\lambda$ for every sketch. Combining these bounds and iterating conditional expectations yields our convergence guarantee. With controlled regularization factors, this saves a logarithmic factor in sampled columns per iteration: $\log n$ for leverage score sampling and $\log(1+d_\lambda)$ for ridge leverage score sampling. **Q3: Motivation for Qwen and potential LLM applications.** Our Qwen experiment is motivated by prior studies that use linear probes to examine information encoded in large language models [3, 4]. We predict STS-B semantic similarity from frozen Qwen2.5-32B representations: 100 examples with $102{,}400$ features obtained by concatenating 20 layers. This tests the solver on a wide regression problem with structured real features. Potential applications include repeated ridge probes across layers, tasks, or regularization settings. Our experiment evaluates convergence to the full ridge solution; benefits for held-out prediction or generation remain unestablished. Evaluating these probes on held-out data and exploring their use in downstream LLM tasks would be interesting future work. **References** [1] B. Shi and J. M. Phillips. A deterministic streaming sketch for ridge regression. *AISTATS*, 2021. [2] A. Chowdhury, J. Yang, and P. Drineas. An iterative, sketching-based framework for ridge regression. *ICML*, 2018. [3] W. Gurnee and M. Tegmark. Language models represent space and time. *ICLR*, 2024. [4] F. Zhu, D. Dai, and Z. Sui. Language models encode the value of numbers linearly. *COLING*, 2025.

My view aligns with that of Reviewer NfyF. The paper follows the analytical framework of Chowdhary et al., and I find its conceptual contribution limited. In particular, “fresh sketch” appears to be a construction tailored to the specific ridge regression problem studied, rather than a new sketching method in its own right. I am therefore inclined to leave my score unchanged.

Reviewer_5u8FOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies fresh column sketching for iterative ridge regression, building on the framework of Chowdhury et al. (2018). By exploiting independence across iterations, the authors analyze the sketching error along the current residual solution without requiring uniform approximation of the Gram matrix. This yields improved convergence guarantees for leverage score and ridge leverage score sampling, removing logarithmic factors in the sketch size under suitable regularization conditions. They further derive an oracle residual-aware sampling distribution by minimizing the variance of the relevant sketched matrix-vector product, and proposes practical adaptive and mixture sampling methods.

Critical strengths

This paper studies improved mean-square convergence bounds for fresh leverage score and ridge leverage score sampling by exploiting conditional independence across iterations. Under suitable regularization conditions, the results remove logarithmic factors from the per-iteration sketch size compared with prior fixed-sketch bounds.

The paper derives a variance-minimizing sampling distribution for the current residual problem and develops practical adaptive and mixture sampling methods. Experiments on the listed datasets show improved convergence over standard sampling baselines in the tested settings. The evaluation also includes direct comparisons between fixed and fresh sketches.

Critical weaknesses
  1. The proposed adaptive sampling method is closely related to Li and Niu (2024), which also uses a pilot sketch to guide residual-dependent sampling. Without a direct experimental comparison, the additional improvement over this prior work remains unclear.

  2. The experiments show improved convergence in several settings, while the overall computational benefits remain less clear. Fresh sketching requires a new matrix factorization at each iteration, whereas fixed sketching can reuse one. The experiments do not directly compare the runtime required to reach the same solution accuracy.

Hanyu Li and Chengmei Niu. Optimal subsampling for high-dimensional ridge regression. Knowledge-Based Systems, 286:111426, 2024.

Questions for authors
  1. Li and Niu (2024, Algorithm 2) also use a pilot sketch to approximate the current residual solution and update sampling probabilities during iterative ridge regression. What are the main differences between their method and the proposed adaptive sampling method, beyond the sampling weights? How do the two methods compare experimentally?

  2. Can the authors clarify how the accuracy of the pilot approximation affects the proposal factors Rp(j)R_p^{(j)} for the practical adaptive sampling methods, and whether sufficient conditions can be established to guarantee a smaller directional variance bound than standard ridge leverage score sampling?

2 comments

Thank you for the positive assessment and these constructive questions.

Q1: Relationship to Li and Niu.

We agree that our method and Li and Niu's Algorithm 2 [1] share a similar structure: a pilot sketch estimates the current residual solution and guides fresh sampling. Their sampling rule uses raw column norms and is derived by minimizing a simplified asymptotic covariance trace; ours uses ridge leverage scores. We also replace their column norm pilot with a ridge leverage pilot and introduce a defensive mixture with ridge leverage sampling.

We have added their Algorithm 2 as a baseline on all three datasets, using the same total sampling budget, including the pilot cost. The table reports median relative coefficient errors after 10 updates at the smallest tested budget ss for each dataset:

\text{Dataset} & s & \text{Li–Niu} & \text{Our adaptive} & \text{Our mixture} \\\\ \hline \text{ARCENE} & 500 & 9.07\times10^{-5} & 3.95\times10^{-5} & 2.82\times10^{-5} \\\\ \text{Qwen} & 500 & 4.49\times10^{-9} & 3.62\times10^{-9} & 2.57\times10^{-9} \\\\ \text{Synthetic} & 2500 & 1.27\times10^{-2} & 1.12\times10^{-2} & 8.33\times10^{-3} \end{array}$$ Across the full sweeps, the clearest gains occur on ARCENE. The methods are closer on Qwen and synthetic data. We have also updated all figures in the manuscript to include the additional Li–Niu baseline. **Q2: Pilot accuracy and improvement over ridge leverage sampling.** Let $q=p^\star$ be the oracle probabilities for the current nonzero residual solution, with oracle factor $\rho$. For any proposal $p$ covering the support of $q$, $$R_p=\rho\bigl(1+\chi^2(q\\|p)\bigr), \qquad \chi^2(q\\|p)=\sum_{i:p_i>0}\frac{(q_i-p_i)^2}{p_i},$$ where $\chi^2$ is the Pearson chi-squared divergence. Thus, at equal update sketch sizes, $\chi^2(q\\|p)<1/\rho-1$ guarantees a smaller directional variance bound than ridge leverage sampling. We currently do not provide an a priori pilot size bound ensuring this improvement; deriving such bounds is an interesting direction for future work. We also measure $R_p$ numerically (Section 6, panels (f) of Figures 1–3; Appendix H.4): the mixture's median values across trials and updates are approximately $0.63$, $0.66$, and $0.67$ on ARCENE, Qwen, and synthetic data, respectively, below $1$ and close to $2/\pi\approx0.637$. Proposition 5.2 and Appendix H.5 explain $2/\pi$ as a Gaussian reference for the oracle factor $\rho$. **Computational benefit and runtime.** Appendix B provides running time bounds for achieving prescribed solution and objective accuracy, including the cost of a new factorization at each iteration. Our implementation also caches factorizations for reused sketches and adaptive pilots. We agree that these bounds and the convergence experiments do not establish a general wall-clock advantage over fixed sketching. **References** [1] H. Li and C. Niu. Optimal subsampling for high-dimensional ridge regression. *Knowledge-Based Systems*, 286:111426, 2024.

Thank you for the response and additional experiments. The comparison with Li and Niu (2024) addresses my concern. The response provides a condition for Rp(j)<1R_p^{(j)}<1, but does not clarify how accurate the pilot approximation needs to be to satisfy this condition. I will maintain my score.

Reviewer_NfyFOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper theoretically and empirically studies the effects of using a fresh sketch in every iteration of randomized iterative solver instead of the same sketch in every iteration. For ridge regression on a fat and short matrix, the paper shows that fresh randomness in column sampling indeed helps. The paper shows better convergence guarantees when the sampling and reweighing matrix is built using leverage score, ridge leverage scores and the new proposed oracle-based sampling which is provably optimal. The idea is that with fresh randomness at every iteration, instead of requiring the full subspace embedding guarantee for the matrix AATAA^T, it is sufficient to preserve a matrix vector product. The paper also provides a practical and natural approximation to the oracle sampling scheme. The theoretical claims are backed by experiments on both synthetic dataset and on embeddings obtained from Qwen 2.5 model.

Critical strengths
  1. The paper is written very clearly, addresses an interesting question, will be of significant interest to the RandNLA community. The experiments show significant improvement by using fresh sketches over reused sketches.
Critical weaknesses
  1. The paper has very limited novelty in terms of both algorithms and proof techniques. Leverage scores, ridge leverage scores are very well known in literature, and the oracle-based method is natural consequence of variance reduction. The proof techniques are also straightforward as far as I could understand with the ideas borrowed and extended from works of Chowdhary et al. 2018 and Kacham et al. As such I am not convinced if it novel enough for ICLR.
Questions for authors
  1. Can you clarify the intuition on how fresh randomness also helps removing the logarithmic term from the sample complexity ?

  2. The related work does mention that fresh sketches have been used in IHS methods. How do the guarantees of this paper and underlying ideas, compare and contrast with those works?

2 comments

Thank you for recognizing the clarity, relevance, and empirical results of our work.

Q1: Why does fresh randomness remove a logarithmic factor?

The logarithm in the fixed-sketch sampling bounds [1] comes from uniform spectral approximation. With fresh sampling, conditioning on the past fixes the current residual direction before drawing the next sketch. For leverage sampling, with E^j=V⊤SjSj⊤V−I\widehat E_j=V^\top S_jS_j^\top V-I, we obtain

=\frac{n-1}{s}\lVert z\rVert_2^2.$$ Regularization gives a deterministic bound on the norm of the inverse factor multiplying this matrix–vector error, valid for every sketch. We combine this bound with the conditional variance estimate to prove convergence without requiring a uniform matrix–matrix approximation. The resulting sufficient sizes are $O((\sigma_{\max}^2/\lambda)^2n/\varepsilon^2)$ for leverage sampling and $O(c_\lambda^2d_\lambda/\varepsilon^2)$ for ridge leverage sampling, where $c_\lambda=1+\sigma_{\max}^2/\lambda$. Thus, the logarithmic savings assume controlled regularization factors. Reusing a sketch removes the conditional independence needed for this argument. **Q2: Relationship to IHS and the specific contribution.** Our residual-correction algorithm can equivalently be viewed as regularized Iterative Hessian Sketch (IHS) applied to the dual formulation of ridge regression. General embedding-based IHS guarantees apply when their geometric conditions hold. Pilanci and Wainwright [2] already exploit fresh sketches and directional distortion; Kacham and Woodruff [3, Lemma 3.3] analyze the same residual-direction matrix product. Our analysis builds on these ideas. The sharper expected error formulas of Lacotte and Pilanci [4, Theorem 4.1] require inverse moment identities satisfied by Gaussian sketches and studied for Haar sketches. Leverage sampling on an arbitrary design need not satisfy these identities. The asymptotic Haar/SRHT results of Lacotte et al. [5] are also sketch-specific. These results therefore do not directly yield our column sampling guarantees. Our contribution is to derive explicit finite-sample conditional variance bounds for column sampling and use their dependence on the probabilities to design residual-aware proposals. Optimizing this variance gives $p_i^\star\propto |x_i^{\star(j)}|\sqrt{w_i}$. Our proposal factor theorem propagates the quality of these changing distributions through the iteration, including pilot approximations and a defensive mixture. The contribution combines sampling-specific convergence guarantees with principled residual-aware sampling within the established iterative framework. **References** [1] A. Chowdhury, J. Yang, and P. Drineas. An iterative, sketching-based framework for ridge regression. *ICML*, 2018. [2] M. Pilanci and M. J. Wainwright. Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares. *JMLR*, 2016. [3] P. Kacham and D. P. Woodruff. Sketching algorithms and lower bounds for ridge regression. *ICML*, 2022. [4] J. Lacotte and M. Pilanci. Faster least squares optimization. *arXiv:1911.02675v3*, 2021. [5] J. Lacotte, S. Liu, E. Dobriban, and M. Pilanci. Optimal iterative sketching with the subsampled randomized Hadamard transform. *NeurIPS*, 2020.
Reviewer_NfyFOpenReview ↗

Reply

Thank you for rebuttal. However, I believe the novelty in terms of techniques is still limited and will keep my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.