PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantile Regression Under Memory Constraint

Xi Chen, Weidong Liu, Yichen Zhang

arXiv:1810.08264v1stat.MEecon.EMstat.ML

TL;DR

The paper addresses quantile-regression inference when datasets exceed available memory. It proposes a multi-round linear aggregation method that successively refines an initial estimator, achieving the full-data QR estimator’s asymptotic efficiency under polynomial growth of n in m. The approach also supports increasing dimensionality and applications to distributed sensor networks and streaming data.

  • Problem

    The paper asks how to perform quantile-regression inference when n samples cannot fit in memory and classical full-data methods are unavailable.

  • Method

    The method constructs an explicit linear QR estimator and successively refines it through multiple rounds of aggregated local statistics.

  • Results

    The final estimator achieves the same asymptotic efficiency as QR computed on all data when n = o(m^A) for some constant A.

  • Takeaways & Limitations

    The approach extends memory-constrained QR inference to distributed sensor networks and online streaming data while using O(p²) bits of sensor-to-sensor communication.

  • Takeaways & Limitations

    The paper identifies extension to ℓ1-penalized high-dimensional and censored quantile regression as future work.

Abstract

from arXiv · show

This paper studies the inference problem in quantile regression (QR) for a large sample size $n$ but under a limited memory constraint, where the memory can only store a small batch of data of size $m$. A natural method is the naïve divide-and-conquer approach, which splits data into batches of size $m$, computes the local QR estimator for each batch, and then aggregates the estimators via averaging. However, this method only works when $n=o(m^2)$ and is computationally expensive. This paper proposes a computationally efficient method, which only requires an initial QR estimator on a small batch of data and then successively refines the estimator via multiple rounds of aggregations. Theoretically, as long as $n$ grows polynomially in $m$, we establish the asymptotic normality for the obtained estimator and show that our estimator with only a few rounds of aggregations achieves the same efficiency as the QR estimator computed on all the data. Moreover, our result allows the case that the dimensionality $p$ goes to infinity. The proposed method can also be applied to address the QR problem under distributed computing environment (e.g., in a large-scale sensor network) or for real-time streaming data.

1. Introduction.

The paper studies quantile-regression inference when n samples exceed memory m, replacing biased and costly naïve divide-and-conquer averaging with a multi-round linear aggregation method. The resulting estimator remains efficient for polynomially growing n, supports increasing dimensionality, and extends to sensor networks and streaming data.

  • The paper asks how to estimate and conduct inference for β(τ) when memory stores only m samples while n ≫ m.
  • Naïve divide-and-conquer averages local QR estimators but can fail when n/m² diverges because local bias is O(1/m), and it requires solving n/m optimization problems.Averaging reduces variance but not bias, making computation expensive when the number of batches is large.
  • The proposed LEQR method uses smoothing to construct an explicit linear estimator, then aggregates local statistics by summation and linear-system solution across multiple rounds.The first-round estimator is repeatedly refined using the previous estimate as initialization.
  • As long as n = o(m^A) for some constant A, the multi-round estimator achieves the same asymptotic efficiency as QR computed on all data.The theory also establishes a Bahadur representation with a nearly optimal remainder under conditions on p, m, n, and the number of rounds.
  • The method requires O(p²) bits of communication between sensors and applies to distributed sensor networks and online streaming data.For streaming data, it provides successively refined estimators and an asymptotic normality result; it can also serve as an efficient QR optimization solver.

2. Related works.

Prior iterative methods relax naïve divide-and-conquer sample-size restrictions but rely on twice-differentiable losses, whereas this paper uses smoothing to build a linear QR estimator for its inference method.

  • Iterative aggregation methods relax the condition n = o(m^2) but are based on approximate Newton algorithms requiring twice-differentiability of the loss.
  • The paper's LEQR building block adopts QR smoothing to overcome difficulties in higher-order score expansions for the non-smooth objective.
  • The proposed methodology begins with a new linear type estimator for quantile regression as the basis for inference under memory constraints.

3. Methodology.

The method smooths the non-differentiable QR loss, replaces an unavailable fixed-point solution with a consistent initial estimator, and aggregates linear statistics through iterative bandwidth refinement.

  • 3.1. A linear type estimator of quantile regression: The smoothed QR objective replaces the indicator I{x > 0} with H(x/h), making the approximating loss differentiable.The bandwidth satisfies h → 0, and the resulting derivative includes H(x/h) + τ − 1 + (x/h)H′(x/h).
  • 3.1. A linear type estimator of quantile regression: The smoothed optimization is non-convex and difficult to solve, so LEQR substitutes a consistent initial estimator for the unknown fixed-point solution.This substitution allows the estimator to be computed without solving the fixed-point equation over all data.
  • 3.1. A linear type estimator of quantile regression: A small-batch initial estimator enables LEQR to depend only on aggregated sums of Xi and XiX′i, requiring one optimization rather than N local optimizations.The resulting linear-system computation avoids explicitly forming a matrix inverse.
  • 3.2. Divide-and-conquer LEQR: Divide-and-conquer LEQR applies the linear estimator to each batch and refines the estimate across iterations using theory-guided bandwidths hg.The bandwidth schedule is defined for iterations g = 1, ..., q.

1. Quantile regression in large-scale sensor networks.

Algorithm 1 distributes LEQR across sensors by broadcasting an initial estimate, locally computing compact statistics, and repeating base-station aggregation for q iterations.

  • 1. Quantile regression in large-scale sensor networks: Each sensor receives the initial estimator, computes (Uk, Vk) locally, and transfers aggregated statistics toward the base station.Intermediate nodes retain sums from their children and their own local statistics.
  • 1. Quantile regression in large-scale sensor networks: Algorithm 1 takes data batches, q iterations, the quantile level τ, a smooth function H, and bandwidths hg as inputs.The final output is the estimator β̂(q).
  • 1. Quantile regression in large-scale sensor networks: At the first iteration the algorithm computes an initial estimator from D1, then uses the previous iteration's estimator thereafter.For each batch and iteration, it swaps the batch into memory, computes local statistics, maintains their sums, and updates the estimate.
  • 1. Quantile regression in large-scale sensor networks: The distributed procedure repeats the same aggregation pattern for g = 2, ..., q after the base station computes β̂(1).

2. Computational reduction of quantile regression.

LEQR reduces computation by solving one small-batch QR problem and then updating aggregated statistics, while its online version retains only the current estimator and compact summaries.

  • 2. Computational reduction of quantile regression: O(m^1.25p^3 log m + np^2 + p^3) bounds the final estimator's computation, compared with O(n^1.25p^3 log n) for full-data interior-point QR.The first bound includes initialization, statistic computation, and matrix-related costs.
  • 2. Computational reduction of quantile regression: The method computes local sums in O(np) and O(np^2), with O(p^3) arising from the inversion-related linear-algebra step.
  • 2. Computational reduction of quantile regression: Online LEQR initializes from the first m samples and defines bandwidths for successive intervals while processing newly arriving observations.The initialization uses h = (p/m)^1/2.
  • 2. Computational reduction of quantile regression: For each online observation, the algorithm updates cumulative statistics and computes the current estimator before removing obsolete summaries from memory.At interval boundaries it retains only the latest estimator and cumulative pair.

3. Online quantile regression for streaming data.

The online LEQR algorithm processes streaming data in one pass while retaining only compact running summaries and successively refining quantile-regression estimates. Its estimator achieves the same statistical efficiency as pooled-data QR under the stated conditions.

  • Algorithm: A one-pass procedure maintains only current estimates and weighted sums while producing a sequence of successively refined estimators.The memory state is updated incrementally as observations arrive.
  • Interval construction: The algorithm partitions streaming observations into intervals whose sizes are approximately n_l ≈ n_{l-2}^2, enabling periodic recomputation of an initial estimator.The interval design reflects the point at which additional fresh samples no longer improve the current online estimator.
  • Online memory and efficiency: O(p^2) memory, independent of n, is sufficient for online LEQR apart from O(m) space used to derive the initial estimator.The maintained state consists of prior estimates and weighted sums that can be updated online.
  • Theoretical guarantee: For any interval and time point, online LEQR attains the same statistical efficiency as quantile regression computed after merging all streaming data.Theorem 4.5 also establishes asymptotic normality for the online estimator.

4. Theoretical results.

The theoretical analysis establishes Bahadur expansions and asymptotic normality for multi-round DC LEQR under regularity and dimensionality conditions. Iterative aggregation reduces bias, requires only a constant number of rounds in polynomial-growth settings, and matches pooled-data QR efficiency while allowing p to diverge.

  • Bias reduction: One aggregation round reduces the estimator’s bias order from a_n to a_n^2, so iterative refinement successively improves estimation accuracy.The reduction is induced by the smoothing-based construction of LEQR.
  • Bahadur representation: The Bahadur remainder achieves a nearly optimal rate, matching the known fixed-p classical QR rate up to a logarithmic factor.The stated rate is supported by the theorem’s remainder analysis and comparison with classical QR.
  • Iteration complexity: A constant number of aggregation rounds suffices when n = O(m^A) and p = O(m^δ) for fixed A ≥ 1 and 0 < δ < 1.Under these growth conditions, the Bahadur remainder reaches a nearly optimal rate.
  • High-dimensional setting: The theory permits p to diverge and requires p = o(min{n^(1/3)/(log n)^(2/3), m^δ}) for the asymptotic normality result.The m^δ condition additionally supports consistency of the initial estimator.
  • Asymptotic normality: Theorem 4.4 shows that DC LEQR achieves the same asymptotic efficiency as pooled-data QR, while removing the naïve-DC restriction n = o(m^2).The required number of aggregation rounds is usually small, including when the dimension is large.
  • Bandwidth choice: The method’s bandwidth need not be precisely tuned because additional aggregation rounds can compensate for an inaccurate constant when bandwidths shrink at the prescribed rates.This distinguishes the multi-round construction from many other smoothed QR estimators.

5. Simulations.

Across simulated noise models, iterative DC LEQR achieves near-nominal inference coverage with few rounds, while naïve-DC deteriorates as n becomes large relative to m. The proposed method also retains good performance in high dimensions and offers computational gains.

  • 5.1. Coverage rates.: Coverage rates of DC LEQR are close to the nominal 95% level after q = 4 rounds, whereas naïve-DC coverage is low in most settings, especially when n > m^2.Coverage becomes stable at q = 5.
  • 5.2. Large-dimensional settings.: For p = 1000, DC LEQR coverage approaches the nominal 95% level after four iterations, indicating desirable performance as dimension increases.
  • 5.1. Coverage rates.: The proposed method has small bias, while naïve-DC has much larger bias whose squared magnitude can dominate variance as n grows relative to m.The variance of all methods decays at rate 1/n.
  • 5.3. Sensitivity analysis and data-adaptive choice of the bandwidth.: With q ≥ 3, different bandwidth scaling constants produce coverage rates close to 95%, suggesting robustness to suboptimal scaling choices.
  • 5.3. Sensitivity analysis and data-adaptive choice of the bandwidth.: The variance-estimator ratio is close to 1 for q = 4 or 5 and remains stable across scaling constants.
  • 5.4. Computation efficiency.: DC LEQR is about twice as fast as QR All, faster than naïve-DC, and grows almost linearly in n and q.For large n, DC LEQR also maintains much better coverage than naïve-DC.

6. Conclusions and future works.

The paper concludes that iterative refinement provides an efficient approach to quantile-regression inference under memory constraints and can extend to distributed and streaming settings. Future work targets broader dependence structures and additional QR models.

  • 6. Conclusions and future works.: Future work includes inference with correlated data and evolving coefficients in online settings, potentially using exponentially decaying weights for historical data.
  • 6. Conclusions and future works.: The framework is also slated for study in ℓ1-penalized high-dimensional and censored quantile regression under memory or distributed constraints.

A.2. Proof of Proposition 4.2.

This appendix develops the probabilistic bounds needed for Proposition 4.2 and then uses them to establish the iterative estimator’s rate recursively. The theorem follows by combining the resulting bound with a central limit theorem.

  • A.2. Proof of Proposition 4.2.: The proof bounds the relevant empirical process under condition (C3*) using truncation, moment control, and exponential inequalities.
  • A.2. Proof of Proposition 4.2.: Under condition (C3), the same empirical-process bound is obtained by applying the Cai–Liu exponential inequality after controlling the parameter net.
  • A.2. Proof of Proposition 4.2.: The induction propagates the estimator error through iterations with rate max(p/n, (p/m)^(2g−2)) for iteration g.
  • A.2. Proof of Proposition 4.2.: Theorem 4.4 follows from the Bahadur representation in Theorem 4.3 and the Lindeberg–Feller central limit theorem.

APPENDIX B: CONJUGATE GRADIENT METHOD FOR SOLVING LINEAR SYSTEMS

The appendix explains how conjugate gradients solve the linear systems required by LEQR without explicitly forming a matrix inverse. It also records assumptions and an extension to independent, non-identically distributed data.

  • APPENDIX B: CONJUGATE GRADIENT METHOD FOR SOLVING LINEAR SYSTEMS: Conjugate gradients iteratively solve Vβ = U by updating the solution, residual, and search direction until the residual is sufficiently small.
  • APPENDIX B: CONJUGATE GRADIENT METHOD FOR SOLVING LINEAR SYSTEMS: The method avoids explicit matrix inversion and has complexity O(p^2√κ) in the worst case for a p × p system.
  • APPENDIX B: CONJUGATE GRADIENT METHOD FOR SOLVING LINEAR SYSTEMS: The theoretical extension permits independent but non-identically distributed observations when the true coefficient vector is common across machines.
  • APPENDIX B: CONJUGATE GRADIENT METHOD FOR SOLVING LINEAR SYSTEMS: The appendix imposes uniform conditional-density, eigenvalue, moment, and dimensionality conditions for the non-identically distributed extension.

APPENDIX D: LIMITATION OF THE NA¨IVE-DC APPROACH

The naïve-DC estimator fails when the total sample size is too large relative to batch size because averaging reduces variance but not local-estimator bias. In particular, when n/m^2 diverges, increasing n no longer improves accuracy.

  • The naïve-DC estimator fails for quantile estimation when n ≥ c m^2 in the special case p = 0.
  • The appendix derives the local sample-quantile construction from order statistics and establishes its asymptotic distribution under bounded-density derivative conditions.The sample quantile uses order statistics with j = floor(τ(m + 1)) and γ = τ(m + 1) − j.
  • When n/m^2 →∞, the naïve-DC estimator’s accuracy depends only on m, so increasing n does not improve estimation.This failure occurs under the stated smoothness and growth conditions, with b ≠ 0.
  • The simulations compare DC LEQR, naïve-DC, and QR All across dimensions, noise distributions, sample sizes, and iteration counts.For p = 3, the experiments report coverage, bias, and variance; additional settings use p = 15 and p = 1000.

E.4. Comparison with ADMM.

The comparison evaluates DC LEQR against ADMM-based QR using statistical accuracy, computation time, and communication cost. DC LEQR is reported as faster while achieving coverage rates close to the nominal level, with communication costs depending on different iteration and dimension factors.

  • The ADMM comparison measures coverage, bias, variance, and computation time for p = 15, τ = 0.1, and homoscedastic normal noise.
  • The reported computation-time comparison neglects communication time, whose practical value can vary with the communication protocol.
  • DC LEQR requires O(qp^2(n/m)) communication bits, whereas ADMM requires O(q1p(n/m)) bits and q1 may depend on the Hessian condition number.
  • DC LEQR is faster than the ADMM-based method, while both methods achieve coverage rates close to the nominal 95% level.
  • For p = 3, DC LEQR coverage remains near nominal with sufficient iterations, whereas naïve-DC fails when n is large.
Loading 1810.08264v1…