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 回归等损失函数，并且给出了相应的维度约束条件。