Introduction
In modern machine learning, overconstrained linear regression problems—where the number of observations $n$ far exceeds the number of features $d$—are ubiquitous. The goal is to find a parameter vector $x$ that minimizes the error $L(Ax - b)$ for a given loss function $L$. While efficient "sketching" techniques exist for standard $\ell_1$ and $\ell_2$ losses, many practical applications require more robust or complex loss functions.
This paper addresses this gap by introducing the first "input-sparsity time" algorithms for linear regression using symmetric norms. These norms are invariant under sign changes and permutations of the error vector's coordinates. This broad class encompasses Orlicz norms (scale-invariant $M$-estimators), top-$k$ norms, and max-mix norms.
Problem Formulation and Loss Functions
The authors specifically target symmetric norms and their subset, Orlicz norms. Orlicz norms are particularly relevant as they provide a unified framework for various $M$-estimators used in robust statistics. For instance, the Huber loss, which behaves like $\ell_2$ for small errors and $\ell_1$ for large ones, can be viewed through this lens.
Prior to this work, algorithms for Orlicz norms were either computationally expensive or yielded poor approximation ratios, often off by factors as large as $d \cdot \text{polylog } n$.
Methodology: Linear Sketching Strategies
The researchers propose two primary linear sketching strategies to reduce the dimensionality of the problem while preserving the underlying geometry of the loss function.
1. Row Sampling for Orlicz Norms
For Orlicz norms, the authors developed a novel importance sampling technique based on generalized leverage scores. By constructing a "well-conditioned basis" for the data matrix $A$, they define scores that identify the most informative rows. Sampling $O(d \cdot \text{poly}(\epsilon^{-1}))$ rows according to these scores allows the massive $n \times d$ problem to be reduced to a much smaller one that maintains a $(1+\epsilon)$-approximation of the original Orlicz norm error.
2. SymSketch for General Symmetric Norms
To handle the broader class of symmetric norms, the authors introduced SymSketch, an "oblivious" subspace embedding. Unlike row sampling, SymSketch does not require pre-processing the data matrix. It utilizes a hierarchical structure of diagonal matrices and weights to embed the complex symmetric norm into a standard $\ell_2$ space. This transformation allows the use of highly optimized least-squares solvers on the sketched data.
Key Theoretical and Empirical Results
The theoretical contributions of this paper represent a significant leap over previous state-of-the-art methods. The following table summarizes the improvements in approximation ratios.
As shown in the table, Theorem 1 achieves a $(1+\epsilon)$-approximation for Orlicz norms in input-sparsity time $O(\text{nnz}(A) + \text{poly}(d/\epsilon))$, a major improvement over the previous $d \cdot \text{polylog } n$ ratio. For general symmetric norms, Theorem 2 provides the first provable guarantees in input-sparsity time, with an approximation factor of $\sqrt{d} \cdot \text{polylog } n \cdot \text{mmc}(\ell)$.
Empirically, the algorithms were validated on large-scale datasets, including the U.S. 2000 Census and the UCI YearPredictionMSD dataset. The results demonstrated that SymSketch consistently outperforms uniform sampling and previous embedding techniques, achieving high accuracy (e.g., a 1.25 approximation ratio) with very small sketch sizes (as low as $5d$).
Conclusion and Future Directions
This work provides a powerful framework for efficient regression under a wide variety of loss functions. By leveraging the properties of symmetric norms and developing new sketching techniques, the authors have bridged the gap between theoretical complexity and practical efficiency.
However, challenges remain. The $\sqrt{d}$ approximation factor for general symmetric norms suggests there may be room for further optimization—specifically, whether a $(1+\epsilon)$-approximation is achievable for all symmetric norms. Additionally, extending these techniques to non-symmetric norms remains an open and important problem in the field of universal sketching.
Summary updated