{"id":"7d7b2d04-1533-4b2f-b99d-ac7991863781","arxiv_id":"2412.14380","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"PrivPareto and PrivAgg extend differentially private selection to multiple objectives by composing the sensitivities of individual utility functions into one private score.","lead":"The paper introduces two differentially private mechanisms, PrivPareto and PrivAgg, for picking good options when several goals compete, using both worst-case and local sensitivity. Tests on private decision trees and influential-node selection in social networks show the local-sensitivity versions keep much more utility at small privacy budgets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Per-call epsilon is used repeatedly in DP-MOET and DP-MOTkIN without sequential-composition accounting, so the reported utility at epsilon in [0.01,1] does not establish the claimed end-to-end privacy budget.","rationale":"I read the paper as making two main contributions: a theoretical framework for differentially private multi-objective selection with composed sensitivities, and an experimental demonstration that local-sensitivity variants achieve good utility at small privacy budgets. The theoretical framework is plausible; the apparent sign errors in the appendix proof of Theorem 4.7 look like typos in the written exposition rather than a disproof of the claimed admissibility, and the statement is consistent with known smooth-sensitivity arguments. The issue that actually undermines the central empirical claim is the privacy accounting in the evaluation. The algorithms invoke the selection mechanism many times, but the paper consistently reports the single per-call epsilon as if it were the total privacy budget. This makes the utility advantage over single-call baselines and the abstract's epsilon in [0.01,1] claim unsupported. The concern is concrete, reproducible from the text, and independent of the theoretical soundness of the mechanisms. It does not change the CONDITIONAL verdict, because the theoretical contribution may still be valid and the experiments could be rerun with correct composition, but it is the load-bearing reason the empirical conclusions cannot be accepted as stated.","tokens_in":30250,"tokens_out":18383,"duration_ms":156322,"concrete_test":"Re-run the DP-MOET and DP-MOTkIN experiments with the total privacy budget fixed, for example by dividing the per-call epsilon by the number of private selection calls (k*s + final calls for DP-MOET, k calls for DP-MOTkIN) or by reporting the composed total budget next to every result. Then check whether the local-sensitivity methods still reach the claimed utility levels at a total epsilon in [0.01,1]. If the utility at the true composed budget degrades, the empirical headline should be revised.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central empirical claim is that the local-sensitivity mechanisms achieve strong utility at privacy budgets epsilon in [0.01,1]. The experiments do not actually deliver that claim because Algorithm 1 passes the same epsilon to every private selection call and never splits or composes the budget. In DP-MOET, line 4 calls DP_MOSelection once per generation, and Section 6.2.1 states that DP_MOSelection invokes the underlying PrivPareto/PrivAgg mechanism s times to select s trees; line 15 makes at least one additional final selection call. For the Section 6.3 parameters s=3,k=3 this is already at least 3*3+1=10 calls, and for the Section 6.4 aggregation parameters s=20,k=2 it is at least 41 calls. Likewise, the DP-MOTkIN algorithms call the private selection mechanism once per selected node. By Theorem 2.2, sequential composition means the total privacy loss is the sum of the per-call budgets, so the value labeled epsilon in the tables and figures is not the total privacy budget of the end-to-end algorithm unless all calls share a single epsilon, which the paper does not state or implement. Consequently, the comparison against single-call baselines such as LocalDiffPID3 and the claim of good utility at total epsilon <= 1 are unsupported. This is not a flaw in the mechanism definitions, which may well be epsilon-DP per call; it is a flaw in the privacy accounting used to support the headline utility results.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two mechanisms for differentially private multi-objective selection: PrivPareto, which scores candidates by how dominated they are in a Pareto sense, and PrivAgg, which selects according to a weighted sum of utility functions. For each mechanism the paper develops global- and local-sensitivity versions, with theorems showing how to compose sensitivities of the individual utility functions. The mechanisms are instantiated in two end-to-end frameworks, DP-MOET for cost-sensitive decision trees and DP-MOTkIN for influential node selection, and evaluated on several datasets. The paper claims that the local-sensitivity variants have strong utility for privacy budgets epsilon in [0.01, 1].","tokens_in":30611,"tokens_out":15271,"duration_ms":125779,"significance":"If the local-sensitivity theory were fully correct, this would fill a genuine gap: a general primitive for multi-objective selection under differential privacy with composable sensitivity bounds, plus two concrete application families and a public artifact link. The aggregation sensitivity theorems are simple and essentially correct in substance, and the experimental study is extensive. However, the local-sensitivity admissibility proofs and the end-to-end privacy accounting currently do not support the headline claims, so the contribution is conditional on substantial repairs.","major_comments":[{"comment":"The value called epsilon in the experimental sections is not the total privacy budget of the end-to-end algorithms. In Algorithm 1, line 4 passes the same epsilon to DP_MOSelection, and Section 6.2.1 states that DP_MOSelection invokes the underlying PrivPareto/PrivAgg mechanism s times; line 15 adds a further selection of o items. For the Section 6.3 parameters (s=3, k=3, o=3) this is at least 12 calls, and for the Section 6.4 parameters (s=20, k=2, o=1) it is 41 calls. The DP-MOTkIN family (Section 7.2) similarly calls the private selection mechanism k times. By Theorem 2.2, the total privacy loss is the sum of the per-call budgets, yet the paper does not split epsilon across calls nor report the total. Therefore the claim that local-sensitivity mechanisms achieve strong utility at epsilon in [0.01, 1] is unsupported, and the comparisons with single-call baselines such as LocalDiffPID3 are not made at equal privacy. The authors should divide the budget across calls and report the total, or clearly report both per-call and total budgets and re-evaluate utility at fixed total epsilon.","section":"§6.2.1, §7.2; Theorem 2.2; Tables 1–2 and Figures 2–3"},{"comment":"The proof that delta_PS is admissible contains an incorrect inequality. In the analysis of the first term of Eq. (11), the proof states that for neighboring x and y, u_i(x,r) >= u_i(y,r) + delta_{u_i}(y,0,r). Admissibility and the definition of local sensitivity give |u_i(x,r) - u_i(y,r)| <= LS_{u_i}(y,0,r) <= delta_{u_i}(y,0,r), so the correct lower bound is u_i(x,r) >= u_i(y,r) - delta_{u_i}(y,0,r), not with a plus sign. The set-containment argument in that step uses the incorrect direction. Since admissibility of delta_PS is exactly what licenses the local PrivPareto mechanism's epsilon-DP guarantee, this is a load-bearing gap. A corrected proof is needed.","section":"Appendix A.1, proof of Theorem 4.7"},{"comment":"The function delta_TPR is not admissible as defined. The proof correctly derives LS_TPR(x,0,tau) = max( (P-TP)/(P(P-1)), TP/(P(P-1)) ). However, for t=0 the branch condition \"t <= P-TP\" is always true because P-TP >= 0, so the definition yields delta_TPR(x,0,tau) = (P-TP)/(P(P-1)) only. When TP > P/2 this is strictly smaller than LS_TPR; for example, P=10, TP=9 gives LS_TPR = 0.1 but delta_TPR = 1/90. Thus condition 1 of Definition 2.7 fails. Because delta_TPR and delta_TNR are the admissible sensitivity functions used as inputs to delta_PS and delta_uagg in the local versions of DP-MOET, the privacy guarantees of those instantiations are not established. The definition should be changed to the maximum of the two branches, or to a true upper bound, and the admissibility proof reworked.","section":"Section 6.2.3 and Appendix A.2, Lemma 6.1"}],"minor_comments":[{"comment":"Definition 4.3 defines the Pareto score as -|{r' in R : r' >=_x r}|, which includes r itself since u_i(x,r) >= u_i(x,r). This makes every Pareto score at most -1, contradicting Example 4.4, where Pareto-optimal candidates receive score 0, and the subsequent discussion of global sensitivity in Section 4.2. The definition should exclude the candidate itself, i.e., use r' in R \\ {r}.","section":"Definition 4.3 and Example 4.4"},{"comment":"The proof of Theorem 5.4 contains a false equality: after applying the triangle inequality, the text writes \"= LS_{u_agg}(x,0,r)\" for an expression involving |w_i|. The correct step is sum_i |w_i| LS_{u_i}(x,0,r) >= max_{y: d(x,y)<=1} |sum_i w_i (u_i(x,r)-u_i(y,r))| = LS_{u_agg}(x,0,r). This is a fixable presentation error, but the current chain is mathematically incorrect.","section":"Theorem 5.4 proof"},{"comment":"The shorthand u^{+t}_i(x,r) is defined as u_i(x,r) + sum_{i=0}^t delta_{u_i}(x,i,r), reusing the index i for both the utility-function index and the summation index. This should be written with a separate summation index, e.g., sum_{j=0}^t.","section":"Definition 4.5"},{"comment":"In the decomposition of Line 11, the text writes \"ndom_{y,r} = (ndom_{x,r} ∩ dom_{y,r}) ∪ (ndom_{x,r} ∩ dom_{y,r})\"; the second term should be (ndom_{x,r} ∩ ndom_{y,r}).","section":"Appendix A.1"},{"comment":"The proposed delta_egodensity(G,t,v) can exceed the global sensitivity: for |N_G(v)| = 3 and t = 0, the formula gives 2/(3-0-2) = 2, while the egodensity is in [0,1] and Delta_egodensity is 1. If the paper's stated goal of staying below Delta_u is intended, the function should be capped.","section":"Section 7.3"},{"comment":"The caption says epsilon = {10^{-1}, 10^0, 10^1, 10^2, 10^3}, but the table rows include 0.1, 0.5, 1.0, 2.0, 5.0, 10.0, 20.0, 50.0. The caption and table should be aligned.","section":"Table 2 caption"}],"recommendation":"major_revision","confidential_remarks":"The local-sensitivity errors are concentrated in the admissibility proofs for delta_PS and delta_TPR, and the end-to-end privacy accounting is missing. All appear fixable in principle, but the experimental claims will need to be redone at correct total privacy budgets, so I would not accept the paper in its current form. Please ask the authors for a complete corrected proof of Theorem 4.7 and Lemma 6.1, and for a re-analysis of the experiments under proper sequential composition."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know about this paper. First, it does something genuinely useful: it takes the single-objective DP selection toolbox (exponential mechanism, report-noisy-max, local dampening) and shows how to feed it a Pareto score or a weighted aggregate of several utility functions, with sensitivity computed from the sensitivities of the individual utilities. Definition 4.5's delta_PS and Theorems 5.3/5.4 are the real content, and they are reusable building blocks for anyone doing DP selection with multiple objectives. The applications to decision trees and influential nodes are reasonable testbeds, and the local-sensitivity variants clearly beat global-sensitivity baselines in their experiments.\n\nSecond, the paper as it stands has two soft spots. The bigger one is the privacy accounting in the experiments. Algorithm 1 calls the private selection mechanism multiple times: s times per generation, k generations, plus a final call, and the same epsilon is passed to every call. Under sequential composition (Theorem 2.2, which the paper itself states), the total privacy loss is a multiple of that epsilon, not epsilon. The paper never splits the budget or reports the total, so the claim of good utility at epsilon in [0.01, 1] for the end-to-end algorithms is unsupported. This does not sink the per-call mechanisms, which may well be epsilon-DP, but it does sink the headline empirical comparison. The fix is straightforward: allocate the budget per call or report the composed total.\n\nThe smaller soft spot is in the proof of Theorem 4.7. In the appendix, showing delta_PS(x,t+1,r) >= delta_PS(y,t,r) uses the inequality u_i(x,r) >= u_i(y,r) + delta_{u_i}(y,0,r). For neighboring x,y, admissibility gives u_i(x,r) <= u_i(y,r) + delta(y,0,r) and u_i(x,r) >= u_i(y,r) - delta(y,0,r); the sign is wrong. The theorem may still be true — the definition of delta_PS is plausible — but the proof as written has a gap. That needs a fix before the mechanism's DP guarantee rests on it.\n\nNeither issue is fatal to the framework. The mechanism definitions are separable from the experimental accounting, and the proof gap is localized. But both need to be addressed before the empirical claims are taken at face value.\n\nThis paper is for anyone working on DP selection, DP optimization, or private machine learning. It deserves a serious referee, and I would send it out, but I would expect heavy revision on the experiments and a corrected proof of Theorem 4.7.","headline":"Useful mechanism-level ideas for DP multi-objective selection, but the experimental privacy accounting and a key proof step are not sound as written.","tokens_in":31142,"tokens_out":2685,"would_cite":true,"duration_ms":22872,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper introduces two differentially private mechanisms, PrivPareto and PrivAgg, that select near-Pareto-optimal candidates under multiple competing objectives, with local-sensitivity versions that stay accurate at privacy budgets as…","keywords":["differential privacy","multi-objective selection","Pareto optimality","local sensitivity","global sensitivity","exponential mechanism","decision trees","influential node selection"],"falsifier":"Run DP-MOET with s=3, k=3, and output size 3 and count the calls to DP_MOSelection: three selections per generation for three generations plus one final selection, so ten calls. Feed that count into the sequential composition theorem to compute the total budget as 10 x epsilon; then compare output utilities at epsilon=0.01 and 0.1 under this accounting and audit privacy loss empirically on a neighboring dataset to determine whether the reported epsilon is the per-call or total budget.","tokens_in":30075,"feed_emoji":"🔒","tokens_out":7436,"duration_ms":61364,"temperature":0.7,"pith_summary":"Existing differentially private selection mechanisms handle a single objective, but many real problems—medical diagnosis, network influence, decision-tree construction—require balancing several competing objectives at once. The paper closes that gap with two mechanisms: PrivPareto, which scores each candidate by how many other candidates dominate it and privately selects a point near the Pareto frontier, and PrivAgg, which privately selects by a weighted sum of the objectives. The core technical contribution is a way to compute the sensitivity of these composite scores from the sensitivities of the individual utility functions, supporting both global and local sensitivity. Experiments on cost-sensitive decision trees and top-k influential node selection show that the local-sensitivity versions achieve utility close to non-private baselines at epsilon in [0.01, 1], where global-sensitivity versions need far larger budgets.","feed_headline":"Private multi-objective selection works at low epsilon","feed_subtitle":"PrivPareto and PrivAgg pick near-Pareto-optimal candidates while keeping data private, even at epsilon 0.01.","key_machinery":"The load-bearing object is the admissible sensitivity function, a computationally efficient upper bound $\\delta_u(x,t,r)$ on element local sensitivity that satisfies two conditions: it dominates the actual sensitivity at $t=0$, and it does not increase too fast as the database moves to a neighbor at distance $t$. The paper proves that this property is preserved under the two composite scores: for the Pareto score, $\\delta_{PS}(x,t,r) = |dom^-_{x,t,r}| + |ndom^+_{x,t,r}|$ counts how many candidates could change domination status within distance $t$; for the weighted sum, the weighted combination of admissible per-objective functions is again admissible. This lets a data analyst provide only per-objective sensitivities, and the machinery composes them automatically for use in a single-objective DP selector.","core_discovery":"The central claim is that multi-objective private selection can be reduced to single-objective private selection by defining a composite score whose sensitivity is algorithmically derivable from user-supplied sensitivities. For PrivPareto, the Pareto score $PS(x,r) = -|\\{r' \\in R : r' \\succeq_x r\\}|$ counts how many candidates dominate $r$; the paper proves that $\\delta_{PS}(x,t,r) = |dom^-_{x,t,r}| + |ndom^+_{x,t,r}|$ is an admissible sensitivity function, making the local-sensitivity version differentially private. For PrivAgg, the weighted sum $u_{agg} = \\sum_i w_i u_i(x,r)$ has global sensitivity bounded by $\\sum_i |w_i| \\Delta_{u_i}$ and an admissible local-sensitivity function $\\delta_{u_{agg}}(x,t,r) = \\sum_i |w_i| \\delta_{u_i}(x,t,r)$. With these compositions, any single-objective selection mechanism—exponential, report-noisy-max, permute-and-flip, or local dampening—can be dropped into the selection step. The paper also derives admissible sensitivity functions for true positive rate, true negative rate, degree centrality, and egocentric density, and embeds the mechanisms in evolutionary algorithms for decision trees and top-k node selection.","pith_inferences":["Because admissibility is preserved when per-objective sensitivity functions are composed, the same construction extends beyond the paper's two examples: any composite score built from monotone operations on admissible sensitivity functions could be plugged into PrivPareto or PrivAgg.","The paper's per-run privacy accounting is ambiguous: DP-MOET invokes the private selector $s$ times per generation for $k$ generations plus one final call, so under sequential composition the total budget is a multiple of the reported epsilon; a clean end-to-end guarantee would require either splitting epsilon across calls or reporting the total.","The Pareto-score mechanism requires no weights, so it may be the better fit when objectives are incommensurate or when the analyst cannot justify a weighting; PrivAgg remains the tool when weights are known.","A natural stress test is to compare the two mechanisms' regret against the true Pareto set on synthetic fronts where the optimum is known, isolating score quality from sensitivity estimation."],"forward_implications":["Data analysts can apply differentially private multi-objective selection to a new problem by supplying only the utility functions and their per-objective sensitivities; the composite sensitivity is computed automatically.","Local-sensitivity versions achieve substantially better utility than global-sensitivity versions in both applications, and in most experiments match non-private baselines at epsilon in [0.01, 1].","The mechanisms are composable building blocks: DP-MOET for cost-sensitive decision trees and DP-MOTkIN for top-k influential node selection are built from the same selection step, so the same machinery can be embedded in larger private algorithms.","The sensitivity framework covers both node-based utilities (true positive rate, true negative rate) and edge-based utilities (degree centrality, egocentric density), spanning at least two common privacy models."],"supporting_citations":[{"why":"Defines admissible sensitivity functions and the local dampening mechanism; PrivPareto and PrivAgg rely on this admissibility framework.","marker":"[12]"},{"why":"Introduces local sensitivity and local sensitivity at distance t, the theoretical basis for the local-sensitivity versions.","marker":"[29]"},{"why":"Provides the exponential mechanism and the sequential composition theorem used as the selection step and privacy accounting.","marker":"[27]"},{"why":"Supplies the permute-and-flip mechanism, one of the single-objective selectors that can replace the selection step.","marker":"[26]"},{"why":"Supplies report-noisy-max, another single-objective selection mechanism that PrivPareto and PrivAgg can use.","marker":"[11]"},{"why":"Defines the C-metric used to measure how much of the non-private Pareto front the private methods recover.","marker":"[40]"},{"why":"Inspires the DP-MOET evolutionary search structure for building decision trees.","marker":"[37]"}],"fun_headline_variants":["PrivPareto and PrivAgg: private multi-objective selection","Multi-objective DP selection works at epsilon 0.01","Local sensitivity unlocks low-epsilon multi-objective privacy","Compose sensitivities to pick Pareto-optimal privately"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The experiments report epsilon as if it were the total privacy budget for the whole evolutionary algorithm, although the algorithm calls the private selection step many times, so the true total budget is larger than the reported value.","fun_headline_variants_meta":{"raw":{"variants":["PrivPareto and PrivAgg: private multi-objective selection","Multi-objective DP selection works at epsilon 0.01","Local sensitivity unlocks low-epsilon multi-objective privacy","Compose sensitivities to pick Pareto-optimal privately"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000902,"raw_usage":{"total_tokens":3913,"prompt_tokens":1005,"completion_tokens":2908,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":621,"completion_tokens_details":{"reasoning_tokens":2840}},"tokens_in":621,"tokens_out":2908,"duration_ms":18908,"temperature":1.0,"reasoning_tokens":2840,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:17:02.526287+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run DP-MOET with s=3, k=3, and output size 3 and count the calls to DP_MOSelection: three selections per generation for three generations plus one final selection, so ten calls. Feed that count into the sequential composition theorem to compute the total budget as 10 x epsilon; then compare output utilities at epsilon=0.01 and 0.1 under this accounting and audit privacy loss empirically on a neighboring dataset to determine whether the reported epsilon is the per-call or total budget.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines admissible sensitivity functions and the local dampening mechanism; PrivPareto and PrivAgg rely on this admissibility framework."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces local sensitivity and local sensitivity at distance t, the theoretical basis for the local-sensitivity versions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the permute-and-flip mechanism, one of the single-objective selectors that can replace the selection step."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies report-noisy-max, another single-objective selection mechanism that PrivPareto and PrivAgg can use."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the C-metric used to measure how much of the non-private Pareto front the private methods recover."}],"review_version":1}