Abstract
Verifying whether a survey accurately represents a population usually requires an impractical number of samples due to the "curse of dimensionality." This paper proposes a clever workaround: instead of checking if the datasets perfectly match, it checks if they produce the same regression models. By introducing the SurVerify algorithm, the authors provide a way to validate survey credibility using a number of validation samples that is completely independent of the data's dimensionality.
Introduction: The Curse of Dimensionality in Survey Validation
In the social sciences, economics, and healthcare, large-scale surveys are rarely perfect representations of the underlying population due to logistical and financial constraints. Researchers need to know if they can trust the conclusions drawn from this potentially flawed survey data.
Traditionally, this is framed as a "distribution testing" problem—measuring the distance between the survey's data distribution and the true population's distribution using metrics like Total Variation or Wasserstein distance. The fatal flaw here is the curse of dimensionality: as the number of features (dimensions) in the survey grows, the number of samples required to measure this distance grows exponentially. This makes traditional validation practically impossible for modern, high-dimensional datasets.
The SurVerify Approach
The authors pivot from asking "Are these distributions identical?" to "Do these distributions yield the same conclusions for a specific task?"
- A New Metric (FDD): They introduce the Functional Distance of Distributions (FDD). Instead of comparing the data distributions directly, FDD measures the $L_2$ distance between the optimal regression model trained on the survey data and the optimal regression model trained on the true population.
- The
SurVerifyAlgorithm: To test this, the authors propose a two-phase algorithm: - Phase 1: Train a regression model (e.g., Ridge, Lasso, or Kernel regression) on the large, potentially biased survey dataset.
- Phase 2: Draw a very small, high-quality "sample-to-test" from the true population. Evaluate the survey-trained model's loss on these true samples. If the loss is close to the expected intrinsic noise, the survey is deemed "credible" for regression.
Crucially, SurVerify evaluates the model's loss rather than trying to reconstruct the true population's model. This is the secret sauce that bypasses the curse of dimensionality.
Theoretical Foundations and Sample Complexity
The most mathematically surprising result is that SurVerify requires a number of validation samples that depends only on the desired error tolerance ($\epsilon$) and confidence level ($\delta$)—it is $O(1/\epsilon^2 \log(1/\delta))$. It does not depend on the number of features ($d$) in the dataset.
The authors mathematically prove that if you tried to validate the survey by learning a second regression model from the true population and comparing the weights (reconstruction), the sample cost would scale with the dimension (e.g., $O(d/\epsilon^2)$ for Ridge). As shown in the table above, evaluating loss is fundamentally cheaper than estimating parameters.
Empirical Evaluation
- Synthetic Data: Generated with Gaussian covariates and noise, this allowed the authors to manually control the exact distance between the survey distribution and the true distribution. On this data, as the survey distribution drifted further from the true population,
SurVerifyrejected the survey using drastically fewer samples than the worst-case theoretical bound, thanks to its early-stopping mechanism. - Real-world Data (ACS_Income): The authors used the "Female" subpopulation as the survey data and the "Male" subpopulation as the true distribution.
SurVerifysuccessfully detected the distribution shift between the male and female subpopulations. Even though this dataset violated the theoretical assumption of homoskedasticity (constant noise variance), the algorithm still performed reliably, showing practical robustness.
Conclusion and Future Work
By relaxing the requirement from "perfect statistical representation" to "valid for regression," an unsolvable exponential problem becomes highly tractable. While the current theoretical proofs rely on assumptions like bounded data and exogenous noise, the authors suggest extending this framework to handle heteroskedastic noise, heavy-tailed distributions, and broader classes of machine learning models where Rademacher complexity bounds are available.
Summary updated