# Testing Credibility of Public and Private Surveys through the Lens of Regression

arXiv: https://arxiv.org/abs/2410.05458 · HTML: https://mlsanity.com/paper/2410.05458/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 68 references that are in the map.
- First posted on arXiv 7 Oct 2024.

## Builds on (most cited first, 17 of 17)

- [Retiring Adult: New Datasets for Fair Machine Learning](https://mlsanity.com/paper/2108.04884/) (2021)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12](https://mlsanity.com/paper/1709.02753/) (2017)
- [Local Differential Privacy and Its Applications: A Comprehensive Survey](https://mlsanity.com/paper/2008.03686/) (2020)
- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Differentially Private Simple Linear Regression](https://mlsanity.com/paper/2007.05157/) (2020)
- [Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning](https://mlsanity.com/paper/2303.07152/) (2023)
- [The Impact of the U.S. Census Disclosure Avoidance System on Redistricting and Voting Rights Analysis](https://mlsanity.com/paper/2105.14197/) (2021)
- [Easy Differentially Private Linear Regression](https://mlsanity.com/paper/2208.07353/) (2022)
- [On the Rademacher Complexity of Linear Hypothesis Sets](https://mlsanity.com/paper/2007.11045/) (2020)
- [Sharp Concentration Results for Heavy-Tailed Distributions](https://mlsanity.com/paper/2003.13819/) (2020)
- [Optimal Testing of Discrete Distributions with High Probability](https://mlsanity.com/paper/2009.06540/) (2020)
- [Which Distribution Distances are Sublinearly Testable?](https://mlsanity.com/paper/1708.00002/) (2017)
- [Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning](https://mlsanity.com/paper/1911.07357/) (2019)
- [Marich: A Query-efficient Distributionally Equivalent Model Extraction Attack using Public Data](https://mlsanity.com/paper/2302.08466/) (2023)
- [Stochastic Online Linear Regression: the Forward Algorithm to Replace Ridge](https://mlsanity.com/paper/2111.01602/) (2021)

## Abstract (arXiv)

Testing whether a sample survey is a credible representation of the population is an important question to ensure the validity of any downstream research. While this problem, in general, does not have an efficient solution, one might take a task-based approach and aim to understand whether a certain data analysis tool, like linear regression, would yield similar answers both on the population and the sample survey. In this paper, we design an algorithm to test the credibility of a sample survey in terms of linear regression. In other words, we design an algorithm that can certify if a sample survey is good enough to guarantee the correctness of data analysis done using linear regression tools. Nowadays, one is naturally concerned about data privacy in surveys. Thus, we further test the credibility of surveys published in a differentially private manner. Specifically, we focus on Local Differential Privacy (LDP), which is a standard technique to ensure privacy in surveys where the survey participants might not trust the aggregator. We extend our algorithm to work even when the data analysis has been done using surveys with LDP. In the process, we also propose an algorithm that learns with high probability the guarantees a linear regression model on a survey published with LDP. Our algorithm also serves as a mechanism to learn linear regression models from data corrupted with noise coming from any subexponential distribution. We prove that it achieves the optimal estimation error bound for ℓ1 linear regression, which might be of broader interest. We prove the theoretical correctness of our algorithms while trying to reduce the sample complexity for both public and private surveys. We also numerically demonstrate the performance of our algorithms on real and synthetic datasets.