Zhou and Lin's AIHT algorithm achieves logarithmic regret for online quantile regression

Online high-dimensional regression faces two key challenges: data arrives sequentially and the model must remain sparse for interpretability and efficiency. Standard methods like iterative hard thresholding (IHT) apply a fixed projection frequency, which can prematurely discard weak but important features early on. In a new paper, Zitian Zhou and Nan Lin introduce Adaptive Iterative Hard Thresholding (AIHT), which dynamically adjusts the thresholding schedule. Early in training, AIHT delays hard-thresholding to let weak coordinates accumulate signal. Later, it increases projection frequency to stabilize the sparse estimator and exploit local curvature. The method is designed for quantile regression, where the loss is nonsmooth and data may be heavy-tailed—a challenging setting for online learning.

The authors prove that under restricted curvature and gradient-leakage conditions, AIHT stays within an inflated sparse cone and exhibits a two-phase convergence behavior, achieving logarithmic regret for a sliding-window objective. Simulations on synthetic data for online quantile regression confirm the advantage over standard online sparse-learning baselines, and ablation studies highlight the importance of adaptive scheduling. This work provides a theoretically grounded and practical algorithm for real-world applications like financial risk modeling or sensor network monitoring, where streaming data with outliers is common and model sparsity is critical.