Introduces a formal framework for auditing group fairness when model owners can strategically and adaptively update their models, characterizing which updates are allowed as long as the audited property (e.g., fairness) is preserved.
Proposes a general PAC auditing procedure based on an Empirical Property Optimization (EPO) oracle, enabling efficient estimation of fairness properties using a minimal number of labeled samples even under arbitrary admissible updates.
Defines the SP dimension, a new combinatorial complexity measure that governs distribution-free sample complexity for auditing statistical parity, and shows that the same framework extends to other objectives such as prediction error and robust risk.