A Statistical Perspective on Algorithmic Leveraging

Abstract

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.

44 pages, 17 figures

References in corpus (1)

• The Big Data Bootstrap

Cited by in corpus (28)

• Revisiting the Nystrom Method for Improved Large-Scale Machine Learning
• A Distributed and Incremental SVD Algorithm for Agglomerative Data Analysis on Large Networks
• Random projections for Bayesian regression
• Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm
• Fast and Robust Least Squares Estimation in Corrupted Linear Models
• A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
• The Singular Value Decomposition, Applications and Beyond
• Optimal Cox Regression Subsampling Procedure with Rare Events
• Randomized methods to characterize large-scale vortical flow network
• A determinantal point process for column subset selection
• Theory of Dual-sparse Regularized Randomized Reduction
• Optimal Sampling Designs for Multi-dimensional Streaming Time Series with Application to Power Grid Sensor Data
• Implementing Randomized Matrix Algorithms in Parallel and Distributed Environments
• Efficient Algorithms and Error Analysis for the Modified Nystrom Method
• An Explicit Sampling Dependent Spectral Error Bound for Column Subset Selection
• Active sampling: A machine-learning-assisted framework for finite population inference with optimal subsamples
• Continual Learning via Online Leverage Score Sampling
• Signatures of partition functions and their complexity reduction through the KP II equation
• A Bootstrap Method for Error Estimation in Randomized Matrix Multiplication
• An Asymptotic Analysis of Minibatch-Based Momentum Methods for Linear Regression Models
• Gradient-based Sampling: An Adaptive Importance Sampling for Least-squares
• Compressed and Penalized Linear Regression
• Poisson Subsampling Algorithms for Large Sample Linear Regression in Massive Data
• Sampling-Based Methods for Multi-Block Optimization Problems over Transport Polytopes
• On the asymptotic properties of a bagging estimator with a massive dataset
• Smoothing spline ANOVA for super-large samples: Scalable computation via rounding parameters
• Coresets for Regressions with Panel Data
• Subsampled One-Step Estimation for Fast Statistical Inference