Efficient Symmetric Norm Regression via Linear Sketching

Zhao Song, Ruosong Wang, Lin F. Yang, Hongyang Zhang, Peilin Zhong

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.

Examples of robust loss functions like Huber and Fair.

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.

Comparison of approximation ratios showing the paper's improvements.
  • 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

Abstract

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. 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.
BibTeX
@inproceedings{song2019efficient,
  author = {Zhao Song and Ruosong Wang and Lin F. Yang and Hongyang Zhang and Peilin Zhong},
  title = {{Efficient Symmetric Norm Regression via Linear Sketching}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=YEYMD03vvHS},
}
Figure