Differentially Private Algorithms for the Stochastic Compositional Optimization Problem

Zhuanghua Liu, Weida Li, Xiaokui Xiao, Bryan Kian Hsiang Low
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:1279-1287, 2026.

Abstract

In this paper, we study the stochastic compositional optimization problem under the constraint of differential privacy. We first introduce two private algorithms: noisy stochastic compositional gradient descent (NSCGD) and the noisy stochastically corrected stochastic compositional gradient (NSCSC) method. We use the algorithmic stability approach to establish bounds on the excess population loss of both methods in strongly convex and convex cases. However, these methods require gradient computations that are super-linear in the number of training samples. To address this, we propose a class of output perturbation-based randomized algorithms by exploiting the stability of the compositional empirical risk minimizer under the privacy constraint. These algorithms achieve comparable excess population risk with significantly reduced gradient computations.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-liu26b, title = { Differentially Private Algorithms for the Stochastic Compositional Optimization Problem }, author = {Liu, Zhuanghua and Li, Weida and Xiao, Xiaokui and Low, Bryan Kian Hsiang}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {1279--1287}, 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/liu26b/liu26b.pdf}, url = {https://proceedings.mlr.press/v300/liu26b.html}, abstract = { In this paper, we study the stochastic compositional optimization problem under the constraint of differential privacy. We first introduce two private algorithms: noisy stochastic compositional gradient descent (NSCGD) and the noisy stochastically corrected stochastic compositional gradient (NSCSC) method. We use the algorithmic stability approach to establish bounds on the excess population loss of both methods in strongly convex and convex cases. However, these methods require gradient computations that are super-linear in the number of training samples. To address this, we propose a class of output perturbation-based randomized algorithms by exploiting the stability of the compositional empirical risk minimizer under the privacy constraint. These algorithms achieve comparable excess population risk with significantly reduced gradient computations. } }
Endnote
%0 Conference Paper %T Differentially Private Algorithms for the Stochastic Compositional Optimization Problem %A Zhuanghua Liu %A Weida Li %A Xiaokui Xiao %A Bryan Kian Hsiang Low %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-liu26b %I PMLR %P 1279--1287 %U https://proceedings.mlr.press/v300/liu26b.html %V 300 %X In this paper, we study the stochastic compositional optimization problem under the constraint of differential privacy. We first introduce two private algorithms: noisy stochastic compositional gradient descent (NSCGD) and the noisy stochastically corrected stochastic compositional gradient (NSCSC) method. We use the algorithmic stability approach to establish bounds on the excess population loss of both methods in strongly convex and convex cases. However, these methods require gradient computations that are super-linear in the number of training samples. To address this, we propose a class of output perturbation-based randomized algorithms by exploiting the stability of the compositional empirical risk minimizer under the privacy constraint. These algorithms achieve comparable excess population risk with significantly reduced gradient computations.
APA
Liu, Z., Li, W., Xiao, X. & Low, B.K.H.. (2026). Differentially Private Algorithms for the Stochastic Compositional Optimization Problem . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:1279-1287 Available from https://proceedings.mlr.press/v300/liu26b.html.

Related Material