Pith. sign in

REVIEW 3 major objections 7 minor 81 references

Distributed Differentially Private Data Analytics via Secure Sketching

T0 review · 3 major / 7 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 2412.00497 v2 pith:UOFSMKAW submitted 2024-11-30 cs.CR cs.LG

Jakob Burkhardt , Hannah Keller , Claudio Orlandi , Chris Schwiegelshohn This is my paper · ORCID
classification cs.CRcs.LG
keywords differentialprivacylinear-transformationmodelJohnson-Lindenstrausssketchoblivioussubspaceembeddinglow-rankapproximationridgeregressionsecuremultipartycomputationinfinitedivisibility
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 7 minor

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.

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 (3)
  1. [§4.2, Theorem 4.4, Eq. (2), Corollary 4.7] 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.
  2. [§4, Definitions 4.1–4.2, Lemma 4.6] 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.
  3. [§5, Theorems 5.4, 5.7, 5.8] 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.
minor comments (7)
  1. [Corollary 4.7 (proof)] 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.
  2. [Theorems 5.4 and 5.8 (statements/proofs)] 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.
  3. [Theorem 5.7 (proof)] 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′.
  4. [Table 1] 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.
  5. [References] References [64] and [65] both cite the same paper (N. M. Stausholm, PODS 2021) and should be merged.
  6. [Lemma 5.3] 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.
  7. [Theorem 4.4 statement] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the privacy and utility derivations reduce to standard Gaussian/Laplace mechanisms, infinite divisibility, and external OSNAP subspace-embedding bounds; self-citations are not load-bearing.

full rationale

The derivation chain is self-contained with respect to the claimed results. The privacy analysis (Theorem 4.4, Lemma 4.6, Corollary 4.7) reduces the distributed randomizer R_D and the linear transformation T_S to the standard additive Gaussian/Laplace mechanism: per-client noise is chosen so that the summed noise on each sketch output is exactly the noise of the central mechanism, relying on infinite divisibility and a Chernoff bound (Lemma 4.5) on the number of honest clients contributing to each row. This is a genuine reduction rather than an assumption of the conclusion, and the central mechanism's privacy is established externally through sensitivity analysis (Lemmas 3.3 and 3.4). The utility theorems (5.4, 5.7, 5.8) use the OSNAP subspace-embedding property from external work by Nelson and Nguyên [58] and Cohen [22]; the paper explicitly states that the main proofs use the [22] parameter trade-offs, while the authors' own prior work [42] is mentioned only as an alternative trade-off changing the bounds by logarithmic factors and is not used to establish the main theorems. The experimental section varies noise variance as n^{-p} to illustrate interpolation between local and LTM behavior, but these choices do not feed back into the theorems; the experiments are validation, not calibration. The concerns I found are correctness risks rather than circularity: a possible mismatch between the delta/d threshold in Eq. (2) and the delta/(sd) budget used in Theorem 4.4's composition, and the utility theorems being vacuous when n falls below the fallback threshold 8m ln(dm/delta)+t'. Neither involves fitting a parameter to the target output nor deriving a claim from its own statement. Therefore no circular step is present.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central claims rest on standard subspace embedding bounds, the security of additive secret sharing, bounded input ranges, and the infinite divisibility of the noise. One assumption is specific to this paper: the ridge regression guarantee requires λ ≥ poly(ε^{-1}, d, log 1/δ), otherwise the additive error terms explode.

free parameters (1)
  • experimental noise-interpolation exponent p = 0.5, 0.6, 0.7, 0.8, 0.9, 1.0
    Hand-chosen knob in Section 6.2 to interpolate noise variance between local (p=0) and LTM (p=1); not part of the theoretical results and not used to set theorem constants.
assumptions (5)
  • standard math OSNAP matrices from [22] satisfy the subspace embedding property (Definition 3.1) with m = O(k log(k/β)/α²) and s = O(log(k/β)/α)
    Relied upon in Theorems 5.4, 5.7, 5.8; cited to [22].
  • domain assumption Additive secret sharing provides an information-theoretically secure MPC protocol tolerating k-1 semi-honest corruptions
    Section 4.3; needed for Lemma 4.3 and Corollary 4.11.
  • domain assumption Input values are bounded in magnitude by η
    Used to bound sensitivity in Corollaries 4.7 and 4.10; standard bounded-range assumption.
  • domain assumption The noise distribution D is symmetric and infinitely divisible, so the sum of (n-s-t')/(2m) i.i.d. samples is distributed as D'
    Core noise-splitting property in Theorem 4.4; instantiated by Gaussian and Gamma/Laplace distributions.
  • ad hoc to paper Ridge regression requires λ ≥ poly(ε^{-1}, d, log 1/δ)
    Assumption in the introduction and Theorem 5.8; without it the additive error terms p and p² are not small.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Distributed Differentially Private Data Analytics via Secure Sketching." pith.science (2026). https://pith.science/paper/UOFSMKAW

@misc{pith2026241200497,
  author       = {Pith},
  title        = {Pith review of: Distributed Differentially Private Data Analytics via Secure Sketching},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UOFSMKAW}},
  note         = {Machine review of arXiv:2412.00497}
}
read the original abstract

We introduce the linear-transformation model, a distributed model of differentially private data analysis. Clients have access to a trusted platform capable of applying a public matrix to their inputs. Such computations can be securely distributed across multiple servers using simple and efficient secure multiparty computation techniques. The linear-transformation model serves as an intermediate model between the highly expressive central model and the minimal local model. In the central model, clients have access to a trusted platform capable of applying any function to their inputs. However, this expressiveness comes at a cost, as it is often prohibitively expensive to distribute such computations, leading to the central model typically being implemented by a single trusted server. In contrast, the local model assumes no trusted platform, which forces clients to add significant noise to their data. The linear-transformation model avoids the single point of failure for privacy present in the central model, while also mitigating the high noise required in the local model. We demonstrate that linear transformations are very useful for differential privacy, allowing for the computation of linear sketches of input data. These sketches largely preserve utility for tasks such as private low-rank approximation and private ridge regression, while introducing only minimal error, critically independent of the number of clients.

Figures

Figures reproduced from arXiv: 2412.00497 by the authors.

Figure 1
Figure 1. Adversary’s View the protocol to corrupt up to all but one servers and all but one client. We also operate in the same semi-honest setting, but define parameters 𝑡 and 𝑡 ′ for the number of tolerated server and client corruptions. The view View𝑅,Π,𝐴 𝐶𝑐𝑜𝑟 ,𝑆𝑐𝑜𝑟 (𝑥) of the adversary consists of all the information available to the corrupted clients 𝐶𝑐𝑜𝑟 and servers 𝑆𝑐𝑜𝑟 plus the final output of the honest, uncorrupted… view at source ↗
Figure 2
Figure 2. Plots depicting the asymptotic behavior of error [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Plots depicting the asymptotic behavior of error [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Plots depicting the error 𝜙 as 𝑛 increases, for 𝜀 ∈ {0.01, 0.03, 0.05, 0.1} (top to bottom) and 𝜆 ∈ {1, 10, 100} (left to right). The middle row depicts the same choice of parameters as [PITH_FULL_IMAGE:figures/full_fig_p018_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

81 extracted references · 57 canonical work pages

  1. [1]

    Dimitris Achlioptas. 2003. Database-friendly random projections: Johnson- Lindenstrauss with binary coins. J. Comput. Syst. Sci. 66, 4 (2003), 671–687. https://doi.org/10.1016/S0022-0000(03)00025-4

    doi:10.1016/s0022-0000(03)00025-4 2003

  2. [2]

    Apple and Google. 2021. Exposure Notification Privacy-preserving Analytics (ENPA). White Paper

    2021

  3. [3]

    Raman Arora, Vladimir Braverman, and Jalaj Upadhyay. 2018. Differentially Private Robust Low-Rank Approximation. In Advances in Neural Information Processing Systems

    work page 2018

  4. [4]

    Sanjeev Arora, Elad Hazan, and Satyen Kale. 2006. A Fast Random Sampling Algorithm for Sparsifying Matrices. In Approximation, Randomization, and Com- binatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomizati...

    work page 2006

  5. [5]

    Maria-Florina Balcan, Simon Shaolei Du, Yining Wang, and Adams Wei Yu. 2016. An Improved Gap-Dependency Analysis of the Noisy Power Method. In 29th Annual Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 49), Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (Eds.). PMLR, Columbia University, New York, New York, USA, 284–309....

    work page 2016

  6. [6]

    Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Thakurta. 2020. Practical Locally Private Heavy Hitters. J. Mach. Learn. Res. 21 (2020), 16:1–16:42. https: //jmlr.org/papers/v21/18-786.html

    work page 2020

  7. [7]

    Raef Bassily and Adam D. Smith. 2015. Local, Private, Efficient Protocols for Succinct Histograms. In Proceedings of the Forty-Seventh Annual ACM on Sym- posium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, Rocco A. Servedio and Ronitt Rubinfeld (Eds.). ACM, 127–135. https: //doi.org/10.1145/2746539.2746632

    arXiv 2015

  8. [8]

    Smith, and Abhradeep Thakurta

    Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. 2014. Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS

    work page 2014

Show all 81 references
  1. [9]

    Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn. 2019. Oblivious dimension reduction for k-means: beyond subspaces and the Johnson-Lindenstrauss lemma. InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC

    2019

  2. [10]

    Amos Beimel, Iftach Haitner, Kobbi Nissim, and Uri Stemmer. 2020. On the Round Complexity of the Shuffle Model. In Theory of Cryptography: 18th International Conference, TCC 2020, Durham, NC, USA, November 16–19, 2020, Proceedings, Part II. Springer-Verlag, Berlin, Heidelberg,...

    2020 doi

  3. [11]

    Bertin-Mahieux

    T. Bertin-Mahieux. 2011. YearPredictionMSD. UCI Machine Learning Repository. DOI: https://doi.org/10.24432/C50K61

    2011 doi

  4. [12]

    Andrea Bittau, Úlfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghu- nathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. 2017. Prochlo: Strong Privacy for Analytics in the Crowd. In Proceedings of the 26th Symposium on Operating Sys...

    2017

  5. [13]

    Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. 2012. The Johnson- Lindenstrauss Transform Itself Preserves Differential Privacy. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012 . IEEE Computer...

    2012 doi

  6. [14]

    Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. 2005. Prac- tical privacy: the SuLQ framework. In Proceedings of the Twenty-Fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (, Balti- more, Maryland,) (PODS ’05). Association for Computing...

    2005

  7. [15]

    Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth

    Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. 2017. Practi- cal Secure Aggregation for Privacy-Preserving Machine Learning. In Proceedings of the 2017 ACM SIGSAC Conference on Compu...

    2017

  8. [16]

    Tony Cai, Yichen Wang, and Linjun Zhang

    T. Tony Cai, Yichen Wang, and Linjun Zhang. 2021. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics 49, 5 (2021), 2825 – 2850. https://doi.org/10.1214/21-AOS2058

    2021 doi

  9. [17]

    Sarwate, and Kaushik Sinha

    Kamalika Chaudhuri, Anand D. Sarwate, and Kaushik Sinha. 2012. Near-optimal Differentially Private Principal Components. In Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held...

    2012

  10. [18]

    Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev

  11. [19]

    Albert Cheu and Chao Yan. 2023. Necessary Conditions in Multi-Server Differ- ential Privacy. In 14th Innovations in Theoretical Computer Science Conference (ITCS)

    2023

  12. [20]

    Clarkson and David P

    Kenneth L. Clarkson and David P. Woodruff. 2009. Numerical linear algebra in the streaming model. InProceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009 , Michael Mitzenmacher (Ed.). ACM, 205–214. https://doi....

    2009

  13. [22]

    Michael B. Cohen. 2016. Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, V A, USA, January 10-12, 2016, Robert Krauthgamer (Ed.). SIAM, 278–287. https:...

    2016 doi

  14. [23]

    Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu

    Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. 2015. Dimensionality Reduction for k-Means Clustering and Low Rank Approximation. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA...

    2015

  15. [24]

    Ronald Cramer, Ivan Bjerre Damgård, and Jesper Buus Nielsen. 2015. Secure Multiparty Computation and Secret Sharing . Cambridge University Press

    2015

  16. [25]

    Ivan Damgård, Hannah Keller, Boel Nelson, Claudio Orlandi, and Rasmus Pagh

  17. [26]

    Christos Dimitrakakis, Blaine Nelson, Aikaterini Mitrokotsa, and Benjamin I. P. Rubinstein. 2014. Robust and Private Bayesian Inference. In Algorithmic Learning Theory. Springer International Publishing, Cham, 291–305

    2014

  18. [27]

    Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. 2006. Our Data, Ourselves: Privacy Via Distributed Noise Generation. In Advances in Cryptology - EUROCRYPT

    2006

  19. [28]

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrat- ing Noise to Sensitivity in Private Data Analysis. In Theory of Cryptography

    2006

  20. [29]

    Cynthia Dwork and Aaron Roth. 2014. The Algorithmic Foundations of Differen- tial Privacy. Foundations and Trends in Theoretical Computer Science (2014)

    2014

  21. [30]

    Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. 2014. Analyze gauss: optimal bounds for privacy-preserving principal component analysis. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014 , David B. Shmoys (Ed.). ACM, 11–20...

    2014

  22. [31]

    Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. 2019. Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity. In Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

    2019

  23. [32]

    Jordi Fonollosa. 2015. Gas sensor array under dynamic gas mixtures. UCI Machine Learning Repository. DOI: https://doi.org/10.24432/C5WP4C

    2015 doi

  24. [33]

    James Foulds, Joseph Geumlek, Max Welling, and Kamalika Chaudhuri. 2016. On the Theory and practice of privacy-preserving Bayesian data analysis. In Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence (Jersey City, New Jersey, USA) (UAI’16). A...

    2016

  25. [34]

    Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker

  26. [35]

    Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Adam Sealfon

  27. [36]

    Badih Ghazi, Ravi Kumar, Pasin Manurangsi, and Rasmus Pagh. 2020. Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual...

    2020

  28. [37]

    Slawomir Goryczka and Li Xiong. 2017. A Comprehensive Comparison of Multi- party Secure Additions with Differential Privacy.IEEE Transactions on Dependable and Secure Computing (2017)

    2017

  29. [38]

    Moritz Hardt and Eric Price. 2014. The Noisy Power Method: A Meta Algo- rithm with Applications. In Advances in Neural Information Processing Systems , Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (Eds.), Vol. 27. Curran Associates, Inc. https://proce...

    2014

  30. [39]

    On Computing Pairwise Statistics with Local Differential Privacy. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, Alice Oh, Tristan Naumann, Am...

    2023

  31. [41]

    Georges Hebrail and Alice Berard. 2012. Individual household elec- tric power consumption. UCI Machine Learning Repository. DOI: https://doi.org/10.24432/C58K54

    2012 doi

  32. [42]

    Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, and Chris Schwiegelshohn. 2023. Sparse Dimensionality Reduction Revis- ited. CoRR abs/2302.06165 (2023). https://doi.org/10.48550/ARXIV.2302.06165 arXiv:2302.06165

    2023 doi arXiv

  33. [43]

    Moritz Hardt and Aaron Roth. 2012. Beating randomized response on incoherent matrices. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (New York, New York, USA)(STOC ’12). Association for Computing Machinery, New York, NY, USA, 1255–1268. https:/...

    2012 doi

  34. [44]

    Michael Kapralov and Kunal Talwar. [n. d.]. On differentially private low rank approximation. 1395–1414. https://doi.org/10.1137/1.9781611973105.101 arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611973105.101

    doi

  35. [45]

    Lee, Kobbi Nissim, Sofya Raskhod- nikova, and Adam Smith

    Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhod- nikova, and Adam Smith. 2008. What Can We Learn Privately?. In 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS)

    2008

  36. [46]

    Manohar Kaul. 2013. 3D Road Network (North Jutland, Denmark). UCI Machine Learning Repository. DOI: https://doi.org/10.24432/C5GP51

    2013 doi

  37. [47]

    Kane and Jelani Nelson

    Daniel M. Kane and Jelani Nelson. 2012. Sparser Johnson-Lindenstrauss trans- forms. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012 , Yuval Rabani (Ed.). SIAM, 1195–1206. https://doi.org/10.1137/...

    2012 doi

  38. [48]

    Krishnaram Kenthapadi, Aleksandra Korolova, Ilya Mironov, and Nina Mishra

  39. [49]

    Smith, and Abhradeep Thakurta

    Daniel Kifer, Adam D. Smith, and Abhradeep Thakurta. 2012. Private Convex Opti- mization for Empirical Risk Minimization with Applications to High-dimensional Regression. In The 25th Annual Conference on Learning Theory (COLT)

    2012

  40. [50]

    Beatrice Laurent and Pascal Massart. 2000. Adaptive estimation of a quadratic functional by model selection. Annals of statistics (2000), 1302–1338

    2000

  41. [51]

    Marcel Keller. 2020. MP-SPDZ: A Versatile Framework for Multi-Party Com- putation. In CCS ’20: 2020 ACM SIGSAC Conference on Computer and Commu- nications Security, Virtual Event, USA, November 9-13, 2020 , Jay Ligatti, Xin- ming Ou, Jonathan Katz, and Giovanni Vigna (Eds.). A...

    2020

  42. [52]

    Xiyang Liu, Weihao Kong, and Seewong Oh. 2022. Differential privacy and robust statistics in high dimensions. In Conference on Learning Theory

    2022

  43. [53]

    Luca Melis, George Danezis, and Emiliano De Cristofaro. 2016. Efficient Private Statistics with Succinct Sketches. https://doi.org/10.14722/ndss.2016.23175

    2016

  44. [54]

    Xiangrui Meng and Michael W. Mahoney. 2013. Low-distortion subspace em- beddings in input-sparsity time and applications to robust linear regression. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, Dan Boneh, Tim Roughgarden, and Jo...

    2013

  45. [55]

    Jason Milionis, Alkis Kalavasis, Dimitris Fotakis, and Stratis Ioannidis. 2022. Dif- ferentially Private Regression with Unbounded Covariates. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Researc...

    2022

  46. [56]

    Woodruff

    Yingyu Liang, Maria-Florina Balcan, Vandana Kanchanapally, and David P. Woodruff. 2014. Improved Distributed Principal Component Analysis. In Ad- vances in Neural Information Processing Systems 27: Annual Conference on Neu- ral Information Processing Systems 2014, December 8-1...

    2014

  47. [57]

    Vaikkunth Mugunthan, Antigoni Polychroniadou, David Byrd, and Tucker Hybi- nette Balch. 2019. Smpai: Secure multi-party computation for federated learning. In Proceedings of the NeurIPS 2019 Workshop on Robust AI in Financial Services

    2019

  48. [58]

    Jelani Nelson and Huy L Nguyên. 2013. OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS

    2013

  49. [59]

    Aleksandar Nikolov. 2023. Private Query Release via the Johnson-Lindenstrauss Transform. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Al- gorithms, SODA 2023, Florence, Italy, January 22-25, 2023 , Nikhil Bansal and Viswanath Nagarajan (Eds.). SIAM, 4982–5002. htt...

    2023 doi

  50. [60]

    Rasmus Pagh and Mikkel Thorup. 2022. Improved Utility Analysis of Private CountSketch. In Advances in Neural Information Processing Systems , S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (Eds.), Vol. 35. Curran 19 Associates, Inc., 25631–25643. https://pro...

    2022

  51. [61]

    Kentaro Minami, HItomi Arai, Issei Sato, and Hiroshi Nakagawa. 2016. Differ- ential Privacy without Sensitivity. In Advances in Neural Information Processing Systems, D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (Eds.), Vol. 29. Curran Associates, Inc. https://pro...

    2016

  52. [62]

    Tamás Sarlós. 2006. Improved Approximation Algorithms for Large Matrices via Random Projections. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings . IEEE Computer Society, 143–152. https://d...

    2006 doi

  53. [63]

    Or Sheffet. 2019. Old Techniques in Differentially Private Linear Regression. In Proceedings of the 30th International Conference on Algorithmic Learning Theory (Proceedings of Machine Learning Research, Vol. 98) , Aurélien Garivier and Satyen Kale (Eds.). PMLR, 789–827. https...

    2019

  54. [65]

    Nina Mesing Stausholm. 2021. Improved Differentially Private Euclidean Distance Approximation. In PODS’21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Virtual Event, China, June 20-25, 2021, Leonid Libkin, Reinhard Pichler, and ...

    2021

  55. [66]

    Gilles Pisier. 1999. The volume of convex bodies and Banach space geometry. Cambridge Tracts in Mathematics. 94

    1999

  56. [67]

    Kunal Talwar, Shan Wang, Audra McMillan, Vojta Jina, Vitaly Feldman, Bailey Basile, Aine Cahill, Yi Sheng Chan, Mike Chatzidakis, Junye Chen, Oliver Chick, Mona Chitnis, Suman Ganta, Yusuf Goren, Filip Granqvist, Kristine Guo, Frederic Jacobs, Omid Javidbakht, Albert Liu, Rich...

    2023 arXiv

  57. [68]

    Jalaj Upadhyay. 2018. The Price of Privacy for Low-rank Factorization. In Ad- vances in Neural Information Processing Systems

    2018

  58. [69]

    Prateek Varshney, Abhradeep Thakurta, and Prateek Jain. 2022. (Nearly) Opti- mal Private Linear Regression for Sub-Gaussian Data via Adaptive Clipping. In Proceedings of Thirty Fifth Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 178) , Po-Ling L...

    2022

  59. [70]

    Slavkovic

    Duy Vu and Aleksandra B. Slavkovic. 2009. Differential Privacy for Clinical Trial Data: Preliminary Evaluations. In ICDM Workshops 2009, IEEE International Conference on Data Mining

    2009

  60. [71]

    Thomas Steinke. 2020. Multi-Central Differential Privacy. https://doi.org/10. 48550/ARXIV.2009.05401

    2020 doi arXiv

  61. [72]

    Di Wang, Lijie Hu, Huanyu Zhang, Marco Gaboardi, and Jinhui Xu. 2023. Gen- eralized Linear Models in Non-interactive Local Differential Privacy with Pub- lic Data. Journal of Machine Learning Research 24, 132 (2023), 1–57. http: //jmlr.org/papers/v24/21-0523.html

    2023

  62. [73]

    Smith, and Jinhui Xu

    Di Wang, Adam D. Smith, and Jinhui Xu. 2018. Noninteractive Locally Private Learning of Linear Models via Polynomial Approximations. In International Conference on Algorithmic Learning Theory . https://api.semanticscholar.org/ CorpusID:67856419

    2018

  63. [74]

    Yu-Xiang Wang. 2018. Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain. In Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI

    2018

  64. [75]

    Fienberg, and Alexander J

    Yu-Xiang Wang, Stephen E. Fienberg, and Alexander J. Smola. 2015. Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo. In Proceedings of the 32nd International Conference on Machine Learning, ICML

    2015

  65. [76]

    Di Wang, Marco Gaboardi, and Jinhui Xu. 2018. Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited. In Advances in Neural Information Processing Systems

    2018

  66. [77]

    Woodruff

    David P. Woodruff. 2014. Sketching as a Tool for Numerical Linear Algebra. Found. Trends Theor. Comput. Sci. 10, 1-2 (2014), 1–157. https://doi.org/10.1561/ 0400000060

    2014

  67. [78]

    Fuheng Zhao, Dan Qiao, Rachel Redberg, Divyakant Agrawal, Amr El Abbadi, and Yu-Xiang Wang. 2022. Differentially private linear sketches: efficient imple- mentations and applications. In Proceedings of the 36th International Conference on Neural Information Processing Systems ...

    2022

  68. [79]

    Kai Zheng, Wenlong Mou, and Liwei Wang. 2017. Collect at once, use effectively: making non-interactive locally private learning possible. In Proceedings of the 34th International Conference on Machine Learning (ICML) . 20

    2017

  69. [81]

    Stanley L. Warner. 1965. Randomized Response: A Survey Technique for Elimi- nating Evasive Answer Bias. J. Amer. Statist. Assoc. (1965)

    1965

  70. [2013]

    Privacy via the Johnson-Lindenstrauss Transform. J. Priv. Confidentiality 5, 1 (2013). https://doi.org/10.29012/JPC.V5I1.625

    2013 doi

  71. [2019]

    In Advances in Cryptology EUROCRYPT

    Distributed Differential Privacy via Shuffling. In Advances in Cryptology EUROCRYPT

  72. [2021]

    On the Power of Multiple Anonymous Messages: Frequency Estimation and Selection in the Shuffle Model of Differential Privacy. In Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, C...

    2021

  73. [2023]

    In The Web Conference (WWW)

    Differentially Private Selection from Secure Distributed Computing. In The Web Conference (WWW)

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.