Optimal Variance and Covariance Estimation Under Differential Privacy in the Add-Remove Model and Beyond

Shokichi Takakura, Seng Pei Liew, Satoshi Hasegawa
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:595-603, 2026.

Abstract

In this paper, we study the problem of estimating the variance and covariance of datasets under differential privacy in the add-remove model. While estimation in the swap model has been extensively studied in the literature, the add-remove model remains less explored and more challenging, as the dataset size must also be kept private. To address this issue, we develop efficient mechanisms for variance and covariance estimation based on the \emph{Bézier mechanism}, a novel moment-release framework that leverages Bernstein bases. We prove that our proposed mechanisms are minimax optimal in the high-privacy regime by establishing new minimax lower bounds. Moreover, beyond worst-case scenarios, we analyze instance-wise utility and show that the B{é}zier-based estimator consistently achieves better utility compared to alternative mechanisms. Finally, we demonstrate the effectiveness of the B{é}zier mechanism beyond variance and covariance estimation, showcasing its applicability to other statistical tasks.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-takakura26b, title = { Optimal Variance and Covariance Estimation Under Differential Privacy in the Add-Remove Model and Beyond }, author = {Takakura, Shokichi and Liew, Seng Pei and Hasegawa, Satoshi}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {595--603}, 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/takakura26b/takakura26b.pdf}, url = {https://proceedings.mlr.press/v300/takakura26b.html}, abstract = { In this paper, we study the problem of estimating the variance and covariance of datasets under differential privacy in the add-remove model. While estimation in the swap model has been extensively studied in the literature, the add-remove model remains less explored and more challenging, as the dataset size must also be kept private. To address this issue, we develop efficient mechanisms for variance and covariance estimation based on the \emph{Bézier mechanism}, a novel moment-release framework that leverages Bernstein bases. We prove that our proposed mechanisms are minimax optimal in the high-privacy regime by establishing new minimax lower bounds. Moreover, beyond worst-case scenarios, we analyze instance-wise utility and show that the B{é}zier-based estimator consistently achieves better utility compared to alternative mechanisms. Finally, we demonstrate the effectiveness of the B{é}zier mechanism beyond variance and covariance estimation, showcasing its applicability to other statistical tasks. } }
Endnote
%0 Conference Paper %T Optimal Variance and Covariance Estimation Under Differential Privacy in the Add-Remove Model and Beyond %A Shokichi Takakura %A Seng Pei Liew %A Satoshi Hasegawa %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-takakura26b %I PMLR %P 595--603 %U https://proceedings.mlr.press/v300/takakura26b.html %V 300 %X In this paper, we study the problem of estimating the variance and covariance of datasets under differential privacy in the add-remove model. While estimation in the swap model has been extensively studied in the literature, the add-remove model remains less explored and more challenging, as the dataset size must also be kept private. To address this issue, we develop efficient mechanisms for variance and covariance estimation based on the \emph{Bézier mechanism}, a novel moment-release framework that leverages Bernstein bases. We prove that our proposed mechanisms are minimax optimal in the high-privacy regime by establishing new minimax lower bounds. Moreover, beyond worst-case scenarios, we analyze instance-wise utility and show that the B{é}zier-based estimator consistently achieves better utility compared to alternative mechanisms. Finally, we demonstrate the effectiveness of the B{é}zier mechanism beyond variance and covariance estimation, showcasing its applicability to other statistical tasks.
APA
Takakura, S., Liew, S.P. & Hasegawa, S.. (2026). Optimal Variance and Covariance Estimation Under Differential Privacy in the Add-Remove Model and Beyond . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:595-603 Available from https://proceedings.mlr.press/v300/takakura26b.html.

Related Material