Leveraged volume sampling for linear regression
Leveraged volume sampling for linear regression
复制标题
DOI：
--
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Michal Derezinski;Manfred K. Warmuth;Daniel J. Hsu
中科院分区：
文献类型：
--
作者：
Michal Derezinski;Manfred K. Warmuth;Daniel J. Hsu
假设线性回归问题中给出了一个n×d设计矩阵，但除非明确要求，否则每个点的响应都是隐藏的。我们的目标是只对一小部分回复进行抽样，然后产生一个权重向量，其在*所有*点上的平方损失之和至多是最小值的1+epsilon。当k非常小时(例如，k=d)，联合采样点的不同子集是至关重要的。其中一种称为“体积抽样”的方法有一个独特而理想的特性，即它产生的权重向量是对最优值的无偏估计。因此，自然会问这种方法是否提供了关于实现1+epsilon损失近似所需的响应数量k的最优无偏估计。令人惊讶的是，我们发现，当我们需要非常准确的近似时，体积抽样的表现可能很差--确实比某些I.I.D.更糟糕。估计有偏差的抽样技术，如杠杆得分抽样。然后，我们开发了一种新的重新缩放的体积抽样变体，它产生了避免这种不良行为的无偏估计，并且至少具有与杠杆得分抽样一样好的尾界：样本量k=O(dlogd+d/epsilon)足以高概率地保证总损失至多1+epsilon乘以最小值。因此，我们改进了以前已知的无偏估计的最佳样本量，k=O(d^2/epsilon)。我们的重定标过程导致了一种新的有效的体采样算法，该算法基于行列式拒绝采样技术，在行列式点过程中具有潜在的更广泛的应用。其他贡献包括引入重新调整体积抽样所需的组合学，以及开发在此过程中产生的相依随机矩阵和的尾界。
Suppose an n x d design matrix in a linear regression problem is given, but the response for each point is hidden unless explicitly requested. The goal is to sample only a small number k << n of the responses, and then produce a weight vector whose sum of squares loss over *all* points is at most 1+epsilon times the minimum. When k is very small (e.g., k=d), jointly sampling diverse subsets of points is crucial. One such method called "volume sampling" has a unique and desirable property that the weight vector it produces is an unbiased estimate of the optimum. It is therefore natural to ask if this method offers the optimal unbiased estimate in terms of the number of responses k needed to achieve a 1+epsilon loss approximation. Surprisingly we show that volume sampling can have poor behavior when we require a very accurate approximation -- indeed worse than some i.i.d. sampling techniques whose estimates are biased, such as leverage score sampling. We then develop a new rescaled variant of volume sampling that produces an unbiased estimate which avoids this bad behavior and has at least as good a tail bound as leverage score sampling: sample size k=O(d log d + d/epsilon) suffices to guarantee total loss at most 1+epsilon times the minimum with high probability. Thus, we improve on the best previously known sample size for an unbiased estimator, k=O(d^2/epsilon). Our rescaling procedure leads to a new efficient algorithm for volume sampling which is based on a "determinantal rejection sampling" technique with potentially broader applications to determinantal point processes. Other contributions include introducing the combinatorics needed for rescaled volume sampling and developing tail bounds for sums of dependent random matrices which arise in the process.