Conceptio › Archive › arXiv CS

arXiv CSopen access

Integrating Feature Correlation in Differential Privacy with Applications in DP-ERM

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

neural-networks

machine learning, deep learning, neural networks

Integrating Feature Correlation in Differential Privacy with Applications in DP-ERM Tianyu Wang∗

Luhao Zhang†

Rachel Cummings‡

arXiv:2605.03945v1 [cs.LG] 5 May 2026

May 6, 2026

Abstract Standard differential privacy imposes uniform privacy constraints across all features, overlooking the inherent distinction between sensitive and insensitive features in practice. In this paper, we introduce a relaxed definition of differential privacy that accounts for such heterogeneity, allowing certain features to be treated as insensitive even when correlated with sensitive ones. We propose a correlation-aware framework, CorrDP, which relaxes privacy for insensitive features while accounting for their correlations with sensitive features, with the correlations quantified using total variation distance. We design algorithms for differentially private empirical risk minimization (DP-ERM) under the CorrDP framework, incorporating distance-dependent noise into gradients for improved theoretical utility guarantees. When the correlation distance is unknown, we estimate it from the dataset and show that it achieves a comparable privacy-utility guarantee. We perform experiments on synthetic and real-world datasets and show that CorrDP-based DP-ERM algorithms consistently outperform the standard DP framework in the presence of insensitive features.

Introduction

The growing reliance on personal data in domains such as economics and healthcare has amplified the need for privacy-preserving algorithms. Differential Privacy (DP, Dwork [2006]), which enforces a worst-case bound on privacy loss, ensures that the output of an algorithm does not depend significantly on any single data point. As a result, DP has become a standard methodology for safeguarding privacy during analysis of sensitive data. However, traditional DP assumes that all features of an individual’s data are equally sensitive, often leading to overly conservative privacy-utility trade-offs in practice. In many real-world applications, feature sensitivity can vary, where some are highly sensitive (e.g., health status) and other are less so (e.g., age group). However, these features are often correlated. Consider a healthcare dataset containing both a patient’s blood pressure readings and age. Blood pressure measurements, which can reveal medical conditions, are more sensitive, while age may be less sensitive if presented in broad categories (e.g., age groups). However, these features are often correlated—age influences typical blood pressure ranges. Applying a uniform privacy mechanism that disregards these distinctions can lead to excessive information loss and suboptimal utility. Adding equal noise to both features also overlooks their correlation, distorting the dataset more than necessary. Recent semi-sensitive DP approaches [Shen et al., 2023, Ghazi et al., 2024] address such distinctions by treating some features as private (e.g., blood pressure) and others as public (e.g., age). However, this approach risks privacy violations because revealing age can expose the conditional distribution of blood pressure, undermining its privacy. An ideal privacy mechanism would therefore account for such correlations by robustly protecting the sensitive measurements while adding minimal noise to less sensitive but correlated features. ∗ Department of Industrial Engineering and Operations Research, Columbia University. Email: [email protected]. † Department of Applied Mathematics and Statistics, Johns Hopkins University. Email: [email protected].

‡ Department of Industrial Engineering and Operations Research, Columbia University. Email: [email protected]. Supported in part by NSF grants CNS-2138834 (CAREER) and EEC-2133516.

Empirical Risk Minimization (ERM) is among the most fundamental and well-studied problems in privacy-preserving machine learning [Chaudhuri et al., 2011]. The goal of ERM is to find the best parameter θ ∈ Rm of a (convex) loss function to minimize empirical risk given a dataset D of size n; privacy of the output parameter is often achieved via incorporating noise into the gradient when conducting gradient descent at each step, i.e., DP-SGD [Abadi et al., 2016, Wang et al., 2017]. In the standard (ϵ, δ)-DP setting, √ DP-ERM algorithms achieve a minimax optimal utility guarantee Õ ( m/(nϵ)). While this utility guarantee is theoretically minimax optimal [Bassily et al., 2014], this guarantee can be overly conservative, particularly in high-dimensional settings with few sensitive features, as DP-SGD applies uniform noise to all dimensions. In this work, we investigate whether relaxing the DP definition can improve the privacy-utility tradeoff, particularly in datasets with features that are known to less sensitive. Specifically, we aim to answer: (1) What is an appropriate privacy mechanism for datasets with insensitive features that may be correlated with sensitive features? and (2) How much can a relaxed notion of differential privacy improve the privacy-utility tradeoff? To address these questions, we design a privacy framework and mechanisms that consider the correlation among features while ensuring rigorous privacy and utility guarantees. Contributions. Motivated by the limitations of standard DP and practical applications where not all features are equally sensitive, we propose a new correlation-aware differential privacy framework (CorrDP). Our framework leverages feature correlations to achieve improved utility guarantees with modified algorithms, including extensions of both the standard Laplace mechanism and DP-ERM. In particular, our contributions are as follows: 1. New Frameworks Incorporating Feature Correlation in DP: We introduce CorrDP, a new DP notion incorporating feature correlations in the privacy constraint between neighboring databases. This notion offers a natural way to quantify correlations between sensitive and insensitive features, and collapses to the standard DP definition when all features are sensitive. It seamlessly integrates probability distances such as total variation distance, and standard mechanisms like the Laplace mechanism can be adapted to fit within this framework. 2. Improved Privacy-Utility Tradeoff in DP-ERM: We apply CorrDP into DP-ERM and design corresponding CorrDP-SGD algorithms that incorporate distance-dependent noise for loss functions satisfying certain smoothness properties (see Assumption 3.4), which includes generalized linear models. Our theoretical results showpthat CorrDP offers an improved privacy-utility tradeoff, providing a utility improvement by a factor of m/ms under mild conditions, when ms features are sensitive. 3. Distance Estimation: When the correlation distance is unknown at the time of noise addition, we propose an estimation procedure that uses an upper confidence bound for the empirical estimate. This procedure, integrated within the CorrDP framework, eliminates the effects of both estimation and sensitivity errors while maintaining the same level of privacy-utility performance. 4. Empirical Evaluation: To demonstrate the practical utility of distance estimation and the CorrDP framework, we conduct experiments using both synthetic and real-world datasets. Our experiments confirm that using CorrDP achieves better accuracy for the same fixed privacy budget.

1.1

Related work

Relaxations of DP. Recent studies consider relaxations of DP to achieve better privacy-utility tradeoffs, especially for ERM. When relaxing the DP notion at the feature level, Ghazi et al. [2021] considered label DP, which protects only the labels rather than the entire feature set. This is a special case of the notion called semi-sensitive DP, where the feature domain includes both sensitive and insensitive features [Chua et al., 2024]. Under such a setup, Shen et al. [2023] designed a specific boosting algorithm for linear classification, while Ghazi et al. [2024] investigated the general DP-ERM problem when the sensitive domain size is finite. Empirically these relaxations have been successfully applied to vision [Shi et al., 2022] and language [Schneider et al., 2024] tasks without utility guarantees provided. In general, all these methods often rely on strong 2

assumptions about the independence between insensitive and sensitive features. On the other hand, metric DP [Andrés et al., 2013, Zhao and Chen, 2022, Imola et al., 2022] relaxes the standard DP notion under a general metric space. However, no prior work in the metric DP framework studied the possibility of capturing correlations between features for improved utility guarantees for DP-ERM. (See Appendix B.1 for more discussion.) In contrast, our CorrDP notion specifies this by incorporating feature correlations with different sensitivity levels for general ERM losses, while allowing infinitely sensitive domains. Besides feature-level relaxations, other work incorporates the heterogeneity of elements within the data domain to relax privacy constraints. These relaxations include distance in entry pairs [Acharya et al., 2020], task-aware latent representation [Cheng et al., 2022], and graphs of data generating distributions [Geumlek and Chaudhuri, 2019]. All these relaxations operate under local DP without a trusted data collector, compared to our setup under global DP [Dwork, 2006]. Utility Improvements in DP-ERM. In the context of DP-ERM, other utility improvements arise from public data or better gradient geometry. When the loss in DP-ERM is convex with the feature √ function dimension m, the minimax optimal utility guarantee Õ nϵm can often be improved by relaxing certain conditions, typically through adaptive gradients and/or the use of public data. When the gradient lies 1 in a low-dimensional subspace, the utility bound can be improved to Õ nϵ [Zhou et al., 2020]. In more general settings where better gradient geometry is available, the private adaptive gradient method can further enhance utility. For example, Asi et al. [2021] introduced non-isotropic noise into the gradient, while Li et al. [2022] utilized side information as a preconditioner √ to adapt to the gradient geometry. These approaches c both achieve a better utility rate Õ( nϵ ) with c ≪ m. When incorporating public data into training, Alon et al. [2019], Lowy et al. [2024] gave information theoretic utility lower bounds depending on the number of public data point. As highlighted in Section 4, our utility improvements are achieved by leveraging a refined noise scale that accounts for feature correlation with a reasonable privacy condition. This approach does not fundamentally rely on the availability of public data or assumptions about gradient geometry, and can be further improved when some favorable conditions, such as low-dimensional subspaces or improved gradient geometry, are present. Correlated Data. Correlation between entries in the database may cause unexpected privacy issues. As discussed in Kifer and Machanavajjhala [2011], one of the challenges when releasing correlated datasets is tuning noise to balance the privacy-utility tradeoff. Song et al. [2017] proposed Pufferfish privacy, which is a generalization of DP and handles correlated entries. Zhang et al. [2022a] provides a discussion on the correlated data in DP. To the best of our knowledge, all these works focus on correlation between individuals rather than features. Zhang et al. [2022b] introduced attribute privacy for sensitive features, extending Pufferfish to allow feature correlations. Their approach protects privacy at the dataset- or distribution-level, whereas our framework focuses on the individual-level. (See Appendix B.1 for a more detailed discussion.) Chaudhuri and Courtade [2025] proposed Add-remove Heterogeneous DP, where privacy levels depend on each user’s data; in contrast, our framework relaxes privacy in a dataset-independent way, based on statistical relation of insensitive attributes to sensitive ones. Aliakbarpour et al. [2025] proposed Bayesian Coordinate DP (BCDP) in a local DP setting without a trusted curator, which typically yields worse utility than central models.

CorrDP: setup and mechanisms

Let X be the data domain where each point X ∈ X ⊆ Rm can be partitioned as X = (X S , X U )⊤ , where S is the indices of sensitive features that require protection, and U is the indices of insensitive features, with S ∪ U = [m] and S ∩ U = ∅. Let ms be the number of sensitive features: ms = |S|. While the main body of the paper adopts a binary framework distinguishing sensitive and insensitive features, one can naturally extend CorrDP by assigning a sensitivity parameter to each feature. This yields a relaxed CorrDP notion without compromising theoretical guarantees. Appendix C.2 provides a detailed discussion and illustrates applications to ERM. In the standard (global) differential privacy (Definition B.1 in Appendix B), all feature components of

a data point are assumed to be equally sensitive, and thus the same privacy constraint is enforced on the change of any feature component between neighboring databases D, D′ . To capture heterogeneity among feature changes, we present the concept of CorrDP that incorporates a distance metric between databases d(D, D′ ), which quantifies the degree of privacy loss for feature differences there. Definition 2.1 (Neighboring Database). Databases D and D′ are neighboring if they differ in at most one entry, e and e′ , which themselves differ only in their sensitive features or insensitive features. See Remark 2.4 for commentary on this restriction. Definition 2.2 (CorrDP). A randomized algorithm A is (ϵ, δ)-correlated differentially private for a distance metric d if for all subsets R ⊆ Range(A) and for all neighboring databases D, D′ , ϵ

P(A(D) ∈ R) ≤ e d(D,D′ ) P(A(D′ ) ∈ R) + δ. We require the distance metric d(D, D′ ) to satisfy certain properties. Definition 2.3 (Axioms of Sensitivity Distance). For two neighboring databases D, D′ , the distance metric d captures how much the changes between D and D′ depend on the sensitive component, and must satisfy the following: (1) d(D, D′ ) ∈ [0, 1], (2) when e and e′ differ in sensitive features (i.e., in S), d(D, D′ ) = 1, (3) when e and e′ differ only in their insensitive features (i.e., in U), d(D, D′ ) ∈ [0, 1), and (4) when all differing insensitive features are independent of the sensitive features, then d(D, D′ ) = 0. Definition 2.3 ensures that sensitivity appropriately captures correlations between sensitive and insensitive features. When the insensitive features are only weakly correlated, the privacy constraint is relaxed; if neighboring databases differ in sensitive features, then CorrDP coincides with standard differential privacy. Remark 2.4. The notion of neighbors excludes changes in both sensitive and insensitive features because then d(D, D′ ) = 1, and the CorrDP constraint becomes exactly DP. Although CorrDP can be defined to include this case, no additional benefits can be gained from using this relaxed notion. In the main body, we define d(D, D′ ) based on the Total Variation (TV) Distance, which naturally satisfies the desired properties above. In Section B.2, we describe other properties preserved by CorrDP, and in Section B.3, we discuss other distances that can be used. Definition 2.5 (Choice of d). For neighboring databases D, D′ that differ in two entries e and e′ , d(D, D′ ) := max T V (PX S |eI , PX S |(e′ )I ), I:I⊆[m]

(1)

where PX S |eI is the conditional distribution of the sensitive features X S given X I = eI . TV distance is defined as T V (P, Q) := supA∈F |P(A) − Q(A)| for a measurable space (Ω, F) and probability distributions P and Q on (Ω, F). Then (1) satisfies the axioms in Definition 2.3. Next we present some concrete examples demonstrating how the CorrDP framework can be used. Example 2.6. Consider X = (X (1) , X (2) )⊤ , where S = {1}, U = {2}. X (1) and X (2) are partially correlated with PX (1) |X (2) =k ∼ Bernoulli(k/3), ∀k ∈ {1, 2}. Suppose databases D, D′ differ in entries e, e′ . If e = (1, 2)⊤ and e′ = (0, 1)⊤ , then d(D, D′ ) = 1 since T V (PX (1) |X (1) =1 , PX (1) |X (1) =0 ) = 1. However, if e = (1, 2)⊤ and e′ = (1, 1)⊤ , then d(D, D′ ) = T V (PX (1) |X (2) =2 , PX (1) |X (2) =1 ) = 1/3 < 1. In this case, the influence of this change on the privacy constraint is smaller since the two entries only differ in the insensitive coordinate. Example 2.7. Consider an economic dataset that includes a sensitive income feature X (1) , and an insensitive geography feature X (2) . If D, D′ differ only in the geographical information of one individual, this geographical information could still inadvertently reveal information about the individual’s income level, as the income distribution is correlated with location. Then this geography feature also requires protection, albeit with a reduced budget of ϵ/d(D, D′ ). In the extreme case where income depends solely on the geography, a change in location directly reveals the exact income level, and the privacy budget for this feature reduces to ϵ, since the geography information alone is sufficient to determine the individual’s income. 4

2.1

Laplace Mechanism with CorrDP

We show how to adopt the Laplace Mechanism to achieve privacy under CorrDP, and show the utility improvements. First, we introduce sensitivity under CorrDP. Definition 2.8 (ℓ1 , Coordinate, and Correlated Sensitivity). The ℓ1 -sensitivity of function f : N|X | → RK is: ∆f := max D,D′ ∥f (D) − f (D′ )∥1 , and the sensitivity of the k-th coordinate fk of f is: ∆fk := neighbors P P max D,D′ |fk (D) − fk (D′ )|. The correlated sensitivity is: ∆C f = min{ j∈S ∆fj + j∈U ∆fj T V (j), ∆f } neighbors

and T V (j) = maxx1 ,x2 ∈X T V (PX S |x(j) , PX S |x(j) ). 1 2 P Note that ∆f ≤ k∈[K] ∆fk , where equality holds when there exists a pair of neighboring databases that attains the maximum coordinate sensitivity ∆fk for all k ∈ [K]. The definition of correlated sensitivity accounts for the heterogeneous privacy constraints for insensitive features j ∈ U, incorporating their correlation with sensitive features through a weighting factor, T V (j). Next we show that the Laplace Mechanism can be modified to satisfy CorrDP by using correlated sensitivity, and can lead to improved accuracy guarantees. Definition 2.9 (CorrDP Laplace Mechanism). For a function f : N|X | → RK where the i-th dimension fL (D, f, ϵ) = of f only applies to the i-th feature of D, the CorrDP Laplace mechanism is defined as: M f (D) + (Y1 , . . . , YK ), where Yi ∼i.i.d. Lap(∆C f /ϵ). Theorem 2.10 (CorrDP Laplace Guarantees). The CorrDP Laplace mechanism is (ϵ, 0)-CorrDP, and ∀β ∈ fL (D, f (·), ϵ)∥∞ ≤ ∆C f log(K/β) ] ≥ 1 − β. (0, 1], P[∥f (D) − M ϵ The proof is given in Appendix A.1. The standard Laplace mechanism ML [Dwork, 2006] has a highprobability accuracy guarantee of ∥f (D) − ML (D, f, ϵ)∥∞ ≤ ∆f log(K/β) . Comparing this with Theorem 2.10, ϵ we see that the CorrDP Laplace mechanism yields better accuracy exactly when the lack of correlation across features leads to lower sensitivity, thereby requiring less noise to be added.

CorrDP ERM

Given a dataset D = {(xi , yi )}i∈[n] and an individual loss function ℓ(θ; (X, Y )) where X denotes the features priv and Y denotes the label, DP-ERM ∈ Rm close to thenon-private solution: Pn aims to obtain a solution θ θ̂ ∈ argminθ∈Θ {F (θ, D) := 1/n i=1 ℓ(θ; (xi , yi ))} with the guarantee of being differentially private. Across each privacy mechanism and setting, we measure the utility gap of θpriv as the additional empirical loss from adding privacy: R(θpriv ) := F (θpriv , D) − F (θ̂, D). (2) Existing DP-ERM models that satisfy (ϵ, δ)-DP will automatically satisfy our relaxed (ϵ, δ)-CorrDP notion, so the existence of CorrDP algorithms is a priori known. Our main goal is to see whether relaxing to CorrDP and appropriately modifying the DP-ERM algorithms will lead to utility improvements. We next give some assumptions that will be necessary for our results. Assumption 3.1 (Neighboring Database in ERM). The entry that differs across neighboring databases D, D′ only differs in sensitive features or insensitive features in X, and cannot differ in the label Y . This assumption refines Definition 2.1 by excluding label changes in Y . This follows prior work [Shen et al., 2023], which treated labels as public and not requiring privacy protection. Since changing labels may change all features (due to the relationship between features and label), then CorrDP in this setting will collapse to standard DP, and no additional improvements can be seen. When labels are private and features are public, one can use Label DP [Ghazi et al., 2021]. See Appendix C.2 for a detailed comparison between CorrDP and Label DP. For the ERM problem, we consider general smooth convex losses with bounded decision and feature domains. 5

Assumption 3.2 (Regularity of Loss Function). The loss function ℓ is L-Lipschitz, i.e., |ℓ(θ1 ; (x, y)) − ℓ(θ2 ; (x, y))| ≤ L∥θ1 − θ2 ∥2 . Assumption 3.3 (Boundness of Domain). The decision domain X is bounded such that ∀x ∈ X , ∥x∥2 ≤ B, and the parameter is bounded: ∥θ∥2 ≤ D. The boundness of domain and parameters is naturally imposed for theoretical analyses in DP-ERM algorithms [Wang et al., 2017]. In practice, unbounded gradients can be handled via gradient clipping. In Appendix C.2, we relax Assumption 3.3 and show that our main results still hold. Finally, we link the sensitivity of features to the parameter coordinate. Assumption 3.4. For the i-th coordinate of the gradient, i ∈ [m], (∇θ ℓ(θ; (x1 , y)) − ∇θ ℓ(θ; (x2 , y))i ≤ P (i) (i) (j) L (j) C1 L|x1 − x2 | + C2 j̸=i m |x1 − x2 | for some constants C1 , C2 . This assumption requires the loss function to be smooth with respect to changes in x, and the sensitivity of the i-th parameter coordinate to be mainly controlled by the i-th feature component. We note that Assumptions 3.3 and 3.4 for CorrDP-SGD are slightly stronger than the standard assumptions than DP-SGD, but Assumption 3.3 holds when all feature coordinates have relatively similar ranges (which can be done from normalization in model fitting) and Assumption 3.4 holds when ℓ(θ; (x, y)) can be represented by ℓ̃(θ⊤ x, y) for some ℓ̃, i.e., generalized linear model (GLM), such as OLS or logistic regression. We next demonstrate that both linear regression with Ordinary Least Square (OLS) and logistic regression satisfy these assumptions. Example 3.5 (Linear Regression, OLS). Consider the squared loss ℓ(θ; (x, y)) = (θ⊤ x − y)2 with bounded domain as in Assumption 3.3. If y is bounded, then Assumption 3.2 is satisfied with L = 2 supx |θ⊤ x−y|∥x∥2 ≤ 2B(D + maxy |y|) < ∞. The sensitivity of the i-th coordinate (∇θ ℓ(θ; (x1 , y)) − ∇θ ℓ(θ; (x2 , y)))i can be P (i) (i) (i) (j) (i) (j) written as 2(y − θ⊤ x1 + θi x2 )(x1 − x2 ) + 2 j̸=i θj x2 (x1 − x2 ). If the boundary parameter satisfies B|θi | ≤ CD m , ∀i ∈ [m] for some constant C > 0, then Assumption 3.4 is satisfied with C1 = 4B + 2CD/m and C2 = 2CD. ⊤

Example 3.6 (Logistic Regression). Consider the logistic loss ℓ(θ; (x, y)) = log(1+eθ x )−yθ⊤ x for y ∈ {0, 1} with bounded domain as in Assumption 3.3. Define σ(t) = (1 + e−t )−1 . The sensitivity of the i-th coordinate (∇θ ℓ(θ; (x1 , y)) − ∇θ ℓ(θ; (x2 , y)))i can be written as: (i)

(i)

(σ(θ⊤ x1 ) − y)(x1 − x2 ) + x2 (σ(θ⊤ x1 ) − σ(θ⊤ x2 )). (i)

(i)

(3) (i)

(i)

Since 0 ≤ σ(·) ≤ 1, the first term in (3) satisfies |(σ(θ⊤ x1 ) − y)(x1 − x2 )| ≤ |x1 − x2 |; since σ(·) is 1/4P (i) (j) (j) Lipschitz, the second term in (3) satisfies x2 |σ(θ⊤ x1 )−σ(θ⊤ x2 )| ≤ B4 |θ⊤ (x1 −x2 )| ≤ B4 j∈[m] |θj ||x1 −x2 |. If the boundary parameter satisfies B|θi | ≤ CD m , ∀i ∈ [m] for some constant C > 0, then Assumption 3.4 is satisfied with C1 = 2 + CD/(4m) and C2 = CD/4.

3.1

CorrDP-SGD Algorithm and Guarantees

We now present CorrDP-SGD in Algorithm 1, which incorporates CorrDP with DP-SGD [Bassily et al., 2014, Abadi et al., 2016]. The key change is the modified noise scale in Line 1, where the noise terms σi are set. Compared with the noise added in the standard DP-SGD mechanism [Bassily et al., 2014], in the noise variance term σi2 for i ∈ U, the unit scale 1 is replaced with max{T V (i), m2s /m2 } ≤ 1. Despite the smaller noise imposed on the insensitive features, we show that the privacy guarantee of CorrDP still holds. Theorem 3.7 (Privacy Guarantee of CorrDP-SGD). Under Assumptions 3.1, 3.2, 3.3 and 3.4, for ϵ, δ > 0 Algorithm 1 is (ϵ, δ)-CorrDP. The full proof of this main result is given in Appendix A.2. We give a proof sketch here, starting with the result for the full-batch gradient descent (nq = n). The analysis is similar to the standard moment 6

Algorithm 1 CorrDP Stochastic Gradient Descent (CorrDP-SGD) input Parameter domain Θ, number of iterations T , step sizes αt , dataset D = {(xi , yi )}i∈[n] with sensitive features S and insensitive features U, sample size nq with 1 ≤ nq ≤ n, CorrDP parameters (ϵ, δ) 1: Initialize θ1 , set ms = |S| and T V (i) = maxx1 ,x2 ∈X T V (PX S |xU , PX S |xU ) ∀i ∈ U, and set diagonal entries 1 2 of the noise variance {σi2 }i∈[m] ( σi2 =

(log(1/δ)+1)L2 T , n2 ϵ 2 (log(1/δ)+1)L2 T max{T V (i),m2s /m2 } , n2 ϵ 2

if i ∈ S; else

(4)

2: for t = 1, . . . , T do 3: Randomly sample nq datapoints {(x(i) , y(i) )}i∈[nq ] from the dataset D. 4:

Generate noise b ∼ N (0, diag(σ 2 )) and update: Pnq θt+1 = ΠΘ θt − αt ( n1q i=1 ∇θ ℓ(θt ; (x(i) , y(i) )) + b) .

5: end for output θpriv = θT +1 .

accountant argument [Abadi et al., 2016], replacing the parameter ϵ in the DP constraint with ϵ/d(D, D′ ), which is dataset-dependent. This modified moment accountant argument requires a refined analysis of the distributional distance between D and D′ for the sensitive and insensitive components. When D and D′ differ only in sensitive features S, the noise imposed on the sensitive features S is the same as the standard noise to preserve the privacy for the sensitive features, and the noise term m2s /m2 imposed on the insensitive features U ensures that privacy for the insensitive features is preserved from Assumption 3.4. Conversely, when D and D′ only differ in insensitive features, the noise term T V (i) imposed on the insensitive feature i ∈ U ensures privacy for that i-th feature. For the general version of the stochastic gradient descent where nq < n, the full batch result can be directly extended to SGD using privacy amplification via sampling [Balle et al., 2018]. Remark 3.8. When Assumption 3.1 is replaced with a stronger assumption that e and e′ differ in sensitive features or in one insensitive feature in X, we can simplify T V (i) as maxx1 ,x2 ∈X T V (PX S |x(i) , PX S |x(i) ) for 1 2 the same privacy guarantee of Theorem 3.7. Theorem 3.9 (Utility Guarantee Under Assumptions 3.1, 3.2, 3.3 and 3.4, for Algop of CorrDP-SGD). Pm rithm 1 with step sizes αt = D/ (L2 + i=1 σi2 )t and T = Θ(n2 ), if F (θ, D) is convex, then R(θpriv ) = p P Õ (ms + min{ i∈U T V (i), ms /4}) log(1/δ)/(nϵ) . The choice follows by verifying the square norm of the gradient at each step is E[∥F (θt , D)∥22 ] ≤ Pmstepsize 2 L + i=1 σi and applying Theorem 2 of Shamir and Zhang [2013]. The full proof of Theorem 3.9 is given in Appendix A.3. P Corollary 3.10 (Improved Utility Guarantee). Under the same conditions as Theorem 3.9, if i∈U T V (i) = √ Θ(ms ), then R(θpriv ) = Õ ms /(nϵ) . 2

This result demonstrates that if there are many insensitive features that are each not very P √ correlated with sensitive features, i.e., i∈U T V (i) = Θ(ms ), then compared with the DP-ERM utility of Õ ( m/(nϵ)) Bassily et al. [2014], Wang et al. [2018], CorrDP-SGD significantly improves utility guarantee when ms = o(m). Such improved utility guarantees under heterogeneous noise scales in Algorithm 1 can be applied to improve utility performance under strongly convex and general nonconvex losses (e.g., Corollary C.1) and other privacy-preserving first-order algorithms including SVRG [Wang et al., 2017] or Adam, while reducing the gradient complexity. Extension to Neural Networks. Beyond GLMs, CorrDP can also be applied to more general loss functions of the form ℓ(f (θ; x), y) that do not satisfy Assumption 3.4. Consider general loss functions of the 7

form ℓ(f (θ; x), y), where f (θ; x) : Rmθ × Rmx → R. Here, θ ∈ Rmθ and x ∈ Rmx have different dimensions (mθ = ̸ mx ). The most common application of such general loss functions is neural networks (NN) and CorrDP-SGD can be run to differentially privately train neural networks while adding reduced noise to the first layer, which will also result in improved performance relative to DP-SGD (under mild conditions). We consider a fully connected NN, with the following assumptions similar to Assumption 3.4: Assumption 3.11 (Sensitivity of Fully Connected NN). Consider f (θ; x) = g(θ(K) · · · g((θ(0) )⊤ x)), where g(·) denotes the activation function of the NN parameterized by θ = (θ(0) , . . . , θ(K) ), with the total dimension PK mθ = i=0 mθi . Then for parameter θ(0) ∈ Rm×d0 , where d0 is the number of neurons in the first hidden P (i) (i) (j) L (j) layer: (∇θ ℓ(f (θ(0) ; x1 ), y) − ∇θ ℓ(f (θ(0) ; x2 ), y))i ≤ C1 L|x1 − x2 | + C2 j̸=i m |x1 − x2 |, i ∈ [mθ0 ]. When adapting Algorithm 1 in the context of neural networks, we adjust the noise b = (b(0) , . . . , b(K) ), (k) with b(0) ∈ Rm×d0 , and the total dimension is mθ . Each noise term is sampled independently: for bi,j ∼ (k)

N (0, σi,j ), k ∈ {0, 1, . . . , K}, the noise scale ∀i ∈ [m], j ∈ [d0 ] is set as: ( (0) (σi,j )2 =

(log(1/δ)+1)L2 T , if i ∈ S; n2 ϵ 2 (log(1/δ)+1)L2 T max{T V (i),m2s /m2 } , n2 ϵ 2 (k)

(5)

else 2

T For the noise applied to the subsequent layers ∀k ≥ 1, we use (σi,j )2 = (log(1/δ)+1)L . Under Assumption 3.11, n2 ϵ 2 running CorrDP-SGD (Algorithm 1) to add noise to i-th row of θ(0) for i ∈ U according to Equation (5), satisfies (ϵ, δ)-CorrDP. √ P m When i∈U T V (i) = Θ(ms ), in NNs, CorrDP improves the utility guarantees from Õ nϵ θ under regular √ mθ −(m−ms )d0 DP [Wang et al., 2017] to Õ by instantiating Theorem 3.9. If the number of neurons in nϵ

the first hidden layer d0 is large compared with those of subsequent layers, this provides significant utility improvements. In specialized NNs like RNN modules, insensitive features may be processed in the first several layers without sensitive feature modules, and so there may be opportunities for more significant utility improvements via CorrDP.

3.2

Lower Bound

We provide a near-matching lower bound in terms of n, ϵ, and problem dimension. The key is to build the equivalence between CorrDP and standard DP definitions so that we can translate known lower bounds from DP [Bassily et al., 2014] to CorrDP. A full proof is in Appendix A.4. Theorem 3.12 (Lower bound for (ϵ, δ)-CorrDP algorithm). Let n, m ∈ N, ϵ > 0 and δ = o(1/n). Consider {T V (i)}i∈U sorted in descending order, denoted {T V (i) }i∈U . For every (ϵ, δ)-CorrDP algorithm that outputs θpriv , there exists a D such that with probability at least 1/3, q ms +maxk∈[(m−ms )] {k(T V (k) )2 } R(θpriv ) = Ω min 1, . nϵ

Comparing this lower bound to the utility P upper bound of CorrDP-SGD in Theorem 3.9, observe that (T V (1) )2 ≤ maxk∈[(m−ms )] {k(T V (k) )2 } ≤ i∈[(m−ms )] T V (i), so this is near-matching in terms of the problem dimension.

Estimating TV distance in CorrDP-SGD

In this section, we show how to extend CorrDP-SGD to handle the fact that the TV distance may not be known. The expression for the noise terms σi (Equation (4)) in CorrDP-SGD depends on the maximum of the conditional total variation distance T V (i). However, this term may be unknown in general, and can leak 8

information when estimated from D. In this section, we demonstrate that in many scenarios, the error from this additional estimation step is insignificant after proper processing. As a simple example, imagine there is domain knowledge of the exact value or a near-exact upper bound: Ui = T V (i)(1 + o(1)). It is easy to see that the utility and privacy guarantees are not affected in this case by simply replacing each unknown T V (i) with Ui , i ∈ U . We will mainly focus on the more general case when such knowledge is not available, but the estimation of TV distance is regular and smooth. Our goal will be to find adjusted expressions for the noise terms in Equation (4) while still obtaining similar privacy and utility guarantees to the case where T V (i) are known. In Equation (4), when {T V (i)}i∈U are unknown, the straightforward approach is to empirically estimate d them from the dataset D as T V D (i) and use these in place of {T V (i)}i∈U . However, this ignores that the estimation procedure itself can leak information about the database, and thus this procedure alone will not lead to correct privacy guarantees. Instead, we adjust the estimation of {T V (i)}i∈U in the noise terms σi . We require two assumptions: that this estimator has bounded error and bounded sensitivity. p d Assumption 4.1. With probability at least 1 − β, for each i ∈ [m], |T V D (i) − T V (i)| ≤ c2 log(1/β)/nγ for some c2 ∈ (0, ∞) and γ ∈ (0, 21 ]. d d Assumption 4.2. For all neighbors D, D′ , ∀i ∈ U, |T V D′ (i) − T V D (i)| ≤ cn3 for some c3 < ∞. Assumption 4.1 ensures the estimation error of the TV distance decreases with the sample size. Assumption 4.2 ensures the stability of the TV distance estimate, requiring that changing one sample leads to a bounded impact on the estimator. This is reasonable since one sample only influences the probability d V D (i) that satisfy mass by at most 1/n. In Appendix D, we provide examples of the empirical estimator T Assumptions 4.1 and 4.2, and their corresponding value of γ. For example, in Examples D.1 and D.3 where X S |X U = x follows a Gaussian distribution and X follows a joint Gaussian distribution, then γ = 12 because mean estimation in this setting has a convergence rate of exactly Op (n−1/2 ). For a more general case of X S |X U = x, the corresponding γ is strictly less than 12 when using nonparametric estimation methods [Tsybakov, 2008], such as kernel or histogram estimate (see Example D.2) to estimate the conditional distribution. In this general case, we use the following estimation procedure for T V (i) in the noise term σi2 . g V (i) = Definition 4.3 When {T V (i)}i∈U is unknown, replace T V (i) with T p (In-Sample TV Estimation). γ 2 d T V D (i) + 2c2 log((m − ms )/δ)/n in the expression for σi in Equation (4). d The additional term in the estimator ensures sufficient noise is added, since the empirical distance T V (i) may underestimate T V (i). The error of the sensitivity does not explicitly appear in Definition 4.3 because its magnitude is O(1/n) by Assumption 4.2, and thus is dominated by the estimation error as a consequence of Assumptions 4.1, and is explicitly taken into account by Definition 4.3 when n is large. Theorem 4.4 (Guarantees of CorrDP with In-Sample TV Estimation). When the estimator in Definition 4.3 is used for the noise terms σi , Assumptions 4.1 and 4.2 hold, and n = Ω(log(1/δ)), then Algorithm 1 is (ϵ, 2δ)-CorrDP and achieves the same utility guarantee as Theorem 3.9. The proof of Theorem 4.4 is more involved than the standard analyses in Theorem 3.7 due to the g dependence of T V on the database D, and can be found in Appendix A.5. First, since the empirical estimator d T V can underestimate the true TV distance, the analysis introduces a high-probability upper bound to g ensure that T V (i) ≥ T V (i), ∀i ∈ U. This guarantees conservative noise calibration and enables control of the Renyi divergence, following the proof technique for Theorem 3.7. Second, the noise variances for D and D′ may be different, which introduces an additional difference that must be accounted for in the privacy analysis. We show that the resulting difference can be bounded by Θ(1/n2 ) using Assumption 4.2, and thus still yields valid privacy guarantees. Remark 4.5 (Publicly available data). Suppose there is a public database D̃ of p size ñ that shares the same g d covariate distribution with our database D. Then setting T V (i) := T V D̃ (i) + 2c2 log((m − ms )/δ)/ñγ from d the empirical estimate T V D̃ (i) and plugging this estimate into the expression for σi in Equation (4), will preserve the guarantees of Theorem 4.4. 9

Numerical experiments

In this section, we empirically demonstrate that CorrDP achieves a better privacy-utility tradeoff than standard DP for empirical risk minimization. We use CorrDP-SGD (Algorithm 1) as the foundational algorithm across different experimental setups, and compare the utility of CorrDP against three baseline methods: (i) Semi : adds noise only on the feature component corresponding to the sensitive feature; (ii) Standard : standard DP-SGD that adds uniform noise to all features [Abadi et al., 2016]; (iii) Partial : discards the sensitive features and runs non-private algorithms only on insensitive features. The Semi baseline should provide an upper bound on utility for CorrDP since Semi provides a weaker privacy guarantee that doesn’t account for correlations across sensitive and insensitive features. Our goal is to show that CorrDP achieves better utility than the Standard and Partial baselines, and performs comparably to Semi. Our loss setup encompasses strongly convex losses (e.g., linear and logistic regression) and non-convex losses (e.g., neural networks). For privacy parameters, we set δ = 10−4 in synthetic datasets and δ = 10−5 in real datasets. We specify the noise magnitude used by each method in our problem setting. Across all methods, the default configuration (Standard ) injects additive noise b ∼ N (0, diag(σ 2 )) at each round, with σi2 = C · log(1/δ)+1 for ϵ2 some constant C > 0. • For Semi, when using OLS or logistic regression, we change σi2 = 0 for indices i ∈ U ; when using neural (0) networks, we change (σ(i,j) )2 = 0 for i ∈ U at the first layer, and apply the standard noise scale to all subsequent layers. • For CorrDP, when using OLS or logistic regression, we change σi2 = C · log(1/δ)+1 T V (i) for indices ϵ2 (0) 2 log(1/δ)+1 i ∈ [m]; when using neural networks, we change (σ(i,j) ) = C · T V (i) at the first layer, and ϵ2 apply the standard noise scale to all subsequent layers. In both cases, the unknown T V (i) is estimated g V (i) using finite samples, as described in by the upper bound estimate of the empirical counterpart T Section 4. Detailed configurations of gradient descent and results of TV distance estimation for each dataset are provided in Appendix E.

5.1

Synthetic dataset and results

We first consider synthetic data, and run a (ridge) linear regression model with loss ℓ(θ; (x, y)) = (y − θ⊤ x)2 + 1 2 S U ⊤ n ∥θ∥2 . We generate the synthetic training data according to a multivariate Gaussian, X = (X , X ) ∼ 2 ⊤ N (µ, Σ), Y = θ X + η with η ∼ N (0, 5 ). Among all features in X, we index the sensitive features as S = [ms ] and index the insensitive features as U = [m]\[ms ]. For the parameters µ and Σ in the marginal distribution, we set   1 if i = j ∈ S      if i = j ∈ U 2 µi = (−1)i+1 , i ∈ [m] and Σi,j = 0.5 if i, j ∈ S, i ̸= j .    0.5 if i, j ∈ U, i ̸= j    0.1 if i ∈ S, j ∈ U √ For each component of the true parameter i ∈ [m], θi = (−1)i+1 i + 1. We set m = 100, n = 2000, ms = 10, m − ms = 90. Therefore, the conditional distribution of sensitive features can be directly calculated and estimated from the posterior of the Gaussian distribution, which is still Gaussian. Figure 1a presents empirical findings on this dataset, which plots the utility gap (Equation (2)) as a function of ϵ for all four algorithms, where lower utility gap indicates better performance. We observe that CorrDP always outperforms Standard and Partial, especially so in the high privacy regime. The performance of CorrDP is comparable to that of Semi, especially for more reasonable values of ϵ, indicating that substantial performance is not lost with the stronger privacy guarantees. All three methods that incorporate the sensitive features (CorrDP, Semi, and Standard ) outperform Partial, which ignores these features. In Section E.1, we 10

Algorithm corr

semi

partial

0.09

0.08

0.040

0.07

0.035

8 6

Utility Gap

Utility gap

standard

0.06 0.05

0.04

0.03

0.02

0.030 0.025 0.020 0.015 0.010

0.2

0.4

0.6

0.8

User-level ε

1.0

(a) Synthetic Data (OLS)

0.2

0.4

0.6

User-level ε

0.8

1.0

0.1

0.2

0.3

0.4

0.5

User-level ε

0.6

0.7

(b) Adult (Log. Reg)

(e) Medical Cost (Linear Regression)

(f) Medical Cost (2-NN)

0.8

0.16 0.14

Utility gap

0.12 0.10 0.08 0.06 0.04 0.02 0.10

0.15

0.20

0.25

User-level ε

0.30

0.35

0.40

(d) Credit Card (Logistic Regression)

Figure 1: Privacy-utility trade-offs for least-square regression, logistic regression, and neural network training. The shaded area around each curve shows the standard deviation error band. We do not run the Partial algorithm on the Sepsis, Credit Card, and Medical Cost datasets since it is not comparable to use the same architecture only with partial features.

include additional empirical results that vary the number of sensitive features ms , and find that the number of sensitive features does not qualitatively impact the overall findings.

5.2

Real-world datasets and results

We also empirically evaluate the performance of CorrDP on four real-world classification or regression datasets: Adult [adu], Sepsis [sep], Credit Card [cre] and Medical Cost [med]. These datasets include both discrete and continuous features, where all discrete features are processed with one-hot encoding. For the three classification datasets (Adult, Sepsis, Credit Card), we use the same categorization of these features into sensitive (private) and insensitive (public) as Shen et al. [2023]. For the Medical Cost dataset (regression task), we set sex, smoke, region as insensitive features and all others as sensitive. Adult dataset [adu]. The dataset contains around 48,800 individuals in US and the standard task is to predict whether the annual income of an individual reaches $50k. Following Shen et al. [2023], we set race, gender, workclass, fnlwgt as insensitive features and age, educational-num, hours-per-week, marital-status, relationship as sensitive features. After filtering, we retain 45,175 sample points with 9 features (represented in 31 feature dimensions due to one-hot encoding of discrete features) and train a logistic regression model for binary classification. In Figure 1b, the baseline accuracy for the non-private algorithm is 83%, and we calculate the accuracy gap of private algorithms relative to this. We observe that CorrDP even outperforms Semi, and suffers less than a 4% accuracy drop compared with the non-private baseline, even in a relatively high privacy regime

(0.2 < ϵ < 0.5). Sepsis dataset [sep]. The dataset contains 110,204 patients in Norway who were diagnosed with infections and the standard task is to predict whether a patient survived an additional 9 days. The dataset contains 3 features: sex, episode number, and age. Following Shen et al. [2023], we set sex, episode number as insensitive features and age as the sensitive feature. Both sex and episode number are categorical features, with 2 and 5 categories respectively. The original sepsis dataset is imbalanced with 92.6% data from one class (‘Yes’) and the remaining 7.4% from the other class (‘No’). To address this imbalance, we use the SMOTE algorithm [Chawla et al., 2002] using the imblearn (imbalanced-learn) [Lemaitre et al., 2017] Python package, which combines SMOTE-based oversampling with Edited Nearest Neighbours (ENN) cleaning. Specifically, SMOTE-based oversampling generates synthetic minority samples by interpolating numerical features while assigning categorical features via nearest-neighbor voting, and ENN subsequently removes samples that are inconsistent with their local neighborhood to reduce noise. After pre-processing to address the class imbalance, we randomly sample 10,000 points from the resulting balanced dataset. We train a two-layer neural network, where the activation function and the number of neurons in the hidden layer are ‘Softplus’ and 5 respectively, and the activation function of the final layer is the ‘softmax’. Based on the extension of CorrDP to NNs presented in Section 3.1, for CorrDP and Semi, both CorrDP and Semi reduce the injected noise by restricting perturbations to the insensitive input components of the first layer. In Figure 1c, the baseline accuracy for non-private algorithm is 69%, and we observe that CorrDP has similar performance to Semi and consistently outperforms Standard, despite the stochasticity of the neural network initiation and batch gradient descent. Credit Card dataset [cre]. The dataset contains around 30,000 credit card customers in Taiwan over a 6-month period, and contains features corresponding to demographic information, credit data, payments, and statement information. The standard task on this dataset is to predict whether a customer will make the default payment next month. Following Shen et al. [2023], we set sex, education, marriage, and age as insensitive features, and set the remaining 19 features as sensitive. We use the full samples from the dataset and train a logistic regression model. As shown in Figure 1d, CorrDP achieves nearly the same utility as Semi and substantially outperforms Standard across all privacy levels. Medical Cost dataset [med]. The dataset contains records from 1,337 individuals related to their health information and their medical costs as billed by health insurance. The standard task on this dataset is to predict the individual medical costs billed by health insurance. The dataset contains seven features: age, sex, bmi, children, smoker, region, charges. We set sex, smoke, region as insensitive features, and all others as sensitive. We randomly sample 1,000 points from the dataset and evaluate two model classes: linear regression and a two-layer neural network with 20 hidden neurons and ‘Softplus’ activations. Results are reported in Figures 1e- 1f). Across both models, CorrDP consistently outperforms Standard and performs comparably to Semi, further confirming that CorrDP achieves strong privacy-utility trade-offs while reducing the noise scale relative to standard differentially private methods.

Discussion

In this work, we studied CorrDP, a relaxed notion of differential privacy that incorporates feature correlation across partitioned sensitive and insensitive features. We showed how this notion can be applied to the DP-ERM and DP-SGD algorithms. Our theoretical results show that CorrDP leads to utility improvements for the same fixed ϵ value, relative to standard DP. The essence of these improvements comes from adding less noise to features that are independent from, or only weakly correlated with, the sensitive variables. We

verified these findings empirically across real and synthetic datasets. We also gave extensions of these results, showing that our algorithmic framework could be applied (i) to neural networks with more general loss functions, (ii) when there was uncertainty about the level of correlation, and (iii) using general notions of distance across features. Our work has several limitations that point to promising directions for future research. First, the framework is most effective when the distinction between sensitive and insensitive features is clearly defined. In settings where sensitivity lies on a spectrum and the boundary is less clear, we introduce relaxations in Appendix C.2 that still yield improved utility guarantees. Second, ensuring privacy while maintaining strong utility under CorrDP-SGD requires additional assumptions on the feature space and the structure of the fitted model. Third, the noise calibration in CorrDP-SGD relies on an (upper bound) estimate of the TV distance. While we provide a method for computing such an estimate, this step can be computationally demanding in high-dimensional problems, with some potential remedies discussed at the end of Appendix D. Advances in distance estimation methods would directly enhance the efficiency of this step in CorrDP. Furthermore, extending the theoretical guarantees of CorrDP to other statistical tasks, such as hypothesis testing and related inferential problems, would be worth investigating.

References Adult income dataset. https://www.kaggle.com/datasets/wenruliu/adult-income-dataset. Accessed: Jan 2025. Default of credit card clients. https://archive.ics.uci.edu/dataset/350/default+of+credit+card+ clients. Accessed: Mar 2025. Medical cost dataset. https://www.openml.org/search?type=data&status=active&id=46289. Accessed: Mar 2025. Sepsis survival dataset. https://www.kaggle.com/datasets/joebeachcapital/ sepsis-survival-minimal-clinical-records/data. Accessed: Jan 2025. Martin Abadi, Andy Chu, Ian Goodfellow, H 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, CCS ‘16, pages 308–318, 2016. Jayadev Acharya, Kallista Bonawitz, Peter Kairouz, Daniel Ramage, and Ziteng Sun. Context aware local differential privacy. In Proceedings of the 37th International Conference on Machine Learning, ICML ‘20, pages 52–62, 2020. Maryam Aliakbarpour, Syomantak Chaudhuri, Thomas Courtade, Alireza Fallah, and Michael Jordan. Enhancing feature-specific data protection via bayesian coordinate differential privacy. In Proceedings of the 28th International Conference on Artificial Intelligence and Statistics, AISTATS ‘25, pages 4069–4077, 2025. Noga Alon, Raef Bassily, and Shay Moran. Limits of private learning with access to public data. Advances in Neural Information Processing Systems, 32, 2019. Miguel E Andrés, Nicolás E Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. Geoindistinguishability: Differential privacy for location-based systems. In Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS ‘13, pages 901–914, 2013. Hilal Asi, John Duchi, Alireza Fallah, Omid Javidbakht, and Kunal Talwar. Private adaptive gradient methods for convex optimization. In Proceedings of the 38th International Conference on Machine Learning, ICML ‘21, pages 383–392, 2021.

Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in Neural Information Processing Systems, 31, 2018. Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proceedings of the IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS ‘14, pages 464–473, 2014. Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC ‘14, pages 1–10, 2014. Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011. Syomantak Chaudhuri and Thomas A. Courtade. Managing correlations in data and privacy demand. In Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security, CCS ’25, pages 2384–2398, 2025. Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer. SMOTE: Synthetic minority over-sampling technique. Journal of Artificial Intelligence Research, 16:321–357, 2002. Jiangnan Cheng, Ao Tang, and Sandeep Chinchali. Task-aware privacy preservation for multi-dimensional data. In Proceedings of the 39th International Conference on Machine Learning, ICML ‘22, pages 3835–3851, 2022. Lynn Chua, Qiliang Cui, Badih Ghazi, Charlie Harrison, Pritish Kamath, Walid Krichene, Ravi Kumar, Pasin Manurangsi, Krishna Giri Narra, Amer Sinha, Avinash Varadarajan, and Chiyuan Zhang. Training differentially private ad prediction models with semi-sensitive features, 2024. arXiv preprint 2401.15246. Luc Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation distance between high-dimensional gaussians with the same mean, 2018. arXiv preprint 1810.08693. Cynthia Dwork. Differential privacy. In Proceedings of the 33rd International Colloquium on Automata, Languages, and Programming, ICALP ‘06, pages 1–12, 2006. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014. Joseph Geumlek and Kamalika Chaudhuri. Profile-based privacy for locally private computations. In Proceedings of the 2019 IEEE International Symposium on Information Theory, ISIT ‘19, pages 537–541, 2019. Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. Deep learning with label differential privacy. Advances in Neural Information Processing Systems, 34:27131–27145, 2021. Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, and Chiyuan Zhang. On convex optimization with semi-sensitive features. In Proceedings of the 37th Annual Conference on Learning Theory, COLT ‘24, pages 1916–1938, 2024. Tristen Hayfield and Jeffrey S Racine. Nonparametric econometrics: The np package. Journal of statistical software, 27:1–32, 2008. Jacob Imola, Shiva Kasiviswanathan, Stephen White, Abhinav Aggarwal, and Nathanael Teissier. Balancing utility and scalability in metric differential privacy. In Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, UAI ‘22, pages 885–894, 2022.

Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradient methods under the polyak-lojasiewicz condition. In Proceedings of the 2016 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, pages 795–811, 2016. Daniel Kifer and Ashwin Machanavajjhala. No free lunch in data privacy. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, pages 193–204, 2011. Guillaume Lemaitre, Fernando Nogueira, and Christos K Aridas. Imbalanced-learn: A python toolbox to tackle the curse of imbalanced datasets in machine learning. Journal of Machine Learning Research, 18 (17):1–5, 2017. Tian Li, Manzil Zaheer, Sashank Reddi, and Virginia Smith. Private adaptive optimization with side information. In Proceedings of the 39th International Conference on Machine Learning, ICML ‘22, pages 13086–13105, 2022. Wenqian Li and Yan Pang. Private wasserstein distance, 2024. arXiv preprint 2404.06787. Hai Liu, Dequan Xu, Youliang Tian, Changgen Peng, Zhenqiang Wu, and Ziyue Wang. Wasserstein generative adversarial networks based differential privacy metaverse data sharing. IEEE Journal of Biomedical and Health Informatics, 2023. Andrew Lowy, Zeman Li, Tianjian Huang, and Meisam Razaviyayn. Optimal differentially private model training with public data. In Proceedings of the 41st International Conference on Machine Learning, ICML ‘24, 2024. Alain Rakotomamonjy and Ralaivola Liva. Differentially private sliced wasserstein distance. In Proceedings of the 38th International Conference on Machine Learning, ICML ‘21, pages 8810–8820, 2021. Angelika Rohde and Lukas Steinberger. Geometrizing rates of convergence under local differential privacy constraints. The Annals of Statistics, 48(5):2646–2670, 2020. Mathieu Sart. Density estimation under local differential privacy and Hellinger loss. Bernoulli, 29(3): 2318–2341, 2023. David Schneider, Sina Sajadmanesh, Vikash Sehwag, Saquib Sarfraz, Rainer Stiefelhagen, Lingjuan Lyu, and Vivek Sharma. Masked differential privacy, 2024. arXiv preprint 2410.17098. Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In Proceedings of the 30th International conference on machine learning, ICML ‘13, pages 71–79, 2013. Zeyu Shen, Anilesh Krishnaswamy, Janardhan Kulkarni, and Kamesh Munagala. Classification with partially private features, 2023. arXiv preprint 2312.07583. Weiyan Shi, Aiqi Cui, Evan Li, Ruoxi Jia, and Zhou Yu. Selective differential privacy for language modeling. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics, pages 2848–2859, 2022. Shuang Song, Yizhen Wang, and Kamalika Chaudhuri. Pufferfish privacy mechanisms for correlated data. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1291–1306, 2017. Alexandre B Tsybakov. Introduction to nonparametric estimation. Springer Science & Business Media, 2008. Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. Advances in Neural Information Processing Systems, 30, 2017. Di Wang, Marco Gaboardi, and Jinhui Xu. Empirical risk minimization in non-interactive local differential privacy revisited. In Advances in Neural Information Processing Systems, volume 31, 2018. 15

Tao Zhang, Tianqing Zhu, Renping Liu, and Wanlei Zhou. Correlated data in differential privacy: Definition and analysis. Concurrency and Computation: Practice and Experience, 34(16):e6015, 2022a. Wanrong Zhang, Olga Ohrimenko, and Rachel Cummings. Attribute privacy: Framework and mechanisms. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pages 757–766, 2022b. Ying Zhao and Jinjun Chen. A survey on differential privacy for unstructured data content. ACM Computing Surveys, 54(10s):1–28, 2022. Yingxue Zhou, Zhiwei Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private SGD with gradient subspace identification, 2020. arXiv preprint 2007.03813.

Omitted Proofs

A.1

Proof of Theorem 2.10

Theorem 2.10 (CorrDP Laplace Guarantees). The CorrDP Laplace mechanism is (ϵ, 0)-CorrDP, and ∀β ∈ fL (D, f (·), ϵ)∥∞ ≤ ∆C f log(K/β) ] ≥ 1 − β. (0, 1], P[∥f (D) − M ϵ Proof. Consider two neighboring databases D, D′ ∈ N|X | , and let f (·) be some function f : N|X | → RK . Let fL (D, f, ϵ) and pD′ denote the probability density function pD denote the probability density function of M ′ ′ f of ML (D , f, ϵ) with D:,i and D:,i as their i-th column (feature) respectively. Then for any arbitrary point z ∈ RK : ϵ|f (D:,i )−zi )| ! K Y exp(− ) pD (z) ∆C f = ϵ|f (D )−z )| :,i i pD′ (z) i=1 exp(− ) ∆C f K ′ Y ϵ(|f (D:,i ) − zi | − |f (D:,i ) − zi |) exp = ∆C f i=1 ! ′ K ′ Y ϵ|f (D:,i ) − f (D:,i )|1Di ̸=D:,i ≤ exp ∆C f i=1 ! P ′ ϵ k∈[K] ∆fk 1D:,k ̸=D:,k ≤ exp ∆C f ϵ ′ ′ 1D:,S =D:,S + exp(ϵ)1D:,S ̸=D:,S , ≤ exp d(D, D′ ) P where the second inequality comes from the fact that ∆f ≤ k∈[K] ∆fk , and the third inequality follows ′ from considering the two cases when D:,S = D:,S and D:,S ̸= D:,S (since only one insensitive feature can change by Definition 2.1). For the utility guarantee, we have: ∆C f ∆C f f P ∥f (D) − ML (D, f (·), ϵ)∥∞ ≥ log(K/β) = P max |Yi | ≥ log(K/β) ϵ ϵ i∈[K] ∆C f ≤ KP |Yi | ≥ log(K/β) ϵ β =K· K = β, 16

where the first equality comes from the definition of the mechanism, the second equality comes from a union bound over i ∈ [K], and the second step comes from the fact each Yi ∼ Lap(∆C f /ϵ) and tail bounds on the Laplace distribution. We note that this analysis is nearly identical to the utility guarantee of the Laplace Mechanism in Dwork [2006], but is included for completeness.

A.2

Proof of Theorem 3.7

Theorem 3.7 (Privacy Guarantee of CorrDP-SGD). Under Assumptions 3.1, 3.2, 3.3 and 3.4, for ϵ, δ > 0 Algorithm 1 is (ϵ, δ)-CorrDP. A.2.1

Helper Lemmas

We first introduce and prove the following lemmas, which will be used in the proof of Theorem 3.7. Lemma A.1 (High-Probability Composition of CorrDP). Suppose with probability 1 − δ2 (taken over the randomness in the dataset and the algorithmic mechanism), the algorithm A satisfies (ϵ, δ1 )-CorrDP. Then A is (ϵ, δ1 + δ2 )-CorrDP. Proof. Consider the good event E that A is (ϵ, δ1 )-CorrDP with P(E) = 1 − δ2 . Then: ϵ

≤ (1 − δ2 )(e d(D,D′ ) P(A(D) ∈ S|E) + δ1 ) + δ2 · 1 ϵ

= (1 − δ2 )e d(D,D′ ) P(A(D′ ) ∈ S|E) + δ1 + δ2 − δ1 δ2 ϵ

≤ e d(D,D′ ) P(A(D′ ) ∈ S) + δ1 + δ2 where the second inequality is because P(A(D′ ) ∈ S) ≥ (1 − δ2 )P(A(D′ ) ∈ S|E) from the total probability decomposition. Definition A.2 (Renyi Divergence). The α-Renyi divergence between distributions P and Q is defined as: " α−1 # 1 dP (x) log Ex∼P , Dα (P ∥Q) = α−1 dQ(x) For special values α = 1, ∞, the α-Renyi divergence is defined by taking the corresponding limit of the right-hand side. Lemma A.3 (α-Renyi Divergence between two Multivariate Gaussians). For two m-dimensional distributions P = N (µ1 , Σ1 ), Q = N (µ2 , Σ2 ),   1 log |Σ2 | + Tr(Σ−1 Σ1 ) + (µ2 − µ1 )⊤ Σ−1 (µ2 − µ1 ) − m , if α = 1 2 2 2 |Σ1 | Dα (P ∥Q) = . α/2 (1−α)/2  1 log |Σ2 | |Σ1 | + α2 (µ1 − µ2 )⊤ ((1 − α)Σ1 + αΣ2 )−1 (µ1 − µ2 ), else α−1 |(1−α)Σ1 +αΣ2 |1/2 Proof. We prove the case α ̸= 1 by direct calculation from the definition, and then obtain the α = 1 case by taking a limit. First, denote the densities of P and Q as p(x) and q(x) respectively: p(x) =

1 1 ⊤ −1 − exp (x−µ ) Σ (x−µ ) , 1 1 1 2 (2π)m/2 |Σ1 |1/2 17

q(x) =

1 1 ⊤ −1 − exp (x−µ ) Σ (x−µ ) . 2 2 2 2 (2π)m/2 |Σ2 |1/2

For α ∈ (0, 1) ∪ (1, ∞), we have p(x)α q(x)1−α = (2π)−m/2 |Σ1 |−α/2 |Σ2 |−(1−α)/2 1 ⊤ −1 × exp − α(x − µ1 )⊤ Σ−1 1 (x − µ1 ) + (1 − α)(x − µ2 ) Σ2 (x − µ2 ) . 2 In the exponent, we expand the quadratic form in x: ⊤ −1 α(x − µ1 )⊤ Σ−1 1 (x − µ1 ) + (1 − α)(x − µ2 ) Σ2 (x − µ2 ) ⊤ −1 −1 ⊤ −1 ⊤ −1 = x⊤ αΣ−1 x − 2 αΣ−1 1 + (1 − α)Σ2 1 µ1 + (1 − α)Σ2 µ2 x + αµ1 Σ1 µ1 + (1 − α)µ2 Σ2 µ2 . {z } {z } | | =:A

=:b

Let −1 A := αΣ−1 1 + (1 − α)Σ2 ,

−1 b := αΣ−1 1 µ1 + (1 − α)Σ2 µ2 .

Then x⊤ Ax − 2b⊤ x = (x − A−1 b)⊤ A(x − A−1 b) − b⊤ A−1 b. Hence 1 1 p(x)α q(x)1−α = (2π)−m/2 |Σ1 |−α/2 |Σ2 |−(1−α)/2 exp − (x − A−1 b)⊤ A(x − A−1 b) exp − c0 − b⊤ A−1 b , 2 2 where we set −1 ⊤ −1 c0 := αµ⊤ 1 Σ1 µ1 + (1 − α)µ2 Σ2 µ2 .

Note that the integral of the centered Gaussian is standard: Z 1 (2π)−m/2 exp − (x − A−1 b)⊤ A(x − A−1 b) dx = |A|−1/2 . 2 Rm Therefore Z

1 p(x)α q(x)1−α dx = |Σ1 |−α/2 |Σ2 |−(1−α)/2 |A|−1/2 exp − c0 − b⊤ A−1 b . 2

Define Σα := (1 − α)Σ1 + αΣ2 . Two standard (but checkable) matrix identities hold for positive definite Σ1 , Σ2 and scalar α: −1 −α |A| = |αΣ−1 |Σ2 |−(1−α) |Σα |−1 , 1 + (1 − α)Σ2 | = |Σ1 |

c0 − b⊤ A−1 b = α(1 − α)(µ1 − µ2 )⊤ Σ−1 α (µ1 − µ2 ).

(6) (7)

These can be verified by expanding both sides or by diagonalizing in a basis where the matrices commute; they are standard in formulas for Gaussian Chernoff/Renyi divergences. Substituting (6) and (7) into the integral, we get Z −1/2 p(x)α q(x)1−α dx = |Σ1 |−α/2 |Σ2 |−(1−α)/2 |Σ1 |−α |Σ2 |−(1−α) |Σα |−1 1 × exp − α(1 − α)(µ1 − µ2 )⊤ Σ−1 (µ − µ ) 1 2 α 2 α/2 (1−α)/2 |Σ2 | |Σ1 | α(1 − α) ⊤ −1 = exp − (µ − µ ) Σ (µ − µ ) . 1 2 1 2 α 2 |Σα |1/2

Finally, plug into the definition, by Definition A.2, Z 1 Dα (P ∥Q) = log p(x)α q(x)1−α dx α−1 α(1 − α) |Σ2 |α/2 |Σ1 |(1−α)/2 1 1 ⊤ −1 log + log exp − (µ − µ ) Σ (µ − µ ) = 1 2 1 2 α α−1 α−1 2 |Σα |1/2 α 1 |Σ2 |α/2 |Σ1 |(1−α)/2 + (µ1 − µ2 )⊤ Σ−1 = log α (µ1 − µ2 ), α−1 2 |Σα |1/2 which is exactly the expression stated in the lemma for α ̸= 1. Specially, when α = 1, the Kullback-Leibler divergence between two Gaussians is known to be 1 |Σ2 | ⊤ −1 log + Tr(Σ−1 Σ ) + (µ − µ ) Σ (µ − µ ) − m . KL N (µ1 , Σ1 ) ∥ N (µ2 , Σ2 ) = 1 2 1 2 1 2 2 2 |Σ1 | Since Dα (P ∥Q) is continuous in α and Renyi divergence converges to KL divergence as α → 1, taking the limit α → 1 in the above expression gives the α = 1 line in the statement. This completes the proof. λ P[M(D)=θ] Lemma A.4 (Property of CorrDP Privacy Loss). Define αM (λ; D, D′ ) = log Eθ∼M(D) P[M(D . Then: ′ )=θ] • Composability: Suppose M consists of a sequence of K adaptive mechanisms M1 , . . . , MK . Then: αM (λ) ≤

K X

αMi (λ).

i=1 ϵ • Tail bound: For any ϵ > 0, the mechanism M is ( d(D,D ′ ) , δ)-differentially private for, λ ϵ , δ ≥ exp αM (λ) − d(D, D′ )

for some λ ≥ 0. ϵ Lemma A.4 follows immediately from Theorem 2 in Abadi et al. [2016] by replacing ϵ there with d(D,D ′) .

Lemma A.5. Consider any algorithm A that is (ϵ, δ)-CorrDP on a database D with n entries. Then if it is executed in a subsampled dataset Dnq ⊆ D by selecting each data point independently with probability ζ ∈ (0, 1], i.e., the sampling fraction ζ and run A. This subsampled version of algorithm A is (ζϵ, ζδ)-CorrDP. ϵ Lemma A.5 follows immediately from Theorem 9 in Balle et al. [2018] by replacing ϵ there with d(D,D ′) .

A.2.2

Proving Theorem 3.7

We now return to the proof of Theorem 3.7. Proof. We start the case of the full-batch gradient descent with nq = n. When nq = n, we prove through the moment accountant argument in Abadi et al. [2016]. Consider the overall gradient mechanism M consisting of the privacy guarantee at each iteration M1 × . . . Mi . . . × MT . First, we define the privacy loss at an outcome θ ∈ Θ as: c(θ; M, D, D′ ) := log

P[M(D) = θ] . P[M(D′ ) = θ]

(8)

For the given mechanism M, we define the λ-th moment αM (λ; D, D′ ) as the log of the moment generating function evaluated at the value λ: αM (λ; D, D′ ) := log Eθ∼M(D) [exp(λc(θ; M, D, D′ ))]. 19

(9)

Due to the composability and the tail bound properties of the moment accountant (Lemma A.4), we only need to show: λϵ αM (λ; D, D′ ) ≤ . (10) 2T d(D, D′ ) ′

2 log(1/δ) λϵ Then we set λ such that δ ≥ exp(− 2d(D,D ≥ 2d(D,D )ϵ log(1/δ) = Θ(log(1/δ)) for a constant ′ ) ) (i.e., λ = ϵ ϵ) and satisfy the privacy condition. Consider the two distributions with respect to input D and D′ at each time step t. That is: n

P :=

1X ∇θ ℓ(θt , (xi , yi )) + b n i=1 n−1

1X 1 Q := ∇θ ℓ(θt , (xi , yi )) + ∇θ ℓ(θt , (x′n , yn′ )) + b. n i=1 n We can represent P and Q by N (µD , diag(σ 2 )) and N (µD′ , diag(σ 2 )), where: µD =

n n−1 1X 1X 1 ∇z ℓ(z, yi )|z=θt⊤ xi xi , µD′ = ∇z ℓ(z, yi )|z=θt⊤ xi xi + ∇z ℓ(z, yn )|z=θt⊤ x′n x′n . n i=1 n i=1 n

Recall the definition of α-Renyi divergence in Definition A.2. Then αM (λ; D, D′ ) = λDλ+1 (P ∥Q). Plugging Lemma A.3 in, we have: 2 λ(λ + 1) X (µD − µD′ )i ′ αM (λ; D, D ) = . 2 σi i∈[m]

And our goal is to let

of each coordinate equally, σi2 ≥

(µD −µD′ )i λϵ ≤ 2T d(D,D ′ ) . Specifically, we allocate the privacy cost i∈[m] σi D ′ )i 2 i.e., ( (µD −µ ) ≤ (λ+1)mTϵ d(D,D′ ) , ∀i ∈ [m]. This is equivalent to saying σi

λ(λ+1) P

(λ+1)mT d(D,D ′ )(µD −µD′ )2i . Based on Assumptions 3.3 and 3.4, we have: ϵ2

|µD − µD′ |i ≤

1 LX (C1 LBi 1{x(i) ̸=x′(i) } + C2 Bj 1{x(j) ̸=x′(j) } ). n n n n n m

(11)

j̸=i

From Assumption 3.3, we have: mBi2 = Θ(B 2 ). Following the definition of neighboring database in Assumption 3.1, we consider the following cases: • When D, D′ differ in the subsets of sensitive feature: d(D, D′ ) = 1. For the sensitive feature i ∈ S, P 2(λ+1)L2 mBi2 T 2L σi2 ≥ ; For the insensitive feature i ∈ U, |µD − µD′ |i ≤ Cnm j∈S Bj , plugging it back, n2 ϵ 2 2

s 2 we have: σi2 ≥ 2L Tn(λ+1)B (m 2 ϵ2 m ) .

• When D, D′ differ in the subsets of insensitive feature: d(D, D′ ) ∈ (0, 1]. The noise scale of the sensitive feature matches the one in standard DP in the Therefore, we only need to consider P previous Ccase. 2C1 LB 2L 1 Bi L insensitive features i ∈ U, |µD − µD′ |i ≤ Cmn ≤ . Plugging it back, we have: j∈U Bj + n n 2

T V (i) σi2 ≥ 2L T (λ+1)B . n2 ϵ 2

Therefore, the following noise choice satisfies the privacy guarantee by setting λ∗ = Θ(log(1/δ)) as discussed above. ( ∗ (λ +1)B 2 L2 T , if i ∈ S; 2 n2 ϵ2 σi = (λ∗ +1)B . (12) 2 2 L T max{T V (i),m2s /m2 } , else n2 ϵ2 Then we show that our results hold for the case when nq < n. At each step, the current update with respect to the full batch in Algorithm 1 is equivalent to: 20

θt+1 = ΠΘ

! n αt X (∇θ ℓ(θt ; (xi , yi )) + bi ) , where bi ∼ N (0, ndiag(σ 2 )). θt − n i=1

If we apply this algorithm to the SGD with subsampling ratio ζ with nq = ζn with a randomly selected subset {(x(i) , y(i) }i∈[nq ] , the corresponding gradient descent each time becomes: θt+1 = ΠΘ ⇐⇒

θt+1 = ΠΘ

! nq αt X θt − (∇θ ℓ(θt ; (xi , yi )) + bi ) , where bi ∼ N (0, ndiag(σ 2 )). nq i=1 !! nq 1 1 X (∇θ ℓ(θt ; (x(i) , y(i) ))) + b , where b ∼ N (0, diag(σ 2 )). θt − α t nq i=1 ζ

Applying Lemma A.5, this gives (ζϵ, ζδ)-CorrDP. From the noise terms defined in Equation (4), by changing the noise scale from b ∼ N (0, ζ1 diag(σ 2 ) to b ∼ N (0, diag(σ 2 )) gives (ϵ, ζδ)-CorrDP.

A.3

Proof of Theorem 3.9

Theorem 3.9 (Utility Guarantee Under Assumptions 3.1, 3.2, 3.3 and 3.4, for Algop of CorrDP-SGD). Pm rithm 1 with step sizes αt = D/ (L2 + i=1 σi2 )t and T = Θ(n2 ), if F (θ, D) is convex, then R(θpriv ) = p P Õ (ms + min{ i∈U T V (i), ms /4}) log(1/δ)/(nϵ) . Before proving Theorem 3.9, we first state the following lemma, which follows immediately from Theorem 2 in Shamir and Zhang [2013]. Q Lemma A.6 ([Shamir and Zhang, 2013]). Recall the stochastic gradient descent θt+1 = Θ (θt − αt G(θt )), where E[G(θt )] = ∇F (θt , D) and E[∥G(θt )∥22 ] ≤ G2 in Algorithm 1. For any T > 1, if αt = GD√t , then: E[F (θT , D) − F (θ̂, D)] ≤ O

DG log T √ T

= Õ

DG √ T

(13)

We now return to the proof of Theorem 3.9. Proof. Lemma A.6 gives a bound on R(θpriv ), but in order to apply the lemma, we need to compute the upper bound of E[∥G(θt )∥22 ] in Algorithm 1. We begin as follows: X E[∥G(θt )∥22 ] = E[∥∇F (θt , D) + b∥22 ] = E[∥∇F (θt , D)∥22 ] + E[∥b∥22 ] ≤ L2 + σi2 . (14) i∈[m]

Recall the definition of {σi }i∈[m] in (12), we can further bound the second term of Equation (14) by: X

σi2 ≤

X m2s B 2 D2 T log(1/δ) (m + min{T V (i), }) s n 2 ϵ2 m2 i∈U

i∈[m]

B D T log(1/δ) ≤ n 2 ϵ2 ≤

B 2 D2 log(1/δ) ϵ2

(m − ms )m2s ms + min{ T V (i), }) m2 i∈U ! X ms ms + min{ T V (i), } . 4 X

! (15)

i∈U

Above, the second inequality follows from the fact there are m − ms insensitive features in all. The third s) inequality follows from ms (m−m ≤ 14 , and T = Θ(n2 ). m2

Plugging this upper bound back into Equation (14) gives, B 2 D2 log(1/δ) E[∥G(θt )∥22 ] ≤ L2 + ϵ2

ms + min{

X i∈U

! ms T V (i), } . 4

We can now apply Lemma A.6 with: v ! p u s X X u BD log(1/δ) ms B 2 D2 log(1/δ) ms t 2 m + min{ T V (i), G= L + } m + min{ T V (i), } ≤ L+ s s ϵ2 4 ϵ 4 i∈U

i∈U

and eliminate constant B, D, C to obtain the bound in Theorem 3.9.

A.4

Proof of Theorem 3.12

Theorem 3.12 (Lower bound for (ϵ, δ)-CorrDP algorithm). Let n, m ∈ N, ϵ > 0 and δ = o(1/n). Consider {T V (i)}i∈U sorted in descending order, denoted {T V (i) }i∈U . For every (ϵ, δ)-CorrDP algorithm that outputs θpriv , there exists a D such that with probability at least 1/3, q ms +maxk∈[(m−ms )] {k(T V (k) )2 } R(θpriv ) = Ω min 1, . nϵ

We first introduce the following lemma. Lemma A.7 (Lower bound for 1-way marginals). Let m, n ∈ N, ϵ > 0 and δ = o(1/n). There is a √ number M = Ω(min{n, ϵm }) such that for Pnevery (ϵ, δ)-differential private algorithm A, there is a dataset D = {d1 , . . . , dn } ⊆ {− √1m , √1m }m with ∥ i=1 di ∥2 ∈ [M − 1, M + 1] such that, with probability at least 2/3, √ P we have: ∥A(D) − q(D)∥2 = Ω(min{1, nϵm }), where q(D) = n1 i∈[n] di . Lemma A.7 is nearly identical to Lemma 5.1 (Part 2) in Bassily et al. [2014]. The only modification is that we invoke the following Lemma A.8 to obtain the required lower bound with probability 2/3. The remainder of the proof is identical. √ Lemma A.8 (Modified Corollary 3.8 of Bun et al. [2014]). There exists n∗ = Ω ϵm such that for every n ≤ n∗ , there exists a dataset D = {d1 , . . . , dn } ⊆ {− √1m , √1m }m such that, with probability at least 2/3, 2 ∥A(D) − q(D)∥2 > 27 . We now return to the proof of Theorem 3.12. Proof. We consider sensitive and insensitive components separately, for any (ϵ, δ)-CorrDP algorithm. First, consider the sensitive components. Then (ϵ, δ)-CorrDP algorithm is the same as (ϵ, δ)-DP algorithm 1 1 since d(D, D′ ) = 1. For this, we construct DS = {e1 , . . . , en } ⊆ {− √m , √m }ms . Applying Lemma A.7, s s √ Pn m we know there exists such DS with ∥ i=1 ei ∥ ∈ [M1 − 1, M1 + 1] and M1 = Ω(min{n, ϵ s }), such that √ m ∥A(D)S − q(D)S ∥2 = Ω(min{1, nϵ s }) with probability at least 2/3. Then, consider the insensitive components. Denote k ∗ ∈ argmaxk∈[(m−ms )] {k(T V (k) )2 }, note that for the change of the insensitive components, if we only change the insensitive component where the indice corresponding to {T V (k) }k∈[k∗ ] , the algorithm becomes ( T Vϵ(k) , δ)-DP. For this, we construct DU = Pn ∗ ∗ {e′1 , . . . , e′n } ⊆ {− √1k∗ , √1k∗ }k ∪ 0ms −k . Applying Lemma A.7, we know there exists DU with ∥ i=1 ei ∥ ∈ √ √ k∗ (T V (k∗ ) )2 k∗ (T V (k∗ ) )2 }), }) [M2 −1, M2 +1] and M2 = Ω(min{n, such that ∥A(D) −q(D) ∥ = Ω(min{1, U U 2 ϵ nϵ with probability at least 2/3. p p Pn If we set di = ei ⊕e′i , we have: ∥ i=1 di ∥2 ∈ [ M12 + M22 − 2, M12 + M22 + 2]. Combining the discussion of the two paragraphs above, this happens at least probability 1/3. 22

Set d = (x, y) and consider the following convex loss function as: ℓ(θ; d) = −θ⊤ d, s.t. ∥θ∥2 ≤ 1. Then with probability 1/3, F (θpriv , D) − F (θ̂, D) = ∥

n X

di ∥2 (1 − (θpriv )⊤ θ̂)

i=1 n 1 X ∥ di ∥2 ∥θpriv − θ̂∥22 2n i=1 ! p M12 + M22 =Ω n   q   ms + maxk∈[(m−ms )] {k(T V (k) )2 }  . = Ω min 1,   nϵ

≥

A.5

Proof of Theorem 4.4

Theorem 4.4 (Guarantees of CorrDP with In-Sample TV Estimation). When the estimator in Definition 4.3 is used for the noise terms σi , Assumptions 4.1 and 4.2 hold, and n = Ω(log(1/δ)), then Algorithm 1 is (ϵ, 2δ)-CorrDP and achieves the same utility guarantee as Theorem 3.9. m2

Proof. Without loss of generality, we consider each T V (i) > ms2 for i ∈ U. Otherwise, the estimation error procedure does not introduce any privacy loss since the noise scale formula is the same. Following the same notation as in the proof of Theorem 3.7, we still compare distributions P and Q. However, P and Q become 2 g N (µD , diag(σP2 )) and N (µD′ , diag(σQ )) with different variance terms depending on the estimation of T V, ′ 2 2 which depends on D and D further. Setting C = (log(1/δ) + 1)L and T = Θ(n ) in (4), then p g g log((m − ms )/δ) CT T V D (i) CT V D (i) C d 2 σi = = = 2 (T V D (i) + 2c2 ). n 2 ϵ2 ϵ2 ϵ nγ We compute the moment privacy loss: αM (λ; D, D′ ) =

m X λ+1 λ 1 2 2 2 2 [ log σQ,i − log σP,i − log((λ + 1)σQ,i − λσP,i )] 2 2 2 i=1

λ(λ + 1) X [(µD − µD′ )i ]2 2 − λσ 2 . 2 (λ + 1)σQ,i P,i

(16)

i∈[m]

λϵ For the privacy guarantee, following Lemma A.1, it is equivalent to showing αM (λ; D, D′ ) ≤ T d(D,D ′ ) with probability 1 − δ in this case. Compared√with the proof in Theorem 3.7, we only focus on the change in the log((m−ms )/δ) d noise term from T V (i) to T V D (i) + 2c2 . nγ g Based on Assumption 4.1, we have: T V (i) ≤ T V (i), ∀i ∈ U with probability 1 − δ. We then want to bound the right-hand side in the first line and second lines of (16). We can bound the first part (i.e., the first line in (16)), through an application of Lemma A.9, stated below.

Lemma A.9 (Bounds on Variability Loss). Let λ and u be any constants. Suppose (n, v) satisfies n ≥ 10C max{λ,1} and |u − v| ≤ C u n for some constant C > 0. Then, (λ + 1) log u − λ log v − log[(λ + 1)u − λv] ≤ 23

2λ(λ + 1)C 2 . 3n2 u2

(17)

g g d d Specifically, the sensitivity of the estimand |T V D (i) − T V D′ (i)| = |T V D (i) − T V D′ (i)| ≤ Cn2 . For each component i, we then bound it by

2λ(λ+1)C22 2

g 3n2 T V D (i)

2λ(λ+1)C 2

λϵ , here the last inequality holds as long as ≤ 3n2 T V 2 (i)2 ≤ 4T P∗

2 2 ϵ T VP∗ (i) T ≤ n (λ+1)C , which can be satisfied when T = Θ(n2 ). 2 2

For the second part (i.e., the second line in (16)), we only need to focus on the indices i ∈ U. More specifically, for |λ| ≤ C2 , keeping other terms except T V in (4) as constant, for each component i ∈ [m], we have: 2 (λ + 1)σQ (i) − λσP2 (i)

p p log((m − ms )/δ) log((m − ms )/δ) d d = (λ + 1)(T V D′ (i) + 2c2 ) − λ(T V D (i) + 2c2 ) γ n nγ p log((m − ms )/δ) c3 d d d + λ(T V D′ (i) − T V D (i) + ) ≥T V D (i) + c2 nγ n ≥ T V (i). λ2 c2

3 where the first inequality follows from the fact n2(1−γ) ≥ c2 log((m−m = Θ(log(1/δ)). Then we can show s )/δ) 2 [(µD −µD′ )i ]2 [(µD −µD′ )i ]2 λ(λ+1) P λ(λ+1) P λϵ ≤ ≤ 2T d(D,D ′ ) , where the latter inequality follows i∈[m] (λ+1)σ 2 −λσ 2 i∈[m] 2 2 T V (i)2 Q,i

P,i

from the proof in Theorem 3.9. Note that we do not need to consider the case T VP∗ (i) = 0 for some feature i ∈ U that are independent d with check. That is, if we find T V D (i) ≤ √ the sensitive features, which can be done via a preprocessing √ c2

log((m−ms )/δ) , then with probability 1 − δ, T V (i) ≤ c2 nγ

log((m−ms )/δ) , ∀i ∈ U. nγ

The utility guarantees can be derived with the same rate with respect to n as in Theorem 3.9. This P σ2

is because, P i∈[m] σ′2i = Θ(1) comparing the noise σ without in-sample estimation and the noise σ ′ with i∈[m] i √ m in-sample estimation. Following the convexity condition there, we can still derive the rate Õ nϵ s . A.5.1

Proof of Lemma A.9

Proof. Define ∆ = v − u. Therefore, (λ + 1) log u − λ log v − log (λ + 1)u − λv = (λ + 1) log u − λ log(u + ∆) − log(u − λ∆) ∆ λ∆ = −λ log 1 + − log 1 − . u u For |x| ≤ 1/10, the following inequality holds: 2 − log(1 + x) ≤ −x + x2 . 3 Applying this bound to x = ∆/u and x = −λ∆/u, we obtain ∆ ∆ 2 ∆2 ∆ 2λ ∆2 −λ log 1 + ≤ −λ − = −λ + , 2 u u 3u u 3 u2 λ∆ ∆ 2λ2 ∆2 − log 1 − ≤λ + . u u 3 u2 Summing the two inequalities cancels the linear terms and yields ∆ λ∆ 2λ(λ + 1) ∆2 −λ log 1 + − log 1 − ≤ . u u 3 u2

(18)

By assumption |∆| ≤ C/n, hence max{λ, 1}|∆| max{λ, 1}C ≤ . u nu , then If n ≥ 10C max{λ,1} u

|∆| 1 ≤ , u 10

λ|∆| 1 ≤ , u 10

so the inequality (18) applies. Finally, using ∆2 ≤ C 2 /n2 gives ∆ 2λ(λ + 1)C 2 λ∆ 2λ(λ + 1)∆2 −λ log 1 + ≤ . − log 1 − ≤ u u 3u2 3n2 u2

Additional details from Section 2

B.1

Definitions and variants of differential privacy

We provide the definitions of (global) differential privacy, semi-differential privacy and metric-differential privacy for completeness and further comparison. Definition B.1 ((Global) Differential Privacy [Dwork, 2006]). A randomized algorithm A is (ϵ, δ)-differentially private if for all neighboring databases D, D′ and for all potential output parameters R in the output space of A, we have: P(A(D) ∈ R) ≤ eϵ P(A(D′ ) ∈ R) + δ. Definition B.2 (Semi-Differential Privacy [Shi et al., 2022]). A randomized algorithm A is (ϵ, δ)-semidifferentially private if for all neighboring databases D, D′ (that differ in some selected features of a single example) and for all potential output parameters R in the output space of A, we have: P(A(D) ∈ R) ≤ eϵ P(A(D′ ) ∈ R) + δ. Definition B.3 (Metric-Differential Privacy [Andrés et al., 2013]). A randomized algorithm A is (ϵ, δ) metric-differentially private if for all neighboring databases D, D′ , and for all potential output parameters R ˜ ·), we have: in the output space of A, for some distance metric d(·, ′

P(A(D) ∈ R) ≤ eϵd(D,D ) P(A(D′ ) ∈ R) + δ. Comparison between CorrDP and metric DP. Although both CorrDP and metric DP provide privacy guarantees that account for variations in data similarity, there are key differences worth highlighting. In metric DP, common distance types set in d˜ include Euclidean distance, Wasserstein distance, angular distance, and temporal distance, which all impose stronger privacy constraints if two elements are close naturally. However, existing literature on metric DP has not explored formalizations to capture feature correlation as CorrDP does. Under metric DP, it is possible to capture feature correlation by setting ˜ D′ ) = 1{eS ̸=(e′ )S } + κ1{eS =(e′ )S ,eU ̸=(e′ )U } for some κ > 1. However, this definition would still not account d(D, for dependencies across features without a proper value of κ. In contrast, the definition in CorrDP naturally captures feature correlation.

Comparison between CorrDP and Attribute Privacy [Zhang et al., 2022b]. The attribute privacy notion in Zhang et al. [2022b] is designed to protect an entire column (attribute) across the whole database, e.g., prevent an attacker from learning the distribution of a sensitive attribute in the population. However, CorrDP is a row-level privacy notion that protects each individual’s record via correlations between sensitive and insensitive features. Additionally, our work and Zhang et al. [2022b] consider different adversarial models. In the attribute privacy of Zhang et al. [2022b], leaking one individual’s information is allowed as long as the column statistics remain hidden. However, in CorrDP, the influence of any single individual needs to be explicitly controlled. Comparison between CorrDP and Label DP. As can be seen from Definition 2.2, LabelDP is a special case of CorrDP, where the labels Y are treated as sensitive features and the inputs X are insensitive components, provided X and Y are independent. However, this inclusion does not hold in the DP-ERM setting. Since ERM aims to predict Y from X, the independence assumption between X and Y does not hold. Under CorrDP, the change in insensitive input features leads to changes in the sensitive components (i.e., labels), which must be protected. In contrast, LabelDP assumes that all input features are public and do not contribute to privacy leakage, focusing solely on protecting privacy of labels.

B.2

Properties of CorrDP

Many properties of standard differential privacy are preserved under CorrDP, including post-processing, composition, and (under appropriate conditional) subsampling. Proposition B.4 (Basic Properties of CorrDP). Let M be a randomized mechanism that satisfies (ϵ, δ)CorrDP with respect to a protected feature set S and a dataset-dependent correlation metric d(·, ·). Then the following properties hold. 1. Post-processing. For any (possibly randomized) measurable mapping f , the composed mechanism f ◦ M also satisfies (ϵ, δ)-CorrDP with respect to the same S and d. 2. Composition. Suppose M1 and M2 are independent mechanisms that satisfy (ϵ1 , δ1 )-CorrDP and (ϵ2 , δ2 )-CorrDP, respectively, with respect to the same protected feature set S and the same correlation metric d. Then their sequential composition (M1 , M2 ) satisfies (ϵ1 + ϵ2 , δ1 + δ2 )-CorrDP. 3. Subsampling. Let Sub be a (possibly randomized) subsampling procedure, and consider the subsampled f mechanism M(D) := M(Sub(D)). Suppose M satisfies (ϵ, δ)-CorrDP with respect to a correlation metric dsub (·, ·) defined on subsampled datasets, dsub (Sub(D), Sub(D′ )) = d(D, D′ ) f satisfies (ϵ, δ)-CorrDP with respect to the almost surely with respect to the randomness of Sub. Then M same protected feature set S and the same correlation metric d. Proof. We prove each property directly from the definition of CorrDP. Post-processing. Fix any measurable set E in the output space of f ◦ M. Then there exists a measurable set F in the output space of M such that Pr[f (M(D)) ∈ E] = Pr[M(D) ∈ F ]. Therefore, for any pair of datasets D, D′ , ′

′

Pr[f (M(D)) ∈ E] = Pr[M(D) ∈ F ] ≤ eϵ/d(D,D ) Pr[M(D′ ) ∈ F ] + δ = eϵ/d(D,D ) Pr[f (M(D′ )) ∈ E] + δ. Hence f ◦ M satisfies (ϵ, δ)-CorrDP. Composition. This result follows immediately from Theorem B.1 in Dwork and Roth [2014] by replacing ϵ ϵ there with d(D,D ′) . 26

Subsampling under correlation stability. Fix any measurable set A. Conditioning on the randomness of Sub and using that M is (ϵ, δ)-CorrDP with respect to dsub , h i f Pr[M(D) ∈ E] = E Pr[M(Sub(D)) ∈ E | Sub] h i ′ ≤ E eϵ/dsub (Sub(D),Sub(D )) Pr[M(Sub(D′ )) ∈ E | Sub] + δ . By the assumed stability condition, we have: h i ′ f Pr[M(D) ∈ E] ≤ eϵ/d(D,D ) E Pr[M(Sub(D′ )) ∈ E | Sub] + δ ′ f ′ ) ∈ E] + δ. = eϵ/d(D,D ) Pr[M(D

f satisfies (ϵ, δ)-CorrDP. Therefore M

B.3

Other distance measures in CorrDP

Here we consider two other potential distance measures that could be used used in the CorrDP framework beyond TV distance, to demonstrate that other distance measures can be used as well. Any choice of distance measure should simply satisfy the axioms of Definition 2.3 and satisfy Assumptions 4.1 and 4.2. Hellinger distance.

Hellinger distance is defined as: sZ p p 1 ( P(x) − Q(x))2 dx. H(P, Q) = √ 2

Like TV distance, Hellinger distance is bounded between 0 and 1, and thus H(·, ·) can be used in place of T V (·, ·) in Definition 2.5. Furthermore, in terms of empirical estimation, similar to Assumptions 4.1 and 4.2, Hellinger distance has well-understood concentration properties, which could be utilized for convergence results [Rohde and Steinberger, 2020, Sart, 2023], and it exhibits low sensitivity to changes in individual data points, which would enable similar results to Theorem 4.4. Wasserstein Distance. Wasserstein Distance measures the minimal cost of transforming one distribution into another, and is defined as: W (P, Q) =

inf γ∈Π(P,Q)

E(x,y)∼γ [∥x − y∥],

where Π(P, Q) is the set of joint distributions with marginals P and Q. With advantageous analytical properties such as computationally tractability and computability from finite samples, it has been used in text document similarity measurement [Li and Pang, 2024], domain adaptation [Rakotomamonjy and Liva, 2021], and generative adversarial networks [Liu et al., 2023]. Under certain regularity conditions (e.g., bounded support), Wasserstein distance satisfies the required sensitivity and concentration assumptions.

Additional details from Section 3

C.1

Utility guarantee of CorrDP-SGD of other losses

Under other conditions of F (θ, D), we can strengthen the accuracy guarantee as follows: Corollary C.1. Under Assumptions 3.1, 3.2, 3.3 and 3.4 (as well as F (θ, D) is G-smooth with respect to θ), P if i∈U T V (i) = Θ(ms ) and we apply Algorithm 1 with αt = Θ(1/G):

• If F (θ, D) satisfies Polyak-Lojasiewicz condition with respect to θ [Karimi et al., 2016], i.e., ∥∇θ F (θ, D)∥22 ≥ 2µ(F (θ, D) − F (θ̂, D)) for some µ > 0 for any θ, then R(θpriv ) = O nm2 ϵs2 if we set θpriv = θT +1 ; √ m • For general F (·, ·), E[∥∇θ F (θpriv , D)∥22 ] = Õ nϵ s if we set θpriv = θm where m is uniformly sampled from {1, . . . , T }. Proof. In both cases, from Inequality (15) and X

B σi2 ≤

i∈[m]

D2 T log(1/δ) n2 ϵ2

i∈U T V (i) = Θ(ms ), we have:

! ms + min{

T V (i), ms /4}

=Θ

i∈U

ms T log(1/δ) n 2 ϵ2

(19)

First if F (θ, D) satisfies Polyak-Lojasiewicz condition and is G-smooth, we have: 1 1 E[F (θt+1 , D) − F (θt , D)] ≤ E − ∇θ F (θt , D)⊤ (∇θ F (θt , D) + b) + ∥∇θ F (θt , D) + b∥2 G 2G 1 1 =− ∥∇θ F (θt , D)∥2 + E[∥b∥2 ] 2G 2G P 2 µ i∈[m] σi ≤ − (F (θt , D) − F (θ̂, D)) + G 2G where the first inequality follows by F (θ, D) is G-smooth and the stepsize αt = Θ(1/G). The second inequality follows from the Polyak-Lojasiewicz condition. Rearanging the terms and summing over t = 1, . . . , T , recall θpriv = θT +1 , the definition of R(θ) and the bound in Inequality (15), we have: P T i∈[m] σi2 µ T µ T ms T log(1/δ) priv R(θ )≤ 1− ≤ 1− R(θ1 ) + R(θ1 ) + O . G 2G G n 2 ϵ2 n2 ϵ2 , we have the utility guarantee: Then, setting T = O log ms log(1/δ) R(θ

priv

ms log(1/δ) ) ≤ O log (n) n 2 ϵ2 2

= Õ

m s

n 2 ϵ2

Second, for the general case of F (θ, D), denote the noise imposed at the step t as bt , we have: 1 1 ⊤ 2 ∥∇θ F (θt , D) + bt ∥ E[F (θt+1 , D) − F (θt , D)] ≤ E − ∇θ F (θt , D) (∇θ F (θt , D) + bt ) + G 2G 1 1 ∥∇θ F (θt , D)∥2 + E[∥bt ∥2 ]. =− 2G 2G From this, we have: P 2 1 i∈[m] σi 2 ∥∇θ F (θt , D)∥2 ≤ E[F (θt ) − F (θt+1 )] + . 2G 2G P Then Em,{bt }t∈[T ] [∥∇θ F (θm , D)∥2 ] = T1 i∈[T ] Ebi [∥∇θ F (θt , D)∥2 ]. Rearanging the above terms and summing over t = 1, . . . , T , we have: X 2G(F (θ1 , D) − E[F (θT +1 , D)]) + σi2 T i∈[m] X 2GR(θ1 ) 2GR(θ ) ms T log(1/δ) 1 2 ≤ + σi ≤ +O , T T n 2 ϵ2

E[∥∇θ F (θpriv , D)∥22 ] = Em [∥∇F (θm , D)∥22 ] ≤

i∈[m]

where the second inequality follows by the fact E[F (θ T +1 , D)] ≥ F(θ̂, D), and the third inequality follows by the bound in Inequality (15). Then, setting T = O

√

p E[∥∇θ F (θ

C.2

priv

, D)∥22 ] = Õ

nϵ ms log(1/δ)

ms log(1/δ) nϵ

, we have the utility guarantee: √

ms nϵ

= Õ

Additional discussions and relaxations of assumptions

In this subsection, we provide additional discussions and examples of relaxing the various modeling assumptions. For the relaxing assumptions, we consider cases where (i) the gradient and domain assumptions are violated; (ii) sensitive and insensitive features are not distinguished clearly; and (iii) label privacy. Relaxations of Gradient and Domain Assumptions. We can relax Assumptions 3.3 and 3.4 with the following alternative: Assumption C.2 (Relaxation of Bounded Domain and Gradients). There exists some constant C, such that:   X (∇θ ℓ(θ; (x1 , y)) − ℓ(θ; (x2 , y)))i ≤ CL 1x(i) ̸=x(i) + 1/m 1x(j) ̸=x(j)  , ∀i 1

j̸=i

This assumption does not require that both gradients and domains are bounded. Instead, it only requires that the gradient can possibly change in a bounded range. Therefore, Assumption C.2 is a variant of the bound derived in the proof of Theorem 3.7 to ensure the validity of our results. Corollary C.3. Under Assumptions 3.1, 3.2, C.2, for ϵ, δ > 0, Algorithm 1 is (ϵ, δ)-CorrDP. This corollary follows the same proof as Theorem 3.7, where the only difference is to replace Equation (11), which comes from Assumptions 3.3 and 3.4, with Assumption C.2. Relaxations of Distinction between Sensitive and Insensitive Features. Building on our basic binary categorization for sensitive and insensitive features, it is possible to incorporate a generalization to continuous sensitivity scores to allow different levels of protections across features. We can instead consider a sensitivity score si ∈ [0, 1] for each feature, with the special case of binary distinctions captured as si = 0 for each sensitive feature and si = 1 for each insensitive feature. The distance d in Definition 2.5 can be modified by using these scores as a weight vector {sj }j∈[m] for each feature: d(D, D′ ) =

max

j∈[m],ej ̸=(e′ )j

(1 − sj ) max T V (PX S |ei , PX S |(e′ )i ) + sj . i:i⊆[m]

To demonstrate the key properties of this augmented definition, note that if e and e′ differ in some completely sensitive feature with sj = 1, then d(D, D′ ) = 1, which reduces the original DP definition. On the other hand, if e and e′ only differ in some completely insensitive feature with sj = 0, then d(D, D′ ) = maxi:i⊆[m] T V (PX S |ei , PX S |(e′ )i ). Otherwise, if e and e′ differ in some semi-sensitive feature sj > 0, the proposed d could be, e.g., a weighted combination of 1 and maxi:i⊆[m] T V (PX S |ei , PX S |(e′ )i ), where the latter is the original value of distance without the continuous relaxation. This definition could be directly incorporated into the noise terms in Algorithm 1 by changing T V (i) when i ̸∈ S to: σi = (1 − si ) max T V (PX S |xU1 , PX S |xU2 ) + si . x1 ,x2 ∈X

This change would, however, lead to an increase of the noise scale added in Algorithm 1, which would in turn weaken the utility guarantee in Theorem 3.9. However, as long as there exists some si < 1 for insensitive features, the noise would be smaller than that under standard DP-SGD and would still lead to an improved utility compared to standard DP-SGD. 29

Relaxations of Label Privacy. Under our current binary framework, labels must be treated as fully sensitive if we want to protect them completely. To allow a partial level of label protection, we can introduce a label-specific scale sl ∈ [0, 1] into the distance metric d. Concretely, compared with the original d, one could use distance: ˜ D′ ) = max{sl 1{labels change} , d(D, D′ )} ∈ [0, 1]. d(D, Here sl = 1 recovers full DP protection on the label (so d˜ = 1 whenever it changes), while sl = 0 treats it as fully public. With this d˜ in hand, the CorrDP-SGD noise terms in Equation (4) simply change from max{T V (i), m2s /m2 } to max{T V (i), m2s /m2 , sl } and the proof of Theorem 3.7 goes through identically. Note that we incorporate sl into the noise scale of all insensitive features since changing labels affects all gradient coordinates. Then as long as sl is smaller than 1, CorrDP still provides meaningful utility improvements compared with classical DP due to smaller noise scales.

Additional Details in Section 4

In this appendix, we present concrete examples with two features that satisfy Assumptions 4.1 and 4.2, along with proofs that they satisfy these two assumptions. These examples are presented in Section D.1. In Section D.2, we extend to scenarios involving multiple sensitive features.

D.1

Examples satisfying Assumptions 4.1 and 4.2

In this subsection, we consider the two-feature problem with one sensitive and one insensitive feature, denoted as X S and X U respectively, in separate cases for when these features are discrete or continuous. We show n how assumptions are satisfied under the dataset D = {(xSk , xU k )}k=1 . X U is discrete. We discuss two cases depending on whether X S is discrete or not. When X S is discrete, we apply the following empirical estimate. Example D.1 (Estimation and Sensitivity Guarantees for Discrete Features). Suppose X S ∈ {ai | i ∈ [KS ]} and X U ∈ {bj | j ∈ [KU ]} with joint distribution P(X S = ai , X U = bj ) = pi,j . For any j ∈ [KU ], define the conditional distribution pi,j Pj (i) := P(X S = ai | X U = bj ) = P . k∈[KS ] pk,j Pn Define the empirical counts ni,j := k=1 1{xSk =ai , xUk =bj } , then the plug-in estimator of Pj is bj (i) := P ni,j P

k∈[KS ] nk,j

, ∀i ∈ [KS ],

and the corresponding empirical estimator of the total variation distance ∀j1 , j2 ∈ [KU ] is 1 d T V D (Pj1 , Pj2 ) := 2

bj1 (i) − P bj2 (i) . P

(20)

i∈[KS ]

Then, under mini,j pi,j > 0, the conditional total variation distance estimator d T VD =

max

j1 ,j2 ∈[KU ]

satisfies Assumptions 4.1 and 4.2 with parameters c2 =

d T V D (Pj1 , Pj2 ) q

log(KS KU ) 1 1 mini,j pi,j , c3 = mini,j pi,j , γ = 2 .

Proof. First, applying the multinomial concentration inequality and a union bound over (i, j), for any β ∈ (0, 1), with probability at least 1 − β, r ni,j log(KS KU /β) − pi,j ≤ uniformly over (i, j). n n 30

P Since mini,j pi,j > 0, we have nj = i ni,j = Θ(n) uniformly over j. For any j1 , j2 ∈ [KU ], consider P |c| 1 T V (Pj1 , Pj2 ) := 2 i∈[KS ] |Pj1 (i) − Pj2 (i)|. Then using the identity ab − dc ≤ |a−c| b + bd |b − d|, and applying concentration bounds to ni,j and nj , we obtain s bj (i) − Pj (i) ≤ C log(KS KU /β) , ∀i ∈ [KS ], P n mini,j pi,j for some constant C > 0. Summing over i and taking a union bound over (j1 , j2 ), s log(KS KU /β) d T V D (Pj1 , Pj2 ) − T V (Pj1 , Pj2 ) ≤ C . n mini,j pi,j Therefore, Assumption 4.1 is satisfied with c2 =

log(KS KU ) 1 mini,j pi,j and γ = 2 .

bj (i) − P b′ (i) ≤ For sensitivity, changing one sample affects at most one ni,j and one nj by 1. Hence, P j 1 1 nj ≤ n mini,j pi,j . Therefore, for any (j1 , j2 ),

d d T V D (Pj1 , Pj2 ) − T V D′ (Pj1 , Pj2 ) ≤ n min1i,j pi,j .

Taking the maximum over (j1 , j2 ) yields d d VD −T V D′ ≤ sup T

D,D ′

1 = Θ(n−1 ). n mini,j pi,j

1 Therefore, Assumption 4.2 is satisfied with c3 = mini,j pi,j .

When X S is continuous, we apply the following histogram estimate. Example D.2 (Estimation and Sensitivity Guarantees for Histogram Smoothing). Suppose X U ∈ {bj | j ∈ [KU ]} with P(X U = bj ) = pj , and X S ∈ R satisfies |X S | ≤ B. For each j ∈ [KU ], let pj (·) denote the conditional density of X S given X U = bj . PnWe partition [−B, B] into K PS bins {Bi }i∈[KS ] of equal width h. Define the empirical bin counts ni,j := S U 1 , n := ·,j k=1 {xk ∈Bi , xk =bj } i∈[KS ] ni,j . Then the histogram estimator of the conditional density is ni,j , ∀x ∈ B . The corresponding plug-in estimator of the total variation distance is pbj (x) := n·,j i h 1 d T V D (pj1 , pj2 ) := 2

Z B −B

|b pj1 (x) − pbj2 (x)| dx =

1 X 2

i∈[KS ]

ni,j2 ni,j1 − . n·,j1 n·,j2

Setting the histogram bandwidth h = Θ(n−1/3 ), then the conditional total variation estimator d T VD =

max

j1 ,j2 ∈[KU ]

d T V D (pj1 , pj2 )

satisfies Assumptions 4.1 and 4.2 with parameters c2 = B

log KS KU B 1 minj pj , c3 = minj pj , γ = 3 .

Proof. For any j1 , j2 ∈ [KU ], we decompose d T V D (pj1 , pj2 ) − T V (pj1 , pj2 ) ≤ T V (pj1 , pbj1 ) + T V (pj2 , pbj2 ). We bound each term using the standard bias–variance decomposition for histogram density estimators (see, e.g., as a special case of kernel density estimators in Chapter 1.2 of Tsybakov [2008]). For any j ∈ [KU ], s log(KS /β) 1 T V (pj , pbj ) = ∥b pj − pj ∥1 ≤ B h + , 2 nj h 31

with probability at least 1 − β. Since minj pj > 0, we have nj = Θ(n) uniformly over j with high probability. Taking h = Θ(n−1/3 ) yields s log(KS /β) T V (pj , pbj ) ≤ B . n2/3 minj pj Applying this bound to both j1 and j2 , and taking a union bound over all (j1 , j2 ), we obtain s log(KS KU /β) d T V D (pj1 , pj2 ) − T V (pj1 , pj2 ) ≤ B . n2/3 minj pj q K S KU 1 Therefore, Assumption 4.1 is satisfied with c2 = B log minj pj , γ = 3 . For sensitivity, changing one sample affects at most one bin count ni,j by ±1, and hence changes pbj by at most O(1/(nj h)) on a single bin. Therefore, ∥b pj − pb′j ∥1 ≤ nCj , which implies T V (pj1 , pbj1 ) − T V (pj1 , pb′j1 ) ≤

C C ≤ . nj n minj pj

Applying the same argument to j2 and taking the maximum over (j1 , j2 ), we obtain d d VD −T V D′ ≤ sup T

D,D ′

C = Θ(n−1 ). n minj pj

Therefore, Assumption 4.2 is satisfied with c3 = minBj pj . X U is continuous. distributed:

When X S is continuous, we present the example of estimation if X is jointly Gaussian

Example D.3 (Estimation and Sensitivity Guarantees for Gaussian Marginal Distributions). Suppose X ∼ N (µ, Σ). Define the estimators Pn ϕ̂ :=

U U S S i=1 (xi − x̄ )(xi − x̄ ) Pn , U U 2 i=1 (xi − x̄ )

ψ̂ := x̄S − ϕ̂x̄U ,

η̂ 2 :=

1X S 2 (x − ϕ̂xU i − ψ̂) . n i=1 i

(21)

The empirical conditional distribution estimator is Pbu := N (ϕ̂u + ψ̂, η̂ 2 ), and the plug-in estimator of the conditional total variation distance is d T V D (u1 , u2 ) := T V (Pbu1 , Pbu2 ). Then the conditional total variation estimator U d d T V D := max T V D (xU i , xj ). 1≤i,j≤n

√

satisfies Assumptions 4.1 and 4.2 with parameters c2 = C

log n , c3 = Cη , γ = 12 for some constant C. η

S U 2 Proof. First, for any u, the conditional distribution satisfies X |S X = u ∼ N (ϕu + ψ, η ) for some X ΣSS ΣSi ϕ, ψ, η ∈ R determined by µ, Σ. For each X (i) = xi , i ∈ U, given ∼ , then the posterior ΣiS Σii X (i) distribution X S ∼ N (µ̂S (xi ), Σ̂S (xi )) with:

µ̂S (xi ) := µS|xi = µS + ΣSi Σ−1 ii (xi − µi ), 32

Σ̂S (xi ) := ΣSS − ΣSi Σ−1 ii ΣiS .

(22)

For any u1 , u2 ∈ R, we have Puk = N (ϕuk + ψ, η 2 ),

Pbuk = N (ϕ̂uk + ψ̂, η̂ 2 ),

k = 1, 2.

Since the two Gaussian distributions have the same variance within each pair, |ϕ| |u1 − u2 | T V (pu1 , pu2 ) = 2Φ − 1, 2η

|ϕ̂| |u1 − u2 | d T V D (u1 , u2 ) = 2Φ 2η̂

! − 1,

with Φ(·) is the c.d.f. of the standard normal distribution. Therefore, |ϕ̂| |u1 − u2 | |ϕ| |u1 − u2 | d T V D (u1 , u2 ) − T V (pu1 , pu2 ) ≤ 2 sup Φ′ (t) − 2η̂ 2η t∈R 1 |ϕ̂| |ϕ| ≤ √ |u1 − u2 | − η̂ η 2π Next, |ϕ̂| |ϕ| 1 1 1 − ≤ |ϕ̂ − ϕ| + |ϕ| − . η̂ η η̂ η̂ η By standard concentration for least-squares estimators (21), with probability at least 1 − β, r r log(1/β) log(1/β) |ϕ̂ − ϕ| ≤ C , |η̂ − η| ≤ C . n n p Moreover, since x ∼ N (µ, Σ), max1≤i≤n |xU log(n/β) with probability at least 1 − β, so that for i | ≤ C U u1 , u2 ∈ {xU , . . . , x }, n 1 p |u1 − u2 | ≤ C log(n/β). √ log(n/β) d V D (u1 , u2 ) − T V (pu1 , pu2 ) ≤ C η√n . Therefore, Assumption 4.1 is Combining these bounds yields T satisfied with γ = 12 and c2 = C

√

log n for some constant C. η

For sensitivity, changing one sample perturbs ϕ̂ and η̂ by at most O(n−1 ). Since Φ is Lipschitz and d d d T V D (u1 , u2 ) depends smoothly on ϕ̂/η̂, it follows that T VD −T V D′ ≤ Cη · n1 = Θ(n−1 ). Therefore, Assumption 4.2 is satisfied with c3 = η1 . When X S is discrete, we can run a multi-class logistic regression to estimate the likelihood P (X S |XU = u) and calculate the TV distance based on the definition. When the parametric distribution assumption does not hold and X S is discrete, the kernel density estimates satisfy the same rate as Example D.2.

D.2

Extensions to Multiple Sensitive Features

Our previous examples can also be extended to include multiple sensitive features. In particular, the key arguments carry over with modified dimensional dependence: Q 1. When X S and X U are both discrete, let X S ∈ k∈[ms ] {a1,k , . . . , aKS,k ,k } denote a vector of ms categorS U ical sensitive features. Then the joint distribution can be written as P X = (ai1 ,1 , . . . , aims ,ms ), X = bj = pi1 ,...,ims ,j . Applying the same uniform concentration arguments as in Example D.1 over all joint r Q log ( k∈[ms ] KS,k )·KU categories, we obtain c2 = mini ,...,i ,j pi ,...,i ,j , γ = 21 . 1

2. When X S can be continuous and X U is discrete, we partition the space of the entire X S into bins P {Bj }. The empirical density estimator becomes p̂j (x) =

S U k∈[n] 1{xk ∈Bj , xk =bj } nj hms

. Then using the same q 1 bias–variance decomposition as in Example D.2, the estimation error scales as O(h) + O . m s nh Then balancing the two terms in the estimation error with h = Θ(n−1/(ms +2) ) yields γ = ms1+2 . 3. When (X S , X U ) follows a joint Gaussian distribution, the conditional distribution X S | X U remains Gaussian with parameters given by (22). Therefore, the same total variation bounds as in Example D.3 apply component-wise, yielding γ = 12 by Proposition 2.1 of Devroye et al. [2018]. General Guideline for Multivariate Mixed Features. We can apply the kernel estimate to estimate distance when X S is high-dimensional with both discrete and continuous features via a product kernel, i.e., a Gaussian kernel for continuous features and a discrete kernel for discrete features, which is automated in standard statistical packages (e.g., Hayfield and Racine [2008]). In general, to estimate T V (PX S |X U =x1 , PX S |X U =x2 ) from D when X U is continuous and X S is continuous, the following methods can be used: • Nonparametric methods: Use a kernel in X U -space and define weights to construct weighted empirical distributions. Compute (or approximate) the TV distance of these two estimated distributions. For each X U = x, Kh (xU i − x) wi (x) = Pn , U j=1 Kh (xj − x) Pn and estimate p̂x (s) = i=1 wi (x1 )Kh (s − xSi ). Then we can estimate the TV distance via kernel density or histogram. • Parametric methods: Fit a parametric form for P (X S |X U = x), e.g., Gaussian distribution in Example D.3. This way, we can compute TV distance in a closed form or a simple integral or binned manner. High-Dimensional Estimation. When an analytical solution is unavailable or in a very high dimension, TV distance can be estimated using Monte Carlo sampling. For problems with very high dimensions, one can leverage generative modeling techniques (e.g., f -GANs and variational representations) to approximate TV distance since T V (P, Q) = sup∥f ∥∞ ≤1 EP [f (X)] − EQ [f (Y )], and f can be approximated with some parametrized fθ as a discriminated network with clipping for bounded output. More importantly, exact estimation of TV distance is not necessary – our framework only requires an upper bound that is not overly loose, as discussed in Section 4.

Additional details on experiments

All experiments were run on a PC laptop with Processor 8 Core(s), Apple M1 with 16GB RAM. It took around 40 hours to run all the experiments. All classification and regression problems are implemented through scikit-learn and PyTorch. We restrict the neighboring databases to allowing changes in sensitive features or one of the insensitive features.

E.1

Synthetic data

Gradient Descent. For each private and non-private algorithm, we apply full gradient descent on the ridge regression loss over the entire dataset at each step, using a fixed step size α = 0.001. The total number of iterations is set to T = 4000.

TV Distance Estimation. For two neighboring databases, we permit changes to only one insensitive feature. Given the marginal distribution over both sensitive and insensitive features X ∼ N (µ, Σ), there are two different cases: • For those features with indices i%2 = 0, i.e., the prior mean µi = −1; • For those features with indices i%2 = 1, i.e, the prior mean µi = 1. T V (i), we ensure Following the estimators specified in Equation (22) and recalling that σi2 = C log(1/δ)+1 ϵ2 p p ′ the (ϵ, δ)-CorrDP guarantee by setting xi = µi − 2 log(2ms /δ), xi = µi + 2 log(2ms /δ) such that the i-th component is bounded within [xi , x′i ] with probability 1 − 2δ , ∀i ∈ [ms ]. For the empirical estimate, we use the empirical mean and variance from the dataset. Additional Results. To demonstrate the robustness of our method relative to the Standard baseline, we vary the number of sensitive features ms to 5, 20, 50, 80 (corresponding to 0.05m, 0.2m, 0.5m, 0.8m), with the results presented in Figure 2. We observe qualitatively similar results as in the main body (compare to Figure 1a), suggesting that the number of sensitive features does not impact the overall findings. Algorithm corr

standard 12

partial

Utility gap

semi

40 30

10 0

0 0.05

0.10

0.15

0.20

0.25

User-level ε

0.30

0.35

0.40

0.05

0.10

(a) ms = 0.05m

0.15

0.20

0.25

User-level ε

0.30

0.35

0.40

(b) ms = 0.2m

12 10

standard corr semi

Utility gap

8 6 4

6 4 2

2 0

0 0.05

0.10

0.15

0.20

0.25

User-level ε

0.30

0.35

0.40

0.05

0.10

0.15

0.20

0.25

User-level ε

0.30

0.35

0.40

(d) ms = 0.8m

Figure 2: Privacy-utility trade-offs for least-square regression under (ϵ, δ)-DP or (ϵ, δ)-CorrDP on synthetic data.

E.2

Adult dataset [adu]

Gradient Descent.

We categorize all features as follows: Table 1: Feature Categorization of Adult Dataset

Continuous Discrete

Sensitive

Insensitive

age, educational-num, hours-per-week martial-status, relationship

fnlwgt race, gender, workclass

We optimize the standard logistic regression loss ℓ(θ; (x, y)) = −(y log σ(θ⊤ x) + (1 − y) log(1 − σ(θ⊤ x))) for binary y ∈ {0, 1}, where σ(u) = 1/(1 + exp(−u)). For each private or non-private algorithm, we apply the full gradient descent to the whole dataset at each step with a fixed step size α = 0.05. We set the total iteration number T = 5000. TV Distance Estimation. For two neighboring databases, we permit changes to only one insensitive feature. This introduces two additive contributions to the TV distance: one from the continuous sensitive features and one from the discrete sensitive features. For a particular insensitive feature xu , x′u , we take a rough upper bound for calculating the sum of the conditional distance with respect to the sensitive continuous features X S,c and discrete features X S,d : max T V (PX S |xu , PX S |x′u ) ≤ max{ max′ T V (PX S,c |xu , PX S,c |x′u ) + max′ T V (PX S,d |xu , PX S,d |x′u ), 1}

xu ,x′u

xu ,xu

• For discrete insensitive features u ∈ {race, gender, workclass}: – To obtain the discrete distribution PX S,d |xu , we apply the multiclass logistic regression (‘multinomial’) and estimate the probability of all the value combinations of all the discrete variables. Then we calculate the TV distance of these two discrete distributions by its formula and find the maximum xu , x′u to obtain T V (u). – To obtain the continuous distribution PX S,c |xu , we use the empirical distribution with data points with Xu = xu . Then we calculate the TV distance by histogram approximation as Example D.2. • For continuous insensitive features u ∈ {fnlwgt}: – To obtain the discrete distribution PX S,d |xu , we apply the multiclass logistic regression (‘multinomial’) and estimate the probability of all the value combinations of all the discrete variables. Then we calculate the TV distance by its formula and find the maximum pair xu , x′u to obtain T V (u). – To obtain the continuous distribution PX S,c |xu , we model them as Gaussian and apply Equation (22) to estimate the posterior, with xu = 0, 1 (since we do MinMaxScaler and each resulting feature lies in [0, 1]). Then we calculate the TV distance by integral following Example D.3. Additionally, we assign identical noise levels to all one-hot encoding columns corresponding to the same raw feature. The resulting privacy noise scales for each insensitive feature are reported in Table 2. Table 2: Relative privacy noise scale for insensitive features in Adult dataset (Note that 1 means the same relative privacy noise scale as sensitive features) Feature Name

race

gender

workclass

fnlwgt

Scale

0.23

0.90

0.22

Notably, workclass is highly correlated with the features educational-num, hours-per-week. Consequently, despite not being classified as a sensitive feature, workclass requires a relatively high level of privacy protection owing to its correlation with the sensitive features. 36

E.3

Sepsis dataset [sep]

Gradient Descent. For the neural network, we use a batch size of 1024 and constant step size of 0.005, with a total of T = 200 iterations. In each iteration, we clip the gradient norm to 5. The private scale only applies to the insensitive components U of weight and the bias in the first layer. Denote ŷ = σ2 (w2⊤ σ1 (w1 x + b1 ) + b2 ). Then for w1 ∈ R5×3 , b ∈ R5 , and the privacy scale only applies to the parameter estimate of (w1 )i,j , bi , ∀i ∈ [5], j ∈ U . TV Distance Estimation. Recall that we sex and episode number are considered insensitive features, and age is considered the sensitive feature, and that sex and episode number are categorical, with 2 and 5 categories respectively. For two neighboring databases, we allow changes of both insensitive features. Therefore, we calculate the max TV distance between the conditional distribution of age on all 10 joint parameter combinations of sex and episode number. We obtain T Vmax = 0.3, ∀i ∈ {sex, episode number} using histogram approximation.

E.4

Credit Card dataset [cre]

Gradient Descent. For the logistic regression model, we apply the full gradient descent to the whole dataset at each step, with a fixed step size α = 0.005 and a total of T = 2000 iterations. TV Distance Estimation. Recall that the insensitive features are sex, education, marriage, and age. We use the histogram estimate to compute T V (sex) = 0.103, T V (education) = 0.8113, T V (marriage) = 0.8295, T V (age) = 1. All discrete features are encoded using one-hot encoding.

E.5

Medical Cost dataset [med]

Gradient Descent. For the linear regression model, we apply full gradient descent over the entire dataset at each step with a fixed step size α = 0.001 and T = 5000 iterations. For the neural network, we use a batch size of 1000, a constant step size of 0.005, and T = 1000 iterations, with gradient norms clipped to 10 at each step. As before, the private scale only applies to the insensitive components U of weight and the bias in the first layer. TV Distance Estimation. We set age, sex, region as insensitive features, and bmi, children, smoker as sensitive features. After one-hot encoding, the dataset contains 8 features in total and compute T Vmax = 0.36.

Record · ID 155278 · SHA-256 7c4b4c7f9970ed31
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.