Introduction
This paper introduces the first "input-sparsity time" algorithms for linear regression using a broad class of loss functions known as symmetric norms (which include Orlicz, top-$k$, and max-mix norms). By leveraging novel row-sampling techniques and a new sketching tool called SymSketch, the authors achieve a $(1+\epsilon)$-approximation for Orlicz norms, shattering the previous best approximation ratio of $d \cdot \text{polylog } n$.
The Challenge of Robust Loss Functions
In machine learning, linear regression is typically solved by minimizing the $\ell_2$ norm (least squares) or $\ell_1$ norm (least absolute deviations). However, real-world data often requires more robust or flexible loss functions, such as M-estimators (like the Huber loss) or Orlicz norms.
The primary challenge is that as datasets grow to massive scales ($n \gg d$), standard optimization becomes computationally prohibitive. Researchers frequently use "linear sketching"—multiplying the data by a small random matrix to compress it—to accelerate the process. While sketching is well-understood for standard $\ell_p$ norms, it has been notoriously difficult to apply to more complex "symmetric norms" (norms that remain invariant under sign-flips and coordinate permutations). Previous attempts either suffered from very poor approximation guarantees or were too slow to be practical for sparse data.
Proposed Methods
The authors propose two distinct approaches tailored to the type of norm being optimized:
1. Weighted Row Sampling for Orlicz Norms
Instead of using random projections, which can significantly distort Orlicz norms, the authors developed a weighted row-sampling algorithm.
- Orlicz Leverage Scores: They generalize the concept of "leverage scores" from $\ell_2$ regression to Orlicz norms. By defining a "well-conditioned basis" for the Orlicz norm, they can calculate precise sampling probabilities.
- Importance Sampling: By sampling rows of the data matrix based on these scores, they create a much smaller, weighted version of the problem. This compressed problem can be solved quickly while maintaining high accuracy.
2. SymSketch for General Symmetric Norms
For the broader class of symmetric norms, the authors introduce SymSketch, an "oblivious" subspace embedding.
- Hierarchical Sampling: SymSketch conceptually partitions the entries of a vector into groups based on their magnitude. It uses a hierarchy of sampling matrices to ensure that both "heavy" entries and the "long tail" of smaller entries are preserved in the sketch.
- Dimensionality Reduction: This technique allows them to embed a high-dimensional symmetric norm problem into a much smaller $\ell_2$ space, which can then be solved using standard numerical linear algebra.
Key Insights
- Convexity as a Bridge: For Orlicz norms, the authors realized that if they could approximate the sum $\sum G(|y_i|/\alpha)$, they could approximate the norm itself due to its unique definition. This insight allowed them to adapt tools from M-estimation.
- Input-Sparsity Time: The algorithms are designed to run in $O(\text{nnz}(A))$ time—meaning the computational bottleneck is simply reading the non-zero entries of the matrix once. This represents the gold standard for efficiency in large-scale linear algebra.
- Universal Sketching: This work represents a major step toward "universal sketching"—the goal of finding a single sketching matrix that works simultaneously for a wide variety of different loss functions.
Key Results
The theoretical guarantees provided by this paper mark a significant leap forward in the field of randomized numerical linear algebra.
- Orlicz Norms (Theorem 1): The method achieves a $(1+\epsilon)$-approximation in $\tilde{O}(\text{nnz}(A) + \text{poly}(d/\epsilon))$ time. This is a massive improvement over the previous state-of-the-art, which was stuck at an approximation ratio of $d \cdot \text{polylog } n$.
- General Symmetric Norms (Theorem 2): The SymSketch approach achieves a $\sqrt{d} \cdot \text{polylog } n \cdot \text{mmc}(\ell)$ approximation. Here, $\text{mmc}(\ell)$ is a measure of how "concentrated" the norm is. For many common norms (like top-$k$ or box-norms), this factor is merely a polylogarithmic term.
- First of its Kind: This is the first algorithm to provide provable guarantees for the general class of symmetric norm regression in input-sparsity time.
Limitations and Future Work
- Growth Constraints: The Orlicz norm algorithm assumes the function $G$ has at most quadratic growth (similar to $\ell_2$). The authors note their method currently fails for $p > 2$ because oblivious subspace embeddings with low distortion do not exist for those cases.
- The Gap to $(1+\epsilon)$: While they achieved $(1+\epsilon)$ for Orlicz norms, the general symmetric norm result still carries a $\sqrt{d}$ approximation factor. The authors pose it as an open question whether a $(1+\epsilon)$ ratio is possible for all symmetric norms.
Summary updated