We provide efficient algorithms for overconstrained linear regression
problems with size $n \times d$ when the loss function is a symmetric norm (a
norm invariant under sign-flips and coordinate-permutations). An important
class of symmetric norms are Orlicz norms, where for a function $G$ and a
vector $y \in \mathbb{R}^n$, the corresponding Orlicz norm $\|y\|_G$ is defined
as the unique value $\alpha$ such that $\sum_{i=1}^n G(|y_i|/\alpha) = 1$. When
the loss function is an Orlicz norm, our algorithm produces a $(1 +
\varepsilon)$-approximate solution for an arbitrarily small constant
$\varepsilon > 0$ in input-sparsity time, improving over the previously
best-known algorithm which produces a $d \cdot \mathrm{polylog} n$-approximate
solution. When the loss function is a general symmetric norm, our algorithm
produces a $\sqrt{d} \cdot \mathrm{polylog} n \cdot
\mathrm{mmc}(\ell)$-approximate solution in input-sparsity time, where
$\mathrm{mmc}(\ell)$ is a quantity related to the symmetric norm under
consideration. To the best of our knowledge, this is the first input-sparsity
time algorithm with provable guarantees for the general class of symmetric norm
regression problem. Our results shed light on resolving the universal sketching
problem for linear regression, and the techniques might be of independent
interest to numerical linear algebra problems more broadly.

提供了高效的算法来解决超定的线性回归问题，其中损失函数是对称范数（在符号反转和坐标置换下不变的范数），当损失函数为 Orlicz 范数时，算法产生一个 (1+ε)- 近似解，在输入稀疏时间内改进了先前已知的算法。

线性草图的高效对称范数回归

Efficient Symmetric Norm Regression via Linear Sketching

Random sampling has become a critical tool in solving massive matrix
problems. For linear regression, a small, manageable set of data rows can be
randomly selected to approximate a tall, skinny data matrix, improving
processing time significantly. For theoretical performance guarantees, each row
must be sampled with probability proportional to its statistical leverage
score. Unfortunately, leverage scores are difficult to compute.
A simple alternative is to sample rows uniformly at random. While this often
works, uniform sampling will eliminate critical row information for many
natural instances. We take a fresh look at uniform sampling by examining what
information it does preserve. Specifically, we show that uniform sampling
yields a matrix that, in some sense, well approximates a large fraction of the
original. While this weak form of approximation is not enough for solving
linear regression directly, it is enough to compute a better approximation.
This observation leads to simple iterative row sampling algorithms for matrix
approximation that run in input-sparsity time and preserve row structure and
sparsity at all intermediate steps. In addition to an improved understanding of
uniform sampling, our main proof introduces a structural result of independent
interest: we show that every matrix can be made to have low coherence by
reweighting a small subset of its rows.

通过简单的迭代行抽样算法和加权少数行使每个矩阵的相干度低，我们能够使用随机抽取行的方式进行矩阵近似，以大大提高数据处理速度。