Improved Generalization Guarantees in Restricted Data Models
This work addresses the trade-off between privacy and accuracy in data analysis for domains like genomics, offering a method to enhance performance under specific data assumptions.
The paper tackles the problem of accuracy loss in differentially private data analysis by assuming weakly correlated distant attributes in data models, showing that it is possible to re-use privacy budget across different data portions to significantly improve accuracy without increasing overfitting risk.
Differential privacy is known to protect against threats to validity incurred due to adaptive, or exploratory, data analysis -- even when the analyst adversarially searches for a statistical estimate that diverges from the true value of the quantity of interest on the underlying population. The cost of this protection is the accuracy loss incurred by differential privacy. In this work, inspired by standard models in the genomics literature, we consider data models in which individuals are represented by a sequence of attributes with the property that where distant attributes are only weakly correlated. We show that, under this assumption, it is possible to "re-use" privacy budget on different portions of the data, significantly improving accuracy without increasing the risk of overfitting.