- 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
-
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?
-
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)?
-
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
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.
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>d regime, compressing A⊤A using Frequent Directions as observations arrive. Our work considers the non-streaming, high-dimensional regime n≪d, using repeated column sampling to approximate the Gram matrix AA⊤ 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 when ℓ≥k+∣A−Ak∣F2/(λε), with time O(ndℓ) and space O(dℓ). Our fresh LS/RLS solver costs O(t(nnz(A)+n2s+n3)) 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 z. For leverage score sampling, with Ej=V⊤SjSj⊤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.