Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Authors: Lucas Rosenblatt
Yuliia Lut
Ethan Turok
Marco Avella Medina
Rachel Cummings
Venue: ICML 2025 poster (2025)
Keywords: differential privacy
imbalanced learning
synthetic data
binary classification
Primary area: social_aspects->privacy
TL;DR: We consider imbalanced learning under differential privacy, presenting negative results on some existing natural approaches and positive results on modified algorithms, along with empirical evaluations.

Abstract: Imbalanced learning occurs in classification settings where the distribution of class-labels is highly skewed in the training data, such as when predicting rare diseases or in fraud detection. This class imbalance presents a significant algorithmic challenge, which can be further exacerbated when privacy-preserving techniques such as differential privacy are applied to protect sensitive training data. Our work formalizes these challenges and provides a number of algorithmic solutions. We consider DP variants of pre-processing methods that privately augment the original dataset to reduce the class imbalance, alongside DP variants of in-processing techniques, which adjust the learning algorithm to account for the imbalance. For each method, we either adapt an existing imbalanced learning technique to the private setting or demonstrate its incompatibility with differential privacy. Finally, we empirically evaluate these privacy-preserving imbalanced learning methods under various data and distributional settings. We find that private synthetic data methods perform well as a data pre-processing step, while class-weighted ERMs are an alternative in higher-dimensional settings where private synthetic data suffers from the curse of dimensionality.

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Lucas Rosenblatt
Yuliia Lut? Ethan Turok? 2 Marco Avella-Medina Rachel Cummings
Abstract
fraudulent transactions (Makki et al., 2019), medical diag- nostics for rare diseases (Singh et al., 2020; Yuan et al., 2018), or predicting natural disasters (Johnson & Khoshgof- taar, 2019). Applying standard machine learning algorithms without adjustment can lead to poor predictions on rare events because these methods are designed for training data that approximately balanced, assume that false posi- tives and false negatives have equal misclassification costs.
Imbalanced learning occurs in classification set- tings where the distribution of class-labels is highly skewed in the training data, such as when predicting rare diseases or fraud detection. This class imbalance presents significant algorithmic challenge, which can be further exacerbated when privacy-preserving techniques such as differen- tial privacy are applied to protect sensitive train- ing data. In this paper, we formalize approach- specific privacy challenges faced by standard im- balanced learning remedies and develop algo- rithmic adaptations with proven DP guarantees. We consider DP variants of pre-processing meth- ods that privately augment the original dataset to reduce the class imbalance, alongside DP vari- ants of in-processing techniques, which adjust the learning algorithm to account for the imbal- ance. For each method, we either adapt an exist- ing imbalanced learning technique to the private setting or demonstrate its incompatibility with differential privacy. Finally, empirically evalu- ate these privacy-preserving imbalanced learning methods under various data and distributional set- tings. We find that private synthetic data methods perform well as a data pre-processing step, while wlightee ERMs are an alternative in higher- dimensional settings where private synthetic data suffers from the curse of dimensionality.
In the machine learning community, the problem of im- balanced learning has been widely studied in non-private settings (He & Garcia, 2009; Sun et al., 2009; Chawla et al., 2004). This issue can tackled with two main approaches. The first approach is use pre-processing techniques to balance the training dataset, such oversampling (Chawla et al., 2002) or other data augmentation based methods. The second approach is to use in-processing techniques to modify the machine learning model itself to account for the imbalance, such as bagging (Breiman, 1996) or loss re- re-weighting (Karakoulas & Shawe-Taylor 1998; Rigollet & Tong, 201 Scott, 2012: Tong, 2013; Xu et al., 2020b).
In applications when data are both sensitive and imbalanced for instance, in the detection of rare diseases (Ficek et al., 2021) we need machine learning tools that preserve pri- vacy while maintaining high accuracy. Differential privacy (abbreviated DP) has emerged as a powerful technical defi- nition in machine learning and theoretical computer science to address privacy concerns using formal algorithmic tools. Many traditional machine learning algorithms have DP im- plementations (Gong et al., 2020; Chaudhuri et al., 2011; Abadi et al., 2016; Fletcher & Islam, 2017). However, ex- tending such approaches to private data augmentation meth- ods for imbalanced settings encounters two main challenges. Firstly, it has been shown that private classifiers can amplify minority group loss, magnifying bias and unfaireess (Tran et al., 2021; Pujol al., 2020; Rosenblatt al., 2024b). Secondly, pre-processing techniques such as oversampling run the risk of increasing sensitivity of the learning task, thus increasing privacy loss. One must therefore be careful when designing anced learning that improve performance with respect to the minority class without over-inflating the privacy budget.
1. Introduction
The problem of imbalanced learning typically refers to classification tasks where one of the label-classes is sub- stantially underrepresented in the training data. This oc- curs commonly in real-world applications, such detecting
'qqual contribution 'New York University "Work completed while Y.L. and E. were at Columbia University. 'Columbia Uni- versity, Correspondence to: Lucas Rosenblatt <lr2872@ dt2872@nyu.cdu>>
prreccppreservinggg techniques for imbal-
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Table I: Summary of methods we consider alongside short takeaways. The (Type) indicates the practical outlook for each method: P (Positive), N (Negative), or M (Mixed).
1.2. Related Work
Imbalanced learning and privacy. The problem of imbal- anced data often arises in machine learning when the size of one data class is considerably smaller than the other data class. Prior work on imbalanced learning without privacy constraints is extensive (Chawla et al., 2004; He & Garcia, 2009; Sun et al., 2009; Galar et al., 2011; Krawezyk, 2016; López et al., 2013; Branco et al., 2016), alongside work studying adjustments to common learning losses for imbal- anced classification (Scott, 2012; Menon al., 2013). The challenge of handling imbalanced data in machine learning becomes much harder when privacy constraints are added, as accuracy for the minority class can be low even for non- private classification (Lau & ditionally, prior work shows that differentially private al- gorithms can disproportionally affect minority groups by amplifying the lost of accuracy of a minority class (Bag- dasaryan et al., 2019; Jaiswal & Provost, 2020) as well as magnify bias and unfairness (Xu et al., 2020a; Pujol et al., 2020; Farrand et al., 2020; Tran et al., 2021). Work by (Jor- don et al., 2019) studies bagging under differential privacy with the assumption of a publicly available data sample; we do not make any such assumptions, and thus can operate in the most general settings.
Method (Type)
Key Observations
Oversampling
Sensitivity rises with repeated sumples, leading to excessive privacy loss.
(Pre-processing. N)
SMOTE
Sensitivity scales with dimension, rendering pri- vacy loss impractical.
(Pre-processing, N)
Private Synthetic Data
processeeeseddd synthetic data preserves DP and performs well for imbalanced tasks.
(Pre-processing. P)
Bagging (Non-Privatee
Lacks meuningful privacy guarantees; loo small 6 values are infeasible.
(Inproccessing N)
Bagging (Private)
Splitting the privacy budget across weak leamers impacts both privacy and utillity.
(In ilnpprocessing.. N)
2021). Ad-
Weighted FRM
Theory shows how to incorporate class weights into the objective while maintaining privacy.
(Pre-pracessing. P)
Weighted DP-SGD
Class weight adjustments for DP-SGD are straighffowward but mixed performance.
(Pre-pracessing. M)
1.1. Our Contributions
In this work, we explore both pre-processing and in- processing methods for private imbalanced binary classi- fication (and note that many of our methods have natural extensions to the multi-class settings). In Section 3, we account for the privacy degradation caused by the well- known anttataugmentaionnn technique SMOTE (Chawla et al., 2002), showing that its privacy loss scales as (c22*k) for d- dimensional data and k new data points (unacceptably large for practical settings). This motivates an alternative: using black-box DP synthetic data techniques for augmenting mi- nority data, which is trivially private via post-processing (Proposition 8) and empirically effective.
Private synthetic data generation. There has been much progress in recent years on methods for differentially private data synthesis and generation (McKenna et al., 2019; Vietri et al., 2020; Rosenblatt et al., 2020; Aydore et al., 2021; Zhang et al., 2021; Cai et al., 2021; Boedihardjo et al., 2022). Some of the best-performing methods follow the Select- Measure-Project paradigm (Tao et al., 2021; McKenna et al., 2022); we discuss further in Section 3.3.
Private subsampling and deep learning. It is known that randomly subsampling the input database before running a private mechanism can improve the privacy guarantees (known as amplification by subsampling) (Bassily et al., 2014; Bun et al., 2015; Wang et al., 2016), although data- dependent subsampling can have negative privacy impacts (Bun et al., 2022). Relatedly, the advent of differentially private gradient descent via gradient clipping and moments accounting (Abadi et al., 2016; Sun et al., 2022) has led to privatized versions of many standard deep learning models that exhibit strong empirical performance (Gong et al., 2020; Yousefpour et al., 2021), although private generative models can intensify the imbalance in the data offer a lower qual- ity synthetic data (Cheng et al., 2021; Ganev et al., 2022). Recent work has expressed skepticism over the performance of these methods, hypothesizing instead that their strength can be partially explained by the effect of unreported hyper- parameter tuning in a "dishonestly" private manner (Paper- not & Steinke, 2021; Redherg et al., 2024). Thus, we solely run our models with default hyper--pramee settings.
Shifting to in-processing in Section 4, we evaluate model bagging (Breiman, 1996); though prior work claimed an 'intrinsic" DP guarantee for bagging (Liu et al., 2020), we demonstrate that the resulting privacy parameters are not meaningful (Proposition 4). As positive in in-processnng re- sult, we adapt the canonical private empirical risk minimiza- tion (ERM) algorithm (Chaudhuri et al., 2011) to class- weighted variant (Algorithm 1, privacy given in Theorem 5). DP-SGD also trivially allows for class weights ( (Algorithm 4, privacy given Proposition 6). However, we find that even strong neural model trained with weiihte DPD performs poorly, suggesting neural models may not be ideal for small to medium-sized classification tasks on tabular data. Instead, our extensive experiments on datasets from imblearn (Lemaitre et al., 2017) suggest that training a strong non- non-private model (like XGBoost) on DP best performance, followed by DP weighted ERM.
imbalanced
synthetic data yields the
2

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Personalized differential privacy. Our observation that minority samples can incur larger privacy loss echoes the literature personalized (a.k.a. individualized) DP (PDP) (Kifer & Machanavajjhala, 2011; Jorgensen et al., 2015), which relaxes the global definition by assigning user-specific budgets. In contrast, all results in this paper respect the standard global DP guarantee; incorporating PDP into class- imbalance learning pipelines remains an open direction.
A well-known technique for achieving (e, O)-D is with the Laplace mechanism (given in Appendix A). Alter- natively, one can use the the Gaussian mechanism to achieve (c, (c.P) (Dwork et al., 2006). In both cases, noise is added to the output of a real valued function f that depends on the sensitivity of f. For the Gaussian mechanism, we consider the E sensitivity of the function (i.e. A2f = maXncighhors D.D (D) - f(D") l2,, where || ll2 denotes the Euclidean norm), and add noise sampled from .V' (M- 02 (A2f)². 2 -22) The Gaussian 2
2. Preliminaries
mechanism further requires that e < 1 for the privacy guar- antees to hold. In settings where data points can be un- bounded, clipping can be applied to project each X, in the range [-R, Ri; doing so reduces the sensitivity of the function, and hence the scale of noise that must be added. Additionally, DP has a number of helpful properties. It composes (Theorem 7) i.e. the privacy parameter degrades gracefully as additional computations are performed on the same database, and is robust to post-processing (Theorem 8), meaning that any further analysis on the output of a differentially private algorithm cannot diminish the privacy guarantees (formal statements available in Appendix A).
Imbalanced Learning. De = = (X,9) y) denote a dataset, where X is a set of d-dimensional instances from a known range [ R, R2 and y is a vector of binary labels. Each (2r, yt) E [- R, Rjdd x {0, }} a single labeled training example. We partition X into X and X2, respectively denoting the sets of entries of X that are labeled with 0 and
1, where these sets are of size |X9 no and | = n1- To model the imbalanced setting, we assume without loss of generality that n1 < 14g-
We define r = no > 1 to be the imbalance ratio between the positive and negative label classes in the sample. The goal of imbalanced learning is to develop binary classifier that accurately learns from the imbalanced dataset D. In other words, we seek to learn a function f f |-R, R) + {o, }} by minimizing given loss function L weighted by class imbalance in the training label distribution.
3. Pre-processing Methods for Private Imbalanced Learning
In this section, we consider applying pre-processing meth- ods for data augmentation to address class imbalance: given level of class imbalance in the training data, augment or replace the dataset to increase support for the minority class. After applying a pre-processing method, we can then pri- vately learn a classifier on the augmented dataset. The first two methods we consider oversampling in Section 3.1 and SMOTE in Section 3.2 are non-private pre- proceeseessnng methods; we show that both of these methods substantially increase the sensitivity of the downstream private learning mechanism. This increase in sensitivity is due to the fact that these methods generate synthetic minority samples that are highly dependent on the original data, so changing one input point in the original database may lead to many points being changed in the augmented database. This motivates our consideration of private synthetic data generation for data pre-processing in Section 3.3. In the case of private synthetic data, we instead perform our privacy intervention upstream, learning a DP parameterization of the distribution of our data, from which we can draw arbitrary samples for downstream, non private model training.
Differential Privacy. DP limits the effect of any individ- ual's s data on a computation and ensures that little can be in- ferred about the individual from an appropriately calibrated randomized output. Intuitively, it bounds the maximum amount that single data entry affect analysis performed on the database. Two databases D, D' are neighboring if they differ in at most one entry. In this work, we present results for the bounded variant of neighboring datasets, i.c., neighboring datasets are the same size, [D] = [D', and are identical except for a single entry. All of our results can be extended the unbounded variant, i.e., where D' can be constructed through addition/removal, so DI = D + (Kifer& & Machanavajjhala, 2011).
Definition 1 (Differential Privacy (Dwork et al., 2006)). An algorithm M: : D + R is (c, -)d-fferreettillll private if for every pair of neighboring databases D' E D, and for every subset of possible outputs& S C R,
Pr[M(D) E ES] S exp(e) Pr(M(D)) E +.
When 5 M may be called e-differentially private.
3.1. Oversampling
'ee assume that X lies in a bounded range because this is necessary for differentially private regression (see, c.g.. (Chaudhuri al., 201 ))) If bound on the data points is not known priori, then one can use domain knowledge or using other private methods such& as Propose- Releaee (Dwork & Lei, 2009).
A common technique for dealing with class imbalance in data is apply an oversampling algorithm that first gener- ates N additional synthetic samples from the minority class, before performing learning the augmented dataset. The
3

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
learning algorithm then takes as input the original dataset D v), concatenated with the N new minority class (positive label) samples. While N can be chosen freely by the analyst, a common parameter regime is to choose N = - - m to equalize the size of the two classes. A sim- ple oversampling method is to replicate each minority point in X, either [N/mi] or [N/m1] times to ensure N total new points; we refer to this as deterministic oversampling." 2
Table 2: SMOTE requires a dramatic adjustment to the privacy parameter:(leff) the adjusted values of input privacy parameter e' to the DP algorithm for varying desired privacy budgets e, and (right) the resulting privacy budgets c if e' is unadjusted, under practical assumptions: ò = 1/n2 with 10000, d = 25, k 5, y 0, [N/n1] = 1.
Input c' required for desired c.
Resulting c from unadjusted c'.
As formalized in Proposition 2, deterministic oversampling increases sensitivity of any downstream DP learning algo- rithm by a multiplicative factor of [N/mi] + 1. This is because the maximum of [N/n[] additional samples gener- ated from each minority point, along with the minority point themselves, will all be used in the downstream algorithm.
<=1
<=5 5
10
é' =5
é' 10
0.00469 0.02346
0.04632
213.21
1066.06
2132.1
orem 3 should be viewed as a negative result (i.e., SMOTE makes ensuring downstream privacy very difficult). Addi- tionally, note that with only the (c, O)-DP result, one might wonder whether the large increase in epsilon can be avoided by allowing a positive 8. Thus, we include and highlight the (e, 5) result, which shows that this is not the case; even when a strictly positive failure probability 8 >> O is allowed, the explosion in is still present (albeit reduced by 1/k factor). Intuitively, we frame the result as follows: introducing new, minority class examples based linear interpolations of cxisting minority class examples leads to significantly higher privacy sensitivity. See Table 2 for ex- amples of how large practical e values can become, after adjusting for the sensitivity of SMOTE preprocessed data.
Let D (X,y) be a dataset with nn minor- ity instances, and let M be an arbitrary (e, 8)-DP algorithm. Instantiating M on the dataset D concatenated with the output of oversampling to generate N additional minority N 1 5( N samples is (<( m1 1),
Proposition 2.
m1 + diffefffereltillly private.
3.2. SMOTE
The Synthetic Minority Oversampling TEchnique (SMOTE (Chawla et al., 2002), Algorithm 2, deferred to Ap- pendix B.1) is a more advanced oversampling technique and has become a benchmark for imbalanced learning (see, e.g., (Fernández et al., 2018)). For N iterations, the algo- rithm: (1) selects an instance from the minority class, (2) finds the k nearest neighbors of this point under &a distance and samples one uniformly at random, and (3) generates a new minority instance as a random convex combination of the original instance and its selected nearest neighbor. Unfortunately, Theorem 3 shows that applying SMOTE as a pre-processing step before any differentially private algorithm substantially increases the sensitivity of the down- stream computation: the increase in effective epsilon is exponential in d and linear in N. This dramatic increase in the e factor, if unaccounted for, leads to an overall e'DD guarantee for extremely large e' values that provide mean- ingless privacy guarantees.
We further note that this negative result has implications for more advanced glass-imbalancees methods that embed the SMOTE algorithm (SMOTEBoost (Chawla et al., 2003), SMOTEBagging (Wang & Yao, 2009), etc.). For good mea- sure, we empirically demonstrate the poor private perfor- mance of SMOTE (with the proper sensitivity adjustment) in Appendix B.
3.3. Private Synthetic Data
We have shown that non-private data augmentation tech- niques for imbalanced learning, like oversampling and SMOTE, explode downstream privacy parameters by am- plifying sensitivity. Private data pre-processing avoids this limitation. Specifically, we propose leveraging existing pri- vate synthetic data algorithms to produce private balanced dataset that is usable for learning. State-of-the-an methods for producing synthetic data with a DP guarantee follow the same general approach: first, they select DP measure- ments to evaluate on the data (Select), then compute these measurements on the sensitive data (Measure), and finally fit a new distribution to those measurements (Project) (Liu et al., 2021). New samples can then be drawn from the private distributional model to combat data imbalance one simple and general approach is to draw enough new sam- ples of the minority class to balance both classes. A formal version of this procedure is given in Algorithm 3 (deferred to Appendix B.2 for space); note that any DP synthetic data
Theorem 3. Let D yX be a d-dimensional dataset, with n, minority instances, and let M be an arbitrary e-DP algorithm. Then instantiating M on D concatenated with the output of SMOTE(X, N, k) is both (e420-4042d N O)DD and (é',))-D, for any y 2 O and for,
m
é <(1 + +2)22 a002dd
INT
A full proof of Theorem 3 is deferred to Appendix B. The-
"One could also randomly and independently sample point to replicate from the minority class N times, also exacerbating downstream sensitivity. For simplicity of presentation we stick with deterministic oversampling.
F

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
generation method could be substituted in Stage I of Al- gorithm 3. Furthermore, arbitrarily many samples can be drawn from the privately fitted distributional model due to post-processing (Theorem 8).
dataset D by randomly subsampling k examples from D (with or without replacement) to constitute each D, Then train a base model on each subsample D, using a base weak learner. To generate prediction ğ: for a given sample X,, take the majority vote of predictions from each weak learner.
Algorithm 3 defaults to performing conditional sampling to up-sample the minority class for parametric models (i.e. condition a new generated sample on fixed positive or negative feature label), as this is sample efficient. For non- parametric models, one take more general rejection sampling approach. In Appendix E, we empirically com- pare two ofuc-oo--thearr DP synthetic data methods: the PrivBayes (Zhang et al., 2017) and Generative Networks with the Exponential Mechanism (GEM) (Liu et al., 2021) algorithms. Both GEM and PrivBayes are parametric mod- els and thus permit conditional class sampling. We then give our empirical results in Section 5 with GEM for clarity, as we found it outperformed PrivBayes across the board.
Since the bagging procedure is randomized, recent work has suggested that it is intrinsically differentially private, based on the randommess in sampling and in the predictions of the weak learners which would imply that bagging is potential in-processing method for handling imbalanced data. Specifically, Liu et al. (2020) showed that for a dataset of size n. bagging with parameters (m, k) satisfies (c, 5)DD for e = m k In( xt11 and 6 = 1 - (-=1))= m
However, we highlight a significant issue with this approach, simply by inverting these expressions, and solving for m and le given commonly desired settings of and 6, namely that 5 is polynomially small in n. Proposition 4 states that this ce-parameterization reveals a major issue: we cannot set 5 to be very small without setting e to be exceedingly small as well; see Appendix C.1 for a simple proof.
4. In-processing Methods for Private Imbalanced Learning
Proposition 4. For a bagging classifier composed of non- differentially private learners to achieve 8 = n .then it must also be that S for all >>> 1.
ln-processing methods account for class imbalance by ad- justing the learning process. They broadly fall into two main categories: ensemble-based classifiers and cost-sensitive classifiers. Our first in-processing method we consider in Section 4.1 is bagging, which is an ensemble-based classi- fier over splits of the training data. We show that although bagging non-private learners does provide some inherent privacy, the resulting DP parameters are not meaningful in practice. Cost-sensitive classification assumes a greater cost to misclassifying minority class examples in the training data (Chawla et al., 2004); the primary approach to accom- modate asymmetric misclassification costs are weighting strategies during model training. In Section 4.2, we revisit canonical results from (Chaudhuri al., 2011) on differen- tially private empirical risk minimization (ERM) and show how to introduce sample weights. Finally, in Section 4.3, we show that the widely-used differentially private stochastic gradient descent (DP-SGD) methods for deep learning can easily accommodate class-based weighting.
Such a small c value, paired with a constant- sonstant-sensitivity func- tion, would not allow the private output to sufficiently vary across different databases, even if they differ in many data- points, meaning that the private output cannot provide mean- ingful accuracy. Therefore, non-private classifiers cannot be used in bagging procedures to simultaneously provide meaningful privacy and accuracy guarantees.
One approach to improving private bagging would be to use private classifiers as the weak learners; in that setting, the privacy would follow easily via composition over all the private classifiers used. Given dataset D and a bagging procedure that trains m 8) regression models, then by advanced composition (Dwork et al., 2014), for any 8 > O, this version of private bagging would satisfy (e',mō DP for e' = /2m In(1/8" e e+ +me(e" - 1). As we show empirically in Appendix C.I (Figure 3), this can still result in poor empirical performance in reasonable settings. One explanation is that since many private weak learners are needed, the privacy budget is "spread too thinly" over all the classifiers. That is, to satisfy a desired e' privacy budget, the per-learner privacy parameter e has to be small, thus significantly reducing performance.
mō +
4.1. Bagging and Private Bagging
Bagging is used widely in practice in imbalanced learning settings, as it has been shown to foster more diversity in model parameters and may help mitigate overfitting to the majority class by elevating minority class importance in the bootstrapped training subsets. This empirical strength, robustness, and improved bias-variance tradeoff' of bagging techniques in imbalanced learning is well known (Ueda & Nakano, 1996; Moniz et al., 2017; Haixiang et al., 2017).
Tighter composition analyses exist based on moments ac- countants (Abadi et al., 2016; Wang et al.. 2019), where the dataset is also subsampled for each computation. These methods are most effective when only a small fraction of
The standard bagging procedure (Breiman, 1996) is as fol- lows: create m subsamples {Di.... } of a training
Many even prefer stronger requirement, which is that 8 is cryptographically small, or negligible, in n.
5

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
the dataset are included in each subsample: to contrast, many bagging procedures rely on much larger sub-samples disbursed among fewer learners (Sun et al., 2015). Addition- ally, in Appendix C.1, we explore a range of private bagging configurations - including disjoint splits (exploiting parallel composition), stratified sampling to preserve minority-class representation (under different privacy assumptions), and alternative voting schemes- yet find these bagging variants similarly yield limited performance under class imbalance. Overall, these empirical results are negative for bagging: one potential reason is that since so few minority class ex- amples existed in the dataset, subsampling further reduces the number of minority examples available to each weak learner. We provide further insights in Appendix C.I.
D = {(1 v:));= where y E {O...., k} represents the class label of each sample, we compute the class frequen- cies for class k as म. = 1 > Zi-1 1yy = k). The inverted class frequency vector Ω
= (1/fo..... 1/ gives the Ty.
3
sample weights ui; = _ -| E [0, 1], where each sample is weighted according to the inverse frequency of its class in the dataset. We choose this weighting scheme to align with our "warm-up" results in Appendix C.2 along with prior work (Chawla et al., 2004; Galar et al., 20.1).
Algorithm 1 Weighted ERM w/ Objective Perturbation
Inputs: Data D = {zi, with yi E {o,...,kk .).. parameters e, X, c, loss E(y.. B), weight function
W: D - [0, 1]m
Output: Approximate minimizer B pprie
4.2. Weighted Approaches
3 Let w = WWD), e" = 4nd
6'=6-é e"
"(++A))
Cost-sensitive classification assumes a greater cost to mis- classifying minority class examples and is a well-studied and practically effective method for combating class imbal- ance (Zhou& & Liu, 2005). Weighting strategies during model training are the primary approach used to accommodate mis- classification costs (Chawla et al., 2004). In Section 4.2.1 we show how to adapt the private ERM given in (Chaudhuri et al., 2011) under a bounded weighting scheme. Later in Section 4.3 we show that DP-SGD can be modified to ac- commodate weights naturally. We also evaluate weighting strategies with additive noise mechanisms under distribu- tional assumptions where the Bayes optimal classifier is known (e.g.. a Gaussian mixture). This follows the setting of (Yang& & Xu, 2020), but within a differential privacy framework. We present this as a "warm-up" problem and refer interested readers to Appendix C.2 for details.
4 If > 0 then A = 0 else A
- X, c' =
((er/_11)
(ensuring e' 2 0 as in (Chaudhuri et 2011)).
5 Draw vector b according to PDF ubb x e
6 Compute B Ppric = o f, Ei= Wi Ely:, x. B) +
Theorem 5 states that Algorithm I is still DP. To accommo- date changes in class balance between neighboring datasets, our privacy analysis handles scenarios where neighboring datasets differ minority class label, thereby slightly altering class proportions and associated sample weights.
Sketch of Theorem 5. Specifically, we show that the total change in weights, if the minority class size and label propor- tions changed by one, is bounded as Σ,= tu;-w(( < 2-1 Consequently, we must adjust the sensitivity of the pertur- bation vector b. A previous bound of 2 was shown without weights in (Chaudhuri et al., 2011) 1), and under our weighting scheme we show that it's necessary to adjust that bound to b - b'll2 I 3, and to adjust the algorithm accordingly. Here we offer an intuitive sketch of the key idea. Recall that
4.2.1. WEIGHTED PRIVATE ERM
Standard Empirical Risk Minimization (ERM) trains model by minimizing average loss function over dataset, i.e., optimizing parameters of some model class to reduce the gap between predicted and true data values (Vapnik, 1991; Devroye et al., 2013). Many cost-sensitive approaches to class imbalance rely on sample-weighted objective mini- mization in the ERM framework, where the minority class samples are wp-weighted in the loss function relative to the sample majority (Tang et al., 2008). We show in Theorem 5 that the differentially private empirical risk minimization (ERM) procedure of (Chaudhuri et al., 201 1) can be adapted to accommodate such minority sample weights, which we outline in Algorithm 1. Weighting samples in the objective function allows us to tune the impact of the minority class on the final model parameters.
ensures privacy by adding a ran- dom linear term b T /3 whose scale matches the sensitivity of the weighted loss. When one minority label flips between neighboring datasets, the class proportions, and hence the sample weights, change by at most 1/n. This perturbs the weighted empirical risk by (1/nn) ) in &g norm, and thus we show that we can retain privacy by inflating the noise radius from 2 (standard ERM) to 3. Importantly, the convexity and smoothness of the loss still guarantee a unique minimizer, and the optimization landscape remains well-behaved. A full proof, with all the necessary adjustments and details introduced by the weighting, is deferred Appendix C.
Theorem 5. Algorithm I instantiated with a loss function C(y, n) that is convex and twice differentiable with respect 8² to n. with lay fly. n)l S 1 and 1op fly, 7)) S c.ror all y. is e-differentially private.
We instantiate Algorithm I with the weight function W(D) as the inverted class frequency for each sample in our experiments in Section 5. More formally, for a dataset
6

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Although our theoretical (and empirical in Section 5) re- sults focus a logistic regression ERM algorithm, our results directly apply to the kernel method and SVM given in (Chaudburi et al., 201 Surprisingly, no adaptation of private ERM under sample weights was previously known; (Giddens et al., 2023) had recently considered the problem for more complicated weighting schemes, but under some undesirable assumptions (more on this in Appendix C.3).
weights (Priv. Weighted LogReg, Algorithm 1, Section 4.2 i.e. private ERM under class weighting), and (4) an in-processing DP-SGD-trained FTTransformer model (Huang et al., 2020) with sample-weighted cross-entropy loss (Priv. Weighted FTT, Algorithm 4, Section 4.3). Note that we defer some additional visualizations that help build intuition for the effect of private noise on each classifier's decision boundary (using synthetic data) to Appendix D.2, along with complete results and details (Section E).
4.3. Weighted DP-SGD
5.1. Philosophy: Pipelines, not Isolated Models
Competitive approaches to many private classification prob- lems are given with deep learning models, often tuned using variant of the differentially private stochastic gradient de- scent (DP-SGD) algorithm (Bassily et al., 2014; Abadi et al., 2016) (canonical version given in Algorithm 4, but with weighted cross cross-entropy loss). DP-SGD follows an iterative process of sampling mini-batches of the data, computing gradients on the sampled points, clipping the gradients to have a bounded εz-norm to reduce sensitivity, adding noise that scales with e and the clipping parameter to preserve privacy, and finally updating the model using the resulting clipped noisy gradients.
Throughout the empirical component of this work we con- sider the overall learning pipeline, that couples a privacy mechanism with the downstream model best suited to that mechanism. DP mechanisms are never deployed in a vac- uum: their performance depends strongly on how they are paired with downstream architectures, optimization routines, and hyperparameter regimes. In particular, our philosophy is motivated by three observations: (1.) Synthetic-data gen- erators decouple privacy from prediction, so their natural partner is strong non-private tabular learner (e.g. boosted trees). (2.) Weighted DP-SGD is expressly tuned for deep networks; foreing it onto a linear model would artificially depress its performance.
For cost-sensitive gradient updates under class imbalance, it is straightforward to show that weights can be incorpo- rated into a standard binary classification loss L(y: ú; w) (e.g. cross-entropy) while maintaining privacy. Proposi- tion 6 formalizes this claim, with the simple proof deferred to Appendix D. It's worth noting, however, that incorporat- ing weights may alter the per-sample gradients in ways that complicate naive sensitivity arguments. In Appendix D. we provide a refined analysis (Lemma 19) showing that the overall gradient sensitivity in the weighted setting can be bounded by 2C/ B, ensuring the same privacy guarantees where here B denotes the DP-SGD mini-batch size.
(3.) Prior DP benchmarks (Ja- yaraman & Evans, 2019; Suriyakumar et al., 2021) like- wise compare methods in their most effective configura- tions. Accordingly, the atomic unit of comparison is the pipeline: DP mechani sm, intermediate data, a, final predictor ). Table 1 should be interpreted as comparing best-effort pipelines under a common (c, 8) bud- get, rather than as an architecture-contrllled ablation.
5.2. Evaluations on Real Data
We next empirically evaluate the performance of our meth- ods for private binary classification under class imbal- anced data using eight datasets from the Imbalanced (Lemaitre et al., 2017) repository. These datasets represent a variety of settings, with imbalance ratios r E [8.6, 130] and sizes n E [336, 11183]; see Table 11 for complete details.
Proposition 6. Algorithm 4, a standard DP-SGD procedure with weighted cross-entropy loss given by Cly (:w)- = - Ei= ws [y, log(ū.) + (1 - y:) log(1 0.)], (c, -ddiffrrnnnl private.
5. Experiments
In Figure 1, we show how performance varies with privacy level; our performance metrics include general metrics like AUC, F1, and Precision, as well as metrics that are more tailored to imbalanced classification, such as Recall, Worst Class Accuracy etc. The macro-average accuracy (Maero- Avg-ACC) helps evaluate performance across both classes without bias toward the majority class, while the geometric mean (G-Mean) balances sensitivity and specificity. Higher is better for all metrics. Figure 1 presents results on the mammography dataset, which was representative of general trends for all datasets. Complete plots are presented in Figures 6 to 13 in Appendix E.
We evaluate methods under varying privacy and class imbalance conditions on real datasets from the imblearn (Lemaitre et al., 2017) repository, with imbalance ratios r E [8.6, 130] and sizes n E [336, 1 11183] (full summary in Table 11, deferred Appendix E). For private classifiers, we evaluate (1) GEM as a pre-processing step to generate balanced synthetic data for prr-private XGBoost model (GEM- + NonPriv. XGBoosi, Algorithm 3, Section 3.3), (2) a private in-processing ERM logistic regression model without class weights (Priv. LogReg, (Chaudhuri et al., 2011), Section 4.2), (3) a private in-prccessing ERM logistic regression model with sample
7

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Table 3: Average performance rankings of the DP imbal- anced learning approaches, across all e settings and datasets. Average ranks are in [1, 4] and in descending order, so lower is better. We adopt the Olympic medal convention: gold silver and bronze cells signify first, second and third best performance, respectively.
Figure I: Performance for mammography dataset for over- all performance metrics (AUC, F1, Balanced Accuracy, Precision) and metrics appropriate for imbalanced clas- sification settings (Recall, Worst Class Accuracy, Macro Average Accuracy, Geometric Mean) under varying e {0.05, 0.1, 0.1, 0.5, 1.0, 5.0} and over 10 random initializations.
AUC
1.0
Model
AUC
F1
Bal-ACC
Precision
GEM XGiBoost
1.45
1.45
1,48
1.45
Priv. LogReg
2.77
2.62
2.89
2.62
0.5
Priv. Weighted LogReg
3.19
2.65
2.59
2.65
Weighted FTT
2,89
3.34
0.0
Recall
Worst-ACC
Macro-ACC
G-Mean
Balanced Acc.
Precision
GEM XGBoost
2.26
1.45
1,48
1.45
1.0
Priv. LogReg
2,20
2.89
2.89
2. 2.86
Priv. Weighted LogReg
2.11
2.59
2.59
2.59
0.5
Priv. Weighted FTT
3.70
3.37
3,34
3.40
Varying Privacy Budget We observed that for all datasets, the GEM+XGGBost method improved with increased pri- vacy budget. Figure 1 presents results on the manmography dataset, which is representative of general trends. Higher dimensionality increased the difficulty across the board (e.g., there was a larger difference between non-private performance and private performance with, for example, the ear_ ear_eval_+ 44 dataset (Figure 10)), but we did not find meaningful trend or interaction between imbalance ratio and dimensionality. Absolute dataset size correlated with the classification performance, expected. Complete plots are presented in Figures 6-13 in Section E.
Recall
Worst Class Acc.
1.0
0.5
0.0
Macro Avg. Acc.
G-Mean
1.0
0.5
0.0
10
10"
10-1
10"
GEM + NonPriv. XGBoost
Priv. Weighted FTT
Priv. LogReg
Best Non. Priv.
Additionally, in our experiments, we found that more minor- ity examples led to more stable improved performance from the GEM+XGBoost model. For example, the mammogra- phy (Figure 1) and abalone (Figure 13) datasets, both of which have the highest number of minority class examples, also exhibited the best performance for the GGBoxt synthesizer at low levels of epsilon, and the most stable performance overall across varied privacy parameters.
Priv. Weighted LogReg
Empirical Takeaways. Private variants of neural models (Priv. Weighted FTT, for example) may be inappropriate in general for relatively low-data regimes under class im- balance due to minority example sparsity, especially when weighted ERM based methods like Priv. Weighted LogReg perform well and are less expensive to train. Moreover, pre-processing with private synthetic data (GEM + Non- Priv. XGBoost) displayed the most robust performance across varying privacy levels and imbalanced datasets in our experiments, consistently ranking highest across nearly all metrics. Unfortunately, DP data synthesis is limited to din-dimensional datasets (Rosenblatt et al., 2022). Priv. Weighted LogReg performed best in terms of Recall, and performed second best on average in terms of the other im- balanced classification metrics. Our empirical results lead us to recommend these two methods, pre-processing with private synthetic data or weighted ERM based methods, depending on chosen metric or data context.
In Table 3, we present average rankings across all datasets imbal-
and epsilon values for the four privacy-preserving anced learning approaches we explore; here, lower is better, and highest average performance in each row is highlighted according to the Olympic medal convention (gold, silver, bronze). GEM + XGBoost performs best, ranking highest across 7 of the 8 metrics on average. As expected, Priv. Weighted LogReg performs worse than its unweighted coun- terpart on overall metries. Overall metrics are well known to be poor indicators in imbalanced learning, as many of them weight negative and positive class performance equally (He & Garcia, 2009). However, on the metrics more appropriate for imbalanced classification, Priv. Weighted LogReg outper- forms the unweighted variant in 3 out of 4 metrics, and has the best average Recall among all private models. In stark contrast, Priv. Weighted FTT consistently peder-performed.
Explaining GEM's Strong Performance One plausible explanation for GEM's strong performance is rooted well-
8

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
studied properties of differentially private synthetic data generation (Tao al., 2021; McKenna et al., 2022; Qian et al., 2024). In particular, DP synthetic data algorithms rely heavily on k-way counting queries, which are precisely the kinds of aggregate statistics that differential privacy is designed to protect and measure accurately. By focusing on low-dimensional correlations and co-oceurrence relation- ships which may be sufficient for many classification tasks (Hollmann et al., 2025)- GEM can capture and preserve essential structure in the data with high fidelity. Moreover, class-conditional sampling allows GEM to up-sample mi- nority classes similarly to SMOTE, mitigating imbalance at its root. While a formal theory to explain these phenom- ena would likely require distributional assumptions and an extensive theoretical framework, our experiments suggest these capabilities help explain GEM's performance.
prove private classification. Hybrid methods that leverage DP synthetic data in lower-dimensional embeddings before training a weighted ERM model also warrant exploration. We hope our initial findings prompt broader theoretical and empirical advances in private imbalanced classification.
Impact Statement
Learning algorithms are deployed more and more in sensi- tive domains, such as healthcare and finance, necessitating algorithms that ensure data privacy, particularly in the pres- ence of class imbalance (for example, when fairness or equity are a concern). Our work highlights the challenges of applying standard imbalanced learning techniques in differ- entially private settings, identifying both algorithmic tools that work and those that do not. We believe that combin- ing DP techniques with imbalanced classification strategies can lead to the safeguarding of andivddual-eevd information while maintaining strong predictive performance in high stakes settings. Nonetheless, deploying these approaches in practice would require careful consideration of the domain constraints, and likely some collaboration with policymak- ers and other stakeholders ensure responsible use.
6. Conclusion and Future Work
Private binary classification under class imbalance is espe- cially challenging. We showed that standard non-private methods like SMOTE and bagging become ill-suited for DP, largely because they inflate the downstream privacy loss. By contrast, private weighted ERM and DP private synthetic data generation approaches can preserve privacy and yield good performance, although DP synthetic data methods suf- fer from the curse of dimensionality, which is a significant limitation in most practical settings (McKenna et al., 2019; Rosenblatt et al., 2022).
Acknowledgements
Y.L. was supported in part by NSF grant 2138834 (CAREER). M.A.M. was supported in part by NSF grant DMS-2310973, R.C. was supported in part by NSF grants CNS-2138834 (CAREER) and IIS-2147361. L.R. was sup- ported by the NSF under GRFP Grant No. DGE-2234660.
While our study focused on binary classification (a com- mon setting in fraud detection, rare-disease diagnosis, spam filtering, etc.), many of our ideas naturally extend to mul- tiple classes. Pre-processing, SMOTE, Proposition 2 and Theorem 3 depend on the fac- tor [N/m1], i.e. the maximum number of synthetic sam- ples per real minority point. In the multiclass setting we could simply replace this by [N analyze each class independently, and take the worst-case bound. in-processing. Weighted ERM admits multinomial logis- tic regression with categorical cross-entropy; the convex- ity assumptions required by Theorem 5 continue to hold. Likewise, DP-SGD uses the same gradient-clipping routine with a softmax loss, so the sensitivity bound of Lemma 19 carries over verbatim. Synthetic data. GEM and other Se- -e--MeeuuurePPoeee synthesizers already model the joint distribution of all attributes; conditioning on categorical target variable merely changes the sampling query. With these natural extensions in mind, we leave a rigorous end- to-end evaluation of multiclass performance to future work.
For oversampling or
References
Abadi, M.. Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Analytics, P. Twitter study august 2009, 2009. http:// pearanalytics com/ 2012/12/1witter- http::iittettttttt-teee (accessed on 2022-08-24).
/uploads/ pdf,
Aydore, S., Brown, W., Kearns, M., Kenthapadi, K., Melis, L., Roth, A., and Siva, A. A. Differentially private query release through adaptive projection. In International Conf on Machine Learning, pp. 457-467. PMLR, 2021.
Bagdasaryan, E.,, Poursaeed, O., and Shmatikov, V. Differ- ential privacy has disparate impact on model accuracy. Advances in neural information processing systems, 32, 2019.
In addition, there are ample open questions about the inter- play between differential privacy and imbalanced learning. New imbalanced-learinee -earning-ppecificc loss functions (Cui et al., 2019; Cao et al., 2019; Li et al., 2021) might further im-
Bassily, R., Smith, A., and Thakurta, A. Private empirical

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foun- dations of computer science, pp. 464-473. IEEE, 2014.
Practice of Knowledge Discovery in Databases, Caviat- Dubrovnik, Croatia, September 22-26, 2003. Proceedings 7. pp. 107-119, Springer, 2003.
Bauer, E. and Kohavi, R. An empirical comparison of voting classification algorithms: Bagging, boosting, and variants. Machine learning. 36:105-139, 1999.
Chawla, N. V., Japkowicz, N., and Kotez, A. Special issue learning from imbalanced data sets. ACM SIGKDD explorations newsletter, 6(1):1-6, 2004.
Biswas, S., Dong, Y., Kamath, G.. and Ullman, J. Coin- press: Practical private mean and covariance estimation. Advances in Neural Information Processing Systems, 33: 14475-14485, 2020.
Chen, T. and Guestrin, C. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd inter- national conference on knowledge discovery and data mining, pp. 785-794, 2016.
Boedihardjo, M., Strohmer, T., and Vershynin, R. Private sampling: noiseless approach for generating differen- tially private synthetic data. SIAM Journal on Mathemat- ics of Data Science, 4(3):1082-11) 111,, 2022.
Cheng, V., Suriyakumar, V. M., Dullerud, N., Joshi, S., and Ghassemi, M. Can you fake until you make it? impacts differentially private synthetic data on down- stream classification fairness. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Trans- parency, pp. 149-160, 2021.
Branco, P., Torgo, L., and Ribeiro, R. P. A survey of predic- tive modeling on imbalanced domains. ACM computing surveys (CSUR), 49(2):155,, 2016.
Cui, Y., Jia, M., Lin, T.-Y., Song, Y. and Belongie, S. Class- balanced loss based effective number of samples. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 9268 0888-9977,288 2019.
Breiman, L. Bagging predictors. Machine learning, 24: 123-140, 1996.
Bun, M., Nissim, K., Stemmer, U., and Vadhan, S. Differen- tially private release and learning of threshold functions. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 634 649. IEEE, 2015.
Devroye, I.., Györfi, L., and I Lugosi, G. A probubilistic the- ory of pattern recognition, volume 31. Springer Science & Business Media, 2013.
Bun, M., Drechsler, J., Gaboardi, M., McMillan, A., and Sarathy, J. Controlling privacy loss in sampling schemes: An analysis of stratified and cluster sampling. In 3rd Symposium on Foundations of Responsible Computing (FORC 2022), 2022.
Dwork, C. and Lei, J. Differential privacy and robust statis- tics. In Proceedings of the 4 ACM Symposium on Theory of Computing, STOC '09, 2009.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrat- ing noise to sensitivity in private data analysis. Theory of cryptography conference, pp. 265-284, Springer, 2006.
Cai, K., Lei, X., Wei, J., and Xiao, X. Data synthesis via differentially private markov random fields. Proc. of the VLDB Endowment, 14(1) ((11))2190-2200) 2021.
Dwork, C., Roth, A., et al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theo- retical Computer Science, 9(3-4):21 11:22711107,, 2014.
Cao, K., Wei, C., Gaidon, A., Arechiga, N., and Ma,
T. Learning imbalanced datasets with ditti-nistribution- aware margin loss. Advances in neural information pro- cessing systems, 32, 2019.
Farrand, T., Mireshghallah, F,, Singh, S., and Trask, A. Neither private nor fair: Impact of data imbalance on utility and faimess in differential privacy. In Proceedings of the 2020 Workshop Learning in Practice, pp. 15-19, 2020.
Chaudhuri, K., Monteleoni, C.,, and Sarwate, A. D. Differ- entially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Machine
Chawla, N. V., Bowyer, K. W., Hall, L. O., and Kegelmeyer, W. P. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 16:321-357, 2002.
Fernández, A., Garcia. S., Herrera, F., and Chawla, N. V. Smote for learning from imbalanced data: progress and challenges, marking the 15-year anniversary. Journal of artificial intelligence research, 61:863-905, 2018.
Chawla, N. V., Lazarevic, A., Hall, L. O., and Bowyer, K. W. Smoteboost: Improving prediction the minority class in boosting. In Knowledge Discovery in Databases: PKDD 2003: 7th European Conference on Principles and
Ficek, J., Wang, W., Chen, H., Dagne, G., and Daley, E. Differential privacy in health research: A scoping review. Journal of the American Medical Informatics Association, 28 28(10):2269 22762227662222 2021.
10

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Fletcher, S. and Islam, M. Z. Differentially private random decision forests using smooth sensitivity. Expert systems with applications, 78: 16-31, 2017.
Jaiswal, M. and Provost, E. M. Privacy enhanced multi- modal neural representations for emotion recognition. In Proceedings of the AAAI Conference Artificial Intelli- gence, volume 34, pp. 7985-795599 0993, 2020.
Galar, M., Fernandez, A., Barrenechea, E., Bustince, H., and Herrera, F. A review ensembles for the class im- balance problem: bagging-, boosting- and hybrid-based approaches. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 42(4): 463 484, 2011.
Jayaraman, B. and Evans, D. Evaluating differentially pri vate machine learning in practice. In 28th USENIX Secu- rity Symposium (USENIX Security 19), pp. 1895-1912, 2019.
Jenssen, M., Joos, F., and Perkins, W. On kissing numbers and spherical codes in high dimensions. Advances in Mathematics, 335:307-321, 2018.
Ganev, G., Oprisanu, B., and De Cristofaro, Robin hood and matthew effects: Differential privacy has disparate impact on synthetic data. In International Conference on Machine Learning, pp. 6944-6959, PMLR, 2022.
Johnson, J. M. and Khoshgoftaar, T. M. Survey on deep learning with class imbalance. Journal of Big Data, 6(1): 1-54, 2019.
Giddens, S., Zhou, Y., Krull, K. R., Brinkman, T. M., Song, P. X., and Liu, F. A differentially private weighted empirical risk minimization procedure and its appli- cation to outcome weighted learning. arXiv preprinl arXiv:2307.13127, 2023.
Jordon, J., Yoon, J., and van der Schaar, M. Differentially private bagging: Improved utility and cheaper privacy than subsample-and-aggreghl Advances in Neural In- formation Processing Systems, 32, 2019.
Gong, M., Xie, Y., Pan, K., Feng, K., and Qin, A. K. A survey on differentially private machine learning. IEEE computational intelligence magazine, 15(2):49-66) 64, 2020.
Jorgensen, Z., Yu, T., and Cormode, G. Conservative or liberal? personalized differential privacy. In 2015 IEEE 31SI international conference on data engineering, pp. 1023-1034, IEEE, 2015.
Gorishniy, Y., Rubachev, I., Khrulkov, V., and Babenko, A. Revisiting deep learning models for tabular data. Ad- vances in Neural Information Processing Systems, 34: 18932-18943, 2021.
Kabatiansky, G. and Levenshtein, V. I. On bounds for packings on sphere and in space. Problemy peredachi informatsti, 14(1):3-25, 1978.
Haixiang, G., Yijing, L.. Shang, J., Mingyun, G., Yuanyue, H., and Bing, G. Learning from class-imbalanced data: Review of methods and applications. Expert systems with applications, 73:220-255 22992920292202 2017.
Karakoulas, G. and Shawe- Taylor, J. Optimizing classifers for imbalanced training sets. Advances in neural infor- mation processing systems, 11, 1998.
Hardt, M., Ligett, K., and McSherry, A simple and practical algorithm for differentially private data release. Advances in neural information processing systems, 25, 2012.
Khan, S., Naseer, M., Hayat, M., Zamir, S. W., Khan, F. S., and Shah, M. Transformers in vision: A survey. ACM computing surveys (CSUR), 1110)) 2022.
Kifer, D. and Machanavajihala, A. No free lunch in data pri- vacy. In Proceedings of the 2011 ACM SIGMOD Interna- tional Conference on Management of data, pp. 193-204, 2011.
Hart, E... Stork, D. G., Duda, R. O., al. Pattern classifi- cation. Wiley Hoboken, 2000.
He, H. and Garcia, E. A. Learning from imbalanced data. IEEE Transactions on knowledge and data engineering, 21(9):1263-1288) 2009.
Krawezyk, B. Learning from imbalanced data: open chal- lenges and future directions. Progress in A Artificial Intelli- gence, 5(4):221-232, 2016.
Hollmann, N., Müller, S., Purucker, L.., Krishnakumar, A., Körfer, M., Hoo, S. B., Schirrmeister, R. T., and Hutter, F. Accurate predictions on small data with a tabular foundation model. Nature, 637(8045)33193322 2025.
Kulesza, A., Suresh, A. T., and Wang, Y. Mean estimation in the add-remove model of differential privacy. arXiv preprint arXiv:2312.06653. 2023.
Huang, X., Khetan, A., Cvitkovic, M., and Karnin, Z. Tab- transformer: Tabular data modeling using contextual em- beddings, 2020.
Lau, A. and
J. Statistical privacy guaran- tees of machine learning preprocessing techniques. arXiv preprint arXiv:2 109.02499 2021.

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Lemaitre, G., Nogueira, F., and Aridas, C. K. Imbalanced- lear:: A python toolbox to tackle the curse of imbalanced datasets in machine learning. Journal of machine learning research, 18(17)11-5, 2017.
Provost, F. and Fawcett, T. Analysis and visualization of
classifier performance: Comparison under imprecise class and cost distributions in: Proc of the 3rd international con- ference on knowledge discovery and data mining, 1997.
Li, M., Zhang, X., Thrampoulidis, C., Chen, J., and Oymak, S. Autobalance: Optimized loss functions for imbal- anced data. Advances in Neural Information Processing Systems, 34:3163-3177, 2021.
Pujol, D., McKenna. R., Kuppam, S., Hay, M., Machanava- ijhala, A., and Miklau, G. Fair decision making using Privacy-protectte data. In Proceedings of the 2020 Con- ference on Fairness, Accountability, and Transparency, pp. 189-199, 2020.
Liu, H., Jia, J., and Gong, N. Z. On the intrinsic differential privacy of bagging. arXiv preprint arXiv:2008.0940 09845, 2020.
Qian, Z.,, Davis, R., and van der Schaar, M. Synthcity: benchmark framework for diverse cases of tabular synthetic data. Advances in Neural Information Process- ing Systems, 36, 2024.
Liu, T., Vietri, G., and Wu, S. Z. Iterative methods for pri- vate synthetic data: Unifying framework and new meth- ods. Advances in Neural Information Processing Systems, 34:690-702. 0009000--2220 2021. 2021.
Redberg, R., Koskela, A., and Wang, Y.-X. Improving the privacy and practicality of objective perturbation for differentially private linear leamners. Advances in Neural Information Processing Systems, 36, 2024.
López, V., Fernández, A., Gareía, S., Palade, V., and Herrera, F. An insight into classification with imbalanced data; Empirical results and current trends on using data intrin- sic characteristics. Information sciences, 250: 13-141, 2013.
Rigollet, P. and Hütter, J.-C. High-dimensional statistics. arXiv preprint arXiv:2310. 19244, 2023.
Rigollet, P. and Tong, X. Neyman-Pearson classification,
convexity and stochastic constraints. Journal of Muchine Learning Research, 2011.
Makki, S., Assaghir, Z., Taher, Y., Haque, R., Hacid, M.- S., and Zeineddine, H. An experimental study with im- balanced classification approaches for credit card fraud detection. JEEE Access. 7:93010-93098 930022 2019.
Rosenblatt, L., Liu, X., Pouyanfar, S., de Leon, E., Desai, A., and Allen, J. Differentially private synthetic data: Ap- plied evaluations and enhancements. arXiv:2011.055:: 2020.
McKenna, R., Sheldon, D., and Miklau, G. Graphical modeel based estimation and inference for differential privacy. In International Conf on Machine Learning, pp. 4435-4444. PMLR, 2019.
Rosenblatt, L., Holovenko, A., Rumezhak, T., Stadnik, A., Herman, B., Stoyanovich, J., and Howe, B. Epistemic parity: Reproducibility as an evaluation metric for differ- ential privacy. arXiv:2208. 12700, 2022.
McKenna, R., Mullins, B., Sheldon, D., and Miklau, G. Aim: An adaptive and iterative mechanism for differentially private synthetic data. arXiv preprint arX1v.2201.12677, 2022.
Rosenblatt, L.,, Herman, B., Holovenko, A., Lee, W., Loftus, J., McKinnie, E., Rumezhak, T., Stadnik, A., Howe, B., and Stoyanovich, J. Epistemic parity: Reprodueibility as an evaluation metric for differential privacy. ACM SIGMOD Record, 53(1):65-744 2024a.
Menon, A., Narasimhan, H., Agarwal, S., and Chawla, S. On the statistical consistency of algorithms for binary classification under class imbalance. In International Conference on Machine Learning, pp. 603-611. PMLR, 2013.
Rosenblatt, L., Stoyanovich, J., and Musco, C. A simple and practical method for reducing the disparate impact of dif- ferential privacy. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 21554 21562, 2024b.
Moniz, N., Branco, P., and Torgo, L.. Evaluation of ensemble methods in imbalanced regression tasks. In First Interna- tional Workshop on Learning with Imbalanced Domains: Theory and Applications, pp. 140- PMLR, 2017.
Scott, C. Calibrated asymmetric surrogate losses. Elec- tronic Journal of Statistics, 6(none):958 - 992, 2012. doi: 10.1214/12-EJS699, URL https: //doi. org/10. 1214/12-EJS69
Musin, O. R. The kissing number in four dimensions. An- nals of Mathematics, pp. 1 1-32, 2008
Papernot, N. and Steinke, T. ing with renyi differential privacy. arXiv preprint arXiv:2/ 10.03620, 2021.
Hyperparameter tun-
Singh, R., Ahmed, T., Kumar, A., Singh, A. K., Pandey, A. K., and Singh. S. K. Imbalanced breast cancer classifi- cation using transfer learning. JEEE/ACM transactions on
12

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
computational biology and bioinformatics, 18(1):83-93, 2020.
Wang, S. and Yao, X. Diversity analysis imbalanced data sets by using ensemble models. In 2009 IEFE symposium computational intelligence and data mining, pp. 324- 331. IEEE, 2009.
Sun, C., van Soest, J., and Dumontier, M. Improving correlation capture in generating imbalanced data using differentially private conditional gans. arXiv preprint arXiv:2206. 13787, 2022.
Wang, Y.-X., Lei, J., and Fienberg, S. E. A mini- max theory for adaptive data analysis. arXiv preprint /002.v6602.40000 2016.
Sun, Y., Wong, A. K., and Kamel, M. S. Classification of imbalanced data: A review. International journal of pattern recognition and artificial intelligence, 23(04): 687-719, 2009.
Wang. Y.-X., Balle, B., and Kasiviswanathan, S. P. Subsam- pled rényi differential privacy and analytical moments accountant. In The 22nd International Conference on Ar- tificial Intelligence and Statistics, pp. 1226-1235. PMLR, 2019.
Sun, Z., Song, Q. Zhu, X., Sun, H., Xu, B., and Zhou, Y. A novel ensemble method for classifying imbalanced data. Putlern Recognition, (8(5):1623-11
2015.
Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, P., Rault, T., Louf, R.. Funtowiez, M.. et al. Transformers: State-of-the-ait natural language processing. In Proceedings of the 2020 conference on em- pirical methods in natural language processing: system demonstrations, pp. 38-45, 2020.
Suriyakumar, V. M., Papernot, N., Goldenberg, A., and Ghassemi, M. Chasing your long tails: Differentially private prediction in health care settings. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pp. 723-734, 2021.
Tang, Y., Zhang, Y.-Q.. Chawla, N. V., and Krasser, S. Syms modeling for highly imbalanced classification. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), (9)1):281-288 2008.
Wyner, A. D. Capabilities of bounded discrepancy decoding. Bell System Technical Journal, 44(6):1061-1122 1965.
Xu, D., Du, W., and Wu, X. Removing disparate impact of differentially private stochastic gradient descent model accuracy. arXiv preprint arXiv:2003.0366 2020a.
Tao, Y., McKenna, R., Hay, M., Machanavajjhala, A., and Miklau, G. Benchmarking differentially private synthetic data generation algorithms. arXiv preprint mxXiv2212.009233 2021.
Xu, Z., Dan, C., Khim, J., and Ravikumar, P. Class-weighted classification: Trade-offh and robust approaches. In In- ternational Conference on Machine Learning, pp. 10544- 10554. PMLR, 2020b.
Tay, Y., Dehghami, M., Bahri, D., and Metzler, D. Efficient transformers: A survey. ACM Computing Surveys, 55(6): 1-28, 2022.
Yang. Y. and Xu, Z. Rethinking the value of labels for improving class-imbalanced learning. Advances in neural information processing systems, 33:19290-19301, 2020.
Tong, X. A plug-in approach Neyman-Pearse Peanssn classifica- tion. The Journal of Machine Learning Research, 14(1): 3011-3040, 2013.
Yousefpour, A., Shilov, I., Sablayrolles, A., Testuggine, D., Prasad, K., Malek, M., Nguyen, J., Ghosh, S., Bharadwaj. A., Zhao, J., Cormode, G., and Mironov, Opacus: User- friendly differential privacy library in PyTorrh. arXiv preprint arXiv:2 12298, 2021.
Tran, C., Dinh, M., and Fioretto, F. Differentially private empirical risk minimization under the faimess lens. Ad- vances in Neural Information Processing Systems, 34: 27555-27565, 2021.
Ueda, N. and Nakano, R. Generalization error of ensemble estimators. In Proceedings of International Conference on Neural Networks (ICNN"96) 96),, volume 1, pp. 90-95. IEEE, 1996.
Yuan, X., Xie, L., and Abouelenien, M. A regularized ensemble framework of deep learning for cancer detec- tion from multi-class, imbalanced training data. Pattern Recognition, 77:160-172, 2018.
Vapnik, V. Principles of risk minimization for learning the- ory. Advances in neural information processing systems, 4, 1991.
Zhang, J. Cormode, G., Procopiuc, C. M., Srivastava, D., and Xiao, X. Privbayes: Private data release via bayesian networks. ACM Transactions on Database Sys- tems (TODS), 42(4): 41, 2017.
Vietri, G., Tian, G., Bun, M., Steinke, T., and Wu, S. New oracle-efficient algorithms for private synthetic data re- lease. In International Conf on Machine Learning, pp. 9765-9774. PMLR, 2020.
Zhang, Z., Wang, T., Honorio, J., Li, N., Backes, M., He, S., Chen, J., and Zhang, Y. Privsyn: Differentially private data synthesis. 2021.
13

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Zhou, Z. and Liu, X.-Y. Training cost-sensitive neural networks with methods addressing the class imbalance problem. IEEE Transactions on knowledge and data engineering, 18(1):63-77, 2005.
14

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
A. Deferred Preliminaries
In this section, we provide some standard preliminaries for DP mechanisms that were deferred for length. One well-known technique for achieving (c. OD-DP is by adding Laplace noise. The Laplace distribution with scale b the distribution with probability density function: (=(==6) = 25 exp( ).). ). The Laplace Mechanism of (Dwork et al., 2006) takes in a real-valued function f, a database D, and a privacy parameter and produces the (random) output: f(D) + Lf/c.. For the Laplace mechanism, the sensitivity of real-valued function f is defined as: A maXacighhors D.D (f(D) - f(D")).
Additionally, here formal statements of two key theorems in differential privacy. Composition (Theorem states that applying differentially private algorithms sequentially results in combined privacy guarantees of (e1 + 62, + 62). Post-processing (Theorem 8) notes that any post-processing of the output of differentially private mechanism preserves its original privacy guarantees.
Theorem 7 (Basic Composition (Dwork et al., 2006)). Let Mi be algorithm that is (Ei, (1)-DP,, and let M2 be an algorithm that is (E2, DD. Then their composition (M1,M2) is (c1 + 62, - DD.
Theorem 8 (Poss-processing (Dwork al., 2006)). Let M D R be algorithm that is e-differentially private, and let f: R R' be an arbitrary function. Then f c M: : 'D + R' is c-differentially private.
15

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
B. Pre-processing Methods and Analysis
Algorithm 2 SMOTE(X,, NN, k) (Chawla et al., 2002)
Input:
minority class instances X1 = (.1,....40 J. dataset dimension d, number of points to be generated N, number of
nearest neighbors k.
2 Output: N synthetic minority class samples
for I....,7 do
3 Compute & nearest &2 neighbors of æt from X1: (ar) (...-..., x.)
end for
for 1. ,,..,,NN N do
4
= f mod n, where 0 mod n is interpreted as n
5 Randomly choose x4, one of the & nearest neighbors of æ;;
for -,.... d do
6 Sample u, uniformly from [0, 1]
7
St.j = (1 uy u + uj vij
end for
8 return (zt:1 1)
end for=0
B.1. SMOTE
Before offering the complete proof of the SMOTE result (Theorem 3), we provide a brief sketch to help guide the reader. We first define the quantity Y = |SMOTE N, k) e SMOTE(X', N, k)] which gives the symmetric difference between SMOTE applied to two neighboring datasets X, X', where @ denotes symmetric difference. Y can be fully described as a sum of Bernoulli random variables with parameters that depend on k, N, ni, and the maximum number of times one point from Rd can appear among k-nearest neighbors of other points from Rd. SMOTE only takes in the minority class data, and does not use majority class data at all in generating new synthetic data. Thus, without loss of generality, Theorem 3 only considers the modification of a minority class example that has positive label; if the minority class was actually the negative label, this could be dealt with in the analysis simply by renaming.
Now, to bound the maximum number of times one point can appear among k-nearest neighbors of other points, denoted ld, k),, we require Lemma 9. This lemma lower bounds 1(d, k)) via a geometric argument that relies on the notion of kissing number K (d), defined as the greatest number of equal non-overlapping spheres in RRd that can touch another sphere of the same size (Musin, 2008; Jenssen et al., 2018).
Lemma 9. Let ((d, k) be the maximum number of times one point from Rd can appear among the k-nearest neighbors of n4 other points from Rd. Then, t(d, k) min(k- K(d), n1)-
The exact value of the kissing number ((d) for general is an open problem, but is known to be asymptotically bounded by k-20.207540 2075)((+((() I(d, k) < 1:20/1 (Wyner, 1965; Musin, 2008; Kabatiansky & Levenshtein, 1978). Returning Y, then apply one-sided Chernoff bound constraining the probability that Y is much greater than its mean. Plugging in Lemma 9 and appropriate parameters yields Theorem 3.
Now, for the formal proof, following a restatement of Theorem 3.
Theorem 3. Let D (X,y) be a d-dimensional datasel, with nı minority instances, and let M be an arbitrary e-DP algorithm. Then instantiating M on D) concatenated with the output SMOTE(X, N, k)) is both (c(20/1012d) N [+1)) DDDP and (c,8)-DD DDD. for any 7 2 and for.
mi
c [ 722 4042d
INT
8 [(काग (<-xr==)
400.4 N
22
n1
k'
Proof. Let D = (X, and D' = (X', be two neighboring datasets such that D' = DU ((r 1)}. and let M be an arbitrary cDP algorithm. For the remainder of the proof, fix SMOTE parameters N E N and Z+. Define [(d, k) to be the maximum number of times one point from &d can appear among the k-nearest neighbors of an arbitrary set of other points in R.d To simplify notation, we may denote l(d, k) as simply I when d and & are clear from context.
16

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
To compare the outputs of SMOTE(X, N, and SMOTE(X", N, k), we fix the internal randomness of SMOTE between these two runs, which includes randomly choosing nearest neighbor and randomly sampling inside the for-loop. That is, an output point will be different only if the new point in X' replaces the selected nearest neighbor a that was chosen under X. For each iteration where x replaces a previous nearest neighbor, there is 1 probability that x is the selected nearest neighbor.
Define the random variable = NN, e SMOTE(X', N)), where @ denotes a symmetric difference. Then Y can be described as the sum of independent Bernoulli random variables that are if x is the selected k-nearest neighbor. Each trial has success probability 1/k, and there are { A total trials, corresponding to the ( datapoints that can be mi
neighbors to z and the N iterations through the database. For simplicity of presentation, we drop the ceiling notation for I.N ni
the remainder of the proof, but it is implied if N not divisible by #1. Thus Binomial
L:N 70: 1/k) and E[
Note that using the upper bound Y S we can obtain an immediate DP guarantee for M applied to the output of SMOTE using group privacy. Specifically, since Y s LN the output of SMOTE, which is equivalent to changing LN + 1 entries of the input to M (since the imput to M is the original ai
n,, we know that changing one entry of X would change up to IN entries of
database X concatenated with the output of SMOTE). Thus by the group privacy property of DP, these IN + entries that R2
depend on æ would jointly receive a (e( IN + 1), 0)-P guarantee.
However, since Y is a random variable, one can instead use a high probability bound on Y as it may lead to an improved e bound. There some chance that Y will fail to satisfy this bound, and this failure probability will later be incorporated into the ō parameter of DP. Using one-sided Chernoff bound, we bound the probability that Y is significantly greater than its mean:
Pr Y ( Pr
IN
2+7
IN m
(1)
m k
for any 7 0.
For ease of notation, let N₁ = 1. N/n,, and let T(D) = (X, U SMOTE N,K.. Then for an arbitrary set of outputs S C. (M), we can obtain the following bounds on the output of M o T on D and D':
Pr[M(T(DD) E E s]= = Σ Pr[M(T(D)) S 5 Pr[y- 5
Ni
PH[M(T(D') E S|Y = 5] Pr[YY =
Σ
e E =] Pr(y = +
Σ
('PP(M(((D)) E SSY 5 Pr(Y 5]
(1778)1
(1+7)N1/K
Ni k
S (c(tiiii
E SY= Σ P(M(TD)))SS j| = +] c Ni 2
S (c (M(())))) (PM E S + M-M--
The first equality is due to the law of total probability, the second step is due to the group privacy property of DP, and the third step separates the sum into small and large j values based on the parameter y. In the fourth and fifth steps, we bound each coefficient e by the largest value of j in the respective sum. For small j values we then the apply the law of total probability; for large j. we upper bound each term (r(M( E S = J] by 1, so the remaining sum is simply the probability that Y is greater than the smallest "large") j value, which is then bounded by the one-sided Chernoff bound of Equation (1).
Therefore, the composition of first applying SMOTE and then applying M to the original dataset along with the output of 245 kmj
SMOTE is
((1 + 7) LN e
1N
-differentially private.
Next, we prove Lemma 9, which gives lower bound for a parameter 1(d, kb) that describes the maximum number of times
17

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
one point from R. can appear among k-nearest neighbors of other points from Rd, The proof is geometric argument that relies the notion of kissing number (dd), which is the greatest number of equal sized non-overlapping spheres in Rd that can touch another sphere of the same size (Musin, 2008; Jenssen et al., 2018).
Lemma 9.
Let ld, k) be the maximum number of times one point from TRd can appear among the k-nearest neighbors of m other points from R. Then, l(d, k) = minkk- K [(d), n1).
Proof. Trivially I(d, k) S ni so in the following, we will consider the case where ny is sufficiently large. Also w.l.o.g. we will consider (d) kissing number spheres of radius r = 1.
Consider constructing a point set S around the origin O = (O.... 0) E Rd such that S contains points whose 1-nearest neighbor is O. We next define the points z; E Rd, s.t. {21, .... I (K) where each 2; is the center point in each of the K (dd) kissing point spheres around the unit sphere centered O. By construction, each | 2 and | - 42yl22 2 2 for every other zj E S.
We have so far set S with cardinality [S| = [dd,, which contains the ((d) centroids whose 1 -enarestt neighbor is O. Recall that we allow ourselves to break ties in distance arbitrarily. Ties are often broken probabilistically in k-nearest implementations, but we are considering the "worst-case" scenario for our analysis of S.
We now demonstrate that we cannot locally increase S. That is, ((d) is the maximum number of points who can share a 1 I-nearest neighbor with O. We show this by contradiction.
Consider adding new point +K())+1 into the set S of 1-nearest neighbors with O. How can JK(d)+1 be a valid 1-nearest neighbor of O? If || ll2 > 2, O is certainly not its l-nearest neighbor; instead, for some E S, || 2x; ||2 < [| - 2 by construction. If ([zx((a)) S 2 then it would either: (1) Have O as its 1-nearest neighbor, implying that [[0(())++ +1 0 I [|0x())++ - mill2 for all x; E S. which then implies that | - >x(d++ill S ||ar 0 12 for at least one point zj E 5, thus either shrinking [S] or leaving it the same size, or, (2) Have a fixed V3 E as its
--nearest neighbor, implying that x - xy || 2 [|0x(())++ - zzil2 for all x, E S and O, but then implying that || - <x(d)+all2 S ||2 - OOl2 for some other Ta E S by the triangle inequality, again shrinking |.S]. Thus, a new point Tk(d)+1 cannot be added to S when k- = 1, and I(d, 1) = K(d).
Next we generalize this result from 1-nearest neighbors to k nearest neighbors, demonstrating that 1(d, k) kK(d). We will do this by duplicating points in S from the --nearest neighbor construction to create a set S" and then again show by contradiction that this set S' cannot locally increase in size.
For k-nearest neighbor, we construct a set of points S' as follows, where each si for j E (1...., k} is an exact replica of w; from S. Thus, S {=] xb, #1 = U... J {a 2 ..,, = Note that |S kK (d), where we have k duplicates of the set S from the 1-nearest neighbor example.
For each point of E S", there are k- 1 points (=],..., ) * ut for which || x 12 = 0. As before, the distance from the origin each point |aا O by construction, and for each of and the kK (d) A 1 points æy that are not
duplicates of r/. | اللl 2 2. Thus for S' of size (d),,, then O is a k-nearest neighbor of every point in S', using
worst-case tie breaking.
We next show that the number of points with O as nearest neighbor cannot increased by adding a new point x i+1
*K(a++1
to S" The argument is analogous the argument for 1-nearest neighbor. If [|=])(]]+ 2, then O is certainly not its k-nearest neighbor; instead, for some size k set (xt,,.., xx C S', ||
K(0)+ =2I12 < || O112 by construction.
If (+ +(0)+1ll2 lll2 then it would either:
3+1 Have O in its set of k-nearest neighbors, implying that || k(a+++ O1l2 S k(1)+1 - x ll2 for at least one of E S'. which then implies that ||ا|- - 5+1 +lle I ||- Ol12 for at least one point 2. E S, thus either shrinking |S'| or leaving it the same size.
Have an entire set (a/....,.ff ) E S' as its k-nearest neighbors, again shrinking |S] by the triangle inequality as in the 1-nearest neighbor argument.
Thus, we have shown that [S'| cannot be locally improved, and that 1(d, k) kd).).
18

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
The exact value of the kissing number K in general d dimensions is an open problem, but is known to be lower bounded by K > 20.2076((1+0(1) (Wyner, 1965; Musin, 2008) and upper bounded by K s 20-4012d (Kabatiansky & Levenshtein, 1978). Thus when n is not too small, A:20 2073d((+00))))) < ((d, k) < k20.4042d We note that even though the exact value of the kissing number is unknown, its bounds are asymptotically tight, with exponential dependence on d.
Plugging in the maximum value of 22024042 for l(d, k) into the differentially privacy bounds derived above recovers the guarantees of the theorem.
Empirical Results: SMOTE Here we present simple empirical results illustrating that SMOTE as a pre-processing step before differentially private learning results in extremely poor performance. Figure presents the performance of SMOTE as a pre-processing method before DP logistic regression with three different e values, compared with non non-private logistic regression and DP logistic regression without SMOTE applied. The evaluation is performed the manmography dataset (see Section 5) with variety of imbalance ratios created by subsampling.
As predicted, downstream performance degrades significantly after SMOTE- indueed adjustments as described in Table 2. Note how proper privacy adjustments after SMOTE (dotted lines) negatively impact performance compared to DP logistic regression without SMOTE (solid red line). This empirically confirms our negative result of Theorem 3, that SMOTE should not be a preferred pre-pro pe-processing method for differentially private imbalanced learning.
SMOTE Performance (F1) Across imbllace Ratios mata-mammorsphhy
0.75
307
10
12a
Figure 2: SMOTE pre- pre-processing on downstream DP logistic regression (with adjusted e) on the manmography dataset. Data was subsampled (log-scale x-axis: n E [500, 1000, 2000, 5000, 10000) and evaluated across imbalance ratios e [4, 8, 12.3
B.2. Re-sampling with DP Synthetic Data
The privacy of Algorithm 3 is straightforward to long as the data synthesizer in Stage is (c, 6)-DP, then Stage 2 will retain the same privacy guarantee by post-processing (Theorem 8).
Proposition 10. Algorithm is (c, difffrrrentl private.
Algorithm 3 Balancing w/ Private Data Synthesizer
Input: (c, diiffeerentllll private data synthesizer S, original dataset D, desired number of samples N, and any additional
parameters for P.
2 Output: A balanced dataset D' where no 71.
3 Stage 1: Parameterize Distribution
4 Learn/parameterize a differentially private distribution 0 over the data domain i.e. A +- S(D.P).
5 Stage 2: Sample New Dataset D'
if 0 is parametric then
6 Sample N/2 minority examples D mn, then sample N/2 majority examples D',, no-
7 return concatenation [D], I-
else if 0 is non-parametric then
8 Perform rejection sampling based class label to draw balanced samples (i.c., ensure no ni N/2 in the final dataset D' by sampling from S(D) until target sizes are reached).
end
9 return =0
19

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
C. In- In-processing Methods and Analysis
C.1. Bagging and Private Bagging
Proposition 4. For a bagging classifier composed of non-differentially private learners to achieve = n=", then it must also be that c < 1 for all >
Proof. From Theorem in (Liu et al., 2020), given a training dataset of size n and an arbitrary non-private base learner, bagging with replacement with m base models and subsample size of i has privacy parameters m log( =++ and n
8 1 (m=1)=
m. Solving for k in the ō equation and plugging in 8 = n yields,
log(1 - n n)
m k log(n 1) log(n)
Plugging this in to the expression for gives, for n > 1.
log(n 1) log(n)
log(1 n1
log(n 1) log(n)
log (1 + n -
log(1 n
log (1 n2 n=_1)
log (1 + n
log(11 n S
log (1 n n-
log (1 + n -
Thus, for 1. applying the bound of log(1 + x)) S x yields the result.
Empirical exploration We also present some empirical results for DP Bagging to illustrate its poor performance as an pnppoocssinng method for DP imbalanced learning. Figure 3 presents the performance of DP bagging using DP logistic regression weak learner, compared against the two baselines of non-private logistic regression and DP logistic regression without bagging. For each DP-LR in the Bagged classifier, the privacy budget was split among the estimators using advanced composition (setting with variety of imbalance ratios created by subsampling. As predicted, we observe that private bagging underperformed relative to a single DP logistic regression classifier across sample sizes and imbalance ratios.
1/2 and ė = 1/n²). The evaluation is performed on the mummography dataset (see Section 5)
Disjoint Parallel Composition vs. Bootstrapped Bagging One natural approach to improving privacy in bagging is to train each weak learner on disjoint subsets of the dataset (rather than on bootstrapped or overlapping subsets). principle, using parallel composition may yield a better overall privacy guarantee than the standard bootstrapped setting with advanced composition: because each individual's data can only appear in one of the weak learners, the overall privacy cost does not grow with the number of learners in the same way that it does under advanced composition.
To this end, we first evaluated a uniformly sampled disjoint bagging method that partitions the dataset into k subsets of size N/k, trains one DP logistic regression (DPLR) learner per subset, and then aggregates predictions via majority vote. Table 4 (for imbalance ratio r = 8) and Table 5 (for r = 32) compare this Disjoint approach against the Adv. Comp. version, where each weak learner trained on a bootstrapped subsample and the privacy budget composed using advanced composition rules. We vary the total number of learners E (5, 10, 20} and report F1 scores (mean + std. dev. over 10 runs). Overall, performance remains modest for both methods, and one method is not clearly better than the other, indicating that simply introducing parallel composition via disjoint partitions does not substantially improve the utility of private bagging when the dataset is imbalanced. One reason is that the disjoint splits further reduce the already limited number of minority-class examples available to each learner, exacerbating data imbalance and minority class scarcity.
Stratified Disjoint Splits We also examined a variant of the disjoint-split approach that leverages stratified sampling to preserve minority-clase representation in each partition. This setting presupposes that the practitioner can publicly observe class labels when constructing subsamples; thus, this setting is not directly comparable with privacy assumptions we make for other methods in this paper. Nonetheless, for comparison, we report results in Table (r = 8) and Table 7 (r = 32).
20

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
While stratification can slightly improve the representation of minority samples in each split, performance still remains limited. The main challenge is that each weak learner's privacy noise is amplified by the small per-learner sample size, leading to weak models that do not effectively capture minority class signal.
Soft vs. hard voting A second potential avenue for mitigating the degradation from private learning within bagged ensembles is to adopt different voting schemes when aggregating predictions. While hard voting uses a simple majority of discrete class predictions, soft voting first averages predicted probabilities across learners and then applies a threshold (see, c.g., (Bauer& & Kohavi, 1999) for an analysis of such voting mechanisms in the non-private setting). Tables (imbalance r' 8) and 9 (r 32) show the effect of switching from hard voting to soft voting the standard advanced composition bagging scheme (i.e. where each weak learner is bootstrapped). In some scenarios, soft voting slightly outperforms hard voting, but in other settings the results mixed.
Bagging Performance (F1) Across Imbalance Ratios (r= no/M,, matm-mammography r= 16
r= 8
r=
1.00
0.50
0.25
0.00
10a
104
10a
104
10a
104
10a
104
LR, Non- Private
DPLR
Bagged DPLR (n_ _s.ssmmatoorsS)
Bagged DPLR (n_ mo_estimatars-10)
Bagged DPLR (n_ jo_esimmttors-20)
Figure 3: Fl score performance on subsamples of the mammography dataset (imblearn) comparing differentially private logistic regression (DPLR) and DP bagging (DPLR as weak learner). Data was subsampled (log-scale x-axis: E [500, 1000, 2000, 5000, 10000) and evaluated across imbalance ratios r E [4, 8, 16, 32].
Method
n=500
n=1000
n=2000
n=5000
n=10000
LR. Non-Private
0.662 + 0.1
0.741 + 0.076
0.721 = 0.073
0.740 + 0.031
0.716 + 0.022
Bagged DPLR, Adv. Comp. (Festtiaaoss
0.177
0.124
0.178 = 0.115
0.164 = 0.128
0.094 + 0.048
0.217 0.116
Bagged DPLR, Disjoint (Fessimatoos = 5))
0.205 0.086
0.207 + 0.099
0.213 = 0.146
0.170 0.087
0.166 0.118
Bagged DPLR, Ady. Comp. (Flestimatrrs 10)
0.273
0.197
0.138 + 0.093
0.142 + 0.076
0.201 01066
0.254 0.142
Bagged DPLR, Disjoint (Testimators 10)
0.113 + 0.078
0.068 + 0.062
0.249 = 0.190
0.121 + 0.076
0.150 + 0.075
Bagged DPLR, Adv. Comp. (Nestimanes 20)
0.150
0,153
0.159 - 0.114
0.160 = 0.120
0.249 0.116
0.186 0.193
Bagged DPLR, Disjoint (Nesimatoos = 20)
0.189 + 0.179
0.248 + 0.185
0.162 + 0.137
0.263 + 0.116
0.253 + 0.119
Table 4: Bagging performance with disjoint learners (uniform sampling), Fl score for imbalance ratio 8.
Method
n=500
n=1000
n=2000
n=5000
n=10000
LR. Non-Private
0.400
0.299
0.509 + 0.170
0.548 + 0.152
0.618 + 0.079
0.547
0.065
Bagged DPLR, Adv. Comp. (Nesttimaors 5)
0.074 +: 0,071
0.069 + 0.065
0.052 + 0.035
0.036 +: 0.024
0.056 +: 0.065
Bagged DPLR, Disjoint (Necimators 5)
0.082
0.074
0.055 0.048
0.068 + 0.045
0.097
0.045
0.060 0.040
Bagged DPLR, Adv. Comp. (Nesttmantes 10)
0.011 + 0.033
0.026 + 0.043
0.048 = 0.029
0.052 + 0.034
0.064 + 0.055
Bugged DPLR, Disjoint (Megssimatons 10)
0.034
0.081
0.108 + 0.087
0.047 = 0.038
0.096 0.059
0.068 0.052
Bagged DPLR, Ady. Comp. (Flestimaoes 20)
0.000
0.000
0.000 + 0.000
0.097 = 0.084
0.070 + 0.042
0.062 0.062
Bagged DPLR, Disjoint (fessimstons
20)
0.000 + 0.000
0.000 + 0.000
0.063 = 0.055
0.061 + 0.034
0.065 + 0.049
Table 5: Bagging performance with disjoint learners (uniform sampling), F1 score for imbalance ratio 32.
21

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Method
n=50
n=1000
n=2000
n=5000
n= n=10000
LR, Non-Private
0.662 0.109
0.743 + 0.000
0.712 = 0.000
0.667
0.000
0.714 + 0.000
DPLR
0.291 + 0.110
0.131 + 0.153
0.254 = 0.168
0.205 + 0.151
0.157 + 0.092
Bagged DPLR, Adv. Comp. (Pestimmtors = 5)
0.074 + 0.071
0.069 + 0.065
0.052 + 0.035
0.036 + 0.024
0.056 0.065
Bagged DPLR, Stratified (Testimatoos 5)
0.154 = 0.084
0.233 = 0.147
0.197 = 0.101
0.249 + 0.122
0.168 1 0.083
Bugged DPLR, Adv. Comp. (Flextimanes 10)
0.273 + 0.197
0.138 + 0.093
0.142 = 0.076
0.201 + 0.066
0.254 + 0.142
Bagged DPLR, Stratified (festimators 10)
0.220 + 0.101
0.189 + 0.110
0.167 = 0.098
0.147 + 0.092
0.192 + 0.108
Bagged DPLR, Adv. Comp. (Nestimators 20)
0.150 + 0.353
0.159 + 0.114
0.160 = 0.120
0.249 + 0.116
0.186 + 0.193
Bagged DPLR, Stratified (Tigstimatos
20)
0.157 0.086
0.149 + 0.083
0.200 = 0.111
0.158 + 0.090
0.205 0.080
Table 6: Bagging performance with disjoint learners (stratified sampling), F1 score for imbalance ratio r r= 8.
Method
n=000
n=1000
n==000
n=5000
n=10000
IRR Non-Private
0.:400 + 0.299
0.286 + 0.000
0.375 + 0.000
0.571 + 01.00)
0.473 + 0.000
DPLR
0.086 + 0.055
0.168 + 0.173
0.064 + 0.061
0.074 + 0.044
0.070 + 0.074
Bagged DPLR, Ady. Comp. (Flestimators 5)
0.074 0.071
0.069 + 0.065
0.052 + 0.035
0.036 0.021
0.056 0.065
Bagged DPLR, Stratified (Fiestimators 5)
0.058 + 0.049
0.084 + 0.069
0.063 = 0.037
0.077 + 0.057
0.075 + 0.058
Bagged DPLR, Adv. Comp. (Nestimanes 10)
0.011 0.033
0.026 + 0.043
0.048 = 0.029
0.052 0.034
0.064 0.055
Bagged DPLR, Stratified (Feesimmatoss 10)
0.050 + 0.063
0.039 + 0.029
0.067 = 0.044
0.082 - 0.023
0.055 + 0.037
Bagged DPLR, Adv. Comp. (Pestimatoss 20)
0.000 0.000
0.000 + 0.000
0.097 + 0.084
0.070 + 0.042
0.062 0.062
Bagged DPLR, Stratified (Mestimstors = 20)
0.000 + 01000
0.087 + 0.050
0.087 + 0.044
0.064 + 0.051
0.054 + 0.044
Table 7: Bagging performance with disjoint learners (stratified sampling). F1 score for imbalance ratio r 32.
Method
n=500
n=1000
n=2000
n=5000
n=10000
LR, -oi-Priv
0.662 = 0.109
0.741 + 0.076
0.721 + 0.073
0.740 + 0.031
0.716 = 0.022
Bagged DPLR, Soft (Mestimatooss
5)
0.262 = 0.093
0.220 = 0.127
0.208 + 0.105
0.206 + 0.143
0.230 = 0.157
Bagged DPLR, Hard (Flestimatoes
0.074 1 0.071
0.069 1 0.065
0.052 1 0.035
0.036 1 0.024
0.056 - 0.065
Bagged DPLR, Soft (Niestimatoes 10)
0.212 1 0.074
0.226 1 0.098
0.123 1 0.065
0.238 1 0.179
0.205 - 0.167
Bagged DPLR, Hard (Testimators 10)
0.273 + 0.197
0.138 + 0.093
0.142 + 0.076
0.201 + 0.066
0.254 = 0.142
Bagged DPLR, Soft (Nestimatoes
20)
0.205 + 0.0
0.265 + 0.177
0.280 + 0.114
0.127 + 0.071
0.154 - 0.092
Bagged DPLR, Hard (Restimatoes
20)
0.150 = 0.153
0.159 + 0.114
0.160 + 0.120
0.249 1 0.116
0.186 = 0.193
Table 8: Performance table for imbalance ratio
8, Hard vs. Soft voting.
Method
n=500
n=1000
n=2000
n=5000
n=10000
LR. Non-Private
0.400 1 0.299
0.509 1 0.170
0.548 1 0.152
0.618 1 0.079
0.547 1 0.065
Bagged DPLR, Soft (Festimators 5)
0.074
0.038
0.066 + 0.044
0.060 + 0.046
0.073
0.058
0.083 + 0.070
Bagged DPLR, Hard (Frestimatoes
5)
0.074 + 0.071
0.069 + 0.065
0.052 + 0.035
0.036 + 0.021
0.056 + 0.065
Bagged DPLR, Soft (Mestimaatons 10)
0.049 = 0.074
0.047 = 0.054
0.033 + 0.024
0.064 = 0.038
0.039 = 0.032
Bagged DPLR, Hard (Teestimators
10)
0.011 = 0.033
0.026 = 0.043
0.048 + 0.029
0.052 + 0.034
0.064 = 0.055
Bagged DPLR, Soft (flsstimatios
20)
0.000 1 0.000
0.085 1 0.156
0.019 1 0.028
0.059 1 0.037
0.083 1 0.036
Bagged DPLR, Hard (Mestimatoes
20)
0.000 1 0.000
0.000 T 0.000
0.097 1 0.084
0.070 1 0.042
0.062 1 0.062
Table 9: Performance table for imbalance ratio r = 32, Hard vs. Soft voting.
22

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
C.2. Warm-up: A Known Population
As warm-up, we quantify the estimation error of the Bayes optimal classifier for known Gaussian mixture.
Example 11. Let [Xi, Hiz E IR==1 x {0, 1 be randomly sampled such that X is mixture of Gaussians and is binary class label. Specifically, let {X, ys = 1 ~ [N and {X, y = 0} ~ (N o²). The domain of X here is a priori unbounded, but we can later bound X with clipping to reduce sensitivity.
This setting was also studied in (Yang & Xu, 2020), who showed that the Bayes optimal classifier is given by [x( [(xx 2 0) for (No + 212/2 (see (Hart et al., 2000) for a textbook treatment). That is, assign the positive label if and only if X > 0. We construct a private estimate of to build intuition for the effect of noise on imbalanced learning.
The private classification mechanism MBOC R - (0,1) makes private estimates of Pos M4 by first clipping each X; to lie in the range! !- R, R] before applying the Gaussian mechanism the clipped data compute the empirical mean." Formally, define,
Th
CLIP R) + N 0,
2R 22
2 2og
122 8
jub
126
nbb
22
for E {0, 1]. where CLIP denotes clipping X; into the range [-R, Rl. Then a natural mechanism for privately computing the Bayes Optimal Classifier is MBoc(X) = T(( 2 0) for 0 -= 22
Proposition 12. The mechanism MBo is (8),28) differentially private. Assume max pu). | S B for some known
bound and > + a / (owg4n/3)))) For any imbalance ratio r 2 1, with probability at least 1 - B/2, the 0 produced
by M BBC satisfies
6- 0l s 20gg((())))
(1+r)+ 28 log(1.25/8)
r2).
ngr²
Furthermore, for any estimator 0 of with probability at least - -3/2.
0 - 01 2 v (1+)) s '(1 - -3/2),
where ((-) denotes the cumulative distribution function of a standard normal distribution.
The proof of this is relatively straightforward. As sketch, privacy guarantees follow from the Gaussian Mechanism. For the accuracy guarantee, we first provide high probability bound on the potential affects of clipping the data to Rt and then provide brohhprobabblity eиror bound accounting for the noise added to each of the (c, diffferrentll private estimates Po and مr. The proof relies on known bounds for the population mean of X (for example, if X is mixture of Gaussians over AGE, one could assume a minimum of and a maximum of 120).
Proof. Recall our private mean estimates for each class are,
Σ CLIP + Go, An 1 111
Σ CLIP(X,, R) G1,
=E(Y==0)
:E(V==1)
where Go ~ ~N(0, 7 Dr G. ~ NN(0, op,) ) and CLIP(x, R) maxf - R. min(x, This clipping function guarantees Thus, the Gaussian mechanism gives (c, 6DP with
the sensitivity of our private mean computation function is Aʃ
2R ny
variance oh 2 20g((1.25/))
SR² 15g(1.25/6)
First, we'll argue that with our choice of R with probability 3/2 clipping does not bias the data. To see this let
( sid o2). We will use the following standard concentration result for the maximum of sub- Gaussian random variables to bound them.
22 Lemma 13 (Rigollet & Hütter, 2023)). Let Zi.... Zn Hd o2). Then, Pr(maxisigs [Z/] > t) S 2ne 2=3
This the canonical private mean estimator, but we note that improved methods exist. (Biswas et al., 2020; Kulesza et al., 2023).
23

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Consecutively using the triangle inequality, Lemma 13, and R B + log(An/B)) we see that,
(R- (R-2)²
Pr[
max s
X R|
$ Pr
max Ss
Z + B >
R
S 2ne
S 3/2. 20d
Therefore, with probability at least 1 - 3//
0-0 =
1
CLIP(X,, pa Go
1
Σ
CLIP(X,, MI +G1 GG
2
710
(E(Y==0)
iE(Y==)
1
(X, - no) + Go + 1
E
(X, - m1) + G1
2
1E(Y=0))
(E(Y==1}
1
2
N
0.
+ DP: + T
2
700
= N (0.
0²
2R log log (1.25/))
(1
+
r) +
(1+
(2)
n0
niee
Combining (2) with the fact that for NO, 2²) we have the inequality Pr([Z] > S 2e - we conclude that with probability 1.
02
2R 1og(1.25/0)
00-05 0
(1+r)+
(1+r")//2oo((4/)))
nie²
no
This completes the utility proof of the proposed estimator.
Let's now turn the question of the best achievable deviation. We note that in this example the MLE of 0 is available in closed form, namely ÜMIL = (X" + 1/2, where X -
nlg Σx= (1 yt) Xr and X R; Σ X, Furthermore well know that this case the narrowest ÔMIL NO, [++))²)) is the minimum variance unbiased estimator.
4ng
confidence interval for f is |0 o /11 + r)/ng 4- -1- 0 o / r)/mo - (1 3/2)].
Proposition 12 tells us that in Example 11, private classifier from the ideal model class has privacy error that scales linearly in the class imbalance parameter r, which is minimized under no class imbalance. Unfortunately, imbalanced data often has >>>> 1; for example, when detecting spam Twitter (Analytics, 2009), ~ 32, and in the datascts used in Section 5 in our empirical evaluations, ranges between 8.6 and 130.
Linking to Imbalanced Metrics A natural question, building on Proposition 12, is how we might weight samples when calculating 0 to improve performance on imbalanced metrics, such as Recall, under this simple population model. To do this, we consider a re-weighted classifier, fe,, where the weights 7 are tied to class prevalence. We can then reason about
weights under this classifier and show, for example, that the true positive rate can be written as TPR = 4 [1~>)(11-
This analysis informs setting weights based on class prevalence estimates (e.g., = 1/ Pr(y: = 1)) to better target imbalance-focute metrics like Recall.
Formal Discussion Consider the re-weighted classifier fo,, where 0,, = y + - 7))o Note that the optimal Bayes classifier in this model class, and can be written fe (X). We will denote the Gaussian random variables for the majority and minority classes as Zo ~ N(4, og) and Z ~ N(H1, of) respectively, and the Gaussian random variable for the added, zero-centered noise for privacy as Z (O,
Then, can derive a population version of true positive rate under fe, as.
TPR Pr(fe, (X) 1|Y 1)
Pr 2 7/1 + (1 - 7) 1))
$ (1 7)(11 no),
24

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Our original imbalance ratio r is sample-specific estimate of the true population imbalance ratio, r* Pr(Y 0)/ Pr(Y = 1). Here, will consider r", alongside population version of positive rate PR Pr(Y 1) TTr. This
gives insight into exact form of the Recall metric for Example 11, which is - Φ ( (1 + +r"). Note that Recall gets worse as the imbalance ratio increases. However taking < 1/2 improves Recall relative to the standard optimal Bayes classifier. One way to choose such a is to take the inverse probability weight = 1 Pr(( = 1) 1 + r". These population parameter considerations motivate an empirical weighted counterpart to fa (x). Such precise distributional knowledge is rarely known practice and unverifiable under differential privacy (where the data cannot be accessed directly without noise mechanisms). Instead we will by default account for r by setting weights inversely proportional to class prevalence in weighted methods, motivated by this reasoning and prior work (Chawla et al., 2004).
Quantifying the Benefits of Re-weighting in Imbalanced Metrics Here we provide detailed calculations showing that the re-weighted classifier fe, outperforms the optimal Bayes classifier f0, in various imbalanced metrics, summarized in Table 10. Recall that fo, is a threshold-baan based classifier defined
fe, (X) 1( 2 0,),
(3)
where 0, - 7/4 (1 P) The parameter 0, weighted average of the means for each class, μr and Mus with y controlling the weight given each class.
Metric
Formula
Recall (Re(7))
(1 + r*) + ()1
Precision (Pre(7))
4((1 ([(1-))A)
Balanced Accuracy (BA(7))
4 (((1=))4))+0(1)
Fl Score (F1(7))
(((1-))A)
D((1 ([[1))]]++ -
Table 10:
Some imbalanced classification metrics, defined as functions of the imbalance weight parameter for the reweighted classifier fo,, where A Ai =o for ease of presentation.
Recall Metric. The True Positive Rate (TPR) is defined as the probability that the classifier correctly identifies a positive instance. For a given sampled from the positive class (Y = 1), we have,
TPR
Pr( fe, (X) = -
Pr N 7/1 + (1-7)po)
Since X Y distributed as ((1,, o2), we can standardize this normal variable as,
-
7/11 + 7)p0 - 141
TPR = Pr
Thus, the TPR can be written using the cumulative distribution function (CDF) of the standard normal, denoted here Φ given
TPR ( 7 -mo) mo)
We define the population imbalance ratio r* the ratio of the probability of the negative class the probability of the positive class i.e.
Pr(Y-
Pr(Y = 1)
25

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
The total probability of positives (i.e. positive rate PR is just
PR = P
= =) 1+r
Recall is defined as the ratio of true positives the total actual positives,
(1~>) Ho!
TPR
Recall
PR
Simplifying gives,
Recall Re(y) = (1 (1+ (l (11 no)
This shows that Re(r) decreases the imbalance ratio r* increases, because the term + r*) magnifies the effect of the Gaussian term.
This implies that Re(r) can be improved relative to the Bayes Optimal Classifier by choosing < the threshold 0, to be more inclusive of the positive class, thereby increasing the true positive rate.
2. This adjustment shifts
Precision Metric. Precision is defined as the ratio of true positive rate to all positive predictions, or
TPR
Precision
TPR + FPR
where FPR denotes False Positive Rate.
False Positive Rate (FPR) are defined as the probability that the classifier incorrectly identifies a negative instance as positive. For X sampled from the negative class (Y = 0),
FPR Pr(So, -X)=
Pr(Zo 2 7/1 + (1 (1-7)pp)
We can similarly standardize this normal variable:
X 14 >
7P1 + (1 - 7)H40 140
FPR Pr
0
which simplifies to,
FPR Pr 2> 7(m1 Mo)
where 7 ~ (0, 1). Thus, FPR can be written as:
FPR = 1 1 + (7(1n -
-H0) 1b0
This yields
(1- (olg--ma sug)
TPR
Precision Pre(y)
TPR FPR
(1-7)(M Pal
+ (1 r
7(11 -Ma)
As r" increases, the FPR becomes larger, leading to a potential decrease in Pre(y). This result shows that in adjusting ? better performance can achieved on either Re(7) or Pre(y).
26

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Balanced Accuracy. Balanced accuracy is defined the average of TPR and TNR. We require the following explicit formulas for TPR and TNR, where TPR previously defined for Recall:
[1 (1->)1 140)
TPR +
and
140 )) ②b
(7/21 -1))
TNR = Pr (Zo S 8.) Pr 2 2
Therefore, Balanced Accuracy is simply
+ [1~ Ho)
+ + (2
BA(
2
F1 Score. F1 Score can be written as:
TPR
F1 Score
2. TTPR FPR + FNR
The expressions for TPR, FPR, and FNR have been previously derived follows:
(1 714 1o)
TPR = Φ
7(111 -mO)
FPR $
(1 (1-7)(11 -HO)
FNR 1 +
Substituting these yields an expression for the Fl Score:
2. (1-3)(11H0 Ho)
F1(7)
2 $
(1-7)(111
+ 7(11 Po)
(1-7)(ms
Simplifying yields:
+
(1- (1-7)(41 -HO
F1(7)
+b
+ (1 (00
- ②b
7(11 ppa)
27

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
C.3. Weighted Private ERMs
Assumptions from (Giddens al., 2023). We list here (for completeness) the undesirable assumptions from (Giddens et al., 2023) that we overcome. Their privacy proof works only for loss functions that take in a single argument, which excludes standard models like logistic regression, SVM, and others. Additionally, they made the assumption that the difference of weights across neighboring datasets goes to 0 as n. + oc, which is too strong for our inverse proportional weights strategy. We also note that in differential privacy, sensitivity is analyzed under worst case assumptions even if the influence of a single data point diminishes as n2 grows large. One therefore should avoid privacy statements that rely on asymptotic assumptions.
Notation for ERM Proof. For parity and ease of comparison, we will use mostly overlapping notation with (Chaudhuri al., 2011). We will denote the Euclidean norm of R2 by ||x|||- For an integer n, the notation [ra] will represent the set {1,2, ...,,...... ..). Boldface will be used for vectors, and calligraphic type for sets. For square matrix A, the induced I2-norm will be indicated by | Algorithms will accept input training data D = (x,, y.) E X x ) : 1,2,..., consisting of n data-label pairs. In binary classification, the data space is X' = Rd and the label set is y = 0, 1. It will
be assumed throughout that X' is the unit ball, hence ||x:112 S 1. Note that the extension of the proof to || Xx ll2 S is
straightforward and commonly implemented in practice. This is also how we implemented our code.
We aim to construct a predictor f + y. The quality of our predictor on the training data is assessed using a nonnegative loss function & y R. In regularized empirical risk minimization (ERM), we select predictor that minimizes the regularized empirical loss, optimizing over within a hypothesis class H. The regularizer AN is used to prevent over-fitting, for some function N of the predictor. Altogether, this yields the ERM loss function:
(f,
Σ ((x.)(xx)) + (N( 72
We can slightly modify the regularized ERM by introducing weighting scheme to correct for class imbalance. Let w [W1, ......; wn] be vector of sample weights, where each corresponds to a weight assigned to the i-th sample in the dataset D. This yields.
1 n E w. Ely,, f(x:)) + (f) Jf,, D. w)
We consider weights w, that do not explicitly affect the regularization term (N is standard, as regularization should penalize model complexity independent of class imbalance weighting.
Ridge Regression. From here on, we will focus on ridge regression, so instead of a penalty of the form AN((F we will use ~ 11 where our predictor is x² and /3 is a vector of coefficients that can be multiplied with sample vector x to produce a prediction.
common choice of weight vector w = [wi, w.,...., ..., Wen] is to compose weights such that they correspond the inverse frequency of the class label in the training (Provost & Fawcett, 1997). In other words, w; is inversely proportional the prevalence of the class label y; associated with each sample (x;, y:). Let be the number of total samples in dataset D, and Y be the set of unique class labels. Then let the = = - 1[y k). --1 ( a and define the weights
Wk
for E 10.1).
(4)
Considering neighboring datasets and class weights Consider D = ( Wi yx, (where x and y are the feature and label vectors, respectively), and where ys E {O...., k}, and a class weight w, as defined above.
Recall n, < no. We then have weights
y if I
n1
m1
mi
11
71
if
lo
No
28

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
where To and 1 the of row indexes of that partitions it into x(") and x x(1) (denoting the majority and minority class feature vectors, respectively). Note that 1 #1 and thus n2 mg )--11 b1 #o )
Recall that for privacy, we consider neighboring dataset x' of size n no + n. We will denote the new weights of neighboring dataset features x' by {u<)==
We note that neighboring datasets will have weights that fall under one two cases below, Without loss of generality we will assume they differ in the jth data point.
C1: The differing sample between the neighboring sets is such that z'j & zj, but keeps the same label i.e. v/ - Vj- This implies that wi un = 0 v = I,...,n. n. Under this case, there no change in weights between neighhoring datasets D and D'
C2: The differing sample between the neighboring is such that x'j # my and also v/ # yj- In this case need to reason about the effect this difference entails on the class weights.
Case follows that,
1
71
1 C 1 if if Ch
-1
(1
#1
(1(+++1
where if 7 C J means that the minority class gets even smaller between the two neighboring datasets. The complementary scenario is,
1
1
I C
n0+11
(1(
27
Au
if 1
Since by assumption n1 < To, we have that
22
We analyze these two scenarios independently.
f1
Scenario when 1 4 i.c the minority becomes smaller. Then we have.
1
1
n(n1 + no) (no + 1)(m1 - -1)
n² (no + 1)(m 1)
27
=
n
+
na 1
"0
11
So,
() (a)
if E 1i,
1
n1
w
(mi (1
if &t 11,
no+1
n²
while 1 #1
+
1 + mo
=
mino
2
and
a
Bi n
if J:
W/
nin n2
if Io.
Therefore,
Σ (5
Mw: w/l
Σ
w/l +
Σ
|w0 w/!
itjJE
n10
T4o +
1
(m1
1)
+
f1
14g
n
n
In Scenario 2, we have J, C I i.e. (minority becomes larger). Thus,
1
1
71
n²
A/
#6
n1
no
(n)
1)(na 1)²
29

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
and
(1h + (100 nn=1 if E 11
#1+1
12.
!
n1 if $ 11- [1g 1
Ro
Therefore,
Σ +
wy
w!l
70
(no 1).
n1 + 21 n
11
711 + 7o 1
71
We have thus shown that the total change in weights, if the minority class size and label proportions change by one, is bounded as Eizp |0; w/l - 4. We give this intermediate result in Lemma 14.
Lemma 14. Consider D = [(r y=) = (x,y), where yi E {0, 1) and a neighboring data set D'' differing in the jth data point. Then, for the weights defined in (4) we have that Ei j [w; - w/ll S 4.-
Now, for completeness, we reproduce standard definitions in the form they appear in (Chaudhuri et al., 2011), including a slightly stronger variation of Definition then what described in Section
Assumptions loss. We make almost the same loss assumptions (Chaudhuri al., 2011). Here, restate definitions of strictly conver and r-strongly conver from their paper for convenience. We also require the convex loss function E(,, -) to be twice differentiable functions with respect to the second argument, and such that 2 Eyy m)) S 1 and 3xpt f(y, 1)) S c
8²
Bry
for some fixed c.
Definition 15. A function (B3 over / Id is strictly convex if for all (0, B. and Bd
H (aß (1 a))²') < aH( + (B)
is T-strongly convex if for all a E (0, 1), 3, and B3,
H (aB+ s + (1- - 2 - a))
| a)) 311 -
1
Privacy model. Assume A(D) generates a classifier, and let be a dataset that differs from in one entry (assumed to be the private value one individual). They are neighboring datasets in the standard sense, e.g. D' and share n the probability that A(D) S close to the probability that
points (x&, yt). The algorithm A ensures DP for any A(D') E S, with the probability taken over the randomness in the algorithm.
Definition 16. An algorithm A(B) taking values in set T provides c-
# (S = D) SET D,D' (S B = D Se.
sup sup
where the first supremum is over all measurable C T, the second is over all datasets D and DD' differing in a single entry, and ((-(1) is the conditional distribution (measure) on T induced by the output A(B) given a dataset B. The ratio interpreted be whenever the numerator and denominator are both
We also restate sensitivity, as it appears in (Chaudhuri et al., 2011). Consider g : (R'")" - IR a scalar function of -1,-.. En, where each 2, IRm represents the private value of individual i; the sensitivity of g defined as follows.
Definition 17. The sensitivity of function g (Rmm)" TR. is the maximum change in the value of g when one entry of the input database changes. More formally, the sensitivity 5(g) of g is defined as:
S(g) max ( P
max [g( 414h ................................ ..) g( 2i- 21 Z441 zn)1
For the function A(D) = argmin J(B,D) the output is a vector A(D) + b, where random noise with a density of vb) bll,, where a is the normalizing constant. The parameter 7 depends on e and the lag-ensitivity of A(-).
30

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Definition 18. The -y-sensitivity of vector-valued function is defined as the maximum change in the Lg norm of the value of g when entry of the input database changes. More formally,
((A) = max
max
| 24....) A .4....))....
Objective perturbation. The approach to private ERM first proposed by (Chaudhuri et al., 2011) adds noise to the objective function itself and then produces the minimizer of the perturbed objective. The perturbed objective is:
Jpriv (3, J(3 D) + 1 b²
n
Note that the privacy parameter here does not depend on the sensitivity of the of the classification algorithm. That is, the privacy parameter e is determined by the amount noise added to the objective function through n b B, and depends on the properties of the loss function and the regularizer rather than on the sensitivity of the classification algorithm's output. With the addition of weight vector w, this perturbed objective becomes:
Jpriv (3, D, w) (1,,,, bTB.
C. PRIVACY OF ALGORITIM
In this section, we show that Algorithm using the weighted ERM objective function (3, w) is e-differentially private. e.g. the output of the weighted (B, (,, D, w) is (c, diffferrreet private. We assume for each w; E w, |ws/ 1. Note in particular that our analysis covers the case of logistic regression, which as stated, (Chaudhuri et al., 2011) does not. Still, much of what follows is a adapted directly from the proof given by (Chaudhuri et al., 2011), with careful accounting for the weights vector w; for sake of completeness and ease of comparison, all steps are stated as closely as possible to what appears in the prior work.
Theorem 5, Algorithm instantiated with loss function Ely.1) 1)) that is convex and twice differentiable with respect to n
with a ()) $ 1 and ( 1)) S for all y, is c-differentially private.
Proof. Consider B Spriv output by Algorithm 1. Note.
n n Σ
1 (A A) w (v..
1 b n objective perturbation
Bpriv arg min
(5)
weighted ERM objective
We observe that given any fixed 3 Sprio and a fixed dataset D, there always exists a such that Algorithm I outputs Spriv on input D. Because is differentiable and convex, and N(.)) is differentiable, we can take the gradient of the objective function and set it B prie Therefore, we set
0 V J priv (B priv: D, w)
D.)
(B prive D. w) + -b AB priv
1
w. Vé(y, xf 3prie) + (A+ 1+B priv + b,
n
and therefore
b = ws (yi, X 3 (rrin)xi - + A)3 priv.
(6)
We claim that as E is twice differentiable and J(B,D) + 11 is strongly convex, given a dataset D (X1, ....... (xn,30 yn), there is a bijection between b and B Sprse- Equation (6) shows that two different b values can- not result in the same Brrig- Furthermore, since the objective is strictly convex, for a fixed b and there is unique B 3privi
31

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
therefore the map from b to $ Spriu is injective. The relation Equation (6) also shows that for any Ppries there exists b for which / pric is the minimizer, so the map from b Syrio is surjective.
To show c-DP, we need to compute the ratio g(Pprin DD/g(B priv (D)) of the densities of B Prrio under the two datasets D and D'. This ratio can be written as:
g prin (D) [(b D)
[ pric -> b(D))
g ( priv (D')
p(b'DD") Dr) (B priv b'(D'))|-
where [[3 priu blD). J( priv u(b[D") are the densities of b given the output B priv. when the datasets are DD and D' respectively.
b(D") the Jacobian matrices of the mappings from P Ppri b, and ((b(D) and
First, we bound the ratio of the Jacobian determinants. Let b denote the j-th coordinate of b. From Equation (6) we have,
b
wi ('( 8 pric x()x - r(A + A) priv.
Given dataset D, the Ait entry of the Jacobian matrix J(f b|D) is
0b(5)
(k) E'w S )x (1) x(()) n(A + A)Ulj k)),
ag (K)
priv
where I(.) is the indicator function. We note that the Jacobian defined for 3 prrio because || and are globally twice differentiable.
Let D) and D' be two datasets which differ in the value of the n-th item such that D = {(11,31) ..... (xn-1, 1xn-1, 1n-1), (Xe, }n)} and D' = {(x1, V1). (Xn-1, Bn- Bn-1), (X K.)). Moreover, we define matrices A and E as follows
A ndI Σ
w, (",,, xx) Xxx + nAla
E Wi 8l (" 3r xi + wt l" Borix x
Then, J(3 J(pprio + b/D) = A, and J(pir - = - E).
We now account for the fact that some wi and y, may change across neighboring datasets. Consider each summand inside E. not the one that changed (i.e., i f nt), then y/ y/ and x x, The change in that term purely from the difference in weights Wi vs. wn Since ||x|||2 S and ("(-) c, one gets ( )x,x w, (... )x,x ll2 S 2c w/ wa/.
By Lemma 14, summing over all such # yields total 2c Σitn lug wal < 2c(1 1). For i (the changed point), the difference can alter x, vs. X and l", but still, the norm is at most 2c. Adding them up gives
|| S 2c (1- 1 + 2c S 4c.
(1-11)
Consider,
(e priv - b(2'))
dett (A+ + F.]
(J priv + b/D)) det A|
By sub-muliplicatiiiity of the spectral norm, and recalling det(AA + E) = exp (tr log + A-1 B)), we can get,
det(A+E) det = |det([ + A--E)) < exp (tr(A- < exp
4ed
n(( (n(++1) A)
Acd Thus, we will define e" m(*+aj and set e' c". Hence (ee((A+E)) det((A) A)]
< <ee".
32

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Next, bound the ratio of the densities of b. Recall that [((()] 1, for any = and [ws), Iud. ||x,|| 1, and Lemma 14 we have that,
shows that ΣiØs [wt
w/fl I
||b' - bl12
wyl (1j, Ponv Ja, - (.j Bpir)a' + Σ sy.
(w; -w() El (1(,, 22. )oss)
2 + Σ
ww - wil = 2 + 1 - 1
inj
This implies that,
|b - |b']| S ||b b'll S 3.
which differs slightly from the original (Chaudhuri et al., 2011) work, which bounded ||b b'll S adjustment, we can write:
With this bound
(b(D) |bbld~ 1b1l// sur((i p(blDD') (D') |bb]|=-
b
where surf(x)) denotes the surface area of the sphere in d dimensions with radius æ. Here the last step follows from the fact that surf(x) s s11)x=-1, where s(1) is the surface area of the unit sphere in Rd.
Finally, we ready to bound the ratio of densities:
p(ppiial (D)
((bDD)
det det()((ppra) prir + b(D
g prse (Dr) (')
det (J (Sprr + b'(D))
m(bDD)
det + E)1
((
det A|
S é' c--d'
S e
Thus, Algorithm satisfies Definition 16.
33

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
D. DP-SGD FTTransformer
For completeness, we give the DP-SGD algorithm with the weighted cross-entropy loss explicitly embedded in Algorithm 4. For more details on the DP-SGD algorithm, see (Abadi al., 2016) and see (Yousefpour et al., 2021) for details on the empirical implementation.
Algorithm 4 Differentially Private SGD (with weighted Cross-Entron Loss)
1 Inputs: Database D {z,,, yi with n entries where each yı {0, 1}. privacy parameters (e, 8), learning rate n) clipping norm C, minibatch size B, batch sampling probability q L//n, number of iterations T, initial random model parameters 0.
2 Output: Model parameters Ppriv- for iteration 1 to T do
3 Construct a batch of expected size L by sampling each point into the batch with probability q
4 Partition the batch into minibatches of size B
for each minibatch 6 do
5
Compute model predictions ù: f(x;; 0) for each i E 6. Compute binary weighted cross-entropy loss as L(u. ú; w) 1 Di=1 wi (y log(ús) + (1 - 1:)))l)l log(1 -0:)))) ú;)]
6
7
Compute per-sample gradients VC, = wi (Di Vi) X;
Clip gradients V., = VL. min (1, |V2.1la
9
Parameterize x² for ('D,,, where é' = O E/ T log (t)) for (e, overall (Abadi et al., 2016).
10
Add noise: VL, v,, + N(O 22 Update model parameters - 11 E &L,
11
end for
end for
12 Return differentially private model parameters: Opeiv 0. =0
Proposition 6. Algorithm 4, a standard DP-SGD procedure with weighted cross-entropy loss given by Cly, w) E. we [y, log(ús) + (1 yx) log(1 ú.)], is (c, -idiffeerntt private.
Proof. Cly, D; w) does not effect the sensitivity of the gradient VL; with respect to each sample; the gradient is bounded by the norm bound C due to clipping. When each per-sample gradient VL, clipped to V., = VL, - min (1, TV | the sensitivity of the gradient is limited to 2C. Adding Gaussian noise calibrated to this sensitivity ensures that the overall training procedure satisfies (c, 5)-D, Re-weighting of samples in the loss function pre-clipping does not affect these privacy guarantees.
D.1. Note on Weighted DP-SGD Sensitivity
We note that in the standard unweighted case where w; = 1 for all i = I,..., clipping guarantees that the minibatch average gradient B Eieo VL, has sensitivity 2C/B. B. This is used in the noise calibration of standard implementations of noisy DP-SGD. We note however that in the weighted case all the V,, could change due the weights w;, making the sensitivity in fact 2C'. We show below that in fact the sensivity of the average Y Eieb V.,, is bounded by 2C/ B if C|V < C.
Lemma 19 (Sensitivity of Weighted DP-SGD under Class Weights). For each mini-batch b of size B, let VL, w.: y1 ja denote the weighted per-sample gradient. Suppose thut (); )xal S C. Then,
Σ - < 2Cno C KED
2C
Bn
n B
Proof. By construction, w, depends only on the ratio of n, and no- In the refined analysis given by Lemma 14, we showed n We will show something analogous here for the gradients;
that the total change in weights satisfies Σi= |w; - -w/-w/1= < 1- consider two neighboring datasets D and D' differing one sample.
34

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Weights are w; (recall #1 my). As before, let,
Aa i 11,
04
i To.
where lo and 1 are the set of row indexes of X that partitions it into Do and D1. We can denote _ 1 and a
51
thus
+
)-11 = ( + #o ) Keeping the minibatches equal for D, D', we have, V = wi(ii y: 22-- so
m1
no
(we - wii va)a
i
VL 4
wy(0s 85)æ, w/
Vy)='g. =
We'll first consider the case r C I i.e. the minority becomes smaller. Then we have,
1
1
1
1
n(n1 + no)
n² (no + 1)(m - 1)
#1
0
711
n1
+
(no + 1) -)
So,
13
(ny - 11
i I
w/
n no+1 n
(mi
(m1-1)(no++))) (1)
if $ Iı,
while 71
1.
2
and
no
761
no
Via No
n1
i 41,
W/
n
if E To-
n
We'll consider this now with the difference in the loss between the two sets,
Bo Ba+1)
(0:-
ys
Jai
i iiit #
1L,- JL
221 m1=1) (3:- yı Jai
i lo
no (ūj Uz )az
no+1 (0/ v/)= i= j.
After simplifying, we get,
n (0: ye)
i E I1 i i j.
1L,- VL =
1 (0 V/ 22
i e To
(Ú3 yリ )ay not1 -0/ V1)a''
i= j.
Conversely, when I C Ii (i.e. the minority gets larger), we have
x (0: y:)
i E Ii
VL
1I4
( y1)
i ie lo, i i j.
(0) f3) )zz
#1 (0) Vi b
i i= j.
Therefore,
1
Σ kebs
VL, V2:)
B -
C
C
2no +1
2Cno
C
<
B
B
n1
B
n
Bn
nl
2
35

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
D.2. Visualizing Decision Boundaries
Next we explore the effect of differential privacy on decision boundaries by presenting visualizations on 2-dimensional synthetic data. These visualizations of decision boundaries help develop intuition for how private noise impacts model predictions, particularly in class- insalaneba settings.
We generate a small (n = 1000) synthetic 2-dimensional mixture of Gaussians, where majority (negative) and minority (positive) classes are separable in the feature space. Specifically, the random vector (X1, X2] is sampled from the following
process: with probability 0.9, [X ~ ([ 0 ). and with probability 0.1, [X1 ~ (V, 4], 0
) Thus, the mixture has two components: one centered [0, 0j and the other [4, 4J. both independent and with variance 4.
Figure 4 compares the decision boundaries of non-differentially private and differentially private classifiers this data, allowing us to directly observe the impact of the privacy preserving methods on how the model makes decisions. The blue points represent majority (negative) class examples, while the red points represent minority (positive) class examples. The blue region denotes where the model will predict a negative label, and the red region denotes where the model will predict a positive label. The underlying data distributions are also visible these figures, represented as an mean-centered ellipse capturing 2 standard deviations of the id-Gaussian.
Inspecting Figure 4 helps build intuition for the effect of DP decision boundaries. We observe that Priv. Weighted FTT fails to learn meaningful decision boundary (labeling everthing negative), while Priv. LogReg is catastrophically noisy (flipping the decision boundary). GEM + NonPriv. XGBoost (Algorithm 3) is lossy relative to SMOTE + NonPriv. XGBoost, but maintains a class separating boundary.
SMOTE NonPriv. XGBonst
NonPriv. LoqReg
NonPriv. XGRonst SW)
NonPriv, Weighted FTT (With SW)
GEM NonPriv XGBoost
Pris. LogReg
Priv. Weighted LogReg
Priv. Weighted FTT
Figure 4: Top row shows decision boundaries of non-DP classifiers (high performance on the task, AUC e [0.94, 0.97). Bottom row illustrates the decision boundaries of DP classifiers = 1.0, d = 1e-5 where applicable), which perform worse. The underlying true data generating function for each class represented as an ellipse (dotted white line), where the center of the ellipse the mean and each point on the dotted line represents standard deviations from the mean.
36

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
E. Additional Experimental Results and Details
Methods Evaluated Here, we restate exhaustively the range methods we evaluate under different privacy and class imbalance conditions. We categorize methods as pre-processing or in processing methods.
We evaluate: (1) a private synthetic data method (GEM)
pre-processing step, generating class-balanced sample for downstream, non-private XGBoost model (GEM + NonPriv, XGBoosi, Section 3.3), (2) a private ERM logistic regression model as an in-processing step without class weights (Priv. LogReg, exact method from (Chaudhuri et al., 20,1), see Section 4.2), (3) private ERM logistic regression model as an in-processing step with sample weights (Priv. Weighted LogReg, our modified algorithm under class weighting, Algorithm in Section 4.2), and (4) DP-SGD trained FTTransformer model as an in-processing step with sample weights in the cross-entropy loss (Priv. Weighted FTT, Section 4.3).
We also compare the performance of these methods against the following non-private baselines: (1) vanilla XGBoost model with in processing sample weights (NonPriv. Weighted XGBoost), (2) an XGBoost model without class sample weights, pre- pre-processing step (SMOTE NonPriv. XGBoost), (3) a logistic regression model with and without sample weights (as in-processing) (NonPriv. Weighted LogReg / NonPriv. LogReg), and (4) non-private FTTransformer model with and without sample weights in the cross-entropy loss (as in-processing) (NonPriv. Weighted FTT / NonPriv. FTT). These methods serve as baselines for comparison to measure the effects of adding differential privacy, and the role of weighting in model performance.
using SMOTE
Experimental Details All datasets we chose were purposefully low-dimensional enough to be run with GEM. Neural models (GEM and FTTransformer) were trained using an NVIDIA T4 GPU, with e E {0.05, 0.1, 0.5, 1.0, 5.0} (privacy budget range following guidance from (McKenna et al., 2022)). Private models were trained for 20 epochs, while non- private models were trained for 100 epochs with early stopping. FTTransformer was initialized with default architecture hyper-parameters (dimension=32, depth=6, 8 heads, dropout of 0.1). DP-SGD was performed with the Opacus pytorch library using recommended parameters (Yousefpour et al., 2021). No hyperparameter tuning was performed for the private models to ensure "honest" comparisons (Papernot & Steinke, 2021): hyperparameters were lightly tuned for non- non-private models using randomized cross-validation Results are given with standard deviations over 10 randomly seeded data splits and parameter initializations. GEM models are computationally expensive (Liu et al., 2021; Rosenblatt et al., 2024a); they were trained in parallel on the same NVIDIA T4 and took over 50 compute hours. XGBoost and LogReg models trained within seconds, while FTTransformer models required minutes.
ID
Name
Repository & Target
r Zoo
Size n
# Features
ecoli
UCI, target: imU
8.6
336
7
2
yeast mc2
UCI, target: ME2
28
1,484
8
3.
solar_flare_mn
UCI, target: M-O
19
1,389
32
4
abalone
UCI, target: 7
9.7
4,177
10
car_eval__ 33
UCI, target: good, v good
12
1,728
21
car_eval 4
UCI, target: vgood
26
1,728
21
mammography
UCI, target: minority
42
11,183
6
8 1b
UCI, target: 19
130
4,177
10
Table 11: Imbalanced learning datasets used from the imbl imblearn package.
GEM Summary. Much of tabular private synthetic data generation has focused on matching distributions based on the broad class of linear statistical queries, often referred to as counting queries. The objective generally set up as follows: you are given finite set of queries Q, and the objective is construct a synthetic dataset D such that the maximum error across all queries in Q, defined max (g)),, is minimized.
GEM is an (e, 8)P neural method that fits private, parameterized weight distribution Go. where @ represents the learnable parameters of the model. It follows the Select-Measure -eajert-Prooect paradigm, and its main novelty lies in the project step: the method fits neural network, denoted as Gg. to approximate a distribution over the data domain in differentially private manner. This network generates a product distribution Po. where Po represents the output distribution over a discretized version of the data domain.
37

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Hyperparameter
Value
Description
Dimension of marginal considered in random query workload.
T
100
Number of iterations for the GEM algorithm.
0.67
Weighting parameter for the GEM algorithm.
loss_p
2
The p-norm used in the loss function.
1r
le-4
Learning rate for the optimizer in the GEM algorithm.
max_idxs
100
Maximum number of indices considered during each iteration.
max_iters
100
Maximum number of iterations for optimization.
ema_weights__etz
0.9
Smoothing parameter for exponential moving average weights.
embeddinggooe dim
512
Dimensionality of the embedding space for the neural network generator.
Table 12: Hyperparameters we used when running GEM and their respective descriptions.
The process works by sampling random Gaussian noise vectors 2, which are passed through the neural network Go to output a distribution Po(z) in the same domain as the target data. This product distribution normalized to ensure it behaves as a valid marginal probability vector. Once fit, arbitrarily many samples can be generated from the fully specified distribution Pg.
Any statistical query be described as function mapping Pa to value in [0. i..., ((p)) = = Po(r), where (xx) is the predicate function defining the query. Any query is differentiable with respect to the parameters 0 of the model. Given set of queries 9: E Q1:r, which are privately selected using the Exponential Mechanism, and answers ā, E Aur privately computed using an additive noise mechanism, a natural loss function for the parameterization 0 is given by:
LGEM (Q.Q = Σ (a:(Po) ā.l
KE(T]
GEM iteratively updates 0 to minimize this loss function, incorporating the observed queries and answers. The most common linear query class used are k-way marginal queries (Hardt et al., 2012; Vietri et al., 2020; Aydore et al., 2021). In our experiments, we parameterized GEM to use 3-way marginal queries. We detail other hyperparameter settings for GEM in Table 12.
PrivBayes Summary. PrivBayes builds Bayesian network to approximate the joint distribution of the data by factorizing it into sequence of conditional probabilities, which it can then sample from to create differentially private synthetic data. To ensure DP, it first selects an attribute ordering using mutual information (privatized by an additive noise mechanism) to determine parent-child relationships. Then, for each attribute, estimates the attribute's conditional probability distribution given its parent attributes using a DP noise-perturbed frequency table. Once the Bayesian network is constructed, synthetic data points are generated by sampling from the learned network.
FTTransformer Summary. We adapt recently proposed transformer-basee model, FTTransformer (Gorishniy et al., 2021), to the DP setting, which involves minor adjustments to the model architecture for compatibility with Opacus (Yousefpour et al., 2021). FTTransfrrmer is neural tabular data classifier that is competitive with well-known gradient boosting tree-based methods like XGBoost (Chen & Guestrin, 2016); its novelty lies in data transformations for attenuation by the attention layers in a transformer architecture (Wolf et al., 2020; Tay et al., 2022; Khan et al., 2022). Our empirical results rely on modifications to implementations for DP-SGD from the Opacus library (Yousefpour et al., 2021) and the base implementation for FTTransformer from (Huang et al., 2020).
After experimenting with different neural architectures in the non-private setting, we found that the FTTransformer architecture was significantly better than other methods on tabular data tasks, even for imbalanced classification. However, when transitioning to the private setting, we found that all of the neural methods using DP-SGD had trouble under class imbalance. FTTransformer still performed best among these (albeit poorly relative to other model classes), so we included the Private FTTransformer implementation to represent the class of neural models trained with DP-SGD (using a weighted cross-entropy loss, which helped a little on imbalanced classification metrics).
38

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
NonPriv XGBoost
--- PrivBayes NarPriv. XGBoost
AUC
F1
Balanced ACC.
Precision
1.00
1.00
1.00
1.00
0.75
0.75
0.75
0.75
0.50
0.50
0.50
0.50
10
10"
10
10
10
100
10
10
Recall
Worst Class Acc.
Macro Avg. Acc.
G-Mean
1.00
1.00
1.00
0.75
0.75
0.75
0.75
0.50
0.50
0.0
0.50
0.25
0.25
0.5
0.25
Figure 5: Comparison of Priv Brive (Zhang et al., 2017) and GEM (Liu et al., 2021) as private preprocessing steps on the manmography dataset, with XGBoost as the downstream non non-private classifier. PrivBayes while generally weaker, shows similar performance trends to GEM increases and strong private pre-processing step for imbalanced classification.
E.1. Performance of models on all imblearn datasets
This section presents figures that detail exhaustive performance across privacy parameter (i.e., varying from 0.01 to 5.0) for all the datasets listed in Table 11.
AUC
P1
1.0
0.0
Belanced
1.0
1.0
0.5
Mauro Avg. Acc.
G-Mean
0.5
10-1
10-1
100
GEM NonPrix XCBoost
Prw Weighted FIT
LogReg
Priv Weighted LogRngg
Figure 6: Privacy-preserving predictors across settings for ecoli dataset.
39

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
AUC
1.0
0.5
Balanced Acc.
Precision
0.5
0.0
Recall
Worst Class Acc.
1.0
0.0
Macro Avg. Acc.
G- G-Mean
1.0
0.5
0.0
10
10c
10-1
10"
GEM NonPriv. XGBoost
Priv. Weighted FTT
Priv. LogReg
Best Non. Priv.
Priv. Weighted LogReg
Figure 7: Privacy-preserving predictors across e settings for abalone dataset.
AUC
1.0
0.0
Balanced
Precision
1.0
1.0
0.5
Mauro Aug. Ace.
G-Mean
0.5
10-1
10
109
GEM NonPri XCBoost
Prov Weighted FIT
LogRig
Priu.
Priv Weighted LogRng
Figure 8: Privacy-preserving predictors across settings for car_eval_ 34 dataset.
40

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
AEC
1.0
Jelanced
Predisoon
1.0
0.5
Recal
Warst Class Act.
0.5
Macro Arg. Acc.
G-Mean
0.5
0.0
10
10
10
GEM + NonPrx XGDoost
Pri. Weighted PTT
Logfeg
Priv. Weighted LogReg
Figure 9: Privacy-preserving predictors across settings for solar solar_flare______eeeeeallaeaeeee m0 dataset.
AUC
F1
1.0
0.0
Balanced
Precision
1.0
1.0
0.5
Mauro Arg. Acc.
G-Meun
0.5
10-1
10-1
100
GEM NonPrix XCBoost
Prw Weighted FIT
LogRig
Priv Weighted LogRngg
Figure 10: Privacy-preserving predictors across settings for car_eval_ dataset.

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
1.0
Helanced
Predisoon
1.0
0.5
Recal
Warst Class Act.
0.5
Macro Arg. Acc.
G-Mean
0.5
0.0
10
10
10'
GEM + NonPri XGDoost
Pri. Weighted PTT
Logfeg
Priv Weighted LogReg
Figure 11: preeecyirrseriing predictors across e settings for yeast me2 dataset.
AUC
Fl
1.0
0.0
Belanced
1.0
1.0
0.5
Mauro Aug. Acc.
G-Mean
0.5
10-1
10-1
100
GEM NonPrv XCBoost
Pro Weighted FIT
LogReg
Priv Weighted LogRngg
Figure 12: predictors across settings for mammographyy dataset.
42

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
AUC
1.0
Predisoon
1.0
0.5
Recal
Warst Class Act.
0.5
Macro Arg. Acc.
G G-Mean
0.5
0.0
10
10
10'
GEM + NonPri XGDoost
Pri. Weighted PTT
Logfeg
Priv Weighted LogReg
Figure 13: predictors across settings for abalone 19 dataset.
43

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
E.2. Complete non-private results
Table 13: Ecoli Dataset
Standurd Bal-ACC
Imbalanced! 1
Metries
Approach
AUC
Prec//Recal
Worst-ACC
Ave-ACC
G-Mean
MCC
Non-Private
Idemtity NonPriv. LogReg
0.94 1: 0.04
0.09 0.12
0.53 1 0.04
0.3
0.07
0.06 a: 0.07
0.53 4: 0.04
0.15 = 0.19
0.11 0.16
Idemlit + NonPriv. Weighted LogReg
0.93 0.04
0.27
0.52+ 0.120..1/ +.17
0.61
0.77 +
0.75
0.51 0.13
Idonitt NonPriv. XGBoost
0.91 + 0.07
0.15
0,77 + 0.09
0.77:
0
0.77 + 0.09
0.73
0.12
0.61 0
Idcntity + NonPriv. Weighted XGBoost
0.91 :: 0.08
0.16
0.8 0.1
0.72:1:.11//633
0.3
08:
0.77 0.13
0.17
SMOTE NonPriv. LogReg
0.94 1 0.04
0.61 0.09
0.88 0.06
0 0088 0.11
0.83 0,07
0.88 1 0.06
0.88
0.06
0.59
SMOTE NonPriv. Weighted LogReg
0.94 +: 0.04
0,51 0.07
0.86 0.05
0.36 0.06/ = 0.1
0.79 0.06
0.86+ 0.05
0.85
0.05
0.5 = D.08
SMOTE-+ NonPriv, Weighted XGB
0.68 +
0.85
0.65 0.12.
0.74
0.85 0.07
0.84 0.08
0.11
SMOTE- NonPtriv. XGBoost
0.94 0.04
0.7 0.11
0.85 + 0.08
0.7 0.74
0.74
0.85 + 0.08
0.84
0.68 0.12
Identity + NonPriv. Weighted FTTransformer
0.51 A.1:2:0.12
0.12 0.09
0.51
0.12 1: 0.10 0.11
0.13
0.51
0.11
Table 14: Abolone Dataset
Standard BaI-ACC
Imbalanced 1
Metries
Approach
AUC
Prec/Reccal
Worst-ACC
Avg-ACC
G-Mean
MCC
Non-Private
ldcnlit + NonPriv. LogReg
0.81 : 0.02
0.0 0.0
0.5 15::00 0.0
0.000.0 0.0
0.0 0.0
0.5 : 0.0
0.0
0.0 0.0
Identit NonPriv. Weighted LogReg
0,81 1 0.02
0.38 0.03
0,73
1 0.03
0,27 1: 0.03 00,03/0.63. 1: 0.04
0.63 1: 0.04
0.73 1 0.03
0.72 0.03
0.32 1: 0.04
Identity NonPriv. XGBoost
0,84 :: 0.02
0.19 0.05
0.55 4 0.02
0.29 :: 0.08
0.04
0.14 0.04
0.55 : 0.02
0.36
0.05
0.15 0.06
Ideniity NonPriv, Weighted XGBoost
0.84 0.02
0.35 0.04
0.66
0.04 0..4 0.05
0.43 0.05
0.66+ 0.03
062 0.04
0.28 0.28
SMOTE NonPriv, LogReg
0.83 :: 0.02
0,36
0.78
: 0.02
0.22 : 0.01 /088 = 0.03
0.69 0: 0.02
0.78 1 0.02
0.77 = 0.01
0.34 0.02
SMOTE++
Weighted LogReg
0.00
0.76
0.19 1:
0.03
0.76
0.74 000
SMOTE NonPriv. Weighted XGB
0.84 1: 0.02
0.37 1: 0.04
0.69 0.03
0.3 1. 0.04 0.49 0.07
0.49 :: 0.07
0.69 4: 0.03
0.66 0.04
0,3 = 0.05
SMOTE NonPriv. XGRoost
0.84 0.02
0.04
0.64
0.29 + 00.6
0.36
0.64
0.04
0.04
Idanityy NonPriv, Weighted FTTransfomeer
0,70 0.03
0.06 +: 0.09
0.52 + 0.04
0,19 :: 0.20 0.07
= 0.14
0.07 = 0,14
0,52 : 0.04
0.19 0,19
0.08 0.08
Table 15: Car_ eval 34 Dataset
Standard
Imbalanced 1
Metries
Appronch
AUC
F1
BaI-ACC
Prec/Recall
Worst-ACC
Avg-ACC
G-Mean
MCC
Non-Private
Identity NonPriv. LogReg
1.0 +
0,86 0.05
0.89 0.04
0.95 + /0.79 + 0.08
0.79 + 0.08
0.89 + 0.04
0.89
0.05
0.85 0.05
Idomiity NonPriv, Weighte LogReg
1.0 0.0
0.85 :: 0.03
0.98 + 0.9
0.74 = 0.05 1.0 0.0
0.97 2: 0.01
0.98 :: 0.0
0.98 0.0
0.84 0.03
Identity NonPtiv, XGBoost
0.0
0.02
0.98
0.94
0.97 0.03
0.98
0.02
Identity NonPriv. Weighted XGBoost
1.0 -: 0.0
0.94 1:41:000 0.03
0.99 1: 0.0
0.89 :: 0.05 1.0 +: 0.0
0.99 2: 0.01
0.99 1: 0.0
0.99 1 0.0
0.94 0.03
SMOTE+ NonPriv. LogReg
0.03
0.98
0.74 0.04/
0.97
0.98 0.0
0.98 0.0
0.03
SMOTE+ NonPriv, Weighted LogReg
1.0 0,0
0.73 0.03
0.97 0.0
0,58 = 0.03 / 1.0 = 0.0
0.94 0.01
0.97
0.97 0.0
0.74 0.02
SMOTE+ NonPriv. Weighted XGB
1.0
0,95 0.02
0.99 : 0.01
0.92 : 0.05 / 0.99 : 0.02
0.98 0.01
0.99 : 0.01
0.99 = 0.01
0.95 0.02
SMOTE+ NonPriv, XGBoost
1.0 0.0
0.96 1.661000 0.02
0.98 0.01
0,94 1: 0.04 / 0.97 1: 0.03
0.97 1: 0.03
0,98 1 0.01
0.98 001
0.95 0.02
Identity NonPriv, Weighted PrTransformer
1.00 +: 0.00
0.92 0.04
0.96 + 0.03
0.91 + 0.04/ / 0.94 + 0.06
0.93 +: 0.06
0.96 +: 0.03
0.03 0.03
0.04 0.04
Table 16: Solar_ faarr_lare_mddd Dataset
Standard
Imbalanced 1
Metrics
Approach
AUC
Bal-ACC
Prec/Recall
Worst-ACC
Avg-ACC
G-Meun
MCC
Non-Private
Identity NonPriv. LogReg
0.79 1: 0.06
0.03 1 0.05
0.51 1: 0.02
0.15 1 0,34/0.01
4: 0.03
0.01 :: 0.03
0.51 :: 0.02
0.05 = 0.11
0.04 1 0.1
Idcntity + NonPriv. Weighted LogReg
0.79 : 0.06
0.25 0.08
0.67
: 0.08
0.17 : 0.05 00.05/0:444
0.16
0.44 :: 0.16
0.67 : 0.08
0.62 = 0.11
0.22
Identity NonPriv, XGBoost
0,73 0.04
0.09 1: 0.09
0.53 0.03
0,17 1 0.16/
1 0.06
0.06 2: 0.06
0.53 1 0.03
0.19
0.19:0117 0.17
0.08 0.09
Identity: NonPriv. Weighted XGBoost
0.74 0.04
0.2 : 0.05
0.61
4 0.04
0.15 : 0.04/ + 0.09
0.31 : 0.09
0.6 : 0.04
0.53 = 0.07
0.15 0.06
SMOTE+ NonPriv Logkeg
0.76+0007 0.07
0.19+
0.67 0.06
0,11 + 0.02.
0.12
0.57=0.1
0.67 + 0.06
0.66 000
0.17+
SMOTE- NonPriv. Weighttdd LogReg
0.75 0.07
0.17 0.03
0.69
2 0.06
0.1 0.02 0.75 0.13
0.63 163:00005
0.69 0.06
0.69 = 0.06
0.17
SMOTE++ NonPriv, Weighted XGB
0.04
0.96
0.52
0.06/
0.52 0.1
0.27
SMOTE+ NonPriv. XGBoost
0.7-1.0.05
0.07 1 0.06
0.52 1: 0.02
0.08 1: 0.07 / 0.06 4: 0.05
0.06 1: 0.05
0.52 : 0.02
0.2
0.03 0.05
Idenlity + NonPriv. Weighted PiTranfformer
0.76 0.06
0.12
0.53
0.20 + 0.07 0.08
0.06 + 0.08
0.53 +
0120 0.20
0.14
44

---

Differential Privacy Under Class Imbalance: Methods and Empirical Insights
Table 17: @ar_eval_4 4 Dataset
Standard
Imbalanced 1
Metrics
Approuch
AUC
F1
Bal-ACC
Prec/Recall
Worst-ACC
Avg-ACC
G-Mean
MCC
Non-Privute
Identit NonPriv. LogReg
1.0 1 0,0
0.75 1: 0.1
0.82 0.07
0.93 1 0.08 / 0.64 1: 0.13
0.64 a: 0.13
0.82 1: 0.07
0.79 = 0.08
0.76 4: 0.1
Identity NonPriv. Weighted LogRey
1.0 +: 0.0
0.75
0.06
0.99 +: 0.9
0.6 0.08 / 0.0
0.97 : 0.01
0.99 0.0
0.99 0.0
0.76 0.05
Ideniity NonPriv, XGBoost
1,0+:00 0.0
0.06
0.99 0.03
0,98 + 0.07 F0.98 0.05
0.98 =: 0.05
099 0.03
0.99
000
0.98 0.06
ldmiliy+ + NonPtiv. Weighted XGBooos
1.0 0.0
0.85 1: 0.06
0.99 0.0
0.74 = 0.09/ / 1.0 + 0.0
0.99
0.99 0:0
0.99 099:00
0.85 :: 0.06
SMOTE+ NonPriv. LogReg
0.0
0.68
0.98 0.01
0,99
0.99
SMOTE NonPriv. Weighted LogReg
1.0 +: 0.0
0.77 à: 0.06
0.99 4: 0.0
0.63 +: 0.08 / 1.0 + 0.0
0.98 :: 0.01
0.99 + 0.0
0.99 +.0 0.0
0.78 : 0.05
SMOTE+ NonPriv. Weighted XGB
1.0
0,96 0.06
1,0
0.92
0.0
1.0-0.11
1,0+
1.0
0.06
SMOTE+ NonPriv. XGBoost
0.0
0.97 0,05
0.99 0.01
0,95 = 0.09 0,99 = 0.02
0.99 = 0.02
0.99 0.01
0.99 0.01
0.97 = 0.05
Identity + NonPriv. Weighted FTTransforme
0.99 1: 0.01
0.82 0.10
0.94 1: 0.97
0.78 4 0.14 / 0,90 0.14
0.89 2: 0.13
0.94 1: 0.07
0.07 = 0.07
0.10 : 0.10
Table 18: Yeast_me's Dataset
Standard
Imbalanced 1
Metries
Approach
AUC
F1
Bal-ACC
Prec//Recal
Worst-ACC
Avg-ACC
G-Mean
MCC
Non-Private
Identity NonPriv. LogReg
0,88 1: 0.06
0.0 0.0
0.5 0.0
0.0 2: 0,0 4: 0.0
0,0 s 0.0
0.5 4 0.0
0.0 0.0
0.0 0.0
Idemiity NonPriv. Weighted LogReg
0,88 + 0.06
0.27 + 0.07
0.56 + 0.04
0.22 + 0.07 + 0.08
0.37 + 0.08
0.66 + 0.04
0.59 + 0.07
0.25 0.07
Idaniity NonPiiv, XGBoost
0.03
0.13
0.62
0.52 0.18/
0.25
0.22 0.05
0.49
0.14
Idemiit+ + NonPtiv. Weighted XGBoost
0.94 1: 0.03
0.113
0.77 1 0.08
0,38 1: 0.13 /0.13//0.55 :: 0.15
0.58
0.77 1 0.08
0.74
0.45 0.14
SMOTE+ NonPriv. LogReg
0.94
0,18 1:
+: 0.14
0.78
0.84
0.07
SMOTE + NonPriv. Weighted LogReg
0.94
0.2 0:01
0.82 + 0.04
0.11 /0.89 1999-...1 0.1
0.74+00.0
0.82 0.04
0.82 - 0.04
0.03
SMOTE+ NonPriv. Weighted XGB
0.92 0.04
04 0.09
0.71 1
0.39 :: 0.12//.455 0.08
0.45
0.71 + 0.04
0.66
0.07
0.39
SMOTE+ NonPriv. XGBoost
0.92::0000
0.12
0,71
+ 0.06
0.41 1: 0.15 0.12
0.45
0.71 1 0.06
0,66
0.1
0.41 1 0.12
Identit+ + NonPriv. Weighted FTTransformer
0.51 1: 0.10
0,03 0.04
0.50 4: 0.05
0.02 1: 0.03 / 0.09
1: 0.16
0.09 1: 0.16
0.50 : 0.05
0.22
0.22
0,05 0.05
Table 19: Mammography Dataset
Standard
Imbalanced 1
Metries
Approach
AUC
F1
Bal-ACC
Prec//Recal
Worst-ACC
Ave-ACC
G-Mean
MCC
Non-Private
Identit NonPriv LogReg
0.9 1 0.02
0.53 0.05
0.7 1 0.03
0.8 1: 0.07 /0. 1: 0.06
0:4 0.06
0.7 0.03
0.63 = 0.05
0.55 0.05
Identity + NonPriv. Weighted LogReg
0.91 1: 0.02
0.4 :: 0.02
0.84 1: 0.02
0.27 1 0.02
1: 0.05
0.73 1: 0.05
0.84 1 0.02
0.84
0.03
0.43 0.03
Idenlity NonPriv. XGBoos
0.94 + 0.02
0.69 + 0.04
0.79 0.03
0,82 + /0.59 + 0.06
0.59 + 0.06
0.79 + 0.03
0.77
0.04
0.69 0.03
Idemiity NonPriv, Weighted XGBoost
0.94 + 0.02
0.65 :: 0.04
0.87 + 0.03
0.57 : 0.04 + 0.06
0.75 0.06
0.87 :: 0.03
0.86 = 0.04
0.65 :: 0.04
SMOTE+1 NonPriv. LogReg
0.29 0.01
0.17
0.05
0.86
0.02
0.35
SMOTE- NonPriv. Weighted LogReg
0.92 1: 0.02
0.19 0.01
0.85 1: 0.02
0,11 1: 0.01 / 0.88 1: 0.03
0.82 :: 0.01
0.85 1 0.02
0.85 = 0.02
0.27 1 0.01
SMOTE+ NonPriv. Weighted XGB
0.92 0.02
0.04
0.87
0.58 0.06 0.75
0.75
0.87 +
0.02
0.04
SMOTE+ NonPriv. XGBoost
0.93 +: 0.02
0.65
+ 0.04
0,86
+ 0.03
0.59 + 0.05 / 0.73 + 0.05
0.73 0.05
0.86 + 0.03
0.85
= 0.03
0.65 0.04
ldcnlity + NonPriv, Weighted FTTransfommrr
0.88 :: 0.03
0.21 0.16
0.59 + 0.08
0.40 = 0.34 0.17
0.19 1.19:0.11 0.17
0.59 : 0.08
0.23 0.23
0.16 0.16
Table 20: Abolone_ 19 Dataset
Standurd
Imbalanced 1
Metrics
Appronch
AUC
F1
BaI-ACC
Prec/Recall
Worst-ACC
Avg-ACC
G-Mean
MCC
Non-Private
Identit NonPriv. LogReg
0.75 1 0.11
0.0 0.0
0.5
1.0.0 0.0
0.0 1: 0.0 1 0.0
0,0 1 0.0
0.5 : 0.0
0.0 0.0
0.0 0.0
Identity NonPriv. Weighted LogReg
0.72 4: 0.11
0.06 4: 0.05
0.59 4: 0.1
0.03 :: 0.03 :: 0.18
0.25 :: 0.18
0.1
0.2 = 0.25
0.07 0.07
Ideniity NonPriv. XGBoost
0.72.+0.11 0.12
0.03
0.09
0.51
0.03
0.32 0.02 0.05
0.02+00.05
0.51 + 0.03
0.04 00440011
0.04+0.13
Idamiity + NonPriv, Weighted XGBoost
0.76 0.11
0.04
1 0.04
0.55
2 0.07
0.02 = 0.02 = 0.15
0.15
0:5
0.29 = 0.26
0.04 0.06
SMOTE++ NonPriv. LogReg
0.82 0.06
0.76 0.08
0.02 0.0
0.76 0.13
0.000
SMOTE- NonPriv. Weighted LogReg
0.83 4: 0.06
0.03
1: 0.0
0.73 1: 0.06
0.02 :: 0.0 4: 0,13
0.66 0.02
0.73 0.06
0.73 - 0.05
0.08 0.02
SMOTE+ NonPriv. Weighted XGB
0.79++0.1
0.08
+ 0.06
0.57
0.06 + 0.04 0.11
0.17+
0.57+0006
0.36+02
0.09
SMOTE+ NonPriv. XGBoost
0.78 :: 0.09
0.08
: 0.07
0.57 0.07
0.06
= 0.05 0.15
0.15
0.57 0.07
0.31
0223
0.08 0.08
Ideatity + NonPriv. Weighted FTTransformer
0.56 1: 0.09
0.01 1: 0.01
0.53 1 0.10
0.00 1: 0.01 0.38
0.12 0.12
0.53 1 0.10
0.29 2 0.29
0.04 0004100 0.04
45


Reviews:
[{"review_id": "ol8ECDWyIW", "reviewer": "Reviewer_uyZY", "summary": "The paper explores class imbalance in differentially private ML settings. The authors consider common pre-processing and in-processing methods for dealing with class imbalance, and look at extending them to the DP setting. They show that some commonly used non-private methods like SMOTE are not well suited to the DP setting and that alternatives like DP synthetic data or DP-weighted ERM perform better in a private class imbalance setting. Experiments are performed over 8 benchmark imbalanced binary classification datasets.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **(Q1) Why XGBoost instead of using GEM+LogReg?**\n\nThank 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. \n\nHowever, 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.\n\n> **(Q2) Do you see natural extensions to SMOTE that are privacy-friendly...?**\n\nThank 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. \n\nInstead, 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).\n\n> **(Q3)...How can the leading methods be extended to multiclass settings?**\n\nThank 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.**\n\n> **(Q4)...rejection sampling or conditional sampling (GEM)**\n\nIn 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.\n\n> **(Q5)...was any of the GEM training procedure changed?**\n\nNo 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.\n\n> **(Q6)...DP-SGD minibatch size clarification.**\n\nApologies, 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!", "claims_and_evidence": "The paper generally make two main claims:\n1. The first claim is that oversampling methods are poor for DP settings as they increase the sensitivity of DP algorithms that are trained on them. This is supported by clear theorems that show the sensitivity is amplified and these approaches are not well-suited.\n2. The second is that the use of DP synthetic data is the strongest approach for dealing with class-imbalance. This is fairly well-supported by an extensive set of experiments, although some results I feel are misleading or unclear (see weaknesses + questions below).", "methods_and_evaluation_criteria": "The methods and evaluation criteria used are suitably chosen for the problem and are fairly exhaustive. The paper considers a good number of methods for dealing with class imbalance (as highlighted in Table 1) and how to extend them to a DP setting. Experiments are performed over 8 commonly used benchmark datasets in imbalanced binary classification problems and multiple evaluation metrics are presented for the classifiers.", "theoretical_claims": "I did not review the full technical proofs (contained in the appendix) but the stated results in the main paper seem to logically follow.", "experimental_designs_or_analyses": "The experimental design is generally sound. The methods are ranked across 8 benchmark datasets for imbalanced data and a specific dataset is chosen to highlight multiple evaluation metrics across the methods.  However, I have a few issues with the setup used for GEM (see questions below).", "relation_to_broader_scientific_literature": "The key contributions fit well into the broader literature on DP-ERM and private synthetic data generation and as far as I am aware, these methods have not been studied extensively in class-imbalance settings. To the best of my knowledge, this is also the first work to extensively study the class-imbalance setting under DP.", "essential_references_not_discussed": "There are no related works that I feel are missing or not discussed.", "other_strengths_and_weaknesses": "**Strengths:**\n\n- Class imbalance in a DP setting is an important practical problem that has many uses yet is not well-studied in the literature.  This paper addresses and fills this research gap.\n- The paper covers a wide-range of class imbalance methods for both pre-processing and in-processing and shows how to extend them to the DP setting. The experiments are also extensive and show a clear conclusion that DP synthetic data is the most robust method.\n- The paper is well-written and generally clear.\n\n**Weaknesses:**\n\n- The results are limited to binary classification settings and it is not immediately clear how findings or some methods can be extended to a multi-class setting.\n- The leading conclusion is that DP synthetic data is a strong option to handle class imbalance, however the evaluation against other baselines seems unfair (see below).\n- I think SMOTE presented as is, is also an unfair baseline (see questions below).", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. The GEM+XGBoost method is misleading because it is compared against (mostly) logistic regression baselines. It is unclear from Table 3 how much of the benefit comes from the DP synthetic data or if the benefit is from the actual XGBoost model vs. the simpler logistic regression models. Why was XGBoost chosen instead of using GEM+LogReg? Indeed, some of the tables in the Appendix for the non-private setting highlight that there is often a big accuracy discrepancy between (non-private) LogReg and XGBoost and this would also be reflected in the DP experiments.\n2. The comparison for SMOTE seems somewhat unfair. As stated, using SMOTE as-is increases the DP sensitivity which in turn amplifies the DP epsilon needed to maintain the same level of DP which is a nice result. However, the actual SMOTE algorithm has not been adapted for privacy compared to other methods specifically changed to provide DP guarantees. Do you see natural extensions to SMOTE that are privacy-friendly, i.e., by perturbing points that are sampled?\n3. How can the leading methods be extended to multiclass settings? It’s briefly discussed for the oversampling methods like SMOTE, but do the methods like synthetic data and weighted ERM easily extend?\n4. For GEM, it is unclear to me if rejection sampling was used or conditional sampling? If conditional sampling, was the generator network structure changed over the standard GEM approach?\n5. Was any of the GEM training procedure changed to adapt to a class-imbalanced setting? More specifically, for the workload of queries given to GEM, do you have suggestions for achieving best accuracy in imbalanced settings?\n6. To clarify in L340, I presume $B$ in the $2C/B$ refers to the DP-SGD minibatch size? I am not sure this is clear from the main paper.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RDVuNVXRFd", "reviewer": "Reviewer_KHpD", "summary": "This paper deals with the (in)consistency of differential privacy and imbalanced class learning, especially binary classification problem where the minority class is very small. The non-private learning algorithms for the imbalanced classes usually increase the weights of minority classes through oversampling, argumentation, Bagging, reweighting methods etc. However, these methods are shown to be inconsistent with differential privacy because DP would increase the privacy risk, bias and unfairness. So this paper evaluated the private versions of these methods and provide some suggestions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **...related to invidualized differential privacy, not discussed...**\n\nWe 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.\n\n> **(W1) ...did not find a formalization / could not find solutions...**\n\nA 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.\"\n\nOur 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.\n\n> **(W2)...didn't know what was central and main proposition...**\n\nOur work does not have a single central theorem; instead, we compare a variety of methodologies for imbalanced classification under differential privacy constraints.\n\n> **(W3)...Proposition 2 trivial...**\n\nWe 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.\n\n> **(W4)...Theorem 5 is confusing...**\n\nDue 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.\n\n> **(W5) (typos)**\n\nThank 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\\\\}$) \n\n> **(Q1) [what do we mean by assuming that FP and FN have equal misclassification costs]?**\n\nThis 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.\n\n> **(Q2)...privacy loss scale in Lines 78-80?**\n\nCertainly. 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.\n\n> **(Q3) Line 6 in Algorithm 1**\n\nLine 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.\n\n> **(Q4) (explain Line 1795)?**\n\nThe 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.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "not all of them. I checked some essential ones and those in Section 3. They are correct.", "experimental_designs_or_analyses": "yes. The experiments are well-designed", "relation_to_broader_scientific_literature": "This paper helps better understand the relationship between differential privacy and those standard learning algorithms for imbalance classes.    It seems that it is related to invidualized differential privacy in the literature, which is not discussed in the paper.", "essential_references_not_discussed": "no as far as I know", "other_strengths_and_weaknesses": "Strengths:  \n\n(1) The paper provided a systemetic evaluation of different differential private algorithms used in the standard machine learning for imbalanced classes.  The observations are interesting and convincing. \n(2)The paper tackles an interesting and important problem in practice. \n\nWeakness:\n(1) The abstract says this work\"formalizes these challenges\". But I did not find such a formalization.  Also the abstract says that this paper \"provides a number of algorithmic solutions\".  I could not find those solutions in the paper.   My impression is that this paper mainly focus on the evaluation of the DP version of those learning algorithms for imbalanced learning not on the methods. \n(2) The presentation is a little sloppy. Moreover, different parts seems to be isolated from each other.  There are many propisitions in this paper. It seems that they are just flattened.  I don't know which one is the central and main proposition. \n(3) Proposition 2 is trivial.  It is an easy observation. \n(4) Theorem 5 is very confusing.  There are no explicit intuition before this proposition. \n(5)  Algorithm deals with multi-label classification inAlgorithm 1 instead of binary classification problem as specified in Introduction.", "other_comments_or_suggestions": "(1) Line 85: undersampling -> subsampling\n(2) Line 152: L2->L_2", "questions_for_authors": "Q1:  In the last senetence of the first paragraph in Introduction, \"these methods ...  assume that false posi\u0002tives and false negatives have equal misclassification costs\". What does this mean?\nQ2:  Could you explain more about the privacy loss scale in Lines 78-80?  \nQ3:  Could you explain Line 6 inAlgorithm 1?\nQ4: Could you explain the reason why \"Re-weighting of samples in the loss function pre-clipping does not affect these privacy\nguarantees\" (Line 1795)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "I6ozB5QrzH", "reviewer": "Reviewer_EyJH", "summary": "This paper studies the problem of privacy when the dataset is imbalanced such that there is one class that has significantly less data points than the other class. Specifically, the paper tackles the problem of training a binary classifier on imbalanced data. Known techniques for up-sampling the minority class data samples are studied and compared, while discussing the shortcomings and advantages of each. This was also shown experimentally.\n## update after rebuttal\nThe authors have shed more light to their contribution; therefore, I raised my score to a 3.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **The paper is very well written and easy to read and follow.**\n\nThank 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.\n\n> **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.**\n\nWe 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: \n\n**(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. \n\n**(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). \n\n**(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).", "claims_and_evidence": "The paper supports the claims well with experiments.", "methods_and_evaluation_criteria": "The methods to evaluate the results are valid and they use real datasets, which is very good to show the real implications of this problem and different techniques.", "theoretical_claims": "Although the work is mostly empirical, there are some propositions, lemmas, and theorems. Mainly, the proofs are in the appendix. I checked the correctness to the best of my ability, and I did not find any issues.", "experimental_designs_or_analyses": "The experiments were designed well to support the claims of the paper. The comparisons done between the different private up-sampling techniques and their effect on the accuracy of the model supported the claims made in the paper.", "relation_to_broader_scientific_literature": "This work offers a good overview and comparison of the different techniques that could be used when the data is imbalanced. This would be helpful in some areas, such as medicine, where data could be very skewed.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper is very well written and easy to read and follow. 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. I would recommend another venue for this work.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k7VhkYn8df", "reviewer": "Reviewer_PW3A", "summary": "This work looks at training classifiers with differential privacy (DP) guarantees in the presence of data imbalance (in the binary classification case) while enforcing fairness guarantees. They look at data augmentation methods and in-processing methods where fairness is attempted to be imposed by changing the model training process (viz. by using weights for different classes). It is seen that sophisticated private data augmentation methods (viz. GEM) tend to outdo in-processing based methods and certainly outperform non-private upsampling/oversampling methods. In addition, data augmentation needs to be done carefully and privately, as methods like oversampling or SMOTE can increase the sensitivity of the data due to dependence on existing minority samples.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **…limited to binary classification…insights on generalizing to the multiclass setting?**\n\nThank 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:\n\n**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. \n\n**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.\n\n**For GEM / Other Synthetic Data:** \nExtending 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.\n\n>  **...please justify why it is valid/fair to compare using different models for each method?**\n\nThank 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. \n\nOur 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. \n\nThese 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).\n\nThen, within each approach *variant* (disparate approaches both in pre-processing and in-processing), we selected candidates for highlighted comparison:\n\n1. **Most performant pre-processing methods (GEM, DP Synthetic Data)**:\nWe 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.\n\n2. **Most performant in-processing methods (Weighted ERM and DP-SGD with FTTransformer)**:\nThese 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.\n\nWe 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.\n\nIn 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 ).", "claims_and_evidence": "* The claims are supported by strong empirical evidence over binary classification tasks for different models for 8 datasets from imbalanced-learn and across multiple methods.\n* Some claims about privacy are backed up by theoretical DP guarantees.", "methods_and_evaluation_criteria": "* Yes they do.\n* However, the authors do not appear to use the same classifier architecture across all different methods, which concerns me as regards to the fairness of comparison.", "theoretical_claims": "* The proofs seem correct, at least for the one on naive oversampling. I have not been through other proofs in detail.", "experimental_designs_or_analyses": "* I think there's only one issue, that is with the heterogeneity of model types/architectures used for comparing different methods, as discussed in \"Methods and Evaluation Criteria\". It might be that this is a solid evaluation, but I need to understand the authors' choice of using different models for different methods better: 1) Why did they decide to use different models (XGBoost, logistic regression, FTTransformer)? What influenced their choices? Is this really an apples-to-apples comparison? 2) What may change if they use the exact same classifier across privacy-addition methods, so to speak?", "relation_to_broader_scientific_literature": "* This supplements previous work on fairness in terms of utility and privacy (viz. Tran et al.) and works on alleviating data imbalance (viz. SMOTE), including by generating synthetic data with DP (viz. GEM, PrivBayes), in the context of machine learning, and contributes in terms of studying the efficacy of data processing or in-processing as a way of imposing fairness requirements. This investigation is timely and important as practitioners may benefit from studying the efficacy of these methods in terms of balancing fairness and privacy guarantees while maintaining utility.", "essential_references_not_discussed": "No missing references come to mind.", "other_strengths_and_weaknesses": "* Please refer to aforementioned comments. I think this paper has many strengths and provides a nice overview of using fairness-aware DPML methods to practitioners.\n* However, one big weakness (potentially) is the heterogeneity of the classifier types used in the evaluation, which potentially is not an apples-to-apples comparison between the methods discussed in the paper.\n* One minor limitation, which the authors acknowledge (and should not be held too strongly against them) is that their discussion and evaluation is limited to binary classification. However, it will be appreciated if the authors can provide a few more insights on generalizing it to the multiclass setting, beyond what is discussed in the paper.", "other_comments_or_suggestions": "None.", "questions_for_authors": "* Can the authors please run experiments over all the methods that they discuss but compare over the same architecture for a better apples-to-apples comparison? This alone, if addressed, will be sufficient for me to raise my score.\n* Or can you please justify, very concretely, why it is valid and fair to have a comparison using different models for each method? I know that there might be some limitations (viz. bagging only being possible with certain architectures viz. XGBoost). However, could it be that there exists another compatible architecture which, if used, may lead to a different trend?\n\nAs such, with the heterogeneity between models, I cannot fully certify if the empirical takeaways are actually valid, because this does not seem like an apples-to-apples comparison. What would help is if these trends are seen while using the **same** model across all these methods.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper initiates an examination of the differential privacy properties of representative pre-processing and in-processing methods for class imbalance learning, with new insights backed up by theoretical and empirical justifications. 

The work is well-presented and paves the way for further investigations on private class imbalance learning. All reviewers are on the positive side. In the final paper, authors are encouraged to clarify the issues raised in reviewers, especially regarding the choice of baselines in Table 3 and its implications as suggested by reviewers uyZY/PW3A.
Decision: Accept (poster)