PaperlayerView exact revision on arXiv

Source-linked AI summary

A Statistical Perspective on Algorithmic Leveraging

Ping Ma, Michael W. Mahoney, Bin Yu

arXiv:1306.5362v1stat.MEcs.LGstat.ML

TL;DR

The paper addresses the lack of statistical analysis for leverage-based sampling, which had previously been studied mainly for algorithmic and numerical benefits. It develops a Taylor-based bias-and-variance framework for linear-regression subsampling, finds no statistical dominance between leverage and uniform sampling, and proposes empirically improved variants.

  • Problem

    Prior work on algorithmic leveraging focused on algorithmic and numerical issues rather than its statistical bias and variance for parameter estimation.

  • Method

    The paper analyzes linear-regression subsampling estimators with a Taylor expansion around ordinary least squares and proposes SLEV and LEVUNW.

  • Results

    Neither leverage-based nor uniform sampling dominates in bias and variance; empirical studies on synthetic and real data indicate that the theory predicts practice and the new algorithms improve performance.

  • Takeaways & Limitations

    Statistical evaluation complements worst-case algorithmic analysis by revealing trade-offs that motivate shrinked leverage scores and unweighted leveraging.

  • Takeaways & Limitations

    The analysis concerns parameter estimation in Gaussian linear regression with a fixed predictor matrix and a fixed number of predictors.

Abstract

from arXiv · show

One popular method for dealing with large-scale data sets is sampling. For example, by using the empirical statistical leverage scores as an importance sampling distribution, the method of algorithmic leveraging samples and rescales rows/columns of data matrices to reduce the data size before performing computations on the subproblem. This method has been successful in improving computational efficiency of algorithms for matrix problems such as least-squares approximation, least absolute deviations approximation, and low-rank matrix approximation. Existing work has focused on algorithmic issues such as worst-case running times and numerical issues associated with providing high-quality implementations, but none of it addresses statistical aspects of this method. In this paper, we provide a simple yet effective framework to evaluate the statistical properties of algorithmic leveraging in the context of estimating parameters in a linear regression model with a fixed number of predictors. We show that from the statistical perspective of bias and variance, neither leverage-based sampling nor uniform sampling dominates the other. This result is particularly striking, given the well-known result that, from the algorithmic perspective of worst-case analysis, leverage-based sampling provides uniformly superior worst-case algorithmic results, when compared with uniform sampling. Based on these theoretical results, we propose and analyze two new leveraging algorithms. A detailed empirical evaluation of existing leverage-based methods as well as these two new methods is carried out on both synthetic and real data sets. The empirical results indicate that our theory is a good predictor of practical performance of existing and new leverage-based algorithms and that the new algorithms achieve improved performance.

1 Introduction

The paper extends algorithmic leveraging from an algorithmic focus to statistical analysis of bias and variance in large-scale linear regression. It shows that leverage-based and uniform sampling have different statistical trade-offs, then proposes two new leveraging methods and evaluates them empirically.

  • Motivation: Sampling reduces large data sets to smaller surrogate problems before computations such as regression or matrix approximation.The approach selects rows, constraints, or variables and uses the resulting subproblem for computation.
  • Existing paradigm: Algorithmic leveraging samples according to empirical statistical leverage scores and has been applied to least-squares, least absolute deviations, and low-rank approximation.These applications target computational efficiency in large-scale data analysis.
  • Contribution: The paper provides an analytic framework for statistical properties by using Taylor expansion around the ordinary least-squares solution.The framework approximates subsampling estimators as linear combinations of random sampling matrices and studies conditional and unconditional bias and variance.
  • Main result: Neither leverage-based nor uniform sampling dominates the other statistically in bias and variance, despite leverage-based sampling's uniformly superior worst-case algorithmic results.Leverage sampling improves variance size scale relative to uniform sampling, but very small leverage scores can substantially inflate variance.
  • New algorithms: SLEV increases low-leverage sampling probabilities, while LEVUNW uses leverage-based sampling followed by an unweighted least-squares subproblem.Both methods are designed to improve bias and variance relative to vanilla leveraging and uniform sampling while retaining leverage-based algorithmic benefits.
  • Empirical evaluation: Empirical evaluations on synthetic and real data indicate that the theory predicts practical performance and that the two new algorithms improve performance.The study also reports improved conditional and unconditional bias and variance from shrinked leverage scores and, typically, from solving a biased subproblem.

2 Background, Notation, and Related Work

This section introduces least-squares regression, leverage-based subsampling, and two proposed estimator variants. SubsampleLS samples rows with replacement, rescales them, and solves a smaller weighted problem whose coefficient dimension matches the original estimator.

  • Linear models: The paper studies parameter estimation in a Gaussian linear regression model with fixed design matrix X and Gaussian noise.The model uses coefficient vector β0 and noise ϵ ∼ N(0, σ2I).
  • Notation: Statistical leverage is the diagonal of the regression hat matrix and quantifies the influence of each observation in the design matrix.Leverage scores can also be expressed using an orthogonal basis for the column space of X.
  • SubsampleLS: SubsampleLS samples r > p rows and responses using probabilities πi, rescales each sampled row by 1/(rπi), and solves the weighted least-squares subproblem.Sampling is represented with a random sampling matrix and rescaling with a diagonal reweighting matrix.
  • SubsampleLS: The resulting weighted subproblem estimates the original least-squares solution while retaining the original coefficient dimension.Approximation quality depends critically on the sampling probabilities.
  • Proposed estimators: SLEV samples and reweights using a convex combination of normalized leverage-score and uniform distributions.The mixture is controlled by α ∈ (0, 1).
  • Proposed estimators: LEVUNW samples with leverage probabilities but solves an unweighted least-squares estimator, separating the sampling distribution from the reweighting distribution.This differs from the other estimators, which use the same distribution for sampling and reweighting.
  • Running time: Leverage-based implementations can outperform QR decompositions or SVD in running time for matrices as small as several thousand by several hundred.The section discusses implementations designed for large-scale parallel environments.

3 Bias and Variance Analysis of Subsampling Estimators

The paper develops Taylor-series methods to analyze bias and variance in subsampling estimators, comparing leverage-based and uniform sampling and motivating two new algorithms. The analysis identifies complementary statistical trade-offs and conditions affecting variance and approximate unbiasedness.

  • Analytic framework: Taylor-series expansions approximate subsampling estimators as linear combinations of random sampling matrices, enabling conditional and unconditional bias–variance analysis.The expansion is taken around the expected sampling-probability vector or the full-sample least-squares solution.
  • LEV and UNIF: Neither LEV nor UNIF is uniformly better statistically: LEV has a smaller p/r variance scale, while UNIF avoids inflation from very small leverage scores.LEV variances can grow arbitrarily with 1/hii, whereas UNIF has an n/r scale and is not inflated by small leverage scores.
  • New algorithms: SLEV mixes leverage-score and uniform probabilities, raising small probabilities and shrinking large leverage scores to limit variance inflation.With 1−α = 0.1, its minimum probability is at least 0.1/n, and the required oversampling relative to LEV is about 10%.
  • New algorithms: LEVUNW uses leverage-based sampling to construct an unweighted, biased least-squares subproblem, with expectation results describing approximate centering under different conditioning regimes.When leverage scores are equal, its variance matches uniform sampling; more generally, the cited variance is not inflated by very small leverage scores.
  • Bias: Both leverage-based and uniform sampling are unbiased to leading order when the linear approximation is valid.The conditional result concerns approximation to the full-sample least-squares estimate; the unconditional result concerns approximation to the true parameter under the stated negligible-remainder condition.
  • Interpretation: The statistical properties of algorithmic leveraging can differ substantially from its worst-case algorithmic advantages.The paper frames this contrast as the central distinction between algorithmic and statistical evaluation.

4 Main Empirical Evaluation

The empirical evaluation uses synthetic regression data spanning nearly uniform to very nonuniform leverage scores, then compares LEV, UNIF, SLEV, and LEVUNW through bias and variance. Results broadly corroborate the theory: LEV improves over UNIF when leverage scores are nonuniform, while SLEV with α≈0.9 and LEVUNW offer complementary advantages.

  • 4.1 Description of Synthetic Data: Synthetic data span nearly uniform, moderately nonuniform, and very nonuniform leverage-score regimes using GA, T3, and T1 designs.The simulations use y = Xβ + ϵ with ϵ ∼ N(0, 9I_n) across 1000 runs and multiple n,p settings.
  • 4.2 Leveraging Versus Uniform Sampling on Synthetic Data: LEV and UNIF have similar performance for GA, diverge more for T3 and T1, and LEV generally achieves lower MSE when they differ.The contrast tracks the increasing nonuniformity of leverage scores across the three data-generating models.
  • 4.2 Leveraging Versus Uniform Sampling on Synthetic Data: Variance decreases roughly as 1/r, with LEV following a p/r leading term while UNIF decreases more slowly in line with an n/r term.Both squared bias and variance generally decrease as subsample size increases, while bias remains much smaller than variance.
  • 4.3 Improvements from Shrinked Leveraging and Unweighted Leveraging: For SLEV, increasing α generally reduces bias and variance; α≈0.9 is slightly better than LEV, whereas LEVUNW often has the smallest unconditional bias and variance for T3 and T1.SLEV with α≈0.1 performs notably worse, similarly to UNIF.
  • 4.4 Conditional Bias and Variance: LEVUNW has lower conditional variance for T3 and T1 but can have larger bias than UNIF under very aggressive downsampling; for moderate to large r, its bias is substantially lower than UNIF.LEVUNW is approximately unbiased relative to the full-sample weighted least-squares estimate, not the unweighted estimate.
  • 4.4 Conditional Bias and Variance: The default recommendation is SLEV with α≈0.9 because it is close to LEVUNW unconditionally and can be much better conditionally.The recommendation applies with either exact or approximate leverage scores.

5 Additional Empirical Evaluation

Additional experiments examine rank loss, fast approximate leverage scores, and real data. They show that leverage-based methods generally preserve rank with fewer samples, fast approximations retain nearly identical statistical results, and practical behavior follows the synthetic-data findings.

  • Singular subproblems: UNIF commonly produces singular subproblems under aggressive downsampling, whereas LEV preserves rank with roughly r/p ≥ 2 in the reported synthetic examples.With fewer than 100 samples, nearly all UNIF subproblems were singular; more than 300 samples were needed for nearly all to be nonsingular.
  • Singular subproblems: LEV outperforms UNIF in rank preservation, especially when leverage scores are nonuniform.When singularity occurs, many dimensions may be omitted from the subproblem, changing estimator bias and variance.
  • Bias and variance: In aggressive downsampling, LEV variance can be choppy and worse than UNIF, while both LEV variance and bias decrease as r increases.The reported degradation may be related to rank-deficiency issues.
  • Fast approximate leveraging: Fast approximate leverage-score algorithms can run faster than exact methods for sufficiently large problems and permit data roughly 1.5 times larger in n or p.For very small matrices, projection and matrix-multiplication overhead can make the fast algorithms slightly slower.
  • Fast approximate leveraging: Using exact, BFast, or GFast leverage scores yields nearly identical statistical results for LEV, SLEV, and LEVUNW, while improving algorithmic performance.This pattern was observed for variances and was reported overall for the evaluated estimators.
  • Real data: In the RNA-Seq data set, nearly uniform leverage-score probabilities imply that leverage-based methods perform similarly to uniform sampling.The data contain n = 51,751 observations and use p = 121 parameters.

6 Discussion and Conclusion

The discussion contrasts algorithmic and statistical evaluations of algorithmic leveraging. It concludes that new statistically motivated methods improve statistical performance while retaining the usual algorithmic benefits.

  • Discussion: Worst-case algorithmic analysis favors leverage-based sampling uniformly, but statistical bias and variance comparisons show no universal dominance over uniform sampling.The contrast motivates evaluating leveraging from both perspectives.
  • Conclusion: The paper’s empirical evaluation indicates that its theory predicts practical performance for existing and newly proposed leveraging methods.The conclusion also reports improved statistical performance from the new methods.
  • Conclusion: The statistical framework bridges algorithmic and statistical perspectives and supports more refined questions about leveraging and related algorithmic frameworks.The authors identify differences among formulations in statistics, computer science, machine learning, and numerical linear algebra as a challenge addressed by the paper.

A Asymptotic Analysis and Toy Data

This appendix relates the paper’s analytic approach to asymptotic relative efficiency and uses toy data sets to illustrate algorithmic leveraging.

  • Appendix overview: The appendix connects the analytic methods to asymptotic relative efficiency and examines toy data sets illustrating aspects of algorithmic leveraging.These results are presented as supplementary material and are not used elsewhere in the paper.

A.1 Asymptotic Relative Efficiency Analysis

The paper compares UNIF, LEV, SLEV, and LEVUNW through asymptotic relative efficiency for linear combinations of parameter estimates. The analysis uses leading-order expressions under an asymptotic parameterization of (X^T X)^−1.

  • Relative efficiency: Relative efficiency compares sample sizes required by two estimators to meet a performance standard, with smaller variance corresponding to greater efficiency.For p-dimensional estimates, the comparison is made for linear combinations c^T β̂ and c^T β̃.
  • Relative efficiency: The asymptotic analysis compares UNIF with LEV, SLEV, and LEVUNW using leading-order relative-efficiency expressions.Analogous comparisons among SLEV, LEV, and LEVUNW can also be derived.
  • Theoretical comparisons: Lemmas characterize the leading-order asymptotic relative efficiencies of LEV, SLEV, and LEVUNW against UNIF.The displayed expressions ignore residual variance and may be difficult to evaluate on real or synthetic data because they are expressed in terms of α_n.

A.2 Illustration of the Method on Toy Data

The toy examples show that leverage-score structure strongly shapes the bias and variance of sampling-based regression estimates. Depending on the data configuration and parameter values, uniform, leverage-based, and the two modified methods can each have different statistical behavior.

  • Toy-data setup: Toy examples isolate how leverage-score structure affects algorithmic leveraging, including uniform, highly nonuniform, and worst-case configurations.The examples emphasize extreme cases that also illuminate less extreme behavior in realistic data.
  • Uniform scores: Uniform leverage scores make algorithmic leveraging equivalent to uniform sampling, with all four estimators having equal variances in the simple linear-combination example.For the sample-mean example, all three asymptotic efficiencies are O(1); for the simple linear combination, the unconditional variances equal σ2{1/r}.
  • Variance comparisons: SLEV and LEVUNW can have smaller variance than LEV and UNIF in selected settings, while LEV and UNIF can each outperform the other depending on problem parameters.SLEV increases the probability of low-leverage samples, whereas LEVUNW uses an unweighted leverage-subsampled subproblem and is therefore biased for a given data set.
  • Nonuniform scores: Very small leverage scores can inflate leveraging variance because the variance terms depend on inverse leverage scores.The paper gives hii = 1/n4 as an extreme case in which a variance term for LEV is much larger than for UNIF.
  • Illustrated variance patterns: Adding an intercept tends to increase small leverage scores, and in the Regression Surface example the four estimates’ variances become close as n grows.For the Inflated Regression Line, variances generally decrease with increasing n, whereas the In-fill Regression Line exhibits roughly flat or slightly increasing variances.
  • Example comparison: Examples with uniform leverage scores are statistically favorable, whereas the truncated Identity and Worst-case Matrix examples are problematic for statistical performance for different reasons.The truncated Hadamard and random Gaussian examples provide near-uniform leverage scores, while the truncated Identity and Worst-case Matrix examples produce highly nonuniform scores.

B Appendix: Proofs of our main results

This appendix section begins the paper’s proof development by stating that it will establish proofs of several main results.

  • Appendix overview: The section introduces the appendix proof sequence for several of the paper’s main results.No specific lemma, derivation, or conclusion is supplied in the passage.

B.1 Proof of Lemma 1

The proof of Lemma 1 develops derivatives of the weighted regression estimator around full-sample least squares using matrix-calculus identities and vectorization.

  • Setup: The sampling process is represented by X and includes UNIF, LEV, and SLEV as special cases.The results are stated to hold more generally than these three sampling schemes.
  • Expansion: A Taylor expansion around the all-one weight vector connects the weighted estimator to the full-sample ordinary least-squares estimate.The expansion uses a second-order remainder that is op(||w − w0||) near w0 = 1.
  • Matrix calculus: The derivation simplifies the estimator’s derivatives through differentiation by parts, vectorization, Kronecker products, and matrix-differentiation results.The cited steps combine these identities by algebra and the chain rule.
  • Conclusion: The displayed derivative expression uses the least-squares residual vector and coordinate vectors to complete the lemma’s proof.The passage defines ˆe as the ordinary least-squares residual vector and ei as the ith coordinate vector.

B.2 Proof of Lemma 2

The proof of Lemma 2 derives conditional and unconditional expectation and variance results for the sampling-weighted estimator, then specializes the sampling probabilities to leverage scores.

  • Conditional result: The proof treats W as the sampling process and begins by establishing a conditional result.It uses E[w] = 1 to calculate the estimator’s conditional expectation.
  • Variance derivation: The conditional variance is rewritten in matrix form and expressed using the sampling-probability vector π and the all-ones matrix Jn.Additional algebra produces the variance expression for ˜βW.
  • Variance decomposition: The proof separates a term involving X(XT X)−1 from the variance of the remainder term RW.This decomposition appears in the matrix-form variance expression.
  • Leverage specialization: Setting πi = hii/p specializes the general sampling result to leverage-based probabilities and establishes the conditional conclusion.The passage states that this substitution proves the conditional result.
  • Unconditional result: The unconditional result follows by taking expectations over the response and applying the rule of double expectations to obtain variance.The proof concludes by deriving the corresponding expectation and variance results.

B.3 Proof of Lemma 5

The proof expands the unweighted leveraging estimator around its expected multinomial sampling weights. It expresses the estimator as a weighted least-squares estimate plus a linear perturbation and a remainder.

  • The unweighted leveraging weights wLEV UNW follow a multinomial distribution Multi(r, π).
  • The Taylor expansion writes ˜βLEV UNW as ˆβwls plus a first-order perturbation in wLEV UNW − w0 and a remainder RLEV UNW.
  • The expansion uses W0 = Diag{rπ}, the weighted least-squares estimator ˆβwls, and the weighted LS residual vector ˆew.

B.4 Proof of Lemma 6

The proof derives the conditional expectation and variance of the unweighted leveraging estimator from its Taylor expansion and multinomial sampling distribution. The expectation uses the weights’ mean, while the variance includes a first-order term and the remainder variance.

  • Taking conditional expectation of the Taylor expansion yields ˆβwls plus a weight-deviation term and Ew[RLEV UNW].
  • Because Ew[wLEV UNW] = rπ, the expectation simplifies using the multinomial weights’ mean.
  • The conditional variance contains the weighted residual term and the remainder contribution Varw[RLEV UNW].
  • The resulting variance expression is (XT W0X)−1XT Diag{ˆew}W0Diag{ˆew}X(XT W0X)−1 + Varw[RLEV UNW].

B.5 Proof of Lemma 7

The proof establishes asymptotic variance orders for leveraging and uniform estimators by bounding their second variance components. It also uses a leverage-based matrix bound for the unweighted estimator.

  • The variance of a contrast cT˜βLEV is obtained from cT Var(˜βLEV)c, motivating analysis of Var(˜βLEV).
  • Cauchy–Schwarz bounds are used to control the second variance component of ˜βLEV.
  • The proof analogously derives the order of the second variance component for ˜βUNIF.
  • The same bounding strategy is applied to the second variance component of ˜βLEV UNW.
  • The matrix bound (XT Diag{hii}X)−1 = O(1/(min(hii)αn)) supports the unweighted leveraging variance analysis.
Loading 1306.5362v1…