A statistical perspective on algorithmic leveraging
A statistical perspective on algorithmic leveraging
复制标题
DOI：
10.5555/2789272.2831141
复制
发表时间：
2013-06
期刊：
影响因子：
--
通讯作者：
Ping Ma;Michael W. Mahoney;Bin Yu
中科院分区：
文献类型：
--
作者：
Ping Ma;Michael W. Mahoney;Bin Yu
处理大规模数据集的一种流行方法是抽样。该方法使用经验统计杠杆得分作为重要抽样分布，在对子问题进行计算之前利用样本和重新缩放数据矩阵来减小数据大小。现有的工作主要集中在算法问题上，但没有一项工作涉及到这种方法的统计方面。在这里，我们提供了一个有效的框架来评估线性回归模型中估计参数的算法杠杆的统计特性。特别是，对于基于杠杆的抽样的几种版本，我们得出了偏差和方差的结果。我们发现，从偏差和方差的统计角度来看，杠杆抽样和均匀抽样都不会主导另一种抽样。这一结果尤其令人震惊，因为众所周知的结果是，从最坏情况分析的算法角度来看，与均匀抽样相比，基于杠杆的抽样提供了一致优越的最坏情况算法结果。在这些理论结果的基础上，我们提出并分析了两种新的杠杆算法：一种是构造一个具有“收缩”杠杆得分的较小最小二乘问题(SLEV)，另一种是求解一个较小且未加权(或有偏)的最小二乘问题(LEVUNW)。实验结果表明，我们的理论可以很好地预测现有的和新的基于杠杆的算法的实际性能，并且新算法的性能得到了提高。
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.