We study oblivious sketching for $k$-sparse linear regression under various
loss functions such as an $\ell_p$ norm, or from a broad class of hinge-like
loss functions, which includes the logistic and ReLU losses. We show that for
sparse $\ell_2$ norm regression, there is a distribution over oblivious
sketches with $\Theta(k\log(d/k)/\varepsilon^2)$ rows, which is tight up to a
constant factor. This extends to $\ell_p$ loss with an additional additive
$O(k\log(k/\varepsilon)/\varepsilon^2)$ term in the upper bound. This
establishes a surprising separation from the related sparse recovery problem,
which is an important special case of sparse regression. For this problem,
under the $\ell_2$ norm, we observe an upper bound of $O(k \log (d)/\varepsilon
+ k\log(k/\varepsilon)/\varepsilon^2)$ rows, showing that sparse recovery is
strictly easier to sketch than sparse regression. For sparse regression under
hinge-like loss functions including sparse logistic and sparse ReLU regression,
we give the first known sketching bounds that achieve $o(d)$ rows showing that
$O(\mu^2 k\log(\mu n d/\varepsilon)/\varepsilon^2)$ rows suffice, where $\mu$
is a natural complexity parameter needed to obtain relative error bounds for
these loss functions. We again show that this dimension is tight, up to lower
order terms and the dependence on $\mu$. Finally, we show that similar
sketching bounds can be achieved for LASSO regression, a popular convex
relaxation of sparse regression, where one aims to minimize
$\|Ax-b\|_2^2+\lambda\|x\|_1$ over $x\in\mathbb{R}^d$. We show that sketching
dimension $O(\log(d)/(\lambda \varepsilon)^2)$ suffices and that the dependence
on $d$ and $\lambda$ is tight.

该论文探讨了在不同的损失函数下，对于 $k$- 稀疏线性回归的随机抽样方法以及其误差上界，其中包括了稀疏的逻辑回归和 ReLU 回归等损失函数，并且给出了相应的维度约束条件。

稀疏线性回归的最优草图界限

Optimal Sketching Bounds for Sparse Linear Regression

Kernel methods are fundamental in machine learning, and faster algorithms for
kernel approximation provide direct speedups for many core tasks in machine
learning. The polynomial kernel is especially important as other kernels can
often be approximated by the polynomial kernel via a Taylor series expansion.
Recent techniques in oblivious sketching reduce the dependence in the running
time on the degree $q$ of the polynomial kernel from exponential to polynomial,
which is useful for the Gaussian kernel, for which $q$ can be chosen to be
polylogarithmic. However, for more slowly growing kernels, such as the neural
tangent and arc-cosine kernels, $q$ needs to be polynomial, and previous work
incurs a polynomial factor slowdown in the running time. We give a new
oblivious sketch which greatly improves upon this running time, by removing the
dependence on $q$ in the leading order term. Combined with a novel sampling
scheme, we give the fastest algorithms for approximating a large family of
slow-growing kernels.

本文介绍一种新的快速算法来解决机器学习中的核方法，特别是针对多项式核、沿用 Taylor 级数展开的高斯核等问题。这个算法基于一种新的采样方法和改进的 skecthing 算法，提出了更快速算法解决机器学习中的各个核问题。

多项式度数的多项式核的快速轮廓绘制

Fast Sketching of Polynomial Kernels of Polynomial Degree

Kernel methods are fundamental tools in machine learning that allow detection
of non-linear dependencies between data without explicitly constructing feature
vectors in high dimensional spaces. A major disadvantage of kernel methods is
their poor scalability: primitives such as kernel PCA or kernel ridge
regression generally take prohibitively large quadratic space and (at least)
quadratic time, as kernel matrices are usually dense. Some methods for speeding
up kernel linear algebra are known, but they all invariably take time
exponential in either the dimension of the input point set (e.g., fast
multipole methods suffer from the curse of dimensionality) or in the degree of
the kernel function.
Oblivious sketching has emerged as a powerful approach to speeding up
numerical linear algebra over the past decade, but our understanding of
oblivious sketching solutions for kernel matrices has remained quite limited,
suffering from the aforementioned exponential dependence on input parameters.
Our main contribution is a general method for applying sketching solutions
developed in numerical linear algebra over the past decade to a tensoring of
data points without forming the tensoring explicitly. This leads to the first
oblivious sketch for the polynomial kernel with a target dimension that is only
polynomially dependent on the degree of the kernel function, as well as the
first oblivious sketch for the Gaussian kernel on bounded datasets that does
not suffer from an exponential dependence on the dimensionality of input data
points.

提出了一种通用方法，可将数值线性代数中的随意草图解决方案应用于数据点的张量，从而根据多项式内核函数的大小开发了第一个仅在目标维度上具有多项式依赖性的多项式内核的忽略草图，并且无需因输入数据维数而遭受指数依赖。