Auditing Fairness under Model Updates: Fundamental Complexity and Property-Preserving Updates
This work addresses the challenge of reliably auditing fairness in real-world deployments where models are updated, which is crucial for ensuring bias-free AI in societal applications, though it is incremental in extending auditing methods to dynamic settings.
The paper tackles the problem of auditing group fairness in machine learning models that are adaptively updated, establishing fundamental complexity bounds and proposing a framework for efficient auditing with minimal labeled samples, achieving distribution-free bounds characterized by a novel SP dimension measure.
As machine learning models become increasingly embedded in societal infrastructure, auditing them for bias is of growing importance. However, in real-world deployments, auditing is complicated by the fact that model owners may adaptively update their models in response to changing environments, such as financial markets. These updates can alter the underlying model class while preserving certain properties of interest, raising fundamental questions about what can be reliably audited under such shifts. In this work, we study group fairness auditing under arbitrary updates. We consider general shifts that modify the pre-audit model class while maintaining invariance of the audited property. Our goals are two-fold: (i) to characterize the information complexity of allowable updates, by identifying which strategic changes preserve the property under audit; and (ii) to efficiently estimate auditing properties, such as group fairness, using a minimal number of labeled samples. We propose a generic framework for PAC auditing based on an Empirical Property Optimization (EPO) oracle. For statistical parity, we establish distribution-free auditing bounds characterized by the SP dimension, a novel combinatorial measure that captures the complexity of admissible strategic updates. Finally, we demonstrate that our framework naturally extends to other auditing objectives, including prediction error and robust risk.