Introduction
In the era of massive datasets, scenarios where the number of data points ($n$) vastly exceeds the number of features ($d$) are increasingly common. Standard optimization algorithms become prohibitively slow or impossible to execute when data cannot fit into memory. To address this, researchers employ oblivious sketching: multiplying the data matrix by a random, data-independent matrix $S$ to create a significantly smaller "sketch," and subsequently solving the optimization problem in this reduced space. Because the sketch is generated without examining the data, it is highly effective for streaming environments (where data arrives sequentially) and distributed systems.
While oblivious sketching for $\ell_2$ regression (standard least squares) is well-established, extending these techniques to $\ell_1$ regression (which is robust to outliers) and logistic regression (the cornerstone of classification) has proven difficult. Previous oblivious sketches for these problems either required impractically large sketch sizes (e.g., $d^5$) or yielded poor approximation factors. This paper introduces a novel sketching algorithm that reduces data size to a near-linear sketch while maintaining a constant-factor approximation, dramatically outperforming prior state-of-the-art methods in both theoretical complexity and practical performance.
Methodology: The "Sketch & Solve" Paradigm
The authors adopt the "Sketch & Solve" framework, which consists of computing $SX$ (where $S$ is a random oblivious linear map) and finding the optimal parameters $\beta$ using the sketched data. The paper introduces several key innovations to optimize this process:
- Multi-level Subsampling: The sketch utilizes $O(\log n)$ levels, with each level subsampling the data at an exponentially decreasing rate.
- Densified Base Level: In prior work, the base level (level 0) mapped each data point to a single bucket using a CountMin-style sketch. This paper densifies this level by mapping each point to multiple buckets ($s > 1$). This redundancy resolves collisions for "heavy hitters"—influential data points that disproportionately impact the model.
- Refined Analysis: Rather than bounding the expected contributions of weight classes, the authors employ a "reverse perspective" to analyze which weight classes are adequately represented at each level. This analytical shift tightens the approximation factor from $\ge 8$ down to a 2-approximation.
Key Theoretical Insights
The theoretical contributions of this work bridge the gap between $\ell_1$ and logistic regression sketching. By incorporating a data-dependent parameter $\mu$—which measures the complexity of compressing the data—the authors successfully adapt $\ell_1$ techniques for logistic regression.
Crucially, the asymmetric nature of logistic loss means that, unlike standard $\ell_p$ norms, signs cannot simply be flipped. The authors' reliance on CountMin-style sketches (which sum elements) rather than Count-sketches (which use random signs) is vital for preserving coordinate signs, an essential property for logistic regression.
These insights lead to a significant theoretical leap: for logistic regression, the sketching dimension is improved from roughly $\tilde{O}(\mu^7 d^5)$ to $\tilde{O}(\mu d^{1+c})$ for any constant $c > 0$. For $\ell_1$ regression, the dimension is reduced to $\tilde{O}(d^{1+c})$. Both achieve an $O(1)$-approximation, moving from high-degree polynomial dependencies to nearly linear ones.
Empirical Evaluation
The authors evaluated their method on three real-world benchmarks (Covertype, Webspam, and Kddcup) and a challenging synthetic dataset ($n=40,000, d=100$) engineered with multiple heavy hitters to stress-test previous sketching methods.
- Robustness to Heavy Hitters: On the synthetic dataset, the new sketch achieved approximation ratios near 2. In contrast, previous state-of-the-art methods struggled, yielding ratios between 7 and 8.
- Superiority over Cauchy Sketches: For $\ell_1$ regression, the proposed method outperformed classic Cauchy-based sketches in both accuracy and computational efficiency.
Limitations and Future Directions
While the proposed sketching algorithm represents a major step forward, several limitations and open questions remain:
- Regularization Cost: Extending the sketch to handle variance-based regularized logistic regression introduces an additional $\sqrt{n}$ factor to the sketch size. The authors prove that for their specific CountMin-style approach, this $\Theta(\sqrt{n})$ dependence is unavoidable.
- Sparsity Trade-offs: Achieving a $(1+\epsilon)$-approximation requires an exponential dependence on $1/\epsilon$, a common bottleneck in the $\ell_1$ embedding literature.
- Optimal Bounds: A primary open question is whether the upper bound can be further reduced to exactly $O(\mu d)$, or if the current lower bound of $\Omega(\mu + d)$ can be raised to close the theoretical gap.
Summary updated