INO-SGD: Addressing Utility Imbalance under Individualized Differential Privacy
Authors: Xiao Tian
Jue Fan
Rachael Hwee Ling Sim
Bryan Kian Hsiang Low
Venue: ICLR 2026 Poster (2026)
Keywords: differential privacy
individualized differential privacy
IDP-SGD
data imbalance
utility imbalance
accuracy disparity
collaborative machine learning
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We identify that under individualized DP, different privacy budgets of data owners can induce undesirable utility imbalance during deployment, and propose the first algorithm INO-SGD to address it.

Abstract: Differential privacy (DP) is widely employed in machine learning to protect confidential or sensitive training data from being revealed. As data owners gain greater control over their data due to personal data ownership, they are more likely to set their own privacy requirements, necessitating individualized DP (IDP) to fulfil such requests. In particular, owners of data from more sensitive subsets, such as positive cases of stigmatized diseases, likely set stronger privacy requirements, as leakage of such data could incur more serious societal impact. However, existing IDP algorithms induce a critical utility imbalance problem: Data from owners with stronger privacy requirements may be severely underrepresented in the trained model, resulting in poorer performance on similar data from subsequent users during deployment. In this paper, we analyze this problem and propose the INO-SGD algorithm, which strategically down-weights data within each batch to improve performance on the more private data across all iterations. Notably, our algorithm is specially designed to satisfy IDP, while existing techniques addressing utility imbalance neither satisfy IDP nor can be easily adapted to do so. Lastly, we demonstrate the empirical feasibility of our approach.

Published as a conference paper at ICLR 2026
INO-SGD: ADDRESSING UTILITY IMBALANCE UNDER INDIVIDUALIZED DIFFERENTIAL PRIVACY
Xiao Tian :2, Jue Fan Rachael Hwee Ling Sim' & Bryan Kian Hsiang Low!
*Department of Computer Science. National University of Singapore 2 "Ageney for Science, Technology and Research (A (A*STAR), Singapore
{xiao. tian, jue. . fan, rachael sim sim)@u.uoo nus. edu lowkhê comp. nus. edu.sg
ABSTRACT
Differential privacy (DP) is widely employed in machine learning to protect confi- dential or sensitive training data from being revealed. As data owners gain greater control over their data due to personal data ownership. they are more likely to set their own privacy requirements, necessitating individualized DP (IDP) fulfil such requests. In particular, owners of data from more sensitive subsets, such as positive cases of stigmatized diseases, likely set stronger privacy requirements, as leakage of such data could incur more serious societal impact. However, exist- ing IDP algorithms induce critical utility imbalance problem: Data from own- ers with stronger privacy requirements may be severely underrepresented in the trained model, resulting in poorer performance on similar data from subsequent users during deployment. In this paper, we analyze this problem and propose the INO-SGD algorithm, which strategically weights data within each batch to improve performance the more private data across all iterations. Notably, our algorithm is specially designed to satisfy IDP, while existing techniques address- ing utility imbalance neither satisfy IDP nor can be easily adapted to do so. Lastly, we demonstrate the empirical feasibility of our approach.
INTRODUCTION
Machine learning (MI.) focuses on building a model that draws patterns from existing data so that can be applied to future prediction tasks. Since data is essential yet always scarce, model owners who possess and train ML models often have to collect data from individual data owners. For example, medical institutes acquire data from hospitals to train a model that predicts the risk of heart diseases (Panagopoulos et al. 2022). To build the best model. model owners should ideally be allowed to use all data without restrictions. However, this brings potential threat to data owners' privacy when some third-party users access the trained model. For example, adversarial techniques such as membership inference attacky (Shokri et al.) 2017) can reveal identity sensitive data. Thus, model owners must ensure data privacy when training models to achieve long-term healthy collaboration.
Existing works have established advanced techniques to represent and preserve privacy. Differential privacy (DP) introduced by Dwork (2006) is a widely accepted measure of privacy. The core intu- ition behind DP is that personal information is protected if for any individual datum d, any dataset with d results in a trained model that is almost indistinguishable from another model trained on the same dataset without d with regards to a predetermined privacy budget set by data owners. Then a potential attacker cannot tell for certain from the trained model whether an individual datum is present in the dataset. Based on DP, many differentially private MI. (DP-MI.) techniques have been developed and deployed, including differentially private stochastic gradient descent (DP-SGD) (Abadi et al. 2016). where Gaussian noise is used to perturb the gradient at each SGD step.
With rising awareness of data protection and privacy, many laws have legally enforced personal data ownership, such as General Data Protection Regulation (GDPR) (Regulation, 2018 in the European Union and California Consumer Privacy Act (CCPA) (Pardau 2018) in the United States. Such laws state that data are legal properties of their owners, which entitle data owners to decide the extent which model owners can use their data and hence indicate their own privacy requirements.

---

Published as a conference paper at ICLR 2026
In practice, privacy requirements can vary across data owners (Berendt et al. 2005 Jensen et al. 2005). For example, owners of data from more sensitive subsets (e.g., positive cases of stigmatized diseases, historically disadvantaged races) may require stronger privacy in classification tasks as data leakage could incur discrimination or denial of services (Best & Arseniev-Koehler, 2023 Lai & TTnnner 2022). At first glance, model owner can fulfil such individualized differential privacy (IDP) requirmennts by maintaining the strongest level of privacy across all data owners. However, as described by the privacy-utility tradeoff (Makhdoumi & Fawaz, 2013), using the strongest DP level undesirably reduces the utility (performance) of the trained ML model. To exploit each owner's s privacy budget as much as possible (to attain highest utillity,, BBenisch et al.) (2024) proposes individualized DP-SGD (IDP-SGD) to achieve IDP, which we introduce in detail in Sec. 2.1
However, (I) does IDP-SGD have any limitation, such as when data owners holding different groups of data within the data space have different privacy requirement?? For example, in classification problems, each class might have different privacy requirements; privacy requirements may vary across categories of data sharing similar traits (e.g., different types of the same disease). In Sec. S.I. we show that IDP-SGD has the following issue: when data owners with exclusive data have different IDP requirements, the trained ML model may have lower utilities for the more private owners. During deployment, the imbalanced utilities will negatively affect the model owner (e.g., medical institute with disease model) and subsequent users (e.g., patients with the same diseases as the more private owners) affected by the model's s decisions. This leads to the next question: (II) Can we proactively correct this IDP-induced utility imbalance across data owners? To address this, we propose the individualized noisy ordered SGD (LNO-SGD) algorithm in See. 3.2 Our key idea is that we should down-weight certain less important gradients, which in our case harm the model, as they worsen the imbalance and distract the model from learning the more difficult data, which would be from the more private owners or harder-to-predic data from less private owners. Importantly, the algorithm has to be specially designed such that it still satisfies each data owner's s IDP requirement, and we explain in Sec. 3.1 why existing techniques addressing data imbalance cannot be easily adapted to do so. We theoretically analyze the benefits of INO-SGD in Sec. 3.3 and demonstrate its empirical performance in Sec. 4
2 BACKGROUND AND RELATED WORKS
2.1 (INDIVIDUALIZED) DIFFERENTIAL PRIVACY
Let DD be the collection of datasets. Two datasets D, Dd E D are neighboring with regards to datum d if they differ only by d (i.e., DA D {d], where A denotes symmetric difference). A
randomized algorithm A D + St takes in (training) dataset D E DD and returns (randomized) output vector w E Ω C R. Let P denote the distribution of A(D)) Differential Differrnttt privacy (DP) (Dwork 2006) works by comparing the output distributions p and p when algorithm A takes in neighboring datasets D and Dd. Intuitively. privacy is protected if any attacker cannot easily distinguish the output distributions produced by any pair of neighboring datasets. In App. [B.] we introduce different notions of DP, including (e, 0)-DP (Dwork et al. (2006) and Rényi DP (Mironov. 2017/. which differ in how the difference between P and p is measured. All these notions involve parameter 2 0 called privacy budget: smaller (close to 0) requires both distributions to be more indistinguishable. and hence corresponds to stronger privacy.
Suppose there are N data owners [N] == 21, .N} with subsets (Da)ee[N and privacy budgets = (cn) ( [ Individualized DP (IDP) works by restricting the difference in output distributions P2 and p by the unique privacy budget of the differing datum d's owner, o(d). Formally,
Definition 2.1 (IDP (Alaggan et al. 2016 A randomized algorithm A : D + S satisfies (c, 8)- individualized differential privacy O)DP))-IPP) for any datum d, any pair of neighboring datasets D, Dd E 'D such that D A Dd = {d} and every possible output set O C Ω
Pr[A(D) E O] < eoou Pr(A E O] +
A satisfies (a,, E)-iddividualized Rényi DP ((a,, IIDD) if for any datum d and any pair of such D and Dd, the Rényi divergence of order (oo(d) (see App. 1.2.2 between Pa and D" satisfics
D Daciay (P) || 11 S Eo(d)-
2

---

Published as a conference paper at ICLR 2026
Through algorithm A. owners with smaller privacy budgets en attain stronger privacy. To fulfil IDP, Boenisch et al. (2024) proposes two IDP-SGD variants, SAMPLE and SCALE (refer to App. B.2 SAMPLE samples owner n ''s data using individualized sampling rate 9ni SCALE controls the algorithm's modular sensitivity A := supp A ( [IA(D)) - with respect to each datum d, which ensures the maximum change datum can bring is restricted by its owner's privacy budget. To achieve this, SCALE scales each individual gradient gd such that its norm does not exceed its owner o(d)ss individualized clipping threshold Cold). The processed gradients are then summed up and perturbed by a Gaussian noise of O, (r-sized zero vector) mean and o I²I (r X r identity matrix) variance where a is the noise scale. The privacy guarantee of IDP-SGD is as follows:
Theorem 2.2 (Privacy of IDP-SGD (Boenisch et al. 2024)). IDP-SGD running for T iterations satisfies (ax, E)-IDPP, where En- 2T An
2.2 DATA IMBALANCE AND RELEVANCE TO THIS WORK
In this section, we introduce the data imbalance issue in MI. and its relevance to this work. Let 0 be model parameters and {(0;; d) denote the loss on datum d under O. Let L(0; D) Edep {(0; d) be the optimization objective (empirical loss). Suppose the training set can be partitioned into dis- joint groups of data E........ EN such that data within each group share similar traits and data across different groups have different traits. Thereby, each group has its own optimization objective C, [(::g.) Data imbalance refers to (t) the imbalance in sizes of different groups in the training set (hence in each sampled batch of gradient- based algorithms under uniform sampling), that is. | ....... |gvl differ significantly. For example, class imbalance (Niaz et al. 2022) exists when the training set D is partitioned based on class labels.
Data imbalance has two major negative impacts on gradient- based training algorithms such as SGD: minority initial drop (MID) (Ye et al. (021) and biased optimization objective (BOO). We illustrate them by showing a typical learning curve under data imbalance in Fig. [(a) considering 2 groups, minority group g (RED) and majority group & (BLUE D MID refers to initial drop fluctuation in model utility on minority group g1, while utility on majority group g2 improves as normal. As shown in Fig. [(b) let Gt.g, and Gr,z, denote the summed gradient of 81 and & used update model parameters from 0,-1 to 0, at iteration l. Let L, denote the angle between Gr.g, and Gr.gz- Francazi al. (2023) shows that for full-batch gradient descent to ensure the losses for both groups strictly decrease (in expectation) at iteration t, 2, has to satisfy the following condition (Cond. (T)
G G
1 + cos (2+)
0.
(1)
At earlier iterations, when 0 is far from the optimum for both groups, every individual gradient is large. Thus, the magnitude |Gr,e.] || for majority group & is much larger than Gr || since contains more gradients. The angle 2e is expected to be large as the directions of G and Gt.e, differ when the two groups have different optimization objectives. As cos (4)) and hence the left- hand side of Cond. (I) are negative, Cond. ①[ is not satisfied. Thus, when the loss for majority group &2 decreases, the loss for minority group gı may not. The loss for gı is only guaranteed to decrease when Cond. [I] is satisfied after more iterations: as the model parameters approach the optimum of 82. the gradients in ga become small in magnitude, making the left-hand side of Cond. (T) positive. BOO applies to the final optimum found as shown in Fig. I[c] when there are sufficient iterations for the model to converge. The training process will focus more reducing the expected loss E [f(0; d)) for majority group 82- This is because with more data from &2. a decrease in E [ d)] will bring a larger decrease in the objective ((0; D) = L, (0) + L2(0) than decrease in E,es, [e(0: d)). Therefore, BOO biasedly results in less optimal utility for g1.
At first glance, readers may think that MID is less harmful than BOO because MID would disappear with more iterations. However, this is not true under (I)DP which only allows limited number of iterations. It is possible that the privacy budgets are used up when MID still goes on, causing a significantly low utility for the minority groups, especially when the ML task is difficult (shown later in Sec. 4. making MID more harmful. Thus, under (I)DP we should focus on the entire learning dynamics, which refers to the model utility for each group at every stage of training.
In work, however, we do not assume data imbalance (+) (i.e., each owner can have similar number of data). Instead, we focus on how IDP induces the same impacts MID and BOO for
This can he generalized to multiple groups Francazi al. 2023
3

---

Published as a conference paper at ICLR 2026
Per genggruu utility
Cleckng Bi axlimum RED opaimum
AnD ontmmum B.
Fexture
Actual
RED oztmum
Festure 2
Fasture 2
cTE clpping radus
MBD
800
optimiter
group
optimizar
Kin. group
No. of ofiterations
Feature
Feature 1
Feeture 1 (a) SAMPLE.
Feeture 1
(a) Traits.
(b) MID.
(c) BOO.
(b) SCALE.
Figure 1: Graphical illustration of traits and causes of MID and BOO under data imbalance. MID happens at earlier stages due to imbalanced gradients, while BOO de- scribes the final stage where the trained model favors ma- jority classes. Here BLUE and RED optimum refer to the op- timizers within the group (i.e., arg ming C(O; g1 or 82)).
Figure 2: Illustraiion of IDP- induced utility imbalance with 2 data owners, BLUE (less private) and RED (more private). Model parame- ters 0 are updated in direction that reduces BLUE's 's loss but increases RED.
gradient-based algorithms, which lead to utility imbalance across different groups. In Sec. 3.1 and App. B.3] explain why this cannot be solved in the same way as existing methods tackling data imbalance. A separate branch of works on DP and biasedness of ML. models is disparate impact of DP (Bagdasaryan et al.) 2019), which studies how DP-ML models exacerbate data imbalance in the training set. Our work differs as we consider IDP and focus on the underrepresentation of data from the more private owners. The training set itself not necessarily imbalanced.
METHODOLOGY
3.1 IDP-INDUCED UTILITY IMBALANCE
We consider the setting where the training set still contains disjoint groups of data 82. &8 with respective optimization objectives (0), but the training set D can be fairly balanced and each group is of similar size. In this section, show that MID, BOO and utility imbalance can still occur when owners of data from different groups have different IDP requirements. For example, when owners of positive-case data of stigmatized diseases prefer stronger privacy in classification tasks, IDP can induce utility imbalance (see App. A.2 for more examples).
We first give the intuition why utility imbalance can still arise from both the SAMPLE and SCALE variants of IDP-SGD on balanced datasets. We demonstrate with 2 data owners BLUE (less private) and RED (more private) and plot visualizations in Fig.
SAMPLE: In SAMPLE, data owners share the same clipping threshold but have different sampling rates. App. C.I.I shows that the sampling rate for less private owner can be significantly larger than a more private one, Thus, in Fig. 2(a) there are more gradients from BLUE than RED at each iteration. Since all gradients are clipped to the same magnitude, the sum of clipped gradients from BLUE is much larger in magnitude than RED, causing MID to occur. Similarly, the training focuses more on reducing the expected loss of BLUE than RED and BOO occurs.
SCALE: In SCALF, data owners share the same sampling rate but have different clipping thresh- olds. App. [.I.I shows that the clipping threshold for a less private owner can be significantly larger than more private one. Thus, in Fig. 2(b although the numbers of gradients from both owners are similar, each clipped gradient from BLUE has a much larger magnitude than RED, The magnitude of BLUE'S ' summed gradients is thus much larger than RED and MID occurs. Such biased gradients similarly focus more on reducing the expected loss of BLUE than RED and BOO occurs.
Next, we present the following theorem to theoretically justify why data from the more private owners might not have a decreasing loss under IDP (and hence their utilities may drop):
Theorem 3.1 (Informal). Consider two data owners with subsets Dr. Dz. sampling rates qı q2 and clipping thresholds C1, Cz. At each iteration t, if the following condition (Cond. (2)
1 cos( 4)) 2a C2
Ci
>
(2)
is satisfied with 0 being problem-specific term, by choosing a sufficiently small learning rate n, the expected losses for both owners are guaranteed to decrease under standard assumptions. When Cond. (2) is not satisfied (e.g.. S 0), the loss for owner may increase (MID).
4

---

Published as a conference paper at ICLR 2026
App. C.I.2 proves and further discusses the theorem. Cond. suggests that when the two owners have different optimization objectives (4, is large and cos( ( < 0) and similar number of data (111) R [22)), the more private owner 1 who has a much smaller sampling rate 9I clipping threshold C₁ in the denominator (hence left-hand side of Cond. 2 < () could suffer from an in- creasing loss. Unlike Cond. ① (for data imbalance), Cond. 22 (for IDP-induced utility imbalance) requires problem-specific term > O due to IDP-SGD components such as individualized clip- ping which also makes it harder to satisfy. For the IDP-SGD algorithm, as the clipping thresholds are fixed, Cond. (2) may remain unsatisfied across many iterations for some owners (e.g., the more private owner or minority group). Thus, MID becomes longer and more severe.
Undesirability of IDP-induced utillity imbalance. If the ML model has significantly lower utility on some group (e.g,, due to positive-case patients having stronger IDP requirements), the model owner and subsequent users with data in such group who are impacted by the model decisions are affected. Thus, the model owner must address such IDP-induced utility imbalance during training to improve the utilities of worst-off groups during deployment (see App. A.2).
gives detailed review of existing works (possibly loosely) related to utility imbalance and their unsuitability to tackle IDP-induced utility imbalance under IDP. To summarize, we classify existing works into three categories:
Unsuitability of existing works. App. B.3
(1) Correcting data/class imbalance: This category is the most relevant as they also seek to correct utility imbalance across groups. Their core idea is to control the per-group summed gradients |[G.g...] || in Cond. I to obtain more balanced gradients to reduce MID and BOO. We note that adapting such works either (a) violate IDP requirements (e.g.. by upscaling or oversampling the
minority groups (He & Garcia 2009), (b) under-utilize the IDP budgets and give lower overall utility (e.g.. by downscaling or undersampling the majority groups (He & Gareia 2009)), (c) have their effects eliminated by clipping (e.g., rescaling the loss function (Japkowicz) (2000).
(2) Correcting De-exacerbated accuracy disparity (Bagdasaryan et al.) 2019 Tran et al. [222
Xu et al. 2021): These works do not satisfy IDP and are tailored to DP's s disparate impact from clipping and noise addition, yet IDP-induced utility imbalance arises from an orthogonal cause.
(3) Achieving group/individual fairness: These works seek to achieve similar predic- tions/behaviors across protected groups, which greatly differs from our goal to achieve similar model utilities across data owners. Thus, we do not compare with this category of works.
Thus, there is no prior work that addresses IDP-induced utility imbalance or can be easily adapted to do so. Our work seeks to fill this gap while still adhering to each owner's IDP preference.
3.2 THE INO-SGD ALGORITHM
Samples desconding order of loss 8.
The imbalanced gradient, sampling rate and clip- ping threshold (Fig. 2 & Cond. 2 in IDP-SGD cause the IDP-induced utility imbalance (MID and BOO) and must be addressed. While gradients from the more private owners cannot be upscaled due to IDP, approaches that downscale gradients from the less private owners would waste privacy budgets and lead to a lower overall utility due to the privacy-utility tradeoff (see App. C.2.1 for fur- ther discussions and for empirical evidence). How can we instead strategically discard the less important information (e.g., from less private owners) while retaining the most important in- formation? The importance of gradient informa- tion of each datum in batch B, at iteration di- rectly correlates with their individual loss values (Kawaguchi & Lu 2020 Shrivastava et al., (0166). Thus, at first glance, the solution should keep only the gradients with highest-pi μ losses or discard the gradients with smallest- μ losses. However, these simple approaches violate IDP by increasing the algorithm's modular sensitivity (see App. C.2.
Penssample clipping thresholds.
r(1) mi2)
m19i r(10)
Average importance score
Batch importance function (BIF)
(ne meesincreenngg ng
important Hillt
less Important
Per-sample gradient nor upper board
U
Figure 3: Graphical illustration of the INO- SGD algorithm. At iteration t, a batch B (e.g.. 10 data) is sampled. The gradients are computed and sorted by descending loss. INO-SGD calculates the average importance score of each gradient by integrating the im- portance function within its associated interval. By multiplying the clipped gradients to their scores, important gradients are fully kept while less important ones are partially discarded.
5

---

Published as a conference paper at ICLR 2026
To exploit the order of losse: while still preserving IDP, we devise unique algorithm, individual- ized noisy ordered SGD (INO-SGD) (Fig. [3. The key intuition behind INO-SGD is as follows:
When a new datum is added, INO-SGD first ex-
amines if its gradient ga is important based on the
When I 2
When I' <
rank of d's loss. If it is deemed important, INO-
Arranged clipping thresholds
Arrenged clipping thresholds
SGD simply clips it to its clipping threshold Cotay; otherwise, INO-SGD restricts its norm an up- per bound smaller than Cotd)- which makes room to upscale other more important gradients while the total change is capped by Co(d). thus ensur- ing modular sensitivity A S Cota) and achieving IDP (further intuition is given in Sec. 3.3.1.
Preset TIF
Figure 4: At each iteration t, BIF fe (solid line) is constructed by transforming TIF fuil (blue dashed line). The r-axes refer to the po- sition of each ordered gradient piece and the y-axes refer to its importance score.
Specifically, INO-SGD adopts a "continuized" view of each datum's gradient as collection of infinitely small gradient pieces whose loss values all equal to the datum's 's loss (see Fig. B). For each datum d, at most a total of Co of its gradi-
pieces are kept and the rest are discarded to ensure modular sensitivity A S Co(d)- Hence, the sum of gradient pieces is at most D == Ede Cotdy- Suppose all kept gradient pieces are ordered in descending order of loss, An importance function assigns an importance score between 0 (least important) and 1 (important) to each gradient piece, which indicates how much of the piece will be eventually kept. Moreover, since the summed gradient will be made noisy, INO-SGD only assigns low importance scores to a limited number of gradient pieces to maintain a reasonably high signal- to-noise ratio. This is captured by a preset tail importance function: only gradient pieces falling within the tail of length are assigned scores < 1.
Definition 3.2 (TIF). For fixed length 7 >> O, a tail importance function (TIF) fun [0, [0, 1] is a non-increasing, Riemann vieetal-inttgraale function such that for any e E [0, 7). fua(() represents the importance of gradient piece at the (c/7)-th quantile over the tail of length 7
functiiooonnno
Based on TIF, for each sampled batch B,, we de- fine its unique batch importance function (BIF) by assigning importance score 1 to the gradient pieces outside the tail (i.e., they are important) as shown in Fig. 3 In other words, the domain of BIF in- cludes all gradient pieces within [0, [o]. where I' is the sum of clipping thresholds of data in B. The transformation from TIF to BIF is shown in Fig. 4 and BIF is formally defined in App. [C2.3] By integrating the importance scores of all gradi- ent pieces from a gradient (r.(M) ranked k-th in the batch, INO-SGD calculates the average im- portance score Pk of this gradient. The norm of this gradient then restricted to (&Co(x,(k)) (an easy way as shown in Alg. i to simply scale the clipped gradient by pk). In the end, steps similar to IDP-SGD are performed: summing up the clipped gradients (weighted by importance scores), adding noise to the summed gradient, estimating the av- erage gradient" and performing gradient descent.
Algorithm 1 The INO-SGD algorithm.
Input: Fach owner n E [N]'s datasets Dn, sam- pling rates qu. clipping thresholds C.: initial model parameters 0g; noise scale o; TIF fua. Output: Trained model parameters Or.
1: B, + 0; b + Σme(N] D.!
2:
for iteration ( E [T] do
3:
B. + U, subset sampled from D,, w.p. 4n
4:
fa f- BIF computed from fua and B,
5:
B; + B, sorted by order of losses
6:
+ function mapping k [[Bl]] to index
of Bi's k-th datum in B.
7:
(cx) B.1) <- cumulative sums of first data's 's clipping thresholds in B;
8:
B.]] <- average importance scores (S fe/(c. - ck-1) dc)ke]]B[])
9:
for datum d in B, do
10:
+ Vol(O.
11:
Ee ga/ max (1, /Cooa)
12:
end for
13:
G. + 1= (1BB((k)
1B.1
A detailed pseudocode of INO-SGD is given in
Alg. | We highlight that the runtime of INO-SGD
14:
G. + (G. + N((.,, L /b
almost the same as IDP-SGD (App. C.2.4) as the time taken for backpropagation (Line I0) domi- nates the time needed for the additional sorting and integration (Line and
15:
0: + 0 GGG n
16:
end for
17:
return updated model parameters OT
"Our algorithm and analysis also work with other sorting order. See App. C.2.2 for discussion.
Using the expected batch size = Emetoy qul (n, instead of the actual B. avoids extra privacy loss.
6

---

Published as a conference paper at ICLR 2026
Choice of TIF. To flexibly control the TIF shape via few parameters, recommend using Beta distribution Beta( a, B) to model the model owner's 's belief regarding the fraction of important data. A larger a would increase the weights of the more important gradients within the tail while a larger B should reduce the weights of the less important gradients within the tail. The value of horizontal flip of Beta c.d.f. (c) == - 20 point represents its importance based on the belief. In App. C.2.5, we include a guideline on how to tune the above hyperparameters in practice. More generally, one can interpret TIF as survival function (David & Mitchel, 2012) that is specially defined on finite range. The model owner can also use other functions they deem interpretable (we give an example in App. C.2.5).
xx) =-) dx/ So ===1(1 xx)--1 dæ at
3.3 THEORETICAL ANALYSIS OF INO-SGD
3.3.1 PRIVACY GUARANTEE OF INO-SGD
Theorem 3.3 (Privacy of INO-SGD). For any TIF fuil and the corresponding BIF fr at each iteration t E [T', INO-SGD satisfies (a, ε) EIIDPP, where En2 = 2T',,, Ough/oo 2,
) it is crucial to show that for any datum d, the modular sensitivity A at iteration is bounded by d'' s clipping threshold Co(d). When d is added to batch B₁, the impact of less important data (with loss smaller than d) will not change due to the fixed-length tail of BIF. The importance score of more important data may increase (as they are "pushed" to the left by Cota)) ) However, we ensure the total change in the summed gradients and d's clipped gradient is bounded by Cotd)- Our proof makes use of the triangle inequality, the bound each gradient's 's 1,2-norm, and the telescoping sum created by our BIFs Notably, as INO-SGD consumes privacy budgets at the same rate as IDP-SGD, we are not sacrificing number of iterations for better learning dynamics. In App. D.4.5, we empirically validate the privacy guarantee of INO-SGD by showing that the LiRA membership inference attack (Carlini et al. 2022) cannot effectively distinguish which data are used for training.
To prove Thm. 3.3 App. C.3.1
Remark. The use of order of loss in each batch (c.g., sorting) does not incur extra privacy costs, as such order at iteration i. comes from the MI. model obtained at iteration t - 1, which is already protected by (I)DP in earlier rounds (i.e., similar the gradients we obtain iteration t for each sampled datum). Thus, although INO-SGD uses the gradients and the order of loss, as we bound its (modular) sensitivity at each iteration t, it strictly satisfies IDP by adaptive composition.
INO-SGM mechanism. We generalize INO-SGD to a general IDP mechanism based on the sampled Gaussian mechanism (SGM) in App. B. a. follows (proven and discussed in App. C.3.2
Theorem 3.4 (INO-SGM, informal). Let g be a function mapping an arbitrary set of data B to H' such that [[g(d]]| is upper bounded by Addd) Let w be score-based function map- ping, B to some order. Suppose B == {d: d is sampled with probability Go(d)}- Then releasing Ek= Pkg(= + NN ofI Ixxr) satisfies IRDP, where Pk set in the same way as in BIF.
3.3.2 INO-SGD ADDRESSES IDP-INDUCED UTILITY IMBALANCE
When INO-SGD strategically downweights data with lower losses. it mitigates MID for more pri- vate owners with higher losses. This can be seen by applying Thm. 3.1 with the owners with higher and lower loss as owners 1 and 2, respectively. When cos(Z.) is negative, INO-SGD effectively decreases the numerator, increases the left-hand side of Cond. 2 potentially beyond s. Now we analyze the optimization objective of INO-SGD. The cumulative clipping thresholds (ct)xE[[s..] in Line 8 of Alg. [ fall in different positions across iterations, which complicates the theoretical analysis. Thus, we analyze
(UPE) dataset D instead. In D, each owner may have different number of data based on their original sampling rates and clipping thresholds (D imbalanced). To illustrate, consider the SAMPLE algorithm with different sampling rate Sup- pose we sample multiple subsets (B, (Br) for large T according to sampling rates (gx (nn)) We construct the UPE dataset D = U B,. Rumning INO-SGD on ò with all sampling rates = 1/T is approximately equivalent to running INO-SGD on D as the sampled batches are similar.
The vanilla IDP- is effectively optimizing C(O; D). Since δ is imbalanced, IDP- suffers from MID and BOO discussed in Sec. 2.2 In contrast, our INO-SGD is less affected by MID
Analysis for SCALE is similar.
7

---

Published as a conference paper at ICLR 2026
ID INO
Owmer Dinnrr?
porgroppho toos
INO IDP recal
80-
2/6 Gaming 4N trainin
Sboas
Owner
NO
No. fioratons:
No. taraions
No. of fertten
(a) MNIST.
(b) CIFAR-10.
(c) CIFAR-
0.5 2 4 50.5 Privacy budget
Figure 5: Per-group utility corresponding to different own- ers for IDP-SGD and INO-SGD. INO-SGD significantly improves model utility (~ 10% accuracy) for the more private owners without lowering the utility for the less private owners.
(a) CIFAR-10.
tnitraiiing
training
INO IDP recall
IDP NO
tramning
3
10
10
Privacy budget
No. of horaddnns
No. narazlons
No. of forrstont
(b) CIFAR-100.
(a) MNIST.
(b) 10.
(c) CIFAR-100-FV.
Figure 6: INO-SGD's per- group recall minus IDP-SGD's. Model utilities for the more pri- vate owners show higher increase.
Figure 7: Comparison of overall model utility between IDP-SGD and INO-SGD. INO-SGD consistently im- proves/preserves the overall model performance.
and BOO as it effectively optimizes different objective L (see App. the gradient at each iteration is an unbiased estimate of derivative of fma):
C.3.3 3 for verification that
Theorem 3.5 (Objective of INO-SGD). INO-SGD specified by TIF Jua effectively minimizes
fua (0: D) = R EK w) d=)())))
where K is the number of data in Đ and w (wx) is non-increasing sequence of weighting coefficients less than 1 and πI (k) represents the index of datum with k-th largest loss in D.
As the weight sequence is non-increasing, a smaller k assigns a larger weight we to the k-th largest loss in D. Intuitively, data that are harder learn (e.g.. belonging more private owners/near the decision boundary) are assigned larger weights than easier ones (c.g.. belonging to less private owners). Hence, the more private groups have a larger weight in the objective, thus mitigating
MID and BOO. The INO-SGD objective fin can also be viewed as (see App. C.3.4 1..4foo for details)
the mixed conditional value-at at-risk (Ogryzak 2000) of loss (i.e., a weighted expectation of worse-case losses). Thus, data from more private owners with worse/larger losses are improved. an objective that better corrects for utility imbalance than average loss when minimized and is less affected by outliers with large loss than the maximal loss (Shalev-Shwartz & Wexler 2016).
an ordered weighted average (OWA) function with positive non -on-increasing weights. Weymark (1881) shows that such functions satisfy the Eigou-Dalton principle (Pigou 1912 Dalton 1920h:
if the model can reduce a larger individual loss (likely from a more private owner) by increasing another smaller individual loss (likely from less private owner), the OWA loss decreases. Thus, minimizing the OWA loss reduces imbalance across owners with different IDP requirements.
4 EXPERIMENTS
In this section, we empirically compare INO-SGD with IDP-SGD under a variety of settings. App. D. describes our setup (e.g., data owners and their privacy budgets) in detail. To summarizo" we train Papernot et al. (2021)'s convolutional neural network models for better performance under (I)P on the MNIST (LeCun et al. 1998), CIFAR-I0 or CIFAR-I00 (Krizhevsky & Hinton 2009) dataset. Each data owner holds data from (CIFAR-10, CIFAR-100) or multiple distinct classes
App- D also contains additional experiments under more datasets, models and settings.
8

---

Published as a conference paper at ICLR 2026
(MNIST) with no overlap. Additionally, for CIFAR-100-FV, we consider subset of CIFAR-100 with 2 data owners each possessing a domain of data FISH and VEHICLE respectively. In all exper- iments, owners with smaller index require stronger privacy. We focus two questions: (Balance) Does INO-SGD improve model performance on the worse-off validation groups (measured by per- group loss/recalyy corresponding the more private data owners during training and reduce the performance gap between the more private and less private groups throughout training? (Utlliy) Since balance often comes a cost, does INO-SGD achieve the above by sacrificing overall model utility (measured by validation loss/accuracyy? We answer (B) in Sec. 4.1 and (U) in Sec. 4.2 Sev-
eral other desirable properties of INO-SGD are discussed in Sec. 4.3
Our implementation can be
found at htttt::t/////
ino sgo
4.1 ADDRESSING UTILITY IMBALANCE
In Fig. 5 we plot the per-group loss/recall corresponding to each data owner across iterations for IDP-SGD and INO-SGD. For groups corresponding to the more private owners (e.g., *), INO-SGD gives consistently better performance throughout learning: the INO-SGI) perfor- mance starts to increase earlier and faster than IDP-SGD while ending with better performance when training completes. We stress that MID occurs at different time based on ML task com- plexity. In simpler tasks like MNIST, MID occurs at around 1/ /4 of the entire training stage, while in more difficult tasks like CIFAR-10 10. privacy budgets are used up before MID even ends. This aligns with our emphasis that MID is more significant under (I)DP. App. D.2 includes results for more datasets (e.g., real-world clinical datasets), models (e-g.. ResNet- 18 (H et al. 2016)) and settings (e.g., more variation in privacy budgets; less heterogeneity among owners; presence of label noises). Moreover, it also includes additional results that show how INO-SGD improves the worst-group utility and hence further validate that INO-SGD addresses utility imbalance in Fig.
To investigate how model performances under INO-SGD change from IDP-SGD for data owners with different privacy budgets, we consider the CIFAR-IO and CIFAR-I00 datasets where we have many data owners with various privacy budgets. For both datasets, we plot graphs of changes in model performance against privacy budgets to show INO-SGD's effectiveness for different privacy budgets in Fig. 6 We also plot their linear regression line in orange. Across training stages, INO- SGD significantly increases the recall validation data groups associated with more private owners (left) at the expense of a moderate decrease in the recall on less private ones (right). By the end of training. both CIFAR-10 and CIFAR- 100 datasets show statistically significant Pearson correlations between the changes in recall and privacy budgets (p-value < 0.001 in both cases). In particular, the scatter plot of CIFAR- appears noisier because the complexity of each class in CIFAR- 100 varies and has higher variance than C1.AR-10. A more private data owner with easier-to-learn data might attain similar utility as another less private data owner with difficult data.
4.2 PRESERVING OVERALL MODEL UTILITY
Although the main goal of INO-SGD is to correct utility imbalance, Fig. 7 demonstrates that INO-SGD also results in equal slightly better overall (aggregated) model utility. For all experi- ments, INO-SGD generally achieves a smaller loss/higher accuracy than IDP-SGD through- out training. This verifies our intuition in Sec. 3.2 that by dropping certain information from the sampled gradients, we are not wasting privacy budgets but rather deleting information that nega- tively affects model performance. The results also imply that vanilla IDP-SGD leads to a subop- timal privacy-utility tradeoff, while INO-SGD improves over it. In App. D3 we include more results using larger datasets and models under various settings and observe the same trend.
4.3 OTHER EMPIRICAL BENEFITS AND DISCUSSIONS
In real life, a data owner itself may own data from multiple heterogeneous groups. Such groups may have different sizes and learning complexities, which cause utility imbalance to occur within the owner itself. In App. D we demonstrate that INO-SGD addresses this too and results in better within-owner learning dynamics.
Better within-owner learning dynamics:
We include some results based on eer-group/overall loss since we analyze and solve the problem theoreti- cally through the lens of loss. The recall/accuracy results are provided for all experiments in App. D
9

---

Published as a conference paper at ICLR 2026
our ablation studies show that INO- SGD performance is better than IDP-SGD across different choices of the TIF funl including the tail length y, specific values of and B when construct fuil using Beta distribution, more generally the specific forms of TIF. This shows the practicability INO-SGD.
Robustness to hyperparameetr choice: In App. D.4.2
also choose set TIF more aggressively trade some overall utility for less utility imbalance. In App. D.4.3] we demonstrate that INO-SGD Pareto- dominates simple methods (that satisfy IDP) in such cases.
Pareto superiority: The model owner
CONCLUSION AND DISCUSSION
In this work, identify and analyze the problem of IDP-induced utility imbalance and explain why it differs from standard data imbalance. We then propose the INO-SGD algorithm and theoretically analyze its properties. Lastly, we empirically show that INO-SGD addresses the utility imbalance problem on range of different datasets. One possible limitation (discussed in App. E. is that increasing the utility of more private owners might reduce that of the less private ones. While this could be explained by the IDP-balance-utile tradeoff (see App. E.2). future work can consider exploring the Pareto frontier characterizing this tradcoff or other methods to address IDP-induced utility imbalance. Future work can also explore other use cases of our proposed unique IDP mecha- nism, INO-SGM. In App. we answer other questions a reader may have.
10

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
This paper presents work whose goal is to advance the field of machine learning (ML). In particular, identifies and addresses the problem of IDP-induced utility imbalance where the trained ML model has lower utilities on certain groups during deployment. This problem is justified and significant as the model owner and subsequent users with data in such groups who are impacted by the model decisions are negatively affected. Moreover, our work emphasizes data privacy, which protects the privacy of individuals. Therefore, our research promotes ethical Al with positive societal impact.
REPRODUCIBILITY STATEMENT
In App. D.I we describe in detail the devices, datasets, models and settings used in all our experi- ments. In each experiment subsection, also clearly explain how each experiment is done. We also provide our source code in the supplementary materials which includes the necessary information for reproducibility
ACKNOWLEDGEMEENT
This research is supported by the National Research Foundation, Singapore under its Al Singapore Programme (AISG Award No: AISG3-RP-2022-022 Xiao Tian and Jue Fan are supported by Agency for Science, Technology and Research (A*STAR) Graduate Academy. The authors would also like thank the anonymous reviewers and AC for their helpful feedback. The authors would also extend special thanks to Prof. Jonathan Scarlett for his valuable comments and suggestions at the earlier stage of this research.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 308-318, 2016.
Mohammad Alaggan, Sébastien Gambs, and Anne-Marie Kermarrec. Heterogeneous differential privacy. Journal of Privacy and Confidentiality, 7(2), 2016.
Rangachari Anand, Kishan Mehrotra, Chilukuri K Mohan, and Sanjay Ranka. An improved algorithm for neural network classification of imbalanced training sets. IEEE Transactions Neural Networks, 4(6):962-966 969, 1993.
Raman Arora, Raef Bassily, Tomás González, Cristóbal A Guzmán, Michael Menart, and Enayat Ullah. Faster rates convergence to stationary points in differentially private optimization. In Proc. ICML, pp. 1060-1092. PMLR, 2023.
Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate impact on model accuracy. In Proc. NeurIPS, volume 32, 2019.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy profiles and amplification by subsampling. Journal of Privacy and Confidentiality, 10(1), 2020a.
Borja Balle, Gilles Barthe, Marco Gaboardi, Justin Hsu, and Tetsuya Sato. Hypothesis testing interpretations and Rényi differential privacy. Proc. AISTATS, pp. 2496-2506 2020b.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. In Proc. NeurlPS, volume 32, 2019.
Bettina Berendt, Oliver Günther, and Sarah Spickermann. Privacy in e-commerce: Stated prefer- ences vs. actual behavior. Communications of the ACM, 48(4):001-106, 2005.
Rachel Kahn Best and Alina Arseniev-Kochles The stigma of diseases: Unequal burden, uneven decline. American Sociological Review, 88(5):938-96 2023.

---

Published as a conference paper at ICLR 2026
Franziska Boenisch, Christopher Mühl, Adam Dziedzic, Roy Rinberg, and Nicolas Papemot. Have it your way: Individualized privacy assignment for DP-SGD. In Proc. NeurIPS, volume 36, 2024.
Zhiqi Bu, Jialin Mao, and Shiyun Xu. Scalable and efficient training of large convolutional neural networks with differential privacy. In Proc. NeurIPS, volume 35, pp. 38305-38318, 2022.
Zhiqi Bu, Yu-Xiang Wang, Sheng Zha, and George Karypis. Automatic clipping: Differentially private deep learning made easier and stronger. In Proc. NeurlPS, volume 36, pp. 41727-41764, 2023.
D. Campos and Bernardes. Cardiotocography. UCI Machine Learning Repository, 2000. DOI: https///cbiorg//102444/////////
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Mem- bership inference attacks from first principles. In 2022 IEEE symposium on security and privacy (SP), pp. 1897-1914 14. IEEE, 2022.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E Hinton. Big self-supervised models are strong semi-supervised learners. In Proc. NeurIPS, volume 33, pp. 22243-22251 2020a.
Xiangyi Chen, Steven Z. Wu, and Mingyi Hong. Understanding gradient clipping in private SGD: A geometric perspective. In Proc. NeurIPS, volume 33, pp. 13773-13782. 2020b.
Yongqiang Chen, Kaiwen Zhou, Yatao Bian, Binghui Xie, Bingzhe Wu, Yonggang Zhang, MA KAILI, Han Yang, Peilin Zhao, Bo Han, et al. Pareto invariant risk minimization: Towards mitigating the optimization dilemma in outtof-distribution generalization. In Proc. ICLR, 2023.
Hugh Dalton. The measurement of the inequality of incomes. The economic journal, 30(119 348-361, 1920.
Richard Darlington. Another look at "cultural fairness". Journal of educational measurement, (2):71-82, 1971.
Rudrajit Das, Satyen Kale, Zheng Xu, Tong Zhang, and Sujay Sanghavi. Beyond uniform Lipschitz condition in differentially private optimization. In Proc. ICML, pp. 7066-7101. PMLR, 2023.
G Kleinbaum David and Klein Mitchel. Survival analysis: A self-learning text, 2012.
Jiahao Ding, Xinyue Zhang, Xiaohuan Li, Junyi Wang, Rong Yu, and Miao Pan. Differentially private and fair classification via calibrated functional mechanism. Proc. AAAI, volume 34(01), pp. 622-629, 2020.
Youlong Ding and Xueyang Wu. Revisiting hyperparameter tuning with differential privacy, 2025. URL
http//bbb22211. 01852
Natalie Dullerud, Karsten Roth, Kimia Hamidieh, Nicolas Papernot, and Marzych Ghassemi. Is fairness only metric deep? evaluating and addressing subgroup gaps deep metric learning. In Proc. ICLR, 2022.
Cynthia Dwork. Differential privacy. In International Colloquium on Automata, Languages, and Programming, pp. 1-12, 2006.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in CryptologyEEUROCHE 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 486-503, Springer, 2006.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Con- ference, pp. 214-226, 2012.
Maria S Esipova, Atiyeh Ashari Ghomi, Yaqiao Luo, and Jesse Cresswell. Disparate impact in differential privacy from gradient misalignment. In Proc. ICIRR 2023.
12

---

Published as a conference paper at ICLR 2026
Tom Farrand, Fatemehsadat Mireshghallah, Sahib Singh, and Andrew Trask. Neither private fair: Impact of data imbalance on utility and fairness in differential privacy. In Proceedings of the 2020 Workshop on Frivacy-Preserving Machine Learning in Practice, pp. 15-19, 2020.
Emanuele Francazi, Marco Baity-Jesi, and Aurelien Lucchi. theoretical analysis of the learning dynamics under class imbalance. In Proc. ICML, pp. 10285-10322, PMLR, 2023.
Prakhar Ganesh, Hongyan Chang, Martin Strobel, and Reza Shokri. On the impact of machine larning randomness on group fairness. In Proceedings of the 2023 ACM Conference on Fairness, Accountabilityy and Transparency, pp. 1789-1800, 2023.
Georgi Ganev. DP-SGD PATE: Which has less disparate impact on GANs?, 2021. URL https: wtw.v.org/abs////. 211161611
Georgi Ganev, Bristena Oprisanu, and Emiliano De Cristofaro. Robin Hood and Matthew effects: Differential privacy has disparate impact on synthetic data. In Proc. ICML, pp. 6944-6955 PMLR, 2022.
Joel Goh and Melvyn Sim. Distributionally robust optimization and its tractable approximations. Operations research, 58(4-part-1::902-917 2010.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Proc. NeurlPS, volume 29, 2016.
Haibo He and Edwardo A Garcia, Learning from imbalanced data. IEEE Transactions on Knowledge and Data Engineering, 2169):1233-1284 2009.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. Proc. CVPR, pp. 770-778, 2016.
Matthew Jagielski, Michael Kearns, Jieming Mao, Alina Oprea, Aaron Roth, Saced Sharifi- Malvajerdi, and Jonathan Ullman. Differentially private fair learning. In Proc. ICML., pp. 3000- 3008. PMLR, 2019.
Nathalic Japkowicz. The class imbalance problem: Significance and strategies. In Proceedings of the International Conference on Artificial Intelligence, volume 56, pp. 111-117, 2000.
Carlos Jensen, Colin Potts, and Christian Jensen. Privacy practices of internet users: Self-reports versus observed behavior. International Journal Human- Computer Studies, 63(1-2):203-227, 2005.
Kenji Kawaguchi and Haihao Lu. Ordered SGD: A new stochastic optimization framework for empirical risk minimization. In Proc. AISTATS, pp. 669-679. PMLR, 2020.
Daniel S Kermany, Michael Goldbaum, Wenjia Cai, Carolina CS Valentim, Huiying Liang, Sally Baxter, Alex McKeown, Ge Yang, Xiaokang Wu, Fangbing Yan, et al. Identifying medical diag- noses and treatable diseases by image-based deep learning. Cell, 172(5): 122-1131, 2018.
Moritz Knolle, Robert Dorfman, Alexander Ziller, Daniel Rueckert, and Georgios Kaissis. Bias- aware minimisation: Understanding and mitigating estimator bias in private SGD, 2023. URL
12018
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Uni- versity of Toronto, 2009.
Bogdan Kulynych, Yao- Yuan Yang, Yaodong Yu, Jaroslaw Blasiok, and Preetum Nakkiran. What you see is what you get: Principled deep learning via distributional generalization. In Proc. NeurIPS, volume 35, pp. 2168-2183, 2022.
Samantha Lai and Brooke Tanner. Examining the intersection of data privacy and civil rights. Brook- ings, 2022.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEFF, 86(11) (6(11):2277-2324 1998.
13

---

Published as a conference paper at ICLR 2026
Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie. Convergence of Adam under relaxed assump- tions. In Proc. NeurIPS, volume 36, pp. 52166 -21166,,,,,,- 2023.
Tsung-V Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. In Proc. ICCV, pp. 2980-2998 2017.
Zinan Lin, Sivakanth Gopi, Janardhan Kulkarni, Harsha Nori, and Sergey Yekhanin, Differentially
private synthetic data via foundation model APIs I: Images. arXiv preprint arXiv:2305. 2023.
Andrew Lowy, Devansh Gupta, and Meisam Razaviyayn. Stochastic differentially private and fair learning. In Workshop on Algorithmic Fairness through the Lens of Causality and Privacy, pp. 86-119. PMLR, 2023.
Ali Makhdoumi and Nadia Fawaz. Privacy-utility tradeoff under statistical uncertainty. In 5 Anmual Allerton Conference on Communication, Control, and Computing, pp. 1627-1634. IEEE, 2013.
llya Mironov. Rényi differential privacy. In IEEE 30th Computer Security Foundations Symposium, pp. 263-2752222 205,275,222 2017.
Ilya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaussian mechanism, 2019.
Meenatchi Sundaram Muthu Selva Annamalai and Emiliano De Cristofaro. Nearly tight black-box auditing of differentially private machine learning. In Proc. NeurlPS, volume 37, pp. 131482- 131502, 2024.
Nazim Uddin Niaz, KM Nadim Shahariar, and Muhammed JA Patwary. Class imbalance problems in machine learning: A review methods and future challenges. In Proceedings of the 2nd International Conference Computing Advancements, pp. 485-490, 2022.
Wlodzimierz Ogryczak. Multiple criteria linear programming model for portfolio selection. Annals of Operations Research, 97(1):143-162, 2000.
Andreas Panagopoulos. Timo Minssen, Katerina Sideri, Helen Yu, and Marcelo Corrales Com- pagnucci. Incentivizing the sharing of healthcare data in the Al era. Computer Law & Security Review, 45:105670, 2022. ISSN 0267-3649. doi: https://doi.org//100111//
2022. 105670. URL btttps://www.set wttp///wciieeeiireetttttt com http///et...cosseeeeee//rriaaaaa 5026736492200018
Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Úlfar Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. In Proc. AAAI, volume 35, pp. 9312-9321, 2021.
Stuart L Pardau. The California Consumer Privacy Act: Towards a European-style privacy regime in the United States. J. Tech. & Pol'y, ,, 23:68, 2018.
Arthur Cecil Pigou. Wealth and welfare. Macmillan and Company, limited, 1912.
Rui Qiao, Zhaoxuan Wu, Jingtan Wang, Pang Wei Koh, and Bryan Kian Hsiang Low. Group-robust sample reweighting for subpopulation shifts via influence functions. In Proc. ICLR, 2025.
General Data Protection Regulation. General Data Protection Regulation (GDPR). Intersoft Con- sulting, Accessed in October, 24(1), 2018.
Sean Robertson. NLP from scratch: Classifying names with character-level RNN. PyTorch Tuto- rials, 1(0), 2017.
Haichao Sha, Yang Cao, Yong Liu, Yuncheng Wu, Ruixuan Liu, and Hong Chen. Clip body and tail separately: High probability guarantees for DPSGD with heavy tails, 2024. URL https:
1
Shai Shalev-Shwartz and Yonatan Wexler. Minimizing the maximal loss: How and why. In Proc. ICMI., pp. 793-801. PMLR, 2016.
14

---

Published as a conference paper at ICLR 2026
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference at- tacks against machine learning models. IEEE Symposium on Security and Privacy, pp. 3-18. IEEE, 2017.
Abhinav Shrivastava, Abhinav Gupta, and Ross Girshick. Training region-based object detectors with online hard example mining. In Proc. CVPR, pp. 761-769, 2016.
Rachael Hwee Ling Sim, Yehong Zhang, Mun Choon Chan, and Bryan Kian Hsiang Low. Collab- orative machine learning with incentive-aware model rewards. In Proc. ICML, pp. 8927-8936. PMLR, 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Proc. ICLR, 2014.
Getoar Sopa, Juraj Marusic, Marco Avella-Medina, and John P. Cunningham. Scalable differentially private bayesian optimization, 2025. URL /ttpt::/ /ttp:/p///aaii...r////////////// http://.rggabb/////00 06044
Mingxing Tan and Quoc Le. EfficientNet: Rethinking model scaling for convolutional neural net- works. In Proc. ICML, pp. 6105-6114. PMLR, 2019.
Xiao Tian, Rachael Hwee Ling Sim, Jue Fan, and Bryan Kian Hsiang Low. DeRDaVa: Deletion- robust data valuation for machine learning. In Proc. AAAI, volume 38, pp. 15373-15381, 2024.
Florian Tramèr and Dan Boneh. Differentially private learning needs better features (or much more data). Proc. ICLR, 2021.
Cuong Tran, My Dinh, and Ferdinando Fiorctto. Differentially private empirical risk minimization under the faimess lens. In Proc. NeurlPS, volume 34, pp. 27555-27565 2021a.
Cuong Tran, Ferdinando Fioretto, and Pascal Van Hentenryck. Differentially private and fair deep learning: A Lagrangian dual approach. In Proc. AAAI, volume 35, pp. 9932-9939, 2021b.
Khang Tran, Ferdinando Fioretto, Issa Khalil, My T. Thai, and Linh Thi Xuan Phan NhatHai Phan. FairDP: Certified fairness with differential privacy, 2025. URL htt.httss///rxiv.orrg//////
2305.16443
Archit Uniyal, Rakshit Naidu, Sasikanth Kotti, Sahib Singh, Patrik Joslin Kenfack, Fatemehsadat Mireshghallah, and Andrew Trask. DP-SGD vs PATE: Which has less disparate impact on model accuracy?, 2022. https:::: httpt:/ss:///axxttt httt:p::///xxxvv.orrgg abss 2200 12576
Tim Van Erven and Peter Harremos. Rényi divergence and Kullback-Leibler divergence. IEEE Transactions Information Theory, 60(7))3797-3880, 2014.
Hua Wang, Sheng Gao, Huanyu Zhang, Weijie J. Su, and Milan Shen. DP-HyPO: An adaptive private hyperparameter optimization framework, 2023. URL
abs/
5306.057333
Jianxin Wei, Ergute Bao, Xiaokui Xiao, and Yin Yang. DPIS: An enhanced mechanism for differen- tially private sgd with importance sampling. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pp. 2885-2899, 2022.
John A Weymark. Generalized Gini inequality indices. Mathematical Social Sciences, 1(4):409~ 430, 1981.
Tianyu Xia, Shuheng Shen, Su Yao, Xinyi Fu, Ke Xu, Xiaolong Xu, and Xing Fu. Differentially private learning with per-sample adaptive clipping. In Proc. AAAI, volume 37(9), 10444- 10452, 2023.
Ruicheng Xian, Qiaobo Li, Gautam Kamath, and Han Zhao. Differentially private post-processing for fair regression. In Proc. ICML, pp. 54212-54235. PMIR, 2024.
Depeng Xu, Shuhan Yuan, and Xintao Wu. Achieving differential privacy and faimesss in logistic regression. In Companion Proceedings of The 2019 World Wide Web Conference, pp. 594-599, 2019.
15

---

Published as a conference paper at ICLR 2026
Depeng Xu, Wei Du, and Xintao Wu. Removing disparate impact model accuracy in differentially private stochastic gradient descent. In Proc. KDD, pp. 1924-1932, 2021.
Han-Jia Ye, De-Chuan Zhan, and Wei-Lun Chao. Procrustean training for imbalanced deep learning. In Proc. ICCV, pp. 92-102, 2021.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. In Proc. NeurIPS, volume 33, pp- 15511-15521, 2020.
Jingzhao Zhang, Tianxing Hc, Suvrit Sra, and Ali Jadbabaic. Why gradient clipping accelerates training: A theoretical justification for adaptivity. Proc. ICLR, 2019.
Tao Zhang, Tianqing Zhu, Kun Gao, Wanlei Zhou, and Yu Philip. Balancing learning model pri- vacy, fairness, and accuracy with early stopping criteria. IEEE Transactions on Neural Networks and Learning Systems, 34(9):5557-556, 2021.
Yuang Zhang, Liping Wang, Yihong Huang, Yuanxing Zheng, Fan Zhang, and Xuemin Lin. Grad- Stop: Exploring training dynamics in unsupervised outlier detection through gradient, 2025. URL
/ / org/ als / 2412 2. 08501
Han Zhao and Geoffrey Gordon. Inherent tradeoffs in learning fair representations. Journal of Machine Learning Research, 23(57):1-26, 2022.
16

---

Published as a conference paper at ICLR 2026
A
OVERVIEW
A.
SUMMARY OF NOTATIONS
Below gives summary all notations used in this paper.
Constants and Variables
4
Angle between group summed gradients iteration
0 0,
Empty set
r-length vector of O's
A
Algorithm; ML training algorithm
Rényi order
Vector of per-owner Rényi orders
ap
Rényi order computed for data owner n Beta distribution parameter
Sampled batch from
B
Sampled batch iteration Sampled batch at iteration from data owner n sorted B, based on descending order of individual losses Arbitrary set of data Expected batch size Beta distribution parameter Clipping threshold
Bt.
B
b
B
C
Point over the tail of length 7/
Vector of accumulated clipping threshold
Ck
Accumulated clipping threshold until (and including) the k-th ranked datum
Cn
Clipping threshold data owner n
D
Dataset
UPE dataset associated with D
Dd
Neighboring dataset of D with regards to datum d
Da
Dataset of data owner n.
D
UPE dataset of data owner
D
Set of datasets A random event
d
Datum within dataset
8
Tolerance term in (e, 8)-DP
e
Privacy budget
data owner; privacy level a mechanism
Vector of per-owner privacy budgets
6n
Privacy budget of data owner n;;
Rényi Privacy budget of data
Vector of Rényi privacy budgets of data owners
Rényi Privacy budget of data owner
Learning rate
Fg
Group fairness metric Filtration up to the end of iteration t Gradient used for descent iteration Summed gradient of group g, at iteration / Sum of (weighted) clipped gradient at iteration t Perturbed gradient at iteration t Group n within a dataset
Fi
G
Gr
Ge
G
gn
ga
Individual gradient with regards datum d Individual gradient with regards to datum at iteration Clipped individual gradient with regards datum d Clipped individual gradient with regards to datum d at iteration t
gr.d
ga
grd
T,
Sum of clipping thresholds of sampled data iteration Length of tail
Lxx
T. X identity matrix
17

---

Published as a conference paper at ICLR 2026
K
Number of data in D Index of datum in D Number used in fast integration in INO-SGD Lipschitz constant
&
L
Quantities measured in 2D Lebesgue measure
L
Smoothness constant
Level of CVaR
N
Number of data owners Index of data owner
O
Subset of Set of algorithm outputs Vector algorithm outputs
Ω
Uncertainty set
Possible weights within uncertainty set Possible weight assigned k-th ranked datum Scaling factor to scale gradient of datum d to its clipped gradient at iteration t Expected scaling factor owner at iteration
Ps
Lrd
onn
(2)
Expected squared scaling factor of owner at iteration
Pnn
d
Problem-specific positive term used Cond. 12 Sampling rate
g
Vector of individualized sampling rates Uniform sampling rate in UPE dataset Sampling rate of data owner Number of parameters in an ML model Importance score
On
Importance score of datum
Pk
Importance score of the k-th ranked data Scoring function in INO-SGM
Noise scale
mroblem-speciff positive term used in Cond. 5
Sn
Problem-specifie positive term used in Eq. 13 and 14
T
Total number of iterations
L
Index of iteration
Total number of sampling iterations to contruct 5
Index of sampling iteration to construct /
Set of possible model parameters Vector of model parameters
0"
Optimal model parameter for ERM Model parameters after iteration t Possible value of us Possible value of
0,
u
w
Vector of weights in INO-SGD objective
We
Weight associated with k-th ranked datum in INO-SGD objective
X
Set of possible values of x, Unlabelled datum
A sensitive attribute Uniform bound for stochastic gradient from owner n Label of data
En
1
Model's predicted label of data Gaussian noise added at iteration /
Ze
Functions and Operators
Symmetric difference between two sets An arbitrary function An arbitrary non-negative function term
18

---

Published as a conference paper at ICLR 2026
Cardinality of set
L?-norm of
F
Set (1.2......) Sensitivity of
Modular sensitivity of with regards datum
BH
Expectation of
(.n
Tail importance function
f((-)
Batch importance function at iteration t
Owner of : group membership function
p)(()
Output distribution returned by algorithm A when taking in dataset D
Pr[j]
Probability of
s.rt(.)
Sorted version of in descending order
Beta(
Beta distribution
Rényi divergence of order between and c Distance between and o over the domain of x Distance between and over the domain y Global loss function with parameter and dataset
(x(.0)
((:0)
C(;0)
Global loss function in the UPE dataset
(:0)
INO-SGD objective with parameter and dataset o Owner o's loss function with parameter
2o())
((50)
Individual loss function with parameter and datum Individual Ioss function with parameter and the k-th datum Larger value between and o Gaussian distribution of mean and variance
(+))
maxf.o)
(()
V
Derivative of with regards to Index of datum whose loss ranked in the whole dataset Index of datum whose loss is ranked in the batch at iteration t Function that maps set of data to their order
T()
T
(()
A.2 USE CASES
In this section, we explain why this work important in real life. is common for different groups or data owners to have different privacy preferences. Data owners with certain attribute values/class labels (e.g., stigmatized diseases, race) could be more disadvantaged than others when data leakage occurs out of privacy attack, as this may bring them discrimination or denial of services (Best & Keseniev-Kochlee 2023 Lai Tanner 2022). Since DP is highly relevant in such fields to protect their privacy, our work's use cases are broad. For example, hospital located at the center of a disease outbreak will have much more positive cases and require stronger privacy than a hospital located far away to protect their patients. Similarly, students from marginalized backgrounds may prefer stronger privacy; social media users discussing more sensitive topics may desire stronger privacy their profiles; individuals with poor credit histories may want stronger privacy avoid unnecessary loss of opportunities.
Should model utility more private data owners' data be lower? Our answer is no. the trained ML model has lower utility on some group of data within the data space, the model owner and subsequent
with data from such group will be negatively affected. For example, consider the case where a medical institute trains disease model for stigmatized disease. Just because positive-case data owners have stronger privacy does not mean the trained model should perform badly on data from positive-case groups during deployment, since subsequent positive-case patients who are affected by the model's ' decisions will bear the consequences.
This work shows in Sec. 3.1 that IDP could induce severe utility imbalance between the more private data owners and the less private data owners. Because the reasons above, the goal this work is to correct -nduuede utility imbalance, that is, to improve model utility on the worst-off groups corresponding to the more private data owners and reduce the gap between model utilities on groups corresponding to the more private data owners and the less private data owners. Our solution INO- SGD successfully achieves this without sacrificing overall model utility. As the first such work, our work makes significant contribution. Note that improving the utilities of worst-off groups (during
19

---

Published as a conference paper at ICLR 2026
deployment) is also an important goal in fairness (Dullerud al. 2022 Zhao & Gordon 2022) and distributional robustness (Chen et al. 2023 Qiao et al. 2025).
IDP-SGD assumes homogeneous data owners. A naive approach to address different privacy requirements is to always maintain the strongest DP level. However, this would inevitably lead to loss in overall model utility (see App. F Q1 for detailed explanation). The original IDP-SGD work (Boenisch et al. 2024) assumes that each data owner holds similar data. The different privacy preferences come from their natural personalities, where around 34% of people prefer high privacy, 43% prefer medium privacy and 23% prefer low privacy (Alaggan et al., 2016). This setting is applicable ML tasks where training data are in general not very sensitive such as emoji suggestion. In contrast, our work realizes that the nature of data could lead to different privacy preferences too and identifies that this may lead a severe utility imbalance problem.
Individualized privacy progression. We also foresee another potential use case of our work and recognize it as individnalized privacy progression (IPP). IPP captures the change of privacy pref- erences over time. Due to the privacy-utility tradeoff (Makhdoumi & Fawaz 2013), owners who specify low privacy budgets (resulting in low-utility models) may regret their previous choices and wish to increase their privacy budgets. Conversely, owners who set high privacy budgets may be- come increasingly aware of or averse to the risks privacy leakage and desire to lower their privacy budgets. When data owners wish to increase their privacy budgets, they may do to varying de- grees based on the sensitivity (assuming that the model has not been attacked yet), the ML model needs to be rolled back to an carlier timestamp in the training process. This reinforces the importance of maintaining a good learning dynamics throughout the model training process.
their data. If data owners wish to decrease their privacy budgets
B ADDITIONAL BACKGROUND AND RELATED WORKS
B.1 DIFFERENTIAL PRIVACY
In this section, we provide detailed background on differential privacy (DP) for unfamiliar readers.
Let DD be the set of datasets. Consider a dataset D E DD and an algorithm A D - Ω that takes in the dataset D and produces some useful output w A(D) E S.. the context of (parametric) machine learning (ML), algorithm A could refer to the training algorithm that outputs the vector of trained model parameters. If algorithm A is deterministic and always outputs the same w given fixed input dataset D, then attackers can reconstruct the input dataset D by inverting algorithm A (e.g., through membership inference attack (Shokri et al. (017) in ML). which threatens the privacy of data owners. Therefore, when dataset D contains sensitive data, algorithm A is usually algo- rithmically designed to randomized instead and DP is employed to assess the privacy-preserving capability of A.
Randomized algorithm A
Distribution
Input dataset
of output
Neighboring
Closeness
Figure 8: Illustration of DP. When randomized algorithm A takes in pair of neighboring datasets, we say A satisfies DP its output distributions are always close to each other. The close- ness of distributions is defined differently in different variants of DP.
Differential privacy (Dwork) 2006) (DP) is the most commonly adopted notion of privacy nowadays. DP works by comparing the output distributions pd and p when algorithm AA takes in a pair of neighboring datasets D and d (i.e., D A D {d}). If attackers can hardly distinguish all such pairs of D and Ddd then remains private; if attackers can hardly distinguish the output distributions produced by any pair of neighboring datasets, then all data remain private.
20

---

Published as a conference paper at ICLR 2026
DP works by comparing the distributions of randomized output when algorithm A takes in pair of neighboring datasets and D that differ by only one datum Intuitively, if attackers cannot distinguish the distributions of A(D) and A(D*), then they cannot reveal datum d since they are not certain whether is even in the dataset. If all such pairs neighboring datasets result in indistinguishable output distributions through A, then all data are private. Therefore, the formal definition of (pure) DP follows:
Definition B.1 (c-DP (Dwork) 2006)). randomized algorithm A: D + Ω satisfies c-differential
privacy (e-DP) if for any datum any pair of neighboring datasets D, D D such that D A D {d}, and every possible output set O C S2, we have
e Pr[A(D")) O), Pr[A(D) E se
(3)
where e 2 0 is called the privacy budget of data owners or privacy level of algorithm A, which measures how private the algorithm A is.
When privacy budget = O, the algorithm A is absolutely private. In other words, all pairs of neighboring datasets behave exactly the same through A. Iteratively, they all behave the same as the empty set (.. Thus, algorithm A is useless in this case. An example of such an algorithm would be AD E D [A(D) = (0, 1)], which outputs random Gaussian noise regardless of the input dataset. When privacy budget becomes larger, the distributions of A(D) and A(D*) become less close and more distinguishable. The algorithm A becomes less private. On the other hand, this also means that the algorithm output 0 is impacted by the data to larger extent, and hence the output should be more useful or informative. This is commonly known as the privacy- cutiity tradeoff (Makhdoumi & Fawaz 2013).
Nevertheless, c-DP is often considered to be too strict in practice. This is because its definition requires bounded logarithmic difference log PttA( Ee for any O S Ω although for some Pr(A(D)EO) particular output w E Ω, it is almost impossible for algorithm A to output such w (i.e., Pr(A(D) = w) and Pr(A(D4) w] 0). To make sure the bound holds for such edge cases, great amount of extra perturbation and randomization needs to be added to algorithm A, which damages its utility. This phenomenon is more severe complex mechanisms such as model training ML. To mitigate this issue, two common relaxations of e-DP are introduced below.
B.1.1 (IFFEEIIFEEEENTTA. PRIVACY
The most straightforward relaxation of c-DP is to add tolerance term ö to the right-hand side of Eq. 3 Such relaxation is called (c, 5)DP, which aims to solve the edge case issue mentioned in the previous section by allowing very small probability å E (0, 1) that the logarithmic difference bound e is violated, i.e.,
Definition B.2 ((e, 6)-DP (Dwork et al. 2006)). A randomized algorithm A D + Ω satisfies (c, 8) diffeffernttaal privacy ((P) if for any datum d, any pair of neighboring datasets D, Dd E 'D such that D Dd = {d]. and every possible output set O C S2 we have
Pr(A(D) 0J e Pr(A(DD) E 0O}+
where 0 is the privacy budget set by data owners or privacy level of algorithm A (a more private data owner sets a smaller for stronger privacy), and 8 E [0, 1) is a tolerance term which allows for a very small probability that the privacy level e violated.
While (c, 8DP indeed gives better utility in most applications, its major drawback is that it is hard to compute the resulting (c. -DP level when two or more (c, dDP mechanisms are sequentially composed together" (i.e, (D)))) In fact, because of the existence of tolerance intractable to obtain an exact (c, bound for sequentially composed mechanisms, since both mul- tiplication and addition operations appear in the definition. Therefore, for complex DP mechanisms such as ML model training, it is challenging to do privacy accounting, that is, to maintain tight and accurate bound on the privacy consumption as training progresses. Existing techniques such as mo- ments accountant (Abadi et al. 2016) provide relatively good accounting and maintain relatively good model utility.
is now
In comparison, for pure e-DP, can simply sum up the exponents for composed DP mechanisms.
21

---

Published as a conference paper at ICLR 2026
B.1.2 RÉNYI DIFFERENTIAL PRIVACY
To make privacy accounting easier and more accurate, alternative variants of DP are proposed. One of such variants is based on the Rényi divergence of order a (Van Erven & Harremos/ 2014), Day between the output distributions P and P'A corresponding to neighboring datasets D and D Specifically.
Definition B.3 (Rényi Divergence Van Erven & Harremos 2014)), The Rényi divergence of order between distributions pd and pd Da Da(p& (o22plp2 1p2") ) is defined as follows:
J Pr(A(D") w] (P([((D) W (Pr[A(D4) = -w
Do Pa
dw.
(4)
In particular, gence. A smaller Rényi divergence between distributions P and y means that the two distribu- tions closer, thus indicating stronger privacy. Formally,
1, the above Rényi divergence approaches the Kullback-Leible (KL) diver-
Definition B.4 ((a, R)-RDP (Mironov 2017)). A randomized algorithm A D - St satisfies (a, E)- Rényi differential privacy ((a, R)-RDP) if for every pair of neighboring datasets D, Dd E D, we have
Da (Pă
P
where ? 2 is the Rényi privacy level of algorithm A.
The RDP bound of sequentially composed RDP mechanisms simple and tight:
Theorem B.5 (Sequential Composition of RDP (Mironov (017)). Suppose mechanism A₁ satisfies (a,, R-DP and A2 satisfies (ox, RRD- then their sequential composition (2( that releases both oulputs satisfies (ar, + RDD-
Moreover, RDP algorithms satisfy (e, 8)- via the following theorem:
Theorem B.6 (Relation to (c. 6)-DP (Balle et al. 2020b)). A randomized algorithm A that satisfies (a, Rényi DP also satisfies (ē + log((a 1)/a) (log 5 log (oga)/(a 1),8)-Dr DP for any 8 1).
For data owners, is clearly easier for them to specify their privacy preferences using the (c, 8)-DP notion because both and 5 have straightforward meaning. Specifically, is usually to be larger than 0.1 and lower than 10, while ö is set to a small number (c.g., 10 Mcanwhile, they may find challenging to determine the appropriate value for Rényi order and corresponding Rényi privacy budget č. In constrast, model owners need to trace the privacy consumption when they train their ML. models and thus (a, R)-DDP more suitable for them. Since Thm. B.6 allows for the conversion between both notions, it becomes common choice for data owners to use (e, 5)DP to specify privacy preferences and for model owners use (ar, RDP to perform privacy accounting (known RDP accountant).
B.1 SAMPLED GAUSSIAN MECHANISM
The sampled Gaussian mechanism (SGM) is one of the most common DP mechanisms which con- verts any non non-prie private algorithm to one that satisfies DP. It has two components, the noise addition mechanism and the sampling mechanism.
Noise addition mechanism. The noise addition mechanism the most common technique to achieve DP. It works by perturbing the non-private algorithm output w with certain noise of magni- tude comparable to the difference in algorithm outputs given by neighboring datasets, such that the perturbed outputs become indistinguishable attackers.
A quantity called sensitivity is used to represent the maximum difference in algorithm outputs given by neighboring datasets, which is defined formally below (we focus on the 1,2 case which is the most practical);
Definition B.7 (Sensitivity). The (L2 Jsessiiiiyy of an (non- (non-private) algorithm A defined as the 7.2-norm of maximum change in mechanism outputs when takes in pair of neighboring datasets,
22

---

Published as a conference paper at ICLR 2026
that is,
A
sup de D DAD (d)
[[(D)) A(D*)),
where D, Dd are neighboring datasets.
Clipping (Abadi al. 2016 commonly used control the se-seniitivity of an algorithm A. For a vector w and a predetermined clipping threshold C > 0, the clipped vector is
max (1, |w]l/C]
where we scale down w if its Lo-norm exceeds C and do nothing otherwise. For example, given C' = 5, the vector (5) will be clipped to (1) Another vector (2) will not be clipped since its norm is already less than C = 5. By returning the clipped output for mechanism A, we can limit its sensitivity at most C when we add datum or remove a datum from the input dataset D.
After computing or controlling the sensitivity of algorithm A, model owners can add noise of corre- sponding scale achieve different level of privacy. The most practical way add Gaussian noise and the privacy guarantee is given below:
Theorem B.8 (Gaussian Mechanism (Dwork et al. 2006)). For any algorithm A with output di- mensionality r, privacy budget and tolerance (0,1), 1), adding a Gaussian noise of 0, (r-length vector of O's) mean and o² Lyxr (r X identity matrix) variance to the output achieves (e, 6)-DP, where
AAy log (.225/0)
Sampling mechanism. Privacy can be amplificd by sampling (aalle al. 2020a). Suppose in- stead that we sample a subset B C D by independently sampling each datum in 12 with probability q (i.e., Poisson sampling). We call q the sampling rate. Privacy is amplified through Poisson sam- pling because for any neighboring datasets, the datum by which they differ has probability 1 - g of not being sampled, in which case the mechanism outputs on neighboring datasets will be exactly the same.
Combining the Gaussian mechanism and sampling mechanism together, we have the sampled Gaus- sian mechanism (SGM), which refers to the process where we first sample subset B C D using Poisson sampling, pass into algorithm A, clip the output to clipping threshold C and perturb the output with Gaussian noise. SGM achieves the following privacy guarantee:
Theorem B.9 (Privacy of SGM (Mironov et al., 2019)). An SGM with sampling rate q, sensitivity A and noise scale a satisfies (a, RDDP where
200 A ビ=
r²
B.1.4 DIFFERENTIALLY PRIVATE STOCHASTIC GRADIENT DESCENT
Based on SGM, differentially private stochastic gradient descent (DP-SGD) (Abadi et al. 2016 is a widely used DP algorithm to train ML models (DP-ML). Consider the empirical risk minimization (ERM) formulation of MI.. Let L(0; D) == Ede D {(0; d) be the empirical loss function we wish to minimize, where É(0 d) is the individual loss associated with datum d. To approach the minimizer 0" SGD works by iteratively sampling a batch of data and use their averaged or summed gradi- ents to update the model parameter. In contrast, DP-SGD works by iteratively applying SGM to compute the noisy batch gradients G, f- E. ga ON I,xr) used to update model parameters 0 at each iteration f. Here, B, is the Poisson sampled batch using sampling rate b/ [] to achieve the expected batch size b. To control the sensitivity of the batch gradient, each indi- vidual gradient gd <- Vol(O,-1, d) is "clipped" to predetermined clipping threshold C' using ga < ga/ max //') such that the sensitivity their average is at most C. The privacy of DP-SGD is thus guaranteed by adaptive composition of Thm. B.9 as follows.
23

---

Published as a conference paper at ICLR 2026
Theorem B.10 (Privacy of DP-SGD (Mironov al. 2019)). The DP-SGD algorithm running for iterations with sampling rate q, clipping threshold C' and noise scale a satisfies (a, (a,E)-RDP, where
21 2T'q"C"
0²
The detailed algorithm given Alg. below:
Algorithm The DP-SGD algorithm.
Input: Dataset D; initial model parameters Op: sampling rates qi clipping threshold C; noise
scale a.
Output: Trained model parameters Or.
1: 4-g0 -g|DD
2: for iteration & [T' do
3: Be < subset sampled from D with rate
4: for datum d B; do
5: ga - VoL(O,-1,1
6:
8 Ba/ max Taall//
7:
end for
8:
G. - EdEB, gd
9:
G : GG + NO, I,x))
10: 0, t- 0:-1- - r/G:
11: end for
12: return updated model parameters Or
B.2 INDIVIDUALIZEI DIFFERENTIAL PRIVACY
Readers may refer to the main paper for detailed backgrounds on IDP and the IDP-SGD algorithm. The pseudocode of IDP-SGD given in Alg. 3 below:
Algorithm 3 The IDP-SGD algorithm.
Input: Datasets of all data owners D1, D2. Dv: initial model parameters 0y; per-owner sampling rates şi, Q2, ... (Nv per-owner clipping thresholds C₁, "....., CN; noise scale a. Output: Trained model parameters Or.
1: <- - Zn [D,
2: for iteration f E [T] do
[N] do 4: Br. + subset sampled from D2 with rate
3: for owner
5: end for
6: Be + -U B
7:
for datum dl B, do
8:
ga Vo 0,
9:
gd - Ba/ max |gall/Co(d))
10:
end for
G Σ Bd
11:
G k= (k)
12:
G.
N(0,, I
13:
0, + 0. G
end for
15: return updated model parameters 0r
For ease of reference we also include the pseudocodes for the SAMPLE and SCALE variants of IDP-SGD respectively below. The SAMPLE algorithm assigns different sampling rate but the same clipping threshold for different data owners:
Algorithm The SAMPLE algorithm.
Input:
Datasets of all data owners D,. Dz.... DN; initial model parameters On; per-owner
sampling rates y Q2.** ......gvv .vv: clipping threshold C:; noise scale
24

---

Published as a conference paper at ICLR 2026
Output: Trained model parameters 07-
1: En (n.11) [n
2: for iteration & E [2'] do
3: for owner [MV do
4: Bi.n < subset sampled from D, with rate
5: end for
6: B, 5 -U- Bt..
7:
for datum B₁ do
8:
Ed Vol(O,-1.0) d)
9:
gd - Ba/ max ggall/C
10:
end for
11:
G. - Eke (k)
G. :/ G: NO, o² Ixx))
13:
0, 0 n/
end for return updated model parameters Or
15:
The SCALE algorithm assigns different clipping thresholds but the same sampling rate for different data owners:
Algorithm The SCALE algorithm.
Datasets of all data owners D1. D2. Dy; initial model parameters Oo: sampling rate qi per-owner clipping thresholds C₁ C,, Cw: noise scale Output: Trained model parameters 0r.
Input:
1: 4 E In. D,.
2: for iteration [T' do
3: B, < subset sampled from D with rate
4: for datum d B, do
5: Ed Vo
6: gd - ga/ max |ggal [lllo////Cooo)
7:
end for
8:
G + Σ k= (k)
9:
G. 1 G: NO,, I²
10:
0, + 0 0--1-
end for
12: return updated model parameters Or
Specially, the two algorithms may be used jointly (i.e., different sampling rates and different clipping thresholds) which results Alg. and they all satisfy the same privacy guarantee (Thm. 2.2).
B.3 COMPARISON OF IMBALANCE AND FAIRNESS NOTIONS
In this section, we discuss various notions related to utility imbalance across groups, including (1) correcting data/class imbalance; (2) correcting DP-exacerbated accuracy disparity (Bagdasaryan al. 2019); and (3) achieving group/individual faireess. We will explain why and how our work, which focuses on IDP-induced utility imbalance/accuracy disparity, is related to (1), somewhat re- lated to but different from (2) and significantly different from (3).
(1) Data/class imbalance. As introduced in the main paper, data imbalance refers to (+) the imbal- ance in sizes of different groups in the training set, where each group optimizes different objective (e.g., each group holds a class (i.e., class imbalance) or a lot more of one majority class over the oth- ers). Existing works on (i) can be broadly grouped into two categories: data-wise approaches and optimization-wis approaches. Data-wise approaches (He & Garcia 2009) focus manipulating the distribution of original dataset or sampled data at each iteration, so that the number gradients for each group is similar. Oversampling works by sampling more data from the minority groups, but
25

---

Published as a conference paper at ICLR 2026
is infeasible under IDP due to the limited privacy budget of more private data owners. Undersam- pling works by selecting fewer data from the majority group and making their quantity comparable to the minority group, but is also unsuitable under IDP it would worsen the model utility when data are already searce. Optimization-wise approaches, on the other hand, focus on modifying the optimization objectives or algorithms. Many works (Japkowiez 2000; Lin et al.] (017) attempt to rescale the loss function in order to obtain gradients of different magnitudes for different groups. but their effects will be eliminated by gradient clipping in DP/IDP, Anand et al. (1993) and Francazi et al. (2023) rescale the obtained gradients directly to balance gradients from each group, but this will turn change the modular sensitivity of IDP-SGD and hence violate the privacy requirement of the algorithm.
We would like to restate that our setting differs as we do not assume (+), though we recognize data imbalance as a closely related problem since they both exhibit MIl) and BOO.
(2) DP-exacerbated accuracy disparity. Bagdasaryan et al. (2019) first identifics that if there exist underrepresented groups in the training set (i.e., (f) the training set is imbalanced), training with DP algorithms would make such groups even more underrepresented in the trained ML model, which is reflected even lower accuracy/utility on data from such groups (thus the term "DP- exacerbated"). In particular, it explains how clipping and noise addition of DP jointly lead to such a disparate impact and worsen accuracy disparity between the well-represented groups and underrep- resented groups. In contrast, our work does not assume (f) the training set is imbalanced. Instead, we identify that IDP itself can induce utility imbalance. Thus, our work orthogonal to the DP- exacerbated accuracy disparity line of works. Since our work also operates under (I)D,, we use a different term "utility imbalance" to avoid confusion.
Nevertheless, since (ii) and our work both address accuracy disparity/utility imbalance, we give a quick review of existing works on DP-exacerbated accuracy disparity. We thoroughly examine follow-up works of (Bagdasaryan et al. (019) and classify them as follows. (Farrand et al.) 20020] Ganev 2021; Ganev et al., 2022 Uniyal et al. 2022) analyze the problem of DP-exaacrbated ac- curacy disparity
Tran al. (2021a) lab uses alternative objective function which penalizes different (clipped) gradients and (trace of) Hessians among groups which the au- thors identify as sources of the disparate impact of DP: Xu et al. (2021) computes different eniffri thresholds for different data using additional privacy costs in order to control the contribution of each datum; [Esipova al. (2023) spends additional privacy budgets at each iteration to compute strict clipping bound (that is larger than the clipping threshold) and discards the gradients larger than the clipping bound: Kulynych et al. (2022) adopts importance sampling on each group's 's data based on the group size; Knolle et al. (2023) adds regularizing term to the loss function that penalizes large individual gradient norms which bring larger bias when clipped. Notably, these works operate under standard DP and assume uniform privacy budgets across all data owners. Thus, the impact the IDP setting, however, the same
of an additional privacy cost the same for each owner. additional privacy cost consumes larger fraction of the more private data owners' privacy budgets, which worsens the IDP-induced utility imbalance as we had novelly pointed out in Sec. Sec.B.I] More- over, these works are tailored to the disparate impact of DP caused by its clipping and noise addition components, while our utility imbalance arises from an orthogonal cause. Thus, they cannot address IDP-induced utility imbalance. For example, when using Tran et al. (2021a)'s 's alternative objective function, the different sampling rates and/or clipping thresholds introduced by IDP-SGD could still lead to MID, BOO and utility imbalance. Last but not least, is unclear how these works can even be adapted to satisfy IDP.
(3) Group/individual fairness. Here we will explain how group/individual fairness works focus on achieving similar model predictions/behavions across different groups/individuals. which sig- nificantly differs from our work and works in (i) and (ii) which focus on achieving similar model utilities/accuracies across different groups/data owners.
Group fairness: Consider a binary classification problem with class label y E {0, 1} representing whether an outcome is positive (e.g., whether candidate is qualified position). Let á denote the model prediction. Let x, denote a sensitive attribute (c.g., race) and X, denote the set of its possible values. Each value corresponds to a group. A general definition of group fairness, Fg, is
26

---

Published as a conference paper at ICLR 2026
follows (Tran et al. 2025):
Fg max u,EE&
(Prlý 1/2, u, Pr(ý 1/2, U, u,e]),
where u, v are possible values of zs, i random event, and the model owner needs to minimize Fg or ensure it is bounded when training their models. When e = 0. Fg measures the statistical parity (Darlington] I97TI. which means that whether an outcome is positive should independent of the sensitive attribute; when is the event = 1, F5 measures the equality of opportunity (Hardt et al. 2016), which means that all qualified candidates should get similar opportunity of positive outcome; when stricter than equality of opportunity and requires similar probability even when 1s negative. To this end, readers may understand why such works have different goal from ours: it seeks to achieve similar model predictions/hehavion
y. I'g measures the equality of odds (Hardt et al., 2016), which is
across different groups (which may lead to a greater imbalance in utilities some validation sets). Works addressing group fairness under DP include
(Ding et al. [2020] Jagielski et al. 2019 Lowy et al.; [023] Tran et al.) 2021b Xian et al. 2024
Xu et al.] 2019 Zhang et al. 2021).
Individual fairness: Similar to group fairness, individual fairness (Dwork et al. 2012) seeks to achieve similar model predictions/behaviors across different individuals, which is satisfied when
Vx, x'
P (u. 1') - xx(xxx)))
where D is some distance metric over the predicted labels and Dx is some distance metric over the inputs. Likewise, its focus on the model predictions á and differs from ours.
Since the goal of group and individual fairness significantly differ from ours, we do not com- pare with works under this category (iii).
C ADDITIONAL THEORETICAL RESULTS
C.I IDP-INDUCED UTILITY IMBALANCE
C.1.1 IMBALANCED SAMPLING RATES OR CLIPPING THRESHOLDS
In Fig. we show the imbalance in sampling rates and clipping thresholds of data owners that occur in the SAMPLE and SCALE variants of IDPSSGD respectively, computed using an RDP accountant. For example, for SAMPLE a less private owner with c can have a times larger sampling rate (0.19) than more private owner with c = 0.6 (0.019) when clipping threshold C' = 1 and noise scale = 4; likewise, for SCALE less private owner with c can have 10 times larger clipping threshold (3.29) than more private owner with e 0.5 (0.33) when sampling rate g = 0.05. These lead to the imbalanced distribution of gradients the sampled batch B, (Fig. 2 and cause the utility imbalance problem explained in Sec. 3.1
LOW
MED HIGH
LOW
MED:
HIGH
0:20
Cipgira Clonkgthreehhll threshold
5.00
Samplna
1.00
0.10
0.50
0.10
0.00
0.05
1.5 Privacy budget
Privacy budget
(a) Sampling rates q corresponding to differ- ent privacy budgets with added noise scales a = 1.0 to 4.0 in SAMPLE. Specifically, we set tolerance 8 10-5, clipping threshold C 1.0 and number of iterations T = 1000.
(b) Clipping thresholds C corresponding to different privacy budgets with sampling rate q = 0.01 to 0.10 in SCALE. Specifically, we set tolerance 5 10-5, added noise scale a = 4.0 and number of iterations = 1000.
Figure Imbalance of individualized sampling rates and elipping thresholds under IDP- SGD's SAMPLE and SCALE variants. (a) and (b) show the discrepancies in sampling rates and clipping thresholds for different privacy preferences.
27

---

Published as a conference paper at ICLR 2026
C.1.2 PROOF AND DISCUSSIONS FOR THEOREM 3.1
In this section, we state the formal version of Thm. prove it and provide some additional dis- cussions. Specifically, the first part of the theorem (Eq. (5) informs when the MID phenomenon cannot happen and therefore how to mitigate it; the second part of the theorem shows that MID can happen when the condition is not satisfied. Without loss of generality, we suppose there are two data
owners 1 and
Theorem 3.1 (Condition for Per-Owner Monotone Decrease of Loss IDP-SGD, formal),,,, Assume each data owner n objective function Lu is Li-Lisschitz and smooth. Assume the stochastic gradient sampled for each owner satisfies uniform boundedness with regards to the owner's 's full (ooolay(O--1)) S Eata) for some constant &n for each owner n.).
gradient (i.e., Pr(llgrdd
Consider two data owners with dataset, sampling rate and clipping threshold (D1, ni C1) and (D2, 92. C2), respectively. Recall that their corresponding loss objectives are Li and Lz. At each iteration i, when the following condition
42 D2|C2 SS
1+ cos( (4) DiCC
(5)
satisfied with < > 0 being a croblem-specifee term, by choosing a sufficiently small learning rate n, the losses for both owners are guaranteed to decrease in expectation. Moreover, whenever
92 D2 C2
1 + cos (1))
<0,
91 C
there exist ML tasks such that the loss for some owner increases, so the above condition is necessary to guarantee decreasing loss for both owners.
Remark.
The exact definitions of 5 and "sufficiently small" are formally stated in the full proof.
Although the theorem looks comparable to the original Francazi et al. (2023)'s 's condition, proving it is significantly more difficult due to the consideration of various components of IDP, including individualized sampling rates In. individualized clipping thresholds Cn, the gradient clipping mechanism that introduces clipping bias each owner's true gradient and the injected Gaussian noise to guarantee DP.
Interpretation. Thm. 3.1 explicitly illustrates the effects of individualized sampling rates 4n and individualized clipping thresholds C, on per-owner model utility. We now explain what it informs about the utility imbalance problem as we demonstrate graphically in Sec. 3.1 As shown at the start of this section (App. C.I.I. IDP-SGD itself would induce severe imbalance in the individualized sampling rates In and individualized clipping thresholds Cn, Therefore, even if the original training (D2)), the ratio Da would still be large (without loss of generality en D. assume owner is more private). Moreover, the angle L. is expected to be large as the directions of each owner's full gradient differ when the two groups have different optimization objectives. As cos( <:) and hence the left-hand side of Eq. 5 are negative, the condition is not satisfied. Thus, when the loss for the less private owner 2 decreases, the loss for the more private owner may not (which explains why MID can be induced by IDP-SGD too). Unlike the original condition (Eq, []. the C2
set is balanced (DDal
ratio n. 12, C stays constant throughout the training (in contrast the data imbalance setting where the corresponding ratio in Eq. [ gradually decreases) and hence the MID period can be even longer, which worsens the utility imbalance problem.
Relation to INO-SGD. From our proof, it is also clear that the larger the left-hand side of Eq. is, the less severe the utility imbalance problem will be, even when the left-hand side is negative. Our solution, the INO-SGD algorithm, aims to increase the left-hand side much as possible without hurting the overall model utility. By down-weighting the less important data within each batch, INO-SGD is empirically reducing the clipping thresholds C, for the less private data owners in strategic way that incurs no penalty on overall model utility by fully utilizing each owner's 's privacy budget.
Justification of assumptions. Our assumptions in Thm. 3.1 are reasonable and in line with existing imbalance/DP literatures. The smoothness assumption on each owner's objective function is often
28

---

Published as a conference paper at ICLR 2026
used to characterize the change in loss when parameter update is made, as a less restrictive sumption than convexity or strong convexity. It is used in recent imbalance works such as (Francazi
iet al.
2023
Zhang et al. 2025) and DP works such as (Arora et al. 2023 Chen et al. 2020b Das
et al.
2023
Sha et al. 2024). The uniform boundedness assumption is used to bound the stochastic
in the sampled gradients, which is widely used in optimization, especially clipping, literature (Li
ct al.
2023 Zhang et al. 2020 2019).
Proof outline. Since the full proof below is rather long, we provide shorter outline here for better understanding of the proof.
1. We use the symbol
represent non-negative term. Note that we only need to prove for one owner since the proof for the other owner is identical by symmetry. We first upper bound the change in loss L1 (9) using the smoothness assumption (see Eq. O
represent a term and
can be easily seen that term ( in Eq. 6 is non-negative, and the whole right-hand side can be
written the format
77
To this end, if we manage rewrite and bound terms A well such that in the above expression, the above expression is negative and we guarantee the decreasing loss. We eventually achieve this in Eq. of the format
> 0, then by choosing a learning rate y) smaller than
where the first gives a raw version of the target condition (Eq. 12 the middle is from an unavoidable clipping bias (which does not appear in the original Francazi et al. (023 s non-
private setting). Thus, we need the first _ to be larger than the middle + to guarantee decreasing loss, which leads to the right-hand side of the final condition (Eq. 5 not being O.
(a) Term (A)involves the inner product of owner I's full gradient and the noisy summed clipped
gradient G, from both owners. To analyze the imbalance between owners,
break down
G to three components: (i) summed clipped gradient of owner (term (C): (ii) summed clipped gradient of owner 2 (term ( (iii) DP noise. The final bound is given in Eq. 9
For (i) and (ii), we need to handle the clipping bias, that is, the different directions of each owner's 's full gradient and (expectation of) each owner's summed clipped gradient. We handle this by breaking down the summed clipped gradient to the full gradient plus the clipping bias (in our analysis of terms an) (D). The clipping bias is captured by term, ot.d. which is the scaling factor of each gradient to obtain its clipped gradient.
Therefore, (ii) involves the inner product of owner I's full gradient and owner 2's full gradient, which highlights the role of cos( (4).
(iii) vanishes as we take expectation because the DP noise is of zero mean.
(b) Although term (B) is non-negative, we derive a bound in order to better understand it. Simi-
larly, we break down G, to three components: (i) summed clipped gradient of owner 1 (term (ii) summed clipped gradient of owner 2 (term (D)): (iii) DP noise. Since (B) involves quadratic term, need to additionally consider the variance of the three components. The final bound is given in Eq. IO
(C)):
For (i) and (ii), the variances can bounded using & and & because of our uniform boundedness assumption (terms (F) and (
For (iii), the variance is r since the DP noise is Gaussian.
2. Now we have obtained the desired form and a raw condition (Eq. 12p to guarantee decreasing loss which involves the sum of clipping factors Φi.d- Note that the number of clipping factors in the sum is determined by the number of data sampled from each owner, i.e., 4u DD). The clipping factor determined by the clipping threshold of each owner, i.c.. Cn.. So we just have to further rewrite and bound the raw condition (Eq. 12) to a version that involves q., D..l and C, to understand the role of qn and Cn, which exactly the final version (Eq. 55)
We observe that the function mapping each owner's gradient to its clipping factor threshold is Lipschitz. Morcover, the mean of each owner's gradient is the owner's 's full gradient. Therefore, we can derive bound the clipping factor using each owner's 's full gradient (Eq. [3 and 14). By substituting the above bound into the raw condition (Eq. 12). the norm of each owner's 's full gradient is replaced by their clipping thresholds (Eq. (5) which explains why without data imbalance, IDP itself can induce MID and utility imbalance.
The full proof of Theorem 3.1 is as follows.
29

---

Published as a conference paper at ICLR 2026
Full proof. We focus the objective (1) for owner (proof for owner 2 is the same by symme- try). Since L1 is Lm-smooth, we have
T
(i(0,) - -1
G
(6)
2
(B)
Let Z₁ (O, Ixx)) denote the random Gaussian noise added at iteration (to ensure IDP). Let gr,d and Bi,d denote the gradient and clipped gradient associated with datum d at iteration / respec- tively. Let th, == min {1, Cotar/ //lgg...lll ||] 1/ max (1, |lgg.a/// /Coa) E (0, 1] denote the scaling factor to scale a gradient to its corresponding clipped gradient, i.c., Bt.d dr, Then,
Term A
71
VoLi (G. -z,)
(oL1(01-1),
Σ
gid
+
1 Σ
Bid + Z
b
b
d
dEBi,
Vol (
Σ
gidd
"1
VoLI(0
Σ Bidd -n (VL.)(() (22)
d
dEB1.
VoL (0.-))
Σ
-7 VaL,
Σ Br
17 (o.
7)
dEBI.1
dEBi,2
Σ
(1
11 Σ
(1-) -1 (0 7
d
de deB,2
7
Term C
- -
b
de
17
Σ
(.l. gr,a)
d
1
0t 1otpa///oo.0.oooooooooooo/111110 - graal
b
d
7
Lid -
dE
where (1) is due to CCauch-Schwaal inquutaay and (2) is due to the uniform boundedness assump- tion. Likewise,
7
Term
D
<
ord
b
d
7
b
dEB.2
where (recall that) 2, is the angle between the two owner's repertsee summed gradients VoLi and (0L2(0 Therefore,
Terme
Σ de dEB
b
dEB.2
VoLi k,21
(7)
30

---

Published as a conference paper at ICLR 2026
Now to term BB)
L
Term
GG Z,)
2
L2n
(G
+ Ze G. + Zi)
21
121p
1
L2n
|r|
+
G.,, Ze) +
||
Zel Izel?
262
b²
202
(F)
L2n
Term
E
Brd +
Σ
gi,d
262
de Br.1
d
(3)
L
L
Stdd
gr,d
122
i2
Be,
de d 2
(F)
(G)
where (3) is due to Cauchy-Schwarc inequality.
L27
Br,1l
Term
|
6²
d,
L2n Br.l
12
de Be,1
L2d B
[ ( -
12
deB
Len
FLd (0 -8. (e.a)+I/Vo.in VVoo - -gt,
62
dEB,11
(5)
L2n Br,1l
(= -r.all (V - -Br,al'
de
(6)
Leni B
Σ
did
+
62
d
where (4) and (5) are due to Cauchy-Schwarz inequality, (6) due the uniform boundedness assumption. Likewise,
Len Br,2
Term
(1 + de
Σ
12
Therefore,
L 2 Br.1 62
Term
B
Σ
Li (1 +
dEBr,1
22 Br.2l
Σ
Lia (1 +
+
6²
dEB,2
Lum? 12
L
G,
Z,)
12
(8)
212
Let F.- denote the filtration at iteration t (i.c., all the algorithm histories up to the start of iteration
(). Now consider the expectation of terms (A) (Eq.
and (B) (Eq. g) given filtration Fi-1
31

---

Published as a conference paper at ICLR 2026
iteration (i.e., now that we know already a particular 0 what happens to the loss after we update the parameters at iteration t?):
E|term
(A)
Fi-1] S
I2
Σ de B
(o../// - VoL Fe-1
dE d
(o 2, Fr-1
(H)
Term
H
0 because Z, is Gaussian noise with zero mean. For the terms before (H) given
filtration Ft-1, everything. except Bt.1. B, and hence 6, .d. are constant. Like other works that
theoretically analyze DP (Abadi et al. 2016 Bassily et al. 2019), we assume | q Dj and
[B,22 = D2|. Let δτ.1 = EdEDD 0r.a 1-1 and similarly Φr.2 = (o. We have
Ft-1] S 1991 n9i11i1
term
(A)
D2l
=
ot0p0//ehheeiiiilccccoooooooooa- (9)
+ 42
Now to the expectation of term BB)
L27
Br,l
term
B
F
<
E
62
dEB.1
L2
Br.2l
+x2) [r-1
62
deBia
L
2
L2n 2
+ E
(Gr, Zi)
Fi-1
+
2
F
212
(
Since the Gaussian noise Z. ~ NNO,,, o² Ixx)) term
0 and term
(J
We additionaly
20
denote お EdED, FF 11 and similarly
o Ede
[d?
Then,
" T b
E term
B
F
<
D1
TO²
+ +
2
(10)
Combining Eq. and 10
((,) Fe-1] - L.
D1 (
+ 4/ D2 1ade
4n a100
L27
0 12 (1 6 ro²
32

---

Published as a conference paper at ICLR 2026
? ( (1iIDitt.. + D2l
(oC2(00-1)1
--
VaLi(0 (0,- cos(<i)
(ailDilōrn1) + Q2l D2l / (V
(1)
L2 1RIDIP0
+
(M), part
+ D2 202 Pid + + + ro²
(M), part
(11)
In order to guarantee a decreasing loss in expectation, the learning rate should be chosen such that the above term < Note that terms (L) and [M) are never positive. Thus, term [emm[Kmmuss be positive,
and it should be positive enough at least to compensate term
(L) (since we can control term (M) by
varying the step size 17). Let == (41 D 1 + qa 22 52
(clearly 1/ 2 0) and we arrive at the following condition:
V (0
n1 Dil0r.1 + 02) D2
co8 (<4) > th.
(12)
VoLi
ại DD and 92 D2l are clearly controlled by the individualized sampling rates qı and @2 specified by IDP-SGD (e.g., the SAMPLE variant). Now we will break down Φ1,1 and Φ1,2 to see how the above also controlled by the individualized clipping thresholds C and C2 specified by IDP-SGD (e.g., the SCALE variant). We have Φr,1 EdED, F- = Ed D, [min {1, / [rr The function min / has derivative -C on (CI, Thus, when x E ( {i] (by uniform boundedness and triangle inequality). the function 1in ///3 is locally Lipschitz with Lipschitz constant C1 (oo
/r.
(o.l/oo( (0.-1)ll
(0. E1, G.)²
Also, the L2-norm| || 1-Lipschitz. Thus, we have
}
C1 (aax( E1, Gi})² E1.
Φr,1 min L,
(13)
VOLi (0-
Similarly,
δ1. min {
C2 Vo
}
C2 (max Ve E2, C2))² E2.
(14)
That is, T.,1 lies in small region around the clipping factor for owner 1's full gradient, ming1, VoL
2's full gradient, min(1, and øt,2 lies in small region around the clipping factor for owner > 0 and < > 0 respectively. To guarantee Eq. 12 to hold, need
Denote the right-hand sides of Eq. 13 and Eq. as
Ci + 92 D2l min { 1,
}
C2
(oL2(0
qi Dil min 1,
cOS( (e)
[o
Vo III
VoLi
> 41 Diks + D2 + v.
To fully utilize the privacy budgets, except the very end of training, the clipping thresholds C1 and
C2 should be set smaller than the raw gradients (works on adaptive clipping thresholds (Bu et al.
2023
Xia et al. 2023) actually enforce this). Thus, the above reduces
|CCC://.hheeeel/1e00cc/cccc/1/10 Dilsi 2ali+1 42 D2ke + vb
+ Cos q1 DDC
which requires 9: D +g cos 4)) 0 even when the bound is tightest (i.e., 41 = 0). Therefore, letting < = 1aangg==VVoiiii [V, positive), the condition can be reduced to Eq.
D |5 + D2ls2 + ())(qn) (D, (G) (which always
33

---

Published as a conference paper at ICLR 2026
When Eq. 5 and hence Eq.
12 satisfied, referring to the expected loss change in Eq. 11 by
choosing a 7 smaller than
(V ( (1 (alPoónn VoLi V CoC2(0 cvo(11)
9: P:lor 0a D2loc2
V co (00-111))))))))
33
( ([
VoC + E + + Del
oo (I +1
rd²
Mi
bithout
the loss is expected to decrease. Note that both the numerator and the denominator are guaranteed be positive by Eq. 12
Tightness of the result. We first show that whenever + cos(<r) na Da < the losses for both q: 1Pr
owners are not guaranteed decrease together. Consider number parameters r and ob- jectives L1 (0) = 0 + (100- 82)² and (g) (100 01)2 + 62. the clipping thresholds for and C2 respectively and datum is sampled from each owner, i.e., 21 D2 92 D21 = 1. Suppose now 0t-1 (20) Suppose that the mean gradient of each owner n is the actual gradient (0 that is, (_12p) for owner and (-120) for owner 2. 80)/(120 + 803) = - 12/
owner and 2 are C1
In this case, cos( = (80 (-120) (-120) for both owners, if their respective mean gradient is g. the stochastic gradient is a random sample from (Unitorm(g) -0. +50)). Assuming that the DP noise is negligibly smal the expected sum of Unifform(22 -5.2
112/13. 13. Suppose that
clipped gradient is
130 115 10x
1
+9
dg2 dgi
TOa
J
170
70
85
75
Vss+
Ca91
dg2 dgi
-0.816 + 0.566 (-08830)
0.532
130
1115
115
Vo
dg2 dgi
+
10
170
75
85
Vo
Ca92
dga
dgi
=
The loss for owner 1 will decrease only when the expected summed gradient lies between (=120) /
and owner I's mean gradient, i.e., C2 < 1.067, that is, 1 cos(<) 92 Dz 0.0148. This suffices
(144))=l1))) 9:]os < <0, the losses for both owners are not guaranteed to to show that whenever + cos(<L) qu [2 I,
decrease together. This also shows that the problem-specific positive term ç the right-hand side of Eq. ij necessary, compared with the original Francazi al. (2023 's condition (Eq. D
In our proof, the bound for term (A) in Eq. 7 can achieve equality when all the stochastic gradi- E. or (A) is responsible for the
ents for an owner are in the same direction and their norms are either VnLn
(, + 1.. so is tight. This is important because only term
condition (5.. Term ii) only related to term (M) in Eq. and thus even if tighter bound can
be attained, one will arrive at a similar result by choosing a slightly larger learning rate Therefore,
choose reasonably good bound for
C.2 THE INO-SGD ALGORITHM
C.2.1 UNSUITABILITY OF STRAIGHTFORWARI APPROACHES
In this section, we give a list of straightforward approaches address IDP-induced utility imbalance that might be considered at first glance. We will argue why all of them are inadequate:
Enforcing the lowest privacy budget for all owners (e.g., by undersampling using smaller clipping thresholds): This approach aligns with DP-SGD, which under-utilizes IDP budgets and
has a significantly lower overall model utility compared IDP-SGD (Boenisch al. 2024) (see
empirical evidence in App. D.4.3). Our algorithm will fully utilize each owners' IDP budgets
instead.
Randomly downscaling owners with higher privacy budgets (e.g.. by down-weighting or un- dersampling): This approach has several issues. Firstly, for multiple data owners and privacy budgets, it is unclear how set (i) the cutoff between less and more private owners and (ii) how much to downscale from each less private owner. For (i), for example, for 10 owners with en [0.5, 5) evenly, it is unsuitable to directly the mean 2.25 the cutoff since the impact of privacy does not scale linearly with privacy budgets and is hard to quantify a priori; for (ii),
'In our proof, we can that the DP noise appears only in term sufficiently small learning rate 77.
M which can be compensated by
34

---

Published as a conference paper at ICLR 2026
downscaling in the same way from owners with e, 3 and c, = 5 is unsuitable, as there is still imbalance between these two and downscaling owner 3 incurs different utility loss than owner 5. Due to (i) and (īi,, when there are N owners, finding the optimal number of data to drop from each owner requires O(N) hyperparameters, making the approach inadequate. Secondly, this approach also under-utilizes IDP budgets and leads to a worse overall model utility. We provide empirical evidence in App. D.I.3 and App. D.4.3] Thirdly, when some data from less private owners still have higher loss (e.g.,& a harder-to-prediet one), randomly downscaling would undesirably worsen utility imbalance. Our algorithm would order data by their losses to identify the important data we should fully keep. This is sensible as the importance of gradient information of each datum in batch B, at iteration / directly correlates with their individual loss values (Kawaguchi & Lu 2020: Shrivastava et al. 2016).
Keeping samples with top-yi losses: As an example, consider a batch B with 16 data and we keep only the gradients with top-8 losses. A private datum is added to batch B and its loss is ranked 1st. The original 8-th datum d' will no longer be in top-8 and will be discarded. Suppose that the clipping thresholds of and d' are Cotd) and Cota") (recall that o(d) refers to owner of d). The Io-norm of change in the sum of gradients within batch B can reach maximum of Cold) + Cotar) (by triangle inequality), which contradicts the requirement that the addition of d should only cause a change of 1.2-norm Co(d) in the sum of gradients. Thus, keeping samples with top-p losses does not satisfy DP (when all clipping thresholds equate to C, the change can reach 2C) nor IDP.
Discarding samples with smallest-p losses: Consider the DP case when all clipping thresholds are equal. Suppose again that a batch B of 16 data is sampled and we remove the smallest-8 losses. When a private datum d is added to B, if its loss is larger than the datum with 9-th loss, will be kept and the norm of change in the summed gradient is at most Co(a); if its loss is smaller than the datum with 9-th loss it will be discarded and the original 9-th datum d''s s gradient will be kept instead of discarded. The norm of change in the summed gradient still most Ca(a)- When d is instead already in B and will be removed from B, the analysis will be similar to the norm of change when is added to B {d]. Thus, this approach actually satisfies DP. However, does not satisfy IDP. In the case of IDP, when d is added to the batch and its loss is smaller than the 9-th loss, it will be discarded. The original 9-th datum, say d', will be kept instead of discarded, causing change in the summed gradient with norm Co(dr). which can be larger than Co(a)- Thus, the modular sensitivity A is no longer Cota) and this approach does not satisfy IDP.
C.2.2 ALTERNATIVE SORTING ORDERS
In the main paper we propose using the order of loss to rank the importance of data within each batch. However, it can in fact work with many other sorting orders since it is an INO-SGM mechanism as introduced in Sec. 3.3.1 and App. C.3.2
One example is a mixed order: we may rank data primarily based on their ownership (i.e., data from the more private data owners ranked higher) followed by loss values within each owner. In this way, ideally, gradients from the more private data will always be ranked very high and they will never fall into the tail region and be discarded down-weighted. However, we find that this order does not perform as well as directly using the order of loss:
Sometimes, the less private owner's data can be difficult to learn and still have large losses and vice versa. INO-SGD using this order would undesirably downweight such data by assigning them low importance scores.
The least private owner's data are always at the tail, and they could never be learnt. For example, in our CM-PC experiments (see App. D.Ip with 10 data owners, the least private owner 10's maximum accuracy is only 0.2% throughout the learning dynamics using this order, which means that its data is always severely down- weighted and barely learnt.
C.2.3 BATCH IMPORTANCE FUNCTION
Based on the transformation described in Sec. 3.2 we include the formal definition of BIF below:
Definition C.2 (BIF). Given preset TIF faa [0,>] + [0, 1] and a sampled batch B, of data whose sum of clipping thresholds equals rr. the batch importance function (BIF) fe [0, Tx] - [0,1] is
defined in the following way (under the notation of ordered pairs):
rf 2 7, then ft = {(c, 1) C [0 - 71)u((e) Sun(ce (Ce-cc-----aa (T :ce (T, (2272.1.))
35

---

Published as a conference paper at ICLR 2026
If then {(c, fiu(c +1 (7- (1))) e eee [o,r.]]-
Since TIF is non-increasing and Riemann- beemann-nteerabbe, it can be clearly seen that the BIF is also non-increasing and Riemann-integrable, which justifies how INO-SGD computes per-sample im- portance score via integration.
C.2.4 RUNTIME OF INO-SGD
We highlight that the runtime of INO-SGD does not differ much from that of IDP-SGD despite the additional operations, i.e., sorting and integrating:
The most costly steps, including backpropagation and per-sample gradient processing (clipping) are shared by both IDP-SGD and INO-SGD.
The time taken sort the gradients in batch B, is O( B:]), which is negligible compared with the backpropagation time.
Simple TIFs, such step function (e.g.. in App. C.2.5 be integrated exactly in O time. The integration of more complex TIFs can be parallelized within each batch. Moreover, since the same TIF is used throughout training, the model owner can pre-compute a fast integration array:
Pick a number K much larger than the expected sum of clipping thresholds ΣnE[N] gnl Cn:
2. Compute a BIF Ja [0, + [0, based on the TIF fuil;
Compute the cumulative integrals (x(x) = fo¹ fa(e) de for c 0,... ; up to a certain precision. The (x)'sss form the fast integration array.
4. At each iteration t, 5 fc(c)d== - ro fx(c) dc Fx Fx Fx
becomes simple ((1) lookup.
On CIFAR-10 with batch size 1024, the wallelock runtime of epoch in seconds (averaged 10 epochs) for IDP-SGD and INO-SGD are 11.80 + 1.21 and 11.89 + 0.64 respectively, which supports our claim that INO-SGD introduces negligible computational overhead.
C.2.5 REMARKS ON TAIL IMPORTANCE FUNCTIONS
In this section we first give example of an alternative TIF: the model owner can use step function that splits the y-tail into partitions and specifies constant importance scores within each partition: 1/2 for the first, 1/4 for the second, ..., for the last)). App. D.4.2 shows that INO-SGD can still give competitive performance for such functions.
Although INO-SGD may work with various forms of TIFs, we still recommend the Beta- distribution-based TIF mentioned in Sec. 3.2 in the main paper, which allows the model owner flexibly control the TIF shape with only few parameters. Below guideline on how tune these hyperparameters in practice:
The TIF with some tail length 71 and some B1 has a similar shape to another TIF with larger tail length > 71 and larger beta B2 > B1. so it suffices to fix moderately large tail length y (e.g., 50% of the total clipping threshold) to only tune a and [; OR fix and B (e.g.. 1 and 1) and set the tail length to (or only tune the tail length around) a certain percentage of the expected sum of clipping thresholds for each batch.
We demonstrate that INO-SGD is robust to hyperparameter choice in Sec. 4.3 and App. D.4.2 Thus, tuning according to the above guidelines is practical real deployments. When the model owner is willing to trade more overall utility for less imbalance, they can manage the tradeoff by increasing the tail length y (the easiest way), or setting larger & and smaller ß.
C.3 THEORETICAL ANALYSIS OF INO-SGD
C.3.1 PROOF AND DISCUSSIONS FOR THEOREM 3.3
In this section, we give a formal proof of Thm. 3.3 (privacy of INO-SGD). Consider the sub- algorithm in Line 7-16 of Alg. T which takes batch of data B, and returns the sum of clipped gradients G, Let co 0 and e denote the accumulated clipping threshold until (and including)
36

---

Published as a conference paper at ICLR 2026
the k-thh ranked datum (x)- We first prove that for any datum d, the modular sensitivity 4 of the algorithm at iteration t is bounded by d's corresponding clipping threshold Coldy. Suppose that new datum d is added to the batch B,. Without loss of generality, assume that d, is ranked the a-th in the new batch B, U {da}- The importance function changes from ft to s?. It can be seen that all data that are ranked higher than d, receive larger gradient weights while data that are ranked lower than dg are not affected. Therefore, the change in the sum of clipped gradients G2 consists of d 's (weighted) clipped gradient and the increase in (weighted) clipped gradients of all data that are ranked higher than da. that is,
fee Cu
f de Co(d)
a-1
Set St de
Sen ft de
gd, +
Σ k=1
gdd.
(15)
Ck
Ck-1
Ck ck-1
Because of how BIF is constructed from TIF, we have san ft dc - dc-Jaa fo dc Soe
fi de-
fi de = 1a CtCld ft de - Jex CostC))ss) ft de. Thus,
Jea-1+Col40
Se 17 de
CN St de
Se fr dc
Bd, +
Ck-1
gdd
Colah)
Ck Ck-1
Ck Ck-1
(1)
Ca li de
0k- -Ould)))
Sa de - Sa
Colteo
S de
| +||
ca-1
||
Coldh)
Ck ck-1
k=1
ft dc f ContColdd
[Bd,
Ede
de.
St de)
Co(d)
Gu
k=
Ch Ck-1
(2)
e-1
I+Calds)
( (antCales
fi de+ Σ(
ft de
Jex
ft de)
J6-1
(3)
ca
ft dc - pen ft de
fi dct
ca-1
Cold)))))
ft dc
Jco
I Co(d))
Here (1) is because of triangle inequality and the fact that BIF is non-increasing; (2) is because
Bd ga/ max(1, llggl///CCCC (/C))))) and hence ||gall S Co(d) for any datum d: (3) is by telescoping sum.
When a datum dy deleted from the batch B,, the change in sum of clipped gradients is equal to the case where du is added to the batch B; {da}. The - of the change is hence bounded by da's 's clipping threshold Co(ds)- Therefore, we have proven the modular sensitivity statement.
For data owner n [V] whose sampling rate is Jn iteration t and whose clipping threshold is On (and thus the modular sensitivity corresponding to its data), each iteration of the INO-SGD algorithm satisfies (a,,, -DDP by Thm. B.9 (since is an SGM), where
CR ah
Zn = 20
(16)
o?
By composition of RDP along all T iterations (Thm. B.5). we have shown Thm. 3.3
Remark. Note that the use of order of loss in each batch does not incur extra privacy costs, as such order iteration comes from the ML. model obtained at iteration / 1, which is itself standard output under adaptive composition (i.c., similar to the gradients we obtain at iteration t for each sampled datum). Thus, for mechanism using the gradients and/or the order of loss, as long as we bound its (modular) sensitivity at iteration f, it strictly satisfies IDP by adaptive composition.
Remark. We assume that the model owners have decided TIF beforehand (e.g., based past experience) and do not consider the cost of tuning any hyperparameter. This is consistent with other works that devise (I)DP algorithms to solve certain problems (e.g., Xu et al. (2021); Esipova et al.
37

---

Published as a conference paper at ICLR 2026
2023 Lowy al. (2023)) Bounding the DP cost in tuning hyperparameters be addressed by DP hyperparameter tuning works (Sopa et al., 2025 Wang et al. 2023 Ding & Wu 2025). When the privacy budget for hyperparameter selection severely limited, the practitioner can consider few hyperparameter tuning choices based on the following guidelines for the Beta distribution-basel TIF. The practitioner
fix moderately large tail length ? (e.g., 50% of total clipping threshold) to only tune & and ß; when privacy budget is extremely limited, the practitioner can fix and ß (e.g., 1, 1) and tail length (or only tune it around) fixed percentage of the expected sum of clipping thresholds for each batch, and we show INO-SGD is robust to hyperparameter choices in Fig. and Fig. 16
C.3.2
THE INO-SGM MECHANISM
In Thm. 3.4 we give description of the INO-SGM mechanism. We provide the full version below
and prove it.
Theorem 3.4 (INO-SGM, formal). Let be a function mapping an arbitrary set of data B to R such that [g(d)l upper bounded by A Let wa be a function mapping B to some order that works in the following way:
s: R' + R a scoring function that can assign score to each datum in
For subset B C B, w.(B) returns an order of data in B such thut w. (B)(k) returns the datum d with k-th largest score s(d) in B.
Suppose B = {d: d is sampled with probability Qo(d) } is sampled subset of data. Then releasing Σ B
Ek=1 (Bg(E, + (N,,,, satisfies IRDP, where Pk is set in the same way as BIF.
More specifically, y represents function that takes in datum and returns the information wish to obtain from the datum; w, constructs the ordering of any sampled subset B such that (B) gives the k-th ranked datum in B. This can be used represent the importance, certainty, usefulness or any other properties of data. By summing up Pag (1,((())))))))))))))) (k)), information from better data is as- signed larger weight and thus we will in general obtain useful results. The INO-SGM mechanism can potentially be applied to any field where order of data is important and can be used to improve the outcome.
Now we provide a proof of Thm. 3.4 When a new datum da is added to B and assuming de is ranked the a-th of Thm. 3.3 the change in the sum of obtained information consists of d, 's (weighted) information and the increase in (weighted) information all data that are ranked higher than da. that is,
{da), the importance function changes from to f Similar to the proof
[C l de odd)
Ja
c
l de
Set I de
g(db) +
Σ
g(da))
(17)
Ck-1
Ck Ck-c-11
1=
Because of how BIF is constructed from TIF, we have set, fa de dc- sot, I de j fd de
let
Jea-
Doct)
f dc = Set -at-1 (Doi))) fa de - f portDota)) fa dc. Thus,
En-i-Aoldh)
Ca f de Jea-1
c fa de
Sah f dc
s(du)
-((p)) +
Do(d))
Cs Ck-1
C# - ck-1
(1) SCa fa de
( fa de Ser 5
Dotes for de |[g(ds)]
Do(d)) 119(da)l +
Ck Ck-1
fa de [[g(dh)] Ca-1
partdure fa de) [1g(d>)) )| Cs - Ck-1
fo de
Do(d,) k=1
Jc-11
Jt
(2)
Go
a-1
Ce-1tAu(())
patsoios Ja
ga dc
for dc
fe de)
Ca-1
k=1
ck-1
co Doldi)
na de+
fdd de
f de
Ca-1
00
ca-1
38

---

Published as a conference paper at ICLR 2026
Do(c))
l de
D.(d)
Here (1) is because of triangle inequality and the fact that BIF is non-increasing; (2) is because [[g(d]] s Ao()) for any datum d as defined; (3) by telescoping sum.
When datum da is deleted from the batch B, the change in sum of clipped gradients is equal to the case where da is added to the batch B {da]. The no-morm of the change is hence bounded by da clipping threshold Ao(d)- thus completing the proof for modular sensitivity.
For data owner n. E [M] whose sampling rate is On and whose clipping threshold is A, (and thus the modular sensitivity corresponding to its data), the INO-SGM algorithm satisfies (0in (0n))n)=a -RDP by Thm. B.9 where
2 Zn = 20x r²
(18)
Remark. Thm. 3.4 assumes functions g and do not consume further privacy (i.e., they should be independent of dataset B (e.g., at the first iteration of SGD where the model parameters are randomly initialized) or are already protected by IRDP (e.g., at each iteration of INO-SGD).
C.3.3 INO-SGD OBJECTIVE
In this section, we will give formal proof of Thm. 3.5 (objective of INO-SGD). At iteration t, the batch B, sampled from dataset D with per-owner sampling rates q is equivalent batch sampled from D with uniform sampling rate a. Let b denote the (expected) batch size B, For simplicity
assume C = 1 and is intege 10] The expectation of summed gradient (omitting gradient clipping and noise temporarily) is equal to
K
Pr de E Bi] (Pr(T(k) E 7-tail] corresponding + Pr(TT()) & 7-tail)
EB, Go
=
Vl (0)
K
K- k) (111-))<=--1 f
Σe q
f--en fig dc+
K k
K - k Σ
i'(1 -1)x((bbo) Vl (l)(k)(0).
The inner bracketed sum is obviously larger for smaller ks and it is always at most 1. By setting WR = K4 C (1- k (
fi Ex IK-k (1-)))) (- (lx(() -
we show that the expectation of equal the gradient of the INO-SGD objective C (0, D). Therefore, we have proven Thm. 3.5
The fact that vanilla SGD with gradient clipping optimizes the SGD objective function can be gener- alized to INO-SGD as similar first-order optimization technique. Similar to vanilla clipped SGD, INO-SGD with clipping and noise addition also converges to the optimum of the stated objective while suffering from unavoidable bias.
C.3.4 BENEFITS OF INO-SGD OBJECTIVE
In the main paper we give some brief summaries of interpretations of INO-SGD's objective. Here we give more details and discuss them further:
IIn DP analysis, only the ratio between clipping threshold and noise scale, called noise multiplier, matters. 10 can always he rounded up to the nearest integer by lengthening the tail.
39

---

Published as a conference paper at ICLR 2026
We mentioned in the main paper that the INO-SGD objective can be viewed the mixed condi- tional value-at-risk (mixed CVaR) of the loss function l, when l is viewed as a random function of d E D. Specifically, CVaR and mixed CVaR are concepts from risk theory. The X-level CVaR refers to the average loss when only the data with top 100X% losses remain in the dataset (i.e., 100X% worst-case tail of losses) and the mixed CVaR represents a weighted average of CVaRs at different À E (0, 1J (i.e., different severity of worst-case). Thus, the trained model will improve the performance on data with the larger losses which are likely to belong to more private owners. We also mentioned that the INO-SGD objective can be viewed as an objective that better corrects for utility imbalance than average loss when minimized and is less affected by outliers/noises with large loss than the maximal loss. This is shown empirically in Fig. Torh) and Fig. [3(h)
An alternative interpretation is through distributionally robust optimization (DRO) (Goh & Sim, 2010). DRO studies how to preserve robust model performance if the actual data distribution during ML model deployment is different from the training data distribution. To achieve this, typical solution is consider distributions of training data that are different from the training set itself and train a model that can minimize the maximum loss among all these distributions.
Specifically, the INO-SGD loss Lie (0. recovers the DRO objective
K inf sup Σ p4l
0 pEp km
where uncertainty set P = {p : sort(p) 3 w: Ex Ps = L:p 2 0} denotes the set of possible true probabilities of each datum in 1 occurring in the underlying distribution, sort(p) denotes the sorted sequence of p in descending order and 3 denotes partial order over decreasing sequences of length K defined as p I p' e Ak E [K] of the uncertainty set P increases and the trained model becomes more distributionally robust when the learner chooses a larger length of tail y or faster decaying tail importance function fy (e.g, large & and small when using a Beta distribution). This explains why our INO-SGD can give better results than the vanilla IDP-SGD when IDP-induced utility imbalance occurs.
Dン E In particular, the cardinality
D ADDITIONAL EXPERIMENT RESULTS
The experiments are run on the following machines:
Ubuntu 18.04.5 LTS, Intel(R) Xeon(R) Gold 6226R (2.90GHz) with NVIDIA GeForce RTX 3080 GPUs (CUDA 11.3); Ubuntu 22.04.3 LTS, AMD EPYC 7763 with NVIDIA L40 GPUs (CUDA 12.3).
All the programs are written in Python and executed using Anaconda. The implementation details and hyperparameters used can be found from our codes in the supplementary materials.
D.1 SETUP
D.1.1 DATASETS AND DATA OWNERS
We empirically evaluate our proposed method INO-SGD on various tabular, vision and language datasets. For each dataset, we first split the training set into N disjoint subsets representing the datasets owned by N data owners, across different subsets have different traits (e.g., we can split by classes or categories) to simulate the different subsets that could have different privacy preferences. We then assign each data owner a unique privacy budget ranging from low (private) to high (less private). Besides the standard settings (MN, CM, CL. CH, CF, SU (explained detail below)), we consider the following special settings:
way that data within each subset share similar traits and data
Real-world clinical datasets where owners of (likely) positive-case data have stronger privacy requirements, which supports our motivation (CA, PN);
Noisy datasets with random flipped labels (CFN);
Each data owner possesses datum and has its own privacy budget. Data owners with data from the same group have similar privacy budgets sampled from the same distribution with unique mean associated with the group. This resonates with real-life scenarios where data owners with sensitive data in general have less private budgets but vary (CS, CFS);
40

---

Published as a conference paper at ICLR 2026
Sensitive data occasionally have weaker privacy requirements and vice versa (COL, COM); Each owner has a fixed privcy budget but they hold a randomly sampled class in each experiment run. This can eliminate the potential impact of class complexities on per-owner utility (CR).
The details on our datasets and how we set the data owners are described below:
CA: We the UCI CArdiotocography dataset (Campos & Bernardes 2000), which contains
2126 tabular data of fetal cardiotocograms (CTGs) from 3 classes (NORMAL, SUSPICIOUS, PATHOLOGICAL) representing whether fetus is healthy or not. We assign privacy budgets 3 (most private), 4 and 5 (least private) to pathological, suspicious and normal fetuses. Tolerance 6n 10-5 for all owners n E [M]
PN: We use the Pneumonia dataset (Kermany et al. 2018), which contains chest X-ray images from classes (NORMAL, BACTERIALPNEUMMNIA. and V'RAALNEUMMOII). We randomly pick 1341 data from each class as the training set. We set 2 data owners: Owner 1 possesses NORMAL data and requires (5, 10 10-5)- (less private), while Owner 2 possesses BACTERIALP- NEUMONIA and VIRALPNEUMON
patients' data and requires (0.5, 10 DDDP (more private).
MN: We use the MNIST dataset (LeCun et al. 1998). whose training set contains 60000 grayscale images of handwritten digits from to 9. In our experiment, owners, with one possessing digits from to 4 (30596 data) and another possessing digits from 5 to 9 (29404 data). To simulate individualized privacy preferences, we assign privacy budgets
suppose that there are N = data
1 = 0.1 (private) and 62 = 1 (less private) and tolerance 53 = 8g = 10-5
CM: We use the CIFAR-10 dataset (Krizhessyy & Hinton| 2009), whose training set contains 50000 images of objects from 10 classes (e.g., CAT, DOG). We set N = 10 data owners, where owner n possesses data from class n 1. CM refers More private setting where we uniformly assign privacy budgets en ranging from 0.5 (most private) to 5 (least private) and tolerance 8,
10 for all n e []].
CL: Similar to CM, but considers a Less private setting where we uniformly assign privacy bud-
gets 6, ranging from 6 (most private) to 15 (least private) and tolerance 6,- = 10-5 for all n E [N]. CR: Also similar to CM, but considers each data owner holding Randomly sampled class in
each run. Their privacy preferences remain the same. This could eliminate the impact of inherent difference in class complexities.
CS: We use CIFAR- 10 and consider the case where each owner possesses only datum and owners possessing data from the same class have Similar (but not same) privacy preferences. Specifically, each class's 's mean privacy budget uniformly ranges from 0.5 (most private) to 5 (least private), and each owner's privacy budget uniformly sampled from class mean + 0.25. COL: We use CIFAR-10 and consider the case where occasionally some sensitive data have weaker privacy requirements and vice versa, that is, there are Overlaps among data owners. COL considers Less overlaps where each owner possesses 90% data from one class and 10% data from any other classes.
COM: Similar to COL, but considers More overlaps among data owners where each owner pos- sesses 70% data from one class and 30% data from any other classes.
CH: We use the CIFAR-100 dataset (Krizhevsky & Hinton| (009), whose training set contains 50000 images of objects from 100 classes (e.g., FLATFISH, BICYCLE). Every classes come from category (c.g., FLATFISH comes from the FISH category). We set N 100 data owners, where owner n possesses data from class n 1. We uniformly assign privacy budgets e, ranging from 1 (most private) to 10 (least private) and tolerance 6n 10-5 for all n E [N]. CF: We consider N = 2 data owners, each possessing data from one category (i.e., 5 classes). Specifically, Owner owns the FISH category containing AQUARIUMFISH, FLATFISH, RAY, SIIAKK and TROUT classes, while Owner 2 owns the VEHICLESI category containing BICY- CLE, Bus, MOTORCYCLE, PICKUPTRUCK and TRAIN classes. Owner requires (1, 10-1)-5).. - (private) while Owner 2 requires (5, 10 3D (less private). We denote this as CIFAR-100- FV. CFS: Similar to CF and CS, each category's mean privacy budget is 1 and respectively and each owner's s privacy budget is sampled from the Gaussian distribution with mean = its category mean and standard deviation 0.5.
CFN: We use CIFAR-100-FT and consider the case where the dataset is more Noisy. Specifically, we introduce 10% random label flips.
SU: The SUrnames dataset (Robertson) 2017) (SU) contains 20074 surnames from 18 different countries. with Country being the majority country containing 9408 surnames. We consider N = 2 data owners, including a less private data owner who possesses data from the majority
41

---

Published as a conference paper at ICLR 2026
country and requires 10100- (8,10-9)-DP and more private data owner who possesses data from other countries and requires (2, 10 - -DP. This is because data from other countries might be more difficult to obtain compared to the majority country with plenty of data.
For all the datasets listed above, we use their default split of training and validation sets in our experiments.
D.1.2 MODELS AND TRAINING
In the main paper, for vision datasets (MNIST. CIFAR- 10, CIFAR- 100 and CIFAR- 1V--FF,, we use of convolutional neural network (CNN) models proposed by Papernot et al. (2021) which cater to DP-ML and are widely used in existing literature (Trmmr & Boneh] [021] |021 Boenisch et al. 2024).
These CNN models are smaller than popular models such VGG (Simonyan & Zisserman 2014)
or ResNet (He et al., 2016), but are more suitable for DP-ML because the (expected) magnitude of added Gaussian noise (drawn from (0, Ix)r)) increases with the number of model parame- ters r. Also, they use Tanh activation functions which are shown to perform better in DP-ML. We supplement these CNN experiments by considering more complex models and embeddings such as experiment
ResNet- 18 (He et al. 2016) and SimCLRv2 (Chen et al. (2000a). For language dataset (Surnames), we use character-leved long short-term memory (LSTM) model from Boenisch et al. (2024), which is type of recurrent neural network (RNN) model that treats each surname as a sequence of char- acters (i.e., letters and special characters).
The details on all the models used are listed below:
MLP: Refers to a simple Multi-Layer Perceptron (MLP) model with hidden layers each con-
taining 47 neurons and ReLU activations.
PC: Refers to Papernot et al. (202T)s 's CNN models. For MNIST, this refers to a CNN model with 5 hidden layers (Conv-MaxPooll Corrroll-CooM-MaPoolllooo and fully connected layer, for CIFAR- 10, CIFAR- 100 and CIFAR-I00 this refers to a CNN model with 10 hidden layers
with Tanh activation at each convolutional
Maaxpool-Con--Con-Maaaa
FC) with Tanh activation at each convolutional and fully connected layer.
RN: Refers to ResNet-18 (He et al. (0166) model trained from scratch.
SC: Refers to a pretrained SimCLRv2 model 1.50_2x_sk1] (Chen et al. 2020a) which we use
obtain embeddings and train linear model upon them.
EN: Refers to a pretrained EfficientNet B1 model (Tan & Le 2019) which we used to obtain
embeddings and train an MLP with hidden layer containing 512 neurons and ReLU activations. Each input is mapped to a 64-dimensional embedding. The LSTM has a hidden size of 128, with internal linear layers projecting to 512 dimensions.
LS: Refers to character-level LSTM model (Embedding-LLSTM--
We will label each experiment in the format [dataset]-[ [mooee]] (e.g.. MN-PC). For each dataset- model combination, we choose from the two variants of IDP-SGD, SAMPLE and SCALE, at random since they usually have similar performances and it is not yet clearly understood which variant has advantages over another. Specifically, we use SAMPLE for Cardiotocography, MNIST, CIFAR- 100, 100-FV 110AF- and Surnames datasets, and SCALE for Pneumonia, CIFAR datasets. The same setting is used when test method INO-SGD. Furthermore, we repeat each experiment for times and show the means and standard deviations of results to tackle randomness.
CIFAR-
1.1.3 CHOICE OF BASELINE
Since this is the first work that recognizes and addresses IDP-induced utility imbalance, there is no prior work that mitigates the problem and is suitable as baseline. Therefore, we compare against the most important baseline IDP-SGD in all experiments.
In Sec. 3.1 and App. C we have explained why existing techniques addressing utility imbalance (either in non-private or private setting) neither satisfy IDP nor can be easily adapted to do so. To add on, we explain why common techniques to address data imbalance in the non-private setting are not suitable in the IDP setting:
Strategically dropping data from the less private data owners before training (e.g., with data pruning): This does not satisfy IDP. For neighboring datasets D and Dd if the dropping algorithm is deterministic, the resulting datasets D' and De may not be neighboring, thus can be identified
42

---

Published as a conference paper at ICLR 2026
by attackers even if IDP-SGD is applied to D' and Dd if the dropping algorithm is randomized, the resulting datasets D' and Dd may not follow a similar distribution, thus can be identified too. Therefore, it remains non-trivial to design a dropping algorithm that preserves IDP, which is beyond the scope of this work.
Randomly dropping data from less private owners before training: This has two issues. Firstly, for multiple data owners and privacy budgets, it is unclear how to set (i) the cutoff' be- tween less and more private owners and (ii) how much data to drop from each less private owner. For (i), for example, for 10 owners with G, E [0.5, 5] evenly, it is unsuitable to directly use the mean 2.25 as the cutoff since the impact privacy does not scale linearly with privacy budgets and is hard to quantify a priori; for (ii), dropping equal number of data from owners with en = 3 and En 5 is unsuitable, as there is still imbalance between these two and dropping data from <n = 3 incurs different utility loss than én = 5. Due to (i) and (ii), finding the optimal number of data to drop from each owner requires ((N) hyperparameters, making it unsuitable as base- line. Secondly. this method may under-utilize the privacy budgets and data from the less private data owners. Due to the privacy-utility tradeoff (Makhdoumi & Fawaz, (013), the overall utility would be lower than
current baseline IDP-SGD which fully utilizes the privacy budgets of each owner. Below we show the overall validation accuracy (mean (standard deviation)) when we drop 10% to 50% data from less private owners (cutoff mean):
Table 3: Random undersampling degrades overall validation accuracy.
Setting
IDP-SGD
Drop 10%
Drop 20%
Drop 30% Drop 10%
Drop 50%
INO-SGD
CF-PC 46.4 (0.53)
43.88 (0.77)
43.56 56 (0.99)
12.9 (1.67)
42.00 (1.88)
20. 72 (2.51)
48. 10.65)
CL-PC 63.35 (1.28)
62. 18.48 (1.74)
61.61 (2.31)
61.41 (3.31)
58.83 (1.11)
56.47 (5.06)
66. 73 (0.24)
Reducing less private owners' privacy budgets: Similar to the above, it is still unclear how to set the cutoff and how much privacy budgets to reduce from each less private owner. Moreover, this method under-utilizes the privacy budgets and data from the less private owners. Due to the privacy-utility tradeoff (Makhdoumi & Fawaz] 2013). the overall utility would be lower than our current baseline IDP-SGD which fully utilizes the privacy budgets of each owner. We validate the above in App. D.4.3] Note that this includes other methods like reducing less private owners' sampling rates in SAMPLE and clipping thresholds in SCALE.
D.2 ADDRESSING UTILITY IMBALANCE
In the main paper, Fig. (b) and (c) are under the MN-PC, CL-PC and CF-PC setting respec- tively; Fig. a) and (b) are under the CM-PC and CH-PC setting respectively.
In Fig. 10 we present more experiments under various settings and more complex models (c.g.. SU-LS, CM-RN, CM-SC) that illustrate how INO-SGD still addresses utility imbalance induced by IDP-SGD. In particular, for experiments with more data owners (e.g., CH-PC), we show 3 or data owners whose privacy preferences range from low to high for a clearer visualization. We note the following points:
Fig. 10(a) (d) are real-world clinical datasets where owners of (likely) positive-case data have stronger privacy requirements, which reinstates our motivation that utility imbalance is undesir- able for subsequent users of the trained ML model.
Fig. [0h) considers each category as group since each owner's data contain label noises.
shows that INO-SGD's performance is robust to label noises.
Fig. [0(q) and (r) consider possible real-world settings where each data owner only possesses datum and can choose its own privacy budgets. Owners who possess sensitive data can generally prefer stronger privacy but have small variations among themselves. The two results show that
INO-SGD is still effective under such settings.
Fig. 10(s) and it) consider possible real-world settings where occasionally sensitive data have weaker privacy requirements and vice versa. The two results show that INO-SGD is still effective under such settings.
Remark. Similar to MNIST (MN-PC), Pneumonia and CIFAR-10 with extracted embeddings (PN- EF/CM-SC) are also relatively easy-to-learn tasks for which MID happens at an earlier stage of training. In contrast, in more difficuut tasks such as CIFAR-10 (CM-PC/CM-RN) and CIFAR-100 (CH-PC), privacy budgets are used up before MID even ends. This reinstates the importance of considering the entire learning dynamics and the benefit of our INO-SGD algorithm.
43

---

Published as a conference paper at ICLR 2026
IDP
Owner
Per geggroup loss
10-
IDP
Owner Owmer
Per wwr-ggmupe loss.
INC
IDP
Owner
Par-group
60
INO
Owner 2
Owner
Per-group
30
-6
2
IDP
Owner
500
1000
2000
3000
1000
2000
3000
iteraaionn
iterations
iterations
(a) CA-MLPP
(b) CA-MLP.
(c) PN-EN.
(d) PN-EN.
Par-grouup loss
INO Owner
Nur-graang recoun
60
TV sarinnnnn recal
60
130
20
IDP
Owner
IDP
Owner
IDP Cat.
Owner
75009375
iterations
No. of iterations
iterations
No. of iterations
MN-PC.
CF-PC.
(g) SU-LS.
(h) CFN-PC.
groug recall
160
Pece sarunn recail
50
%
Dener
Owner
86
Pesgroup:
Owner
Ovvner
10
20-
Owner Owner
20
Owner Owner
Owner
Owner 3
Owner
1000
2000
3000
1000
2000
3000
1000
2000
3000
1000
2000
3000
No. of iterations
No. of Iterations e
No. of Iberations
No. of iterationn t
CM-PC 5,
CM-PC 03, 6,9.
(k) CM-PC 01, 4,7, 10.
() CL-PC 01, 9.
group %
Pecgroup %
IDP
Per wwg.gouupppp loss
per group loss
IND
10
60-
22 w
IDP
20
300
Owner
Owner
Owner
2000
4000 6000 B000
6
2000 4000 6000 8000
10
100
2000
10
100
2000
No. iterations
No. of iterations
No. iteraaions
No. of iterations
(m) CM-RN 02, 5, 8.
(n) CM-RN O3, 6,9. 9.
(0) CM-SC 03, 7.
CM-SC O2, 9.
%
Pergroup recall
preggrup paggguupreer reall
Sue 88
86 &
moce 8
Group
Group
40.
Group
Group
Group
Group
8
Group
Group
20
20
38
IDP
Cat.
1000
2000
No. of itteraiions
iterations
No. Iterationn
(q) O1,
(r) CFS-PC.
COL-PC 4, 7, 10. (t) COM-PC 01, 4, 10.
11e20u dioio
50-
Por group
20
76
98
1000
2000
3000
1000
2000
3000
1000
2000
3000
No.
iterations
No. of Iterations
No. Iterationn
(u) CH-PC 024, 50, 76.
(v) CH-PC 031, 63, 95.
(w) CH-PC 022, 58, 98.
Figure 10: Comparison of per-owner model utility between IDP-SGD and INO-SGD. Here 02, 5, 8 refers to Owners 2, and and likewise for the others. INO-SGD consistently improves the model performance for the more private data owners while sometimes conservatively lowering the performance for the less private data owners. general, it results more balanced learning dynamics.
44

---

Published as a conference paper at ICLR 2026
90
Warstggruu scc.
Worzz Worst-gmaug gen-ggguuppp acC
60
Whrrs gmoup ace.
30
23-
440
60
20
26
I0P
IDP
INO
160
300
500
1000
2000
3000
2500
5000
9300
2000
4000
Iterations
(a) CA-MLP.
(b) PN-EN.
(c) MN-PC.
(d) CF-PC.
Worst-gree ICC.
Worst-graa grouggrouppp acc.
16
40
group
12
20
IDP
Cat
IDP
IND
2000
3000
No. Ieerations 2
No. of iterations
No. Iteratiins
No. of Iterations
(e) SU-LS.
(f) CFN-PC.
(g) CM-PC.
(h) CL-PC.
Worst-grau gert-grruupoo acc.
200
IDP
INO
Words Worst-grroup acc.
g
Worst-group
60-
-0.
Worst-group
20.
25
10
IDP
IDP
IN
IDP
INC
2000 4000 6000
8000
10
300
2000
1000
2000
3000
2000
4000
No. iterations
No. of iberattonn
No.
Iterations
No. of Itorations
(i) CM-RN.
(i) CM-SC.
(k) CS-PC.
(l) CFS-PC.
Worztgrropp scc.
Mo00 20 BCC.
IDP
INO
20
20
-0
1000
2000
3000
1000
2000
3000
1000
2000
3000
No. of ittratioon
No.
iteration
Mumb or of Iterations
(m) COL-PC.
(n) COM-PC.
(0) CH-PC.
Figure 11: Comparison of worst-owner accuracy between IDP-SGD and INO-SGD. INO- SGD consistently improves the model performance for the most private data owners and thus ad- dress utility imbalance.
45

---

Published as a conference paper at ICLR 2026
INO 1DP accal
training
trainingg
traminn
trainingg
Privacy budget
Privacy budget
(a) CR-PC.
(b) CR-PC.
Figure 12: INO-SGD's per-group utility minus IDP-SGD's. Model utilities for the more private owners show higher increase.
Another way assess utility imbalance is through the worst-group accuracy (i.e., the accuracy of the worst group(s) at different stages of training). In Fig. 11 we demonstrate that INO-SGD con- sistently improves the worst-group accuracy over IDP-SGID. Specifically, for CH-PC (Fig. [[d]), we show the average of the worst 50% owners due to large number of small privacy budgets and difficult classes.
In Fig. 6 we repeat the experiments in Fig. (graphs of changes in model performance from IDP- SGD to INO-SGD against different privacy budgets) on the CR-PC setting, where each of the 10 data owners has fixed privacy budget but receive madomly sampled class in each random run. This could eliminate the impact of inherent different in class complexities. We can see that INO-SGD still effectively improve the utility on the more private owners.
D.3 PRESERVING OVERALL MODEL UTILITY
In the main paper, Fig. tively.
a
L and (c) are under the MN-PC, CL-PC and CF-PC setting respec-
In Fig. 13 we present more experiments that illustrate how INO-SGD improves/preserves overall model utility as compared with IDP-SGD. In particular, we use balanced accuracy for the Surnames dataset (SU-LS) and Cardiotocography dataset (CA-MLP) since their validation sets are highly imbalanced. It can be seen that INO-SGD demonstrates the same trends under the various settings noted in App. D.2
D.4 OTHER EMPIRICAL BENEFITS AND DISCUSSIONS
In this section, we demonstrate and discuss several other benefits of INO-SGD.
D.4.1 BETTER WITHIN-OWNER LEARNING DYNAMICS
We notice that the learning curve within a single data owner is not smooth and demonstrates certain fluctuations when it holds several different groups of data. In real life, this represents groups with data of different distribution but similar privacy preferences (e.g., two types of one stigmatized disease). To investigate it, we analyze the per-class recall for different classes within the same data owner in MN, SU and CF and show it in Fig. [4] Although classes/groups belonging to the same data owner share the same privacy budget, they may have different learning complexities and hence different learning dynamics and duration of the MID effect. For example, in Fig. [4(c) Class O much easier learn than Class (possibly because 0 has more distinguishable shape). Thus, the MID effect of Class O (around iteration to 100) is much shorter than that of Class 3 (around iteration to 3000).
This experiment also demonstrates another benefit of INO-SGD: it also improves the learning dy- namics of different groups within the same data owner. This is because an easy-to-learn group within private data owner can also be learnt fast and its loss will decrease quickly. Samples from such group will then be wown-weighted by the INO-SGD algorithm so that we can focus more on reduc- ing the loss for the more difficult samples from the private data owner. For example, in Fig. [4(c) again, the MID effect with regards to class 3 is significantly improved under INO-SGD (shortened to around iteration 0 to 1500). This shows that IND-SGD not only address IDP-induced utility
46

---

Published as a conference paper at ICLR 2026
IDP INO
Validetion loos
8
Validaation loss.
6
Vollitation
80
2V
30-
20
IDP
INO
10
100 200 300
400
500
6
100 200
300 400
500
1000
2000
3000
1000
2000
3000
No. iterations
No. of iterations
iterations
No. of ittrratoons
(a) CA-MLP accuracy.
(b) CA-MLP loss.
(c) PN-EN accuracy.
(d) PN-EN loss.
20
Validation scc
Valldaation loss
Validation acc:
50.
Balanced
20
25
IDP
IND
IDP
IND
IDP
IND
5000
2000 (f) CF-PC loss.
2000
iterations
(e) MN-PC accuracy.
SU-LS accuracy.
CFN-PC accuracy.
Validation acc.
Welidation loss.
IDP
IND
50-
Velldation loos:
IDP ING
Validation
IDP
INO
IDP
IND
1000
2000
1000
3000
2000
4000 6000 8000 Iterations it
2000 4000 6000 8000
No. Iterations
No. of Iterations
No. iterations
CM-PC accuracy.
CL-PC loss.
(k) CM-RN accuracy.
CM-RN loss.
90
Valdation ace
Validtion acc.
Validetion acc
60.
40
80
Validation
60
20
20-
80
IDP
+
INO
IDP
IND
IDP
IND
IDP
INC
10
2000
1000
3000
2000
3000
1000
3000
iterations
No.
iterations
No. iterations
No. of iterations
(m) CM-SC accuracy.
(n) COL-PC accuracy.
(0) COM-PC accuracy.
(p) CH-PC accuracy.
Figure 13: Comparison of overall model performance between IDP-SGD and INO-SGD.
INO-SGD consistently improves the overall model performance.
Panciass recall
80
90
+
Class
Par-class rccall
60-
75
60-
IDP
Class Class
50-
40-
Pen-caass
IND
3
Percetanc
INO
20
Class
30-
IDP Class
0. 24
7:
2500 5000 7500 9375
500
1000
2000
4000
2000 No. of iterations
4000
No. of itteration
No. of itterations è
No. of itteratins
(a) MN-PC 01 C2, 4.
(b) SU-LS 01 C7, 10.
(c) CF-PC 01 CO, 3.
(d) CF-PC 01 C6
Figure 14: Per-class learning dynamics within data owner. Here 01 C2, refers to Owner Classes 2 and and likewise for the others. Different classes within data owner are learnt with different dynamics. INO-SGD improves such within-owner learning dynamics too.
47

---

Published as a conference paper at ICLR 2026
imbalance, but also mitigate the inherent imbalance caused by different learning complexities among groups.
D.4.2 COMPONENTS OF INO-SGD
The INO-SGD algorithm has main components: the TIF and the ordering of data used. In this section, we conduct ablation studies by removing/varrinn each component to assess its impact. In (I) to (III), we demonstrate that TIF is important. Moreover, INO-SGD is robust the choice of hyperparameters so that it is easy for practitioners to apply it in real life. As mentioned in Sec. 3.2 the hyperparameters of TIF fuit include the tail length y and the form of fuil. Therefore, we run the INO-SGD algorithm using different values of 7, parameters o and B of Beta distribution and also try different function forms such as the step function mentioned App. app.(c.2.5)
(IV), we verify benefit of using descending order of loss by comparing it with a random and an ascending order of loss.
(I) Tail length, In Fig. 15| we show how the learning dynamics change as we change the tail length y, It can be seen that in general, INO-SGD shows an improved learning dynamics when we set to be less than half of the expected sum of clipping thresholds calculated by ΣmE(N DDalgn On (which equals around 256 for CIFAR- 1V0-FV (CF-PC) and 1987 for CIFAR-10 (CM-PC)). If set y to be even larger, there will be too little good information left the batch and the summed gradient will get more noisy due the added Gaussian noise. It will start trading overall utility for better balance.
Volidation acc.
2/4
1/4
4/4
3/4
60
Owmer
Owner 2
Vollic Vollidation azc
2/4
1/4
4/4
3/4
80
Owner
80
20
200
250
200
600 length
1000
1500
2.0
600
1000
1500
length y
length
length Y
(a) CF-PC overall. (b) CF-PC 01, (c) CM-PC overall.
(d) CM-PC 02,9. 9.
Figure 15: INO-SGD robust to choice of ? for a limited range. After that, it starts trade overall utility for better balance. In particular, we plot the model performances at 1/4, 2/4, 3/4, and 4/4 of the entire training stage (in terms of iterations). For the CIFAR-10 dataset, we only show data owners for better visualization.
(II) & and B Beta distribution. In Fig. 16 we show how the learning dynamics change as we change the value of and B in Beta distribution when we set the tail importance function fun- All choices of a and ß enable INO-SGD to produce better learning dynamics than IDP-SGD. Specifically, when is smaller and is larger, INO-SGD will become more and more similar to IDP-SGD because fewer gradients are downtweighted.
50
IDP
2/4
4/4
Owner 1/4 3/4
I0P
1/4
3/4
Vallection acc.
45
Owner 2
2/4
4,4
Valksation acc.
55
2/4
80-
1/4
2/4
Pancroup
60
40
80
50
Owner
4/4
85
40
30
20
133.31
12.31
(4.03
133.31 12.31 5,621
Baa Cis aNo is 2200 Eucro mie
Deta
gerameters
(a) CF-PC overall.
(b) CF-PC 01,
(c) CM-PC overall.
(d) CM-PC 02,9.
Figure 16: INO-SGD is robust to the choice of a and ß if the length of the tail is chosen adequately. The dashed line represents our baseline IDP-SGD. In particular, a small x and large B will cause INO-SGI's performance to be similar to IDP-SGD and vice versa.
(III) Alternative TIF forms. In this section, we consider the alternative function form of tail importance function fuils a step function, as described in App. C.2.5) Specifically, we use 4 steps with constant step length (i.e., instead of setting 7, a and B, we only need to set the constant step length now). We vary the value of the constant step length to see whether our observed trends are still relevant when this alternative function form. The results shown in Fig. 17 and in
48

---

Published as a conference paper at ICLR 2026
particular, recover IDP-SGD when set the step length 0. It can be seen that long choose a reasonable step length (one that is not too long, or more precisely the sum of four steps should not exceed half of Σ e (nll9n C2 (same how choose Y previously)), we can get can conclude that INO-SGD is robust
better learning dynamics than IDP-SGD. Therefore, to the choice of tail importance functions as long as we choose a reasonable tail length 7, We still recommend using the TIF based on Beta distribution because it provides a flexible range of TIF shapes using only two parameters.
50
1/4
3/4
Owner 1
1/4 3/4
1/4
3/4
Volidation azc.
45
60
Owner
Vollidation acc.
55
80-
60-
1/4
24
-5
40
Per-group
40
50
Par-group
40
Owner
Chunee 9
4/4
3/4
30
20
100
length
Step lengthh
length
Step length
(a) CF-PC overall.
(b) CF-PC 21,
(c) CM-PC overall.
(d) CM-PC O2,
Figure 17: INO-SGD is robust to forms of the tail importance function fuil- In this set of experiments, we use the step function with constant step length as described in App. App.(C.2.5) 1/2 for the first step length, 1/4 for the second step length, 1/8 for the third step length, and for the last step length. Similar trends to our main experiments can be observed.
(IV) Impact of order. In Fig. 18 we show the benefit of using descending order of loss by replacing it with (1) random order (INO (random)) and (2) a reverse (ascending) order (IN) (reverse)). The overall results Fig. [8[a] the per-owner results Fig. [8(b] Jnd Fig. ] all show that a descending order is crucial, which justifies our argument that the loss values indicate the importance of data. particular, using a descending order loss not only benefits the performance of the more private data owners (e.g., Owners and 2), but also benefits the performance of the less private data owners (e.g., Owners and 8) because the more difficult data within them are assigned higher importance too.
Volidation
50
IDP (random) IND
(recerse)
S Owner
1000
2000
3000
1000
2000
3000
1000
2000
3000
No. kerations
No of iterations
No. of iterations
(a) CM-PC overall.
(b) CM-PC O2,
(c) CM-PC 01, 7.
Figure 18: Benefit of using descending order of loss.
D.4.3 PARETO SUPERIORITY
Beyond the region where the model owner can simultancously correct utility imbalance and im- prove/preserve overall model utility (which only INO-SGD can achieve), the model owner can also choose set the TIF more aggressively (e.g., downweighting more of the less important gradients by setting a larger tail length 7) in order to trade overall utility to further correct for utility imbal- ance. In this use case, method A is said to Pareto-dominate method B if any level of overall utility, method A corrects for utility imbalance better than method B; at any level of utility imbal- ance, method A achieves higher overall utility than method B. In Fig. 19 we demonstrate that INO-SGD Pareto-dominates naïve methods that satisfy IDP. In particular, we control the INO- SGD's tradeoff by using different tail length Y, and consider the baseline where every data owner decreases their privacy budgets proportionately (e.g. by 10%, 20%, 30%, 40%) to match the most private owner, and we use the standard deviation across per-group recalls to measure utility imbal- ance. Just as the privacy-utility tradeoff (Makhdoumi & Fawaz] 2013) describes, decreasing privacy budgets would incur lower overall utility. so such methods cannot achieve dual improvement in both utility balance and overall utility as INO-SGD achieves. Even if the model owner is willing to trade some overall utility to further correct for utility imbalance, INO-SGD is a better solution because of its Pareto superiority.
49

---

Published as a conference paper at ICLR 2026
Unilit inbalance
24
IND
12
IDP-GGD
Unility Imbalannee
25
20-
20
26
DP-500
1r
INO
35
40
45
48
50
52
54
Overall utiltyy
Overall unility
(a) CF-PC.
(b) CM-PC.
Figure 19: Pareto superiority of INO-SGD. denotes IDPSGGD and denotes DP-SGD using the strongest privacy. * shows reported results where the model owner attains the largest dual improvement in both utility balance and overall utility. The red arrow indicates that INO-SGD Pareto-dominates any method whose tradeoff eurve lies to the upper left of INO-SGD's including the simple baseline. Therefore, INO-SGD offers the model owner a superior way to control the tradcoff between utility imbalance and overall model utility.
Remark. The reverse C-shaped region the right of INO-SGD's tradeoff curve indicates the bustness of INO-SGD discussed App- [D.42] in this region, the model owner can correct for utility imbalance without sacrificing any overall utility.
D.4.4 COMPATIBILITY WITH ADAPTIVE CLIPPING
In App. C.1.2, we note that adaptive clipping methods (Bu al. 2023 Xia al., 2023 would further lengthen IDP-induced MID because they make Cond. 2 more difficult to be satisfied, thus worsening IDP-induced utility imbalance. Fig- 20 verifies this and demonstrates that INO-SGD works effectively to address utility imbalance when using adaptive clipping, since INO-SGD can effectively mitigate MID.
Valicstion acc
.40
Peregmuu vecall
75
Validation
50
Owner
Owner
Owner
Owner
Owper
Owner
IDP
INO
1000 Rerations
2000
3000
2000
1000 Ittrattonn
2000
(a) CM-PC overall.
(b) CM-PC overall.
(c) CM-PC 01, 10.
(d) CM-PC O3, 6,9.
Figure 20: INO-SGD is highly compatible with adaptive clipping. (d) shows that for adaptive clipping Owner 3 suffers from MID till the end, which verifies our theoretical analysis that adaptive clipping could lengthen IDP-induced MID. Since INO-SGD addresses MID and utility imbalance, it significantly improves the performance of such methods.
D.4.5
PRIVACY ASSESSMENT VIA MEMBERSHIP INFERENCE ATTACK
In Sec. 3.3.1 and App. C.3.I we theoretically present and prove the privacy guarantees of INO-
SGD. this section, we conduct the LiRA membership inference attack (Carlini et al. 2022 to empirically verify the privacy protection of INO-SGD.
We first give brief introduction the LiRA method. The goal of LiRA is to infer whether a given datum d is in the training set D (i.e., whether d has been used for training the target model A(D)).
Let M denote the larger pool of data which may or may not used for training. LiRA firstly trains many shadow models via A, each using subset of M, M M. For each trained shadow model A(M) and the target model A(D), LiRA then computes a confidence score for each datum from its corresponding output logits. Let 2x(d) on M. During the attack, for each datum d E M, we fit two Gaussian distributions Agi and A using the confidence scores (d) from shadow models trained with d (i.e., d E M) and shadow models trained without d (i.e., d & M) respectively. The LiRA score of d is then calculated using
M (d) denote d's confidence score from the model trained
Prz~Ayl (2 (D)
LiRA(d) Pre (2 = 2p (d)
50

---

Published as a conference paper at ICLR 2026
Intuitively, the LiRA score represents how different N2 is f If datum is really protected by (D)P,, then the LiRA scores between data used for training (d E D) and not used for training (d D) should be indistinguishable. Empirically, the true positive rate (TPR) and false positive rate (FPR) should be approximately equal to each other for every chosen threshold.
In this experiment, each using half of the data from each group. In Fig. 21 we show the receiver operating character- istic (ROC) curve of IDP-SGD and INO-SGD. We observe that the ROC curves are very close to the line TPR = FPR, which shows that INO-SGD indeed protects the data well. We also see the effect of IDP: for example, in Fig. 21(b] the ROC curve for the more private group with e is closer to the line TPR = FPR compared with that for the less prviate group with 5, which shows that the more private group indeed receives better privacy protection.
follow Boenisch et al. (2024) and train 512 shadow models via INO-SGD,
1.0
1.0
posiioe rate
Thue eositive refe
Tiue posilive ra
r-
r= 20
0.6
0.6
True posiives
0.6
0.6
0.4
0.4
0.4
00.4
0.0
0.0
0.0
0.0
0.0
044
0.6
088
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4 0.6
1.0
0.0
0.2
0.4
0.8
1.0
Faise posttive rate
False positive
positive rate
Faise positive rate
(a) CIFAR-100-FV IDP-SGD.
(b) CIFAR-100-FY INO-SGD.
(c) CIFAR-10
(d) CIFAR-10
IDP-SGD.
INO-SGD.
The privacy of INO-SGD is validated by LiRA membership inference attack. The AUROC for all owners are close to 0.5 and the ROC curves for IDP-SGD and INO-SGD are similar. The AUROCs for the more private owner (smaller and less private owner (larger e) are respectively (a) 0.571, 0.645, (b) 0.563, 0.663, (c) 0.569, 0.623, and (d) 0.563, 0.580 for the subfigures.
Figure 21:
E ADDITIONAL DISCUSSIONS
E. LIMITATIONS
In this section, we explain some possible limitations of the INO-SGD algorithm and discuss their causes and possible future directions.
Firstly, increasing the utility of more private owners might unavoidably reduce that of the less private owners. This is because we have to weaken the dominance of gradients from the less private owners in order to achieve Eq. mitigate MID and BOO, and address IDP-induced utility imbalance. The need for tradeoff is also considered in the Pigou-Dalton principle (Pigou 1912): if we want to improve the model utility for the more private data owners and hence make the utilities for all owners less imbalanced, private ones. To mitigate this limitation and control the tradeoff in the INO-SGD algorithm, the model owner choose the TIF function fuil according to their desired utility for each owner.
must transfer some resources from the less private owners to the more
Secondly, the INO-SGD algorithm can only reduce utility imbalance across data owners to a certain extent without harming the overall model utility. As shown in Fig. 15 and 19] when a more potent TIF function fua is chosen (i.e., TIF with longer tail 7), although the utility imbalance across all owners may be further reduced, the model utility for all data owners starts drop and so does the overall utility. This can be explained by the IDP-balance-utill utility tradeoff elaborated in App. E.2 for the same IDP requirements, there exists tradeoff between overall utility and utility balance. The INO-SGD algorithm is closer to the Pareto frontier of the tradeoff than IDP-SGD, because within certain range INO-SGD simultaneously improves both overall utility and utility balance. To mitigate this limitation, the model owner again choose the TIF function fual carefully.
Thirdly, in this paper, we do not provide theoretical guarantees on how much model utility can be improved for each data owner without harming the overall utility. This requires theoretical analysis of the le-balacce-utlifyy tradeoff which is highly non-trivial and beyond the scope of this paper. Future work can theoretically characterize the Pareto frontier of the IDP-balance-uuill find Pareto-optimal solutions. On the other hand, the theoretical scope of this paper is to analyze the cause and impact of IDP- induinduedd utility imbalance identify (Sec. 3.1 and App. C. and provide
tradeoff and
51

---

Published as a conference paper at ICLR 2026
the privacy and objective analysis of the INO-SGD algorithm propose (Sec 3.3 Nevertheless, our experiments in Sec. Band App. Demmonstrate the empirical benefits of our INO-SGD algorithm over IDP-SGD.
E.2 THE
TRADEOFF
Our experiment has shown that INO-SGD achieves a better learning dynamics than IDP-SGD but it seems that the improvement is somewhat limited (i.e., it does not result in equal performance for every data owner), which seemingly makes our contribution limited. However, in this section, we will briefly discuss the IDP-balance-utee performance for every data owner without loss of overall model utility.
tradcoff and justify why it is not possible to achieve equal
The disparate impact of DP (Bagdasaryan al., 2019) has been well-known drawback that limits the performance of DP-ML models. refers to the phenomenon that DP-ML models give much lower accuracy for underrepresented groups in the training set, and is known be unavoidable due to the nature of DP: since we need to protect the privacy of every datum, we cannot specially make the underrepresented groups identifiable. The only workaround is to undersample the over- represented groups and waste some of their privacy budgets, so as to achieve "similar utility" by giving the overrepresented groups much worse performance. This situation known as the privacy- disparity-utile utillity tradeoff. In IDP, the situation becomes even worse. In Sec. [3. we explain that even the original training set is balanced and there is no underrepresented group, IDP would forcefully create underrepresented groups because of the individualized privacy preferences. Therefore, we are tradeoff in IDP than vanilla DP.
expected to see worse
Our work successfully gets closer to the boundary of the ID--bllanc--utilityy tradeoff, because we are able to achieve better balance without losing the overall model utility. Nonetheless, we are tradeoff. In fact, contribution to the D--abaance-utilityy tradeoff. When the length tail y 100, we are achieving better balance without sacrificing overall model performance. This means that the original IDP- SGD does not hit the ADP--alaace-utille
still facing the
refer to Fig. [5(a) and (b) visualize our
tradeoff bound while our INO- does better. However, when the length of tail 7 2 100, although the utility imbalance is still decreasing, the overall model performance shows a rapid drop too. This where we reach our Pareto frontier and experience the DOP-balance-utilee uutiliy tradeoff.
F OTHER QUESTIONS
Why do we consider the individualized privacy setting? Why would each owner not choose the maximum privacy level?
Research (Berendt et al. 2005 Jensen et al., 2005) has shown privacy preferences can vary across different data owners. Moreover, data owners with more sensitive attributes (c.g., stigmatized discases, race) would prefer stronger privacy data leakage would expose them to discrimination or denial or services (Best & Arseniev-Koehle 2023 have provided several real life applications in App. A.2
Lai & Tanner 2022). We
However, choosing the maximum privacy level is undesirable: The privacy-utility tradeoff (Makhdoumi & Fawaz 2013) is well-studied and shows that using a stronger DP guarantees undesirably reduces the performance (utility) of the trained ML model. Thus, model owner would want to use each data owner's data at a weaker privacy to train a model with the highest utility. In some cases such as collaborative MI. (Sim et al., 2020 Tian et al. 2024), data owners are also the users of trained MI. models and hence they will choose the highest privacy budgets they find acceptable (e.g., when data owners are hospitals and the model owner a medical institute who trains an ML model to predict the risk of heart discase). In other case, model owners can incentivize data owners to choose the highest privacy budgets they find acceptable by rewarding each data owner based on their data values or privacy budgets (i.e., selecting higher privacy budget and weaker privacy will lead to more monetary compensation).
52

---

Published as a conference paper at ICLR 2026
2. Why is the problem of the utility imbalance (and improving the utility more private owners or difficult data) important?
As motivated in Sec. model owners need to collect data from multiple data owners in order to gather sufficient data train good MI model. Moreover, data owners with unique yet sensitive data would prefer stronger privacy, which is not desired by model owners as this would lead to low model utility on these unique data. For example, in healthcare ML applications, data owners with some rare disease are likely to demand strong privacy requirements. However, the goal of training such an ML model is precisely to predict these rare diseases well instead of predicting well for control patients without the diseases. Thus, the model owner should consider using INO-SGD to improve the utility on these more difficult examples and more private data owners.
What is the difference between this and other works that achieve group fairness?
Our goal differs significantly from group faimesss works as explained in App. B.3
4. Do we assume that MID and BOO always occur as a result of IDP-SGD?
No, we do not assume that they always occur. In Thm. 3.1 we theoretically analyze when MID and BOO will not occur and how to correct for it when they occur. Based on that, devise the INO-SGD algorithm.
However, we highlight that even for balanced datasets, MID and BOO can occur as a result of IDP requirements across different owners and theoretically prove it in App. C.1.2
5. In Sec. 4 why does the model achieve relatively low accuracy? Is this weaker than existing works?
We would like to highlight that our empirical results should be compared against IDP- SGD with same privacy budgets DP-SGD that maintains the smallest privacy budget for all owners to attain IDP. For example, the CIFAR-10 experiment where IDP-SGD achieves
50% overall accuracy Fig. [3() the most private owner has a small privacy budget 0.5. When privacy budget is larger (minimum 6), our accuracy also increases and reaches ~ 67% 7(b)
Similar accuracy to ours (e.g. < 60% for small <) in DP-SGD is common for CIFAR- 10 training
from scratch (Ganesh et al. 2023 Muthu Selva Annamalai De Cristofaro 2024 Wei et al.
2022). (Bu et al. 2022 Ganesh et al.) 2023 Lin et al. 2023 use pretrained models to achieve
high accuracy around 90% which we also show in Fig. 13(m) Notably, our work considers IDP
where follow-up works apply.
Besides privacy budget, the impact of data imbalance on model utility is important too. DP can potentially reduce accuracy underrepresented groups (Bagdasaryan al. 2019) and our work shows that IDP can cause it too. INO-SGD would address this data imbalance.
USE OF LLMS
We use LLMs to aid or polish writing such as checking grammar. The methodological contributions do not involve LLMs.
53


Reviews:
[{"review_id": "fhQKVM34Lh", "reviewer": "Reviewer_Tg2g", "summary": "The paper identifies a utility imbalance that arises when training with individualized DP (IDP): data owned by users with stricter privacy budgets (e.g., sensitive subpopulations) receives less effective learning, degrading their group utility even when dataset sizes are balanced. The authors analyze why IDP-SGD induces MID/BOO-style dynamics and propose INO-SGD, which (i) sorts per-batch examples by loss, (ii) constructs a tail importance function (TIF) and corresponding batch importance function (BIF) to assign importance weights, and (iii) scales clipped per-example gradients by these data-dependent weights without exceeding each owner’s clipping threshold, thereby preserving IDP guarantees. They prove IRDP privacy with the same accounting as IDP-SGD and show that INO-SGD can obtain gains on MNIST, CIFAR-10/100, improving the more private groups’ recall while preserving or improving overall accuracy.", "questions": "Refer to the weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+ The paper clearly identifies and analyzes a practical failure mode of IDP training, showing how stricter privacy budgets systematically depress group utility even without data imbalance.\n\n+ The proposed method preserves individualized DP guarantees without additional privacy cost, because it reweights only after clipping and uses the same accounting as IDP-SGD.\n\n+ The experimental results consistently improve performance for highly private users while keeping or improving global accuracy, demonstrating that the approach meaningfully reduces utility imbalance in practice.", "weaknesses": "- The empirical evaluation lacks breadth against strong IDP-compliant alternatives, as it focuses mainly on vision benchmarks and does not compare to a wider set of within-IDP reweighting or sampling schemes.\n\n- The method provides limited guidance for selecting the importance-function hyperparameters, leaving open how to tune them or manage trade-offs across privacy groups in real deployments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "deKlufcYMN", "reviewer": "Reviewer_WnuE", "summary": "The paper studies utility imbalance under individualized differential privacy (IDP). It shows that even on balanced datasets, IDP-SGD (SAMPLE/SCALE) can disadvantage owners (or groups) with stricter privacy (smaller ε) by creating MID (minority initial drop) during training and BOO (biased optimization objective) at convergence. To mitigate this, the authors propose INO-SGD, which (i) sorts per-batch examples by loss, (ii) uses a Tail Importance Function (TIF) to define a Batch Importance Function (BIF), and (iii) rescales clipped gradients by per-rank importance scores before adding Gaussian noise—while keeping each datum’s modular sensitivity bounded by its individualized clipping threshold, thereby preserving IDP.", "questions": "Please check the weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The problem framing is clear. IDP can itself create imbalanced learning dynamics (MID/BOO) even when class counts are balanced. This problem actually step away practical DP deployment.\n\nThe intuition makes sense. To my understanding, it aims to increase the sensitive users' utility by trading off some non-sensitive users' utility. Meanwhile, the loss-ordered importance scheme is designed to not increase per-datum sensitivity (keeps ΔA^d ≤ Co(d)) while re-weighting gradient contributions.", "weaknesses": "The narrative argues standard class-imbalance fixes don’t satisfy IDP or get neutralized by clipping (oversampling/weighting/rescaling), but empirical comparisons with IDP-compliant alternatives are missing.\n\nClaims rest on formal sensitivity bounds and RDP accounting; there’s no auditing checking if per-owner attack success (e.g., per-group LiRA, TPR/FPR rates) still meet TPR/FPR<=exp(ε). Though formal analysis makes sense, using auditing to check if there is any bug in implementation is also important.\n\nThe main figures emphasize per-group recall and validation loss/accuracy. To assess “imbalance”, measures like worst-group accuracy should be reported directly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "jYEJWVpaQb", "reviewer": "Reviewer_mPUX", "summary": "This paper introduces the novel problem of **utility imbalance** caused by individualized differential privacy (IDP). In IDP, each data owner specifies their own privacy level, which offers flexibility but leads to uneven model performance across owners with different privacy budgets. The authors propose **Individualized Noisy Ordered SGD (INO-SGD)**, an algorithm that **adjusts the weighting of data within each batch** to improve outcomes for owners with stricter privacy requirements while maintaining the same privacy guarantee as standard IDP-SGD. Through extensive experiments, the authors demonstrate that INO-SGD enhances the utility of more private groups, effectively mitigating utility imbalance, while maintaining or even improving overall model performance.", "questions": "See the Weaknesses section, please.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**1. Novel and Important Problem Identification:**\nThe paper introduces the new problem of utility imbalance under individualized differential privacy. It shows that while IDP gives users control over their privacy, existing algorithms unintentionally penalize those with stronger privacy. Its focus on how varying privacy budgets create uneven model performance highlights an important direction for future research in differential privacy.\n\n**2. Strong Theoretical Justification and Clear Presentation:**\nThe paper provides a well-structured and convincing theoretical motivation for the identified problem. By connecting the imbalance to sampling rates and clipping thresholds through concepts like Minority Initial Drop and Biased Optimization Objective, it offers clear mathematical insight into the cause of the issue. Theorem 3.1 and its supporting proofs further reinforce the soundness of the argument.\n\n**3. Comprehensive Empirical Validation:**\nThe experiments are extensive and well-executed, covering a diverse range of datasets, models, and privacy settings. The results consistently show that INO-SGD improves the performance of more private groups, effectively mitigating utility imbalance, while maintaining or even enhancing overall model utility.\n\n**4. Novel and Well-Designed Mechanism:**\nThe idea behind INO-SGD is to down-weight less important data within each batch to improve performance on more private data throughout training. This approach is practical and broadly applicable, with potential use in learning problems that involve fairness or group balance.", "weaknesses": "**1.** In some parts, the paper’s wording seems to overstate the performance gains of INO-SGD. For example, lines 444–446 claim that *Across training stages, INO-SGD significantly increases the recall on validation data groups associated with more private owners (left) at the expense of a **small decrease** in the recall on less private ones (right).* However, from Figure 6, it appears that for larger $\\varepsilon$ values (less private owners), IDP-SGD clearly outperforms INO-SGD, and the performance drop for these groups is roughly equal to the gain for more private ones. Additionally, Figures 5 and 7 use validation loss as the utility metric for the MNIST dataset, while recall/accuracy are used for CIFAR-10 and CIFAR-100-FV. Is there a specific reason for this inconsistency? If not, I would suggest using a consistent evaluation metric across datasets for clarity.\n\n**2.** The paper states that INO-SGD guarantees the same privacy level as IDP-SGD (Theorems 2.2 and 3.3). While the paper mentions that INO-SGD consumes privacy budgets at the same rate as IDP-SGD, and therefore maintains the same number of training iterations, it remains unclear why the two methods have exactly the same privacy guarantee at **each iteration**. For instance, INO-SGD involves computing the Batch Importance Function (BIF) from $f_{\\text{tail}}$ and $B_t$, as well as sorting losses—operations specific to INO-SGD. Could the authors provide more intuition or justification for why these additional computations do not affect the per-iteration privacy guarantee?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)