Differentially Private Non-convex Distributionally Robust Optimization

Difei Xu; Meng Ding; Zebin Ma; Huanyi Xie; Youming Tao; Aicha Slaitane; Di Wang

cs.LGFeb 18, 2026

Differentially Private Non-convex Distributionally Robust Optimization

Authors: Difei Xu, Meng Ding, Zebin Ma, Huanyi Xie, Youming Tao, Aicha Slaitane, Di Wang

Organizations: Provable Responsible AI and Data Analytics (PRADA) Lab · King Abdullah University of Science and Technology · State University of New York at Buffalo · Technische Universität Berlin

Abstract

Real-world deployments routinely face distribution shifts, group imbalances, and adversarial perturbations, under which the traditional Empirical Risk Minimization (ERM) framework can degrade severely. Distributionally Robust Optimization (DRO) addresses this issue by optimizing the worst-case expected loss over an uncertainty set of distributions, offering a principled approach to robustness. Meanwhile, as training data in DRO always involves sensitive information, safeguarding it against leakage under Differential Privacy (DP) is essential. In contrast to classical DP-ERM, DP-DRO has received much less attention due to its minimax optimization structure with uncertainty constraint. To bridge the gap, we provide a comprehensive study of DP-(finite-sum)-DRO with $ψ$ -divergence and non-convex loss. First, we study DRO with general $ψ$ -divergence by reformulating it as a minimization problem, and develop a novel $(\varepsilon, δ)$ -DP optimization method, called DP Double-Spider, tailored to this structure. Under mild assumptions, we show that it achieves a utility bound of $\mathcal{O}(\frac{1}{\sqrt{n}}+ (\frac{\sqrt{d \log (1/δ)}}{n \varepsilon})^{2/3})$ in terms of the gradient norm, where $n$ denotes the data size and $d$ denotes the model dimension. We further improve the utility rate for specific divergences. In particular, for DP-DRO with KL-divergence, by transforming the problem into a compositional finite-sum optimization problem, we develop a DP Recursive-Spider method and show that it achieves a utility bound of $\mathcal{O}((\frac{\sqrt{d \log(1/δ)}}{n\varepsilon})^{2/3} )$ , matching the best-known result for non-convex DP-ERM. Experimentally, we demonstrate that our proposed methods outperform existing approaches for DP minimax optimization.

Figures & tables

Divergence	$\psi(t)$	$\psi^{*}(t)$
$\chi^{2}$	$\frac{1}{2}(t-1)^{2}$	$-1+\frac{1}{4}(t+2)^{2}$
KL-regularized CVaR	$\mathbb{I}_{[0,\alpha^{-1})}+t\log(t)-t+1,\alpha\in(0,1)$	$\min(e^{t},\alpha^{-1}(1+t+\log(\alpha)))-1$
Cressie-Read	$\frac{t^{k}-tk+k-1}{k(k-1)},k\in\mathbb{R}$	$\frac{1}{k}\left(((k-1)t+1)_{+}^{\frac{k}{k-1}}-1\right)$

Table 1: Common divergences with

L

-smooth conjugates.

Algorithm	MIA AUC (Mean $\pm$ Std)
Algorithm	$\varepsilon=0.1$	$\varepsilon=1$	$\varepsilon=3$	$\varepsilon=5$	$\varepsilon=8$	$\varepsilon=10$
DP Double SPIDER	0.9719 $\pm$ 0.0059	0.9723 $\pm$ 0.0045	0.9717 $\pm$ 0.0025	0.9723 $\pm$ 0.0021	0.9724 $\pm$ 0.0033	0.9715 $\pm$ 0.0022
DP Recursive SPIDER	0.8234 $\pm$ 0.0127	0.7932 $\pm$ 0.0072	0.7958 $\pm$ 0.0240	0.8014 $\pm$ 0.0383	0.8001 $\pm$ 0.0302	0.7825 $\pm$ 0.0149

Table 2: Membership Inference Attack (MIA) results under different privacy budgets. Lower AUC indicates better privacy. Results are reported as mean

\pm

standard deviation over 5 runs. Bold values indicate best (lowest) privacy leakage for each privacy budget. DP Recursive SPIDER consistently achieves lower MIA AUC compared to DP Double SPIDER across all epsilon values.

Dataset	CIFAR10-ST				MNIST-ST				Fashion-MNIST				CelebA
Dataset	SGDA	Private Diff	DP DS	RS DRO	SGDA	Private Diff	DP DS	RS DRO	SGDA	Private Diff	DP DS	RS DRO	SGDA	Private Diff	DP DS	RS DRO
Non-private	-	-	-	67.58	-	-	-	-	-	-	-	-	-	-	-	-
$\varepsilon=0.5$	41.80	43.06	56.31	53.81	99.16	99.18	99.49	99.66	88.13	88.82	91.39	92.27	88.16	88.18	89.37	90.37
$\varepsilon=1$	45.10	46.13	55.67	55.93	99.48	99.30	99.50	99.56	89.16	89.51	91.37	91.87	89.17	89.01	89.37	90.32
$\varepsilon=5$	51.54	51.29	55.69	56.58	99.49	99.47	99.47	99.45	90.45	90.70	91.36	91.59	89.76	90.14	89.38	90.41
$\varepsilon=10$	52.47	51.68	57.26	55.67	99.55	99.32	99.46	99.45	90.39	91.29	91.38	91.58	89.93	90.35	89.38	90.45

Table 3: Comparison of Test Accuracy (%) Among Two Baseline Methods (DP SGDA and PrivateDiff Minimax) and Our Algorithms (DP Double-SPIDER and DP Recursive-SPIDER). SGDA: DP-SGDA; Private Diff: PrivateDiff Minimax; DP DS: DP Double SPIDER; RS DRO: DP Recursive SPIDER. The results for non-private are give by SCDRO ( Zhang et al., 2023 ) .

Panel of Figure 1 — Figure 1: Experimental Results: The performances of four algorithms on CIFAR10-ST, CelebA, Fashion-MNIST, MNIST-ST respectively

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 2 — Figure 2: Test AUC Results: The performances of four algorithms on CIFAR10-ST, CelebA, Fashion-MNIST, MNIST-ST respectively

Panel of Figure 3 — Figure 3: Test F1 Score Results: The performances of four algorithms on CIFAR10-ST, CelebA, Fashion-MNIST, MNIST-ST respectively

Distributionally Robust Optimization

Distributionally robust optimization (DRO) minimizes risk or cost against a set of plausible probability distributions rather than a single estimated one.

See all 86 papers

Optimal Rates for Pure $\varepsilon$ -Differentially Private Stochastic Convex Optimization with Heavy Tails
Apr 7, 2026Andrew LowyHeavy-Tailed Stochastic Optimization Differential Privacy
CISPA Helmholtz Center for Information Security
Statistical Guarantees for Distributionally Robust Optimization with Optimal Transport and OT-Regularized Divergences
Mar 29, 2026Jeremiah Birrell, Xiaoxi ShenDistributionally Robust Optimization Wasserstein Distributionally Robust Optimization
Department of Mathematics Texas State University San Marcos, TX, USA
Distributionally Robust Optimization via Iterative Algorithms in Continuous Probability Spaces
Dec 29, 2024Linglingzhi Zhu, Yunqin Zhu, Yao XieDistributionally Robust Optimization Wasserstein Distributionally Robust Optimization
1H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology

Apr 7, 2026J/K move · Enter open · S save

Optimal Rates for Pure $\varepsilon$ -Differentially Private Stochastic Convex Optimization with Heavy Tails

Andrew Lowy

CISPA Helmholtz Center for Information Security

Heavy-Tailed Stochastic Optimization Differential Privacy Stochastic Optimization Convergence

Open paper AskPDF arXiv

We study stochastic convex optimization (SCO) with heavy-tailed gradients under pure

\varepsilon

-differential privacy (DP). Instead of assuming a bound on the worst-case Lipschitz parameter of the loss, we assume only a bounded

k

-th moment. This assumption allows for unbounded, heavy-tailed stochastic gradient distributions, and can yield sharper excess risk bounds. Prior work characterized the minimax optimal rate for

ρ

-zero-concentrated DP SCO up to logarithmic factors in this setting, but the pure

\varepsilon

-DP case has remained open. We characterize the minimax optimal excess-risk rate for pure

\varepsilon

-DP heavy-tailed SCO up to logarithmic factors. Our algorithm achieves this rate in polynomial time with high probability. Moreover, it runs in deterministic polynomial time when the worst-case Lipschitz parameter is polynomially bounded. For important structured problem classes -- including hinge/ReLU-type and absolute-value losses on Euclidean balls, ellipsoids, and polytopes -- we achieve deterministic polynomial time even when the worst-case Lipschitz parameter is infinite. Our approach is based on a novel framework for privately optimizing Lipschitz extensions of the empirical loss. We complement our upper bound with a nearly matching high-probability lower bound.

Abstract

Distributionally Robust Optimization

Explore similar work

Optimal Rates for Pure ε\varepsilonε-Differentially Private Stochastic Convex Optimization with Heavy Tails

Statistical Guarantees for Distributionally Robust Optimization with Optimal Transport and OT-Regularized Divergences

Distributionally Robust Optimization via Iterative Algorithms in Continuous Probability Spaces

Optimal Rates for Pure $\varepsilon$ -Differentially Private Stochastic Convex Optimization with Heavy Tails