Differential Privacy Under Class Imbalance: Methods and Empirical Insights

…limited to binary classification…insights on generalizing to the multiclass setting?

Thank you for this interesting direction for extending our work; many of our results do extend naturally to multi-class settings. We’ll update our revised paper with an expanded version of the following:

For SMOTE Result: In both Proposition 4 and Theorem 5, the term $\left\lceil\frac{N}{n_1}\right\rceil$ reflects the number of iterations needed over the minority samples (with $N$ additional samples generated and $n_1$ original minority instances). In a multiclass setting with $c$ classes -- each with $n_1, \dots, n_c$ samples -- we can simply apply the procedure independently for each class. For class $i$, one generates $N_i$ synthetic samples so that the iteration term becomes $\left\lceil\frac{N_i}{n_i}\right\rceil.$ Taking the worst-case over classes, i.e., $\max_{i \in [c]}\left\lceil\frac{N_i}{n_i}\right\rceil,$ ensures that the overall privacy analysis carries over directly.

For ERM / DP-SGD: Multinomial logistic regression and categorical cross-entropy loss (soft-max loss) are natural extensions of the binary setting to multi-class with these models. The loss (softmax with cross-entropy) is convex and differentiable with respect to the model parameters, so the sensitivity bounds used in our weighted ERM analysis hold -- with appropriate adjustments to account for the gradient computed over all classes.

For GEM / Other Synthetic Data: Extending the DP synthetic data generation methods like GEM to multiclass settings is also straightforward! In the multiclass case, the generator is trained to learn the joint distribution over all variables, including a target variable that is potentially categorical.

...please justify why it is valid/fair to compare using different models for each method?

Thank you for raising this point. In the revised paper, we will clarify the driving question of our work, and add a version of the following discussion to address your concerns.

Our work could be framed as a first step to answering the question: Given that you want to make predictions using sensitive, class-imbalanced data, for a fixed privacy budget, which differentially private approach will give you the best performance? We are not aware (as noted by Reviewer uyZY) of any other work that directly attacks this question.

These comparisons were inherently limited by the availability of DP algorithms with explicit adaptations under class imbalance (for example, we went to great lengths to construct a weighted the DP-ERM algorithm, see Theorem 5, Lemma 14 and the proofs, etc. in Appendix C.3.1).

Then, within each approach variant (disparate approaches both in pre-processing and in-processing), we selected candidates for highlighted comparison:

1. Most performant pre-processing methods (GEM, DP Synthetic Data): We use DP synthetic data approaches (GEM and PrivBayes) to generate a class balanced, synthetic dataset. This decoupling allowed us to use any strong non-private classifier downstream. We chose XGBoost precisely because it is known for its robust performance on imbalanced data, and when tested in the non-private setting (see Appendix E.2) we found it generally outperformed a logistic regression baseline (as expected). We made a point to highlight that (strong private data synthesizer)+(strong non-private downstream classifier) is a promising framework; evaluating just that class of models could be its own follow-up work.

2. Most performant in-processing methods (Weighted ERM and DP-SGD with FTTransformer): These methods are representative of, respectively, a private convex optimizer (for ERM) and a DP-SGD-trained neural architecture. Again, we needed to adapt an ERM algorithm under class imbalance. We believe adapting other private in-processing approaches under class imbalance is a very interesting direction for future work; however, it is not often straightforward due to particular care required in the privacy analysis for the sensitivity adjustment under weights.

We did not highlight the empirical comparisons for SMOTE and for bagging (both private and non-private), as they performed poorly and reduced the clarity of our takeaways for the most performant methods we evaluated.

In summary, we acknowledge that its worth carefully considering the appropriateness of assessing methods across model families, and appreciate your concern here. Our intent with this paper was to highlight the trade-offs that arise when addressing class imbalance under DP, and provide a study that covered a lot of ground. We’d further like to highlight that the heterogeneity in approach mirrors trends in prior work, where methods are often compared at fixed privacy budgets, in their most effective form, rather than compared within a uniform model class [e.g., Jayaraman et al. 2019, https://arxiv.org/abs/1902.08874 or Suriyakumar et al., 2021 https://arxiv.org/pdf/2010.06667 ).

(Q1) Why XGBoost instead of using GEM+LogReg?

Thank you for your comment, hopefully we can clarify our choices here. Our primary goal was to compare general approaches to handling imbalanced classification under differential privacy -- not necessarily to benchmark model families (e.g., logistic regression vs. XGBoost, etc.). In our setup, we tested GEM and PrivBayes as differentially private pre‐processing steps to generate a balanced, synthetic dataset. This approach decouples the rebalancing from the classifier so that we can use any strong non-private model downstream, as we know that private ERM (regression) methods have performance limitations [e.g., Jayaraman et al. 2019, https://arxiv.org/abs/1902.08874]. Then, we chose XGBoost because this is the choice that a practitioner would likely make due to its well known overall performance, and in particular its robustness on imbalanced datasets.

However, you are correct that, although a non-private XGBoost model will generally outperform non-private logistic regression, in some of our non-private experiments in Appendix E.2 the LogReg method slightly outperformed XGBoost. However, in our private experiments, we found that the GEM+XGBoost approach was more robust to noise introduced in the dataset for privacy. We’d be happy to add these experiments on the performance of the GEM+LogReg approach into the final version of our paper. However, we stress that our aim generally was to illustrate that leveraging DP synthetic data enables the use of state-of-the-art non-private classifiers, and that (strong private data synthesizer)+(strong non-private downstream classifier) is a promising approach.

(Q2) Do you see natural extensions to SMOTE that are privacy-friendly...?

Thank you for bringing this up; as part of this work, we did spend time considering how one might develop a differentially private SMOTE algorithm. However, in our analysis for Theorem 3, we showed that SMOTE’s linear interpolation approach makes it inherently very sensitive (i.e., its sensitivity grows exponentially with the data dimension and linearly with the number of synthetic samples). In other words, even if one were to add noise directly to the interpolated points (with a differentially private additive noise mechanism), the resulting privacy loss would be unacceptably high. We view this as a key challenge: the reliance on the precise locations of pairs of minority points renders a direct privatization of SMOTE impractical.

Instead, our analysis of SMOTE motivated us to leverage established DP synthetic data methods based on the ``Select–Measure–Project’’ paradigm. These methods learn a DP approximation of the underlying data distribution and then generates synthetic samples in a way that avoids the high sensitivity pitfalls of linear interpolation (by relying on less sensitive $k$-way marginal measurements). So, in summary, our results suggest that using DP synthetic data generation methods circumvents linear interpolation between minority examples in the data (which we showed was highly sensitive, making a direct differentially private adaptation of SMOTE impractical).

(Q3)...How can the leading methods be extended to multiclass settings?

Thank you for this interesting direction for extending our work! Please see our response to Reviewer PW3A, who also asked for a discussion of this extension.

(Q4)...rejection sampling or conditional sampling (GEM)

In our experiments we adopted a conditional sampling strategy -- this is sample efficient and directly addresses class imbalance. Importantly, the underlying generator network structure remains unchanged relative to the standard GEM approach. We will make this more clear in the final version of the paper.

(Q5)...was any of the GEM training procedure changed?

No substantial changes were made to the core training procedure of GEM itself. Our approach leverages the standard GEM training protocol; the adaptation to handle imbalance is performed at the sampling stage. We view this as a feature, since practitioners would not have to change their training procedures to accommodate imbalanced data. Regarding the workload of queries (i.e., the set of measurements used during synthetic data generation), our experiments relied on the default $k$-way marginal selection. That said, in general we believe that selecting queries that capture the most informative low-dimensional marginals -- especially those relevant to the class imbalance itself -- could potentially improve performance in imbalanced settings. This is an interesting direction for future work, and we will add a discussion on it in the final version, thank you.

(Q6)...DP-SGD minibatch size clarification.

Apologies, that did not make it up from the statement of Lemma 19 in the Appendix, but yes, that is correct, B denotes the DP-SGD minibatch size. We will make sure to state this in the final version, thank you!

The paper is very well written and easy to read and follow.

Thank you for your positive feedback regarding the clarity and readability of our paper. We spent a lot of time considering how best to present the nuances of this particular classification setting, and so appreciate this recognition.

However, my main issue with the paper is the originality. The paper uses different known techniques and compares them while giving some insights about them. I think this work is incremental despite offering a nice overview on the topic.

We respectfully disagree; we believe ICML is the right venue for this work. Our paper builds on established imbalanced learning techniques and standard DP mechanisms, and it is, to the best of our knowledge, the first comprehensive study that systematically investigates differential privacy under class imbalance. We acknowledge that we evaluate class-imbalanced adaptations of pre-existing methods; however, this work is quite involved, and crucial to answering the questions our paper poses. We highlight several contributions, including:

(1) We rigorously show that well-known methods such as SMOTE and non-private bagging -- techniques that have been successfully applied in non-private imbalanced classification settings -- can dramatically inflate the sensitivity / render privacy guarantees meaningless when directly applied under DP.

(2) We introduce a weighted variant of the canonical private ERM approach, filling a notable gap in prior work (Theorem 5, see Lemma 14 and Section C.3.1 for the extensive necessary adjustments to show privacy).

(3) Our extensive empirical study -- across multiple imbalanced datasets and a range of privacy budgets -- is the “first work to extensively study the class-imbalance setting under DP” as noted by Reviewer uyZY. Our results not only demonstrate the limitations of certain approaches but highlight promising methods like DP synthetic data (via GEM) as (pre-processing) and the weighted ERM approach (as in-processing).

...related to invidualized differential privacy, not discussed...

We thank the reviewer for raising this point. While our sensitivity analysis -- specifically, how certain samples in imbalanced datasets incur higher privacy loss -- echoes themes from individualized/personalized DP, our work is rooted in standard, global worst-case DP. We will add a brief discussion in the revised version to clarify the connection.

(W1) ...did not find a formalization / could not find solutions...

A fully general formalization of the challenges in DP imbalanced classification is difficult without strong distributional assumptions. Instead, we formalize key sub-problems. For example, Theorem 3 and Proposition 4 characterize the SMOTE and bagging approaches under class imbalance, and Example 11 with Proposition 12 (deferred to the Appendix) does so under a Gaussian mixture assumption. We would be happy to revise from "formalizes these challenges" to more precisely stating that we formalize "approach-specific challenges."

Our solutions include both theoretical insights and concrete algorithmic adaptations. For example, we introduce a private weighted DP-ERM algorithm (Algorithm 1, Theorem 5) and analyze DP-SGD with weighted cross-entropy (Proposition 6, Lemma 19). We also propose a class-conditional sampling pre-processing approach with private synthetic data (Algorithm 3) and provide extensive empirical evaluations. We’d be happy to also adjust the language to clarify these claims.

(W2)...didn't know what was central and main proposition...

Our work does not have a single central theorem; instead, we compare a variety of methodologies for imbalanced classification under differential privacy constraints.

(W3)...Proposition 2 trivial...

We agree, Proposition 2 (regarding the sensitivity amplification via oversampling) is straightforward. We wanted to formalize this intuitive observation to set the stage for the more complex sensitivity analysis in the SMOTE setting (Theorem 5, see Appendix B.1 for proof). We’d be happy to present it informally, inline, so that the central contributions remain emphasized.

(W4)...Theorem 5 is confusing...

Due to space constraints, we deferred much of the discussion and setup for Theorem 5 to Appendix C.3 (in particular, see the paragraph titled “Notation for ERM Proof” and the subsequent Lemma 14, which accounts for the main sensitivity adjustment for weights for privacy). In short, Theorem 5 shows that Algorithm 5 is differentially private. The two paragraphs preceding Theorem 5 respectively provide (1) the notation with discussion of weights, and (2) intuition for how the weights play a role in the proof. We'd be happy to move anything from Appendix C.3 back into the body to make this result more clear.

(W5) (typos)

Thank you for catching the typos - we will correct them in the revised version (e.g., adjust Line 1 in the Algorithm so that $y_i \in \\{0,~1\\}$)

(Q1) [what do we mean by assuming that FP and FN have equal misclassification costs]?

This refers to the common design assumption that the cost of a false positive is identical to that of a false negative. For many applications where imbalanced learning commonly arises, this assumption doesn’t hold. For example, in detecting rare cancers or financial fraud, missing a rare but critical positive event (false negative) might be far more consequential than a false alarm.

(Q2)...privacy loss scale in Lines 78-80?

Certainly. In those lines, we briefly summarize how SMOTE can drastically increase the sensitivity of a downstream DP algorithm. Specifically, by generating multiple synthetic points from a single minority example, the effective privacy parameter $\epsilon$ is scaled by a factor that is exponential in the data dimension and linear in the number of synthetic points. This means that even if the base algorithm is $\epsilon$-DP, applying SMOTE without proper adjustments as a pre-processing step may lead to an effective privacy loss ($\epsilon’$) that is substantially higher. See e.g., the scaling and reverse-scaling we give in Table 2.

(Q3) Line 6 in Algorithm 1

Line 6 describes the core optimization of the weighted DP-ERM algorithm: minimizing the weighted empirical risk, which combines the per-sample loss (weighted by class frequency), an objective perturbation noise term, and a regularizer. We would be happy to elaborate on this step (and provide references for its standard use) in the final version for added clarity.

(Q4) (explain Line 1795)?

The privacy guarantees in our algorithm are based on the sensitivity of the per-sample gradient, which is controlled by a clipping step that bounds the norm of each gradient to a fixed constant C. Although re-weighting changes the magnitude of the computed gradients, the subsequent clipping ensures that no individual sample's contribution exceeds C. Thus, the overall sensitivity remains unchanged.