PaperlayerView exact revision on arXiv

Source-linked AI summary

Information-Based Optimal Subdata Selection for Big Data Linear Regression

HaiYing Wang, Min Yang, John Stufken

arXiv:1710.10382v1stat.ME

TL;DR

Very large data sets create computational barriers for linear regression, while subsampling introduces sampling error and covariance limits tied to subdata size. The paper proposes information-based optimal subdata selection (IBOSS), which deterministically selects informative observations. IBOSS is reported to be faster and to allow slope-estimator variances to converge to 0 as full-data size grows even with fixed subdata size.

  • Problem

    Big-data linear regression requires data reduction because full-data analysis faces computational limitations, while subsampling induces sampling error and covariance typically bounded below by order 1/k.

  • Method

    IBOSS deterministically selects the most informative data points so a small subdata set preserves most information from the full data.

  • Results

    IBOSS is reported to be faster than existing methods, and its estimator variances can converge to 0 as n grows even when k is fixed.

  • Takeaways & Limitations

    IBOSS provides a subdata-based linear-regression approach whose slope-estimator variance can depend on full-data growth rather than remaining tied solely to fixed subdata size.

  • Takeaways & Limitations

    Subsampling-based covariance is typically bounded below by order 1/k, so its variance does not go to 0 as full data size n increases.

Abstract

from arXiv · show

Extraordinary amounts of data are being produced in many branches of science. Proven statistical methods are no longer applicable with extraordinary large data sets due to computational limitations. A critical step in big data analysis is data reduction. Existing investigations in the context of linear regression focus on subsampling-based methods. However, not only is this approach prone to sampling errors, it also leads to a covariance matrix of the estimators that is typically bounded from below by a term that is of the order of the inverse of the subdata size. We propose a novel approach, termed information-based optimal subdata selection (IBOSS). Compared to leading existing subdata methods, the IBOSS approach has the following advantages: (i) it is significantly faster; (ii) it is suitable for distributed parallel computing; (iii) the variances of the slope parameter estimators converge to 0 as the full data size increases even if the subdata size is fixed, i.e., the convergence rate depends on the full data size; (iv) data analysis for IBOSS subdata is straightforward and the sampling distribution of an IBOSS estimator is easy to assess. Theoretical results and extensive simulations demonstrate that the IBOSS approach is superior to subsampling-based methods, sometimes by orders of magnitude. The advantages of the new approach are also illustrated through analysis of real data.

1 Introduction

Big-data linear regression requires data reduction because full-data OLS can exceed available computing capacity, while random subsampling introduces sampling error and size-dependent information limits. The paper proposes IBOSS, which deterministically selects informative points and offers faster computation, distributed suitability, and slope-estimator variances that can vanish as n grows with fixed k.

  • Motivation: For n ≫p, ordinary least squares requires O(np2) computing time, which may exceed available computational capacity.Data reduction is therefore presented as a crucial step for extracting useful information from extremely large data sets.
  • Limitations of existing methods: Random subsampling induces sampling error, and its estimator covariance is typically bounded below by a term of order 1/k.Here k denotes the subsample size, so this lower-bound order depends on k rather than the full data size.
  • IBOSS approach: IBOSS deterministically selects the most informative data points so a small subdata set preserves most information from the full data.Its framework borrows the information-maximization motivation of optimal experimental design for parameter estimation from existing data.
  • IBOSS advantages: O(np) computing time makes IBOSS significantly faster than existing methods and suitable for distributed parallel computing.The algorithm identifies informative points by examining each covariate individually.
  • Statistical properties: With fixed subdata size k, IBOSS estimator variances can converge to 0 as the full data size n becomes large.The paper also states that IBOSS estimators inherit distributional properties of estimators based on the full data.
  • Paper scope: The paper develops the IBOSS framework, derives a lower covariance bound for subsampling estimators, and evaluates IBOSS through asymptotic analysis, simulations, and real-data applications.The framework characterizes D-optimal IBOSS subdata and supports a computationally efficient algorithm.

2 The framework

The framework formulates deterministic subdata selection for linear regression through information matrices and contrasts it with random subsampling. It shows that common subsampling estimators retain covariance lower bounds of order 1/k that do not vanish as n increases.

  • The framework: The linear regression framework defines full-data and subdata least-squares estimators through their corresponding information matrices.Subdata are selected deterministically from the full data using covariates only, while preserving the regression model assumptions.
  • Information-based selection: Selecting covariate values to maximize subdata information minimizes the minimum variance of linear unbiased estimators.This connects the framework to optimal experimental design and motivates optimizing a matrix criterion.
  • Information-based selection: D-optimality maximizes the determinant of the subdata information matrix, minimizing the expected volume of the joint confidence ellipsoid for β.
  • Existing subsampling methods: Random subsampling can produce non-estimable subdata and requires restricting attention to full-rank covariate matrices for covariance analysis.The resulting covariance properties are more complicated for fixed-size sampling without replacement.

3 The D-optimality criterion and an IBOSS algorithm

The D-optimality analysis motivates IBOSS by selecting observations with extreme covariate values. The resulting algorithm has linear-time selection in n for each covariate, supports parallel processing, and retains the relevant convergence order under stated conditions.

  • D-optimality criterion: D-optimality suggests selecting subdata with both smallest and largest values of each covariate, balanced across extremes.The exact determinant bound is attained by 2p extreme points when each occurs equally often.
  • IBOSS algorithm: Algorithm 1 selects r smallest and r largest observations for each covariate, excluding previously selected observations.Here r = k/(2p), with adjustments available when r is not an integer.
  • IBOSS algorithm: O(np + kp^2) is the algorithm’s total time complexity, reducing to O(np) when n > kp.Partition-based selection finds each covariate’s required order statistics in average O(n) time.
  • IBOSS algorithm: IBOSS is faster than algorithmic leveraging, whose computing time is O(np log n).
  • Implementation and inference: The algorithm is suited to distributed parallel computing because covariates can be processed simultaneously before combining selected indexes.Duplicate indexes may reduce the resulting subdata size below k, while preserving the same convergence rate.
  • Theoretical properties: Under fixed p and a positive limiting minimum eigenvalue of the covariate correlation matrix, IBOSS can achieve the same order as the D-optimality upper bound.The result states that the relevant determinant lower bound does not converge to 0 as n approaches infinity.

4 Properties of parameter estimator

The section establishes finite-sample and asymptotic variance properties for IBOSS estimators under stated covariate-distribution assumptions. Its central result is that slope variances can decrease with the full-data size even when the subdata size is fixed, unlike typical subsampling behavior.

  • Theoretical framework: IBOSS variance results include finite-sample bounds and asymptotic properties for estimators obtained from Algorithm 1.The analysis is motivated by D-optimality and covers covariance matrices under various assumptions.
  • Variance behavior: The intercept variance remains proportional to 1/k and therefore does not converge to 0 when the subdata size k is fixed.This limitation is less concerning when inference focuses primarily on slope parameters; an adjusted intercept estimator using full-data means can improve intercept efficiency at additional O(np) cost.
  • Variance behavior: The slope variance is bounded above by a term proportional to p/[k(z_(n−r+1)j−z_(r)j)^2], which may converge to 0 as n increases with fixed k.The general bound applies for arbitrary n, r, and p, and can yield convergence faster than the typical 1/k subsampling rate when p/(z_(n−r+1)j−z_(r)j)^2=oP(1).
  • Asymptotic information: When k is fixed and the covariate sample range diverges, the slope-estimator variance has the order of the inverse squared full-data sample range.Thus, the selected subdata can preserve information at a scale related to the full data size.
  • Distribution-specific comparisons: For normal covariates, covariance components converge at rate 1/log n, while t-distributed covariates give D-OPT IBOSS slope variance rate n^(-2/ν).Under the tν example with ν≤2, this rate is close to the full-data rate, whereas UNI convergence is much slower and common subsampling slope variances remain bounded below by terms proportional to 1/k.

5 Numerical experiments

Numerical studies compare D-OPT IBOSS with random subsampling, leverage-based subsampling, and full-data regression across simulated and real data. D-OPT IBOSS generally provides stronger estimation performance, valid confidence-interval coverage, and favorable computational efficiency.

  • Simulation studies: D-OPT IBOSS uniformly dominates the UNI and LEV subsampling methods for slope estimation across the simulated covariate distributions.Its advantage is more significant for heavier-tailed covariate distributions.
  • Simulation studies: MSEs for D-OPT IBOSS slope estimators decrease as n increases even when the subdata size remains fixed at k = 10^3.For normal covariates, the decrease is slower, with a convergence rate as slow as p/k/log n.
  • Simulation studies: 80%: scaled D-OPT IBOSS slope MSEs are about 80% of those for the subsampling-based approaches.The scaling sets UNI MSEs to one for comparison.
  • Simulation studies: 2.4 times: full-data slope MSE at n = 10^5 is as large as the D-OPT IBOSS MSE using k = 10^3 from n = 10^6.The D-OPT IBOSS analysis therefore outperforms that full-data analysis in the reported mixture-distribution example.
  • Simulation studies: D-OPT IBOSS remains the best-performing subdata method as k increases; with k = 200, it is about 10 times as accurate as LEV with k = 5 × 10^3.This comparison uses slope estimation with n = 10^6 for the specified mixture distribution.
  • Simulation studies: All empirical confidence-interval coverage levels are close to the nominal 0.95 level, supporting valid inference from IBOSS subdata.The study evaluates 95% intervals for the first slope parameter under normal and mixture covariate distributions.
  • Computational efficiency: D-OPT IBOSS compares favorably with LEV in CPU time, and both are more efficient than the full-data method.The timing comparison fixes k = 10^3 across combinations of n and p.
  • Real-data analysis: For CSFII data, D-OPT IBOSS slope estimates have signs consistent with full-data estimates, while standard errors are larger but reasonably good for the small subdata size.The method identifies significant effects of fat, protein, and carbohydrate intake levels, although one full-data significant effect is not identified by IBOSS.

6 Concluding remarks

The paper develops IBOSS for big-data linear regression, analyzes limits of subsampling estimators, and derives a computationally efficient D-optimal selection procedure. Its asymptotic properties and performance are studied theoretically and with simulated and real data, while broader optimality criteria remain future work.

  • Contribution: IBOSS is developed as a subdata selection method for big-data linear regression.The paper frames informative subdata identification as important for extracting useful information from big data.
  • Contribution: The paper derives a lower bound for covariance matrices of estimators produced by existing subsampling-based methods.This analysis is conducted within the IBOSS framework for big-data linear regression.
  • Method and evaluation: D-optimality is used to characterize IBOSS subdata and develop a computationally efficient algorithm that approximates the optimal selection.Theoretical properties of D-OPT IBOSS are examined asymptotically and its performance is demonstrated with simulated and real data.
  • Limitations and future work: Other optimality criteria, including A-optimality and c-optimality, may support efficient IBOSS methods but are not developed here.A-optimality targets average coefficient variance, while c-optimality targets the variance of an estimator of a prespecified parameter function.
  • D-optimal selection: Selecting the 2p covariate-extreme points, with each occurring equally often, yields an information matrix equal to the identity and D-optimal subdata.The selected points use the smallest or largest observed value for each covariate.
  • Algorithmic detail: The constructed subdata may not contain exactly the r smallest and r largest values for every covariate because processing one covariate can remove data points.This is a property of the algorithmically obtained subdata rather than the idealized extreme-point construction.

A.5 Proof of Theorem 5

The proof analyzes how selected order statistics and concomitants determine the asymptotic behavior of the IBOSS information matrix under several tail-support regimes. It then specializes the analysis to normal and lognormal covariates.

  • Order-statistic regimes: The proof treats five cases for the covariate distribution, including fixed r, diverging r with bounded support, and unbounded-tail settings.For an unbounded upper endpoint, the growth of r is restricted by an explicit tail condition.
  • Order-statistic regimes: For the third case, showing z_(n−r+1)j/z_(n)j = 1 + o_P(1) establishes the required asymptotic relation for upper order statistics.The argument uses tail normalization and results from Hall (1979).
  • Selected-subdata moments: The proof uses concomitants of covariate order statistics to track the associated values of the remaining covariates in the selected subdata.These concomitants enter the sample means, variances, and covariance calculations for the selected observations.
  • Distribution-specific cases: For normal covariates, extreme-order-statistic calculations provide the asymptotic ingredients used to derive the corresponding results.The proof invokes Gaussian extreme-value results and combines the resulting relations with earlier equations.
  • Distribution-specific cases: For lognormal covariates, the proof transforms Gaussian variables through z_ij = exp(U_ij) and derives the associated extreme-value behavior.The argument assumes nonnegative pairwise correlations and uses the transformed moments in the final matrix calculations.

A.7 Proof of results in Table 1

For t-distributed covariates, the proof compares the variance orders of slope estimators under D-OPT IBOSS, full-data, and UNI approaches. The supplied results indicate that D-OPT IBOSS and full-data variances decrease with the full sample size, whereas UNI has a slower lower-bound rate.

  • The D-OPT IBOSS slope-estimator variance has the same order as (z(n)1 − z(1)1)−2.
  • The full-data slope-estimator variance has the same order as the inverse of the relevant full-data quadratic covariate sum.
  • The UNI slope-estimator variance has a lower bound of order O(1) when ν > 2, which is slower than n2/ν−1+α.
  • The intercept-estimator variance is of the same order as the inverse of the sample size used in each method.
  • Additional numerical results: In prediction experiments, D-OPT IBOSS uniformly dominates UNI and LEV, with a larger advantage for heavier-tailed covariate distributions.
  • Additional numerical results: For Case 6, D-OPT IBOSS performs almost identically to the full-data approach, while LEV significantly outperforms UNI.
  • Column permutation: After random column permutation, IBOSS performance is very similar to performance under the original covariate-column order.
  • Interaction model: With interaction terms excluded from selection but included in estimation, IBOSS remains the most efficient subdata-based method for both covariate distributions.

S.4 Nonlinear relationships

The nonlinear-relationship experiments evaluate linear-model subdata methods when transformations cannot make the true relationships linear. No method, including full-data estimation, dominates across the considered nonlinear models and metrics.

  • The considered nonlinear setting cannot be represented by a correct finite-dimensional linear model.
  • The simulations use a linear main-effects model for subdata selection even though the full data arise from nonlinear models WM1 or WM2.
  • Figure S.4 reports slope MSEs, intercept MSEs, and mean-response MSPEs as the full data size n changes with k fixed at 1000.
  • No method, including the full-data approach, dominates across the nonlinear-model results.
  • When the underlying model is incorrect, larger sample sizes do not necessarily produce more accurate results, and there is no simple answer regarding the satisfactory method.
  • The authors state that these studies show IBOSS is not always worst, without claiming that it outperforms other methods in this scenario.

S.5 Accuracy-cost tradeoff of the IBOSS method

The accuracy-cost experiments examine how IBOSS estimation error changes with computational time across sample sizes and dimensions. Increasing CPU time generally reduces MSE, sometimes sharply, while comparable-cost comparisons depend on the covariate distribution.

  • Increasing required CPU time produces lower MSE for IBOSS, demonstrating an accuracy–computational-cost tradeoff.
  • From 6.4976 seconds at k = 10^2 to 7.0839 seconds, MSE decreases from 13.57091 to an incompletely supplied value.
  • The reported results characterize IBOSS as significantly increasing estimation accuracy with little increase in computational cost.
  • The large-n, large-p experiments compare IBOSS subdata sizes from 10^3 to 10^5 with repeated UNI runs consuming similar CPU times.
  • For normal covariates, repeated UNI can yield smaller MSE than IBOSS at similar CPU times, but the difference is not very significant relative to IBOSS's advantage for heavier-tailed mixture covariates.

S.6 Comparison with the divide-and-conquer method

The divide-and-conquer comparison evaluates estimation efficiency and CPU time under several covariate distributions and dimensions. Relative efficiency depends on the distribution, while IBOSS D-OPT is especially computationally efficient for large full-data sizes.

  • Method: The divide-and-conquer estimate averages ordinary least-squares estimates computed separately on S = floor(n^1/4) subdata sets.
  • Relative estimation efficiency between IBOSS D-OPT and divide-and-conquer depends on the covariate distribution.
  • The divide-and-conquer method is better for normally distributed covariates, while the methods perform similarly for mixture-distributed covariates.
  • IBOSS D-OPT dominates divide-and-conquer when the covariate has a t1 distribution.
  • IBOSS D-OPT is more computationally efficient than divide-and-conquer, especially for large n, and CPU times do not depend on the covariate distribution.
  • Higher dimension: At p = 500, distribution-dependent estimation patterns remain similar to those at p = 50, while IBOSS D-OPT's computational advantage becomes more significant.

S.7 Performance of IBOSS with regularization method

This section evaluates IBOSS when paired with regularization methods, using simulations with fixed subdata size and varying full-data size. D-OPT IBOSS uniformly outperforms the subsampling methods UNI and LEV, especially for heavier-tailed covariate distributions.

  • Study design: IBOSS subdata are selected and then analyzed with elastic net regularization.The simulations use the glmnet R package, with tuning parameters selected by cross-validation.
  • Study design: The simulations generate full data with p = 60 across sample sizes n = 5 × 10^3, 10^4, 10^5, and 10^6.The subdata size is k = 1000, and the slope parameter has 10 nonzero elements followed by 50 zeros.
  • Evaluation: MSPEs are calculated on a new sample of size 5,000 after fitting elastic net models to subdata of size k = 1000.Results are based on 100 simulation repetitions.
  • Results: D-OPT IBOSS uniformly dominates the subsampling-based methods UNI and LEV for mean-response prediction.The relative performance is similar to that observed for parameter estimation in the main paper.
  • Results: D-OPT IBOSS has a larger advantage when the covariate distribution has a heavier tail.The same qualitative results are obtained with ridge regression, although those results are omitted.

S.8 Unequal variance

This section studies IBOSS under heteroscedastic errors by fixing the subdata size while varying the full-data size. D-OPT IBOSS again uniformly dominates UNI and LEV, while variance stabilization and weighted least squares remain outside the paper’s scope.

  • Simulation design: The heteroscedastic-error simulation uses the main-paper setup but assigns different error standard deviations.Each variance is generated from a squared exponential random variable.
  • Results: D-OPT IBOSS uniformly dominates the subsampling-based methods UNI and LEV when estimating the slope parameter.Its relative performance is similar to the parameter-estimation results in the main paper.
  • Results: The advantage of IBOSS is more significant when the covariate distribution has a heavier tail.This pattern is reported for the heteroscedastic-error simulation as well.
  • Scope: Variance-stabilizing transformations and weighted least squares are outside this paper’s scope and reserved for future work.These methods are identified as common alternatives when error terms have unequal variances.
  • Simulation design: The subdata size is fixed at k = 1000 while the full-data size n changes.MSEs for slope-parameter estimation are presented after taking base-10 logarithms of n and the MSEs.
Loading 1710.10382v1…