PaperlayerView exact revision on arXiv

Source-linked AI summary

Subdata Selection for Measurement-Constrained Linear Regression under Model Misspecification

Yundi Kong, Min Yang, Ping-Shou Zhong

arXiv:2610.19351v1stat.MEstat.ML

TL;DR

When responses are costly, selecting which units to measure is difficult because many existing subsampling criteria assume available responses or correct model specification. ELOS chooses a subset using a covariate-only expected-loss criterion, and the paper reports competitive or improved predictive performance across settings. Its misspecification guarantee averages over directions rather than optimizing for every departure.

  • Problem

    Measurement-constrained selection must choose units from available covariates before responses are collected, while many existing methods assume full responses or correct model specification.

    Source: §1 · pp. 1–2

  • Method

    ELOS minimizes a prediction-oriented expected-loss criterion that reduces to an A-optimality-type criterion using covariates without responses at selection.

    Source: §1 · p. 2, §3.2 · p. 5

  • Results

    ELOS achieves improved or comparable predictive performance with competitive computational efficiency across settings relative to SRS, leverage-score sampling, IBOSS, LowCon, and coreset methods.

    Source: §1 · p. 2

  • Takeaways & Limitations

    ELOS provides a response-free selection approach for settings where outcomes are costly to collect and prediction is the goal.

    Source: §5 · p. 8

    Under misspecification, the criterion is average-case over uniformly distributed directions, not optimal for every fixed or structured departure; the theory also assumes fixed design and homoscedastic errors.

    Source: §5 · p. 8

Abstract

from arXiv · show

In many modern applications, obtaining response variables is costly, time-consuming, or technically challenging, making it impractical to measure outcomes for all available units. In such settings, covariates may be available for a large pool of candidates, but responses can only be collected for a small, carefully selected subset, making the choice of which units to measure a consequential decision. Most existing subsampling methods are developed for massive datasets, emphasizing the trade-off between statistical accuracy and computational cost, and typically relying on the assumption of a correctly specified model. These features limit their suitability in measurement-constrained settings, where statistical efficiency is paramount and model misspecification is often unavoidable. To address these challenges, we develop a new subset selection framework for linear regression that accommodates potential model misspecification. The proposed approach targets predictive expected loss and yields an A-optimality-type criterion that depends only on covariate information, requiring no response observations at the selection stage. We refer to this method as Expected Loss Optimal Selection (ELOS). By focusing on predictive risk rather than model-based optimality, ELOS remains well-defined and robust under misspecification. Simulation studies and real data applications demonstrate that ELOS achieves strong predictive performance and compares favorably with existing methods across a range of scenarios.

1 INTRODUCTION

Measurement-constrained regression selects from a fixed pool of covariates before collecting responses, unlike much existing subsampling work that assumes the full response vector is available. ELOS addresses this setting under possible model misspecification by targeting predictive expected loss with a response-free A-optimality-type criterion.

1 INTRODUCTION

  • Selection is made from a fixed candidate pool using covariates before responses are collected, unlike classical designs that can specify experimental conditions freely.Responses are measured only for the selected observations.Source: §1 · p. 1
  • Most existing subsampling methods assume the full response vector is available and balance statistical accuracy against computational cost, often using model-based criteria.Such methods commonly rely on Fisher information or asymptotic variance.Source: §1 · p. 1
  • Model misspecification can make parameter-estimation criteria misaligned with prediction, while standard coresets typically require responses when forming the subset.LowCon addresses misspecification through a design-based approach, while coreset methods approximate empirical loss.Source: §1 · p. 2
  • ELOS derives a response-free, prediction-oriented A-optimality-type criterion for measurement-constrained selection and reports improved or comparable predictive performance with competitive computational efficiency across settings.The reported comparisons include SRS, leverage-score sampling, IBOSS, LowCon, and coreset methods.Source: §1 · p. 2

2 NOTATIONS AND RELATED WORK IN SUBDATA SELECTION

The section sets up weighted least squares for subset-based estimation and reviews design-based and loss-approximation approaches. It then motivates evaluating selections by expected prediction loss, which connects those perspectives while accounting for both bias and variance.

2.1 Problem setup and notation

  • Weighted least squares represents subset-based estimation by assigning nonnegative weights to observations, with fitted values and residual loss defined through its projection matrix.The estimator is (X⊤WX)^−1X⊤Wy.Source: §2.1 · p. 3

2.2 Optimal sampling selection

  • Probabilistic subsampling chooses inclusion probabilities to improve estimator efficiency, whereas deterministic designs such as IBOSS select covariates to approximate information-optimal designs.IBOSS uses only X and aims for near full-data efficiency under the linear model when r/n is small.Source: §2.2 · p. 3

2.3 Coreset method

  • Coresets use weighted subsets to approximate full-data least-squares loss, but the strongest guarantees and many effective constructions are response-aware.A response-agnostic construction has worst-case approximation ratio O(n/r) and no implementation algorithm is provided.Source: §2.3 · pp. 3–4

2.4 Connection to optimal subsampling and coreset methods

  • The framework evaluates a sparse-weight estimator by expected prediction loss, bridging coreset loss approximation and subsampling efficiency while capturing bias and variance.The criterion is defined using the projection matrix associated with the weighted or subset-based estimator.Source: §2.4 · p. 4

3 MAIN RESULTS

The theoretical results derive expected prediction loss for fixed-design linear regression under correct specification and misspecification. Averaging over misspecification directions yields an A-optimality-type, covariate-only criterion, which ELOS targets through approximate optimization.

3.1 Under correctly specified linear model

  • Under correct specification, minimizing expected full-design prediction loss is equivalent to minimizing an A-optimal subset-selection criterion.The result assumes a fixed design, homoscedastic errors, a subset of size r, and rank(∆X)=d.Source: §3.1 · p. 4

3.2 Under mis-specified linear model

  • Under misspecification, the expected loss depends on an unknown direction, so the method averages loss over directions uniformly distributed on the unit sphere.The misspecification term is assumed orthogonal to X and bounded in average squared magnitude.Source: §3.2 · p. 5
  • The averaged misspecification criterion reduces to an A-optimality-type objective depending only on X, and the selection rule is invariant to σ2 and τ2.Theorem 3 gives an average-case result under a uniform, rotation-invariant distribution on fixed-norm misspecification directions.Source: §3.2 · p. 5

3.3 ELOS: expected loss optimal selection

  • ELOS names the expected-loss criterion itself; IBOSS+ is used as a scalable approximate optimizer because finding the optimal subset is NP-hard.The implementation uses IBOSS+ to approximately minimize the expected prediction loss.Source: §3.3 · p. 6

4 NUMERICAL EXPERIMENTS

The experiments compare predictive performance and selection runtime under simulation and real-data measurement constraints. ELOS performs comparably to or better than IBOSS in simulations and achieves the lowest reported prediction error on both real datasets.

4 NUMERICAL EXPERIMENTS

  • The experiments compare SRS, Coreset, Leverage, IBOSS, MCG, LowCon, and ELOS using full-data OLS as the benchmark; Coreset uses responses and is not measurement-constrained.Selection runtime includes method-specific preprocessing.Source: §4 · p. 6

4.1 Simulation study

  • Across the heavy-tailed simulation settings, ELOS performs comparably to or better than IBOSS, and both have lower REdiff and variability than the other competitors.The ordering changes little across the misspecification levels examined; as subdata size increases, REdiff falls and method gaps narrow.Source: §4.1 · p. 6, Figure 1 · p. 7

4.2 Real-data experiments

  • Real-data stability is assessed over 100 residual-bootstrap replicates, but residual resampling may underrepresent structured misspecification because it does not preserve residual-covariate dependence.The chemical-sensors and YearPredictionMSD experiments use measurement budgets of 1,000 and 5,000, and 1,000 and 10,000, respectively.Source: §4.2 · pp. 6–7, §4.2.1 · p. 7, §4.2.2 · p. 7

4.2.1 Chemical sensors data

  • ELOS achieves the smallest RE for the chemical sensors data at both measurement budgets, with slower selection than SRS, Leverage, and IBOSS but faster selection than Coreset, LowCon, and MCG.The linear model is treated as a working approximation because the sensor-response relationship may involve nonlinear dynamics and interactions.Source: Figure 2 · p. 7, §4.2.1 · p. 7

4.2.2 Million song release year prediction

  • Using all 90 predictors, ELOS attains the smallest RE on YearPredictionMSD at both measurement budgets.The linear model is treated as a misspecified working approximation for this task.Source: Figure 3 · p. 8, §4.2.2 · p. 8

5 DISCUSSION

ELOS offers a response-free, prediction-oriented approach that generally performs best or near-best among response-free baselines while scaling to large candidate pools. Its guarantee and theory have boundaries, including average-case treatment of misspecification directions and fixed-design, homoscedastic assumptions.

5 DISCUSSION

  • Among response-free baselines, ELOS generally achieves the best or near-best predictive accuracy while remaining scalable to large candidate pools.The discussion identifies clinical trials, environmental monitoring, precision agriculture, and survey design as potential resource-constrained applications.Source: §5 · p. 8
  • The misspecification guarantee averages over directions on the unit sphere; it does not establish optimality for every fixed or structured departure.The unknown misspecification direction is unavailable at subset selection.Source: §5 · p. 8
  • Performance may depend on how deviations from linearity are distributed, and strong asymmetry may make limited pilot responses useful for guiding later selection.The discussion proposes adaptive procedures that integrate limited response information as future work.Source: §5 · p. 8
  • The theory assumes fixed design and homoscedastic errors; heteroscedasticity requires a new expected-loss derivation.The residual bootstrap also does not preserve residual-covariate dependence, which may limit its capture of structured misspecification.Source: §5 · p. 8
  • The exact response-free reduction relies on linear least-squares projection; nonlinear-in-parameters extensions require new theory and may introduce approximation error.The discussion names generalized linear and nonparametric regression as directions for future work.Source: §5 · p. 8

A PROOFS FOR SECTION 3

The proofs derive expected loss for subset-based regression, relate it to the A-optimality-type criterion, and establish the misspecification result by averaging over directions. The argument uses projection and trace identities under stated rank conditions.

Proof of Theorem 1

  • Under correct specification, the proof substitutes the linear model into the loss and uses the zero-mean error and vanishing projection bias to reduce expected loss to its variance term.The proof assumes rank(X) = rank(∆X) = d so that X⊤∆X is invertible.Source: Proof of Theorem 1 · p. 11

Proof of Theorem 2

  • Theorem 2 follows from the trace identity linking the residual projection loss to n − 2d + ΨA(∆).The proof invokes the identity established in the proof of Theorem 1.Source: Proof of Theorem 2 · p. 12

Proof of Theorem 3

  • To establish Theorem 3, the proof takes expectation of the quadratic term over a uniformly distributed on the unit sphere in R^(n-d); rotational invariance applies, and the cross-trace term is zero.Source: Proof of Theorem 3 · p. 12

B.1 Simulation study with t-distributed covariates

Under t-distributed covariates, ELOS achieves REdiff comparable to or better than IBOSS across settings; under normal covariates, its REdiff is generally small and concentrated. The section also reports MCG optimization diagnostics.

B.1 Simulation study with t-distributed covariates

  • The t-covariate experiment uses multivariate t(5) covariates with Σ = 5I_b + 5J_b; its other simulation components follow Section 4.1.The same (n, r, τ) combinations are used for the MCG comparison.Source: §B.1 · pp. 13–14
  • ELOS achieves REdiff comparable to or better than IBOSS across all t-distributed settings, while SRS is fastest and ELOS scales more favorably than Coreset as r increases.MCG and LowCon have substantially higher runtimes; Coreset is faster at small r, but its runtime grows substantially with r.Source: §B.1 · p. 13

B.2 Simulation study with normal distributed covariates

  • ELOS generally has small, relatively concentrated REdiff distributions under normal covariates, especially for smaller subsets; Coreset also performs strongly in some settings but takes longer to select.Figure 4 summarizes REdiff variability across 100 replications at each (τ, r) setting.Source: §B.2 · p. 14, Figure 4 · p. 15

C DIAGNOSTIC TABLES FOR MCG

  • MCG diagnostic tables report outer iterations, iteration-cap hits, backtracking and projection counts, and final relative improvement across simulation settings.These quantities provide information about MCG's computational behavior.Source: C DIAGNOSTIC TABLES FOR MCG · p. 15

D ADDITIONAL DETAILS FOR REAL-DATA EXPERIMENTS

The real-data evaluation uses centered residual resampling to generate pseudo-responses, while noting that this procedure does not preserve residual–covariate dependence. On the Chemical Sensor design, ELOS has the smallest test RE at both reported subset sizes.

D.1 Residual bootstrap procedure

  • The residual bootstrap fits full-data OLS, centers and resamples residuals, then adds the resampled residuals to fitted values to form pseudo-responses.The paper uses this procedure to generate pseudo-responses for real-data evaluation.Source: §D.1 · pp. 15–16
  • Independent residual resampling does not preserve residual–covariate dependence, so the bootstrap may understate misspecification carried by that dependence.The authors characterize the procedure as a data-driven alternative to committing to one parametric misspecification scenario.Source: §D.1 · pp. 16–17

E.1 Chemical Sensor Data

  • ELOS has the smallest test RE at r = 1,000 and r = 5,000 on the Chemical Sensor design, with train and test RE patterns consistent across methods and subset sizes.The held-out test set contains 10,000 observations; relative train–test differences are typically small.Source: §E.1 · p. 17
  • The Chemical Sensor analysis uses 4,188,261 observations and 14 covariates plus an intercept after preprocessing, treating the linear model as a working approximation.The held-out evaluation uses a fixed test set of 10,000 observations.Source: §E.1 · p. 17

E.2 Million Song Dataset

On YearPredictionMSD, ELOS attains the smallest test REdiff in higher-dimensional settings, with training and test results close across methods. The section also describes response-dependent screening and the fixed ELOS implementation choices.

E.2 Million Song Dataset

  • YearPredictionMSD contains 515,345 tracks with 90 acoustic descriptors, and its linear regression model is a deliberately restricted working approximation.The dataset is presented as a large-scale setting for evaluating selection under possible misspecification.Source: §E.2 · pp. 17–18
  • For k = 30 and 60, Figure 5 uses response-dependent Pearson screening to define common reduced predictor sets; k = 90 uses all original predictors without that screening.The reduced panels support conditional dimensionality and computational-scaling comparisons.Source: §E.2 · p. 18, Figure 5 · p. 18
  • Train and test RE values are close across methods, and ELOS attains the smallest test REdiff in the higher-dimensional YearPredictionMSD settings.Table 8 reports training and test REdiff over 50 replicates.Source: §E.2 · p. 18, Table 8 · p. 19

F IMPLEMENTATION AND REPRODUCIBILITY DETAILS

  • Method-specific settings were fixed in advance across simulation and real-data experiments, with no dataset-specific tuning; the section records implementation choices for reproducibility.The choices include initialization, tuning parameters, stopping rules, randomized rounding, and duplicate handling.Source: F IMPLEMENTATION AND REPRODUCIBILITY… · p. 19

F.1 Implementation of ELOS

  • ELOS applies IBOSS+ block exchange to the left singular-vector matrix from the compact SVD of the full design matrix.The initial subset uses IBOSS; the procedure performs d exchange iterations and returns exactly r distinct observations.Source: §F.1 · p. 20

F.2 Implementation of Competing Methods

The experiments use distinct implementations for the competing selection methods and fixed random seeds. The complexity discussion gives ELOS computational and working-memory bounds under the stated large-data regime.

F.2 Implementation of Competing Methods

  • SRS samples uniformly without replacement, leverage sampling uses exact scores with replacement and inverse-probability weighting, and IBOSS selects predictor-wise extremes without duplicates.IBOSS excludes the intercept from extreme-value ranking.Source: §F.2 · p. 20
  • Coreset uses the response in its augmented design, so this implementation is a prediction-oriented reference rather than a measurement-constrained method; MCG uses projected-gradient optimization.The MCG implementation uses capped line searches and stops at a relative-improvement threshold or iteration limit.Source: §F.2 · p. 20
  • LowCon constructs randomized Latin hypercube designs and matches points to distinct candidate observations; relaxed-weight sampling instead uses Bernoulli draws, so its realized subset size may differ from r.LowCon searches additional neighbors when its initial candidates have already been selected.Source: §F.2 · pp. 20–21

F.3 Random Seeds and Computational Environment

  • Seeds were fixed across configurations, and reported ELOS runtime includes the compact SVD, IBOSS initialization, and block-exchange refinement.The experiments ran in Julia on a single-threaded CPU environment, with parallelization only across independent replications.Source: §F.3 · p. 21

G.1 Complexity of the Proposed ELOS Procedure

  • ELOS combines compact SVD, IBOSS initialization, and exchange for O(nd2 + nd3 + d4) operations; for fixed low or moderate d, it scales linearly with n.Its working memory is O(nd + n + r + d2).Source: §G.1 · pp. 21–22
  • Table 9 compares computational and working-memory complexities under n ≫ d and d ≤ r ≤ n, with some complete bounds derived from algorithms and implementations.The memory comparison excludes storage of the original input data.Source: Table 9 · p. 22

G.2 Complexity Comparison with Existing Methods

The complexity comparison reports computational and working-memory bounds under the large-data regime. The ELOS ablation separates the selection criterion from its optimizer and uses paired comparisons on shared data and a shared decomposition.

G.2 Complexity Comparison with Existing Methods

  • Table 9 compares computational and working-memory complexities of ELOS with IBOSS+ and competing methods under n ≫ d and d ≤ r ≤ n.Some bounds are derived from published algorithms and the study implementation when the original reference does not state them.Source: §G.2 · p. 22

H ABLATION ON THE OPTIMIZATION PROCEDURE

  • ELOS names the selection criterion, while IBOSS+ is the approximate optimizer used to minimize it in the main experiments.The ablation replaces IBOSS+ with a first-order A-optimal design procedure while keeping the ELOS objective and evaluation procedure unchanged.Source: H ABLATION ON THE OPTIMIZATION PROCEDURE · p. 23

H.1 Experimental Setup

  • The optimizer comparison pairs procedures on the same generated design and response, with one shared singular value decomposition per replication.The experimental setup uses 15 non-intercept covariates from a multivariate t distribution with five degrees of freedom, then adds an intercept.Source: §H.1 · p. 23

H.2 Optimization Procedures

The ablation finds similar predictive errors for two optimizers of the ELOS criterion, especially at the larger measurement budget, while IBOSS+ is substantially faster. Sensor-data results likewise report lower mean relative error and selection time for IBOSS+.

H.2 Optimization Procedures

  • At r = 1000, the absolute paired relative-error differences between the first-order procedure and IBOSS+ are no larger than 0.0006 across n and τ.The table reports relative-error means and standard deviations over paired replications.Source: §H.2 · pp. 23–24, Table 10 · p. 24
  • For r = 100, mean relative error is lower with IBOSS+ at n = 105 and with the first-order implementation at n = 106, providing no evidence of a uniformly superior optimizer.The procedures operate on continuous design weights in the first-order method, which retains the r observations with the largest positive weights; its iteration-limited results are not exact continuous-design solutions.Source: §H.2 · pp. 23–24
  • The first-order procedure takes approximately 26–28 times as long as IBOSS+ at r = 100, and 33–601 seconds versus 0.14–1.47 seconds at r = 1000.Its formal convergence criterion was not reached within the iteration budget in any examined configuration.Source: §H.2 · p. 24

H.3 Optimizer Ablation on the Sensor Data

  • On Sensor data, both optimizers’ errors are of the same order, especially for larger subsets, while IBOSS+ has lower mean relative error and substantially less selection time.Both optimizers show decreasing prediction error as subset size increases.Source: §H.3 · p. 24

I DIAGNOSTIC EXPERIMENTS UNDER ALTERNATIVE MISSPECIFICATION TERMS

The diagnostic compares ELOS and Coreset under several nonlinear misspecification terms. ELOS has lower mean relative error under sinusoidal, monotone radial, and interaction departures, but Coreset performs better under a localized threshold departure.

I DIAGNOSTIC EXPERIMENTS UNDER ALTERNATIVE MISSPECIFICATION TERMS

  • The diagnostic holds random seeds and data-generation settings fixed while changing the nonlinear departure, using 20 repetitions per configuration.The setting uses multivariate t covariates, d = 15, σ = 1, and τ = 3.Source: I DIAGNOSTIC EXPERIMENTS UNDER… · p. 25
  • Under sinusoidal, monotone radial, and interaction departures, ELOS has lower mean relative error than Coreset for every combination of n and r.The table reports mean relative-error differences for alternative misspecification terms at τ = 3, averaged over 20 repetitions.Source: I DIAGNOSTIC EXPERIMENTS UNDER… · pp. 26–27, Table 14 · p. 26
  • Under the localized, discontinuous threshold departure, Coreset outperforms ELOS in all four configurations.The authors suggest that Coreset may adapt to the abrupt conditional-mean change because it uses responses during subset construction; ELOS selects using covariates alone.Source: I DIAGNOSTIC EXPERIMENTS UNDER… · p. 27
  • The threshold result marks a scope boundary: ELOS’s average-case guarantee does not ensure optimality for every fixed or structured misspecification direction.The authors describe ELOS’s strong performance as stable across several distinct smooth nonlinear departures.Source: I DIAGNOSTIC EXPERIMENTS UNDER… · p. 27
Loading 2610.19351v1…