A statistical perspective on algorithmic leveraging

By Ping Ma, Michael W. Mahoney, Bin Yu. 2013

405 citations recorded by the source corpus.

One popular method for dealing with large-scale data sets is sampling. Using the empirical statistical leverage scores as an importance sampling distribution, the method of algorithmic leveraging samples and rescales data matrices to reduce the data size before performing computations on the subproblem. Existing work has focused on algorithmic issues, but none of it addresses statistical aspects of this method. Here, we provide an effective framework to evaluate the statistical properties of algorithmic leveraging in the context of estimating parameters in a linear regression model. In particular, for several versions of leverage-based sampling, we derive results for the bias and variance. 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: one constructs a smaller least-squares problem with "shrinked" leverage scores (SLEV), and the other solves a smaller and unweighted (or biased) least-squares problem (LEVUNW). 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.

Subfields: Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Science and Operations Research

Citations in the corpus

Continual Deep Learning by Functional Regularisation of Memorable Past (2020, background): “These ideas are widely used in the theory of leverage-score sampling (Alaoui & Mahoney, 2015; Ma et al., 2015), where datapoints are picked proportional to the leverage score.”
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm (2013, neutral): “the squared Euclidean norms of rows and columns of the underlying matrix. See [5, 25, 44, 9], and references therein for applications to the column subset selection problem and matrix completion. See [14, 24, 48] for applications of importance sampling to the Nystro¨m Method. Importance sampling has”
GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, methodology): “Following Ma et al. (2014), Yang et al. (2016), we generate four kinds of data matrices, X ∈ n d , with diﬀerent row coherence parameters and condition numbers: coherent and has low condition number; • X = U C diag ( σ H ) V T is coherent and has high condition number; • X = U I diag ( σ L ) V T is…”
Optimal subsampling for quantile regression in big data (2020, background): “ information from massive data with limited computing power. This idea has attracted much attention with extensive literature such as Drineas et al. (2012); Dhillon et al. (2013); Yang et al. (2013); Ma et al. (2015); Wang et al. (2018). Most existing work takes an algorithmic approach and focuses o”
Revisiting the Nystrom Method for Improved Large-scale Machine Learning (2013, background): “For data sets with more nonuniform leverage score properties, random projections and leverage-based sampling will do better (Ma et al., 2014).”
Handbook of Big Data (2016, background): “Because the general multivariate analysis problem is to make statistical inference about the association among variables, increasing n has the eﬀect of improving the certainty of inference due to improved precision of estimates, whereas increasing p has the contrary eﬀect of reducing the certainty…”
Mapping information-rich genotype-phenotype landscapes with genome-scale Perturb-seq (2021, methodology): “We used an approach based on leverage scores, which measure how outlying the rows or columns of a matrix are and which form the basis for many randomized algorithms (Ma et al., 2013).”
Continual Learning via Online Leverage Score Sampling (2019, methodology): “Theoretical accuracy guarantees have been derived for random sampling methods based on statistical leverage scores [37, 20].”
Training Deep Models Faster with Robust, Approximate Importance Sampling (2018, methodology): “Leverage score sampling uses a closely related concept for matrix approximation algorithms [20, 21].”