Oblivious sketching for logistic regression

Alexander Munteanu, Simon Omlor, David P. Woodruff

Abstract

Logistic regression is a fundamental tool in machine learning, yet scaling it to massive, dynamic datasets remains a significant challenge. Traditional coreset methods often require multiple passes over the data and cannot handle "turnstile" streams where entries are updated or deleted. This paper introduces the LogReg-sketch, the first data-oblivious sketch for logistic regression. By utilizing a linear transformation chosen independently of the data, the method enables single-pass compression that is robust to deletions and updates. We demonstrate that this sketch provides provable accuracy guarantees, reduces dataset size to a fraction of the original, and performs competitively with state-of-the-art multi-pass techniques.

Introduction

Logistic regression is a workhorse of modern statistical analysis, but fitting models to truly massive data—such as the terabytes per second generated by the Large Hadron Collider or sprawling, unstructured web databases—presents a significant computational bottleneck. The standard approach to handling such scale involves the use of coresets, which are small, representative subsets of data that approximate the loss function of the full dataset.

However, existing coreset methods suffer from three major limitations. First, they typically require at least two passes over the data to calculate "importance" scores for sampling. Second, they are often rigid, requiring data to arrive in a specific order or only working for regularized versions of the problem. Finally, they cannot easily handle "turnstile" streams, where data entries may be updated or deleted after they have been processed. This paper addresses these gaps by proposing the first "data-oblivious" sketch for logistic regression.

The LogReg-sketch Approach

The authors propose the LogReg-sketch, a method that compresses a massive data matrix $A$ into a much smaller matrix $B = SA$ using a random sketching matrix $S$. Because $S$ is chosen before the data is even seen, the process is "oblivious," allowing for a single-pass implementation that is inherently compatible with data deletions and updates.

Technical Innovations

To overcome the challenges of sketching for logistic regression, the authors introduced several key innovations:

  • Multi-level Hashing: The sketch employs a combination of subsampling at various levels and hashing coordinates into buckets, similar to a CountMin-sketch. This architecture ensures that "heavy hitters"—data points that contribute significantly to the overall loss—are preserved and not obscured by the noise of the remaining data.
  • Handling Asymmetry: Logistic loss is notoriously difficult to sketch because it is asymmetric; misclassifying a point in one direction incurs a different cost than in the other. Standard sketching techniques (like Count-Sketches) use random signs that can break these approximation guarantees. The authors solved this by splitting the loss into a positive part, handled by the multi-level sketch, and a negative part, handled by a small uniform sample.
  • Complexity Parameter ($\mu$): The authors utilize a parameter $\mu$ that captures the inherent "compressibility" of a specific dataset for logistic regression. This allows the sketch size to scale dynamically based on the difficulty of the data rather than just the number of observations.

Experimental Evaluation

The researchers evaluated the LogReg-sketch across several large-scale datasets, including Covertype (forest cover prediction), Webspam (spam detection), and Kddcup (network intrusion). They also utilized a Synthetic dataset specifically designed to be difficult for uniform sampling.

Key Results

  • Significant Size Reduction: The sketch successfully reduces a dataset of $n$ points to a size proportional to $\text{poly}(\mu d \log n)$. For massive $n$, this represents a dramatic reduction in storage and computational requirements.
  • High Efficiency: The sketch can be computed in "input sparsity time," meaning the algorithm only needs to examine the non-zero entries of the data matrix once.
  • Competitive Performance: In head-to-head experiments, the LogReg-sketch performed competitively with non-oblivious methods like leverage score sampling (L2S), despite L2S requiring two passes over the data. On the "hard" synthetic dataset, the LogReg-sketch succeeded where both uniform sampling and Stochastic Gradient Descent (SGD) failed to converge to an accurate solution.
  • Robustness to Noise: When subjected to 1% Gaussian noise to simulate adversarial corruptions, the LogReg-sketch remained stable, whereas the accuracy of uniform sampling methods plummeted.

The "Sketch-and-Solve" Paradigm

One of the most practical aspects of this research is the "sketch-and-solve" workflow. A practitioner can take the compressed sketch and plug it into any off-the-shelf logistic regression solver to obtain an $O(\log n)$ approximation. For those requiring higher precision, the authors demonstrate that a constant $O(1)$ approximation is achievable by slightly modifying the solver to "clip" very small contributions.

Limitations and Future Work

While the LogReg-sketch is a significant advancement, it is not without limitations. The size of the sketch is dependent on the complexity parameter $\mu$; if a dataset is inherently difficult to compress for logistic regression, the resulting sketch may still be relatively large. Additionally, while the $O(\log n)$ approximation is easy to implement, the $O(1)$ approximation requires a specialized solver that may present a barrier to entry for some users.

Future research may extend these oblivious sketching techniques to other Generalized Linear Models (GLMs), potentially providing a unified framework for streaming analysis across a wider variety of statistical problems.

Summary updated

Abstract

What guarantees are possible for solving logistic regression in one pass over a data stream? To answer this question, we present the first data oblivious sketch for logistic regression. Our sketch can be computed in input sparsity time over a turnstile data stream and reduces the size of a $d$-dimensional data set from $n$ to only $\operatorname{poly}(\mu d\log n)$ weighted points, where $\mu$ is a useful parameter which captures the complexity of compressing the data. Solving (weighted) logistic regression on the sketch gives an $O(\log n)$-approximation to the original problem on the full data set. We also show how to obtain an $O(1)$-approximation with slight modifications. Our sketches are fast, simple, easy to implement, and our experiments demonstrate their practicality.
BibTeX
@inproceedings{munteanu2021oblivious,
  author = {Alexander Munteanu and Simon Omlor and David P. Woodruff},
  title = {{Oblivious sketching for logistic regression}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=xy_pUEm0_SH},
}
Figure