Sketching for M-Estimators: A Unified Approach to Robust Regression
Sketching for M-Estimators: A Unified Approach to Robust Regression
复制标题
M 估计量的草图：鲁棒回归的统一方法
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
David P. Woodruff
中科院分区：
文献类型：
--
作者：
K. Clarkson;David P. Woodruff
我们给出了m估计量minx || ax-b || g的算法，其中a∈Rnxd和b∈Rn，y∈Rn的|| y || g由成本函数g：r→r≥指定0，使用|| y ||g程σig（yi）。在o（nnz（a）log n + poly（d（log n）/e））时间，其中nnz（a）表示矩阵A的非零条目的数量可以说是使用最广泛的M估计器，享受L1的鲁棒性能以及L2的平滑度M-Sketch是Verbin和Zhang在估计地球距离的情况下引入的草图的变体。估算值G的生长至少是线性的，最多可以使用M-sketch。 ，单个通过矩阵并找到一个解决方案，其剩余误差在最佳且概率高的恒定因素内。
We give algorithms for the M-estimators minx||Ax − b||G, where A ∈ RnXd and b ∈ Rn, and ||y||G for y ∈ Rn is specified by a cost function G: R → R≥0, with ||y||G ≡ ΣiG(yi). The M-estimators generalize lp regression, for which G(x) = |x|p. We first show that the Huber measure can be computed up to relative error e in O(nnz(A) log n + poly(d(log n)/e)) time, where nnz(A) denotes the number of non-zero entries of the matrix A. Huber is arguably the most widely used M-estimator, enjoying the robustness properties of l1 as well as the smoothness properties of l2.We next develop algorithms for general M-estimators. We analyze the M-sketch, which is a variation of a sketch introduced by Verbin and Zhang in the context of estimating the earthmover distance. We show that the M-sketch can be used much more generally for sketching any M- estimator provided G has growth that is at least linear and at most quadratic. Using the M-sketch we solve the M-estimation problem in O(nnz(A) + poly(d log n)) time for any such G that is convex, making a single pass over the matrix and finding a solution whose residual error is within a constant factor of optimal, with high probability.