{"id":"cffa1133-5c50-4ced-95d5-e90d29599053","arxiv_id":"2412.00497","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A distributed model where a public linear sketch is computed securely over client-side noise achieves central-model-like utility for private low-rank approximation and ridge regression, with error independent of the number of clients.","lead":"This paper introduces a middle-ground model for private data analysis: clients send noisily encoded data through a publicly known linear transformation that is computed by several servers using secure multiparty computation. The authors show this model gives error close to the trusted-central-server model for low-rank approximation and ridge regression, without requiring a single trusted server.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The sparse-sketch DP guarantee has a δ-accounting mismatch: Theorem 4.4 requires δ/(sd) per coordinate, but the fallback (Eq. 2) and Corollary 4.7 use δ/d, leaving a regime where the Gaussian mechanism is invoked with negative δ.","rationale":"The paper makes a valuable conceptual contribution: it identifies the LTM as an intermediate trust model and shows that linear sketches plus infinitely divisible noise can give central-model-like error with distributed trust. The utility analysis (Lemmas 5.1–5.3, Theorems 5.4 and 5.8) is largely self-contained, and the experimental section, while informal, supports the asymptotic trend. My concern targets the privacy proof, which is the foundation: Theorem 4.4 explicitly allocates δ/(sd) − m exp(...) per released coordinate, yet the randomizer's fallback and Corollary 4.7 calibrate the threshold and variance using δ/d. For s>1 this creates a parameter regime where the per-coordinate δ is negative; the Gaussian mechanism cannot satisfy a negative-δ guarantee (it would require pure ε-DP), so the (ε,δ) claim is unproven exactly for the sparse sketches used in the main theorems. The fix is mechanical—replace δ/d by δ/(sd) and adjust the threshold—so the paper is conditionally sound rather than fundamentally wrong. This is consistent with the reader's conditional verdict, but the specific mismatch is sharper than the reader's stated 'small-n is vacuous' concern.","tokens_in":33582,"tokens_out":14396,"duration_ms":142721,"concrete_test":"Recompute the privacy analysis for s=2, m=1, d=1, δ=0.1, t′=0, n=19: Eq. 2 permits nonzero messages, but Theorem 4.4's per-coordinate δ′ = 0.1/2 − exp(−(17/8)) ≈ −0.069 < 0; verify that Lemma 3.3 cannot instantiate the required Gaussian noise and that the composition step therefore fails. Then re-derive Theorem 5.4 and Theorem 5.8 with the corrected threshold n ≥ 8m ln(sdm/δ)+s+t′ and the corresponding variance formula; check whether the published additive error changes.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The privacy proof of Theorem 4.4 composes s decomposed sketch matrices S_i and d columns, so the additive noise mechanism for each released coordinate must satisfy (ε/(sd), δ/(sd) − m exp(−(n−s−t′)/(8m)))-DP. For the Gaussian instantiation this requires the per-coordinate δ′ = δ/(sd) − m exp(−(n−s−t′)/(8m)) to be positive; otherwise Lemma 3.3 is undefined and no finite-variance Gaussian can satisfy the resulting negative-δ inequality, because that would imply pure ε′-DP. However, the fallback randomizer (Eq. 2) only enforces δ/d > m exp(−(n−s−t′)/(8m)) by setting the zero-output threshold at n ≥ 8m ln(dm/δ)+t′, and the proof of Theorem 4.4 repeats the same δ/d condition. For any s>1, there exists an interval n ∈ [8m ln(dm/δ)+t′, 8m ln(sdm/δ)+s+t′) where clients send nonzero randomized messages although the per-coordinate δ′ is negative. Corollary 4.7's variance formula also uses ln(1.25s/(δ/d − m exp(...))), which does not match ε′ = ε/(sd) and δ′ = δ/(sd) − m exp(...). Since the sparse construction uses s = Õ(log(k/α_S)) > 1 in the main utility theorems (5.4 and 5.8), this gap affects the central claim of (ε,δ)-DP with n-independent error. The fix is to replace δ/d by δ/(sd) in Eq. 2 and Corollary 4.7 and adjust the threshold accordingly; after that, the proof appears to go through.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the linear-transformation model (LTM) of distributed differential privacy: n clients add locally sampled noise to their inputs, a trusted platform applies a public linear transformation (e.g., a sparse Johnson-Lindenstrauss/OSNAP sketch) to the noisy inputs, and the sketch output is analyzed publicly. Because the noise distributions are infinitely divisible, the sum of per-client noises equals the central-mechanism noise, yielding (ε,δ)-DP with error independent of n when the sketch is computed via linear secret sharing (tolerating t corrupt servers and t′ corrupt clients). The paper proves privacy theorems for sparse and dense sketching (Theorems 4.4, 4.8 with Gaussian/Laplace instantiations in Corollaries 4.7, 4.10), then shows utility bounds with error independent of n for low-rank approximation (Theorems 5.4, 5.7) and ridge regression (Theorem 5.8, under λ ≥ poly(ε^{-1}, d, log 1/δ)). It includes an MP-SPDZ implementation with scaling experiments and a utility study interpolating between local and central behavior on synthetic and real-world data.","tokens_in":34018,"tokens_out":33973,"duration_ms":312242,"significance":"The paper proposes a genuinely new intermediate trust model (the linear-transformation model), in which a public linear map computed by LSS-based MPC plays the role that the shuffler plays in the shuffle model. The core technical idea — splitting the central additive noise across clients via infinite divisibility and relying on the JL/OSNAP sketch to aggregate it — is elegant and well executed at the conceptual level: the main theorems give n-independent error for low-rank approximation and ridge regression, a property that provably distinguishes the model from the local model (where √n lower bounds apply). The paper is also commendable for shipping an MP-SPDZ implementation with runtime/communication measurements, for stating robustness against corrupt clients explicitly (Definition 4.2), and for keeping the theory parameter-free: no parameter is fitted to data to obtain the theorems, and the experimental noise-scaling exponent p is explicitly presented as an interpolation knob rather than a calibration. If the privacy accounting is corrected, the results would be a solid contribution to the distributed-DP literature.","major_comments":[{"comment":"Theorem 4.4 allocates to each released coordinate the budget (ε/(sd), δ/(sd) − m exp(−(n−s−t′)/(8m))) and composes over s sketches and d columns. The Gaussian instantiation in Corollary 4.7 is therefore only well-defined when δ′ := δ/(sd) − m exp(−(n−s−t′)/(8m)) > 0; for δ′ ≤ 0, Lemma 3.3 cannot be invoked and no finite-variance Gaussian mechanism can satisfy the resulting inequality (it would imply pure (ε′,0)-DP). However, the fallback randomizer in Eq. (2) is activated by the condition n < 8m ln(dm/δ) + t′, which only guarantees δ/d > m exp(−(n−t′)/(8m)), and the proof of Theorem 4.4 repeats the same δ/d condition. Consequently, for every s > 1 there is a non-empty interval of n (roughly [8m ln(dm/δ)+t′, 8m ln(sdm/δ)+s+t′)) in which clients send non-zero randomized messages while the per-coordinate δ′ is negative, so the claimed (ε,δ)-DP guarantee is not established. Corollary 4.7's variance formula inherits the same mismatch: its log argument is 1.25s/(δ/d − m exp(−(n−s−t′)/(8m))), whereas Lemma 3.3 with ε′ = ε/(sd) and δ′ = δ/(sd) − m exp(...) requires ln(1.25/(δ/(sd) − m exp(...))). The fix is local: use δ/(sd) in Eq. (2), in the fallback case of Theorem 4.4's proof, and in Corollary 4.7, with threshold n ≥ 8m ln(sdm/δ)+s+t′. I further ask the authors to re-derive the variance constant: with the stated sensitivity Δ₂ = 2η√s and ε′ = ε/(sd), Lemma 3.3 requires per-entry noise variance 8η²s³d² ln(1.25/δ′)/ε², whereas the variance delivered by Corollary 4.7 after summing the honest clients' noises is (n−s−t′)σ²/(2m) = 2s³η²d² ln(...)/ε², a factor of 4 too small; with the corrected sensitivity 2η the delivered variance is still only s/4 of the requirement.","section":"§4.2, Theorem 4.4, Eq. (2), Corollary 4.7"},{"comment":"The proof of Lemma 4.6 (and hence Theorem 4.4) conditions on the event E that every row of the sketch receives at least (n−t′)/(2m) honest clients' noises and charges the failure probability m exp(−(n−t′)/(8m)) to δ. This accounting is valid only if the set of corrupt clients is independent of the sketch matrix S. In the proposed protocol S is a public matrix — Section 4.3 explicitly tolerates corruption of all but one server, and the servers know S — while Definition 4.2 quantifies the guarantee over all coalitions C_cor, i.e., a worst-case coalition may be chosen with full knowledge of S. For m ≥ 2 and t′ = ⌈n/m⌉ (a parameter range allowed by Theorems 5.4 and 5.7, which assume t′ < n/2), an adversary can corrupt exactly the clients in the support of one output row, making that row's honest-noise contribution zero; the output coordinate is then a deterministic function of corrupted clients' data and no (ε,δ)-DP guarantee can hold. The failure probability of E is then 1 conditional on S, not m exp(−(n−t′)/(8m)). Please state explicitly that the corruption set is fixed before S is sampled and that S is kept from the adversary until all client messages are delivered (which is compatible with the LSS protocol, since clients only need the public transform after sending shares), or otherwise restrict the adversary; as written, Theorem 4.4 does not deliver the guarantee claimed in Definition 4.2.","section":"§4, Definitions 4.1–4.2, Lemma 4.6"},{"comment":"The utility theorems are stated unconditionally, but the mechanism in Eq. (2) outputs the zero vector whenever n is below the fallback threshold, and the utility proofs do not cover that regime. In Theorem 5.4, if the randomizer outputs 0^{ds}, the sketch is zero and the output projection X′ is arbitrary, so ∥A − AX′X′^T∥_F can be Θ(∥A∥_F); the multiplicative-error claim (1+O(α_S)) is vacuous there. Theorem 5.8 does discuss the fallback, but the asserted bound '∥b∥² ≤ η′n ≤ η′m ln(dm/δ)+t′' is not correct as written (the second inequality drops a factor 8 and ignores the additive t′ in the chain), and the fallback error ∥b∥² can still be much larger than the optimal objective, so the multiplicative (1+o(1)) form also requires the noisy regime. The theorems should state the regime n ≥ 8m ln(sdm/δ)+s+t′ (with the s-dependent threshold correcting Eq. (2)) under which they apply; since m (and hence the threshold) is a constant depending only on the privacy/accuracy parameters, adding this qualification does not weaken the 'independent of n' claim, but it is currently missing.","section":"§5, Theorems 5.4, 5.7, 5.8"}],"minor_comments":[{"comment":"In the proof of Corollary 4.7, the additive noise is described as 'n ∼ Lap(0, 2ηm²d/ε)^m' even though the corollary instantiates the Gaussian mechanism; the Laplace scale appears to be copied from Corollary 4.10. This should read Gaussian noise with the variance derived from Lemma 3.3.","section":"Corollary 4.7 (proof)"},{"comment":"Theorem 5.4 states 'Let S ∼ D_sketch(m,n)' without the sparsity parameter s, although the sparse mechanism and Corollary 4.7 are parameterized by s; the proof also cites 'Theorem 4.7' where Corollary 4.7 is meant, and the same citation issue occurs in Theorem 5.8.","section":"Theorems 5.4 and 5.8 (statements/proofs)"},{"comment":"The proof states that each entry of G_i is X_j − Y_j with X_j, Y_i ∼ Γ(1/(n−t), b); this is inconsistent with Corollary 4.10's parameterization Γ(1/(n/m−t′), b) and uses t in place of t′.","section":"Theorem 5.7 (proof)"},{"comment":"The rows of Table 1 appear misaligned: for instance, the Ω(√n) lower bound for local frequency estimation is typeset in the Central column, and the frequency-estimation row contains more entries than there are columns.","section":"Table 1"},{"comment":"References [64] and [65] both cite the same paper (N. M. Stausholm, PODS 2021) and should be merged.","section":"References"},{"comment":"The statement of Lemma 5.3 is grammatically broken ('with probability at least 1−β for some absolute constant η and ∥L∥²_F ≤ ...'); the quantifier over η and the claimed matrix norm inequality should be stated as separate sentences.","section":"Lemma 5.3"},{"comment":"Theorem 4.4's statement contains a mismatched parenthesis in the DP budget ('δ/(sd) − m exp(−(n−s−t′)/8m)))') and Lemma 4.6 has the same typo; worth a pass over the whole section.","section":"Theorem 4.4 statement"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern about the δ/d vs δ/(sd) mismatch is confirmed by reading Section 4.2: it is a genuine inconsistency in Theorem 4.4/Corollary 4.7 that affects the main results, though the fix appears mechanical (use δ/(sd) in Eq. (2), the fallback case, and Corollary 4.7, with the s-dependent threshold). I would also urge the editor to have the authors address the corruption-independence issue in Lemma 4.6 before publication; it is a modeling gap rather than a typo. If the authors resolve both and add the missing n-regime qualifications to Theorems 5.4/5.8, the paper would be acceptable; otherwise the central (ε,δ)-DP claim is not established as stated. The experimental section is honest and well-scoped, but it does not substitute for the theoretical fixes. On fit: the paper suits a security/cryptography venue or a theory venue; the cs.CR arXiv category is consistent."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. The linear-transformation model is a genuine contribution: a trust model between central and local DP, efficiently instantiable with linear secret sharing, that yields n-independent error bounds for low-rank approximation and ridge regression. That is new; prior JL-DP work reduced dimension d, not the dependence on n, and no local or shuffle construction achieves comparable bounds. The second thing is that the sparse-sketch privacy proof has a δ-accounting error, exactly as the stress-test says. Theorem 4.4 per-coordinate budget is δ/(sd) − m exp(−(n−s−t′)/(8m)), but the fallback in Eq. 2 and Corollary 4.7 use δ/d. For any s > 1 there is an interval of n where the fallback does not trigger and this per-coordinate δ′ is negative, so the Gaussian mechanism is invoked with nonpositive δ′. That cannot satisfy (ε′, δ′)-DP. The fix is straightforward: use δ/(sd) in Eq. 2 and Corollary 4.7, and adjust the threshold to n ≥ 8m ln(sdm/δ)+t′. After that, the proof appears to go through.\n\nWhat the paper does well: the model definition is careful about corrupt clients, which the standard shuffle-model definition is not; the noise-splitting via infinite divisibility is elegant; the utility theorems are non-trivial; the related-work comparison is honest. The experiments, while informal, support the asymptotic narrative that LTM error tracks the central model.\n\nSoft spots beyond the δ bug: the n-independent error claim is asymptotic. Below the fallback threshold the randomizer outputs zero and utility is vacuous; the paper only gives a trivial bound there. That should be stated as a condition in the theorems. The experiments use a free interpolation exponent p, which is fine as validation but not a direct test of the theorems. Scattered typos (e.g., 'approxiamtion', a corrupted reference) are minor.\n\nThis paper is for people working on distributed DP and private linear algebra. It deserves a serious referee; with the δ fix it is solid. I would bring it to a reading group.","headline":"A genuinely new trust model with n-independent error for private linear algebra, but the sparse-sketch privacy proof has a δ-accounting bug that must be fixed before the headline guarantees are accepted.","tokens_in":34495,"tokens_out":3846,"would_cite":true,"duration_ms":35297,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes that a public Johnson-Lindenstrauss sketch computed on noise-perturbed rows by secret-shared servers is enough for differentially private low-rank approximation and ridge regression with error independent of the…","keywords":["differential privacy","linear-transformation model","Johnson-Lindenstrauss sketch","oblivious subspace embedding","low-rank approximation","ridge regression","secure multiparty computation","infinite divisibility"],"falsifier":"Run the sparse sketching mechanism with $s=1$, $m=50$, $\\delta=0.01$, $t'=0$: the randomizer outputs the zero vector whenever $n < 8\\cdot 50\\cdot \\ln(50/0.01) \\approx 3408$, so at $n=2000$ the released sketch is identically zero and the low-rank error is the trivial $\\|A\\|_F$ rather than the $n$-independent bound of Theorem 5.4. Measuring the error across $n$ from 1000 to 10000 would directly show where the claimed utility starts to hold.","tokens_in":1837,"feed_emoji":"🔒","tokens_out":2980,"duration_ms":91221,"temperature":0.7,"pith_summary":"This paper tries to show that a very restricted trusted capability—applying a public linear transformation to clients' inputs—is enough to get differentially private analytics with error comparable to the central model, without trusting any single server. The proposed linear-transformation model lets each client add a small amount of noise, then has multiple servers compute a public Johnson-Lindenstrauss sketch of the noisy rows using secret sharing; because the sketch sums many clients' noise pieces, the total noise matches what a central mechanism would add. On low-rank approximation and ridge regression the paper proves error bounds that do not grow with the number of clients $n$, unlike the local model where $\\Omega(\\sqrt{n})$ error is necessary, and it reports experiments where the error asymptotically approaches the central-model baseline as $n$ grows. The significance, if correct, is that a cheap, one-round, information-theoretically secure multiparty computation primitive can replace the trusted curator for a useful class of numerical linear algebra tasks.","feed_headline":"Secure sketching gives privacy error independent of n","feed_subtitle":"Clients add tiny noise, servers apply a public linear sketch, and summed noise matches central-DP error without a trusted party.","key_machinery":"The load-bearing object is the sparse OSNAP sketch, a Johnson-Lindenstrauss transform with $s$ non-zero entries per column, decomposed as $S = (1/\\sqrt{s}) \\sum_{i=1}^s S_i$, where each $S_i$ has one non-zero entry per column. The privacy argument splits each client's noise across this decomposition: by infinite divisibility of the noise distribution, the sum of the noise pieces that land in a fixed output entry is distributed as the noise a central mechanism would add, provided each row receives at least $(n-s-t')/(2m)$ honest clients. Lemma 4.5's Chernoff bound on row occupancy supplies this with high probability, and linear secret sharing lets servers apply the public transform to their shares without communicating, giving a one-round protocol.","core_discovery":"The paper's central discovery is that a public random projection—a Johnson-Lindenstrauss sketch—computed by servers over clients' noise-perturbed rows is enough to reproduce central-model differential privacy in a distributed setting. Because each client adds only a small piece of noise and the sketch sums many pieces together, the total noise entering each output entry matches the noise a central mechanism would add; the infinite divisibility of Gaussians and Laplacians makes this exact. The resulting $(\\varepsilon,\\delta)$-private low-rank approximation has multiplicative error $(1+O(\\alpha_S))$ and additive error $\\widetilde{O}(k d^{3/2} \\alpha_S^{-3} \\varepsilon^{-1} \\log^{1/2}(1/\\delta))$, and ridge regression under a sufficiently large regularization parameter $\\lambda$ has multiplicative error $(1+o(1))$ and additive error $\\mathrm{poly}(\\varepsilon^{-1}, d, \\log 1/\\delta)$. The error in both cases is independent of the number of clients $n$, which is the feature that separates the linear-transformation model from the local model, where $\\Omega(\\sqrt{n})$ error is unavoidable even for basic frequency estimation.","pith_inferences":["The same noise-splitting argument should transfer to any analysis whose objective is preserved by subspace embeddings, such as $k$-means clustering or spectral distance estimation; the error would again be $n$-independent.","Because the dense Rademacher variant achieves pure $\\varepsilon$-DP, the linear-transformation model may be a route to pure-DP central-level accuracy without a trusted party, at the cost of a worse polynomial dependence in $d$ and $\\varepsilon$.","The fallback zero-output regime implies a participation threshold: for a fixed sketch width $m$, privacy and utility only hold when $n \\gtrsim 8m\\ln(dm/\\delta)$; below it the mechanism degenerates. Choosing $m$ as small as target accuracy allows would widen the usable $n$-range.","An immediate experimental check is to hold $m$ fixed and sweep $n$ across that threshold: error should be roughly flat above it and jump to the trivial fallback below it."],"forward_implications":["For low-rank approximation, the Gaussian variant achieves $(1+O(\\alpha_S))$ multiplicative error and additive error $\\widetilde{O}(k d^{3/2} \\alpha_S^{-3} \\varepsilon^{-1} \\log^{1/2}(1/\\delta))$, with no dependence on $n$.","For ridge regression with $\\lambda \\ge \\mathrm{poly}(\\varepsilon^{-1}, d, \\log 1/\\delta)$, the same protocol has $(1+o(1))$ multiplicative error and additive error $\\mathrm{poly}(\\varepsilon^{-1}, d, \\log 1/\\delta)$, again independent of $n$.","A pure $\\varepsilon$-DP variant using dense Rademacher sketches and Laplace-type noise achieves $(1+O(\\alpha_S))$ multiplicative error with additive error $\\widetilde{O}(k^3 d^{3/2} \\alpha_S^{-6} \\varepsilon^{-1})$, at the price of a worse polynomial dependence.","The protocol uses one round of client-to-server communication, and servers apply the public transform locally to secret shares, so the per-server work is dominated by the input size and sketch sparsity rather than by cryptographic operations.","The reported experiments show the mechanism's error approaching the central-model baseline as $n$ grows, on both synthetic and real datasets."],"supporting_citations":[{"why":"gives the $\\Omega(\\sqrt{n})$ local-model lower bound that the $n$-independent LTM error avoids.","marker":"[7]"},{"why":"supplies the central-model low-rank perturbation baseline used in the empirical low-rank comparison.","marker":"[17]"},{"why":"provides the target-dimension and sparsity trade-off for OSNAPs that the utility bounds are parameterized by.","marker":"[22]"},{"why":"provides the subspace-embedding distortion lemma that converts sketch error into low-rank approximation error.","marker":"[23]"},{"why":"defines differential privacy and the Laplace mechanism on which the pure-$\\varepsilon$ variant is built.","marker":"[28]"},{"why":"gives the Gaussian mechanism and sensitivity calibration used for the $(\\varepsilon,\\delta)$ variant.","marker":"[29]"},{"why":"sets the central-model low-rank approximation error bound that the LTM result is compared against.","marker":"[30]"},{"why":"introduces the OSNAP family whose random sign matrices are decomposed into single-nonzero-per-column pieces.","marker":"[58]"}],"fun_headline_variants":["Distributed DP via sketches: error independent of n","Sketches give central privacy without a trusted server","Sketch noise sums to central DP, independent of n","Linear sketches: distributed DP without the local noise penalty","Public sketch, private sum: DP error independent of n"],"cache_read_input_tokens":36608,"weakest_assumption_plain":"The load-bearing premise is that the number of participating clients is large enough that every one of the $m$ sketch rows still contains many honest clients' noise after accounting for corruptions; below the threshold $n \\ge 8m\\ln(dm/\\delta)+t'$ the randomizer outputs the zero vector and the utility theorems do not apply.","fun_headline_variants_meta":{"raw":{"variants":["Distributed DP via sketches: error independent of n","Sketches give central privacy without a trusted server","Sketch noise sums to central DP, independent of n","Linear sketches: distributed DP without the local noise penalty","Public sketch, private sum: DP error independent of n"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000629,"raw_usage":{"total_tokens":2934,"prompt_tokens":998,"completion_tokens":1936,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":614,"completion_tokens_details":{"reasoning_tokens":1858}},"tokens_in":614,"tokens_out":1936,"duration_ms":13531,"temperature":1.0,"reasoning_tokens":1858,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:24:02.531575+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the sparse sketching mechanism with $s=1$, $m=50$, $\\delta=0.01$, $t'=0$: the randomizer outputs the zero vector whenever $n < 8\\cdot 50\\cdot \\ln(50/0.01) \\approx 3408$, so at $n=2000$ the released sketch is identically zero and the low-rank error is the trivial $\\|A\\|_F$ rather than the $n$-independent bound of Theorem 5.4. Measuring the error across $n$ from 1000 to 10000 would directly show where the claimed utility starts to hold.","supporting_citations":[{"cited_title":"Sarwate, and Kaushik Sinha","cited_arxiv_id":null,"evidence_quote":"supplies the central-model low-rank perturbation baseline used in the empirical low-rank comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"defines differential privacy and the Laplace mechanism on which the pure-$\\varepsilon$ variant is built."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"introduces the OSNAP family whose random sign matrices are decomposed into single-nonzero-per-column pieces."}],"review_version":1}