PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed inference for quantile regression processes

Stanislav Volgushev, Shih-Kang Chao, Guang Cheng

arXiv:1701.06088v3math.STstat.ME

TL;DR

Massive datasets make conditional-distribution analysis computationally difficult, especially when many quantile levels are needed. The paper combines distributed quantile estimation with projection, showing that appropriate choices of computing units and grid levels preserve inferential accuracy while enabling efficient inference.

  • Problem

    Estimating conditional quantile functions across many levels is computationally costly, while full-data quantile regression may be infeasible on one computer.

  • Method

    The paper estimates quantile coefficients at grid levels in parallel and projects them to construct a conditional quantile regression process.

  • Results

    The proposed procedure preserves oracle inferential accuracy when the number of subsamples and quantile levels satisfy derived conditions.

  • Takeaways & Limitations

    The method provides a computationally efficient route to inference for conditional quantile processes and conditional distribution functions.

  • Takeaways & Limitations

    More complex models restrict the allowable number of subsamples and therefore reduce possible computational savings.

Abstract

from arXiv · show

The increased availability of massive data sets provides a unique opportunity to discover subtle patterns in their distributions, but also imposes overwhelming computational challenges. To fully utilize the information contained in big data, we propose a two-step procedure: (i) estimate conditional quantile functions at different levels in a parallel computing environment; (ii) construct a conditional quantile regression process through projection based on these estimated quantile curves. Our general quantile regression framework covers both linear models with fixed or growing dimension and series approximation models. We prove that the proposed procedure does not sacrifice any statistical inferential accuracy provided that the number of distributed computing units and quantile levels are chosen properly. In particular, a sharp upper bound for the former and a sharp lower bound for the latter are derived to capture the minimal computational cost from a statistical perspective. As an important application, the statistical inference on conditional distribution functions is considered. Moreover, we propose computationally efficient approaches to conducting inference in the distributed estimation setting described above. Those approaches directly utilize the availability of estimators from sub-samples and can be carried out at almost no additional computational cost. Simulations confirm our statistical inferential theory.

1. Introduction.

The paper develops distributed inference for conditional quantile regression processes, addressing computational costs from large data and dense quantile grids. It establishes conditions on data splitting and quantile levels that preserve inferential accuracy, and proposes efficient inference procedures.

  • Motivation: Distributed quantile regression addresses the infeasibility of solving the full-data optimization problem on one computer by splitting data across S machines.Each machine solves the quantile regression problem on a smaller sub-sample, and results are combined.
  • Motivation: Estimating conditional quantile functions over a dense grid is computationally costly because each new quantile requires rerunning the distributed algorithm.
  • Method: The two-step procedure estimates quantile coefficients at K grid levels and projects them to construct a conditional quantile regression process for any quantile.
  • Theory: Sufficient conditions for the number of subsamples and necessary conditions for quantile levels preserve the oracle rule, with the K lower bound independent of S.The conditions are sharp up to logarithmic factors in some cases.
  • Theory: The interplay among S, K, and model complexity reflects an intrinsic computational-statistical trade-off rather than a proof artifact.
  • Inference: Normal, t-based, bootstrap, and variance-estimation approaches provide computationally efficient inference, while simulations assess their finite-sample behavior.These methods exploit estimators already computed from independent sub-samples.

2. A two-step procedure for computing quantile process.

The paper constructs a conditional quantile regression process by combining distributed estimates on a quantile grid with spline projection. The resulting process supports quantile-function and conditional-distribution estimation across a flexible model class.

  • Model framework: The framework covers fixed-dimensional, diverging-dimensional, locally supported, and non-locally supported transformation models.
  • Divide-and-conquer estimation: The divide-and-conquer algorithm splits observations into S sub-samples, computes local quantile regression coefficients, and pools them at a master machine.
  • Quantile projection: The two-step procedure first estimates β(τ_k) at K grid points and then projects coefficient trajectories onto a spline-function space.
  • Quantile projection: The projection matrix is formed from the grid-level estimates, allowing β(τ) to be computed at arbitrary τ through the projected representation.
  • Distribution-function application: The estimated quantile process can be used to estimate the conditional distribution function, whose properties depend on the projected map τ ↦ Z(x)^Tβ̂(τ).

3. Theoretical analysis.

Theoretical results characterize when distributed quantile estimators and their projected processes retain oracle inferential behavior, with sharp restrictions on splitting and quantile-grid size. The restrictions become tighter as model complexity increases, while smoother quantile functions permit smaller grids.

  • Fixed dimensional linear models: Theorem 3.1 derives sharp remainder bounds using a new Bahadur representation, improving on the more restrictive bound from earlier representations.The sharper expectation bound is crucial for the theorem’s bound on the distributed estimator’s error.
  • Fixed dimensional linear models: The proposed estimator differs from the oracle by a distributed-estimation term and a projection bias bounded by O(G^−η).The oracle estimator itself converges uniformly at rate OP(N^−1/2) under the stated theorem conditions.
  • Fixed dimensional linear models: The sharp lower-bound results show that no divide-and-conquer procedure can achieve precision beyond the local-machine sample size n = N/S.This limitation holds regardless of the total sample size N.
  • Fixed dimensional linear models: S = o(N^1/2(log N)^−1) and G ≫ N^1/(2η) suffice for process-level oracle behavior, while S = o(N^1/2) and G ≫ N^1/(2η) are necessary.The grid-size condition is tied to the smoothness η of the quantile function.
  • Approximate linear models with local basis structure: In increasing-dimensional local-basis models, allowable splitting becomes more restrictive with dimension m, so complex models require larger subsamples and greater computational cost.The sufficient and necessary conditions on S explicitly depend on m.
  • Approximate linear models with local basis structure: For nonparametric models, G ≫ (N/∥Z(x0)∥^2)^(1/(2η)) can be weaker than G ≫ N^(1/(2η)), reducing the required quantile-grid size.This occurs because the oracle estimator’s convergence rate is typically slower in these models, making projection bias easier to keep negligible.

4. Practical aspects of inference.

The paper develops practical inference procedures for distributed quantile regression that reuse subsample estimators, while analyzing covariance estimation, bootstrap validity, and bandwidth selection. These methods avoid costly central computation but have limitations for small numbers of subsamples and nonlinear or uniform inference.

  • 4.1. Inference utilizing results from subsamples.: Subsample-based inference is computationally simple because it requires no costly computation or communication between machines.The procedures directly exploit the availability of S subsample estimators on the central machine.
  • 4.1. Inference utilizing results from subsamples.: For small S, student-t intervals can improve precision, but normal-based intervals may miscover and t-based intervals may be substantially wider.The paper specifically discusses S ≤30 and notes that the approach is unavailable when S is smaller than the parameter dimension.
  • 4.1. Inference utilizing results from subsamples.: Theorem 4.1 establishes asymptotic coverage 1 −α for the studentized confidence interval when S ≥2, including fixed S.If S →∞, the alternative interval based on the asymptotic distribution also has asymptotic coverage 1 −α.
  • 4.1. Inference utilizing results from subsamples.: The proposed subsample bootstrap is formally valid under the stated assumptions and uses stored subsample estimators rather than repeated full-sample estimation.The bootstrap converges conditionally to the relevant centered Gaussian process and differs from cluster-robust bootstrap by avoiding repeated complete-sample estimation.
  • 4.2. Inference based on estimating the asymptotic covariance matrix.: Bandwidth selection is needed to estimate the asymptotic covariance matrix because it balances bias and variance in density-based quantities.The matrix J_m(τ) involves the conditional density and is more difficult to estimate, motivating Powell-type estimators.
  • 4.2. Inference based on estimating the asymptotic covariance matrix.: Under S = o(N^2/5(log N)^−1), the first-order expansion of the pooled estimator matches the Powell oracle estimator's MSE rate.The paper also notes that the subsample-optimal choice h_n ∼n^−1/5 is not optimal for the averaged estimator.

5. Monte Carlo experiments.

The Monte Carlo experiments evaluate distributed quantile-regression inference across model dimensions, subsample counts, variance estimators, and conditional-distribution functionals. Results broadly support reliable inference when the theoretical oracle conditions are met, while coverage deteriorates earlier for more complex models and tail quantiles.

  • 5.1. Results for the divide and conquer estimator: Starting from about S = 20, coverage probabilities of the four confidence-interval procedures are very close.For smaller S, normal and bootstrap intervals under-cover, whereas oracle and t-based intervals maintain nominal coverage.
  • 5.1. Results for the divide and conquer estimator: For m = 32 and n = 512, the oracle rule does not apply for S > 10, while increasing n to 2048 improves coverage behavior.The reported pattern matches the theoretical dependence on model complexity and subsample size.
  • 5.1. Results for the divide and conquer estimator: The asymptotic variance estimators show no notable differences when S is large, and naive hn ∼n−1/5 and optimal hn ∼N−1/5 bandwidths perform similarly.The automatic quantreg choice also performs reasonably well.
  • 5.1. Results for the divide and conquer estimator: Coverage probabilities at tail quantiles τ = 0.1 and 0.9 drop to zero faster than at τ = 0.5 in linear models with normal errors.The paper relates this pattern to different derivatives of the error density across quantiles.
  • 5.2. Results for the estimator bFY |X(y|x): For m = 4, bootstrap and oracle intervals perform similarly once S ≥20, whereas for m = 32 the oracle interval indicates that n is too small even at S = 2.In the m = 32 setting, bootstrap and asymptotic confidence intervals differ because the bootstrap theory assumes the oracle rule holds.
  • 5.1. Results for the divide and conquer estimator: The authors recommend normal approximation for S > 20, bootstrap inference for process-level results, and aggregated within-subample variance estimation for S < 20.These approaches use sub-sample results and are described as requiring no additional computation or implementation in the relevant regimes.

APPENDIX A: APPROXIMATE LINEAR MODELS WITHOUT LOCAL BASIS STRUCTURE

Appendix A extends the oracle-rule analysis to approximate linear models without local basis structure, allowing increasing dimension and general series transformations. It gives complexity-dependent sufficient conditions, covariance-estimation procedures, and process-level extensions.

  • General series models: For the general series model, the oracle rule requires m4(log N)10 = o(N) and S = o(N1/2m−2(log N)−2).The condition becomes more restrictive as model dimension m grows.
  • Comparison with local basis structure: Local-support spline conditions give sharper bounds than the general series conditions when both apply, although the general result covers settings excluded by the local structure assumption.Linear models can generally be handled by the more general corollary but not by the local-support result.
  • Process extensions: The appendix extends the theory from pointwise estimators to conditional-quantile processes and conditional-distribution-function estimators under spline-projection conditions.The process result uses Gaussian-process convergence and requires conditions on K, G, approximation bias, and regularity.
  • Covariance estimation: An additional communication round estimates the asymptotic covariance matrix at oracle rate N−2/5 without optimization on each sub-sample.Each distributed unit computes and returns matrix quantities after receiving the aggregated estimator.

S.3.1. Proofs for Section 3.1.

The proofs establish oracle-rule validity for fixed-dimensional models by combining the oracle estimator’s weak convergence with bounds showing that the distributed estimator has a negligible difference under the stated growth condition.

  • S.3.1. Proofs for Section 3.1.: For fixed-dimensional models, the approximation and centering errors vanish because γN ≡β and cm(γN) = gN(γN) = 0.These simplifications connect the general theorem to the fixed-dimensional setting.
  • S.3.1. Proofs for Section 3.1.: When S = o(N1/2(log N)−1), the aggregated estimator satisfies β−bβor = oP(N−1/2) and inherits the oracle estimator’s weak convergence.The result follows from the oracle estimator’s convergence and the bound on the distributed-estimation remainder.

S.3.2. Proofs for Section 3.2.

The proofs for the process results establish convergence for the oracle and distributed estimators, then show sharp failures when the quantile grid or number of sub-samples is too small or too large relative to sample size and model complexity.

  • S.3.2. Proofs for Section 3.2.: The proofs derive process convergence by controlling the difference between bβor(τ) and bβ(τ), then applying weak-convergence arguments to the oracle process.The distributed and oracle processes differ by a term of order oP(∥Z(x0)∥N−1/2) under the stated assumptions.
  • S.3.2. Proofs for Section 3.2.: The oracle rule fails whenever G ≲N1/(2η) for process convergence, independently of the number of sub-samples S.With increasing model dimension, the corresponding threshold includes the factor ∥Z(x0)∥−1/η.
  • S.3.2. Proofs for Section 3.2.: For sufficiently large S, the oracle rule fails at thresholds of order N1/2, with additional ξm−1 dependence in increasing-dimension settings.The proof constructs data-generating processes demonstrating necessity of these sub-sample bounds.
  • S.3.2. Proofs for Section 3.2.: The necessity proof constructs smooth quantile functions whose localized features lie between adjacent quantile-grid knots, preventing weak convergence when G is too small.The construction applies regardless of S in the fixed-dimension case.

S.3.3.2. A special class of data generation processes.

This section constructs special data-generating processes used to test the necessity of the paper’s oracle conditions. The construction produces failures of weak convergence when the computational parameters violate those conditions.

  • Approximation setup: The spline projection setup represents the quadratic quantile function exactly when the spline degree is at least two.This property is used to isolate the distributed estimation effects from approximation error.
  • Data-generating construction: The constructed processes use discrete covariates with independent responses and quantile functions generated from the family F_a,b.The covariates take scaled unit-vector values, while the response distribution and quadratic quantile function are selected to control bias and approximation behavior.
  • Necessity results: For fixed dimension, weak convergence fails when the number of sub-samples is not o(N^1/2).The contradiction is established by showing divergence or incompatibility with the claimed Gaussian limit.
  • Necessity results: For growing dimension, the same construction yields failure of process convergence under analogous violations of the required growth conditions.The argument uses a dimension-dependent covariate design and shows failure at a coordinate corresponding to a unit vector.

S.4.1. Proof of Theorem 4.1.

This proof establishes the coverage result for distributed confidence intervals by analyzing fixed and increasing numbers of sub-samples. It combines convergence of studentized quantities with uniform empirical-process bounds.

  • Coverage proof: Coverage converges to 1−α for fixed sub-sample counts and also when the number of sub-samples diverges.For diverging sub-sample counts, the relevant t critical value converges to the corresponding standard-normal critical value.
  • Variance estimation: The proof identifies the sample variance of sub-sample estimators as the variance estimator entering the confidence interval.The variance expression is explicitly recognized as the sample variance of the distributed estimators evaluated at the target covariate.
  • Empirical-process control: Uniform asymptotic equicontinuity supplies tightness for the empirical processes needed to control quantile-index variation.The argument uses entropy bounds, moment inequalities, Bernstein or Chernoff bounds, and union bounds.

APPENDIX S.6: REFINED BAHADUR REPRESENTATIONS FOR SUB-SAMPLES AND THEIR PROOFS

This appendix derives refined Bahadur representations for sub-sample quantile estimators and bounds their remainder terms under the paper’s regularity conditions. The proof combines empirical-process approximations with leave-one-out and concentration arguments.

  • Representation: The refined representation decomposes each sub-sample estimator into a leading empirical-process term plus controlled remainder terms.The theorem assumes conditions on m, ξ_m, and n and provides bounds for the resulting remainder components.
  • Contribution: A new bound in the supplementary results is identified as crucial for the paper’s asymptotic bias-reduced procedures.The appendix distinguishes these new bounds from results reproduced from earlier work.
  • Proof strategy: The remainder bounds rely on leave-one-out estimators, Taylor expansions, maximal inequalities, and concentration bounds.The proof repeatedly invokes Bernstein, McDiarmid, Markov, and union-bound arguments to obtain high-probability control.

S.6.2. Proof of Theorem S.6.2.

This proof refines the Bahadur representation under local-basis conditions by exploiting the sparsity of local basis functions. The argument controls localized remainder terms and establishes the required approximation bounds.

  • Local basis structure: Condition (L) restricts relevant basis interactions to at most L consecutive indices, enabling localized remainder control.The proof defines neighboring index sets around the active basis location and uses them throughout the bounds.
  • Remainder control: The proof combines local index decompositions with concentration inequalities and Taylor expansions to control leave-one-out differences.These steps bound the relevant events uniformly over quantile levels, covariates, and basis indices.
  • Theorem conditions: The refined theorem requires mξ_m^2 log n=o(n) and yields bounds for the remainder terms under the local-basis condition.The resulting estimates are obtained for γ_N and are used in the proof of the refined Bahadur representation.
  • Auxiliary results: The appendix verifies the auxiliary bias and variance properties using binomial counts, beta distributions, and polynomial quantile functions.The construction supports the bounds needed for the local-basis theorem.

APPENDIX S.9: TECHNICAL DETAILS FOR SIMULATION AND ADDITIONAL SIMULATION RESULTS

This appendix supplements Section 5 with simulation details and additional figures, including cases for m = 16 and large numbers of subsamples.

  • APPENDIX S.9: Additional simulations examine oracle properties of the divide-and-conquer estimator β(τ) and the distribution-function estimator bFY |X(y|x).The supplement also includes technical details for the simulation settings in Section 5.

S.9.1. Details for Section 5 and additional simulation results.

The supplementary simulations document implementation details and extend the Section 5 coverage analysis to m = 16 and large numbers of subsamples.

  • Implementation: The pooled covariance estimator averages sub-sample covariance estimates computed with kernel-based standard errors from quantreg.The implementation uses se='ker' and covariance=TRUE for each sub-sample before averaging.
  • Simulation implementation: The simulations use c∗(τ) values from Kato’s theory and reuse values based on m = 4 because they change little with m under the design.An independent data set is simulated to compute c∗(τ), reducing simulation computation time.
  • Additional simulation results: Additional figures report coverage for Q(x0; τ) and FY |X(y|x0) across τ, sub-sample counts, and dimensions including m = 16.The confidence-interval comparisons use nominal coverage 0.95, with n = 512 or 2048 and several inference procedures.

S.9.2. Heteroskedastic model.

The heteroskedastic-model supplement studies coverage under linear location-scale shifts and examines how subsample count, dimension, and quantile-grid choices affect oracle inference.

  • Simulation results: Coverage in the heteroskedastic simulations starts to decline earlier than in the corresponding homoskedastic results for m = 4, 16, and 32.The supplement compares the patterns using Figures S.9.4 and S.9.5 with the Section 5 and homoskedastic analyses.
  • Distribution-function inference: Bootstrap confidence intervals for FY |X(Q(x0; τ)|x0) are compared with oracle asymptotic intervals using K = 65 quantile-grid points and G = 32 spline knots.The grid and knot counts are selected to ensure nominal coverage of the oracle intervals.
  • Oracle rule: Coverage reaches the nominal 95% level below a threshold S∗ but drops quickly above it; S∗ moves toward N1/2 as N increases and decreases with dimension m.Under exponential errors, coverage is asymmetric in τ, requiring larger N for small τ to attain the same S∗ magnitude.
  • Oracle rule for bFY |X(y|x): For the quantile-process estimator, larger basis dimension q improves coverage at fixed m and S, while larger m reduces the admissible S∗ for fixed q.The same analysis varies the number of subsamples S, model dimension m, basis dimension q, and quantile-grid points K.

S.9.4. Nonparametric model.

The nonlinear-model simulations examine coverage for quantile and conditional-distribution confidence intervals while varying subsample and basis dimensions. Larger basis dimensions reduce bias but also reduce the admissible number of subsamples.

  • S.9.4.1. Oracle rule for β(τ).: The nonlinear model uses the function 2.5 + sin(2x) + 2 exp(−16x2) with cubic B-spline basis functions and quantile Q(x; τ) = 2.5 + sin(2x) + 2 exp(−16x2) + 0.7Φ−1(τ).The basis is defined using m + 4 knots on [−1, 1].
  • S.9.4.1. Oracle rule for β(τ).: The experiments vary S and m for quantile confidence intervals and S, m, q, and K for conditional-distribution confidence intervals.The conditional-distribution analysis evaluates y0 = Q(x0; τ), so the target distribution value equals τ.
  • S.9.4.1. Oracle rule for β(τ).: At x0 = 0, m = 13 has the worst coverage because large curvature creates substantial bias in Q(x0; τ).Increasing m can reduce this bias, although the resulting smaller S∗ creates a competing constraint.
  • S.9.4.2. Oracle rule for bFY |X(y|x).: Larger m improves performance under fixed S, q, and K by reducing estimation bias, but it also produces a smaller S∗.This pattern is reported for conditional-distribution confidence intervals and is consistent with Corollary 3.10.

S.9.5. Practical conclusions from simulations.

The practical recommendations favor fewer subsamples and more quantile-grid points, with choices calibrated to basis dimension, quantile-function roughness, and effective subsample size. Simulations indicate that exponential errors and rapidly changing quantile spread require particular caution.

  • S.9.5. Practical conclusions from simulations.: Ensure n/m is at least 50 and keep S no larger than n/m as a rule of thumb.These recommendations are motivated by coverage behavior in the simulations.
  • S.9.5. Practical conclusions from simulations.: Coverage starts to decline earlier for smaller quantiles under exponential conditional errors, where the conditional quantile function has larger second derivative.The simulations use the nonlinear model with N = 216 and vary S, m, q, and K.
  • S.9.5. Practical conclusions from simulations.: K > N1/4 worked well in the simulations, while G = K/2 with cubic splines is a reasonable choice.The required constant depends on the roughness of τ 7→Q(x; τ), and K/G > c is sufficient according to the proof discussion.
  • S.9.5. Practical conclusions from simulations.: The supplementary figures report 95% confidence-interval coverage for Q(x0; τ) and F(y0|x0) across normal- and exponential-error settings.The figures include the nonlinear model and vary quantile-grid and projection dimensions in the displayed simulation settings.
Loading 1701.06088v3…