acceptodds
Withdrawn from ICLR 2027

Differentially Private Non-convex Distributionally Robust Optimization

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

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 constraints. 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 developing a novel -DP optimization method, called DP Double-Spider, tailored to this structure. Under mild assumptions, we show that it achieves a utility bound of in terms of the gradient norm, where denotes the data size and 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 , matching the best-known result for non-convex DP-ERM. Experimentally, we demonstrate that our proposed methods outperform existing approaches for DP minimax optimization.

Primary area:
optimization
Keywords:
Differential privacy, distributionally robust optimization

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_UcCnOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies differentially private optimization for finite-sum distributionally robust learning with nonconvex losses. For general ψ\psi-divergences, it uses a dual reformulation involving the model parameters and a scalar auxiliary variable, and proposes DP Double-SPIDER with separate private variance-reduced estimators for the two variable blocks. The authors claim an expected gradient-norm bound of $ \mathcal{O}\left(n^{-1/2}+\left(\frac{\sqrt{d\log(1/\delta)}}{n\varepsilon}\right)^{2/3}\right). $ For KL divergence, the paper introduces a compositional formulation and DP Recursive-SPIDER, claiming to remove the n−1/2n^{-1/2} term and match the cited private nonconvex ERM rate. Experiments on CIFAR10-ST, MNIST-ST, Fashion-MNIST, and CelebA compare predictive performance, gradient norms, membership-inference attacks, and hyperparameter sensitivity.

The intended contribution is a privacy–utility analysis tailored to nonconvex DRO. My principal concerns are whether the stated assumptions and formulations support the stationarity guarantees, and whether the privacy analysis applies to the algorithms and training pipeline actually used.

Critical strengths
  1. Private learning under distributional uncertainty is a worthwhile problem. Exploiting scalar dual or compositional reformulations avoids explicitly optimizing an adversarial weight vector with one coordinate per training example. Adapting variance reduction and privacy-noise calibration to the different quantities in these formulations is a sensible direction. A rigorous improvement in private stationarity guarantees for this setting would be valuable.

  2. The evaluation covers four datasets, several privacy budgets, and complementary optimization, prediction, and privacy metrics. In particular, Appendix E.4 investigates the practical tuning burden through tied, pairwise, and independently sampled clipping thresholds, together with phase-size and learning-rate sensitivity. The sensitivity experiments report three seeds, and the membership-inference experiments report five runs. These investigations address relevant practical questions, although the interpretation of some results requires clarification.

Critical weaknesses
  1. Assumption 3 requires the conjugate ψ∗\psi^* to have bounded domain (p. 4, lines 201–202). However, the divergence definition on p. 3 requires ψ(a)≥0\psi(a) \geq 0, ψ(1)=0\psi(1) = 0, and ψ(a)=+∞\psi(a) = +\infty for a<0a < 0. These conditions imply
\quad\text{for every }t \leq 0.$$ Consequently, the domain of $\psi^*$ contains the entire negative half-line and cannot be bounded. Proposition 1 additionally infers bounds on the optimization variables $x$ and $\eta$ from this assumption (p. 16, line 832), which does not follow and is not enforced by Algorithm 2. The intended assumptions and the resulting gradient bounds therefore need to be established. There is also a consequential mismatch between the original objective and the KL formulation. Equation (2) fixes the divergence-penalty coefficient $\lambda_0$. Its KL specialization is the fixed-temperature log-sum-exp objective. Equation (5), by contrast, optimizes $\lambda \geq \lambda_0$ and includes $\lambda\rho$. The latter corresponds to a KL-ball-constrained formulation, up to an additive constant, whereas that constraint is absent from Equation (2). Stationarity of Equation (5) therefore does not generally imply stationarity of the original $F(x)$, as claimed in Theorem 4. The paper needs to identify the exact problem solved by each method and establish the appropriate stationarity connection. These issues affect the scope and meaning of the headline results. A corrected theorem may be possible, but the supplied statements and proofs do not currently establish it. 2. Algorithm 2 clips the minibatch-averaged gradient or gradient difference (p. 14, lines 4, 6, 10, and 12). The privacy result invoked in Theorem 5 instead concerns averages of individually bounded per-example contributions. Clipping a batch average to norm $C$ bounds its output magnitude, but does not by itself provide sensitivity $2C/b$ for batch size $b$; an independent per-example bound is required. The privacy proof on p. 16 does not establish the necessary connection. Changing to per-example clipping would also require a corresponding utility analysis. Lemma 6 treats the estimators as unbiased and replaces the clipped updates by unclipped gradient expressions (p. 20, lines 1031–1041), without proving that clipping is inactive or controlling its bias. Thus the sensitivity and convergence arguments need to be reconciled for the same implemented mechanism. The experimental privacy claims require clarification. Appendix E.4 describes pretraining and warm starts, including a 12-epoch class-balanced pretrain in Recursive-SPIDER’s main training framework (p. 28, lines 1488–1491), without establishing their privacy status or accounting. Table 2 also reports MIA AUCs of 0.9719 and 0.8234 at $\varepsilon = 0.1$. These unusually high values require reconciliation with the stated guarantee and the attack’s sampling protocol. They do not alone prove a privacy violation, since an unmatched train-versus-test experiment can exploit distributional differences. However, the complete training pipeline and membership experiment must be documented before the results can substantiate a private utility advantage.
Questions for authors
  1. Could the authors clarify what the precise intended replacement for Assumption 3 is? Please identify a nonempty class of divergences satisfying the corrected assumptions and explain how they establish Proposition 1 along the actual Gaussian-perturbed iterates. This is necessary to determine whether the general-divergence result applies to the examples considered.

  2. Does the KL method solve the fixed-penalty problem in Equation (2), or a KL-ball-constrained problem corresponding to Equation (5)? Please state the exact objective controlled by Theorem 4 and establish the claimed stationarity implication. Also clarify how Algorithm 3 enforces λ≥λ0\lambda \geq \lambda_0 and positivity of the noisy scalar estimate used in log⁡(st)\log(s_t) and reciprocal terms. As written, the initialization and unconstrained updates do not supply these conditions, while Lemma 7 uses a logarithm inequality requiring positive arguments bounded away from zero.

  3. Does Algorithm 2 clip individual contributions before averaging, or the batch average as written? Please provide the neighboring-dataset sensitivity and composition calculation for the implemented mechanism. Where does the utility proof control clipping bias, or establish that clipping is inactive for all four estimators? A correction to the clipping operation should be accompanied by the corresponding estimator-error argument.

  4. Was the pretraining described in Appendix E.4 performed on public data, independently privatized, or included in the reported privacy accounting? Please specify the accounting for pretraining, warm starts, and any data-dependent model selection. For Table 2, how are members and nonmembers sampled, including their class distributions? Please reconcile the reported AUCs at ε=0.1\varepsilon = 0.1 with the stated privacy parameters and explain whether the attack represents a matched neighboring-dataset membership test.

  5. What exact quantity is plotted in Figure 1, at which privacy budget, and is the legend correct? Under the displayed legend, the Diff baseline has the lowest terminal gradient norm in all four panels, while the proposed methods’ norms increase in several cases. This conflicts with the interpretation in lines 422–431 and 452–454. Please clarify whether all curves measure stationarity of the same objective under comparable initialization and computational settings, and reconcile the figure with the claimed convergence advantage.

I think the paper addresses an important problem, and I appreciate the attempt to develop differentially private algorithms specifically for nonconvex distributionally robust optimization. The proposed combination of variance reduction and privacy-preserving gradient estimation is interesting, and the authors have included a reasonable range of experiments. However, I have significant concerns about the theoretical justification of the main results. In particular, the assumptions underlying the convergence analysis, the relationship between the original DRO objective and the KL-based reformulation, and the consistency between the clipping mechanisms and privacy proofs need further clarification. I also find that some experimental conclusions are difficult to reconcile with the reported gradient-norm curves and membership-inference results. These issues are important because they directly affect the validity of the paper's main claims, rather than being merely presentation concerns. Overall, I see potential in the research direction, but I do not think the current manuscript provides sufficiently convincing support for its theoretical and empirical conclusions.

Reviewer_ExmqOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes optimization algorithms for DRO with DP guarantees. They build two Spider-style algorithms and analyze the utility of the algorithms, which matches the best-known result in DP-ERM with non-convex loss for DRO with KL-divergence.

Critical strengths

The paper seems to develop algorithms that exploit the structure of different forms of the optimization objective.

Critical weaknesses

More background for DRO is needed. For example why DRO can be formulated as eq 2. Also how can eq 2 be reformulated as 5? It seems to require DRO with specific structure, i.e. KL-divergence. In this regard, can we really characterize the result in sec 5 as an improvement? Or it's a stronger result that only holds for special class of DRO?

I have trouble following Algorithm 3. Lemma 8 states st+1=g(wt+1;ξi)+(1−βt)(st−g(wt;ξi))+ζts_{t+1} = g(w_{t+1}; \xi_i) + (1-\beta_t)\left(s_t - g(w_t; \xi_i)\right) + \zeta_t I didn't see how this follows and where clipping is handled.

Also w is initialized to be 0 but it's required that λ≥λ0\lambda \ge \lambda_0.

Questions for authors

See above

Reviewer_zU3dOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates Differentially Private Distributionally Robust Optimization (DP-DRO) under non-convex loss functions and general ψ\psi-divergences.

Critical strengths

The authors present two main algorithmic contributions:

  1. DP Double-Spider: Designed for general ψ\psi-divergences by reformulating the minimax DRO problem into an unconstrained dual minimization problem over model parameters xx and a dual variable η\eta, using variance-reduced SPIDER-style estimators with Gaussian noise.

2.DP Recursive-Spider: Tailored specifically for KL-divergence DRO by transforming the problem into a compositional finite-sum optimization structure, achieving an improved utility bound of O((dlog⁡(1/δ)nϵ)2/3)\mathcal{O}\left(\left(\frac{\sqrt{d \log(1/\delta)}}{n\epsilon}\right)^{2/3}\right).

The motivation is timely and the empirical results appear promising

Critical weaknesses
  1. In Section 3, Assumption 3 states: "Assume that the domain of the conjugate function ψ∗\psi^* is bounded by a constant S0>0S_0 > 0." However, in the proof of Proposition 1 (Page 16), the authors invoke this assumption to claim: "By Assumption 3, we have ∣x∣,∣η∣≤S0\\|x\\|, \\|\eta\\| \le S_0. Then, by Lemma 2 in Arora et al. (2022), we have ∣(ψ∗)′∣≤2S02M+2MS03\\| (\psi^*)'\\| \le 2 S_0^2 \sqrt{M} + 2 M S_0^3." This represents a fundamental mathematical error and conceptual confusion: The domain of the conjugate function ψ∗(t)=sup⁡a{ta−ψ(a)}\psi^*(t) = \sup_{a} \{ta - \psi(a)\} refers to the input space of the function ψ∗\psi^* (i.e., t∈dom(ψ∗)t \in \text{dom}(\psi^*)), not the Euclidean norm bounds on the optimization variables x∈Rdx \in \mathbb{R}^d or η∈R\eta \in \mathbb{R}. Furthermore, for standard divergences widely used in machine learning (such as χ2\chi^2-divergence where ψ∗(t)=−1+14(t+2)2\psi^*(t) = -1 + \frac{1}{4}(t+2)^2, or KL-divergence where ψ∗(t)=et−1\psi^*(t) = e^t - 1), the domain of ψ∗\psi^* is R\mathbb{R}, meaning it is unbounded. Conflating input domain bounds of a conjugate function with parameter boundedness (xx and η\eta) invalidates Proposition 1, Lemma bounds, and subsequent convergence proofs

  2. In Theorem 7 (Page 18, Line 939), the required large-batch refresh size N1N_1 is bounded by:

N1≥n⋅6D2c0c2N_1 \ge n \cdot 6 D_2 c_0 c_2

where D2D_2 is the variance term defined in Lemma 2 (Page 15) as D2=G2M2λ−2σ2D_2 = G^2 M^2 \lambda^{-2} \sigma^2. In the experimental setup (Appendix E.1, Page 26), the regularization parameter λ0\lambda_0 is set to a small value: λ0=10−3\lambda_0 = 10^{-3}. Because D2D_2 scales quadratically with 1/λ21/\lambda^2, for λ=10−3\lambda = 10^{-3}, D2D_2 blows up by a factor of 10610^6.Consequently, the theoretical requirement dictates that N1≥O(n×106)N_1 \ge \mathcal{O}(n \times 10^6). However, N1N_1 is a batch sampled from the training dataset of size nn, meaning N1N_1 must satisfy N1≤nN_1 \le n. This creates a direct mathematical contradiction: the theory requires batch sizes millions of times larger than the entire dataset size itself, making the theoretical bounds vacuous or impossible to satisfy in practical regimes where λ\lambda is small.

  1. For KL-divergence DRO in Section 5 (Equation 5), the inner minimization requires λ≥λ0\lambda \ge \lambda_0 (where λ0=10−3\lambda_0 = 10^{-3}). However, in Algorithm 3 (Page 14), the update rule is unconstrained:

wt+1=wt−ηztw_{t+1} = w_t - \eta z_t

where w=(xT,λ)Tw = (x^T, \lambda)^T. There is no projection operator ensuring λ≥λ0\lambda \ge \lambda_0 or λ>0\lambda > 0. Without projection, unconstrained gradient updates can push λ\lambda to negative values or zero. If λ≤0\lambda \le 0, terms like exp⁡(l(x;ξ)/λ)\exp(l(x;\xi)/\lambda) experience exponential overflow or undefined logarithmic penalties, causing numerical instability and algorithm collapse during training.

The above theoretical flaws require substantial restructuring and re-derivation of the proofs before submitting to a venue like ICLR.

Questions for authors

See weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.