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

Ayoub Ajarra, Debabrota Basu
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:4735-4743, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-ajarra26a, title = { On the Hardness of Auditing Model Properties Under Updates: Complexity of Property-Preserving Updates }, author = {Ajarra, Ayoub and Basu, Debabrota}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {4735--4743}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/ajarra26a/ajarra26a.pdf}, url = {https://proceedings.mlr.press/v300/ajarra26a.html}, abstract = { 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. } }
Endnote
%0 Conference Paper %T On the Hardness of Auditing Model Properties Under Updates: Complexity of Property-Preserving Updates %A Ayoub Ajarra %A Debabrota Basu %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-ajarra26a %I PMLR %P 4735--4743 %U https://proceedings.mlr.press/v300/ajarra26a.html %V 300 %X 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.
APA
Ajarra, A. & Basu, D.. (2026). On the Hardness of Auditing Model Properties Under Updates: Complexity of Property-Preserving Updates . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:4735-4743 Available from https://proceedings.mlr.press/v300/ajarra26a.html.

Related Material