Online Censoring for Large-Scale Regressions with Application to Streaming Big Data

Dimitris Berberidis, Vassilis Kekatos, Georgios B. GiannakisIEEE TSP 2016 · OpenReview

Abstract

Processing massive streaming datasets for linear regression is computationally expensive. This paper introduces "online censoring" techniques that intelligently skip less informative data points. By employing stochastic approximation and adaptive thresholding, the proposed methods significantly reduce computational, storage, and communication costs while maintaining high estimation accuracy, often outperforming traditional data-agnostic methods.

Introduction

In the era of "Big Data," the sheer volume of information from streaming sensors or massive datasets can overwhelm traditional statistical inference tasks. Linear regression, a fundamental tool for data analysis, becomes prohibitively expensive in terms of power, memory, and time when every data point must be processed.

Existing solutions often rely on data-agnostic methods like Random Projections (RP) or random sampling. However, these methods discard data points blindly, potentially losing rare but highly informative observations. This paper proposes data-adaptive solvers that identify and omit redundant observations on-the-fly based on their "innovation"—the degree to which a new point differs from the current model's prediction.

Methodology: Adaptive and Non-Adaptive Censoring

The authors propose two primary strategies:

  1. Non-Adaptive Censoring (NAC): Uses a fixed rule based on a preliminary estimate, ideal for distributed systems to prevent transmission of redundant data.
  2. Adaptive Censoring (AC): Continuously updates censoring criteria as the model learns, designed to slash computational complexity in centralized streaming environments.

To implement these, the paper develops the Stochastic Approximation Maximum Likelihood Estimator (SA-MLE). This estimator treats censored points as interval-constrained information rather than missing values, squeezing more accuracy out of the data.

Mean Square Error (MSE) performance of first-order and second-order SA-MLE algorithms compared to the Cramer-Rao Lower Bound (CRLB).

As shown in the figure above, second-order methods (Newton-like) converge significantly faster and stay closer to the theoretical Cramer-Rao Lower Bound (CRLB) than first-order (LMS-like) variants.

Key Results and Insights

The core insight is that processing data points close to the current model's prediction yields diminishing returns. By setting a threshold $\tau$, the system can ignore these points.

Data Reduction vs. Accuracy

In simulations, these algorithms censored up to 50-75% of the data with negligible loss in accuracy. Even at 95% reduction, the models remained reliable.

MSE performance across different censoring thresholds (τ), illustrating the trade-off between data reduction and estimation accuracy.

The figure illustrates how increasing the threshold $\tau$ (and thus the censoring rate) affects the Mean Square Error. While higher censoring leads to slightly higher MSE, the computational savings are substantial. The AC-RLS algorithm, for instance, reduces least-squares complexity from $O(Dp^2)$ to $O(dp^2)$, where $d \ll D$.

Comparison with Random Projections

Unlike Random Projections, which might discard high-leverage points, adaptive censoring naturally preserves the most informative data. AC-RLS consistently achieved lower MSE than RP-based solvers at equivalent data reduction levels.

Conclusion

Online censoring provides a robust framework for handling Big Data regression by focusing computational resources on the most informative observations. Future work includes extending these techniques to non-linear models and time-varying processes, as well as refining outlier sensitivity through robust variants.

Summary updated

BibTeX
@article{berberidis2016online,
  author = {Dimitris Berberidis and Vassilis Kekatos and Georgios B. Giannakis},
  title = {{Online Censoring for Large-Scale Regressions with Application to Streaming Big Data}},
  journal = {IEEE Trans. Signal Process.},
  year = {2016},
  url = {https://openreview.net/forum?id=l5sSr0--jPd},
}
Figure