PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Distributed Subsampling for Maximum Quasi-Likelihood Estimators with Massive Data

Jun Yu, HaiYing Wang, Mingyao Ai, Huiming Zhang

arXiv:2005.10435v3stat.MEcs.DCstat.COstat.ML

TL;DR

Massive-data subsampling must reduce computation while preserving estimation efficiency, but replacement-based methods can require all nonuniform probabilities simultaneously. The paper derives optimal Poisson probabilities for quasi-likelihood estimation, develops approximated and distributed procedures, and reports theoretical and numerical support for extracting useful information from massive datasets.

  • Problem

    Existing nonuniform subsampling methods often rely on replacement-based sampling, which is infeasible when probabilities for massive datasets cannot be calculated all at once.

  • Method

    The paper derives A- and L-optimal Poisson subsampling probabilities for quasi-likelihood estimation and develops approximated and distributed implementations with theoretical guarantees.

  • Results

    The proposed Poisson method maintains high estimation efficiency, while theoretical and numerical results support its use for extracting information from massive datasets.

  • Takeaways & Limitations

    Poisson and distributed subsampling provide a practically implementable framework for quasi-likelihood analysis when massive data create computational or storage constraints.

  • Takeaways & Limitations

    The optimal strategy requires calculating ||Σψ(β̂QLE)^-1x_i|| for every observation, taking O(Nd^2) time even when Σψ(β̂QLE) is available.

Abstract

from arXiv · show

Nonuniform subsampling methods are effective to reduce computational burden and maintain estimation efficiency for massive data. Existing methods mostly focus on subsampling with replacement due to its high computational efficiency. If the data volume is so large that nonuniform subsampling probabilities cannot be calculated all at once, then subsampling with replacement is infeasible to implement. This paper solves this problem using Poisson subsampling. We first derive optimal Poisson subsampling probabilities in the context of quasi-likelihood estimation under the A- and L-optimality criteria. For a practically implementable algorithm with approximated optimal subsampling probabilities, we establish the consistency and asymptotic normality of the resultant estimators. To deal with the situation that the full data are stored in different blocks or at multiple locations, we develop a distributed subsampling framework, in which statistics are computed simultaneously on smaller partitions of the full data. Asymptotic properties of the resultant aggregated estimator are investigated. We illustrate and evaluate the proposed strategies through numerical experiments on simulated and real data sets.

1 Introduction

The paper addresses computational and storage barriers in massive-data inference by developing optimal Poisson subsampling for quasi-likelihood estimation and distributed implementation. The proposed approach supports nonuniform sampling without requiring all probabilities simultaneously and is supported by theoretical and numerical results.

  • 1 Introduction: The method targets two big-data barriers: datasets too large for computer memory and computations that take too long.
  • 1 Introduction: Poisson subsampling avoids calculating all nonuniform sampling probabilities at once, addressing memory and computational constraints in massive datasets.Each data point can be included using its own probability while scanning the data sequentially or block by block.
  • 1 Introduction: Poisson subsampling retains high estimation efficiency with nonuniform probabilities compared with subsampling with replacement.
  • 1 Introduction: A distributed version selects subsamples in parallel or at different locations, addressing storage constraints imposed by large-scale data.The paper also investigates asymptotic properties of the resulting estimators and evaluates the strategies on simulated and real datasets.
  • 1 Introduction: The paper develops optimal Poisson subsampling for quasi-likelihood estimators, extending statistical guarantees beyond primarily linear and logistic regression settings.Quasi-likelihood estimation requires assumptions on response moments without specifying the response distribution.

2 Preliminaries

The preliminaries formulate quasi-likelihood estimation and a general Poisson subsampling algorithm, then establish consistency and asymptotic normality under stated assumptions. The framework permits sequential inclusion decisions and random expected subsample sizes.

  • 2 Preliminaries: Poisson inclusion decisions depend only on each data point’s probability, so probabilities need not be available simultaneously for all observations.Probabilities can be used one by one or block by block while scanning the data.
  • 2 Preliminaries: The expected subsample size is the sum of the individual Poisson sampling probabilities, while the realized subsample size is random and smaller than the full dataset under the paper’s setting.
  • 2 Preliminaries: The assumptions constrain parameter space, moments, smoothness, identifiability, and sampling weights to support consistency and stable estimation.The weight condition protects the estimating equation from domination by observations with extremely small sampling probabilities.
  • 2 Preliminaries: Under Assumptions 1–5, the Poisson-subsampling estimator is consistent for the full-data quasi-likelihood estimator at rate r^-1/2.
  • 2 Preliminaries: The framework establishes asymptotic normality for the Poisson-subsampling estimator under the same asymptotic regime.

3 Optimal Poisson Subsampling

The paper derives optimal Poisson subsampling probabilities for quasi-likelihood estimation under A- and L-optimality criteria, then develops approximations that can be computed in a streaming pass. The resulting practical procedures retain theoretical guarantees while reducing computation and memory requirements.

  • Optimal criteria: The optimal probabilities are derived to minimize the asymptotic mean squared error of the subsample estimator under the relevant optimality criteria.The A-optimality formulation targets approximation of the full-data quasi-likelihood estimator.
  • Implementation choices: When the sampling fraction r/N tends to a positive constant, setting M = ∞ does not reduce estimation efficiency according to the simulation results.This simplifies the probability calculation without an observed efficiency loss in that regime.
  • L-optimality: The L-optimality-based probabilities replace the covariance-adjusted covariate norm with ∥x_i∥, reducing computation from O(Nd^2) to O(Nd).This approximation avoids calculating the full covariance structure for every observation.
  • Practical implementation: The practical algorithm uses a pilot subsample to estimate unknown quantities and computes each approximated inclusion probability while scanning observations individually or block-by-block.The full data need not be loaded into memory, making the procedure suitable for massive datasets.
  • Practical implementation: Shrinkage increases small probabilities and decreases large ones, improving stability while retaining the ranking advantages of optimal subsampling and reducing sensitivity to potential outliers.The shrinkage parameter also prevents estimating equations from being inflated by observations with extremely small probabilities.
  • Theory: The practical estimators are shown to satisfy consistency and asymptotic normality under stated assumptions when the pilot and final subsample sizes grow at appropriate rates.The theoretical guarantees are established for the estimator produced by the practical algorithm.

4 Distributed Poisson Subsampling

The paper extends optimal Poisson subsampling to data partitioned across multiple machines by computing local subsamples and aggregating their estimators. The distributed estimator has asymptotic guarantees, but communication and memory constraints limit the usable per-machine subsample size.

  • Distributed framework: The distributed procedure computes subsampling statistics on separate machines, then combines local estimators with the pilot estimator to approximate the full-data quasi-likelihood estimator.The framework is designed for datasets stored across multiple locations and supports parallel computation.
  • Limitations: Pooling subsamples can exceed one machine’s memory, while data transfer may be time-consuming and raise security concerns; therefore, per-machine subsamples cannot be too large.The authors propose aggregating estimators from different machines to address this boundary.
  • Implementation: Machine-by-machine pilot sampling can pool small subsamples with negligible communication time in the proposed setting.The communication claim relies on the pilot subsample size r0 usually being small.
  • Implementation: The method remains valuable for K = 1 because the pilot estimator is already required and avoids repeating iterative calculation on the pilot sample.This connects the distributed procedure to the single-machine case.

5 Numerical Studies

Numerical studies show that MV- and MVc-based Poisson subsampling generally improve estimation efficiency over uniform subsampling across simulations and real data. Performance depends on subsample size, partitioning, shrinkage tuning, and the data setting.

  • Simulation Studies: MV- and MVc-based subsampling consistently produce smaller empirical MSEs than uniform subsampling across four simulated data sets.The result agrees with the theoretical efficiency comparisons.
  • Simulation Studies: As r increases, empirical MSEs decrease for all subsampling methods, supporting consistency of the subsampling estimators.
  • Simulation Studies: The two-step method performs best near ϱ = 0.25, while its advantage over uniform subsampling weakens as ϱ approaches 1.The shrinkage estimator is described as protecting the weighted estimating equation when residual-related terms are close to zero.
  • Simulation Studies: When r/N ≤ 0.3, M = ∞ performs comparably to M = E, whereas M = Q remains satisfactory for r/N ≥ 0.5.The reported MSE is not very sensitive to the choice of M.
  • Simulation Studies: With fixed r, increasing K improves aggregate-estimator accuracy, but with fixed Kr, increasing K deteriorates performance.The method outperforms uniform subsampling for both K = 5 and K = 10.
  • Citation Number Data Set: For the citation data, proposed methods have average estimates close to full-data estimates but significantly smaller empirical standard errors than uniform subsampling.Their empirical MSE dominance also matches the simulation pattern.

6 Conclusion

The paper derives and evaluates optimal Poisson and distributed subsampling methods for quasi-likelihood estimation, establishing theoretical properties and demonstrating potential on simulated and real data.

  • The paper derives optimal Poisson subsampling probabilities and develops a distributed optimal subsampling method.
  • The proposed methods are supported by theoretical analysis and extensive numerical experiments on simulated and real data sets.
  • Theoretical and numerical results demonstrate the proposed method’s potential for extracting useful information from massive data sets.

S.1 Proofs

The supplementary proofs formulate the weighted subsample estimating equation using inclusion indicators and define its derivative for subsequent theoretical analysis.

  • The weighted estimation equation for the subsample uses inclusion indicators to represent which observations are selected.
  • The derivative of the subsample estimating equation is defined as the basis for the subsequent proofs.

S.1.1 Proofs of Theorems 1 and 2

The proofs establish convergence and asymptotic distribution results for the subsample estimator under the stated assumptions, using conditional probability arguments and central-limit reasoning.

  • Conditional central-limit arguments verify the asymptotic distribution under the assumptions, including a Lindeberg-Feller condition.
  • The argument combines the auxiliary lemmas with the theorem assumptions to obtain the final estimator result.
  • The proofs establish convergence of the normalized subsample estimating equation to the full-data equation as subsample size and data size grow.
  • The estimator expansion yields the required probabilistic remainder behavior, and Slutsky’s theorem completes the stated asymptotic result.

S.1.2 Proofs of Theorems 3 and 4

The proofs derive optimal Poisson sampling probabilities by reducing the A- and L-optimality criteria to constrained optimization problems and characterizing their solutions.

  • For the alternative constrained problem, the optimal solution is characterized recursively through a threshold value M and ordered weights.
  • For the L-optimality criterion, minimizing the asymptotic mean square error reduces to a constrained optimization problem over sampling probabilities.
  • The Cauchy-Schwarz inequality shows that probabilities proportional to the optimization weights are optimal when they satisfy the upper-bound constraints.
  • The proof establishes that the threshold satisfies ℏN−k < M ≤ ℏN−k+1, completing the characterization of the optimal probabilities.

S.1.3 Proofs of Theorems 5 and 6

The proofs establish asymptotic control of the proposed subsampling variance estimators and derive the stated theoretical results under the paper’s assumptions.

  • Proof strategy: The first-step subsample contributes only an o_P(r^-1/2) term to the estimation equation under the stated rate condition.The proof therefore focuses on the second-step subsamples for the leading asymptotic behavior.
  • Proof strategy: The arguments repeatedly use triangle inequalities, Hölder inequalities, laws of large numbers, and bounded eigenvalue conditions.These tools control matrix and estimation-error terms in the proof of the variance approximation.
  • Variance approximation: The proofs show that the difference between the estimated and target variance matrices is o_P(r^-1).This follows by combining the intermediate bounds and assumptions before applying a lemma and Slutsky’s theorem.
  • Conclusion: The desired asymptotic conclusions then follow from the established bounds, Lemma S.1, and Slutsky’s theorem.The proof links the intermediate matrix approximations to the final theorem statements.

S.1.4 Proofs of Theorems 7 and 8

The proofs establish consistency and asymptotic behavior for the distributed estimators, showing that partition-wise subsample estimators can be aggregated under explicit growth conditions.

  • Partition-wise estimators: Under Assumptions 1–4, each partition-specific subsample QLE satisfies the required asymptotic approximation with probability approaching one.The result is stated conditionally on each data partition and supports the distributed analysis.
  • Estimator rates: The first-step estimator satisfies ||˜β1−βt|| = O_P(r^-1/2), establishing the required estimation rate.This combines the distance to the full-data QLE with the full-data estimator’s rate.
  • Distributed aggregation: Theorem 8 follows by combining the distributed approximation with Theorem 6 and applying Slutsky’s theorem.The final step transfers the pooled estimator’s asymptotic result to the distributed estimator.

S.2 Additional Simulation Results

Additional simulations compare estimation accuracy and computational cost across MV, MVc, and uniform subsampling in larger and distributed settings. The proposed methods generally outperform uniform subsampling, while MVc is faster and MV can be more informative when memory limits subsample size.

  • Estimation performance: The proposed methods have higher estimation efficiency than uniform subsampling in Case S3, even when some theoretical regularity assumptions fail.Case S3 violates conditions (iii) and (iv) of Assumption 2, yet the observed efficiency advantage remains.
  • Computational efficiency: All subsampling algorithms require significantly less computing time than the full-data QLE, whose Newton–Raphson complexity is O(ζNd^2).Subsampling avoids iterative calculations over the full data.
  • Computational efficiency: MVc usually requires less computation than MV, especially in higher dimensions, because its complexity scales as O(Nd + ζrd^2) rather than O(Nd^2 + ζrd^2).When N > ζrd, the respective complexities reduce to O(Nd) and O(Nd^2).
  • Distributed implementation: In the block-stored-data setting, the relative performance remains similar, while MVc is much faster than MV when the dimension is larger.The distributed experiment combines pilot and optimal estimators across five data files.
  • Accuracy–cost trade-off: MVc achieves smaller MSE than uniform subsampling at the same CPU time, with the advantage increasing as CPU time rises.MV can achieve smaller MSE than both alternatives at the same subsample size but requires longer time for comparable accuracy.
  • Asymptotic normality: The subsampling estimators’ empirical distributions are very close to normal for β1 in Case S1 with r = 2000.This visual check uses 1000 simulation repetitions and overlays estimated normal densities.
Loading 2005.10435v3…