High-dimensional online learning via asynchronous decomposition: Non-divergent results, dynamic regularization, and beyond

A team of researchers has introduced a novel framework to tackle a persistent challenge in high-dimensional online learning: divergent error bounds. In their paper "High-dimensional online learning via asynchronous decomposition: Non-divergent results, dynamic regularization, and beyond," Shixiang Liu, Zhifan Li, Hanming Yang, and Jianxin Yin present a method that prevents the error bounds or required sample sizes from growing uncontrollably as more data batches are processed. This is achieved through an asynchronous decomposition approach that leverages summary statistics from previous batches to construct a surrogate score function for learning from the current batch.

The core of their solution is a dynamic-regularized iterative hard thresholding algorithm, designed to be both computationally and memory-efficient for sparse online optimization problems. The researchers provide a unified theoretical analysis that accounts for both streaming computational errors and statistical accuracy. They prove their estimator maintains non-divergent error bounds and preserves ℓ₀ sparsity—meaning it keeps the model sparse—across all incoming data batches. Crucially, the framework allows the model to adaptively improve as more data arrives, theoretically attaining 'oracle accuracy.' This means it performs as well as if the entire historical dataset were accessible from the start and the true underlying data structure (support) were known in advance. The paper illustrates these properties using the example of a generalized linear model.