On the Hardness of Auditing Model Properties Under Updates: Complexity of Property-Preserving Updates

As machine learning becomes deeply embedded in societal infrastructure, assessing the risks posed by these models has grown increasingly critical. Real-world deployment further complicates this assessment: model owners may apply strategic updates in response to dynamic environments (e.g., financial markets), potentially undermining key guarantees. We formalize this setting and address two goals: (i) accurately estimating a target auditing property-- such as group fairness-- using a minimal number of labeled samples; and (ii) characterizing the complexity of strategic updates by identifying the subset of admissible updates that preserve the property. To this end, we propose a generic algorithmic framework for efficient PAC auditing, powered by an Empirical Property Optimization (EPO) oracle. For statistical parity, we establish distribution-free audit bounds characterized by the SP dimension, a new combinatorial measure that captures the complexity of admissible strategic updates. Finally, we show that our framework naturally extends to other properties, including prediction error and robust risk.