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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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 O(1n+(dlog⁡(1/δ)nε)2/3)\mathcal{O}(\frac{1}{\sqrt{n}}+ (\frac{\sqrt{d \log (1/δ)}}{n \varepsilon})^{2/3}) in terms of the gradient norm, where nn denotes the data size and dd 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 O((dlog⁡(1/δ)nε)2/3)\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ψ(t)\psi(t)ψ∗(t)\psi^{*}(t)
χ2\chi^{2}12(t−1)2\frac{1}{2}(t-1)^{2}−1+14(t+2)2-1+\frac{1}{4}(t+2)^{2}
KL-regularized CVaRI[0,α−1)+tlog⁡(t)−t+1,α∈(0,1)\mathbb{I}_{[0,\alpha^{-1})}+t\log(t)-t+1,\alpha\in(0,1)min⁡(et,α−1(1+t+log⁡(α)))−1\min(e^{t},\alpha^{-1}(1+t+\log(\alpha)))-1
Cressie-Readtk−tk+k−1k(k−1),k∈R\frac{t^{k}-tk+k-1}{k(k-1)},k\in\mathbb{R}1k(((k−1)t+1)+kk−1−1)\frac{1}{k}\left(((k-1)t+1)_{+}^{\frac{k}{k-1}}-1\right)
Table 1: Common divergences with LL -smooth conjugates.
AlgorithmMIA AUC (Mean ±\pm Std)
ε=0.1\varepsilon=0.1ε=1\varepsilon=1ε=3\varepsilon=3ε=5\varepsilon=5ε=8\varepsilon=8ε=10\varepsilon=10
DP Double SPIDER0.9719 ±\pm 0.00590.9723 ±\pm 0.00450.9717 ±\pm 0.00250.9723 ±\pm 0.00210.9724 ±\pm 0.00330.9715 ±\pm 0.0022
DP Recursive SPIDER0.8234 ±\pm 0.01270.7932 ±\pm 0.00720.7958 ±\pm 0.02400.8014 ±\pm 0.03830.8001 ±\pm 0.03020.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.
DatasetCIFAR10-STMNIST-STFashion-MNISTCelebA
SGDAPrivate DiffDP DSRS DROSGDAPrivate DiffDP DSRS DROSGDAPrivate DiffDP DSRS DROSGDAPrivate DiffDP DSRS DRO
Non-private---67.58------------
ε=0.5\varepsilon=0.541.8043.0656.3153.8199.1699.1899.4999.6688.1388.8291.3992.2788.1688.1889.3790.37
ε=1\varepsilon=145.1046.1355.6755.9399.4899.3099.5099.5689.1689.5191.3791.8789.1789.0189.3790.32
ε=5\varepsilon=551.5451.2955.6956.5899.4999.4799.4799.4590.4590.7091.3691.5989.7690.1489.3890.41
ε=10\varepsilon=1052.4751.6857.2655.6799.5599.3299.4699.4590.3991.2991.3891.5889.9390.3589.3890.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 ) .
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

Figure 2: Test AUC Results: The performances of four algorithms on CIFAR10-ST, CelebA, Fashion-MNIST, MNIST-ST respectively
Figure 3: Test F1 Score Results: The performances of four algorithms on CIFAR10-ST, CelebA, Fashion-MNIST, MNIST-ST respectively
More in this topic

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

Explore similar work

CardsList
Apr 7, 2026

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

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 kk-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.

Andrew Lowy

CISPA Helmholtz Center for Information Security

Heavy-Tailed Stochastic OptimizationDifferential PrivacyStochastic Optimization Convergence
AskPDF
Mar 29, 2026

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

We study finite-sample statistical performance guarantees for distributionally robust optimization (DRO) with optimal transport (OT) and OT-regularized divergence model neighborhoods. Specifically, we derive concentration inequalities for supervised learning via DRO-based adversarial training, as commonly employed to enhance the adversarial robustness of machine learning models. Our results apply to a wide range of OT cost functions, beyond the pp-Wasserstein case studied by previous authors. In particular, our results are the first to: 1) cover soft-constraint norm-ball OT cost functions; soft-constraint costs have been shown empirically to enhance robustness when used in adversarial training, 2) apply to the combination of adversarial sample generation and adversarial reweighting that is induced by using OT-regularized ff-divergence model neighborhoods; the added reweighting mechanism has also been shown empirically to further improve performance. In addition, even in the pp-Wasserstein case, our bounds exhibit better behavior as a function of the DRO neighborhood size than previous results when applied to the adversarial setting.

Jeremiah Birrell, Xiaoxi Shen

Department of Mathematics Texas State University San Marcos, TX, USA

Distributionally Robust OptimizationWasserstein Distributionally Robust OptimizationStatistical Learning TheoryAdversarial TrainingOptimal Transport
AskPDF
Dec 29, 2024

Distributionally Robust Optimization via Iterative Algorithms in Continuous Probability Spaces

We study distributionally robust optimization (DRO) for robust inference when the worst-case distribution is continuous, leading to significant computational challenges due to the infinite-dimensional nature of the optimization problem. Unlike traditional discrete DRO approaches, which often suffer from scalability issues, limited generalization, and costly worst-case inference, our framework exploits Brenier's theorem to characterize the least favorable distribution as the pushforward of a transport map from a continuous reference measure. This characterization motivates our study of the minimax problem in Wasserstein space. We propose an iterative algorithmic framework with multiple variants and establish global convergence guarantees under mild assumptions, deriving complexity bounds in terms of subgradient evaluations and inexact Jordan-Kinderlehrer-Otto updates. Numerical results with neural network-based transport maps demonstrate that the proposed method enables both stable training of robust classifiers and effective worst-case inference for classification tasks.

Linglingzhi Zhu, Yunqin Zhu, Yao Xie

1H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology

Distributionally Robust OptimizationWasserstein Distributionally Robust OptimizationRobust Classification
AskPDF