论文标题
绘制算法和山脊回归的下限
Sketching Algorithms and Lower Bounds for Ridge Regression
论文作者
论文摘要
我们提供了一种基于素描的迭代算法，该算法计算$ 1 +\ varepsilon $近似解决方案，用于Ridge回归问题$ \ min_x \ | ax-b \ | ax-b \ | _2^2^2 +λ\ | x \ | x \ | x \ | _2^2 $ were $ a \ in $ a \ in r^in r^{n \ times d pan {对于持续数量的迭代次数（需要在输入上持续数量的传球），我们的算法可以改善早期工作（Chowdhury等人），要求仅素描矩阵仅具有较弱的近似矩阵乘法（AMM），这取决于$ \ varepsilon $以及恒定的子架子的保证，以及恒定的subspace subspace subspace endspace endspace subsedspace。相反，较早的工作要求素描矩阵具有取决于$ \ varepsilon $的子空间嵌入保证。例如，要在$ 1 $迭代中生产$ 1+\ varepsilon $近似解决方案，需要$ 2 $通过输入，我们的算法要求OSNAP嵌入具有$ m = o（nσ^2/λ\ varepsilon）$ lode $ s = o（nσ al。使用相同数量的OSNAP行需要一个稀疏$ s = o（\ sqrt {σ^2/λ\ varepsilon} \ cdot \ log（n））$，其中$σ= \ opnorm {a} $是矩阵$ a $ a $的光谱。我们还表明，该算法可用于为内核脊回归提供更快的算法。最后，我们表明，我们的算法所需的草图大小对于山脊回归算法的自然框架实质上是最佳的，这是通过证明AMM遗忘的素描矩阵上的下限。 AMM的草图大小的下限可能具有独立的兴趣。
We give a sketching-based iterative algorithm that computes a $1+\varepsilon$ approximate solution for the ridge regression problem $\min_x \|Ax-b\|_2^2 +λ\|x\|_2^2$ where $A \in R^{n \times d}$ with $d \ge n$. Our algorithm, for a constant number of iterations (requiring a constant number of passes over the input), improves upon earlier work (Chowdhury et al.) by requiring that the sketching matrix only has a weaker Approximate Matrix Multiplication (AMM) guarantee that depends on $\varepsilon$, along with a constant subspace embedding guarantee. The earlier work instead requires that the sketching matrix has a subspace embedding guarantee that depends on $\varepsilon$. For example, to produce a $1+\varepsilon$ approximate solution in $1$ iteration, which requires $2$ passes over the input, our algorithm requires the OSNAP embedding to have $m= O(nσ^2/λ\varepsilon)$ rows with a sparsity parameter $s = O(\log(n))$, whereas the earlier algorithm of Chowdhury et al. with the same number of rows of OSNAP requires a sparsity $s = O(\sqrt{σ^2/λ\varepsilon} \cdot \log(n))$, where $σ= \opnorm{A}$ is the spectral norm of the matrix $A$. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression. Finally, we show that the sketch size required for our algorithm is essentially optimal for a natural framework of algorithms for ridge regression by proving lower bounds on oblivious sketching matrices for AMM. The sketch size lower bounds for AMM may be of independent interest.
