Metraipolis › archive › dc_0ca93ef604af

The Advantages of Fresh Sketching for Ridge Regression — arXiv:2609.38565

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.38565
License (as archived)
CC0-1.0
Archived
2026-10-07T13:45:22.444Z
SHA-256 of the archived text
3b8f9244a46b342126416467e365683a34f7dbf5f9807d2e91d9be05b2a9df37
Stable URL of this page
https://metraipolis.com/documento/dc_0ca93ef604af

How to cite

The Advantages of Fresh Sketching for Ridge Regression — arXiv:2609.38565 — arXiv (en), https://arxiv.org/abs/2609.38565 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0ca93ef604af (Metraipolis archive dc_0ca93ef604af, sha256 3b8f9244a46b342126416467e365683a34f7dbf5f9807d2e91d9be05b2a9df37)
BibTeX
@misc{dc0ca93ef604af,
  title = {The Advantages of Fresh Sketching for Ridge Regression — arXiv:2609.38565},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.38565},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0ca93ef604af; sha256 3b8f9244a46b342126416467e365683a34f7dbf5f9807d2e91d9be05b2a9df37},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.38565. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-10-01 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.38565 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T13:18:10.224Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).