Beyond Monolithic Perturbation: Heterogeneous Mechanism Design for Multi-Attribute Metric Differential Privacy

Beyond Monolithic Perturbation: Heterogeneous Mechanism Design for Multi-Attribute Metric Differential Privacy Ruiyao Liu, Michael Oluwole, and Chenxi Qiu

arXiv:2610.05561v1 [cs.CR] 4 Oct 2026

University of North Texas Denton, USA

Abstract—Multi-attribute user records are inherently heterogeneous, often combining continuous, categorical, and binary attributes, and they frequently exhibit strong cross-attribute dependencies. Designing high-utility metric differential privacy (mDP) mechanisms for such records is challenging. Simple predefined mechanisms, such as distance-based noise, may be poorly aligned with task-specific utility loss, whereas fully optimization-based mechanisms can be computationally prohibitive for multi-attribute records. We propose Dependency-aware Heterogeneous Data Perturbation (DepHDP), a framework for multi-attribute mDP that combines dependency-aware attribute grouping with heterogeneous perturbation design. Rather than applying a one-sizefits-all mechanism, DepHDP selects an appropriate perturbation strategy for each attribute or attribute group, choosing between efficient predefined mechanisms, such as Laplace or Exponential mechanisms, and optimization-based designs. This selection is guided by both domain size and a predefined-noise adequacy criterion, which quantifies whether task-induced utility loss can be well explained by perturbation magnitude. To support scalable end-to-end optimization, DepHDP estimates grouplevel utility loss through sampling and lightweight surrogate modeling, and jointly optimizes privacy-budget allocation and group-wise mechanism design under a global ℓp -metric mDP constraint. Across three case studies, DepHDP improves privacy– utility trade-offs over uniform baselines at lower computational cost than full-record OPT on evaluated domains.

1. Introduction Modern data-driven systems increasingly rely on multiattribute user records that combine heterogeneous data types, such as continuous locations, categorical device types, and binary indicators. A common collection-time protection is local differential privacy (LDP) [1], where each user perturbs her record before sharing it with an untrusted server. However, standard ϵ-LDP does not distinguish between nearby and distant records: all distinct inputs must satisfy the same indistinguishability requirement. For multi-dimensional or multi-attribute records, this often requires substantial noise, degrading utility for tasks that depend on relative closeness, such as nearby locations or similar user profiles. Metric differential privacy (mDP) [2], also known as dX privacy [3] or Lipschitz privacy [4], addresses this limitation

by calibrating indistinguishability to a distance metric over the input space. Under mDP, closer records must be harder to distinguish than distant records, allowing mechanisms to inject less noise while retaining a formal privacy guarantee. Existing mDP mechanisms are often distance-driven. For example, Laplace-based mechanisms [2] and Exponentialmechanism variants [5] parameterize perturbation probabilities using the distance between the true and perturbed records. These mechanisms are effective when task-induced utility loss is well aligned with distance. However, for heterogeneous multi-attribute records, utility loss can be highly non-radial: perturbations with the same distance may have very different effects depending on which attribute changes and in what direction [6]. This mismatch motivates mechanisms that adapt perturbation design to attribute type, dependency structure, and task-specific loss. To better reduce utility loss, some recent works have also explored optimization-based methods (e.g., linearprogramming (LP) formulations [7], [8]) that directly optimize the mechanism for a specified loss matrix. However, such approaches often incur substantial computational overhead and scale poorly to large domains [9]; moreover, when utility is already mostly distance-determined, the improvements over distance-based predefined noise mechanisms can be modest [4]. Together, these results highlight a recurring trade-off: distance-based predefined-noise (DPN) mechanisms are typically efficient and scalable but may sacrifice utility under complex loss landscapes, whereas optimization-based mechanisms can better tailor utility at the cost of substantially higher computation. In multi-attribute records, this trade-off becomes harder to navigate: attributes can differ sharply in domain size, geometry, and task relevance, so a single perturbation strategy is rarely appropriate across all dimensions. Fig. 1 illustrates this heterogeneity using the 13 attributes collected from the UCI Heart Disease dataset [10] for the downstream task of entropy estimation. We plot each attribute’s domain size (xaxis) against the suitability of DPN (y-axis), quantified by the radial-fit score (defined in Section 3.4): higher scores indicate a more distance-aligned utility-loss landscape, under which DPN is more likely to achieve low utility loss. The figure reveals substantial variation across attributes in both domain size and radial-fit. For example, maximum heart rate achieved ("thalch") and serum cholesterol ("chol") exhibit high radial-fit scores and thus favor DPN, whereas number of

Suitability of DPN (radial-fit score)

Domain size

Figure 1. Attribute-wise preferences for perturbation mechanisms in heart disease prediction [10]. Attributes: age (age), sex (sex), cp (chest pain type), trestbps (resting blood pressure), chol (serum cholesterol), fbs (fasting blood sugar ą 120 mg/dL), restecg (resting electrocardiographic results), thalch (maximum heart rate achieved), exang (exercise-induced angina), oldpeak (exercise-induced ST depression relative to rest), slope (slope of the peak exercise ST segment), and ca (number of major vessels colored by fluoroscopy).

major vessels ("ca") also favors DPN primarily because its domain is sufficiently large that optimization becomes computationally expensive. In contrast, attributes such as sex and exercise-induced angina ("exang") have small domains and low radial-fit scores, suggesting non-radial loss patterns where optimization can more effectively tailor perturbations to the task-induced utility landscape. These observations motivate the central problem studied in this paper: heterogeneous, attribute-wise mechanism selection and optimization under a joint mDP constraint. To the best of our knowledge, systematic treatments of multiattribute mDP beyond straightforward extensions of singleattribute designs remain largely unexplored. Related works: Multi-attribute perturbation study in LDP. Notably, privacy-preserving multi-attribute data collection has also been extensively studied under LDP, but these designs do not transfer directly to the mDP setting. Existing multi-attribute LDP strategies largely follow two (often) suboptimal directions: privacy-budget splitting (SPL), which partitions a total budget across attributes [11], and random sampling (SMP), which perturbs only a subset of attributes per reporting round [12]. Hybrid variants, e.g., random sampling (RS) combined with fake data (FD), further attempt to mask unreported attributes [13]. These approaches are tailored to LDP, where indistinguishability is uniform across input pairs. In contrast, multi-attribute mDP couples privacy constraints and utility losses through a metric (e.g., Euclidean distance [2]) over the joint attribute space, so both privacy constraints and utility optimization are inherently geometryand task-dependent rather than attribute-wise separable. We provide a more detailed comparison between our work with these LDP-based approaches in Section 5 (Related Works).

Our Contributions Contribution 1: DepHDP: a dependency-aware heterogeneous data perturbation framework. To address

the heterogeneity gap in multi-attribute mDP, we propose DepHDP, a multi-stage framework that selects an appropriate perturbation mechanism for each attribute group while accounting for inter-attribute dependence. A key challenge is that utility loss is often non-separable: perturbing one attribute can change the downstream effect of others due to correlations and feasibility constraints, so attribute-wise mechanism selection can misestimate end-to-end degradation. DepHDP addresses this through Stage 1 (attribute grouping), which clusters statistically dependent attributes for joint perturbation. This stage builds on established ideas of dependency-aware grouping and correlation-guided allocation [14], [15]. Stage 2 (utility-loss evaluation and surrogate construction) perturbs one group at a time to obtain group-wise loss profiles and combines them into an end-to-end surrogate objective. Using these profiles, Stage 3 (mechanism selection) determines whether a lightweight DPN mechanism is sufficient for each group (e.g., when loss is approximately radial in metric distance) or an optimizationbased mechanism is needed to capture non-radial loss features. Building on established grouping methods, our contribution is the integration of task-driven mechanism selection and joint mechanism–budget optimization under record-level mDP. Contribution 2: Efficient joint optimization of heterogeneous mechanisms under a global mDP budget. Building on Stages 1–3, DepHDP addresses the remaining scalability bottleneck: jointly optimizing heterogeneous group mechanisms under a single record-level mDP constraint. In particular, we model the record-level distance using an ℓp metric, whose flexibility allows practitioners to encode diverse application-specific notions of similarity by tuning p. Direct full-record optimization is infeasible because the decision variables scale with the exponentially large Cartesian-product domain. DepHDP therefore performs Stage 4 (heterogeneous perturbation optimization) by decomposing the problem into two coupled components: (i) within-group mechanism optimization, which optimizes the selected mechanism for each group under a given group privacy budget, and (ii) cross-group budget allocation, which allocates the global budget to minimize total utility loss using group-specific loss-budget profiles. Importantly, Theorem 1 provides a generalized composition rule for record-level ℓp metric DP over attribute groups, beyond classic sequential composition [12], showing that the composed mechanism satisfies global mDP when the group budgets satisfy an ℓp -norm constraint. We formulate budget allocation as a constrained optimization problem and solve it via Lagrange multipliers [16]. To handle potential non-convex empirical loss-budget curves, we construct convex envelope bounds and provide a conditional suboptimality bound for the fixed Stage-4 surrogate objective in Proposition 2. Contribution 3: Evaluation across three case studies. We evaluate DepHDP on three multi-attribute case studies with diverse dependency structures and utility objectives: Case I: frequency estimation [17], Case II: crowdsourcing aggregation [18], and Case III: entropy-based dependency

preservation [10]. We compare DepHDP with baselines that either apply a single perturbation primitive uniformly, such as DPN with or without Bayesian remapping [19], or use fixed or optimized but mechanism-homogeneous budget allocations across attributes or groups. In particular, our strongest baseline, denoted as ALC+RMP, combines allocation-optimized budget splitting (ALC) with Bayesian remapping (RMP). We also conduct sensitivity studies on DepHDP’s key hyperparameters, including grouping and mechanism-selection thresholds, to examine its utilityefficiency trade-offs. Across all three case studies, DepHDP achieves the lowest end-task utility loss under the same global privacy budget. Compared with ALC+RMP, DepHDP reduces utility loss by 52.5%–55.7% in Case I, 13.8%–19.2% in Case II, and 47.6%–66.7% in Case III. The artifact is available through an anonymous repository [20]. The remainder of the paper is organized as follows. Section 2 reviews preliminaries. Section 3 presents the design of DepHDP, and Section 4 reports experimental results. Section 5 discusses related work, and Section 6 concludes.

2. Preliminaries In this section, we review the preliminaries of mDP, including the threat model and the formal definition, and summarize two main classes of perturbation mechanisms, distance-based predefined-noise (DPN) and optimizationbased (OPT). Threat model. We let X denote the input domain (i.e., the set of possible secret records) and Y denote the output domain (i.e., the set of values real records can be mapped to by perturbation mechanisms). A perturbation mechanism is defined as a randomized mapping M : X Ñ Y . To capture record similarity, we equip X with a distance function d : X ˆ X Ñ Rě0 that quantifies pairwise dissimilarity, e.g., geographic distance for locations, embedding-based distances for categorical values, or application-defined semantic distances. Let the random variable X denote the true input record drawn from X . Following prior work [7], [8], [9], we consider discrete input and output domains, i.e., X and Y are finite sets; in our multi-attribute setting, each attribute has a finite domain or is discretized into finitely many bins [10], [17], [18]. We consider the standard local privacy setting in which each user perturbs their sensitive record locally before sending any information to the data collector. The adversary is the data collector/server, which observes the perturbed report y, knows the perturbation mechanism M, the privacy parameters, and the input metric, and the prior distribution of the true data X . The privacy guarantee does not rely on the server honestly following a particular aggregation protocol; rather, it follows from the local mDP guarantee enforced by M before transmission. We assume only that each participating user applies the prescribed local perturbation mechanism to their own record. Malicious users who submit arbitrary reports may affect utility or estimation accuracy, but do not weaken the local privacy guarantee provided to an honest user by M.

Formal definition of mDP. LDP requires data perturbation to maintain a uniform level of indistinguishability between users’ data [1]. mDP generalizes this concept by tying the privacy guarantee to a distance over the input space: nearby inputs should be harder to distinguish than far-apart ones. Originally proposed for location privacy [2], mDP has been naturally extended to high-dimensional domains such as text embedding [21] and image data protection [22]. Definition 1 (pϵ, dq-mDP). We say that a perturbation mechanism M : X Ñ Y satisfies pϵ, dq-mDP if for each y P Y , ln PrrMpxq “ ys is ϵ-Lipschitz with respect to d, i.e., @x, x1 P X , ˇ ˇ ˇln PrrMpxq “ ys ´ ln PrrMpx1 q “ ysˇ ď ϵdpx, x1 q. (1) Here ϵ ą 0 is the privacy budget controlling the strength of privacy. Intuitively, mDP ensures that small changes in the input x of the perturbation method M result in bounded changes in the distribution of the output Mpxq, thus providing privacy guarantees in the corresponding distance metric space. A lower ϵ signifies a tighter bound, meaning less information can be revealed about Mpxq. Data perturbation algorithms. Over the past decade, substantial effort has focused on designing perturbation mechanisms to achieve mDP [23]. Broadly, existing approaches fall into two categories: (1) Distance-based Predefined-Noise (DPN) mechanisms, such as Exponential mechanisms [5] (Definition 2) and Laplace [2], add noise from a fixed, parametric distribution whose shape is determined by the privacy budget ϵ and the distance between the true record and a candidate perturbed record. (2) OPTimization-based (OPT) mechanisms, such as linearprogramming (LP) formulations (Definition 3), derive the perturbation distribution by solving an explicit optimization problem rather than adopting a fixed parametric form. Definition 2 (Exponential Mechanism [5]). Given a privacy parameter ϵ ą 0 and an input x P X , the (metric) exponential mechanism samples an output y P Y with probability ` ˘ exp ´ 2ϵ dpx, yq ` ϵ ˘, PrrMpxq “ ys “ ř (2) 1 y1 PY exp ´ 2 dpx, y q where dpx, yq measures the distance between x and y. In this paper, we use the exponential mechanism as our primary DPN method considering that both X and Y are discrete, and EM provides a canonical way to sample from an arbitrary discrete output space. However, our framework does not rely on EM per se: other DPN mechanisms (like Laplace [2]) whose conditional distribution can be evaluated (or sampled) as a function of dpx, yq can be plugged into our pipeline with minimal changes. Definition 3 (LP-based mechanism [7]). In LP-based (optimization-based) designs, since both the input and output domains X and Y are discrete, a perturbation mechanism

M can ␣ be(represented by a conditional probability matrix Z “ zx,y xPX , yPY , where zx,y “ PrrMpxq “ ys. Given an input prior πpxq and a utility-loss function cpy|xq, an optimal mechanism is obtained by solving ř ř min (3) xPX yPY πpxqcpy|xqzx,y Z

s.t.

1

zx,y ď eϵdpx,x q zx1 ,y , @x, x1 P X , @y P Y, (4) ř @x P X , (5) yPY zx,y “ 1, zx,y ě 0, @x P X , @y P Y. (6)

Here, the objective minimizes expected utility loss under the prior, and the constraints enforce the mDP-induced indistinguishability conditions parameterized by pϵ, dq. DPN vs. OPT-based mechanisms. DPN approaches are attractive for their simplicity and low runtime [23]: once a noise family is fixed, deployment incurs minimal perinstance computation. They are often effective when the task-induced utility loss is approximately radial, i.e., it depends primarily on the metric distance, so that a single distance-based distribution captures most of the relevant utility structure. In particular, under ℓ1 distances, the Laplace mechanism is optimal for minimizing mean-squared error among oblivious additive-noise mechanisms [4]. However, DPN is inherently limited by its fixed functional form: it may be suboptimal when loss landscapes are nonradial or highly anisotropic, in which case the mechanism cannot adapt its probability mass to utility-critical outputs. In contrast, OPT-based approaches directly solve for a perturbation channel tailored to the given metric and utility loss [7], and can therefore better exploit non-radial loss structures and deliver lower utility loss under the same privacy budget. The main drawbacks are computational: the decision space has Op|X ||Y|q complexity [9], making the resulting programs expensive to solve, especially when the secret record is composed of multiple attributes. Together, these observations motivate a heterogeneous strategy that selects mechanisms on an attribute-wise basis according to attribute type, domain scale, and loss structure.

3. Methodology In this section, we present the design of DepHDP. We first formulate the problem and summarize key challenges in §3.1, then provide an overview in §3.2, and detail the four stages in §3.3–§3.6 and analyze computational complexity and scalability in §3.7.

śL y “ py1 , . . . , yL q P Y fi ℓ“1 Yℓ , where Yℓ denotes the release domain for attribute ℓ. We consider a set of records, each consisting of L heterogeneous sensitive attributes (e.g., a mix of numerical, ordinal, and categorical fields). For each attribute ℓ P rLs, the true value xℓ lies in a domain Xℓ , and theśfull record L is the vector x “ px1 , . . . , xL q P X fi ℓ“1 Xℓ . A perturbation mechanism M maps x to a sanitized output śL y “ py1 , . . . , yL q P Y fi ℓ“1 Yℓ , where Yℓ denotes the release domain for attribute ℓ. DepHDP can accommodate type-specific component metrics without imposing a numerical ordering on nominal attributes. Possible choices include dℓ pa, bq “ 1ra‰bs for nominal or binary attributes, normalized rank distance dℓ pa, bq “ |rℓ paq ´ rℓ pbq|{pmℓ ´ 1q for ordinal attributes with mℓ ą 1 levels, and normalized absolute distance dℓ pu, vq “ |u ´ v|{pbℓ ´ aℓ q for numerical attributes on raℓ , bℓ s with bℓ ą aℓ . For 1 ď p ă 8, record similarity is measured by the weighted product metric dp px, x1 q “ ´ř ¯1{p L 1 p . For p “ 8, its limit with fixed w d px , x q ℓ ℓ“1 ℓ ℓ ℓ positive weights is d8 px, x1 q “ maxℓ dℓ pxℓ , x1ℓ q. We use unit weights unless otherwise specified and define restricted group metrics using the same components and weights. This construction accommodates mixed-type groups without imposing artificial distances on nominal labels. The privacy guarantee is relative to the declared metric; its semantic suitability remains a modeling responsibility. Given dp , a mechanism M satisfies record-level pϵ, dp q-mDP if, for all x, x1 P X and all y P Y , ˇ ˇ ˇ PrrMpxq “ ys ˇ 1 ˇ ˇln (7) ˇ PrrMpx1 q “ ys ˇ ď ϵ dp px, x q.

Unless stated otherwise, we focus on the ℓ2 metric in this work and defer the discussion of ℓ1 and ℓ8 cases to Appendix C. We let Qpϵq denote the feasible family of perturbation mechanism M ! ) ˇ Qpϵq fi M : X Ñ Y ˇ M satisfies (7) under pX , Y, dp q (8) and let LpMq denote the expected task-induced utility loss of M: ř ř LpMq fi xPX πpxq yPY Pr rMpxq “ ys cpy|xq. (9) Our goal is to find an pϵ, dp q-mDP mechanism that minimizes utility loss: M‹ “ arg min LpMq. (10) MPQpϵq

3.1. Problem Statement and Challenges We consider a set of records, each consisting of L heterogeneous sensitive attributes (e.g., a mix of numerical, ordinal, and categorical fields). For each attribute ℓ P rLs, the true value xℓ lies in a domain Xℓ , and theśfull record L is the vector x “ px1 , . . . , xL q P X fi ℓ“1 Xℓ . A perturbation mechanism M maps x to a sanitized output

With the preliminaries in place, we motivate our design with a key observation: multi-attribute records are inherently heterogeneous, so a single mDP perturbation primitive is unlikely to be uniformly suitable across all attributes. As analyzed in Section 2, DPN mechanisms (e.g., Laplace and EM) are efficient and effective when utility loss is largely distance-aligned, whereas OPT mechanisms can better fit complex non-radial loss landscapes but typically scale poorly

Sensitive attributes

Attribute Grouping

Utility Loss Evaluation

𝒢1

② End-to-end loss construction 𝑐 𝐲|𝐱 ≈ 𝑓 c1 𝐲𝒢1 |𝐱 𝒢1 , … , c𝐾 𝐲𝒢𝐾 |𝐱 𝒢𝐾

𝒢2

… 𝒢𝐾 Stage 1

① Within-group loss evaluation 𝐂1 , … , 𝐂𝐾

Stage 2

Perturbation Mechanism Selection

𝒢1

DPN

𝒢2

OPT

𝒢𝐾

DPN

…

Heterogeneous Perturbation Optimization Upper level: Objective: min ℒ ℳ Lower level: For each OPT-based ℳ𝑘 , optimize ℳ𝑘 to find ℒ𝑘 𝜖𝑘 Constraints: Group-wise 2 2 composition σ𝐾 𝑘=1 𝜀𝑘 ≤ 𝜀

Stage 3

Stage 4

Figure 2. The four-stage framework of DepHDP.

as the domain grows. This heterogeneity also exposes the following key challenges: Challenge 1: How to account for inter-attribute dependence. To select suitable perturbation mechanisms, we must characterize each attribute’s utility–privacy profile under downstream tasks, yet these losses are often nonseparable across attributes. In many applications, the impact of perturbing one attribute depends on the values of others (e.g., multivariate aggregation [24]). As a result, independently perturbing attributes can distort intrinsic cross-attribute relationships, produce implausible attribute combinations, and misestimate the true end-task degradation. This motivates attribute grouping: by identifying correlated attributes and perturbing them jointly, we preserve their interactions and obtain a more accurate proxy of downstream utility under perturbation. Challenge 2: How to efficiently evaluate the utility loss. After grouping, evaluating the task-induced utility loss at the full-record level remains computationally prohibitive, as it would require running the ś downstream task over all śL L input-output pairs in ℓ“1 Xℓ ˆ ℓ“1 Yℓ . A key technical requirement is therefore to establish a computationally efficient link between the global utility loss and the group-wise losses, enabling accurate loss estimation without enumerating this full Cartesian-product domain. Challenge 3: How to efficiently optimize heterogeneous perturbation mechanisms across multiple attribute groups. Given a mechanism choice for each attribute group, we need to jointly optimize them under a global recordlevel mDP constraint. Directly optimizing a full-record channel is infeasible because the decision variables scale with the exponentially large Cartesian-product domain. We therefore adopt a decomposition strategy: we design pergroup submechanisms with dedicated privacy budgets and compose them to satisfy record-level mDP. This introduces an additional cross-group decision, i.e., how to allocate the global budget across groups, yielding a bilevel program in which the upper level selects budgets and the lower level computes group-wise optimal mechanisms. The resulting upper-level objective, defined implicitly via lower-level value functions, is typically non-convex, which further complicates the algorithmic design.

Next, we present our method in detail and show how it addresses the above three challenges.

3.2. Algorithm Overview As illustrated in Fig. 2, DepHDP consists of four stages: Stage 1: Attribute grouping. DepHDP first quantifies statistical dependence between each pair of attributes (e.g., using normalized mutual information) and clusters them into K groups G1 , . . . , GK , so that strongly correlated attributes are perturbed coherently rather than independently. Without loss of generality, we reorder attribute indices so that these groups form a partition of rLs and their concatenation follows the index order. For each group Gk (k P rKs), let xk fi xGk denote the sub-record obtained by restricting the full record x to the coordinates in Gk , so that the full record can be written as x “ px1 , . . . , xK q, where xk P XGk . Here, XGk denotes the input domain of group k (i.e., all feasible value combinations over attributes in Gk ), and YGk denotes the corresponding output domain of perturbed sub-records. This grouping decomposes the multi-attribute design problem into K coupled subproblems, each characterized by a group mechanism Mk : XGk Ñ YGk and a group privacy budget ϵk . Accordingly, the original mechanism M is composed across groups as ` ˘ Mpxq fi M1 px1 q, . . . , MK pxK q . (11) Stage 2: Utility loss evaluation. This stage has two components: 1 Within-group loss evaluation: For each group Gk , ⃝ DepHDP estimates the (within-group utility-loss ␣ matrix Ck fi ck pyk |xk q px ,y qPXG ˆYG , where k k k k ck pyk |xk q is defined later in Eq. (17). This matrix Ck is then used in Stage 3 to guide within-group mechanism selection. 2 End-to-end loss construction, where DepHDP esti⃝ mates the overall loss cpy|xq and learns a surrogate that links it to group-wise losses, i.e., cpy|xq « f pc1 py1 |x1 q, . . . , cK pyK |xK qq.

This surrogate is then used in Stage 4 for crossgroup budget allocation.

Stage 3: Perturbation mechanism selection. For each attribute group Gk , DepHDP selects an appropriate perturbation mechanism. It applies a DPN method (i.e., the Exponential mechanism) when the domain is large or the task loss is primarily distance-based, indicated by a high radial-fit/MSElikeness score. Otherwise, when the domain is small or the loss is noticeably non-radial, DepHDP switches to an OPTbased design. Stage 4: Heterogeneous perturbation optimization. Finally, DepHDP jointly optimizes the cross-group budget allocation and the within-group mechanisms via a bilevel formulation. At the upper level, we choose the group budget vector ϵ “ pϵ1 , . . . , ϵK q to minimize the end-to-end utility loss of the composed mechanism. At the lower level, for each group Gk , we instantiate the best within-group perturbation distribution/mechanism subject to the budget ϵk , which induces a group-specific loss-budget function Lk pϵk q. To ensure that any feasible ϵ yields a valid record-level guarantee, we enforce a composition rule (Theorem 1) that lifts the per-group mDP constraints to record-level mDP and thereby couples the allocation across groups. Theorem 1 (Group-wise composition under an ℓp record metric). For each group k (k = 1, ..., K), define the restricted ℓp metric `ř ˘ 1 p 1{p dGk ,p pxk , x1k q “ . (12) ℓPGk wℓ dℓ pxℓ , xℓ q Assume that each group mechanism Mk : XGk Ñ YGk satisfies pϵk , dGk ,p q-mDP, i.e., for all xk , x1k P XGk and all yk P YGk , ˇ ˇ ˇ PrrMk pxk q “ yk s ˇ ` ˘ 1 ˇ ˇln (13) ˇ PrrMk px1 q “ yk s ˇ ď ϵk dGk ,p xk , xk . k ` Then the ˘composed mechanism Mpxq fi M1 px1 q, . . ., MK pxK q satisfies pϵ, dp q-mDP under the full-record metric dp px, x1 q, provided that the group budgets ϵ “ pϵ1 , . . . , ϵK q obey the dual-norm constraint ´ř ¯1{q K q }ϵ}q fi ď ϵ, where p1 ` 1q “ 1, (14) k“1 ϵk with the usual convention }ϵ}8 “ maxkPrKs ϵk (corresponding to p “ 1). Equivalently, řK p Ź if p ą 1 (so q “ p´1 ), it suffices that k“1 ϵqk ď ϵq ; Ź if p “ 1 (so q “ 8), it suffices that maxk ϵk ď ϵ. Proof sketch. By independence across groups in the product mechanism, the log-likelihood ratio for any output y “ py1 , . . . , yK q decomposes as a sum of group-wise log ratios, each bounded by (13). Summing řK these bounds and applying Hölder’s inequality yields k“1 ϵk dGk ,p pxk , x1k q ď }ϵ}q ¨ dp px, x1 q, which is at most ϵ dp px, x1 q under (14); see Appendix A.1 for details. As we focus on the ℓ2 metric řK in this paper, the group-wise composition requires that k“1 ϵ2k ď ϵ2 . Remark. The group-wise composition rule in Theorem 1 provides a generalized privacy accounting principle that

subsumes the standard multi-attribute LDP composition as a special case. When each group contains exactly one attribute (i.e., K “ L and Gk “ tku), the resulting mechanism becomes attribute-wise perturbation, and the constraint in Theorem 1 reduces to the familiar sequential composition condition for multi-attribute LDP as p Ñ 8 [25]. How the record metric shapes mechanism design and allocation. Standard ϵ-LDP bounds every record-pair like1 lihood ratio by eϵ , whereas mDP uses eϵdp px,x q (Eq. (7)). The declared metric shapes both within-group constraints (Eq. (13)) and feasible budget allocations. For a fixed partition and product-form mechanism, Theorem 1 gives řK 1 1 1 k“1 ϵk dGk ,p pxk , xk q ď }ϵ}q dp px, x q ď ϵdp px, x q, (15) provided }ϵ}q ď ϵ, where 1{p ` 1{q “ 1. For př“ 1, 2, 8, this sufficient condition becomes maxk ϵk ď ϵ, k ϵ2k ď ϵ2 , ř and k ϵk ď ϵ, respectively. The metric is fixed before optimization; changing it changes both the guarantee and feasible allocations. Although p “ 8 yields the additive budget constraint of sequential LDP composition, the privacy definitions coincide for the discrete 0{1 record metric, not arbitrary metrics. Notably, DepHDP minimizes estimated end-to-end task loss using group-specific loss–budget profiles, so allocation depends on the selected DPN/OPT mechanisms, task loss, and metric geometry. Grouping supports utility decomposition, but composition requires only conditionally independent group randomizations given the input record, not statistically independent attributes. Next, we introduce the details of the four stages.

3.3. Stage 1: Attribute Grouping DepHDP begins by partitioning the attribute index set rLs into K disjoint groups G1 , . . . , GK , with the goal of perturbing strongly dependent attributes coherently rather than independently. This step is motivated by the observation that independently perturbing correlated attributes may destroy cross-attribute relationships, produce implausible records, and misestimate the downstream utility loss. To construct the groups, we use normalized mutual information (NMI) to measure pairwise statistical dependence between attributes [26]. Continuous attributes are first discretized into bins, while categorical attributes use their original categories. For each attribute pair pi, jq, we compute 2MIpXi ;Xj q Iij fi HpXi q`HpX , where MIpXi ; Xj q is estimated from jq empirical joint and marginal distributions, and HpXi q and HpXj q denote the empirical Shannon entropies. The resulting score Iij P r0, 1s provides a scale-free dependence measure that is comparable across heterogeneous attributes. We then build an undirected dependency graph whose nodes are attributes and whose edges connect attribute pairs with non-negligible dependence: an edge pi, jq is added if Iij ą τgroup , where τgroup “ 0.1 by default. The connected components of this graph define the attribute groups G1 , . . . , GK . We use dependency-aware grouping as a building block that connects group-level loss estimation,

heterogeneous mechanism selection, and privacy-budget allocation within DepHDP.

3.4. Stage 2: Utility Loss Evaluation Given the attribute groups from Stage 1, DepHDP next quantifies how candidate perturbations affect downstream 1 within-group loss utility. This stage has two components: ⃝ evaluation, which constructs group-level utility-loss profiles 2 end-to-end loss construction, for mechanism selection, and ⃝ which learns how group-wise perturbation effects combine into record-level utility loss for budget allocation. 1 Within-group loss evaluation. This component estimates ⃝ the task-induced utility loss incurred when perturbing subrecords in XGk , for k “ 1, . . . , K . The resulting loss profile is a key input to Stage 3, where DepHDP decides whether group Gk should use a distance-based predefined-noise mechanism or an optimization-based mechanism. Let x´k denote the attributes outside group Gk , so that a full record can be written as x “ pxk , x´k q. For a candidate perturbed group value yk , we define the plugin operator Plugk px, yk q fi pyk , x´k q, which constructs a counterfactual record by replacing only the group component xk with yk while keeping the remaining attributes x´k fixed. Let γtask p¨, ¨q denote a task-specific nonnegative discrepancy function, such as absolute error, squared error, or a statistic-specific deviation. For a fixed context x´k , we first define the context-dependent group-isolated loss as c̃k pyk |xk ; x´k q fi γtask pU pxk , x´k q, U pyk , x´k qq , (16)

where U p¨q denotes the downstream utility/statistic of interest. The semicolon makes the fixed context x´k explicit, as the same group perturbation may induce different losses under different contexts. Let Xk and X´k denote the random vectors of attributes within and outside Gk , respectively. To obtain a grouplevel loss value indexed only by pxk , yk q, we average the context-dependent loss over the conditional distribution of the remaining attributes: ck pyk |xk q fi EX´k |Xk “xk rc̃k pyk |xk ; X´k qs .

(17)

The pointwise loss ck pyk |xk q is mechanism-independent, whereas its expectation LpMq depends on the output probabilities induced by M. The same distinction applies to groupwise losses and their expectations. In implementation, this expectation is estimated from the evaluation set by averaging the observed context-dependent losses associated with xk ; when exact matches are sparse, we use bin-based or samplebased averaging. We collect the group-level losses into the within-group utility-loss profile Ck fi tck pyk |xk qupxk ,yk qPXG ˆYG . For k k small or OPT-eligible groups, DepHDP evaluates all candidate pairs pxk , yk q P Pk , which requires Op|XGk ||YGk |q group-level evaluations. For large groups, where full enumeration is computationally expensive, DepHDP estimates Ck and the corresponding DPN-adequacy scores using sampled candidate pairs.

2 End-to-end loss construction. This component learns ⃝ how record-level utility loss can be predicted from groupwise perturbation effects. Importantly, this step does not assume that the final perturbation mechanism has already been selected. Instead, DepHDP constructs candidate perturbation pairs px, yq to explore the relationship between perturbation patterns and downstream utility loss. For small domains, candidate perturbed records y P Y can be enumerated for sampled inputs x. For larger domains, DepHDP samples a representative subset of feasible perturbed records. These candidate pairs are used only to learn the utility-loss surrogate, before the final group mechanisms and privacy budgets are determined. For each candidate pair pxpsq , ypsq q, we compute the record-level loss ´ ¯ cpsq fi cpypsq |xpsq q “ γtask U pxpsq q, U pypsq q . (18) To relate this end-to-end loss to group-wise effects, we also evaluate group-isolated counterfactuals. For each group Gk , psq psq psq we form Plugk pxpsq , yk q “ pyk , x´k q, where only the psq attributes in Gk are replaced by yk while all other groups remain fixed. ˇ gives the ´ This ¯ sample-level group-isolated loss psq psq ˇ psq psq ck fi ck yk ˇxk ; x´k . Collecting these values yields !´ ¯)T psq psq the training set T fi cpsq , c1 , . . . , cK . s“1 We then fit a surrogate model f on T to predict the record-level loss from the group-isolated losses: cpy|xq « f pc1 py1 |x1 ; x´1 q, . . . , cK pyK |xK ; x´K qq . (19) In principle, f can include interaction terms to capture crossgroup effects. We begin with a quadratic form and empirically find that higher-order interaction terms are negligible in our settings (see Appendix D.2 for details). Therefore, we use the following first-order surrogate in the rest of the paper: řK cpy|xq « β0 ` k“1 βk ck pyk |xk ; x´k q. (20)

We fit the coefficients using nonnegative least squares, enforcing βk ě 0 for all k . This linear surrogate supports Stage 4 by predicting end-to-end loss for candidate mechanisms and budget allocations. Its coefficients capture group contributions but do not imply exact task additivity: cross-group interactions may leave prediction residuals. We evaluate its fit on held-out calibration pairs. Taking expectations yields the approximate objective in Proposition 1. Because we do not bound the residual uniformly over mechanisms, surrogate optimization does not certify optimality for the original objective in Eq. (10). The linear surrogate provides an approximate end-to-end objective for comparing mechanisms and allocations. Held-out calibration pairs assess its fit, and Proposition 1 expresses the corresponding expected-loss approximation. Proposition 1 (Expected utility loss linear surrogate). Let the record-level expected utility loss be defined as in Eq. (9). Assume (i) the record-level mechanism composes across

Domain size |𝓧𝒌 | ≤ 𝝉𝐝𝐢𝐦 𝝉𝐝𝐢𝐦 𝝉𝐝𝐩𝐧 𝐑𝐚𝐝𝐢𝐚𝐥-fit 𝐝𝐩𝐧 Score 𝑺𝒌 ≤ 𝝉𝐝𝐩𝐧 OPT is selected

Figure 3. Intuitive idea of perturbation mechanism selection.

MSE-likeness score. Our MSE-likeness score is motivated by a classical optimality result for mDP under the ℓ1 metric: among oblivious additive-noise mechanisms, Laplace minimizes MSE for identity queries [4]. We implement EM rather than Laplace, so this result provides intuition for the score, not an optimality guarantee for our mechanism. Specifically, it motivates the heuristic that a DPN mechanism may suffice when task-induced loss is largely determined by perturbation magnitude and approximately quadratic in that magnitude. Accordingly, we fit the group loss ck pyk |xk q to the scaled squared-distance model ak d2Gk pxk , yk q ` bk via least squares. Let Pk fi XGk ˆ YGk . Then ÿ

pa‹k , b‹k q “ arg min

aě0, bPR

śK

`

˘2 ck pyk |xk q ´ ad2Gk pxk , yk q ´ b .

pxk ,yk qPPk

(25)

attribute groups as Mpy|xq “ k“1 Mk pyk |xk q, and (ii) the end-to-end utility loss admits the first-order surrogate řK cpy|xq « β0 ` k“1 βk ck pyk |xk ; x´k q. (21)

We then define the MSE-likeness score as a normalized fit quality:

Then the record-level expected utility loss decomposes approximately as řK LpMq « β0 ` k“1 βk Lk pMk q, (22)

Skmse fi 1 ´

where the group-wise expected loss is Lk pMk q fi Ex„π Eyk „Mk p¨|xk q rck pyk |xk ; x´k qs .

(23)

The detailed proof can be found in Appendix A.2.

3.5. Stage 3: Perturbation Mechanism Selection Given a privacy budget ϵk ą 0, we select the perturbation mechanism Mk based on the effective domain size |XGk | and the DPN adequacy score Skdpn . As illustrated in Figure 3, using a dimensionality threshold τdim and a DPN-fit threshold τdpn P p0, 1q, the selection rule is defined as: # is OPT, if |XGk | ď τdim and Skdpn ď τdpn Mk (24) is DPN, otherwise Intuitively, we favor the DPN mechanisms when the effective domain is large (making optimization costly) or when the loss is well explained by the noise magnitude (high radialfit), whereas we invoke optimization-based mechanisms to capture non-radial or heterogeneous loss patterns that are poorly modeled by magnitude-only noise. We use EM for DPN because it supports arbitrary finite metric spaces, and finite-domain LP optimization for OPT. Approximate alternatives such as PAnDA [8] improve scalability without the same exact optimality guarantee as full LP. Additional mechanisms can be incorporated within the framework after verifying their privacy guarantees and profiling their utility and computational costs. Next, we introduce two DPN adequacy scores that help decide whether a simple DPN is likely to be near-optimal for an attribute (or an attribute group): an MSE-likeness score and a more general radial-fit score.

d

¯2

´ ř pxk ,yk qPPk

ck pyk |xk q´pa‹ ˆd2 pxk ,yk q`b‹ q G k k k

|XG ||YG |

` k ˘ k Std Ck ` δ

,

(26)

where δ ą 0 avoids division by zero. A larger Skmse indicates that ck pyk |xk q is well explained by a quadratic function of the metric radius, suggesting that a DPN mechanism is likely sufficient. Conversely, a small Skmse indicates non-quadratic or direction-dependent loss patterns, for which an optimization-based mechanism may be preferable. We implement EM rather than Laplace; the cited result motivates the score but does not establish EM’s optimality for our metrics or downstream tasks. Radial-fit score. The MSE-likeness score above provides a parametric adequacy test by checking whether the loss is approximately quadratic in the noise magnitude. In practice, however, task-induced losses need not be quadratic. A broader (and often more realistic) condition under which DPN mechanisms are adequate is that the loss depends primarily on the noise magnitude and is monotone in that magnitude, regardless of its exact functional form. Concretely, if ck pyk |xk q « g pdGk pxk , yk qq

for some nondecreasing g, (27) then mechanisms whose conditional distribution depends only on dGk pxk , yk q match the dominant structure of the utility loss. To quantify this property, we fit the best nondecreasing function gk‹ that predicts loss from the metric radius using isotonic regression: ÿ ` ˘2 gk‹ “ arg min ck pyk |xk q´gpdGk pxk , yk qq , g nondecreasing

pxk ,yk qPPk

(28) Analogous to Eq. (26), we define the radial-fit score as a normalized fit quality: cř ` ˘2 pxk ,yk qPPk

Skrad fi 1´

‹ pd ck pyk |xk q´gk Gk pxk ,yk qq

|XG ||YG |

` k˘ k Std Ck ` δ

, (29)

where δ ą 0 is a small constant. We interpret Skrad close to 1 as evidence that the utility loss is largely radial (i.e., mainly determined by the metric radius and approximately monotone), in which case distance-based DPN mechanisms are typically adequate. Conversely, a small Skrad indicates substantial non-radial or non-monotone structure, motivating an optimization-based design such as an LP mechanism. Notably, a central question in DepHDP is when OPT’s potential utility gain warrants its offline computational cost. The selection thresholds expose this trade-off: tighter domain limits or stricter evidence of DPN inadequacy favor DPN, while OPT is reserved for tractable groups with poorly distance-aligned loss. Configuration is performed offline; deployment samples from fixed group mechanisms.

According to our mechanism selection strategy (Section 3.5), an OPT-based mechanism is chosen only when the group domain size |XGk | is sufficiently small, so the LP in Eq. (32) remains tractable and can be solved efficiently using standard LP solvers (e.g., the dual simplex method [27]). For moderately larger domains (e.g., |XGk | ě 102 ), we improve scalability via decomposition techniques such as Benders decomposition [28]. Notably, the lower-level problem need not handle DPN groups. For a predefined-noise mechanism, Mk is fully specified once ϵk is given, so its expected loss can be evaluated directly: ÿ ÿ Lk pϵk q fi π k pxk q Mk pyk |xk qck pyk |xk q. xk PXGk

3.6. Stage 4: Heterogeneous Perturbation Optimization Given the selected mechanism for each attribute group, we jointly compose and optimize the group mechanisms under a single record-level mDP constraint, using the endto-end loss surrogate from Proposition 1. We formulate this step as the bilevel program in Eq. (30):

yk PYGk

(33) Upper level problem. Once each Lk pϵk q (k “ 1, ..., K ) is obtained, the bilevel problem formulated in Eq. (30) reduces to the following single-level privacy budget allocation problem: min

tϵk uK k“1

β0 `

K ÿ k“1

βk Lk pϵk q

s.t.

K ÿ k“1

ϵ2k ď ϵ2 , ϵk ě 0.

(34) where β0 , β1 , ..., βK are all non-negative. This problem K ÿ can be solved efficiently via a Lagrangian approach by min β0 ` βk Lk pϵk q introducing a dual variable for the global ℓ2 -composition k“1 řK 2 constraint [16]. The resulting Karush–Kuhn–Tucker (KKT) 2 s.t. k“1 ϵk ď ϵ (group-wise composition under ℓ2 metric), conditions characterize stationary allocations by balancing the ϵk ě 0, @ k “ 1, ..., K. marginal utility–budget tradeoff across groups: at a stationary point, the marginal decrease BLk pϵk q{Bϵk is equalized across Lower level: k up to the Lagrange multiplier. This yields an efficiently For each Mk selected as OPT “ ‰‰ solvable condition for computing the budget distribution “ Lk pϵk q “ min Exk „πk Eyk „Mk p¨|xk q ck pyk |xk q under the quadratic constraint (the Lagrangian algorithm Mk PQk pϵk q details are deferred to Appendix B.1). (30) Here, Qk pϵk q is the feasible set of OPT-based mechanisms řKNotably, when the upper-level objective (β0 ` k“1 βk Lk pϵk q) is non-convex, KKT-based methods may that satisfy the within-group mDP constraint under budget converge only to a local optimum and do not guarantee global ϵk , i.e., optimality. To obtain a tractable alternative, we next introduce ! ) ˇ two convex surrogates of the utility loss. Optimizing these Qk pϵk q fi Mk : XGk Ñ YGk ˇ Mk satisfies pϵk , dGk q-mDP surrogates yields an allocation that is typically close to the (31) optimum in practice, and, importantly, their optimal values Intuitively, the upper level allocates group privacy budgets provide a lower bound on the original non-convex objective ϵ “ pϵ1 , . . . , ϵK q to minimize the predicted end-to-end loss (Proposition 2), enabling us to quantify the suboptimality subject to group-wise composition under ℓ2 metric (Theorem gap of our solution. 1), while the lower level computes each group loss-budget function Lk pϵk q by optimizing Mk via an LP. The resulting Convex surrogates of the loss-budget function. To obtain group mechanisms then compose into the final multi-attribute a tractable loss-budget function Lk pϵk q, we evaluate Lk pϵk q piq k mechanism M “ pM1 , . . . , MK q. Next, we describe how on a uniform grid tϵk uN i“1 with equal interval size. Here, we solve the two-level optimization problems: we let uk “ ruk,1 , . . . , uk,Nk sJ denote surrogate values at the grid points. Discrete convexity is enforced by requiring Lower level problem. To compute the loss-budget function nondecreasing slopes: Lk pϵk q for an attribute group Gk , we solve the following LP problem that finds the minimum expected within-group uk,i`1 ´ uk,i uk,i`2 ´ uk,i`1 utility loss under an ϵk -mDP constraint (i.e., Mk P Qk pϵk q): ď pi`2q , i “ 1, . . . , Nk ´ 2, (35) pi`1q piq pi`1q ÿ ÿ ϵk ´ ϵk ϵk ´ ϵk Lk pϵk q “ min πk pxk q Mk pyk |xk qck pyk |xk q. Mk PQk pϵk q which can be written compactly as Aconv uk ď 0. We then xk PXk yk PYk k (32) approximate Lk pϵk q using two convex surrogates: Upper level:

the privacy allocation ϵ that achieves mintLpϵ‹ q, Lpϵ‹ qu as theř final privacy budget assignment, where Lpϵq fi K β0 ` k“1 βk Lk pϵk q. Let Lopt denote the globally optimal value of the original (possibly non-convex) upper-level problem. The following proposition provides a sandwich bound that quantifies how close our returned solution is to Lopt .

Violate the upper bounds Least convex ഥ 𝒌 (⋅) majorant 𝓛 Greatest convex minorant 𝓛𝒌 (⋅) 𝝐𝟎

… 𝝐𝟏

𝝐𝟐 … 𝝐𝑵𝒌

𝓛𝒌 (⋅)

Proposition 2 (Sandwich bound via convex envelopes). The optimal value Lopt satisfies

𝝐𝑵𝒌 −𝟏

Llower ď Lopt ď mintLpϵ‹ q, Lpϵ‹ qu.

The detailed proof can be found in Appendix A.3.

Figure 4. Convex surrogates of the loss-budget function Lk p¨q.

1 Greatest convex minorant (GCM) Lk pϵk q: the largest ⃝ convex function that underestimates the sampled points, i.e., piq piq Lk pϵk q ď Lk pϵk q for all i. The GCM is obtained by maximizing the surrogate values subject to convexity and pointwise under-approximation: uk P arg max 1J uk uk

´ ¯ piq @i. s.t. Aconv uk ď 0, uk,i ď Lk ϵk k

(36)

2 Least convex majorant (LCM) Lk pϵk q: the smallest ⃝ convex function that overestimates the sampled points, i.e., piq piq Lk pϵk q ě Lk pϵk q for all i. The LCM is obtained by minimizing the surrogate values subject to convexity and pointwise over-approximation: uk P arg min 1J uk uk

´ ¯ piq s.t. Aconv uk ď 0, uk,i ě Lk ϵk @i. k

(37) piq

The LPs in Eqs. (36)–(37) guarantee Lk pϵk q ď piq piq piq k Lk pϵk q ď Lk pϵk q at the sampled grid points tϵk uN i“1 . To use these surrogates in the continuous upper-level optimization, we extend them to all ϵk via piecewise-linear interpolation between adjacent grid points. Because Lk pϵk q is continuous, but may vary nonlinearly between samples, a direct interpolation of the sampled envelopes can still violate the intended bounds between grid points (cf. Fig. 4). To avoid such violations, we apply a conservative horizontal shift to the discrete envelopes before interpolation: the upper envelope is shifted right by one grid step ∆ϵk and the lower envelope is shifted left by ∆ϵk , yielding valid pointwise bounds over the entire budget range in practice. After shifting, we apply boundary corrections (discard outof-range endpoints and insert extrapolated/aligned boundary points) and then use piecewise-linear interpolation to obtain 1 continuous, monotone envelopes L1k pϵq ď Lk pϵq ď Lk pϵq over the full budget interval while preserving convexity of the upper envelope (see Appendix B.2 for details). We denote 1 the resulting continuous bounds by L1k pϵk q and Lk pϵk q. Upper-level solution. We solve the upper-level budget allocation problem using the two shifted convex envelope 1 K surrogates tL1k pϵk quK k“1 and tLk pϵk quk“1 . Let the resulting ‹ ‹ allocations be denoted by ϵk and ϵk for k “ 1, . . . , K , respectively. We then define řK a record-level expected loss lower bound: Llower fi β0 ` k“1 βk L1k pϵ‹k q. In DepHDP, we select

Notably, Proposition 2 quantifies allocation suboptimality for the fixed Stage 4 surrogate, while the task experiments evaluate the utility achieved by the complete pipeline.

3.7. Computational Complexity and Scalability We now summarize offline and deployment costs. Let N be the reference-data size, L the attribute count, and K the group count. Stages 1–2. After discretization, sparse pairwise dependence estimation takes OpN L2 q time, followed by OpL2 q graph processing. Evaluating Qk candidate pairs per group costs ř Op k Qk ceval k q, including context averaging and task evaluation. Here, Qk “ |XGk ||YGk | for exhaustive evaluation and is smaller with sampling. Surrogate construction additionally evaluates full-record and group-isolated losses for T calibration pairs, stores an OpT Kq design matrix, and performs solver-dependent nonnegative least-squares fitting. Stage 3. Given precomputed losses and distances for Pk ř pairs, quadraticřfitting costs Op k Pk q; sorting and isotonic fitting cost Op k Pk log Pk q, plus validation. Stage 4. With precomputed distances, EM construction and loss evaluation cost Op|XGk ||YGk |q per budget. OPT has Op|XGk ||YGk |q decision variables and Op|XGk |2 |YGk |q privacy constraints; solver time and memory depend on sparsity and tolerance. For each group, we evaluate EM or solve the OPT LP at sampled budgets to construct its loss– budget profile. We then fit convex envelopes, optimize the K group budgets, and construct the final mechanisms at the allocated budgets. Finally, storing all group mechanisms explicitly requires ř Op k |Xř Gk ||YGk |q space. Sampling one output per group costs Op k |YGk |q per record by scanning probability rows. Optional alias-table preprocessing reduces sampling to OpKq, excluding input indexing and output assembly. Notably, restricting OPT to tractable groups improves scalability over monolithic OPT on the evaluated domains, but does not eliminate domain-size and storage limitations.

4. Performance Evaluation In this section, we evaluate the performance of DepHDP. §4.1 describes the experimental setup. §4.2 compares

DepHDP with baseline methods in terms of utility loss. Additional experiments supporting adequacy-based selection and task-aware allocation, assessing surrogate and threshold sensitivity, and comparing against all-DPN, full-record OPT, and other optimization-based methods are provided in Appendix D.

4.1. Experimental Setup Datasets. We evaluate DepHDP on three representative multi-attribute case studies with different attribute types and downstream utility objectives: Case I: Frequency Estimation (Adult Census) [17], with 15 demographic and socioeconomic attributes, where utility loss is the discrepancy between privatized and reference marginal frequency distributions; Case II: Crowdsourcing Aggregation (Wine Quality) [18], with 5 quality-related attributes, where utility loss is the deviation of majority-vote aggregation results from the non-private outputs; and Case III: Entropy-Based Dependency Preservation (Heart Disease) [10], with 13 mixed clinical/demographic attributes, where utility loss is the perturbation-induced change in information-theoretic statistics, including marginal entropy, joint entropy, and total correlation. Our evaluation simulates a local-privacy deployment in which the held-out test records constitute the protected population: each test user keeps their raw record locally and sends to the server only a privatized report generated by the finalized ϵ-mDP randomizer. For each of the three case studies, we use the same fitting/test protocol, randomly selecting 62.5% of the records as the fitting split and the remaining 37.5% as the test split. The fitting split is used only as offline calibration information for DepHDP, including estimating attribute domains and discretization bins, pairwise dependency scores for grouping, empirical priors or feature statistics, DPN-adequacy scores, utility-loss profiles, and the surrogate model for budget allocation. It is not a substitute for the protected users’ reports: it captures expected population structure and task-loss geometry, but not the realized records in the held-out test population. Thus, directly using the fitting prior or sampling from the fitting split would provide only historical or population-level information, whereas privatized test reports provide record-specific signal from the actual protected users, which is important for tasks such as recommendation, navigation, and crowdsourcing decisions. Once the offline configuration is fixed, no raw test record is used for mechanism configuration, parameter tuning, or budget allocation. During evaluation, each test record is locally perturbed under the global privacy budget ϵ, and task degradation is measured using the task-specific utility-loss definition in Eq. (9). Raw test records are accessed only by the offline evaluator to compute non-private reference statistics and benchmarking utility loss. Although the datasets used in our experiments are publicly available, we use them solely for reproducible benchmarking rather than as alreadypublic user disclosures. Baselines and DepHDP variants. We compare DepHDP with four homogeneous-mechanism baselines of the form

“A ` B”, where A denotes the budget-allocation strategy and B denotes the per-group perturbation method. For allocation, SPL uniformly splits the global budget across groups [29], while ALC optimizes the group-wise budget allocation under the global mDP constraint. For perturbation, DPN applies a distance-driven predefined-noise mechanism, while RMP further applies Bayesian remapping as post-processing [19]. This yields four baselines: SPL+DPN, SPL+RMP, ALC+DPN, and ALC+RMP. A pure OPT baseline that optimizes every group is omitted because it is computationally impractical for the multi-attribute domains considered here. We report four DepHDP variants. DepHDP-m and DepHDP-r estimate DepHDP’s configuration quantities using the full dataset and use the MSE-likeness and radial-fit scores, respectively, for Stage 3 mechanism selection. DepHDP-ms and DepHDP-r-s use the same two scores but estimate configuration quantities only from the fitting split and evaluate utility on the protected test split; the “-s” suffix denotes this split-data setting. Computing resources. Our experiments were conducted on a workstation equipped with an Intel Core i9-13900F CPU (24 cores, 2.00–5.60 GHz), 32 GB DDR5 memory (4800 MHz), and an NVIDIA GeForce RTX 4090 GPU with 24 GB GDDR6X VRAM. All LPs were solved in MATLAB using linearprog from the Optimization Toolbox [27].

4.2. Utility Loss Evaluation We first evaluate the downstream utility loss incurred by different privacy mechanisms under a fixed global privacy budget. Using the task-specific loss definition in Eq. (9), we compare DepHDP with baseline approaches across the three case studies I–III. We examine how utility loss varies with the privacy budget and analyze the impact of optimized budget allocation and mechanism selection on reducing task degradation in multi-attribute settings. We set the default grouping threshold to τgroup “ 0.1, the domain-size threshold to τdim “ 300, and the DPN adequacy threshold to τdpn “ 0.3, 0.1, and 0.2 for Cases I–III, respectively. DepHDP vs. Baselines. Table 1 reports downstream utility loss (mean ˘1.96ˆ standard deviation) across three case studies and global budgets ϵ P t1, . . . , 10u. DepHDP consistently achieves the lowest loss, outperforming the strongest baseline ALC+RMP (optimized allocation + Bayesian remapping). The baselines provide partial improvements: switching from SPL to ALC helps when groups have unequal loss–budget sensitivities, while switching from DPN to RMP can mitigate mismatches between distance-based perturbation and task-specific loss. However, neither change fully addresses non-distance-driven loss, where directly optimizing the perturbation mechanism can provide additional gains. DepHDP’s gains are larger in Cases I and III but modest in Case II, where all-DPN may offer a preferable utility–computation trade-off. More concretely, in Case I (Frequency Estimation), optimized allocation provides only modest gains (ALC+RMP improves over SPL+RMP by 8.1% on average), whereas

TABLE 1. U TILITY LOSS ACROSS DIFFERENT PERTURBATION METHODS (M EAN˘1.96ˆSTANDARD DEVIATION ).

Method SPL + DPN SPL + RMP ALC + DPN ALC + RMP DepHDP-m-s DepHDP-r-s DepHDP-m DepHDP-r Bound-m Bound-r

ϵ “ 1.0 19.84 ± 0.2 18.17 ± 0.2 19.27 ± 0.2 17.42 ± 0.2 8.28 ± 0.1 12.45 ± 0.1 8.28 ± 0.1 12.45 ± 0.1 8.11 ± 0.2 11.90 ± 0.1

ϵ “ 2.0 18.81 ± 0.2 17.64 ± 0.2 17.98 ± 0.2 16.45 ± 0.1 7.67 ± 0.1 11.70 ± 0.1 7.67 ± 0.1 11.70 ± 0.1 7.49 ± 0.2 11.12 ± 0.1

ϵ “ 3.0 17.74 ± 0.2 16.80 ± 0.2 16.69 ± 0.2 15.50 ± 0.1 7.08 ± 0.1 10.82 ± 0.1 7.08 ± 0.1 10.82 ± 0.1 6.92 ± 0.2 10.36 ± 0.1

Case I: Frequency Estimation ϵ “ 4.0 ϵ “ 5.0 ϵ “ 6.0 16.64 ± 0.2 15.54 ± 0.2 14.45 ± 0.2 15.91 ± 0.2 14.95 ± 0.2 13.97 ± 0.2 15.41 ± 0.2 14.18 ± 0.2 13.02 ± 0.2 14.56 ± 0.1 13.63 ± 0.1 12.73 ± 0.1 6.55 ± 0.1 6.07 ± 0.1 5.64 ± 0.1 9.99 ± 0.1 9.25 ± 0.1 8.60 ± 0.1 6.55 ± 0.1 6.07 ± 0.1 5.64 ± 0.1 9.99 ± 0.1 9.25 ± 0.1 8.60 ± 0.1 6.41 ± 0.2 5.95 ± 0.2 5.53 ± 0.2 9.63 ± 0.1 8.94 ± 0.1 8.32 ± 0.1

ϵ “ 7.0 13.40 ± 0.2 13.01 ± 0.2 12.00 ± 0.2 11.84 ± 0.1 5.25 ± 0.1 8.02 ± 0.1 5.25 ± 0.1 8.02 ± 0.1 5.16 ± 0.2 7.76 ± 0.1

ϵ “ 8.0 12.42 ± 0.2 12.11 ± 0.2 11.10 ± 0.1 11.00 ± 0.1 4.89 ± 0.1 7.50 ± 0.1 4.89 ± 0.1 7.50 ± 0.1 4.82 ± 0.2 7.27 ± 0.1

ϵ “ 9.0 11.52 ± 0.2 11.28 ± 0.2 10.31 ± 0.1 10.23 ± 0.1 4.57 ± 0.1 7.03 ± 0.1 4.57 ± 0.1 7.03 ± 0.1 4.51 ± 0.2 6.83 ± 0.1

ϵ “ 10.0 10.70 ± 0.2 10.51 ± 0.2 9.60 ± 0.1 9.54 ± 0.1 4.27 ± 0.1 6.61 ± 0.1 4.27 ± 0.1 6.61 ± 0.1 4.22 ± 0.2 6.42 ± 0.1

Method SPL + DPN SPL + RMP ALC + DPN ALC + RMP DepHDP-m-s DepHDP-r-s DepHDP-m DepHDP-r Bound-m Bound-r

ϵ “ 1.0 28.52 ± 4.3 23.57 ± 3.6 28.32 ± 4.5 22.92 ± 3.9 19.62 ± 7.1 19.76 ± 6.9 19.76 ± 7.1 19.78 ± 7.1 17.60 ± 6.9 17.59 ± 6.9

ϵ “ 2.0 24.66 ± 3.2 21.04 ± 2.6 23.34 ± 4.2 18.97 ± 3.8 15.88 ± 6.3 15.81 ± 6.4 16.07 ± 6.4 16.21 ± 6.2 14.41 ± 6.1 14.42 ± 6.0

ϵ “ 3.0 20.20 ± 2.5 17.41 ± 1.9 18.58 ± 3.6 15.45 ± 2.9 12.99 ± 4.8 13.03 ± 4.8 13.08 ± 4.9 13.05 ± 5.0 11.74 ± 5.0 11.74 ± 5.0

Case II: Crowdsourcing ϵ “ 4.0 ϵ “ 5.0 ϵ “ 6.0 16.30 ± 2.5 13.40 ± 2.4 11.23 ± 2.2 14.05 ± 1.9 11.49 ± 1.8 9.55 ± 1.5 14.80 ± 3.0 11.97 ± 2.6 9.85 ± 2.3 12.61 ± 2.4 10.21 ± 1.9 8.28 ± 1.5 10.49 ± 3.8 8.37 ± 3.1 6.73 ± 2.4 10.52 ± 3.8 8.42 ± 2.9 6.89 ± 2.2 10.61 ± 3.8 8.35 ± 3.1 6.69 ± 2.4 10.35 ± 4.1 8.45 ± 2.9 6.81 ± 2.3 9.64 ± 4.0 7.80 ± 3.1 6.48 ± 2.5 9.58 ± 4.0 7.82 ± 3.1 6.42 ± 2.5

ϵ “ 7.0 9.52 ± 2.0 8.01 ± 1.3 8.29 ± 2.0 6.83 ± 1.2 5.52 ± 1.9 5.56 ± 1.8 5.67 ± 1.8 5.60 ± 1.8 5.34 ± 2.0 5.33 ± 2.0

ϵ “ 8.0 8.15 ± 1.8 6.75 ± 1.1 7.11 ± 1.8 5.74 ± 1.1 4.67 ± 1.5 4.66 ± 1.5 4.72 ± 1.4 4.67 ± 1.5 4.50 ± 1.6 4.48 ± 1.6

ϵ “ 9.0 7.05 ± 1.7 5.74 ± 0.9 6.20 ± 1.6 4.90 ± 0.9 3.96 ± 1.2 4.00 ± 1.2 3.96 ± 1.3 3.99 ± 1.2 3.84 ± 1.3 3.83 ± 1.3

ϵ “ 10.0 6.16 ± 1.5 4.93 ± 0.8 5.48 ± 1.5 4.25 ± 0.8 3.46 ± 1.0 3.45 ± 1.0 3.48 ± 1.0 3.42 ± 1.1 3.34 ± 1.1 3.34 ± 1.1

Method SPL + DPN SPL + RMP ALC + DPN ALC + RMP DepHDP-m-s DepHDP-r-s DepHDP-m DepHDP-r Bound-m Bound-r

ϵ “ 1.0 16.35 ± 0.9 13.38 ± 1.0 15.72 ± 0.9 12.73 ± 1.0 5.66 ± 0.8 5.88 ± 0.8 5.56 ± 0.8 5.71 ± 0.8 5.14 ± 0.7 5.35 ± 0.7

ϵ “ 2.0 14.65 ± 0.8 11.91 ± 1.0 13.70 ± 0.7 11.26 ± 1.0 3.85 ± 0.7 4.41 ± 0.8 3.87 ± 0.7 4.29 ± 0.8 3.68 ± 0.6 3.90 ± 0.6

ϵ “ 3.0 13.15 ± 0.7 10.69 ± 0.9 11.25 ± 0.7 9.55 ± 0.8 3.21 ± 0.7 3.30 ± 0.9 3.18 ± 0.7 3.39 ± 0.9 2.90 ± 0.6 3.08 ± 0.6

Case III: Entropy estimation ϵ “ 4.0 ϵ “ 5.0 ϵ “ 6.0 11.75 ± 0.6 10.41 ± 0.6 9.14 ± 0.5 9.58 ± 0.8 8.54 ± 0.8 7.54 ± 0.7 8.82 ± 0.6 7.12 ± 0.5 6.09 ± 0.5 7.54 ± 0.8 5.99 ± 0.7 4.96 ± 0.6 2.69 ± 0.8 2.37 ± 0.5 2.23 ± 0.5 2.84 ± 0.6 2.61 ± 0.6 2.28 ± 0.6 2.64 ± 0.8 2.38 ± 0.5 2.15 ± 0.5 2.76 ± 0.6 2.55 ± 0.6 2.24 ± 0.6 2.47 ± 0.6 2.23 ± 0.6 2.09 ± 0.6 2.62 ± 0.6 2.33 ± 0.6 2.16 ± 0.6

ϵ “ 7.0 8.00 ± 0.5 6.61 ± 0.7 5.49 ± 0.4 4.36 ± 0.6 2.11 ± 0.6 2.07 ± 0.3 2.10 ± 0.6 2.06 ± 0.3 2.00 ± 0.5 2.06 ± 0.5

ϵ “ 8.0 7.05 ± 0.5 5.80 ± 0.7 5.10 ± 0.4 3.98 ± 0.6 2.01 ± 0.5 2.01 ± 0.5 2.03 ± 0.5 1.99 ± 0.5 1.94 ± 0.5 1.99 ± 0.5

ϵ “ 9.0 6.30 ± 0.5 5.13 ± 0.7 4.83 ± 0.4 3.72 ± 0.6 1.93 ± 0.6 2.00 ± 0.6 1.95 ± 0.6 2.00 ± 0.6 1.89 ± 0.5 1.94 ± 0.5

ϵ “ 10.0 5.73 ± 0.5 4.61 ± 0.6 4.63 ± 0.4 3.54 ± 0.6 1.86 ± 0.6 1.88 ± 0.5 1.85 ± 0.6 1.89 ± 0.5 1.85 ± 0.5 1.89 ± 0.5

DepHDP-m achieves substantially larger reductions: 52.5%– 55.7% relative to ALC+RMP (54.8% on average) and 58.3%– 61.0% relative to SPL+DPN (60.2% on average), indicating that mechanism mismatch is a dominant source of error. In Case II (Crowdsourcing), where distance-driven designs are more competitive, DepHDP-m still reduces loss by 13.8%– 19.2% relative to ALC+RMP (17.0% on average) and by 30.7%–43.8% relative to SPL+DPN (38.4% on average); DepHDP-r follows the same trend with slightly higher loss, yet remains below all SPL/ALC baselines. Finally, in Case III (Entropy Estimation), DepHDP-m improves over ALC+RMP by 47.6%–66.7% (56.6% on average), with especially pronounced gains at large budgets (e.g., at ϵ “ 10, 1.85 vs. 3.54, a 47.7% reduction); DepHDP-r is often nearly identical to DepHDP-m, suggesting that both variants approach the same low-loss regime when distance alignment is strong or remapping is already effective. Overall, Table 1 shows that both aspects of DepHDP are important: cross-group budget optimization accounts for heterogeneous loss sensitivities, and selectively invoking OPT (beyond predefined noise and remapping) is necessary when the utility loss is not distance-driven. In this regime, the baselines largely plateau, whereas DepHDP continues to substantially reduce utility loss. DepHDP With vs. Without Fitting/Test Split. Table 1 compares DepHDP configured using the full dataset

(DepHDP-m/r) with the corresponding fitting/test-split results (DepHDP-m/r-s). The full-data setting serves as an idealized reference for assessing how closely the split-based evaluation approaches the case where configuration has access to all available records. In Case I, the two settings produce nearly indistinguishable utility losses across different budgets. Averaged over all privacy budgets and both scoring variants, the split-based results have 0.36% lower loss in Case II and 1.08% higher loss in Case III. These results indicate that the fitting/test split closely matches the idealized full-data reference, with only mild degradation in Case III, likely due to distributional differences between the fitting and test records. Overall, DepHDP-m/r-s remains close to DepHDP-m/r and continues to substantially outperform the homogeneous baselines. DepHDP vs. Lower Bounds. Finally, to assess how close DepHDP is to the best achievable utility loss under the same group-wise loss evaluations, Table 1 additionally reports two lower bounds derived from Proposition 2, denoted Bound-m and Bound-r, corresponding to DepHDP-m and DepHDP-r, respectively. Comparing DepHDP-m with Boundm (and DepHDP-r with Bound-r) provides an optimality-gap diagnostic: since Bound-‹ is a certified lower bound on the optimal upper-level objective value under the same groupwise loss curves, the gap between DepHDP-‹ and Bound-‹ upper-bounds how far DepHDP-‹ can be from the (unknown)

optimum for ‹ P tm, ru. To summarize this gap, we report the relative error RelErr fi pL ´ Llower q{Llower , where L is DepHDP’s achieved objective value and Llower is the lower bound from Proposition 2. As shown in Table 1, the relative error is at most 5.22%, 12.45%, and 10.06% in Cases I–III, respectively (max over ϵ and over both scoring variants), indicating that DepHDP performs close to the certified lower bound and hence is near-optimal.

5. Related Works Perturbation mechanism for mDP (DPN vs. OPT). Prior data perturbation design work on mDP can be broadly organized into two families: Distance-driven Predefined Noise (DPN) mechanisms and optimization (OPT)-based mechanisms that explicitly solve for a near-optimal perturbation channel under mDP constraints. DPN-based works. Early and most widely studied mDP deployments focus on location privacy on grids. Andrés et al. [2] introduced geo-indistinguishability via planar Laplace noise; subsequent work refined predefined kernels and their deployment (e.g., personalized/group-based noise [30], [31], truncation [32], and federated/blockchain adaptations [33]). A common enhancement keeps the kernel fixed but improves utility via post-processing, such as Bayesian or utility-aware remapping [19], [34]. Hybrid designs further combine mDP with auxiliary privacy/utility notions or context-aware noise [35]. Beyond locations, predefined or hybrid mechanisms have been applied to high-dimensional embeddings in NLP and multimedia, e.g., Laplace noise with nearestneighbor remapping for text [36], [37], truncated exponential mechanisms with semantic candidate sets [38], and perturbations for speech/facial embeddings [22], [39]. Overall, these approaches favor simplicity by relying on a distance-driven kernel (optionally with remapping) fixed a priori. OPT-based works. A parallel line of work optimizes perturbation mechanisms for task-specific privacy–utility trade-offs. Bordenabe et al. [7] formulated optimal geo-indistinguishable mechanisms via LP. Subsequent work improves scalability through LP combined with exponential-mechanism structure [9], input-domain partitioning and Benders decomposition [28], local relevance restrictions [40], and scalable mechanism composition [25]. Other approaches explore reinforcement learning [41], bilevel optimization for taskspecific objectives [42], and sequential perturbation for trajectory privacy [43]. These advances can inform DepHDP’s optimization backends. DepHDP addresses a complementary multi-attribute design problem: selecting DPN or OPT per group using dataand task-dependent adequacy signals, then jointly optimizing group budgets and OPT mechanisms under a record-level metric constraint. Relative to prior decomposition and composition approaches [25], [28], [40], our emphasis is this integrated heterogeneous design. Theorem 1 applies established product-mechanism composition principles and Hölder’s inequality to provide the record-level privacy guarantee for these heterogeneous group mechanisms.

Multi-Attribute Privacy Mechanisms for LDP. Multiattribute LDP lets users perturb high-dimensional records before reporting, but naively perturbing every attribute can introduce excessive noise [11]. Existing designs include budgetcentric strategies, such as privacy budget splitting (SPL) across attributes [11], [44], and sampling-centric strategies that report selected attributes (SMP) [12], sometimes adding fake data (RS+FD) to obscure unselected attributes [13]. Probabilistic graphical models also help preserve attribute correlations [45]. These techniques do not directly resolve our multiattribute mDP design problem. Many LDP approaches focus on allocation or sampling with fixed reporting primitives [11], [13], [45]. In contrast, mDP specifies privacy through a metric over the joint record space, motivating mechanism selection and optimization tailored to task-loss geometry. DepHDP studies the choice between predefined distance-based noise and optimized mechanisms when utility sensitivity varies across attributes (Appendix D.3, Fig. 6). Our setting is a oneshot release under a single global metric-privacy constraint, rather than the repeated-reporting and longitudinal inference settings considered in some LDP studies [12]. Dependency-Aware Grouping and Correlation-Guided Allocation. Prior LDP work studies dependency-aware grouping and correlation-guided allocation: Domingo-Ferrer and Soria-Comas [15] cluster attributes for approximate intercluster independence and apply joint randomized response; Du et al. [14] calibrate perturbation and attribute budgets using correlation bounds under univariate-dominance LDP, a relaxation of standard LDP, and allocate reporting samples to reduce estimation variance. DepHDP instead selects DPN or OPT by task-loss geometry and tractability, then optimizes mechanisms and group budgets using loss–budget profiles to minimize estimated end-to-end loss.

6. Conclusions This paper studies multi-attribute mDP mechanism design under heterogeneous domains and task-induced utility losses, and proposes DepHDP, a decomposition-based framework for heterogeneous mechanism synthesis. DepHDP integrates dependency-aware grouping, landscape-driven selection between DPN and OPT mechanisms, and joint optimization of group-wise perturbation under a global metric constraint. Across diverse case studies, DepHDP consistently achieves lower utility loss than the baselines, especially when loss is weakly distance-aligned and a single monolithic mechanism becomes mismatched. DepHDP shows strong empirical performance but has several limitations. Its bilevel optimization depends on empirically estimated loss–budget profiles, which may be sensitive to sampling rate or distribution shift. DepHDP also restricts optimization-based perturbation to small domains, while scalable OPT mechanisms for large or continuous spaces may require approximate or distributed solvers. Finally, this study considers one-shot release; extending DepHDP to streaming or interactive settings with adaptive budget allocation remains an important direction for future mDP systems.

References

[20] Anonymous Authors, “Artifact for multi-attribute metric differential privacy,” https://anonymous.4open.science/r/ multi-attribute-metric-differential-privacy-6736, 2026, anonymous artifact repository.

[1]

J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy and statistical minimax rates,” in 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013, pp. 429–438.

[2]

M. E. Andrés, N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, “Geo-indistinguishability: Differential privacy for location-based systems,” in Proc. of the 2013 ACM SIGSAC conference on Computer & communications security, 2013, pp. 901–914.

[3]

K. Chatzikokolakis, M. E. Andrés, N. E. Bordenabe, and C. Palamidessi, “Broadening the scope of differential privacy using metrics,” in Proc. of Privacy Enhancing Technologies, E. De Cristofaro and M. Wright, Eds., 2013, pp. 82–102.

[4]

F. Koufogiannis et .al, “Optimality of the laplace mechanism in differential privacy,” arXiv, 2015.

[23] X. Xie, C. Yu, Y. Huang, Y. Cao, and C. Qiu, “A decade of metric differential privacy: Advancements and applications,” 2025. [Online]. Available: https://arxiv.org/abs/2502.08970

[5]

K. Chatzikokolakis, C. Palamidessi, and M. Stronati, “Constructing elastic distinguishability metrics for location privacy,” Privacy Enhancing Technologies (PETS), vol. 2015, p. 156–170, 2015.

[24] C. Li, G. Miklau, M. Hay, A. McGregor, and V. Rastogi, “The matrix mechanism: Optimizing linear counting queries under differential privacy,” The VLDB Journal, 2015.

[6]

C. Qiu, A. C. Squicciarini, C. Pang, N. Wang, and B. Wu, “Location privacy protection in vehicle-based spatial crowdsourcing via geoindistinguishability,” IEEE Transactions on Mobile Computing, pp. 1–1, 2022.

[25] C. Qiu, “Interpolation-based optimization for enforcing lp-norm metric differential privacy in continuous and fine-grained domains,” in Proc. of The 35th USENIX Security Symposium, 2026.

[7]

N. E. Bordenabe, K. Chatzikokolakis, and C. Palamidessi, “Optimal geo-indistinguishable mechanisms for location privacy,” in Proc. of ACM CCS, 2014, pp. 251–262.

[8]

[9]

R. Liu and C. Qiu, “Panda: Rethinking metric differential privacy optimization at scale with anchor-based approximation,” in Proc. of the ACM SIGSAC Conference on Computer and Communications Security, 2025, p. 1290–1304. J. Imola, S. Kasiviswanathan, S. White, A. Aggarwal, and N. Teissier, “Balancing utility and scalability in metric differential privacy,” in Proc. of UAI 2022, 2022.

[10] A. Janosi, W. Steinbrunn, M. Pfisterer, and R. Detrano, “Heart disease,” UCI Machine Learning Repository, 1989, [Dataset]. [Online]. Available: https://archive.ics.uci.edu/dataset/45/heart+disease [11] M. Xu, B. Ding, T. Wang, and J. Zhou, “Collecting and analyzing data jointly from multiple services under local differential privacy,” Proc. of the VLDB Endowment, vol. 13, no. 12, pp. 2760–2772, 2020. [12] H. H. Arcolezi, S. Gambs, J.-F. Couchot, and C. Palamidessi, “On the risks of collecting multidimensional data under local differential privacy,” Proc. VLDB Endow., vol. 16, no. 5, p. 1126–1139, Jan. 2023. [13] H. H. Arcolezi, J.-F. Couchot, B. Al Bouna, and X. Xiao, “Random sampling plus fake data: Multidimensional frequency estimates with local differential privacy,” in Proc. of the 30th ACM International Conference on Information & Knowledge Management, 2021, pp. 47–57.

[21] O. Feyisetan and S. Kasiviswanathan, “Private release of text embedding vectors,” in Proc. of the First Workshop on Trustworthy Natural Language Processing. Online: Association for Computational Linguistics, Jun. 2021, pp. 15–27. [22] J.-W. Chen, L.-J. Chen, C.-M. Yu, and C.-S. Lu, “ Perceptual Indistinguishability-Net (PI-Net): Facial Image Obfuscation with Manipulable Semantics ,” in 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), Jun. 2021, pp. 6474–6483.

[26] T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed. Wiley, 2006. [27] “linprog: Solve linear programming problems,” https://www. mathworks.com/help/optim/ug/linprog.html, 2024, accessed in January 2024. [28] C. Qiu, “Enhancing scalability of metric differential privacy via secret dataset partitioning and benders decomposition,” in Proc. of 33rd International Joint Conference on Artificial Intelligence (IJCAI), 2024. [29] X. Ren, C.-M. Yu, W. Yu, S. Yang, X. Yang, J. A. McCann, and P. S. Yu, “LoPub : High-dimensional crowdsourced data publication with local differential privacy,” IEEE Transactions on Information Forensics and Security, vol. 13, no. 9, pp. 2151–2166, 2018. [30] P. Zhang, X. Cheng, S. Su, and N. Wang, “Task allocation under geoindistinguishability via group-based noise addition,” IEEE Transactions on Big Data, vol. 9, no. 3, pp. 860–877, 2023. [31] B. Ma, X. Wang, W. Ni, and R. P. Liu, “Personalized location privacy with road network-indistinguishability,” IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 11, pp. 20 860–20 872, 2022. [32] C. e. a. Yang, “Blockchain-based indoor location paging and answering service with truncated-geo-indistinguishability,” IET Blockchain, 2021. [33] F. Galli, S. Biswas, K. Jung, T. Cucinotta, and C. Palamidessi, “Group privacy for personalized federated learning,” in Workshop on Federated Learning: Recent Advances and New Challenges (in Conjunction with NeurIPS 2022), 2022.

[14] R. Du, Q. Ye, Y. Fu, and H. Hu, “Collecting high-dimensional and correlation-constrained data with local differential privacy,” in 2021 18th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON), 2021, pp. 1–9.

[34] S. Oya, C. Troncoso, and F. Pérez-González, “Is geoindistinguishability what you are looking for?” in Proc. of the 2017 on Workshop on Privacy in the Electronic Society (WPES), 2017, p. 137–140.

[15] J. Domingo-Ferrer and J. Soria-Comas, “Multi-dimensional randomized response,” in 2022 IEEE 38th International Conference on Data Engineering (ICDE), 2022, pp. 1517–1518.

[35] L. Yu, L. Liu, and C. Pu, “Dynamic differential location privacy with personalized error bounds,” in Proc. of IEEE NDSS, 2017.

[16] D. G. Luenberger and Y. Ye, Linear and Nonlinear Programming, 3rd ed. New York: Springer, 2008. [17] B. Becker and R. Kohavi, “Adult,” UCI Machine Learning Repository, 1996, [Dataset]. [Online]. Available: https://archive.ics.uci.edu/dataset/ 2/adult [18] P. Cortez, A. Cerdeira, F. Almeida, T. Matos, and J. Reis, “Wine quality,” UCI Machine Learning Repository, 2009, [Dataset]. [Online]. Available: https://archive.ics.uci.edu/dataset/186/wine+quality [19] K. Chatzikokolakis, E. Elsalamouny, and C. Palamidessi, “Efficient utility improvement for location privacy,” Proc. of Privacy Enhancing Technologies, vol. 2017, 10 2017.

[36] N. Fernandes, M. Dras, and A. McIver, “Author obfuscation using generalised differential privacy,” ArXiv, vol. abs/1805.08866, 2018. [Online]. Available: https://api.semanticscholar.org/CorpusID: 43942677 [37] O. Feyisetan, T. Diethe, and T. Drake, “Leveraging hierarchical representations for preserving privacy and utility in text,” in 2019 IEEE International Conference on Data Mining (ICDM). IEEE Computer Society, 2019, pp. 210–219. [38] R. S. Carvalho, T. Vasiloudis, and O. Feyisetan, “Tem: High utility metric differential privacy on text,” ArXiv, vol. abs/2107.07928, 2021. [Online]. Available: https://api.semanticscholar.org/CorpusID: 236034456

[39] Y. Han, S. Li, Y. Cao, Q. Ma, and M. Yoshikawa, “VoiceIndistinguishability: Protecting Voiceprint In Privacy-Preserving Speech Data Release ,” in 2020 IEEE International Conference on Multimedia and Expo (ICME), 2020, pp. 1–6. [40] C. Qiu, R. Liu, P. Pappachan, A. Squicciarini, and X. Xie, “Timeefficient locally relevant geo-location privacy protection,” in Proc. on Privacy Enhancing Technologies, 2025. [41] M. Min, H. Zhu, J. Ding, S. Li, L. Xiao, M. Pan, and Z. Han, “Personalized 3d location privacy protection with differential and distortion geo-perturbation,” IEEE Trans. Dependable Secur. Comput., vol. 21, no. 4, pp. 3629–3643, 2024.

In (41) we used (38) for each group. For finite p, relate the group-wise distances to the declared weighted product metric. Define ´ř ¯1{p 1 p dGk pxk , x1k q fi w d px , x q and ℓ ℓ ℓ ℓ ℓPGk ´ř ¯1{p L 1 p dp px, x1 q “ . Then the partition ℓ“1 wℓ dℓ pxℓ , xℓ q implies the identity K ÿ

[42] D. Yu, X. Shi, L. Chai, W.-A. Zhang, and J. Chen, “Balancing localization accuracy and location privacy in mobile cooperative localization,” IEEE Transactions on Signal Processing, vol. PP, pp. 1–14, 01 2023. [43] Y. Xiao and L. Xiong, “Protecting locations with differential privacy under temporal correlations,” in Proc. of CCS, New York, NY, USA, 2015, p. 1298–1309. [44] N. Wang, X. Xiao, Y. Yang, J. Zhao, S. C. Hui, H. Shin, J. Shin, and G. Yu, “Collecting and analyzing multidimensional data with local differential privacy,” in 2019 IEEE 35th International Conference on Data Engineering (ICDE), 2019, pp. 638–649. [45] G. Liu, P. Tang, C. Hu, C. Jin, S. Guo, J. Stoyanovich, J. Teubner, N. Mamoulis, E. Pitoura, and J. Mühlig, “Multi-dimensional data publishing with local differential privacy.” in EDBT, 2023, pp. 183– 194.

hence

dGk pxk , x1k qp “

L ÿ

k“1

ℓ“1

K ´ÿ

¯1{p

dGk pxk , x1k qp

wℓ dℓ pxℓ , x1ℓ qp(,42) “ dp px, x1 q. (43)

k“1

Apply Hölder’s inequality with conjugate exponents pp, qq, where p1 ` 1q “ 1: K ÿ

ϵk dGk pxk , x1k q ď

k“1

K ´ÿ

ϵqk

K ¯1{q ´ ÿ

k“1 K ´ÿ

“

dGk pxk , x1k qp

¯1{p

k“1

ϵqk

¯1{q

dp px, x1 q,

(44)

k“1

where the last equality uses (43).

Appendix A. Omitted Proofs A.1. Proof of Theorem 1: Group-wise Composition Under ℓp Record Metric

´ř ¯1{q K q Therefore, if the group budgets satisfy ď k“1 ϵk ϵ, then combining (41) and (44) yields ` ˘ PrrMpxq “ ys ď exp ϵdp px, x1 q PrrMpx1 q “ ys, (45)

i.e., M satisfies pϵ, dp q-mDP. p For completeness: (i) when 1 ă p ă 8, q “ p´1 and the řK q q Proof. Let the L attributes be partitioned into K disjoint condition ř is k“1 ϵk ď ϵ ; (ii) when p “ 1, q “ 8 and (44) ŤK groups G1 , . . . , GK with k“1 Gk “ rLs. For each group k , becomes k ϵk dGk ď pmaxk ϵk qd1 px, x1 q, so it suffices that let Mk be a (possibly heterogeneous, internally coupled) maxk ϵk ď ϵ. For př“ 8, the recordřdistance is the maximum perturbation mechanism applied to the sub-vector xk and group distance, so k ϵk dGk ,8 ď p k ϵk qd8 . Thus }ϵ}1 ď ϵ satisfying pϵk , dGk q-mDP, i.e., for all measurable Bk Ď YGk , suffices. The argument depends on the declared component “ ‰ ` ˘ “ ‰ metrics and fixed weights, not on numerical encodings of 1 1 Pr Mk pxk q “ y ď exp ϵk dGk pxk , xk q Pr Mk pxk q “ y . nominal categories. (38) Define the joint mechanism over groups ´ ¯ A.2. Proof of Propostion 1 Mpxq “ M1 px1 q, . . . , MK pxK q . (39) Proof. Start from the record-level expected utility loss Using the chain rule and the independent group randomiza(Eq. (9)): tion required by Theorem 1, “ ‰ LpMq fi E E cpy|xq . (46) x„π y„Mp¨|xq PrrMpxq “ ys (40) K ” ı ź Plugging (22) into (9) and using linearity of expectation ˇ “ Pr Mk pxk q “ y ˇ M1 px1 q, . . . , Mk´1 pxk´1 q yields k“1 K ź

“ k“1 K ź

ď

« LpMq

“ ‰ Pr Mk pxk q “ y

paq

`

˘ “ ‰ exp ϵk dGk pxk , x1k q Pr Mk px1k q “ y

exp

K ´ÿ k“1

Epx1 ,...,xK q„π Ey„Mp¨|xq β0 `

ff βk ck pyk |xk q

k“1

k“1

“

«

K ÿ

¯

ϵk dGk pxk , x1k q

1

PrrMpx q “ ys.

“

(41)

β0 `

K ÿ

“ ‰ βk Exk „πk Eyk „Mk p¨|xk q ck pyk |xk q ,(47)

k“1

where π k is the marginal of π on XGkś , and (a) uses the K product-form mechanism Mpy|xq “ k“1 Mk pyk |xk q. where x “ pxk , x´k q and y “ pyk , y´k q denote the

concatenation of group-k components and the remaining components, and ř π k pxk q fi x´k πppxk , x´k qq (48)

B. Detailed Algorithm Descriptions

is the marginal of π on XGk . In ś step (a), we use the deK composed mechanism Mpy|xq “ j“1 Mj pyj |xj q, which implies PrrYk “ yk |X “ xs “ Mk pyk |xk q. Moreover, ÿ “ ‰ Eyk „Mp¨|xk q ck pyk |xk q “ Mk pyk |xk qck pyk |xk q

We consider the upper-level ℓ2 -composition budget allocation problem řK řK 2 2 minϵPRK (61) k“1 Lk pϵk q s.t. k“1 ϵk ď ϵ . `

yk PYk

“ ‰ “ Eyk „Mk p¨|xk q ck pyk |xk q .

Define the group-wise expected loss “ ‰ Lk pMk q fi Ex„π Eyk „Mk p¨|xk q ck pyk |xq ,

then combining (47)–(49) gives řK LpMq « β0 ` k“1 βk Lk pMk q.

(49)

B.1. Lagrange multiplier and KKT conditions

Introducing a Lagrange multiplier λ ě 0 for the quadratic constraint yields the Lagrangian ¯ řK ´ J pϵ, λq “ k“1 Lk pϵk q ` λ ϵ2k ´ λ ϵ2 . (62) A pair pϵ‹ , λ‹ q is KKT-stationary if it satisfies: (Primal feasibility)

(50)

pϵ‹k q2 ď ϵ2 ,

ϵ‹k ě 0 @k, (63)

k“1

(Dual feasibility)

A.3. Proof of Proposition 2

K ÿ

λ‹ ě 0,

(Complementary slackness)

(64) λ‹

K ´ÿ

¯ pϵ‹k q2 ´ ϵ2 “ 0,

k“1

Proof. Let the feasible set of privacy-budget allocations be ! ) E fi ϵ P RK : (the Stage 4 budget constraint holds) . ` (51) 1 Recall that L1k p¨q and Lk p¨q are the (shifted, interpolated) convex minorant and majorant constructed in Stage 4, so that for all k and all ϵk , 1

L1k pϵk q ď Lk pϵk q ď Lk pϵk q.

(52)

Define the envelope objectives řK Lpϵq fi β0 ` k“1 βk L1k pϵk q, řK 1 Lpϵq fi β0 ` k“1 βk Lk pϵk q.

(53) (54)

By (52) and βk ě 0, for any ϵ P E we have the pointwise bounds Lpϵq ď Lpϵq ď Lpϵq. (55) Let ϵ‹ P arg minϵPE Lpϵq, ϵ‹ P arg minϵPE Lpϵq, and ϵ‹ P arg minϵPE Lpϵq denote minimizers over the same feasible set E , and define the optimal objective values Llower fi Lpϵ‹ q.

Lopt fi Lpϵ‹ q,

(56)

(1) Llower ď Lopt : By optimality of ϵ‹ for L, Lpϵ‹ q ď Lpϵ‹ q. Combining with (55) evaluated at ϵ‹ yields ‹

ñ

‹

‹

Llower “ Lpϵ q ď Lpϵ q ď Lpϵ q “ Lopt (57) Llower ď Lopt (58)

(2) Lopt ď mintLpϵ‹ q, Lpϵ‹ qu: Since ϵ‹ , ϵ‹ P E , by optimality of ϵ‹ P arg minϵPE Lpϵq we have Lopt “ Lpϵ‹ q ď Lpϵ‹ q,

Lopt “ Lpϵ‹ q ď Lpϵ‹ q.

(59)

‹

Therefore, Lopt ď mintLpϵ‹ q, Lpϵ qu. Conclusion. Combining the two parts gives Llower ď Lopt ď mintL, Lupper u,

which proves the proposition.

(60)

(Stationarity)

0 P BLk pϵ‹k q ` 2λ‹ ϵ‹k ` NR` pϵ‹k q,

(65) @k, (66)

where BLk denotes the (possibly set-valued) subgradient and NR` p¨q is the normal cone of R` . In the differentiable interior case (ϵ‹k ą 0), (66) reduces to L1k pϵ‹k q ` 2λ‹ ϵ‹k “ 0. For any fixed λ ě 0, the minimization over ϵ separates across k : ! ) ϵk pλq P arg min Lk pϵk q ` λ ϵ2k , k “ 1, . . . , K. (67) ϵk ě0

Define the induced budget-usage function řK spλq fi k“1 ϵk pλq2 .

(68)

Proposition 3 (Monotonicity of spλq). The function spλq is nonincreasing in λ. Proof. Fix λ1 ă λ2 . For each k , let e1 P ϵk pλ1 q and e2 P ϵk pλ2 q. By optimality of e1 at λ1 and e2 at λ2 , Lk pe1 q ` λ1 e21 ď Lk pe2 q ` λ1 e22 , Lk pe2 q ` λ2 e22 ď Lk pe1 q ` λ2 e21 .

Adding the two inequalities cancels the Lk p¨q terms and yields pλ1 ´ λ2 qpe21 ´ e22 q ď 0. Since λ1 ´ λ2 ă 0, we obtain 2 e22 ď eř 1 . Applying ř this argument for each k and summing gives k e22 ď k e21 , i.e., spλ2 q ď spλ1 q. Solving for λ‹ by bisection. If sp0q ď ϵ2 , then the constraint in (61) is inactive and we may take λ‹ “ 0 with ϵ‹k “ ϵk p0q. Otherwise, by Proposition 3, the KKT solution must satisfy the scalar equation spλ‹ q “ ϵ2 , (69) which can be solved efficiently by bisection. A simple bracketing strategy is to start with λmin “ 0 and increase λmax geometrically until spλmax q ď ϵ2 ; then bisection on

rλmin , λmax s returns λ‹ to a desired tolerance, and the corresponding allocation is ϵ‹k “ ϵk pλ‹ q,

k “ 1, . . . , K.

Moreover, if the shifted upper samples are discretely convex, i.e., the segment slopes

(70)

This procedure requires only repeated evaluations of the K one-dimensional problems in (67), and does not require convexity of Lk p¨q (only existence of minimizers on the searched interval).

1

s1i fi

piq

Lk pϵk q ď Lk pϵk q ď Lk pϵk q, i “ 1, . . . , Nk . (71)

To use these envelopes in the continuous upper-level opmax timization over ϵk P rϵmin s, we extend them to all k , ϵk budgets via piecewise-linear (PL) interpolation. However, piq piq piq piq directly interpolating tpϵk , Lk pϵk qqu and tpϵk , Lk pϵk qqu may violate the intended ordering between samples when Lk p¨q varies nonlinearly inside each interval. We therefore apply a conservative one-step horizontal shift prior to interpolation: the upper-envelope samples are shifted right by one grid step ∆ϵk , while the lower-envelope samples are shifted left by ∆ϵk . This creates a safety margin within each grid cell. After shifting, we perform a minimal boundary correction so that the shifted sequences are again max defined on rϵmin s (discard the out-of-range endpoint k , ϵk and insert one boundary point by extrapolation/alignment, as described above). Formally, consider an aligned uniform grid ϵ0 ă ¨ ¨ ¨ ă ϵN (step ∆ϵk ) and discrete samples tpϵi , ℓi quN i“0 and tpϵi , ℓi quN i“0 (dropping subscript k for clarity). After shifting and boundary correction, we obtain two sequences on the 1 1 N original grid, tpϵi , ℓi quN i“0 and tpϵi , ℓi qui“0 . We then define the continuous surrogates by PL interpolation: ´ ¯ ` ˘ 1 1 1 N 1 Lk pϵq “ PL tpϵi , ℓi quN i“0 , Lk pϵq “ PL tpϵi , ℓi qui“0 , (72) where PLp¨q connects adjacent sample points by straight line segments. The following proposition formalizes when the shift–correct–interpolate procedure yields globally valid bounds and preserves convexity of the upper surrogate. Proposition 4 (Validity and convexity of shifted PL envelopes). Fix a uniform grid ϵ0 ă ϵ1 ă ¨ ¨ ¨ ă ϵN with step ∆ ą 0. Let L : rϵ0 , ϵN s Ñ R be non-increasing. Assume N discrete envelopes tℓi uN i“0 and tℓi ui“0 satisfy ℓi ď Lpϵi q ď ℓi ,

i “ 0, . . . , N.

(73)

Define shifted, boundary-corrected samples by 1

1

ℓ0 ě Lpϵ0 q, ℓi fi ℓi´1 pi “ 1, . . . , N q, ℓ1i fi ℓi`1 pi “ 0, . . . , N ´ 1q, ℓ1N ď LpϵN q, 1

(74)

1

1 N 1 and let L “ PLptpϵi , ℓi quN i“0 q and L “ PLptpϵi , ℓi qui“0 q. Then 1

L1 pϵq ď Lpϵq ď L pϵq,

@ϵ P rϵ0 , ϵN s.

(76)

1

satisfy s10 ď s11 ď ¨ ¨ ¨ ď s1N ´1 , then L is convex on rϵ0 , ϵN s.

Recall that the LPs in (36)–(37) produce discrete enpiq k velopes on the sampled budgets tϵk uN i“1 : piq

i “ 0, . . . , N ´ 1,

Proof. Fix any ϵ P rϵ0 , ϵN s and choose the unique i P t0, . . . , N ´ 1u such that ϵ P rϵi , ϵi`1 s. Let

B.2. Horizontal Shift of Convex Surrogate

piq

1

ℓi`1 ´ ℓi , ϵi`1 ´ ϵi

(75)

θ fi

ϵi`1 ´ ϵ P r0, 1s, ∆

1´θ “

ϵ ´ ϵi . ∆

(77)

By PL interpolation, 1

1

1

L pϵq “ θ ℓi ` p1 ´ θq ℓi`1 ,

L1 pϵq “ θ ℓ1i ` p1 ´ θq ℓ1i`1 . (78) 1

(1) Upper bound. If i “ 0, then ℓ0 ě Lpϵ0 q by (74), 1 and ℓ1 “ ℓ0 ě Lpϵ0 q ě Lpϵq since L is non-increasing. 1 1 Thus both endpoints satisfy ℓ0 , ℓ1 ě Lpϵq, and (78) implies 1 1 L pϵq ě Lpϵq. If i ě 1, then ℓi “ ℓi´1 ě Lpϵi´1 q ě Lpϵq 1 and ℓi`1 “ ℓi ě Lpϵi q ě Lpϵq (again by monotonicity), so 1 (78) yields L pϵq ě Lpϵq. (2) Lower bound. If i ď N ´2, then ℓ1i “ ℓi`1 ď Lpϵi`1 q ď Lpϵq and ℓ1i`1 “ ℓi`2 ď Lpϵi`2 q ď Lpϵq since ϵ ď ϵi`1 ď ϵi`2 and L is non-increasing; hence (78) implies L1 pϵq ď Lpϵq. If i “ N ´ 1, then ℓ1N ´1 “ ℓN ď LpϵN q ď Lpϵq and ℓ1N ď LpϵN q ď Lpϵq by (74), so again L1 pϵq ď Lpϵq. Combining the two parts proves (75). 1

(3) Convexity. On each interval pϵi , ϵi`1 q, L is affine with derivative s1i in (76). If s10 ď ¨ ¨ ¨ ď s1N ´1 , these derivatives 1 are nondecreasing across intervals, hence L is convex on rϵ0 , ϵN s.

C. Discussions: Extending DepHDP to ℓ1 and ℓ8 Record Metrics. Our paper primarily focuses on the ℓ2 record metric and the resulting ℓ2 -type budget coupling, but the DepHDP pipeline is largely norm-agnostic and can be extended to other p values, particularly p P t1, 8u, with only localized modifications. (1) Group mechanisms remain LP-based for all p. For a fixed attribute group Gk , Stage 3 designs an pϵk , dGk ,p q-mDP mechanism by solving an LP over the channel Zk . This step continues to be an LP for p “ 1 and p “ 8 because the privacy constraints are still linear in the decision variables: ` ˘ @xk , x1k , yk : zk pyk |xk q ď exp ϵk dGk ,p pxk , x1k q zk pyk |x1k q. (79) Only the constants dGk ,p pxk , x1k q change with p; the optimization template is unchanged. (2) The main change is Stage 4: the budget-coupling norm. Under the product-form composition used in DepHDP,

the global pϵ, dp q-mDP guarantee is enforced by an ℓp -type coupling on the per-group budgets, i.e.,

0.8

Pearson r = -0.331 (p = 3.1e-14) Spearman = -0.365 (p = 2.1e-17)

0.8

Pearson r = -0.308 (p = 1.8e-12) Spearman = -0.351 (p = 6.6e-16)

0.75

0.75 0.7

}ϵ}q ď ϵ

K ÿ

ðñ

0.7

ϵqk ď ϵq pq ă 8q,

(80)

max ϵk ď ϵ pq “ 8q.

kPrKs

(81)

0.5 0

(piecewise-linear) convex program after the same envelope construction; only the feasible set changes. Case p “ 1 and q “ 8. For the additive metric d1 , the budget constraint becomes maxk ϵk ď ϵ, or 0 ď ϵk ď ϵ for each group. Hence Stage 4 decouples into K independent one-dimensional problems: 0ďϵk ďϵ

0.6

Samples Linear fit

0.55

1 where p1 ` ř q “ 1. DepHDP’s upper-level objective remains separable, k βk Lk pϵk q, so Stage 4 continues to be a

ϵ‹k P arg min βk Lrk pϵk q.

0.65 0.6

k“1

or

0.65

(82)

If the surrogate losses decrease with ϵk , the optimum assigns ϵ‹k “ ϵ to each group, which remains valid because the global metric is additive. Case p “ 8 and q “ 1. For the max metric d8 , the budget constraint becomes řK (83) k“1 ϵk ď ϵ. This is a linear coupling, so Stage 4 remains a convex allocation problem. This case is more restrictive because the total budget must be shared across groups. Moreover, if group differences are binary, then d8 px, x1 q P t0, 1u for distinct records, so pϵ, d8 q-mDP approaches a standard ϵLDP-style worst-case guarantee. Summary. DepHDP extends naturally to p P 1, 8. Stages 1– 3 keep the same LP-based structure, while Stage 4 only replaces the ℓ2 coupling with the corresponding dual-norm budget constraint. Thus, these extensions require a budgetallocation modification rather than a framework redesign.

D. Full Additional Experiments D.1. DPN Adequacy Score Validation To evaluate DPN adequacy scores for mechanism selection, we use controlled synthetic loss–distance instances to vary loss geometry and examine its relationship with the OPT–DPN utility gap. Real-world benchmarks rarely provide a large and diverse collection of per-attribute utility-loss matrices. Moreover, in multi-attribute settings, the observed gap can be confounded by heterogeneous attribute sensitivities: some attributes are inherently more critical to downstream utility than others. Synthetic generation allows us to construct over a hundred instances with varied loss matrices and corresponding metrics while controlling these sources of variation. This provides a more controlled test of our hypothesis that higher adequacy scores correspond to smaller utility-loss gaps between DPN and OPT. The experiment therefore evaluates the scores as empirical mechanism-selection indicators, rather than establishing their effectiveness for every real-world task.

0.2

0.4

0.6

Samples Linear fit

0.55 0.5 0

0.2

0.4

0.6

0.8

1

(a) Correlation between MSE- (b) Correlation between likeness score and OPT-DPN Radial-fit score and OPTDPN utility gap utility gap Figure 5. DPN adequacy score validation.

Fig. 5 reports the results. Each point represents one synthetic instance (a sampled utility-loss matrix paired with its metric), with the x-axis showing the adequacy score and the y-axis showing the utility gap between OPT and DPN (larger values indicate larger gains from OPT). We observe a clear negative relationship: when the score is high, the loss is largely explained by noise magnitude/radial structure, and OPT provides little additional benefit—indicating that DPN is already near-optimal; when the score is low, OPT can substantially outperform DPN, suggesting non-radial or uneven loss patterns that require optimization-based tailoring. Concretely, (a) the MSE-likeness score is significantly negatively correlated with the OPT–DPN gap (Pearson r “ ´0.331, p “ 3.1 ˆ 10´14 ; Spearman ρ “ ´0.365, p “ 2.1 ˆ 10´17 ), and (b) the radial-fit score shows a similar negative correlation (Pearson r “ ´0.308, p “ 1.8 ˆ 10´12 ; Spearman ρ “ ´0.351, p “ 6.6 ˆ 10´16 ). The fitted regression lines in both panels summarize the overall decreasing trend.

D.2. Validity of Linear Surrogates via Quadratic-Fit Diagnostics DepHDP uses simple surrogate models to approximate record-level and group-wise utility loss as a function of multi-attribute perturbation magnitudes. To examine whether higher-order terms are needed, we fit the quadratic model ř ř ř p Lpxq “ c ` i ai xi ` iăj bij xi xj ` i di x2i , (84) and use the magnitudes of bij and di to diagnose nonlinearity beyond the linear surrogate. Table 2 summarizes the fitted coefficient magnitudes for all three cases using the default grouping threshold τgroup . Across Cases I–III, the linear coefficients remain Θp1q, whereas the interaction and square terms are consistently much smaller in magnitude. In particular, Case I exhibits near-zero quadratic components (e.g., max |bij | « 10´14 and max |di | « 10´14 ), indicating an essentially linear loss response under our feature scaling. Cases II–III show larger (yet still modest) quadratic effects (up to 10´3 ), suggesting that higher-order corrections exist but are dominated by the linear trend. Overall, these results support the use of linear surrogates in DepHDP as an accurate approximation.

TABLE 2. S UMMARY OF FITTED QUADRATIC SURROGATE COEFFICIENTS ACROSS C ASES I–III.

6 4 4

0.3 0.2

c

min ai

max ai

med |bij |

max |bij |

med |di |

max |di |

7.22 ˆ 10´12 ´5.84 ˆ 10´1 3.96 ˆ 10´2

1.00 9.86 ˆ 10´1 0.98

1.00 1.08 1.01

7.72 ˆ 10´18 4.52 ˆ 10´5 1.66 ˆ 10´3

4.65 ˆ 10´14 5.65 ˆ 10´4 2.92 ˆ 10´3

6.04 ˆ 10´19 4.14 ˆ 10´6 3.55 ˆ 10´3

4.33 ˆ 10´14 1.65 ˆ 10´5 7.42 ˆ 10´3

0.1

0.05

0.1 0

Utility loss to distance ratio

Utility loss to distance ratio

I II III

1

2

3

4

5

6

0

1

Group index

(a) Case I

2

3

Group index

(b) Case II

4

Utility loss to distance ratio

Case #xi

1.5 1 0.5 0

1

2

3

4

Group index

(c) Case III

Figure 6. Sensitivity of utility loss to perturbation magnitude.

D.3. Sensivity of Utility Loss to Perturbation A key challenge in multi-attribute perturbation is that attribute groups can differ substantially in utility criticality: some groups suffer large utility loss under small perturbations, while others tolerate larger perturbations with little degradation. This heterogeneity makes uniform or heuristic budget splitting generally suboptimal and motivates datadriven budget allocation. To quantify this effect, Fig. 6(a)–(c) reports a sensitivity study for each group Gk . We compute the within-group utilityloss matrix Ck “ ck pyk | xk q and distance matrix D ˚ k “ d ˚ Gk pxk , yk q, and characterize perturbation sensitivity by ! ) k |xk q ρk fi dcGk py : px , y q P X ˆY , d px , y q ą 0 , k k G G G k k k k k pxk ,yk q k

which measures utility loss per unit perturbation magnitude. Across all the three case studies in Fig. 6, we observe substantial cross-group heterogeneity in perturbation sensitivity: ρk varies markedly across groups rather than concentrating around a single level. This implies that different groups incur very different utility penalties under comparable perturbation magnitudes. Consequently, uniformly splitting the privacy budget across groups can be inefficient; it may over-protect low-sensitivity groups while under-protecting utility-critical groups.

D.4. Reduced-Domain Record OPT

Comparison

with

Full-

We evaluate 180 configurations: ten reduced-domain cases per task, three tasks, and ϵ P t1, 2, 4, 6, 8, 10u. Both scoring variants are evaluated for each configuration, yielding 360 archived result rows. Domains contain 42–64 states for frequency estimation, 16–64 for entropy estimation, and 36–64 for crowdsourcing. Full-record OPT optimizes an unrestricted channel on the reduced joint domain, whereas groupwise all-OPT restricts the channel to the prescribed product grouping. In this additional experiment, DepHDPr/m select OPT when the corresponding score is below 0.3

and DPN otherwise. DPN uses EM with calibrated Bayesian remapping. The two-group allocation search uses 61 angular grid points under the same ℓ2 composition budget. These settings are specific to this study; the main experiments retain their original task-specific thresholds. Within each configuration, all methods use the same reduced records, saved distance matrices, task loss, and global privacy budget. Grouped methods also share the grouping and allocation-search procedure. Each mechanism policy is evaluated with its reoptimized allocation, so numerical group budgets may differ; the comparison measures the combined effect of selection and allocation rather than mechanism choice at identical budgets. ALC+DPN in Table 1 provides the analogous all-DPN comparison at the original scale. Table 3 presents representative configurations, Table 4 reports task–budget means, and Appendix D.8 lists all 180 configurations. For each configuration, loss reduction is 100pLDPN ´ LDepHDP q{LDPN , and gap closure is 100pLDPN ´LDepHDP q{pLDPN ´Lfull q. DepHDP-r achieves 44.10% mean loss reduction and 59.70% median gap closure; DepHDP-m achieves 58.44% and 85.14%, respectively. These statistics summarize per-configuration ratios across the 180 configurations, rather than ratios of pooled mean losses. Residual gaps reflect grouping, mechanism-family, and allocation restrictions. The results quantify empirical utility gains under the evaluated policies, not a general approximation guarantee. The tables retain the saved experimental metrics; the optional type-specific metrics discussed in Section 3 were not evaluated in these runs.

D.5. Held-Out Adequacy and Selection Stability For each eligible group, we repeat a distance-stratified 70%/30% fitting/validation split 20 times using deterministic seeds. Both directions of an unordered pair remain in the same split to prevent leakage. Quadratic and isotonic models are fitted on training pairs and scored on held-out pairs. We retain the original thresholds of 0.3, 0.1, and 0.2 for frequency estimation, crowdsourcing, and entropy estimation, respectively. The repeated splits assess the stability of mechanism-selection decisions at these thresholds, rather than optimize them. In deployment, thresholds may be tuned on separate calibration-validation data under an offline computation budget, with an independent final evaluation split. Table 5 reports mean original and held-out scores, mean absolute score differences (MAE), normalized aggregate gaps, and mechanism-selection agreement. The normalized gap is 100 MAE { mean |Soriginal |, rather than a mean of individual relative errors. Agreement ranges from 82.5% to

TABLE 3. R EPRESENTATIVE CONFIGURATIONS AT ϵ “ 1 FROM THE PAIRED RESULT ARCHIVE ; LOWER LOSS IS BETTER .

Task Frequency estimation Entropy estimation Crowdsourcing

Domain

Full OPT

Group OPT

DepHDP-r

DepHDP-m

All-DPN

48 16 64

1.626 0.093 8.049

1.918 0.202 11.342

2.106 0.202 14.219

2.106 0.202 11.342

4.563 0.657 23.336

TABLE 4. M EAN LOSS OVER THE TEN REDUCED - DOMAIN CONFIGURATIONS PER TASK AND BUDGET.

Task

ϵ

Full OPT

Group OPT

DepHDP-r

DepHDP-m

All-DPN

FE FE FE FE FE FE EE EE EE EE EE EE CC CC CC CC CC CC

1 2 4 6 8 10 1 2 4 6 8 10 1 2 4 6 8 10

2.33991 1.37556 0.542983 0.232117 0.114878 0.0628776 0.220488 0.0782459 0.0163287 0.00389323 0.00103439 0.000299935 8.09056 2.60194 0.477406 0.0997 0.0223023 0.00512728

2.45465 1.56796 0.719433 0.358386 0.192902 0.110149 0.297246 0.116311 0.0237594 0.00564707 0.00149691 0.000433574 9.59132 3.65556 0.73109 0.161348 0.0382795 0.00944443

2.77441 2.21219 1.49464 1.01695 0.701574 0.492743 0.303851 0.124881 0.0271871 0.00676537 0.001853 0.000546211 12.5168 6.88234 1.73085 0.431453 0.11598 0.033193

2.77441 2.21219 1.49464 1.01695 0.701574 0.492743 0.297246 0.116311 0.0237594 0.00564707 0.00149691 0.000433574 9.67667 3.97745 0.805507 0.178014 0.042653 0.0106965

3.84158 2.49833 1.59341 1.06236 0.724082 0.504512 0.630096 0.305361 0.117735 0.0512203 0.0237454 0.0114079 17.6739 10.2406 3.6328 1.61123 0.734607 0.340639

100% across evaluated task–score combinations. Two binary entropy groups have only one unordered pair and cannot support nonempty fitting and validation subsets; they are excluded from this check but retained in all task experiments. Crowdsourcing radial-fit decisions show the lowest agreement (82.5%), indicating greater sensitivity near the threshold. Resampling and threshold sweeps separately assess score stability and sensitivity across privacy budgets; they do not constitute a full resampling-by-budget factorial evaluation.

D.6. Comparison with an Approximate OPT Backend PAnDA [8] uses anchor-based approximation to reduce optimization cost. We compare it with DepHDP-r using the archived matched-domain benchmark: four domains of 64, 144, 256, and 400 states, three deterministic repeats each, and ϵ P t2, 4, 6, 10, 15u. PAnDA uses α “ 0.95, λ “ 0.4, and the benchmark range divisor 100. Table 6 reports means over the twelve runs per task and budget. At ϵ “ 6, reductions are 43.08%, 24.31%, and 25.27% for frequency estimation, entropy estimation, and crowdsourcing. These are domain-averaged results, not one representative domain per task. Each reported task–budget value averages twelve runs across four domains and three repeats. PAnDA is better in some other settings, including entropy estimation at ϵ “ 4 and crowdsourcing at ϵ “ 10, 15; neither method uniformly dominates. The comparison shows complementary

strengths across task and budget settings, including DepHDPr’s improvements in all three tasks at ϵ “ 6 and PAnDA’s gains in the settings above. LP-based OPT provides the optimum of the stated finitedomain channel problem up to numerical solver tolerances. Anchor approximation does not provide that same exact LP guarantee. Our implementation uses EM and LP-based OPT as two calibrated candidates, not an exhaustive mechanism set. Approximate backends may be added after checking their privacy conditions, profiling their loss, and screening their resource requirements. PAnDA eligibility in this run is determined by the benchmark’s configured 5,000-state resource cap.

D.7. Threshold Sweeps Across All Three Tasks We investigate how the attribute-grouping threshold τgroup in Stage 1 and the mechanism-selection thresholds τdim and τdpn in Stage 3 shape the overall utility-efficiency tradeoff of DepHDP across all three tasks. Fig. 7 examines how the grouping threshold τgroup affects end-to-end utility loss and the number of groups across frequency estimation, crowdsourcing, and entropy estimation. Increasing the threshold strengthens the dependence criterion for connecting attributes, removing weaker edges and potentially splitting groups into smaller components. This changes which attributes are perturbed jointly and which dependencies are captured within groups. Across the evaluated settings, utility loss becomes relatively stable once τgroup exceeds

TABLE 5. H ELD - OUT SCORE VALIDATION OVER 20 DISTANCE - STRATIFIED SPLITS PER EVALUATED GROUP. G AP IS 100 MAE { mean |Soriginal |.

Score

Task

Groups

Original

Held-out

MAE

Gap (%)

Agreement (%)

mse radial mse radial mse radial

FE FE CC CC EE EE

6/6 6/6 4/4 4/4 2/4 2/4

0.6983 0.7551 0.1549 0.1669 0.0298 0.0329

0.6982 0.7545 0.1554 0.1580 0.0304 0.0318

0.0006 0.0011 0.0096 0.0140 0.0016 0.0023

0.09 0.15 6.21 8.38 5.28 7.12

100.0 100.0 95.0 82.5 100.0 100.0

TABLE 6. PA N DA COMPARISON : MEANS OVER FOUR DOMAINS AND THREE DETERMINISTIC REPEATS PER TASK AND BUDGET. N EGATIVE REDUCTION FAVORS PA N DA; A DASH DENOTES A NUMERICALLY NEGLIGIBLE DENOMINATOR .

Task

ϵ

DepHDP-r

PAnDA

Reduction (%)

FE EE CC FE EE CC FE EE CC FE EE CC FE EE CC

2 2 2 4 4 4 6 6 6 10 10 10 15 15 15

0.465312 0.210615 8.94223 0.00761582 0.0911824 2.65696 0.000194363 0.0500351 1.00725 2.38347e-07 0.0198699 0.180825 0 0.0051661 0.0381289

5.94143 0.830443 26.3519 0.125029 0.0798215 4.29508 0.000341458 0.0661047 1.3478 2.32033e-08 0.0333082 0.12234 0 0.0259246 0.0376258

92.17 74.64 66.07 93.91 -14.23 38.14 43.08 24.31 25.27 – 40.35 -47.81 – 80.07 -1.34

approximately 0.2. The resulting range of thresholds with similar utility can guide calibration on these datasets, but does not establish a universally suitable grouping threshold. Figs. 8–10 study the effect of the DPN-selection threshold τdpn under two representative choices of τdim , namely 100 and 300. We report the resulting end-to-end utility loss and wall-clock computation time across different privacy budgets ϵ for Case I (Frequency Estimation), Case II (Crowdsourcing), and Case III (Entropy Estimation), respectively. For each task, we evaluate both the MSElikeness and radial-fit scores to examine the behavior of DepHDP-m and DepHDP-r. The results illustrate the utility-efficiency tradeoff controlled by the mechanism-selection thresholds. Increasing τdpn tightens the DPN selection rule, so fewer groups satisfy Skdpn ě τdpn and DepHDP invokes OPT for more groups whose domains satisfy |XGk | ď τdim . Because OPT explicitly optimizes the perturbation distribution under the mDP constraints, this shift can reduce utility loss at the cost of additional computation. The utility improvements are more pronounced in Cases I and III, whereas Case II exhibits more modest gains in the evaluated settings. Consequently, favoring DPN can provide a more attractive tradeoff for Case II when computational efficiency is prioritized. Increasing the domain-size threshold from τdim “ 100

to τdim “ 300 similarly permits OPT for additional groups. Since DPN is triggered by domain size whenever |XGk | ą τdim , a larger τdim reduces the number of groups forced to use DPN due to their domain sizes. The resulting utility and runtime changes depend on whether these additional groups also satisfy Skdpn ă τdpn and on the benefit of optimizing their perturbation channels. Together, these results show that the two thresholds should be considered jointly when balancing utility loss against computation time. Their values can be selected using separate calibration data subject to an offline computation budget.

30

40

10 5

10

0.2

0.4

0.6

0.8

1

Number of groups

Number of groups

0 0 15 10 5 0 0

0.2

0.4

0.6

20

0.8

1

0.2

0.4

0.6

0.8

1

5

0 0.2

0.4

0.6

0.8

20 15

5

10

0

25

10

0 0

=1 =2 =3 =4 =5 =6 =7 =8 =9 = 10

30

Utility loss

15

30

Utility loss

Utility loss

20

35

=1 =2 =3 =4 =5 =6 =7 =8 =9 = 10

1

Number of groups

=1 =2 =3 =4 =5 =6 =7 =8 =9 = 10

25

0 0

0.2

0.4

0.6

0.8

1

0

0.2

0.4

0.6

0.8

1

10 5 0

group

group

group

Figure 7. Grouping-threshold sensitivity for frequency estimation (left), crowdsourcing (middle), and entropy estimation (right).

18

16

16

18

12

=2 =4 =6 =8 = 10

14 12

Utility loss

Utility loss

Utility loss

=2 =4 =6 =8 = 10

14

14 12

8

8 0.6

0.8

0.2

1

0.4

0.13 0.125 0.12 0.115 0.11 0.8

pdn

Runtime, mse, domain limit 100

1

=2 =4 =6 =8 = 10

0.13 0.125 0.12 0.115

0.2

0.3

0.4

0.5

0.6

10 8

4 0.2

0.4

0.6

0.8

0.2

1

0.4

0.7

0.8

0.9

pdn

Runtime, rad, domain limit 100

100 80 60

=2 =4 =6 =8 = 10

40 20 0 0.4

0.6

0.8

1

Loss, rad, domain limit 300

120

0.2

0.6

dpn

Loss, mse, domain limit 300

0.135

0.11 0.1

12

dpn

0.14

=2 =4 =6 =8 = 10

Computation time (sec)

Computation time (sec)

0.14 0.135

0.6

1

Loss, rad, domain limit 100

Loss, mse, domain limit 100

0.4

0.8

pdn

pdn

0.2

0.6

Computation time (sec)

0.4

4

Computation time (sec)

0.2

14

6

6 8

=2 =4 =6 =8 = 10

16

10

10

10

18

=2 =4 =6 =8 = 10

16

Utility loss

18

0.8

dpn

Runtime, mse, domain limit 300

1

120 100 80 60

=2 =4 =6 =8 = 10

40 20 0 0.2

0.4

0.6

0.8

1

dpn

Runtime, rad, domain limit 300

Figure 8. Frequency estimation: mechanism-selection sweeps for both scores and two domain limits. Top: loss; bottom: runtime. The curve legends indicate privacy budgets.

20

=2 =4 =6 =8 = 10

5

=2 =4 =6 =8 = 10

10

5

0.4

0.6

0.8

0.2

1

0.4

Computation time (sec)

Computation time (sec)

35 30 25

=2 =4 =6 =8 = 10

20 15 10 0.6

0.8

0.2

0.4

30 25

=2 =4 =6 =8 = 10

20 15 10 0.4

pdn

0.6

0.2

1

0.4

0.8

60

=2 =4 =6 =8 = 10

40 20 0 0.2

0.4

0.6

1

0.8

100 80 60

=2 =4 =6 =8 = 10

40 20 0

1

0.2

0.4

pdn

0.6

0.8

1

pdn

Runtime, mse, domain limit 300

Runtime, rad, domain limit 100

0.8

Loss, rad, domain limit 300

80

1

0.6

pdn

100

pdn

Runtime, mse, domain limit 100

0.8

pdn

35

0.2

0.6

Loss, mse, domain limit 300

40

1

10

0

0

1

Loss, rad, domain limit 100

40

0.4

0.8

pdn

pdn

Loss, mse, domain limit 100

0.2

0.6

Computation time (sec)

0.2

=2 =4 =6 =8 = 10

15

5

5

0

0

10

Computation time (sec)

10

15

15

Utility loss

15

20

=2 =4 =6 =8 = 10

Utility loss

20

Utility loss

Utility loss

20

Runtime, rad, domain limit 300

Figure 9. Crowdsourcing: mechanism-selection sweeps for both scores and two domain limits. Top: loss; bottom: runtime. The curve legends indicate privacy budgets.

18

10

14

Utility loss

8 6

12 10 8

12 10 8

4

2

2

0.4

0.6

0.8

1

6

0.2

0.4

Computation time (sec)

100 80

=2 =4 =6 =8 = 10

60 40 20 0.6

0.2

1

0.8

pdn

Runtime, mse, domain limit 100

1

0.4

0.6

0.8

60

=2 =4 =6 =8 = 10

40 20 0 0.6

8

0.2

0.4

0.8

pdn

Runtime, rad, domain limit 100

1

80

=2 =4 =6 =8 = 10

60 40 20 0.4

0.6

0.8

1

Loss, rad, domain limit 300

100

0.2

0.6

pdn

Loss, mse, domain limit 300

80

0.4

10

4

1

120

100

0.2

12

pdn

Loss, rad, domain limit 100

Loss, mse, domain limit 100 120

0.4

0.8

pdn

pdn

0.2

0.6

14

6

4

Computation time (sec)

4

=2 =4 =6 =8 = 10

16

6

0.2

Computation time (sec)

=2 =4 =6 =8 = 10

14

Computation time (sec)

Utility loss

12

18

16

=2 =4 =6 =8 = 10

16

Utility loss

=2 =4 =6 =8 = 10

14

Utility loss

16

0.8

pdn

Runtime, mse, domain limit 300

1

100 80 60

=2 =4 =6 =8 = 10

40 20 0 0.2

0.4

0.6

0.8

1

pdn

Runtime, rad, domain limit 300

Figure 10. Entropy estimation: mechanism-selection sweeps for both scores and two domain limits. Top: loss; bottom: runtime. The curve legends indicate privacy budgets.

D.8. Complete reduced-domain full-OPT comparison These 180 configurations pair the radial and MSE variants from the 360-row result archive. All values are task losses (lower is better); FE, EE, and CC denote frequency estimation, entropy estimation, and crowdsourcing. Case identifiers preserve the archive names. Each task contains ten domain configurations and six budgets. Values are rounded to six significant digits. TABLE 7: All 180 paired reduced-domain configurations. Task Case CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC CC

high G2x6 G3x6 high G2x6 G3x6 high G2x6 G3x6 high G2x6 G3x6 high G2x6 G3x6 high G2x6 G3x6 high G2x6 G3x8 high G2x6 G3x8 high G2x6 G3x8 high G2x6 G3x8 high G2x6 G3x8 high G2x6 G3x8 high G2x8 G3x6 high G2x8 G3x6 high G2x8 G3x6 high G2x8 G3x6 high G2x8 G3x6 high G2x8 G3x6 high G2x8 G3x8 high G2x8 G3x8 high G2x8 G3x8 high G2x8 G3x8 high G2x8 G3x8 high G2x8 G3x8 low G1x6 G4x8 low G1x6 G4x8 low G1x6 G4x8 low G1x6 G4x8 low G1x6 G4x8 low G1x6 G4x8 low G1x8 G4x8 low G1x8 G4x8 low G1x8 G4x8 low G1x8 G4x8 low G1x8 G4x8 low G1x8 G4x8 mixed G1x8 G2x8 mixed G1x8 G2x8 mixed G1x8 G2x8 mixed G1x8 G2x8 mixed G1x8 G2x8 mixed G1x8 G2x8 mixed G1x8 G3x8 mixed G1x8 G3x8 mixed G1x8 G3x8 mixed G1x8 G3x8 mixed G1x8 G3x8 mixed G1x8 G3x8 mixed G4x8 G2x8 mixed G4x8 G2x8 mixed G4x8 G2x8 mixed G4x8 G2x8 mixed G4x8 G2x8 mixed G4x8 G2x8 mixed G4x8 G3x8 mixed G4x8 G3x8 mixed G4x8 G3x8 mixed G4x8 G3x8 mixed G4x8 G3x8

Domain 36 36 36 36 36 36 48 48 48 48 48 48 48 48 48 48 48 48 64 64 64 64 64 64 48 48 48 48 48 48 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64 64

ϵ

DepHDP-m

All-DPN

1 5.3678 6.1836 12.4526 6.35189 2 0.764878 1.19101 6.40657 1.83659 4 0.0190472 0.0517203 1.23599 0.150762 6 0.00065104 0.00284024 0.243018 0.0153976 8 2.45905e-05 0.000172382 0.0520126 0.00179245 10 6.00437e-07 1.084e-05 0.0119303 0.000221234 1 5.83235 6.66956 11.8032 6.863 2 1.04928 1.5169 6.96163 2.18907 4 0.0364036 0.0820665 1.61558 0.202937 6 0.00169162 0.00546668 0.365155 0.0225237 8 9.31987e-05 0.000410321 0.0871482 0.00285437 10 5.44866e-06 3.37756e-05 0.0218416 0.000392285 1 5.24578 5.80964 11.9981 5.90379 2 0.768284 1.13197 6.01268 1.63752 4 0.0192207 0.0485437 1.17421 0.134582 6 0.000653466 0.00267079 0.230527 0.0133728 8 2.45907e-05 0.000159882 0.0489135 0.00151373 10 5.91481e-07 1.01677e-05 0.0110652 0.000184173 1 5.71294 6.31675 11.3392 6.41363 2 1.05239 1.45085 6.59578 1.97168 4 0.03668 0.0775125 1.5452 0.183109 6 0.00169676 0.00514239 0.348879 0.0198342 8 9.32735e-05 0.000389987 0.0825213 0.00246915 10 5.37707e-06 3.18809e-05 0.0206628 0.000334782 1 10.5912 13.0384 13.0384 13.0384 2 4.76668 6.24858 6.24858 6.24858 4 1.12938 1.45136 1.45136 1.45136 6 0.24662 0.315539 0.315539 0.315539 8 0.0556282 0.0714847 0.0714847 0.0714847 10 0.0128119 0.0167139 0.0167139 0.0167139 1 11.9208 14.8472 14.8472 14.8472 2 4.81443 6.95314 6.95314 6.95314 4 1.12941 1.58268 1.58268 1.58268 6 0.24662 0.343778 0.343778 0.343778 8 0.0556282 0.0782878 0.0782878 0.0782878 10 0.0128119 0.0183097 0.0183097 0.0183097 1 1.92061 2.62092 2.73095 2.73095 2 0.0356103 0.159564 0.48948 0.48948 4 4.02406e-05 0.00146178 0.0226109 0.0226109 6 1.57606e-07 1.81556e-05 0.00144501 0.00144501 8 2.24112e-10 0 0.000109073 0.000109073 10 3.24985e-12 0 7.07212e-06 7.07212e-06 1 8.04894 11.3423 14.2191 11.3423 2 1.04327 2.55013 7.79147 2.55013 4 0.0358835 0.109019 1.47864 0.109019 6 0.00168691 0.00592079 0.279399 0.00592079 8 9.31979e-05 0.000376755 0.0563412 0.000376755 10 5.33103e-06 2.58461e-05 0.0121345 2.58461e-05 1 9.79701 10.4685 10.6593 10.6593 2 4.82542 5.39809 5.94292 5.94292 4 1.13139 1.33906 1.65055 1.65055 6 0.246656 0.306454 0.416686 0.416686 8 0.0556285 0.0725014 0.10863 0.10863 10 0.0128119 0.0175231 0.0289913 0.0289913 1 16.4681 18.6163 22.0794 18.6163 2 6.89919 9.95536 15.4212 9.95536 4 1.2366 2.56747 5.5517 2.56747 6 0.250724 0.625646 1.77011 0.625646 8 0.0558096 0.159012 0.574354 0.159012

Full OPT

Group OPT

DepHDP-r

12.4526 6.40657 1.23599 0.243018 0.0520126 0.0119303 11.8032 6.96163 1.61558 0.365155 0.0871482 0.0218416 11.9981 6.01268 1.17421 0.230527 0.0489135 0.0110652 11.3392 6.59578 1.5452 0.348879 0.0825213 0.0206628 23.18 13.8774 6.05723 3.13912 1.44479 0.669815 28.6918 16.2267 6.76591 3.38749 1.5784 0.731459 11.7456 2.76502 0.172743 0.0143111 0.00141691 0.00015629 23.3365 12.4235 2.66754 0.5364 0.115232 0.0262868 15.3669 11.1306 5.29224 2.86124 1.34639 0.640197 26.8248 20.0061 9.80139 4.98611 2.58925

Task Case CC EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE EE FE FE FE FE FE FE FE FE FE

mixed G4x8 G3x8 low G1x10 G4 low G1x10 G4 low G1x10 G4 low G1x10 G4 low G1x10 G4 low G1x10 G4 low G1x6 G3x6 low G1x6 G3x6 low G1x6 G3x6 low G1x6 G3x6 low G1x6 G3x6 low G1x6 G3x6 low G1x6 G3x8 low G1x6 G3x8 low G1x6 G3x8 low G1x6 G3x8 low G1x6 G3x8 low G1x6 G3x8 low G1x8 G3x6 low G1x8 G3x6 low G1x8 G3x6 low G1x8 G3x6 low G1x8 G3x6 low G1x8 G3x6 low G1x8 G3x8 low G1x8 G3x8 low G1x8 G3x8 low G1x8 G3x8 low G1x8 G3x8 low G1x8 G3x8 low G1x8 G4 low G1x8 G4 low G1x8 G4 low G1x8 G4 low G1x8 G4 low G1x8 G4 low G3x10 G4 low G3x10 G4 low G3x10 G4 low G3x10 G4 low G3x10 G4 low G3x10 G4 low G3x8 G4 low G3x8 G4 low G3x8 G4 low G3x8 G4 low G3x8 G4 low G3x8 G4 mixed G1x8 G2 mixed G1x8 G2 mixed G1x8 G2 mixed G1x8 G2 mixed G1x8 G2 mixed G1x8 G2 mixed G3x8 G2 mixed G3x8 G2 mixed G3x8 G2 mixed G3x8 G2 mixed G3x8 G2 mixed G3x8 G2 high G2 G6x8 high G2 G6x8 high G2 G6x8 high G2 G6x8 high G2 G6x8 high G2 G6x8 high G4x8 G5 high G4x8 G5 high G4x8 G5

Domain

ϵ

Full OPT

Group OPT

DepHDP-r

64 20 20 20 20 20 20 36 36 36 36 36 36 48 48 48 48 48 48 48 48 48 48 48 48 64 64 64 64 64 64 16 16 16 16 16 16 20 20 20 20 20 20 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 48 48 48 48 48 48 56 56 56

10 1 2 4 6 8 10 1 2 4 6 8 10 1 2 4 6 8 10 1 2 4 6 8 10 1 2 4 6 8 10 1 2 4 6 8 10 1 2 4 6 8 10 1 2 4 6 8 10 1 2 4 6 8 10 1 2 4 6 8 10 1 2 4 6 8 10 1 2 4

0.0128198 0.112889 0.00306214 7.98794e-06 0 0 0 0.199455 0.062379 0.00729569 0.000905373 0.000115937 1.50146e-05 0.277671 0.118475 0.0245462 0.0051361 0.0011296 0.000260863 0.220784 0.0626712 0.00729569 0.000905373 0.000115937 1.50146e-05 0.298969 0.118804 0.0245462 0.0051361 0.0011296 0.000260863 0.092917 0.00280183 7.96811e-06 0 0 0 0.316516 0.154556 0.0502327 0.0165741 0.0055936 0.00192587 0.309132 0.124364 0.0245654 0.0051361 0.0011296 0.000260863 0.0817471 0.00468396 6.32655e-05 9.09188e-07 0 0 0.294802 0.130662 0.0247255 0.00513823 0.0011296 0.000260863 2.77678 1.92479 0.817659 0.411897 0.235527 0.140581 2.86692 1.94194 0.634999

0.041785 0.226466 0.0193847 0.000146185 1.16765e-06 0 0 0.29367 0.100925 0.0113035 0.0014065 0.000183716 2.45291e-05 0.356018 0.163926 0.0324233 0.00668702 0.001465 0.000339681 0.316883 0.105712 0.0119005 0.00147936 0.000195154 2.60351e-05 0.37699 0.170374 0.0334725 0.0069064 0.00150722 0.000347967 0.202081 0.016587 0.000114818 7.69697e-07 0 0 0.366136 0.206806 0.0679573 0.0222566 0.00752682 0.00260503 0.36704 0.183445 0.038891 0.0083776 0.0018875 0.000448751 0.138105 0.0182776 0.000345872 6.9378e-06 1.02146e-07 0 0.329075 0.177671 0.0410389 0.00934842 0.0022036 0.000543746 2.79918 2.04303 1.11216 0.623618 0.361648 0.214922 2.89298 2.0641 0.94792

0.190273 0.226466 0.0193847 0.000146185 1.16765e-06 0 0 0.29367 0.100925 0.0113035 0.0014065 0.000183716 2.45291e-05 0.356018 0.163926 0.0324233 0.00668702 0.001465 0.000339681 0.316883 0.105712 0.0119005 0.00147936 0.000195154 2.60351e-05 0.37699 0.170374 0.0334725 0.0069064 0.00150722 0.000347967 0.202081 0.016587 0.000114818 7.69697e-07 0 0 0.366136 0.206806 0.0679573 0.0222566 0.00752682 0.00260503 0.36704 0.183445 0.038891 0.0083776 0.0018875 0.000448751 0.167793 0.0579595 0.00739382 0.000910551 0.000112548 1.40156e-05 0.365436 0.223693 0.0682683 0.0196278 0.00565203 0.0016561 3.32556 2.84918 2.08391 1.5231 1.12074 0.832826 3.4214 2.9521 2.0949

DepHDP-m

All-DPN

0.041785 1.27298 0.226466 0.697666 0.0193847 0.227533 0.000146185 0.019391 1.16765e-06 0.0016522 0 0.000146304 0 1.31288e-05 0.29367 0.684022 0.100925 0.302199 0.0113035 0.100851 0.0014065 0.0328954 0.000183716 0.0112524 2.45291e-05 0.00394207 0.356018 0.708455 0.163926 0.370361 0.0324233 0.166607 0.00668702 0.0727947 0.001465 0.0323876 0.000339681 0.0145947 0.316883 0.73819 0.105712 0.326038 0.0119005 0.10679 0.00147936 0.03464 0.000195154 0.0118454 2.60351e-05 0.00414254 0.37699 0.762367 0.170374 0.392355 0.0334725 0.173248 0.0069064 0.0753654 0.00150722 0.0334368 0.000347967 0.0150969 0.202081 0.657414 0.016587 0.202597 0.000114818 0.0165898 7.69697e-07 0.00135682 0 0.000114836 0 9.787e-06 0.366136 0.551355 0.206806 0.377114 0.0679573 0.209288 0.0222566 0.119787 0.00752682 0.0680638 0.00260503 0.0388068 0.36704 0.570222 0.183445 0.379109 0.038891 0.186297 0.0083776 0.0849061 0.0018875 0.0388567 0.000448751 0.0179225 0.138105 0.468422 0.0182776 0.138339 0.000345872 0.0182795 6.9378e-06 0.00248334 1.02146e-07 0.000345908 0 4.88792e-05 0.329075 0.462846 0.177671 0.33796 0.0410389 0.180006 0.00934842 0.0863225 0.0022036 0.0410047 0.000543746 0.0195018 3.32556 3.32556 2.84918 2.84918 2.08391 2.08391 1.5231 1.5231 1.12074 1.12074 0.832826 0.832826 3.4214 3.4214 2.9521 2.9521 2.0949 2.0949

Task Case FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE

high G4x8 G5 high G4x8 G5 high G4x8 G5 high G4x8 G6x8 high G4x8 G6x8 high G4x8 G6x8 high G4x8 G6x8 high G4x8 G6x8 high G4x8 G6x8 high G5 G6x8 high G5 G6x8 high G5 G6x8 high G5 G6x8 high G5 G6x8 high G5 G6x8 mixed G1x8 G2 mixed G1x8 G2 mixed G1x8 G2 mixed G1x8 G2 mixed G1x8 G2 mixed G1x8 G2 mixed G1x8 G5 mixed G1x8 G5 mixed G1x8 G5 mixed G1x8 G5 mixed G1x8 G5 mixed G1x8 G5 mixed G1x8 G6x8 mixed G1x8 G6x8 mixed G1x8 G6x8 mixed G1x8 G6x8 mixed G1x8 G6x8 mixed G1x8 G6x8 mixed G3x8 G2 mixed G3x8 G2 mixed G3x8 G2 mixed G3x8 G2 mixed G3x8 G2 mixed G3x8 G2 mixed G3x8 G5 mixed G3x8 G5 mixed G3x8 G5 mixed G3x8 G5 mixed G3x8 G5 mixed G3x8 G5 native G2 G5 native G2 G5 native G2 G5 native G2 G5 native G2 G5 native G2 G5

Domain 56 56 56 64 64 64 64 64 64 56 56 56 56 56 56 48 48 48 48 48 48 56 56 56 56 56 56 64 64 64 64 64 64 48 48 48 48 48 48 56 56 56 56 56 56 42 42 42 42 42 42

ϵ

Full OPT

Group OPT

DepHDP-r

DepHDP-m

All-DPN

6 0.180923 0.41105 8 0.0552049 0.17932 10 0.0188139 0.081004 1 3.03809 3.05589 2 2.27535 2.35287 4 1.10473 1.37614 6 0.539209 0.814286 8 0.286479 0.494755 10 0.161332 0.308131 1 3.09752 3.11318 2 2.38288 2.45012 4 1.1921 1.45392 6 0.5509 0.851935 8 0.275848 0.506021 10 0.151362 0.305936 1 1.62556 1.9181 2 0.411006 0.696663 4 0.0540799 0.0925045 6 0.00666839 0.0117406 8 0.000812872 0.00150988 10 9.89833e-05 0.000193345 1 1.93066 2.09642 2 0.817003 1.10211 4 0.256688 0.334383 6 0.0725706 0.0939389 8 0.0197818 0.0256005 10 0.00533744 0.00695556 1 2.10885 2.19649 2 1.19292 1.4232 4 0.678469 0.764717 6 0.393532 0.432154 8 0.233329 0.252834 10 0.140326 0.150722 1 1.50793 1.81243 2 0.414653 0.691494 4 0.0540832 0.0947303 6 0.00666839 0.0123207 8 0.000812872 0.00159902 10 9.89833e-05 0.000211154 1 1.83364 2.01278 2 0.820996 1.09798 4 0.256693 0.337376 6 0.0725706 0.0953202 8 0.0197818 0.0262255 10 0.00533744 0.00718156 1 2.61315 2.64908 2 1.57406 1.75803 4 0.380331 0.680486 6 0.0862312 0.237498 8 0.0212049 0.0795036 10 0.00548747 0.0262315

1.42991 0.953027 0.627502 3.5143 3.11682 2.40372 1.82829 1.38973 1.06179 3.53274 3.18036 2.49944 1.92194 1.46626 1.11792 2.1062 1.24654 0.49118 0.181492 0.0648236 0.022835 2.19103 1.54478 0.907525 0.514173 0.280979 0.149862 2.24332 1.74211 1.28267 0.950758 0.709684 0.534855 2.03534 1.24352 0.494173 0.18351 0.0658425 0.0232766 2.13048 1.54476 0.910518 0.516874 0.282898 0.150977 3.24374 2.70169 1.77834 1.11945 0.68175 0.405587

1.42991 0.953027 0.627502 3.5143 3.11682 2.40372 1.82829 1.38973 1.06179 3.53274 3.18036 2.49944 1.92194 1.46626 1.11792 2.1062 1.24654 0.49118 0.181492 0.0648236 0.022835 2.19103 1.54478 0.907525 0.514173 0.280979 0.149862 2.24332 1.74211 1.28267 0.950758 0.709684 0.534855 2.03534 1.24352 0.494173 0.18351 0.0658425 0.0232766 2.13048 1.54476 0.910518 0.516874 0.282898 0.150977 3.24374 2.70169 1.77834 1.11945 0.68175 0.405587

1.42991 0.953027 0.627502 3.5143 3.11682 2.40372 1.82829 1.38973 1.06179 3.53274 3.18036 2.49944 1.92194 1.46626 1.11792 4.56272 1.95121 0.699935 0.256896 0.0925124 0.0329144 4.62455 2.12545 1.11443 0.617409 0.33475 0.17816 4.66762 2.21818 1.45496 1.04714 0.769563 0.573766 3.72856 1.84411 0.694493 0.259795 0.0947395 0.0341829 3.79465 2.04423 1.11002 0.619651 0.337743 0.180476 3.24374 2.70169 1.77834 1.11945 0.68175 0.405587

Related documents

• Beyond Monolithic Perturbation: Heterogeneous Mechanism Design for Multi-Attribute Metric Differential Privacy#1201574
• The Privacy Pass Architecture#134714
• Using Pictograms to Make Privacy Agreements More Accessible#1060624
• A Human-LLM Teaming Framework for Privacy Risk Analysis: An Illustration with CBDC-Based Welfare Schemes#625053
• A Human-LLM Teaming Framework for Privacy Risk Analysis: An Illustration with CBDC-Based Welfare Schemes#622780