PaperlayerView exact revision on arXiv

Source-linked AI summary

The Advantages of Fresh Sketching for Ridge Regression

Linkai Ma, Qilin Li, Petros Drineas

arXiv:2609.38565v1cs.LG

TL;DR

The paper asks whether fresh sketches offer provable advantages for iterative ridge regression with column sampling. It analyzes error along the current residual, derives residual-aware sampling rules, and reports sharper guarantees and experimental convergence advantages.

  • Problem

    Whether fresh randomness improves iterative ridge regression with column sampling has remained an open question.

    Source: §1 · p. 1

  • Method

    The analysis uses conditional independence of fresh sketches to study directional error and derive a variance-minimizing oracle sampling rule with practical adaptive and mixture approximations.

    Source: §1 · p. 2

  • Results

    The fresh-sampling bounds avoid logarithmic factors in sampling-size complexity for the iterative ridge regression framework, while experiments show convergence advantages for residual-aware rules.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    Residual-aware sampling probabilities can be chosen from the variance of the sketched matrix-vector product, using the current residual solution alongside ridge leverage information.

    Source: §1 · p. 2

    The sharper oracle, adaptive, and mixture guarantees depend on factors determined by the residual trajectory and proposal quality that are unknown before the algorithm runs.

    Source: §7 · p. 9

Abstract

from arXiv · show

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.

1 INTRODUCTION

The introduction asks whether fresh sketches improve iterative ridge regression and argues that analyzing error along the current residual yields sharper guarantees and residual-aware sampling.

1 INTRODUCTION

  • The paper studies whether fresh randomness helps iterative ridge regression with column sampling, where column sampling approximates the Gram matrix using fewer features.Earlier fixed-sketch analysis had experiments suggesting fresh samples could accelerate convergence and reduce the sketch size needed, motivating a question about stronger guarantees.Source: §1 · pp. 1–2
  • Fresh sketches require accuracy only along the current residual ridge solution, so analysis can control a sketched matrix-vector product instead of a uniform matrix-matrix approximation.Conditional independence from previous iterations permits variance analysis and propagation of directional error.Source: §1 · p. 2
  • Minimizing the variance of the governing sketched matrix-vector product yields an oracle distribution combining ridge leverage information with the current residual, plus practical adaptive and mixture approximations.The adaptive method uses an initial ridge pilot sketch to approximate the residual; mixture methods combine that proposal with ridge leverage scores.Source: §1 · pp. 2–3
  • At moderate ∥A∥2/λ, fresh leverage score and ridge leverage score sampling achieve geometric convergence using O(n/ε2) and O(dλ/ε2) columns per iteration, saving factors of log n and log(1 + dλ) over Chowdhury et al. (2018).The bounds retain the same geometric rate; dλ is the effective degrees of freedom.Source: §1 · p. 2
  • Experiments on ARCENE, synthetic data, and Qwen2.5 ridge probes show convergence advantages for residual-aware sampling across iteration counts, sketching budgets, and regularization parameters.The experiments also compare fixed and fresh sketches on ARCENE.Source: §1 · p. 3

2 PROBLEM SETUP AND ITERATIVE SOLVER

This section sets up column sampling for ridge regression and describes an iterative solver that draws a fresh sketch as it corrects the residual.

2 PROBLEM SETUP AND ITERATIVE SOLVER

  • The effective degrees of freedom dλ is defined from the regularized singular values and satisfies 0 < dλ < n.The section defines dλ as ∥Σλ∥2, with Σλ = Σ(Σ2 + λIn)−1/2.Source: §2 · p. 3
  • Column sampling independently draws feature indices from a probability distribution and rescales the sampled columns to form a sketch; leverage scores and ridge leverage scores are baseline distributions.The analysis assumes full row rank with d > n > 1 and strictly positive sampling probabilities.Source: §2 · p. 3
  • At each iteration, the solver updates the residual, draws a fresh sketch using the iteration's size and probabilities, and solves a sketched ridge regression problem.For baseline distributions, sketches are independent across iterations; residual-aware distributions depend on past randomness.Source: §2 · p. 3
  • The final solution error reduces to successive residual errors, linking convergence of the iteration to the residual problems it solves.The stated identities express the final error through the last residual solution and successive corrections.Source: §2 · p. 4

3 LEVERAGE SAMPLING

Fresh sketches reduce the required approximation from uniform Gram-matrix control to control along the current residual direction. This supports sharper leverage-score convergence guarantees and, under stated conditions, smaller sketches.

3 LEVERAGE SAMPLING

  • The analysis controls the sketched matrix-vector product along the current residual solution, rather than uniformly approximating the Gram matrix.This directional control is the basis for the leverage-score convergence result.Source: §3 · p. 4
  • With probability at least 1−δ0, the reported bounds give expected squared error at most ε²t||x⋆||² and final relative error at most δ0^-1/2 εt.The bounds apply for fixed t and δ0∈(0,1).Source: §3 · p. 5
  • When σ²_max/λ is controlled, fresh leverage-score sketches save a factor of log n in required sketch size versus Chowdhury et al. (2018).A separate bound using larger sketches improves the contraction factor by O(1/√log n).Source: §3 · p. 5
  • When C(n−1)²δ(s(j))≤ε²/2, independence yields an algorithmic bias bound of ε²t||x⋆||².The passage points to Theorem E.3 for a sufficient sketch size.Source: §3 · p. 5

4 RIDGE LEVERAGE SAMPLING

Ridge leverage score sketches bound error through a sketched matrix-vector product applied to the current residual solution. Under the stated conditions, the analysis improves sketch-size and contraction guarantees.

4 RIDGE LEVERAGE SAMPLING

  • The residual-solve error is bounded using the sketched matrix-vector product applied to the current residual solution.When ||E(j)||₂≤ε<1, the passage gives a sharper bound.Source: §4 · p. 5
  • Conditional variance control for independent ridge leverage sketches combines with the residual-solve error bound to establish convergence.The stated convergence result is for Algorithm 1 with ridge leverage score sampling.Source: §4 · pp. 5–6
  • Ridge leverage score sampling saves a factor of log dλ in sketch size versus Chowdhury et al. (2018) when cλ is moderate.A separate bound uses larger sketches and gains a contraction factor of O(1/√log dλ).Source: §4 · p. 6

5 RESIDUAL-AWARE SAMPLING

Residual-aware sampling uses the current residual solution to choose probabilities that minimize variance in the relevant sketched matrix-vector product. The oracle motivates practical adaptive and mixture proposals, with guarantees that depend on their variance factors.

5 RESIDUAL-AWARE SAMPLING

  • The oracle sampling distribution combines ridge leverage information with the current residual solution to minimize variance in the relevant matrix-vector product.The optimal-sampling proposition introduces this residual-dependent design.Source: §5 · p. 6
  • Numerical experiments suggest ρ(x) is very close to 2/π, the Gaussian reference value used to quantify departures from normality.For the language-model application, the reported Wasserstein-distance quantity Δ is small and generally decreases with scale.Source: §5 · pp. 6–7
  • When the oracle factor is bounded by ρ̄, a sketch size proportional to λρ̄dλ/ε² yields the same δ^-1/2εt relative-error guarantee as Theorem 4.3.The bound applies when the factor is bounded at iterations with nonzero residual.Source: §5 · p. 7
  • The oracle requires the unknown residual solution, so the practical adaptive proposal uses an initial ridge leverage sketch to approximate it.The pilot approximation's variance factors can exceed one, so it alone does not establish contraction.Source: §5 · p. 7
  • The mixture proposal's sketching error is bounded by 1/α times the ridge-leverage error regardless of pilot accuracy, and size proportional to λdλ/(αε²) guarantees mean-square contraction by ε² per iteration.These guarantees are stated for the mixture method.Source: §5 · p. 7

6 EXPERIMENTS

Across ARCENE, synthetic data, and Qwen2.5 ridge probes, the experiments compare six sampling methods and show benefits for residual-aware sampling. A separate comparison finds that fresh sketches avoid the eventual error growth seen with reused sketches at smaller budgets.

Sampler comparisons and settings

  • The six methods are compared using solution error, objective excess, sketch-size and regularization sweeps, and directional-factor panels.Adaptive methods divide their total column budget between an initial pilot and later updates.Source: §6 · p. 7

Comparison with the leverage baselines

  • On ARCENE, the oracle reaches numerical precision faster than three baselines, while adaptive and mixture sampling behave similarly to the oracle and retain lower errors across sketch-size and regularization sweeps.The synthetic-data results are similar, though the gap between the three baselines is smaller.Source: Figure 1 · p. 8, §6 · p. 8

Fixed versus fresh sketches

  • Across the two smaller budgets, median errors eventually grow for every reused-sketch baseline; residual-aware methods reduce errors at every tested budget.At the smallest budget, fresh uniform and leverage sampling also show growing median errors, while fresh ridge leverage makes little progress.Source: §6 · p. 8

Ridge probing of language model representations

  • On the Qwen2.5 probe, residual-aware sampling outperforms the baselines, while uniform sampling converges significantly more slowly.The probe uses 102,400 features and 30 trials; Figure 2 uses the cross-validated λ = 104.5 for the main panels.Source: §6 · p. 8, Figure 2 · p. 9

Observed variance factors

  • Across three datasets, the mixture has lower median proposal factors and generally narrower interquartile bands than pure adaptive sampling.Panel (e) shows the best attainable directional factor along each method’s residual trajectory; panel (f) evaluates adaptive and mixture proposals.Source: §6 · pp. 8–9

7 CONCLUSION

The paper derives sharper fresh-sampling convergence bounds and residual-aware sampling strategies by analyzing sketched matrix-vector-product variance and using conditional independence. Its conclusion identifies unknown residual-trajectory and proposal-quality factors as a limitation of the sharper guarantees.

7 CONCLUSION

  • The analysis yields an oracle sampling rule that minimizes variance, plus adaptive and mixture strategies that approximate it, and experiments demonstrate gains in solution accuracy.The experiments include synthetic and real data, including ridge probes on pretrained Qwen2.5 hidden layers.Source: §7 · p. 9
  • Sharper guarantees for oracle, adaptive, and mixture sampling depend on residual-trajectory factors and, for practical methods, proposal quality, which are unknown before the algorithm runs.The stated worst-case bounds do not quantify experimental improvements; sharper a priori bounds remain an open question.Source: §7 · p. 9

A ALGORITHMS

  • Algorithm 3 uses a ridge-leverage pilot and cached factorization, then forms fresh sampling probabilities and solves a sketched system at each update.The returned estimate sums the per-iteration updates.Source: A ALGORITHMS · p. 15

B RUNNING TIME ANALYSIS

This material gives a per-iteration running-time bound and collects supporting concentration, residual-identity, and variance arguments for fresh column sampling. It also positions the framework relative to prior ridge-regression and sketching work.

B RUNNING TIME ANALYSIS

  • Each iteration costs O(nnz(A) + n^2 max(n, s)) when exact leverage or ridge leverage scores are provided.The bound accounts for matrix-vector products, sketch construction, forming the sketched system, and solving it.Source: B RUNNING TIME ANALYSIS · p. 15

C RELATED WORK

  • Kacham and Woodruff’s refreshed-sketch analysis controls error in the direction of the exact residual solution, the same matrix-vector product analyzed here.The section also surveys iterative sketching, preconditioning, and feature-sampling work.Source: C RELATED WORK · pp. 16–17

D.1 AN EXPLICIT EMBEDDING TAIL

  • The explicit embedding-tail argument specializes a prior concentration proof for the column-sampling laws while retaining its constants and admissibility condition..Source: §D.1 · p. 17

D.2 RESIDUAL IDENTITIES

  • The residual decomposition records identities for the iteration, obtained by substituting the SVD and telescoping the residual updates.The text identifies these as identities also used by Chowdhury et al. (2018).Source: §D.2 · p. 17

D.3 FIXED SKETCH COMPARISON

  • For the fixed-sketch comparison, leverage and ridge leverage sampling require sample sizes of order O(ε^-2 n ln n) and O(ε^-2 dλ ln dλ), respectively, with one sketch reused across iterations..Source: §D.3 · p. 18

E ADDITIONAL RESULTS FOR LEVERAGE SAMPLING

  • The additional leverage-sampling results assume independent sampling with replacement and show that rescaling makes the sketched covariance unbiased.The stated expectation is E[V^T S(j)S(j)^T V] = I_n, yielding E[bE(j)] = 0.Source: E ADDITIONAL RESULTS FOR LEVERAGE… · p. 18

E.1 ERROR IDENTITIES AND VECTOR VARIANCE

  • The error identities support vector-variance analysis; the conditional calculation applies after conditioning on the history of earlier sketches.The identities themselves require no independence assumption.Source: §E.1 · pp. 18–19

E.2 CONVERGENCE AT THE IMPROVED SAMPLE SIZE

The results use conditional variance and embedding-event arguments to establish convergence bounds for leverage sampling, and show that the mean-error identity cancels its linear term. A sketched matrix-vector-product bound links conditional variance to solution error.

E.2 CONVERGENCE AT THE IMPROVED SAMPLE SIZE

  • Conditioning on the past and applying the vector-variance lemma yields the stated mean-square contraction for the improved sample size.The high-probability statement follows from the corresponding bound and a terminal Markov inequality.Source: §E.2 · p. 20

E.3 CONVERGENCE ON THE EMBEDDING EVENT

  • The embedding-event result retains a uniform embedding condition and states a leverage-sampling sample-size assumption of s(j) ≥ 2n/ε^2..Source: §E.3 · p. 20

E.4 SQUARED CONTRACTION OF ALGORITHMIC BIAS

  • For algorithmic bias, the exact identity uses only mean-zero error and invertibility, canceling the linear term and leaving a quadratic quantity.No smallness assumption on the matrix error is required for this identity.Source: §E.4 · p. 22

F.1 ERROR IDENTITY AND CONDITIONAL VARIANCE

  • A solution-error bound relates the iterate’s error to a sketched matrix-vector product, while the section states a conditional variance identity for that product.The conditional calculation fixes the current vector by conditioning on the preceding sketch history.Source: §F.1 · p. 24

F.2 A CONVERGENCE THEOREM FOR RESIDUAL-AWARE DISTRIBUTIONS

The convergence analysis controls iterative error through conditional variance along the current residual solution. Under conditional sampling and specified sample-size conditions, it provides error bounds, including bounds on embedding events.

F.2 A CONVERGENCE THEOREM FOR RESIDUAL-AWARE DISTRIBUTIONS

  • The conditional-variance theorem assumes the sampling distribution and residual solution are fixed by the pre-sketch history, with independent draws for each sketch.The proof iterates a conditional one-step error bound to obtain final solution-error control.Source: §F.2 · pp. 24–25
  • The proof propagates the conditional one-step bound across iterations and relates the final iterate's error to the final residual error.It then applies Markov’s inequality to obtain a probability bound.Source: §F.2 · p. 25

F.3 CONVERGENCE ON THE EMBEDDING EVENTS

  • For ridge leverage sampling, each iteration uses at least 2dλ/ε² samples, and the stated sample-size condition bounds embedding failure probability by δemb.The proof bounds the inverse on the embedding event, then removes the event indicator before conditioning so the sampling law is unchanged.Source: §F.3 · pp. 25–26

G.1 ORACLE CONVERGENCE

The oracle result gives a trajectory-dependent convergence bound, while adaptive and mixture proposals address the practical use of residual-aware probabilities. The appendix also specifies how pilot and update sketches are budgeted in the experiments.

G.1 ORACLE CONVERGENCE

  • With oracle sampling, the relative error is at most δ^-1/2ε^t with probability at least 1−δ.The oracle convergence result defines its factor from the residual at each iteration.Source: §G.1 · p. 26

G.2 ADAPTIVE PROPOSALS AND A DEFENSIVE MIXTURE

  • Pure adaptive proposals do not bound proposal quality: small probabilities can make their factor arbitrarily large, whereas the defensive mixture bounds it uniformly.The mixture combines a proposal with ridge leverage probabilities.Source: §G.2 · p. 27

H.1 IMPLEMENTATION, METRICS, AND SAMPLING BUDGETS

  • The experiment mixture assigns α = 0.1 to ridge leverage probabilities, and adaptive and mixture methods use an initial pilot sketch.For these methods, the pilot and updates together use at most st sampled columns.Source: §H.1 · p. 28

H.2 ARCENE AND SYNTHETIC DATA

The experiments compare fresh and reused sketches and assess residual-aware sampling on synthetic, ARCENE, and Qwen2.5 ridge-probe settings. They also track proposal factors and the oracle factor’s relationship to a Gaussian reference.

H.2 ARCENE AND SYNTHETIC DATA

  • Fresh-sketch experiments compare six sampling laws, while a separate ARCENE comparison tests reused versus fresh baseline sketches; Figure 3 tracks errors and factor trajectories.The separate comparison uses λ = 10, 25 updates, and column budgets s ∈ {200, 400, 800, 1600}.Source: §H.2 · pp. 28–29, Figure 3 · p. 29

H.3 RIDGE PROBES ON QWEN2.5 REPRESENTATIONS

  • The ridge-probe experiment uses frozen Qwen2.5-32B-Instruct representations from 100 STS Benchmark training examples, concatenating 20 layers into 102,400 features per example.Its sampler comparisons include sketch-size and regularization sweeps.Source: §H.3 · pp. 29–30

H.4 VARIANCE FACTOR MEASUREMENTS

  • The diagnostics record the ideal oracle factor for each residual and the actual proposal factor relative to ridge leverage sampling.Adaptive trajectories are evaluated using the exact residual solution, rather than the pilot estimate; methods can have different residuals after their first update.Source: §H.4 · p. 31

H.5 GAUSSIAN REFERENCE FOR THE ORACLE FACTOR

  • For Qwen2.5 ridge probes, the Wasserstein distances from the standard normal are small and trend downward with increasing model size and feature dimension.Figure 5 plots final-layer representations across model sizes and layer-concatenated representations for Qwen2.5-14B and Qwen2.5-32B.Source: §H.5 · p. 31, Figure 5 · p. 32
Loading 2609.38565v1…