arXiv：cs.LG（机器学习，全量分类）· Linkai Ma, Qilin Li, Petros Drineas·· 5 小时前AI 评分38
新鲜草图（fresh sketching）在岭回归中的优势：arXiv 论文证明其可证优势
The Advantages of Fresh Sketching for Ridge Regression
AI 导读
针对列采样迭代岭回归中"复用同一草图还是每步重抽随机性"的开放问题，该论文证明新鲜草图（fresh sketching）具有可证优势。它使误差只需沿当前残差解分析，而非在整个 Gram 矩阵上一致成立，从而为 leverage score 与 ridge leverage score 采样给出更紧的收敛保证，并导出残差感知采样规则。
正文
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 $\textit{reuse}$ the same sketch or draw $\textit{fresh}$ randomness at every step. For (under-constrained) iterative ridge regression with column sampling, whether fresh sketches offer provable advantages has remained open: $\textit{We show that they do.}$ 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.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2609.38565 [cs.LG] |
| (or arXiv:2609.38565v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2609.38565 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Linkai Ma [view email]
[v1]
Tue, 29 Sep 2026 21:24:22 UTC (437 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org