acceptodds
Under review as a conference paper at ICLR 2027

Privacy Admission from Incomplete Rényi Differential Privacy Histories

12 views

Abstract

A privacy accountant must decide whether a proposed release, together with past outputs, meets a total differential privacy budget. We study this decision when the historical record contains only upper bounds at finitely many Rényi differential privacy (RDP) orders, while the proposed request has a known privacy profile. The record defines a class of possible histories. For a request fixed independently of past private outputs and run with fresh randomness, we maximize its composed privacy value over that class while preserving the request as a factor. Retaining only multiplied RDP moments instead permits aggregate laws inconsistent with the specified request. We prove strict randomized-response and Gaussian-DP separations in which this information loss blocks safe admission. Moment duality gives checkable upper bounds with explicit allowances for historical tails and numerical errors. Controlled comparisons recover admissions that the aggregate summary cannot justify and distinguish this information gain from improvements in computed bounds. A second comparison holds the request profile fixed: direct optimization sharpens some admission bounds relative to a reusable historical profile, while reuse trades preparation cost for cheaper subsequent queries.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
differential privacy, privacy accounting, Rényi differential privacy, moment problems, privacy profiles

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_wvY7OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies the problem of privacy admission (i.e. accounting or composition) under the assumption that historical mechanisms may have lost information: only their RDP guarantees for a finite number of mm orders are visible to the accountant, who makes decision about whether the new mechanism can be admitted while satisfying an overall approximate-DP constraint. The key observation/assumption is that the distribution of the new mechanism can be known in exact, therefore converting it to an RDP guarantee for composition with historical mechanisms under known orders brings unnecessary privacy loss. The paper argues in that this loss can be strict, and proposed a solution based on optimization.

The general concept behind the idea is interesting: that compositions can be more accurate by considering exact distributions instead of potentially loose (R)DP bounds, and the paper has a reasonable theoretical contribution with both algorithm design and separation analysis. However, I find the paper difficult to follow, not merely because it is math-involved, but also due to problems like undefined notation, missing pointers to the appendix, and abstract theorems without sufficient intuition or illustrating examples. Besides, I am also concerned about the realism of the problem setting, and the evaluataion.

Critical strengths

S1. The observation that composition from exact distributions provides more accurate privacy guarantees then composition over loose (R)DP guarantees is interesting and may inspire future research that may be beyond the scope of that the paper considers.

S2. The paper is deeply math-involved in its detailed problem formulation, separation results and algorithm design, so that there is a reasonable technical depth.

Critical weaknesses

W1. I find the paper difficule to follow. As mentioned, this is not merely due to its theoretical flavor. In particular:

W1.1. I suppose Section 3 is for preliminaries. However, many definitions are missing here. For example, the paper does not itself contain a formal definition for RDP except for the bounds mentioned near line 110, which can make it hard for readers who are not very familiar with the literature. Besides, the definition of approximate-DP also do not look standard (although it is correct). Near line 125, superscripts like "ac" or ⊥\perp are undefined. "Lebesgue decomposition" was mentioned in Theorem 11 in the appendix, but not here and there is no pointer to it. Similar problems in definitions for hh, K\mathcal{K}, WW and CC (is there a reason for using different characters for WW and CC?). All these makes the presentation difficult to follow, despite a relatively straightforward underlying idea.

W1.2. Line 214 says "Let GμG_\mu denote GDP ... The privacy loss of GμG_\mu is ...". From my understanding Gaussian DP is a privacy notion (similar to RDP), does it mean GμG_\mu is a mechanism that satisfies GDP? Again, no definition for GDP nor pointer to appendix or reference. No formal definition for FaF_a for RR and η\eta.

W1.3. I would suggest providing concrete examples for Theorem 2 to make the paper easier to follow. Currently it only shows that there can be a possible gap. It would be more meaningful to show how large the gap can be under meaningful parameter choices, which also makes the proof more convincing.

W2. While the contribution in algorithm design is meaningful, the problem setting and assumptions require further justification.

W2.1. Is there a concrete example where historical compression can be lossy? The paper justified this in the second paragraph by saying that diverse mechanisms can be applied that provide privacy guarantee unified under RDP, but (1) this does not explain why only a finite number of orders can be kept, since the privacy loss function that accepts α\alpha as a parameter also requires finite storage; (2) the underlying mechanisms are "different" but not "lost", would considering their exact distributions provide a even better result than what this paper is proposing?

W2.2. The abstract assumes that the new request is fixed independently of past private outputs, thus adaptive composition is forbidden, which narrows the practical usage of the proposed solution.

W2.3. While the paper assumes that historical information can be lost such that only finite orders remain, its assumption in Line 110 is that the Renyi divergence bounds in two directions are stored in separate. This is questionable under the proposed setting: the more realistic assumption is that only the final bound, namely the larger of the two is kept.

W3. Experimental settings are somewhat limited. The evaluation considers orders from 2-8, and focused on accept/reject decisions. Based on the inequality near line 152, it is more reasonable to measure the privacy gain, namely the difference in the tolarated δ\delta achieved by the naive composition verses the solution proposed. Besides, the paper should also investigate or discuss about whether the privacy gain works on ε\varepsilon (note that the inequality assumes the same γ\gamma). It would also be interesting wo see the overhead compared to considering exact distributions for all mechanisms, i.e., the lossless case.

Questions for authors

See W1.1, W1.2, W2.1.

4 comments

Thank you for your detailed review. We appreciate your helpful suggestions.

We have uploaded a revised version, with red margin notes naming the review point each change addresses.

W1.1

The revised Background (Section 3) states approximate DP in its standard form: P(A)≤eεQ(A)+δP(A)\le e^\varepsilon Q(A)+\delta for every measurable event and ordered neighboring pair. For α>1\alpha>1, Dα(P∥Q)=log⁡EQ[(dP/dQ)α]/(α−1)D_\alpha(P\Vert Q)=\log\mathbb E_Q[(dP/dQ)^\alpha]/(\alpha-1), so an RDP bound is the moment inequality stored in the receipt. “ac” and “⊥\perp” are the absolutely continuous and singular parts of the request in its Lebesgue decomposition with respect to QQ, and hF(t)=sup⁡A(PF(A)−tQF(A))h_F(t)=\sup_A(P_F(A)-tQ_F(A)) is the request's hockey-stick profile, singular mass included. WW and CC name the values of two different optimization problems: WFW_F maximizes over compatible histories with the request factor fixed (the class KF\mathcal K_F), and CaggC_{\rm agg} over all laws satisfying only the multiplied moments, with KF⊆Aagg\mathcal K_F\subseteq\mathcal A_{\rm agg}. The revision gives these formal definitions in the new Background section (Section 3), defines hh, K\mathcal K, WW, CC and the Lebesgue-decomposition notation where they first appear (Section 4), and points to Theorem 11 in Appendix D.1.

W1.2, W1.3

GμG_\mu is the canonical Gaussian binary experiment (N(μ,1),N(0,1))(N(\mu,1),N(0,1)), the pair that defines μ\mu-GDP. FaF_a is symmetric RR, whose QQ-side likelihood ratio is aa with probability 1/(a+1)1/(a+1) and 1/a1/a otherwise. The historical slack η\eta means EX2,EX−1≤1+η\mathbb EX^2,\mathbb EX^{-1}\le1+\eta. The revision defines GμG_\mu and μ\mu-GDP in Section 3 and FaF_a and η\eta in Section 5 before Theorem 2; the separation proofs are in Appendix D.3.

For example, substitute a=3a=3, η=1/2704\eta=1/2704 into Theorem 13. At γ=5\gamma=5,

WF(5)≤1/52<1/40<1/26≤Cagg(5).W_F(5)\le1/52<1/40<1/26\le C_{\rm agg}(5).

The cap δ=1/40\delta=1/40 separates the decisions, and the difference in privacy values is at least 1/52≃0.01921/52\simeq0.0192. The aggregate witness has mass 1/261/26 at likelihood ratio 6. At this cap its contribution requires γ≥6−26/40=107/20\gamma\ge6-26/40=107/20, whereas retention already admits at γ=5\gamma=5, so the epsilon gap is at least log⁡(107/100)≃0.0677\log(107/100)\simeq0.0677. The revision adds this worked example after Theorem 2 (Section 5).

W2.1

A standard case is DP-SGD: Opacus's RDP accountant composes privacy on a fixed default list of 151 orders, and when that RDP vector, rather than the training configuration, is passed to a later accountant, it is exactly our receipt. On (1): what is passed on is a list of numbers at fixed orders, and no fixed finite set of RDP orders is universally future-sufficient, even with exact saved moments (Proposition 1; Appendix C). On (2): when the full historical laws are available, exact-history accounting applies and can be tighter; our accountant serves the case where only the record is passed on. The revised Introduction gives the Opacus example.

W2.2, W2.3

Adaptive requests are covered when they postprocess a fixed request: Proposition 10 (Appendix D.1) covers transcript-dependent requests Fz=Kz∘F⋆F_z=K_z\circ F^\star when F⋆F^\star is fixed and the data-independent postprocessing kernels are jointly measurable, and the joint output is then dominated by EH⊗F⋆E_H\otimes F^\star. For example, the transcript can select additional noise above a fixed Gaussian baseline, and the accountant checks that baseline. The revision states this condition in Section 4.

Keeping only the larger bound also fits the receipt: a single usual (αj,ρj)(\alpha_j,\rho_j)-RDP bound valid for all ordered neighboring pairs supplies Mj+=Mj−=exp⁡((αj−1)ρj)M_j^+=M_j^-=\exp((\alpha_j-1)\rho_j), and Section 4 notes after the receipt definition that separate directional storage is optional. The DP-SGD record below uses this convention.

W3

The gain appears in privacy values as well as in decisions. The example above guarantees a gain of at least 1/521/52 in δ\delta and at least log⁡(107/100)\log(107/100) in ε\varepsilon. On a DP-SGD record on Opacus's default orders (Section 7.3, Table 3), a Gaussian request μ=1/2 receives certified δ bounds of 2.3e-2, 1.0e-3 and 3.8e-6 at ε=1.10, 1.95 and 3.00, while feasible aggregate laws reach 4.8e-2, 2.7e-3 and 1.2e-5. The aggregate accountant there receives all 61 integer orders. On the 30 Table 2 cases, the same-input aggregate comparison gives certified gaps in 16 cases, up to 0.319 versus 0.423.

When full historical laws are available, exact-history accounting can be cheaper and tighter (Section 7.1, Appendices B.5 and B.9): the two-atom history needs two request-profile evaluations, whereas receipt-based accounting must additionally optimize and verify over all compatible histories.

We hope these responses address your concerns, and we would be grateful if you would consider raising your score.

Thank you for the feedback. I have checked the revision file, while my concerns have been addressed case-by-case, the writting (i.e. W1) has not improved too much, and the paper still looks LLM-generated in general: theoretical claims without sufficient heuristics or examples, tons of symbols in the main text, tabular display of experiment results without figures... They all make the paper extremely hard to follow (for a human reader), and the revised version keeps a similar writing style. Given that one other reviewer also raised concerns on presentation, I am doubtful about whether the current writing is understandable to a general audience of the conference.

I agree that the underlying idea can be interesting, but the paper should be presented in a more human-readable way for evaluating its contribution in my opinion.

Thank you for your continued engagement and for the constructive feedback. We take your comments on presentation seriously.

We are revising the main text to make it easier to follow, and will upload the new version before the discussion deadline. We would be grateful if you could take another look.

Thank you very much for the time you have spent on our paper, for checking the revision, and for naming what makes it hard to follow. We have uploaded a further revision of the main text, with the passages rewritten for readability shown in blue.

Each main result is now preceded by a worked instance. The Introduction gives a randomized-response example, with the threshold, the historical bound and the two privacy values, before any result is stated. Section 5 computes the same instance before Theorem 2 and displays the two-point law that the multiplied moments allow, and Section 6.1 shows how one quadratic function gives the upper bound before Theorem 3. Section 4 now works in one direction without an index, defines the two values compared with the cap in words, and uses fewer symbols; Section 3 sets the standard definitions as displayed formulas. In Section 7, Figure 1 now shows the two main comparisons, the decisions of the direct and aggregate accountants on identical inputs and the DP-SGD caps that the direct accountant admits while an aggregate law exceeds them, with the exact values moved to Appendix A.

We would be grateful if you could take another look. There is still time before the end of the discussion period, and if any passage remains hard to follow or you have further suggestions, we would be glad to revise it.

Reviewer_ao1uOpenReview ↗
Rating
4(+2)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This work initiates the study of privacy accounting with compressed historical Renyi differential privacy profiles.

Concretely, the authors consider the following problem (in this summary, I assume symmetry of the moment bounds for exposition):
We want to determine if a composed mechanism M2∘M1M_2 \circ M_1 is (ϵ,δ)(\epsilon,\delta)-DP. However, the only information we have about M1M_1 is that it is (αj,ρj)(\alpha_j,\rho_j)-RDP for some finite set of orders {αj}\{\alpha_j\}.

A naive solution to this problem would be to use standard RDP accounting, i.e., determine RDP parameters (αj,ρj′)(\alpha_j,\rho'_j) for our mechanism M2M_2, infer that the composed mechanism must be (αj,ρj+ρj′)(\alpha_j,\rho_j + \rho'_j)-RDP, lossily convert this to an (ϵ,δ′)(\epsilon,\delta')-DP guarantee, and check if δ′≤δ\delta' \leq \delta. A more refined solution would be to instead consider the worst-case δ′\delta' that can be realized by a privacy loss random variable L(Z)L(Z) under the shared (αj,ρj+ρj′)(\alpha_j,\rho_j + \rho'_j)-RDP constraints.

However, the authors demonstrate that there exists an even better approach. Rather than discarding most information about known mechanism M2M_2 by compressing it into a composed RDP profile, one can instead use L(X)+L(Y)L(X) + L(Y), where L(X)L(X) is the known privacy loss random variable for M2M_2 and L(Y)L(Y) is the worst-case privacy loss random variable under the historical (αj,ρj)(\alpha_j,\rho_j)-RDP constraints.

The first core contribution is that the authors prove strict separation between both approaches when M2M_2 is either randomized response or a Gaussian mechanism (or an equally private mechanism), and we only have historical constraints for α=2\alpha=2.

The second core contribution is a concrete algorithmic procedure for upper- and lower-bounding δ′\delta' that only requires optimization over linearly many probability atoms, rather than the entire manifold of privacy loss distributions. The procedure is first introduced for privacy loss random variables with compact support. This restriction is then lifted by mapping RDP bounds to tail bounds on the privacy loss distribution. Finally, the authors show that the cost can be amortized over many different M2M_2 by reusing computations made for the same historical RDP guarantees.

In the experimental section, the authors first demonstrate that the already proven separation for randomized response and α=2\alpha=2 is preserved in practice even after relaxations introduced by the algorithm. There remains separation despite relaxations introduced by the algorithm. Then, they demonstrate that the amortized approach results in simlarly good accounting while offering much smaller aggregate runtime.

Critical strengths

Relevant problem

The considered problem is well-motivated and pratically relevant. Composability is a key property of differential privacy. One may also want to compose with mechanisms that have known privacy guarantees but unknown internals. (Renyi) privacy profiles evaluated at a finite set of points are a natural and standard way of communicating privacy guarantees. Due to the real-world relevance of the introduced problem, this work may motivate various follow-up works and could be important for practitioners, i.e., potential impact appears high.

Well-founded approach

The proposed optimization problem follows very naturally from the notion of "receipts" introduced in Section 3. Using moment bounds to track tail mass for otherwise finitely supported privacy loss distributions is an established technique in numerical privacy accounting, i.e., Section 5.2 seems appropriate. Section 5.3 is a nice add-on that simultaneously contributes towards real-world usefulness. So, overall, soundness appears good, although I did not check every proof in detail.

Critical weaknesses

Weak evaluation

Comparing against the naive baseline (Section 6.1) is arguably the more important of the two experiments. However, the authors simply repeat their order-2 randomized response toy example from the methods section. I would at least expect significantly higher orders (dozens or hundreds, which are usually necessary for small ϵ\epsilon). I would also expect different combinations of historical mechanism M1M_1 and M2M_2 (since this is an ML venue, subsampled Gaussian mechanisms might be the most relevant choice, but others would be fine to). As is, there is no empirical evidence that the algorithm's accounting is tight enough to prove separation for non-trivial historical privacy profiles.

Problem may have already been solved for ADP

The work is motivated by the fact that finitely sampled RDP profiles (αj,ρj)(\alpha_j, \rho_j) "provide a compact interface between accountants". However, the same could be said for finitely sampled ADP profiles (ϵj,δj)(\epsilon_j, \delta_j).

While not explicitly framed as "privacy admission" it appears to me like the latter problem has already been solved. Concretely, the "connecting the dots" method of Doroshenko et al. (2022) [1] establishes how to optimally recover a dominating privacy loss random variable L(Y)L(Y) from a finite set of (ϵj,δj)(\epsilon_j, \delta_j) pairs. Thus, it could be used to compute L(X)+L(Y)L(X)+L(Y) as in this work to determine "privacy admission". Furthermore, their method does not require any relaxations and does not require solving of an optimization problem.

This issue puts into question the novelty of the work and the motivation for using RDP profiles as the "interface between accountants".

Questions for authors

Questions

  • Could you please show results similar to Section 6.2 for larger α\alpha and other mechanisms? (Preferably subsampled Gaussian mechanisms, but others would be fine too.)
  • You already use larger α\alpha in Section 6.2, but only show results for your two methods, not for the baseline. Please repeat the same experiments as in Table 2 but show results for the baseline.
  • Is connecting-the-dots the "correct" solution for privacy admission from historical ADP profiles?
  • If yes: What is the motivation for looking at RDP instead? For example, is it more informative at the same number of profile samples?

Other things that influenced my score

  • While I appreciate the formal, technical language used throughout most of the methods section, I believe that it does limit potential impact of the work. The problem you study is fairly intuitive and may be encountered by people who use DP accounting as part of their work/research but do not do core DP research. However, the problem is introduced in Section 3 appears impossible to understand if you are not already intimately familiar with privacy accounting literature. I would strongly encourage you to use some of the extra content page to provide additional background, relate the introduced notation back to standard definitions of approximate differential privacy, renyi differential privacy, dominating pairs, and privacy loss random variables, and explain the intuition behind these definitions. This way, people who use DP as a tool would better understand when to use your method as part of their toolset.
  • Code is provided with the supplementary material (good).

Other comments (no need to respond, do not influence my score)

  • The L(Z)\mathcal{L}(Z) notation for privacy loss random variables suddenly appears in l. 140, but is not previously introduced. Please add an explanation of L\mathcal{L} for future readers.
  • ll. 92-133 recall formalism and composition results introduced by prior work. Please cite this prior work. It might also make sense to clearly divide into separate "background" and "problem statement" sections.

My references

[1] Doroshenko et al. Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions. PETS 2022.

4 comments

Thank you for your thoughtful review. We appreciate your detailed questions.

We have uploaded a revised version, with red margin notes naming the review point each change addresses.

W1 (weak evaluation), Q1 (larger orders)

Separation holds on a realistic DP-SGD history. It is T=1000 steps of the Poisson-subsampled Gaussian mechanism with q=0.01 and σ=1, recorded on the default list of 151 orders of Opacus's RDP accountant. The receipt takes the 61 integer orders, with one bound for both directions; Opacus reports ε=2.10 at δ=1e-5 for this run. The aggregate accountant receives the multiplied moment bounds at all 61 orders. The direct accountant uses only orders 2–8 with order 9 as its tail, which can only loosen its bound. For a Gaussian request with μ=1/2, we report our certified upper value, a lower bound on every Connect-the-Dots result from the same record (see W2), and a feasible aggregate value:

ε = ln γDirect upperCtD lowerAggregate lower
1.102.334e-23.202e-24.832e-2
1.951.002e-31.754e-32.677e-3
3.003.769e-69.480e-61.221e-5

For any cap between our upper bound and a route's lower bound, our accountant admits the request, while that route cannot certify admission even with exact optimization. A second run (q=0.004, σ=1.1, T=3000, Opacus ε=1.14) gives 8.99e-3 versus lower values 1.12e-2 and 2.24e-2 at ln γ=1.10, and 9.89e-5 versus 1.58e-4 and 3.52e-4 at ln γ=1.95. For RR with a=3, the aggregate gap is 0.159 versus 0.188 at ln γ=1.10 and 0.0120 versus 0.0134 at 1.95, with none at 3.00; there the CtD lower value is within 0.02% of our bound at 1.10 and 1.95, since RR reads the history profile at two thresholds.

At core orders 2–32 on the synthetic history, separation is certified for three of four request–threshold pairs, e.g. 0.2216 versus 0.2903 (Gaussian, γ=1). The revision reports the DP-SGD study in Section 7.3 (Table 3; all cases in Appendix E) and the 2–32 comparison in Section 7.2 and Appendix B.9.

Q2 (baseline results)

We ran the baseline on all 30 Table 2 combinations with identical core and tail information, with witnesses verified in exact rational arithmetic. In 16 of the 30, including all 14 at γ=1, the certified direct bound lies below a feasible aggregate value; the largest gap is 0.319 versus 0.423 (orders 2–8, Gaussian μ=3/4, γ=1). At γ=5 the direct bound includes the 0.0102 tail margin of the clipping interval [1/2,2], which exceeds most aggregate values there. In the revision, Table 2 has an aggregate column, Section 7.2 states these gaps, and Appendix B.8 lists all 30 brackets.

W2 (already solved for ADP), Q3 (Connect the Dots), Q4 (why RDP)

Our accountant optimizes the composed objective jointly over single compatible histories and the given request. For a record of sampled hockey-stick values, Connect the Dots gives the discrete privacy-loss law to compose with the known request (Doroshenko et al., Section 4). An RDP record can enter that route through its ADP envelope, the largest hockey-stick value any compatible history attains at each threshold. The envelope combines different histories at different thresholds, so the direct value never exceeds the envelope route; Tables 16 and 17 (Appendix B.6) show strictly smaller bounds for every Gaussian request at γ=1, e.g. 0.2333 versus 0.2428. The middle column above lower-bounds Connect the Dots built from exact envelope values with any choice of dots, and our bound lies below it at every listed threshold. The reusable profile of Section 6.3 follows the envelope route with certified dots at 65 thresholds, for many candidates per receipt.

The motivation for RDP is the interface in use: accountants such as Opacus's compose RDP on a fixed list of orders and pass on that vector. Equal-size RDP and ADP records are informationally incomparable; for an ADP record Connect the Dots remains the natural tool. The revised Introduction and Section 6.3 state this relation; Section 7.3 compares the two routes.

Presentation (other things that influenced my score), Comments

The notation of the problem statement maps onto the standard definitions. The target is P(A)≤eεQ(A)+δP(A)\le e^\varepsilon Q(A)+\delta for every event and ordered neighboring pair, and an RDP bound at order α\alpha bounds the moment EQ[(dP/dQ)α]\mathbb E_Q[(dP/dQ)^\alpha] stored in the receipt. The privacy-loss variable is log⁡(dP/dQ)\log(dP/dQ), and L(X)\mathcal L(X) is the law of XX. A dominating pair is a binary experiment whose profile bounds those of all neighboring pairs. Following your suggestion, a separate Background section (Section 3) recalls them with sources, together with Gaussian DP and composition, and the admission problem follows in its own Section 4.

We hope these responses address your concerns, and we would be grateful if you would consider raising your score.

Thank you for your rebuttal.

My concerns around the experimental evaluation have been resolved, the new results are convincing.
The issues with the presentation have also been addressed.
I also had a look at the other reviewer's comments. Many of them can be attributed to the original exposition, which abstracted away the underlying mathematical concepts from standard DP terminology. I don't see anything in the other reviews as a major issue.


I have one remaining concern, which I would kindly ask you to resolve in a future revision:

In your rebuttal, you clearly discuss ADP vs RDP on two different levels:

  1. Interface level: Either ADP or RDP profiles
  2. Algorithm level:
  • 2a. If using RDP profiles: Either use naive RDP composition, alternative route through connecting the dots (l. 383-388), or the proposed method
  • 2b. If using ADP: Just use connect the dots

However, in the updated manuscript, you only discuss 2a. I.e., we already take for granted that we are only interested in RDP profiles. And under this assumption, we show the proposed method to be better than connect-the-dots.

Please add the following statement from your rebuttal, or an expanded version of it, somewhere in the manuscript: "Equal-size RDP and ADP records are informationally incomparable; for an ADP record Connect the Dots remains the natural tool."


Either way: Most concerns addressed. Good paper. I increased my score accordingly.

Thank you for the positive follow-up and for raising your score.

We added the statement to the Introduction, in the paragraph that introduces Connect the Dots (page 2, lines 64–66):

"Equal-size RDP and approximate-DP records are informationally incomparable; for an approximate-DP record Connect the Dots remains the natural tool."

The same paragraph then describes how an RDP record enters the Connect-the-Dots route through its envelope. Sections 6.3 and 7.3 compare the two routes for an RDP record. The addition carries a red margin note in the uploaded revision. We will keep the manuscript up to date as the discussion continues.

Thank you. @AC: All my concerns have been addressed.

Reviewer_CPN5OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies privacy admission when historical releases are described only by finitely many Rényi differential privacy bounds, while a proposed request has a known privacy profile. The authors optimize the composed privacy guarantee over all histories compatible with the available bounds, preserving the proposed request as a fixed factor. They prove that this can enable admissions that cannot be justified from aggregated RDP moments alone, and develop computational certificates with explicit allowances for tail and numerical errors.

Critical strengths
  1. The paper addresses a meaningful problem. Incomplete historical accounting records are a relevant obstacle to subsequent privacy accounting. The strict separation results demonstrate that preserving the request’s profile can improve admission even when optimization over the aggregated moment constraints is exact.
  2. The paper’s overall approach appears sound and well motivated. By retaining the new request’s privacy profile, the method makes effective use of the information available beyond the incomplete historical RDP records. Formulating admission as a worst-case analysis over all compatible histories provides a logically consistent basis for assessing the total privacy budget.
Critical weaknesses

I do not fully undersantd the whole manuscript, while I have following concerns.

  1. The assumption that new requests are selected independently of previous outputs may be overly restrictive. In practice, users often formulate subsequent queries or adjust their parameters based on earlier results. This assumption therefore imposes an additional requirement on user behavior. Ideally, the mechanism should accommodate such natural interactions without requiring users to avoid adaptive requests. The authors should justify this restriction and clarify whether the common-dominator extension discussed in the appendix can adequately support realistic adaptive workflows.

  2. I suggest that the author more clearly explains how historical information evolves as new queries are admitted and executed. Although the author describes moment updates, I suggest that the author specify what information is retained after each release, particularly whether the executed request’s full privacy profile is compressed into historical RDP bounds. They should also clarify when the reusable historical profile requires revalidation or reconstruction, and how repeated updates affect the tightness of the privacy guarantees and the cumulative computational cost.

  3. The evaluation lacks a dedicated assessment of the cost of maintaining the historical privacy profile after successive releases. The reported timings cover initial construction and candidate queries sharing an unchanged historical record, leaving the cost of subsequent revalidation or reconstruction unclear. I suggest that the author evaluates a sequence of admitted and executed queries, reporting how frequently the profile requires reconstruction, the associated computational overhead, and the cumulative runtime. This would help determine whether the observed efficiency and admission benefits persist as the historical record evolves.

Questions for authors

see Weaknesses

4 comments

Thank you for your careful review. We appreciate your constructive comments.

We have uploaded a revised version, with red margin notes naming the review point each change addresses.

W1

The accountant covers adaptive requests obtained by postprocessing a fixed dominating request. We assume independence because a request fixed before the private transcript and run with fresh randomness makes the joint output exactly the product of history and request, which is what the accountant optimizes over (Proposition 10, Appendix D.1). A request chosen after seeing earlier outputs is still covered when every available choice is a postprocessing of one fixed request F⋆F^\star, that is, Fz=Kz∘F⋆F_z=K_z\circ F^\star with jointly measurable, data-independent kernels KzK_z. The sequential experiment is then dominated by EH⊗F⋆E_H\otimes F^\star, so admitting F⋆F^\star is safe whichever request is chosen.

A covered workflow is a fixed Gaussian baseline for which the transcript selects additional independent noise or other postprocessing; the accountant checks the baseline, which dominates these choices. The revision states this condition in Section 4, next to the product model.

W2

An executed request is compressed into the historical RDP bounds. The receipt holds the saved orders, the positive- and negative-exponent moment bounds at those orders, and the tail bounds. Testing a candidate leaves it unchanged. When an admitted independent request is executed, every stored bound is multiplied by the corresponding request moment, and the request's full profile is used only while it is pending (Section 6.3). A cached historical profile is certified for one receipt, so after an executed release it has to be revalidated or rebuilt. Between executions, one prepared profile serves all candidates sharing the receipt. Section 6.3 of the revision follows the receipt through one admission and one execution, so the state before and after each release is explicit.

W3

We ran a sequence of four admitted and executed releases on the Table 2 history and measured the maintenance cost. The sequence follows the receipt through repeated releases: the profile is built once and rebuilt after each of the first three executed releases.

The history has core orders 2–8, with core and tail bounds enlarged for both neighboring directions. Four predeclared RR requests with a=21/20a=21/20 are checked at (γB,δB)=(5,1/20)(\gamma_B,\delta_B)=(5,1/20). All four requests are admitted, with certified upper bounds 0.0135, 0.0159, 0.0188 and 0.0221. Median cumulative accounting times are 4.45, 11.52, 22.96 and 40.17 seconds; the final total ranges from 40.16 to 40.42 seconds over three measured sequences after one warmup. Times include construction, independent verification, candidate evaluation and moment updates, and exclude private execution and file I/O.

For one candidate per release, direct evaluation is the faster route: it gives identical bounds in all 12 checks, in a median of 0.0077 seconds for four checks, excluding shared moment updates. A prepared profile serves workloads that test many candidates against one unchanged receipt, which share its construction cost. In this sequence each bound is the tail term 2δℓ,u2\delta_{\ell,u}; Appendix B.4 compares admissions after a shared Gaussian update. The revision reports this sequence in Section 7.4, with the full timing table in Appendix B.7 (Table 21).

We hope these responses address your concerns, and we would be grateful if you would consider raising your score.

Thank you for the feedback. I share Reviewer wvY7’s concerns. The manuscript looks LLM-generated in general. I agree that the underlying idea can be interesting. With further refinement, particularly to improve the clarity of the presentation, I believe this work could be published in a well-regarded venue. I would have given the manuscript a Borderline rating if that option had been available. Given the available choices, I selected Weak Reject.

Thank you for your continued engagement and for your kind words about the idea. We take your comments on clarity seriously.

We are revising the presentation of the main text and will upload the new version before the discussion deadline. We would be grateful if you could look at it again.

Thank you for your continued engagement and for the time you have devoted to reviewing our work, and for your assessment of the idea. We have uploaded a further revision focused on clarity, with the rewritten passages shown in blue.

The main change is that the results are now introduced through one running example: a randomized-response request at a fixed threshold, worked through in the Introduction, before Theorem 2 and before Theorem 3, so that each statement can be checked against concrete numbers. The problem statement in Section 4 also uses fewer symbols and defines the compared quantities in words, and Figure 1 shows the main experimental comparisons that were previously given as tables.

We would be grateful if you could take another look. The discussion period is still open, and we would welcome any further comments or questions, which we will be happy to address in the remaining time.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.