{"id":"451a3a00-be0f-44b3-9360-046eadf6840b","arxiv_id":"1909.01502","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Sage enforces a global differential privacy guarantee over a growing data stream using block-level composition, and adds privacy-adaptive training with SLAed validation to maintain model quality.","lead":"Sage is a privacy system that lets companies keep training machine learning models on a sensitive data stream without ever running out of a fixed privacy budget. It splits data into blocks, accounts for leakage block by block, and retrains models adaptively until they pass a private quality check.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Privacy-adaptive training's adaptive stopping invalidates the per-test (1−η) quality guarantee; Proposition 3.1 does not cover multiple retries, so the 'with high probability' quality claim has no proof.","rationale":"The reader's weakest_assumption (developer-supplied pipelines must be truly DP) is real but explicitly scoped in §3 and Appendix A.1; I do not treat a stated trust boundary as the decisive flaw. The budget-doubling resource claim in §3.3 is also false when retries double data rather than ε, but that is an efficiency bound, not a correctness claim about the DP guarantee. The optional-stopping gap is the sharpest: it targets a formal proposition (Prop. 3.1) that is used to support a headline 'with high probability' quality claim, and it is not repaired anywhere in the paper. The block-composition theorem itself (Thm. 4.3 with Appendix A.2 proof) appears mathematically sound for the protocol as written, so the overall verdict remains CONDITIONAL: the DP accounting contribution stands, but the quality-control claim needs a multiplicity correction or a re-stated guarantee.","tokens_in":28183,"tokens_out":20704,"duration_ms":225527,"concrete_test":"Simulate the §3.3 loop: choose a synthetic distribution where the best achievable expected loss is just above the target τ, set η=0.05, and run the full privacy-adaptive procedure (with its doubling rule) 1,000 times. Record the fraction of runs that ACCEPT a model whose true loss exceeds τ, and the distribution of the number of validation attempts K. If the violation rate exceeds η (or exceeds η times the mean number of attempts), the optional-stopping gap is confirmed. A fix would be to replace η in each ACCEPT/RETRY decision by η/K_max or to perform a single final, pre-registered evaluation after the search stops.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 3.1 (Appendix B.1) certifies a single ACCEPT test: for a fixed f^dp, the test returns true only if L_D(f^dp)≤τ with probability at least 1−η. But §3.3's privacy-adaptive training wraps this test in a loop that retrains on more data and/or larger ε after every RETRY, stopping at the first ACCEPT. The final accepted model is therefore selected by optional stopping: the very test that certifies it is the one that caused the loop to terminate. The per-attempt error probability η does not bound the probability that some attempt in the sequence falsely accepts a model whose true loss exceeds τ; a union bound over the random number of attempts K gives roughly Kη. Proposition 3.1 is thus not a valid certificate for the procedure as described, and the abstract's 'with high probability' quality criterion is unproven. The evaluation (§5.2) reports violation rates for the full adaptive procedure but not the retry-count distribution or a multiplicity correction, so it does not close this gap. This concern is orthogonal to the block-composition DP theorem, which appears sound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents Sage, a differentially private machine-learning platform that enforces a global (εg,δg)-DP guarantee over all models released from a sensitive data stream. Its first contribution is block composition, which partitions the stream into blocks and charges each query's privacy loss only to the blocks it actually uses; blocks are retired when they reach a configured ceiling, while fresh blocks arrive with zero accumulated loss, allowing the workload to continue indefinitely if new data arrives fast enough. The second contribution is privacy-adaptive training, which repeatedly retrains a DP pipeline with more data and/or a larger privacy budget and validates via a DP 'SLAed' validator (ACCEPT/REJECT/RETRY) until a quality target is accepted. The paper proves block-composition theorems (Theorems 4.2 and 4.3), gives statistical and DP guarantees for the individual validators, and evaluates the system on NYC taxi and Criteo workloads.","tokens_in":28359,"tokens_out":18547,"duration_ms":183830,"significance":"The block-composition results are a genuine and, on my reading, technically sound contribution: Theorem 4.2 correctly reduces the privacy loss of queries on overlapping blocks to the maximum per-block loss, and Theorem 4.3 extends this to adaptively chosen blocks and privacy parameters on a stream, with the proof in Appendix A.2 correctly handling future blocks that depend on previous outputs through conditioning on the released values. The system design is thoughtful, and the evaluation is substantial (Q1–Q4, Tables 1–2, Figures 5–8). If the quality-control guarantee were fully established, this would be a strong systems paper on DP for ML workloads. However, the central 'with high probability' quality claim for privacy-adaptive training is currently unproven because of optional stopping, so the paper's second advertised contribution needs additional theoretical work.","major_comments":[{"comment":"The paper's claim that privacy-adaptive training produces a model meeting the quality target with high probability is not supported by the stated propositions. Proposition 3.1 (restated as Proposition B.1) bounds the error of a single ACCEPT test for a fixed model: with probability at least 1−η, the test returns true only if L_D(f^dp)≤τ. The procedure in §3.3, however, runs this test repeatedly on newly trained models and stops at the first ACCEPT. The final index K is a stopping time that depends on the entire sequence of validation outcomes, so the event {ACCEPT_K and L_D(f_K)>τ} is contained in the union over t of {ACCEPT_t and L_D(f_t)>τ}; the per-attempt bound of η does not control this union (it is roughly E[K]η even under independence). The abstract's 'with high probability' quality criterion therefore has no proof. The empirical violation rates in Table 2, Section 5.2, are reassuring but do not close the gap because they do not report the retry-count distribution or apply a multiplicity correction. I recommend either proving a guarantee for the adaptive procedure (for example, by composing the tests with a union bound over a bounded number of attempts or by a sequential-testing argument) or revising the claims to state the guarantee per attempt only.","section":"§3.3, Proposition 3.1 and §B.1"},{"comment":"The resource-conservation argument ('the sum of budgets used by all failed iterations is at most equal to the budget used by the final, accepted iteration' and 'at most four times') is stated informally and is not a theorem. If the dataset window is also doubled on RETRY, old blocks are reused with increasing ε, and the cumulative per-block privacy loss across failed attempts plus the final attempt is what actually counts against the block ceiling; the claimed factor of four should be stated as a heuristic or proved with explicit accounting of both the ε doubling and the sample-size doubling. This does not affect the DP guarantee itself, but it is used to justify the Block/Conserve strategy in §5.4, so the claim should not be presented as a formal resource bound.","section":"§3.3, Privacy-Adaptive Training paragraph"}],"minor_comments":[{"comment":"The condition in Theorem 4.3 is stated as a property of AccessControl for every block k; the proof would be easier to follow if it explicitly noted that for a fixed neighboring pair the changed block k is fixed and the other blocks contribute zero privacy loss, so the per-block guarantee suffices without a further union bound over blocks.","section":"4.3 / Algorithm 4c"},{"comment":"Because the adaptive-stopping issue is open, the paper should report the distribution of the number of retries per accepted model (and ideally the maximum), so readers can assess the empirical multiplicity.","section":"5.2, Table 2"},{"comment":"The discussion of symmetric difference notes that changing one record corresponds to a symmetric difference of size 2 and is supported only via group privacy; this should be stated in the main text when event-level privacy is defined, since many readers expect modification to be a neighboring relation.","section":"Appendix A.1"},{"comment":"References [35] and [36] are duplicates; Appendix B.1 contains a typo ('more accuratly'); Section 3.3's resource-conservation paragraph should define precisely what 'budget used by an iteration' means.","section":"References and typos"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a solid systems paper: the block-composition part is sound and the evaluation is extensive. The main weakness is the unproven quality guarantee for the adaptive training loop, which should be fixed before publication. I would not reject on the basis of the block-composition theory, but the 'with high probability' claim in the abstract needs to be either proven or explicitly qualified. The duplicate references and minor typos are easily corrected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the block-composition result is the real contribution and it holds up: Theorem 4.3 correctly reduces privacy loss on the stream to per-block budget sums, and the proof in Appendix A.2 is a clean application of Theorem 4.2 plus [45]'s adaptive composition. That gives DP-ML systems a way to keep training on a growing stream without halting when one model exhausts budget, and the evaluation demonstrates the operational advantage over query- and streaming-level accounting. Second, the quality-control half is not proven as stated. The SLAed validator's Proposition 3.1 certifies a single ACCEPT test, but privacy-adaptive training wraps that test in a retry loop and stops at the first ACCEPT. The final model is selected by optional stopping; per-attempt error η does not bound the probability that some accepted model in the sequence is bad. A union bound gives roughly Kη, where K is the random number of attempts. The paper's abstract claim—that models are released only if they meet quality targets with high probability—has no proof for the adaptive procedure. Tab. 2 violation rates for the full procedure look encouraging, but the paper does not report the retry count distribution or apply a multiplicity correction, so that evidence does not close the gap.\n\nCredit where due: the repeated training/validation stages are carefully thought out, the DP versions of the validators are real mechanisms with proofs of their own (Appendix B), and the REJECT sensitivity argument is loose but valid. Block composition is clearly new relative to PINQ, Rogers et al., and Cummings et al.; the related-work discussion is accurate. No code is released, and the workload simulation in §5.4 omits some parameters and error bars, but those are standard systems-paper weaknesses, not fatal.\n\nWho is this for? People building or studying DP ML platforms and DP composition theory. The block-composition framework deserves to be in the literature; the privacy-adaptive training should be revised so the quality guarantee covers the whole procedure—either by bounding the expected number of retries and applying a union bound, or by reporting family-wise-error-controlled evaluations.\n\nMy verdict: send it to review, but the reviewers should insist the quality claim be either proved for the adaptive loop, or restated as a per-attempt guarantee. The DP accounting result itself is sound.","headline":"Block composition is a sound and useful contribution to DP systems; the 'with high probability' quality guarantee for privacy-adaptive training is unproven due to optional stopping.","tokens_in":28915,"tokens_out":2967,"would_cite":true,"duration_ms":27705,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P27","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Block composition lets a machine-learning platform enforce global differential privacy over an endless data stream without exhausting the privacy budget.","keywords":["differential privacy","block composition","growing databases","privacy budget","machine learning platform","privacy-adaptive training","SLAed validation","data stream"],"falsifier":"Take a Sage-deployed pipeline whose preprocessing computes a global min-max or z-score scaler on the raw training data and uses the fitted parameters to transform features before a DP layer. If an auditor measures membership-inference accuracy on the released model and finds it clearly above what $(\\epsilon_g,\\delta_g)$-DP permits, the block accounting has not captured that data-dependent preprocessing step, and the paper's global-guarantee claim fails in that configuration.","tokens_in":27961,"feed_emoji":"🛡️","tokens_out":5379,"duration_ms":50258,"temperature":0.7,"pith_summary":"This paper presents Sage, a machine-learning platform that promises a global differential-privacy (DP) guarantee over every model and feature ever released from a sensitive data stream. Its central proposal, block composition, splits the stream into blocks, such as one day of data per block, and charges the privacy loss of each query only to the blocks that query actually uses. When a block's loss reaches the configured ceiling, Sage retires that block; new blocks arrive with zero accumulated loss, so training can continue indefinitely as long as the stream grows fast enough. For the second half of the problem, privacy-adaptive training repeatedly retrains a model on more data and/or a larger privacy budget until a DP-aware validator accepts it with high probability as meeting the developer's quality target. The result is an accounting method tuned to how real ML workloads interact with data: overlapping, adaptively chosen subsets of a growing database rather than a single static dataset.","feed_headline":"Block composition keeps ML privacy budgets from running out","feed_subtitle":"New data blocks refresh the privacy budget, so model training can continue indefinitely under a global guarantee.","key_machinery":"Block composition is the central object: a privacy-accounting scheme that splits a data stream into disjoint blocks and accounts for each DP query's privacy loss only on the blocks the query touches. The load-bearing mechanism is the per-block access-control check in Theorem 4.3: a query is allowed only if, for every block it uses, the running totals of the query's $\\epsilon_i$ and $\\delta_i$ remain below the global ceilings. This works because future data blocks are assumed to depend on prior outputs only through DP-released models, so an adversarial change to one record affects one block and no other block's query outputs change. The same construction also powers privacy-adaptive training, since block composition explicitly supports adaptivity in the choice of blocks, privacy parameters, and queries. The proof of Theorem 4.2 reduces block-level accounting to ordinary query-level composition on each block, and Theorem 4.3 lifts that result to streams with adaptive budget choices.","core_discovery":"The paper's main claim is that global DP can be enforced over an entire evolving data stream without ever exhausting the stream's privacy budget, provided the database grows in new blocks faster than models consume them. Formally, Theorem 4.3 states that the AdaptiveStreamBlockCompose protocol is $(\\epsilon_g,\\delta_g)$-DP if, for every block, the access control keeps the sum of the $\\epsilon_i$ (and $\\delta_i$) of all queries using that block below the corresponding global ceiling. The proof reduces the privacy loss of the whole interaction to the maximum privacy loss over individual blocks, because a single added or removed record lies in one block, and queries not seeing that block contribute a privacy-loss ratio of one. Sage implements this protocol as an access-control layer: it deducts requested $(\\epsilon,\\delta)$ budgets from the blocks a pipeline asks for, denies access to blocks whose budgets are exhausted, and trusts each pipeline to be DP. It then couples this accounting with privacy-adaptive training, which doubles the privacy budget or training-set size on retries and uses SLAed DP validators to accept, reject, or retry a model with high-probability guarantees. A sympathetic reading: Sage's contribution is not a new DP learning algorithm but a systems layer that makes the existing DP-ML literature usable on the growing-database workloads real companies run.","pith_inferences":["The same per-block accounting could apply to non-ML analytics on growing databases, such as continuously released statistics over rolling time windows, where the ceiling would be per time block instead of per query.","A natural stress test: if the stream's block arrival rate drops below the rate at which pending pipelines consume budget, the endless-operation guarantee collapses to the static-database regime; practitioners should measure that ratio before adopting Sage.","Sage's strongest guarantee is event-level; the paper itself notes that user-level privacy requires new users to arrive faster than models are released, which mature companies may not satisfy. A useful extension would adapt block composition to user-group shards with a replenishment analysis.","The trust boundary suggests an auditing layer: automated checks that no preprocessing step computes data-dependent non-DP quantities would close the main gap between Sage's accounting and a verifiable end-to-end guarantee."],"forward_implications":["A company can keep releasing models from a sensitive stream indefinitely, as long as new data blocks arrive before the current blocks' budgets are spent.","Privacy loss is no longer charged globally against the whole database, so a pipeline that touches only recent data does not consume budget for old blocks.","Combining blocks before a single noisy computation, rather than answering per-block queries and aggregating, preserves model quality and validation power at the same total privacy cost.","With privacy-adaptive training, a model's release can carry a high-probability guarantee that it met the developer's quality target, even though training and validation are both DP.","Budget-conserving retry strategies let multi-pipeline workloads release more models per hour under a fixed global $(\\epsilon,\\delta)$ ceiling."],"supporting_citations":[{"why":"Supplies the adaptive-composition result that lets Theorem 4.3 charge per-block budgets that may depend on prior outputs.","marker":"[45]"},{"why":"Provides the basic composition arithmetic that the per-block budget check uses to sum $\\epsilon$ and $\\delta$.","marker":"[17]"},{"why":"The earlier theoretical treatment of DP for growing databases that Sage extends and makes practical for ML workloads.","marker":"[12]"},{"why":"Defines the continual-observation streaming regime that block composition improves on by allowing reuse of old data.","marker":"[19]"},{"why":"Source of the partition-based parallel composition and symmetric-difference neighboring-dataset convention used in block-level accounting.","marker":"[39]"},{"why":"Shows increasing training-set size can compensate for accuracy loss from DP, motivating privacy-adaptive training's retry strategy.","marker":"[29]"}],"fun_headline_variants":["Block composition kills the privacy budget ceiling","Endless DP training: blocks refresh the budget","Sage's block trick keeps ML private and trainable forever","Global DP without a dead end: block composition"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The global DP guarantee holds only if every training pipeline really is as private as declared: Sage accounts for budgets but does not verify that preprocessing, training, or validation code implements DP, so any data-dependent transformation outside the DP wrappers leaks information that no block budget charge captures.","fun_headline_variants_meta":{"raw":{"variants":["Block composition kills the privacy budget ceiling","Endless DP training: blocks refresh the budget","Sage's block trick keeps ML private and trainable forever","Global DP without a dead end: block composition"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000215,"raw_usage":{"total_tokens":1455,"prompt_tokens":997,"completion_tokens":458,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":613,"completion_tokens_details":{"reasoning_tokens":398}},"tokens_in":613,"tokens_out":458,"duration_ms":5402,"temperature":1.0,"reasoning_tokens":398,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:17:26.116355+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a Sage-deployed pipeline whose preprocessing computes a global min-max or z-score scaler on the raw training data and uses the fitted parameters to transform features before a DP layer. If an auditor measures membership-inference accuracy on the released model and finds it clearly above what $(\\epsilon_g,\\delta_g)$-DP permits, the block accounting has not captured that data-dependent preprocessing step, and the paper's global-guarantee claim fails in that configuration.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the adaptive-composition result that lets Theorem 4.3 charge per-block budgets that may depend on prior outputs."},{"cited_title":"Dwork, F","cited_arxiv_id":null,"evidence_quote":"Provides the basic composition arithmetic that the per-block budget check uses to sum $\\epsilon$ and $\\delta$."},{"cited_title":"Cummings, S","cited_arxiv_id":null,"evidence_quote":"The earlier theoretical treatment of DP for growing databases that Sage extends and makes practical for ML workloads."},{"cited_title":"Dwork, M","cited_arxiv_id":null,"evidence_quote":"Defines the continual-observation streaming regime that block composition improves on by allowing reuse of old data."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Source of the partition-based parallel composition and symmetric-difference neighboring-dataset convention used in block-level accounting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows increasing training-set size can compensate for accuracy loss from DP, motivating privacy-adaptive training's retry strategy."}],"review_version":1}