Efficient Symmetric Norm Regression via Linear Sketching

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 \polylog n -approximate solution. When the loss function is a general symmetric norm, our algorithm produces a \sqrt{d} \cdot \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.