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

Abstract

Linear regression is arguably the most prominent among statistical inference methods, popular both for its simplicity as well as its broad applicability. On par with data-intensive applications, the sheer size of linear regression problems creates an ever growing demand for quick and cost efficient solvers. Fortunately, a significant percentage of the data accrued can be omitted while maintaining a certain quality of statistical inference with an affordable computational budget. The present paper introduces means of identifying and omitting "less informative" observations in an online and data-adaptive fashion, built on principles of stochastic approximation and data censoring. First- and second-order stochastic approximation maximum likelihood-based algorithms for censored observations are developed for estimating the regression coefficients. Online algorithms are also put forth to reduce the overall complexity by adaptively performing censoring along with estimation. The novel algorithms entail simple closed-form updates, and have provable (non)asymptotic convergence guarantees. Furthermore, specific rules are investigated for tuning to desired censoring patterns and levels of dimensionality reduction. Simulated tests on real and synthetic datasets corroborate the efficacy of the proposed data-adaptive methods compared to data-agnostic random projection-based alternatives.

References in corpus (7)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Sketching as a Tool for Numerical Linear Algebra
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm
• A Statistical Perspective on Randomized Sketching for Ordinary Least-Squares
• Power Scheduling of Kalman Filtering in Wireless Sensor Networks with Data Packet Drops
• Fast Ridge Regression with Randomized Principal Component Analysis and Gradient Descent

Cited by in corpus (7)

• Data Sketching for Large-Scale Kalman Filtering
• Online Categorical Subspace Learning for Sketching Big Data with Misses
• Optimal Sampling Designs for Multi-dimensional Streaming Time Series with Application to Power Grid Sensor Data
• Low-Complexity Methods for Estimation After Parameter Selection
• Decentralized RLS with Data-Adaptive Censoring for Regressions over Large-Scale Networks
• Large-scale Kernel-based Feature Extraction via Budgeted Nonlinear Subspace Tracking
• Robust, Deep, and Reinforcement Learning for Management of Communication and Power Networks