Technical Summary: Adaptive Iterative Hard Thresholding for Online High-dimensional Quantile Regression

1. Problem Statement

The paper addresses the challenge of online high-dimensional sparse regression in streaming environments where data $(Y_t, X_t)$ arrive sequentially. The primary goal is to iteratively estimate a sparse true coefficient vector $\beta^* \in \mathbb{R}^p$ (where the sparsity level $s_0 \ll p$) by minimizing a sequence of loss functions.

The specific focus is on online quantile regression, which utilizes the check loss $\rho_\tau(u) = u(\tau - \mathbb{1}\{u < 0\})$. This setting presents unique difficulties compared to standard online convex optimization:

• Non-smoothness: The quantile loss is non-differentiable, requiring subgradient methods.
• Robustness Requirements: The method must handle heavy-tailed noise, heteroscedasticity, and potential distributional shifts, where standard squared-error losses fail.
• High-Dimensionality: When $p$ exceeds the effective sample size, the empirical Hessian is singular, precluding global strong convexity. Sparsity assumptions are necessary, but enforcing them online introduces algorithmic complexities.

A naive application of Iterative Hard Thresholding (IHT)—applying a hard thresholding operator $H_s$ after every stochastic gradient update—fails in this regime. It creates a "one-step entry barrier" where true variables with initially weak signals are discarded before they can accumulate sufficient gradient mass to re-enter the active set. Conversely, periodic thresholding with fixed intervals fails to adapt to decaying step sizes, eventually providing insufficient movement for support discovery or allowing off-support noise to accumulate uncontrollably.

2. Methodology: Adaptive Iterative Hard Thresholding (AIHT)

The authors propose Adaptive Iterative Hard Thresholding (AIHT), a framework that decouples stochastic gradient evolution from sparse projection. The core innovation is an adaptive schedule that separates the learning process into two distinct phases based on the stability of the iterates.

2.1 Core Mechanism

AIHT operates in epochs. Within an epoch $j$:

1. Candidate-Rstricted Updates: Instead of updating all $p$ coordinates, the algorithm restricts updates to a candidate set $A_j = \hat{S}_j \cup C_j$, where $\hat{S}_j$ is the current support and $C_j$ contains the $m$ largest subgradient components outside the support. This limits "gradient leakage" from off-support coordinates.
2. Delayed Thresholding: Hard thresholding $H_s$ is applied only at the end of the epoch, not after every step. This allows coordinates to accumulate signal over the cumulative step-size mass of the epoch ($B_j = \sum_{t \in T_j} \eta_t$) before being judged.

2.2 Two-Phase Adaptive Schedule

The algorithm dynamically transitions between two phases:

• Phase I (Support Discovery): Uses larger step sizes and less frequent thresholding (longer epochs). This allows weak but informative coordinates to grow and enter the active set.
• Phase II (Local Refinement): Triggered when a stability diagnostic (based on the ratio of projected gradient mapping statistics) indicates the support has stabilized. The algorithm switches to smaller step sizes ($O(1/t)$) and increases the frequency of thresholding (shorter epochs) to exploit local curvature and refine the estimator.

2.3 Handling Distributional Shifts

For non-stationary environments, the authors introduce a restart-enabled version of AIHT. It employs an adjacent-window score contrast detector to identify changepoints. Upon detection, the algorithm performs a "hard restart": resetting the iterate to zero, flushing the buffer, and returning to Phase I to rediscover the new support structure.

3. Theoretical Contributions

The paper establishes rigorous guarantees for AIHT under restricted curvature and gradient-leakage conditions:

• Cone Invariance: The authors prove that under candidate-restricted updates and bounded epoch mass, the iterates remain within an "inflated sparse cone" $\Gamma_\zeta(c, S)$. This ensures that off-support leakage is controlled and does not scale with the ambient dimension $p$, but rather with the sparsity and candidate size.
• Two-Phase Convergence:
  • Phase I: Errors contract geometrically with respect to the epoch mass, up to a stochastic tolerance.
  • Phase II: Once in the refinement regime, the algorithm achieves an error rate of $O((\log t)/t)$.
• Regret Bounds:
  • For the sliding-window objective, the total regret is bounded by $C_I(T_0) + C_{burn} + O(\log T)$.
  • If the transition time $T_0$ and burn-in costs are bounded independently of $T$, the regret is logarithmic ($O(\log T)$), matching the performance of strongly convex online optimization despite the non-smooth, high-dimensional setting.
• Dynamic Regret: In piecewise-stationary settings, the algorithm achieves segment-wise recovery with a dynamic regret bound that scales logarithmically with the segment length and linearly with the number of changepoints.

4. Empirical Results

Simulations validate the theoretical claims and the necessity of the adaptive schedule:

• Robustness: AIHT significantly outperforms dense Online SGD and Truncated Gradient (TG) baselines in terms of steady-state estimation error, particularly under heavy-tailed noise and Huber contamination.
• Schedule Ablation: Comparisons with "every-step" and "fixed-period" thresholding variants demonstrate that:
  • Every-step thresholding suppresses support discovery, leading to high error.
  • Fixed-period thresholding fails to adapt to decaying step sizes, causing suboptimal convergence.
  • AIHT's adaptive timing yields the lowest final error and cumulative excess loss.
• Changepoint Detection: In non-stationary experiments, the restart-enabled AIHT successfully detects changepoints and recovers the new support, whereas non-restarting baselines accumulate persistent error.

5. Significance and Claims

The paper claims that AIHT provides a theoretically grounded solution to the specific difficulties of online high-dimensional quantile regression. Its significance lies in:

1. Decoupling Discovery and Refinement: By separating support discovery (Phase I) from local refinement (Phase II), the method overcomes the "entry barrier" problem inherent in naive hard thresholding.
2. Adaptive Scheduling: It demonstrates that the "epoch mass" (cumulative step size) is a more critical scheduling variable than the raw number of iterations between projections, especially when step sizes decay.
3. Robustness in High Dimensions: It extends the applicability of hard thresholding to non-smooth, heavy-tailed settings where standard convex regularization (like Lasso) or soft-thresholding methods may be less effective or theoretically harder to analyze in the online regime.
4. Rigorous Characterization: The work provides a formal characterization of the two-phase convergence phenomenon and establishes logarithmic regret guarantees for a non-smooth, high-dimensional online learning problem.

The authors note that while the analysis focuses on quantile regression, the algorithmic framework is not tied to the check loss and could potentially extend to other losses (e.g., squared, Huber) under similar restricted curvature assumptions.