The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches

Ashia C. Wilson; Ayush Sekhari; Katrina Ligett; Moshe Shenfeld; Omri Lev; Vishwak Srinivasan

REVIEW 5 major objections 3 minor 18 references

The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches

T0 review · 5 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Gaussian sketching with added noise has a closed-form Rényi privacy curve, yielding tighter bounds for private regression.

desk verdict Solid RDP curve for GaussMix, but the adaptive mechanism has a units error that breaks Theorem 1 as printed; the core is worth a revision. read the letter →

arxiv 2505.24603 v2 pith:OWFH7LSG submitted 2025-05-30 cs.LG

Omri Lev , Vishwak Srinivasan , Moshe Shenfeld , Katrina Ligett , Ayush Sekhari , Ashia C. Wilson This is my paper

classification cs.LG MSC 68P2768W2062J05

keywords GaussiansketchingRényidifferentialprivacylinearregressionlogisticrandomprojectionamplificationtruncatedconcentrated

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

Gaussian sketching, which pre-multiplies data by a random Gaussian matrix, is widely used for scalable computation, and it has long been known to provide some differential privacy; this paper shows that its privacy can be counted exactly through Rényi differential privacy (RDP). The central result is a closed-form RDP curve for the 'Gaussian Mixing Mechanism' $M(X)=SX+\sigma\xi$, in which the guarantee improves as the data matrix's minimum eigenvalue grows, so the data's own structure contributes to hiding any row. The authors use this curve to design differentially private linear and logistic regression algorithms, derive theoretical utility bounds that match the AdaSSP baseline in the hardest case, and report experiments in which their method improves accuracy over prior GaussMix-based and AdaSSP baselines while often running faster. The paper is arguing, in short, that a tight RDP analysis is the right way to unlock the privacy already present in Gaussian sketching.

What carries the argument

The load-bearing object is the function $\varphi(\alpha;k,\zeta)$, a closed-form expression for the $\alpha$-Rényi divergence between the GaussMix outputs on neighboring datasets. It comes from writing the covariance difference between neighboring outputs as a rank-one update $x_i x_i^\top$, applying the determinant lemma $\det(A+uv^\top)=\det(A)(1+v^\top A^{-1}u)$, and then using monotonicity of $\frac{(1-t)^\alpha}{1-\alpha t}$ in $t$ to reduce $x_i^\top(X^\top X+\sigma^2 I_d)^{-1} x_i$ to the bound $\|x_i\|^2/(\lambda_{\min}(X^\top X)+\sigma^2) \le C_X^2/(\lambda_{\min}+\sigma^2)$. This chain has exactly one inequality, so the curve is tight exactly when the differing row is the minimal-eigenvalue eigenvector of $X^\top X$, giving equality for scaled semi-orthogonal $X$. The same $\varphi$ is what turns $\lambda_{\min}$ into a usable privacy amplification knob in the regression algorithms.

What would settle it

Take a matrix $X$ with $X^\top X = C_X^2 I_d$, zero out one row to get a neighbor $X'$, and numerically compute the $\alpha$-Rényi divergence between $N(0, X^\top X+\sigma^2 I_d)$ and $N(0, X'^\top X'+\sigma^2 I_d)$ for several $\alpha \in (1,\gamma)$; Lemma 1 predicts this divergence is exactly $\varphi(\alpha;k,\gamma)$, so a divergence exceeding that value at any such $\alpha$ would refute the claimed tight curve.

Watch

Extended reading notes

Core claim

The paper's central claim is that the Gaussian Mixing Mechanism obeys an exact, closed-form Rényi differential privacy curve. For any data matrix $X$ with row bound $C_X$ and scale bound $\lambda_{\min}$, if $\gamma := C_X^{-2}(\sigma^2+\lambda_{\min}) > 1$, then $M(X)=SX+\sigma\xi$ satisfies $(\alpha,\varphi(\alpha;k,\gamma))$-RDP for every $\alpha \in (1,\gamma)$, where $\varphi(\alpha;k,\zeta) = \frac{k\alpha}{2(\alpha-1)}\log(1-1/\zeta) - \frac{k}{2(\alpha-1)}\log(1-\alpha/\zeta)$. As a corollary, for $\gamma > 5/2$ the mechanism satisfies $(k/(2\gamma^2), 2\gamma/5)$-truncated concentrated DP. The proof bounds the divergence between neighboring outputs by a scalar quadratic form in the differing row, uses the smallest eigenvalue of $X^\top X+\sigma^2 I_d$ to bound that form, and is tight when $X^\top X = C_X^2 I_d$, i.e., when the scaled data matrix is semi-orthogonal. This tight accounting, in turn, underlies new differentially private linear and logistic regression algorithms whose utility bounds match or beat previous methods and whose experiments show better accuracy and lower runtime.

Load-bearing premise

The adaptive algorithm's privacy guarantee assumes that the privately released estimate of the data's smallest eigenvalue, combined with the planned noise level, still satisfies the core lemma's condition on the effective scale; if that calibration between the eigenvalue estimate and the nominal scale is off, the adaptive claim does not follow.

Editorial extensions

If this is right

For any application already using Gaussian sketching as its privacy mechanism, the closed-form RDP curve lowers the reported privacy loss at the same noise level, so the same outputs can be released with a smaller $\varepsilon$ or with more utility at the same $\varepsilon$.
The private linear regression algorithm (LinearMixing) matches the utility guarantee of AdaSSP in the worst case $\lambda_{\min}=0$ and improves on it empirically, while using the same one-shot sketching computation.
The RDP analysis also improves the privacy of existing algorithms that call GaussMix as a subroutine, such as earlier GaussMix-based algorithms, when their noise calibration is switched to the new curve.
For logistic regression, reducing the problem to a private quadratic via polynomial approximation lets GaussMix deliver a one-shot solver that is faster than iterative objective perturbation and at least as accurate on the datasets tested.
The result formalizes a form of privacy amplification: the more spread out the data is (larger $\lambda_{\min}$), the less additive noise is needed for the same privacy guarantee.

Reading between the lines

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

The tightness analysis suggests an instance-specific privacy curve that uses the full spectrum of $X^\top X$ rather than only $\lambda_{\min}$; the authors do not pursue this, but it would give even tighter accounting for anisotropic data.
A testable extension is to run the same Rényi derivation for other sketching ensembles such as randomized Hadamard or sparse sketches, since the determinant-based argument only needs a known lower bound on the sketched covariance's eigenvalues.
For the adaptive mechanism to be fully self-consistent, the privately estimated eigenvalue would need to be re-scaled into the same dimensionless units as the target $\gamma$ used in Lemma 1; with that normalization the authors' Theorem 1 would close cleanly, and the same fix would apply to any algorithm using the adaptive noise scheduler.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Dear colleague,

The paper's core contribution is a genuine new result: a closed-form Rényi DP curve for the Gaussian Mixing mechanism (Lemma 1), derived cleanly from Gaussian divergence formulas and a determinant identity. Corollary 1 gives a tCDP bound, and the comparison to Sheffet's older (ε,δ) analysis shows real improvement. This is worth knowing about even if the surrounding machinery has problems.

What the paper does well: Lemma 1 and Corollary 1 are mathematically sound. The bound is tight in the constructed worst case, the linear regression utility analysis matches AdaSSP in the λmin=0 regime, and the code is available. The tightness discussion is honest about the assumptions under which equality holds.

The soft spot is in the adaptive mechanism, and it is load-bearing. Algorithm 1 mixes normalized and unnormalized scales. Lemma 1 works with the dimensionless quantity ζ = C_X^{-2}(σ²+λmin). Algorithm 1 privately estimates λmin(X^T X), which has units of squared data entries, then sets eη = sqrt(max{γ − eλ, 0}). Theorem 1's proof checks eη² + λmin ≥ γ, but that does not imply the Lemma 1 condition eη² + C_X^{-2}λmin ≥ γ. The stress-test example is correct: with C_X=10, λmin=1, γ=3, η=1, τ=2, z=2, the proof's inequality reads 3≥3, while the effective dimensionless scale is only 2.01. This happens with probability about 0.977, so it is not a rare bad event. As printed, Theorem 1 does not establish the claimed privacy guarantee, and since Algorithm 2 calls Algorithm 1, the regression algorithms inherit the problem.

The fix is local and should be straightforward: normalize the scale estimate (estimate λmin/C_X², which has sensitivity 1, then set eη = sqrt(max{γ − eλ, 0})). The non-adaptive branch also looks wrong: it outputs SX + γ C_X ξ, but to match Lemma 1 with λmin=0 the noise should be √γ C_X ξ. That is a smaller issue but it affects the utility analysis.

A separate empirical flaw: in the logistic regression experiments, k is tuned by grid search on the data and the privacy cost is explicitly not accounted for. That makes the reported ε optimistic.

Is this paper worth a serious referee? Yes. Lemma 1 is important, correct, and likely to be used by others. The adaptive flaw is a units error, not a conceptual one, and it is repairable. I would send it to review with a request to fix the normalization, correct the non-adaptive noise level, re-check the utility proof against the corrected algorithm, and either fix k in advance or account for its selection. A revised version could be a solid contribution.

Referee Report

5 major / 3 minor

Summary. The paper revisits the Gaussian Mixing Mechanism (GaussMix), M(X)=SX+σξ, under Rényi Differential Privacy. Lemma 1 derives a closed-form RDP curve φ(α;k,γ) for α∈(1,γ) when γ=C_X^{-2}(σ²+λmin)>1, and Corollary 1 converts this into a tCDP guarantee. The paper then uses this analysis to build adaptive private linear and logistic regression algorithms (Algorithm 1, Algorithm 2, and the logistic variant), claiming improved privacy-utility trade-offs over Sheffet and AdaSSP, with empirical validation on several datasets. The central privacy lemma is cleanly derived, but the adaptive mechanism in Algorithm 1 and Theorem 1 has a dimensional inconsistency between Lemma 1's dimensionless γ and the scale used in the pseudocode, and the proof contains a sign error in the success event. The utility proof in Theorem 3 also has an unjustified bound for the low-γ branch.

Significance. If Lemma 1 stands, it is a valuable contribution: a tight, parameter-free closed-form RDP curve for Gaussian sketching, derived from standard Gaussian Rényi divergence and determinant identities, with a concrete tightness example. The improved privacy analysis genuinely strengthens prior bounds by Sheffet and can be retrofitted into existing GaussMix-based algorithms. The paper also provides reproducible code and clear experimental comparisons. However, the adaptive Algorithm 1 and its privacy proof (Theorem 1) are load-bearing for the regression applications, and as printed they are not correct; the advertised utility guarantees depend on a noise scaling that the proof does not establish. These issues are localized and repairable, and the non-adaptive Lemma 1 analysis appears sound.

major comments (5)

[§4 (Algorithm 1, lines 4–6) and Appendix D] There is a dimensional inconsistency between Lemma 1 and the adaptive calibration. Lemma 1 defines a dimensionless γ=C_X^{-2}(σ²+λmin(X^T X)), so with σ=eη C_X the condition needed to apply the lemma at level γ is eη² + C_X^{-2}λmin(X^T X) ≥ γ. The proof of Theorem 1 instead verifies eη² + λmin(X^T X) ≥ γ, dropping the normalization by C_X^{-2}. For a concrete failure, take C_X=10, λmin(X^T X)=1, γ=3, η=1, τ=2, and z=1.5; then Algorithm 1 gives eλ=0.5, eη²=2.5, so the proof's inequality is 3.5≥3, but the lemma's effective scale is 2.5+0.01=2.51<3. Since P(z>1.01)≈0.156 exceeds the δ/3≈0.135 slack for τ=2, the claimed (ε,δ)-DP guarantee is violated with non-negligible probability. The fix is to release a private estimate of λmin(X^T X)/C_X² (which has sensitivity 1), set eη²=max{γ−eλ,0}, and verify the normalized condition eη² + λmin(X^T X)/C_X² ≥ γ.
[Appendix D (proof of Theorem 1)] The direction of the success event is stated incorrectly. The displayed identity gives eη²+λmin(X^T X)=γ+ηC_X²(τ−z), which is at least γ exactly when z≤τ, not z≥τ as the text claims. The subsequent failure probability P(eη²+λmin(X^T X)≤γ)=P(z≥τ)=δ/3 is correct for the event {z>τ}, but the sentence 'this is satisfied ... corresponds to having z ≥ τ' is false. The proof must be rewritten with the correct implication; the correction is local, but as printed the argument is invalid.
[§4 (Algorithm 1, line 2) and Appendix F] In the branch γ≤τ, Algorithm 1 outputs SX+γC_Xξ. With this noise, the dimensionless scale in Lemma 1 becomes γ²+C_X^{-2}λmin, which is larger than needed and breaks the utility analysis. Theorem 3's proof in Appendix F bounds the utility loss by O(γ(C_X²+C_Y²)(1+∥θ*∥²)), whereas the γ≤τ branch contributes a noise-scale factor of γ²(C_X²+C_Y²) to the covariance bias, a factor γ>1 larger. The branch should output SX+√γ C_Xξ (equivalently, √γ√(C_X²+C_Y²) on the concatenated matrix in Algorithm 2). This still satisfies Lemma 1 at effective scale at least γ and makes the utility bound in Theorem 3 valid.
[Appendix F (proof of Theorem 3)] The displayed chain ending '= 3√(2k log(3.75/δ))/γ' is not justified. The preceding expression contains min_{1<α<2γ/5} {kα/(2γ²)+log(3/δ)/(α−1)}, which is O(√(k log(1/δ))/γ) only after optimizing over α at roughly 1+√(2γ² log(1/δ)/k) and assuming k is at least a constant multiple of log(1/δ). As written, the additive terms k/(5γ) and log(3/δ)/(2γ/5−1) are dropped without comment. The final scaling γ=O(√(k log(1/δ))/ε) is plausible, but the proof needs to supply the optimization and the required condition on k and δ.
[Appendix J.2 (logistic regression experiments)] The text states: 'The privacy cost of this hyperparameter tuning was not included in our accounting.' The hyperparameter k is selected by grid search over a data-dependent range, so the ε reported for the logistic regression results does not cover the full algorithm. Either the selection must be shown to use only public information, the privacy cost must be absorbed into the budget, or the empirical privacy claims should be qualified. This does not affect Lemma 1, but it is a missing support for the empirical contribution.

minor comments (3)

[§4, 'Usage Without λmin'] The sentence 'In this case γ = σ²' is only correct after normalizing by C_X²; as written it should read γ=C_X^{-2}σ².
[Figure 3 and Appendix J.2] The reported runtime speedups for the logistic regression experiments are stated without confidence intervals or details on how the ratio is computed; adding error bars or a brief description would improve clarity.
[Notation, Algorithm 1 vs. Algorithm 2] Algorithm 1 uses C_X for the row bound while Algorithm 2 calls it with √(C_X²+C_Y²); the pseudocode would benefit from an explicit note that the noise scale in line 2 and line 6 is with respect to the row bound of the actual input matrix.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the RDP curve is derived from external Gaussian-divergence and determinant identities with no fitted constants, and the main caveats are correctness bugs rather than circular arguments.

full rationale

The central privacy result, Lemma 1, is derived from external ingredients: the closed-form Rényi divergence between multivariate Gaussians (Lemma 2, cited to Gil et al. 2013) and the rank-one determinant identity (Brookes 2020). The parameter gamma is defined as C_X^{-2}(sigma^2 + lambda_min), and the bound phi(alpha; k, gamma) follows from bounding x^T Sigma^{-1} x by ||x||^2 / lambda_min(Sigma); no fitted constant is reused as a prediction, and no quantity is defined in terms of the target bound. Corollary 1 is a direct analytic consequence. The regression utility analysis in Theorem 3 relies on external concentration results (Pilanci and Wainwright 2015, Corollary 2) and Wang (2018, Appendix B.2), again with no fitted-input-as-prediction step. The comparison with Sheffet 2019 and Wang 2018 is a benchmark against external work, not a self-citation chain. The most significant weakness is not circularity: in Algorithm 1, line 4 releases an estimate of unnormalized lambda_min with sensitivity C_X^2, while Lemma 1's condition requires the dimensionless quantity C_X^{-2}(sigma^2 + lambda_min) >= gamma; Theorem 1's proof checks e_eta^2 + lambda_min(X^T X) >= gamma, which does not imply the Lemma 1 hypothesis, and the effective dimensionless scale can fall below gamma with high probability. This is an invalid-step/correctness defect in the adaptive mechanism, not a derivation that presupposes its conclusion. Appendix J.2 also states that 'The privacy cost of this hyperparameter tuning was not included in our accounting,' a completeness limitation for the empirical privacy claims, but again this is not a circularity. Because the claimed RDP bound is self-contained against external mathematical facts and no prediction reduces to a fit, the circularity score is 0.

Assumptions & free parameters 2 free parameters · 7 assumptions · 0 invented entities

No fitted constants enter the central RDP derivation; it relies on known Gaussian divergence and determinant lemmas, the bounded-row and scale-bound assumptions, and concentration results from prior work. The chosen algorithm parameters are k and gamma, plus the proof slack chi in Theorem 3. The main hidden data-dependent choice is the logistic regression grid search over k, whose privacy cost is not counted.

free parameters (2)

sketch dimension k = user-set; grid searched from 1.5d to 7.5d in the logistic regression experiments
Controls the privacy-utility tradeoff. In the logistic experiments it is tuned on the data without accounting for privacy cost, which is a hidden selection.
target scale gamma = smallest value such that e_epsilon(eta, gamma, k, delta) <= epsilon, per Algorithm 2 line 1
Calibration parameter that sets the noise level in Algorithm 1. It is not fitted to data in the theory, but it is chosen to meet the privacy target.

assumptions (7)

standard math Closed-form Rényi divergence between multivariate Gaussians (Gil et al. 2013, Lemma 2).
Used in Appendix B to compute D_alpha(M(X) || M(X')).
standard math Determinant lemma det(A + uv^T) = det(A)(1 + v^T A^{-1} u) and the eigenvalue bound x^T A^{-1} x <= ||x||^2 / lambda_min(A).
Used to simplify the divergence and to reduce the bound to gamma; tight when the differing row aligns with the minimum eigenvector.
domain assumption Bounded domain assumption (A1): ||x_i|| <= C_X and |y_i| <= C_Y for all i.
Required for the sensitivity analysis and for Lemma 1's gamma normalization; stated in Section 5.1.
domain assumption Known lower bound lambda_min on lambda_min(X^T X).
Lemma 1 uses this scale bound; Algorithm 1 privately estimates it, which introduces the dimension-mismatch issue.
domain assumption Zero-out neighboring relation and n >= d (A2).
Privacy is defined over row removal and the utility proof assumes an overspecified system, as stated in Section 5.1.
standard math Pilanci-Wainwright Corollary 2 concentration for Gaussian sketched least squares.
Basis of Theorem 3's utility bound; cited and not re-derived in the paper.
domain assumption Second-order polynomial approximation of the logistic loss with approximation error q.
Used for private logistic regression in Section 5.2; validity requires y_i x_i^T theta to lie in [-Q, Q], as stated in Corollary 2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches." pith.science (2026). https://pith.science/paper/OWFH7LSG

@misc{pith2026250524603,
  author       = {Pith},
  title        = {Pith review of: The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OWFH7LSG}},
  note         = {Machine review of arXiv:2505.24603}
}

read the original abstract

Gaussian sketching, which consists of pre-multiplying the data with a random Gaussian matrix, is a widely used technique for multiple problems in data science and machine learning, with applications spanning computationally efficient optimization, coded computing, and federated learning. This operation also provides differential privacy guarantees due to its inherent randomness. In this work, we revisit this operation through the lens of Renyi Differential Privacy (RDP), providing a refined privacy analysis that yields significantly tighter bounds than prior results. We then demonstrate how this improved analysis leads to performance improvement in different linear regression settings, establishing theoretical utility guarantees. Empirically, our methods improve performance across multiple datasets and, in several cases, reduce runtime.

Figures

Figures reproduced from arXiv: 2505.24603 by the authors.

**Figure 1.** λmin + σ 2 required for attaining εDP, using Lemma 1 converted to (εDP, δ)-DP via Proposition 1, and compared to the bound from [Sheffet, 2019, Theorem 2]. We plot (a) the relation between εDP and λmin+σ 2 and (b) the ratio between the εDP attained by each bound. Our improved RDP analysis reduces the final εDP, illustrating the benefit of our new approach. Usage Without λmin. Since the bounded scale assumption canno… view at source ↗

**Figure 2.** Linear mixing performance on four different regression datasets. The parameter [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

**Figure 3.** DP logistic regression using a privately trained CNN feature extractor on binary subsets [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Linear mixing performance on the additional four linear regression tasks. [PITH_FULL_IMAGE:figures/full_fig_p029_4.png]

**Figure 5.** Figure 5: DP logistic regression using a privately trained CNN feature extractor on binary subsets [PITH_FULL_IMAGE:figures/full_fig_p030_5.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

18 extracted references · 15 canonical work pages

[1]

(5) For an invertible matrix A, we have [Brookes, 2020, Section

log det −αx1x⊤ 1 + X ⊤X + σ2Id (det (X ⊤X + σ2Id))1−α(det X ⊤X + σ2Id − x1x⊤ 1 )α ! . (5) For an invertible matrix A, we have [Brookes, 2020, Section. 3.4] det A + uv⊤ = det (A) (1 +v⊤A−1u). Since the matrix X ⊤X +σ2Id is invertible whenever σ2 > 0, this further tells us that the denominator of (5) can be simplified to det X ⊤X + σ2Id 1−α det X ⊤X + σ2Id ...

work page 2020
[2]

Our second baseline, from Sheffet [2017, Algorithm 1], was implemented according to the description in Appendix H.2

The ADASSP algorithm was implemented based on Wang [2018, Algorithm 2], following the procedure detailed in Appendix H.1. Our second baseline, from Sheffet [2017, Algorithm 1], was implemented according to the description in Appendix H.2. This implementation matches that of Sheffet [2017, Algorithm 1], except for an adjustment to account for a factor of 2...

work page 2018
[4]

1, Sheffet '17]: k d = 2.500 ADASSP [Wang '18] [Alg

28 10 1 100 101 DP 0.0 0.1 0.2 0.3 0.4 0.5Test MSE DP = min(10 6, 0.01 n ) Wine dataset Baseline [Alg. 1, Sheffet '17]: k d = 2.500 ADASSP [Wang '18] [Alg. 1, Sheffet '17] Our Analysis: k d = 2.500 Linear mixing (ours): k d = 2.500Linear mixing (ours): k d = 2.500 (a) Wine dataset 10 1 100 DP 0.0025 0.0050 0.0075 0.0100 0.0125 0.0150 0.0175 0.0200 0.0225T...

work page 2009
[9]

We usually denote our dataset {xi}n i=1 where each xi ∈ Rd in the matrix form X = (x1, . . . , xn)⊤. Then, we denote the j’th entry of xi by xi(j). The determinant of a matrix A is denoted by det (A). The set of integer numbers from 1 to n is denoted by [ n]. The all zeros column vector of size d is denoted by ⃗0d := (0 , . . . ,0)⊤. We denote by N (0, Ik...

work page 2013
[11]

We define the discriminant to be ∆H = 1 + 2γ + γ2 log 1 − 1 γ 2 − 8γ 1 + γ + γ2 log 1 − 1 γ which is non-negative

Moreover, G′(α) = 2α − 1 − γ2 log 1 − 1 γ − γ2 γ − α , and multiplying by ( γ − α) > 0 (recall that α < γ) shows G′(α) has the same sign as the quadratic H(α) := (γ − α)G′(α) = (2α − 1)(γ − α) − γ2(γ − α) log 1 − 1 γ − γ2 = −2α2 + 1 + 2γ + γ2 log 1 − 1 γ α − γ 1 + γ + γ2 log 1 − 1 γ . We define the discriminant to be ∆H = 1 + 2γ + γ2 log 1 − 1 γ 2 − 8γ 1 ...

work page 2017
[12]

The first case (when γ ≤ τ ) trivially satisfies this

log (1− 1/α) − log(α) α − 1 . The first case (when γ ≤ τ ) trivially satisfies this. However, for the second case (whenever γ > τ), this is satisfied only if eη2 + λmin(X ⊤X) ≥ γ, which by using the inequality eη2 + λmin(X ⊤X) = γ − λmin(X ⊤X) + ηC2 X τ − ηC2 X z + λmin(X ⊤X) = γ + ηC2 X τ − ηC2 X z corresponds to having z ≥ τ (we note that the case eλ = ...

work page 2014
[13]

H Algorithms: Linear Regression H.1 AdaSSP Algorithm 3 AdaSSP [Wang, 2018] Input: Dataset (X, Y); Privacy parameters ε, δ; Bounds: max i∈[n] ∥xi∥2 ≤ C2 X , max i∈[n] |yi|2 ≤ C2 Y

When we take χ ≪ 1, the bound acquires an extra 2 q term in the excess empirical risk relative to the bound obtained in the linear regression case, introduced by the polynomial approximation. H Algorithms: Linear Regression H.1 AdaSSP Algorithm 3 AdaSSP [Wang, 2018] Input: Dataset (X, Y); Privacy parameters ε, δ; Bounds: max i∈[n] ∥xi∥2 ≤ C2 X , max i∈[n]...

work page 2018
[14]

1: Compute λmin := λmin((X, Y)⊤(X, Y))

Algorithm 4 Sheffet’s Algorithm [Sheffet, 2017, Algorithm 1] Input: Dataset ( X, Y); Privacy parameters ε, δ; Bounds: max i∈[n] ∥xi∥2 ≤ C2 X , max i∈[n] |yi|2 ≤ C2 Y ; Hyperparameter k. 1: Compute λmin := λmin((X, Y)⊤(X, Y)). 2: Set γ ← 4(C2 X +C2 Y ) ε q 2k log 8 δ + 2 log 8 δ . 3: Sample S ∼ N (0, Ik×n). 4: if λmin > γ+ z + 4(C2 X +C2 Y ) log(1/δ) ε for...

work page 2017

Show all 18 references

[16]

The train and test loaders were generated using torch.utils.data.DataLoader with shuffling enabled

The same normalization factor was then applied to the test set. The train and test loaders were generated using torch.utils.data.DataLoader with shuffling enabled. In Appendix K.2 we present additional simulations with the CIF AR10 [Krizhevsky and Hinton, 2009] and the MNIST [...

2009
[500]

Runtime comparisons show the ratio of execution times for the largest simulated ε

Performance metrics are averaged over 250 independent runs, reporting test accuracy along with confidence intervals. Runtime comparisons show the ratio of execution times for the largest simulated ε. K Additional Experiments K.1 Linear Regression We have simulated additional f...

1978
[1961]

Improved approximation algorithms for large matrices via random projections

Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In 2006 47th annual IEEE symposium on foundations of computer science , pages 143–152. IEEE,

2006
[2006]

Private approximations of the 2nd-moment matrix using existing techniques in linear regression

Or Sheffet. Private approximations of the 2nd-moment matrix using existing techniques in linear regression. arXiv preprint arXiv:1507.00056 ,

arXiv
[2009]

edu/~kriz/learning-features-2009-TR.pdf

URL https://www.cs.toronto. edu/~kriz/learning-features-2009-TR.pdf . 14 Yann LeCun and Corinna Cortes. MNIST handwritten digit database,

2009
[2014]

Fashion-MNIST: a novel image dataset for bench- marking machine learning algorithms

Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: a novel image dataset for bench- marking machine learning algorithms. arXiv preprint arXiv:1708.07747 ,

arXiv
[2017]

Opacus: User-friendly differential privacy library in PyTorch

Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, et al. Opacus: User-friendly differential privacy library in PyTorch. arXiv preprint arXiv:2109.12298 ,

arXiv
[2018]

A History of Census Privacy Protections

United States Census Bureau. A History of Census Privacy Protections. https://www.census. gov/library/visualizations/2019/comm/history-privacy-protection.html,

2019
[2020]

Cecilia Ferrando and Daniel Sheldon

URL https://research.facebook.com/blog/2020/6/ protecting-privacy-in-facebook-mobility-data-during-the-covid-19-response/ . Cecilia Ferrando and Daniel Sheldon. Private regression via data-dependent sufficient statistic perturbation. arXiv preprint arXiv:2405.15002 ,

2020 arXiv
[2022]

Yuchang Sun, Jiawei Shao, Songze Li, Yuyi Mao, and Jun Zhang

URL https://eng.snap.com/ differential-privacy-at-snap . Yuchang Sun, Jiawei Shao, Songze Li, Yuyi Mao, and Jun Zhang. Stochastic coded federated learning with convergence and privacy guarantees. In Proceedings of the IEEE International Symposium on Information Theory , pages ...

Pith tools

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

[1] [1]

(5) For an invertible matrix A, we have [Brookes, 2020, Section

log det −αx1x⊤ 1 + X ⊤X + σ2Id (det (X ⊤X + σ2Id))1−α(det X ⊤X + σ2Id − x1x⊤ 1 )α ! . (5) For an invertible matrix A, we have [Brookes, 2020, Section. 3.4] det A + uv⊤ = det (A) (1 +v⊤A−1u). Since the matrix X ⊤X +σ2Id is invertible whenever σ2 > 0, this further tells us that the denominator of (5) can be simplified to det X ⊤X + σ2Id 1−α det X ⊤X + σ2Id ...

work page 2020

[2] [2]

Our second baseline, from Sheffet [2017, Algorithm 1], was implemented according to the description in Appendix H.2

The ADASSP algorithm was implemented based on Wang [2018, Algorithm 2], following the procedure detailed in Appendix H.1. Our second baseline, from Sheffet [2017, Algorithm 1], was implemented according to the description in Appendix H.2. This implementation matches that of Sheffet [2017, Algorithm 1], except for an adjustment to account for a factor of 2...

work page 2018

[3] [4]

1, Sheffet '17]: k d = 2.500 ADASSP [Wang '18] [Alg

28 10 1 100 101 DP 0.0 0.1 0.2 0.3 0.4 0.5Test MSE DP = min(10 6, 0.01 n ) Wine dataset Baseline [Alg. 1, Sheffet '17]: k d = 2.500 ADASSP [Wang '18] [Alg. 1, Sheffet '17] Our Analysis: k d = 2.500 Linear mixing (ours): k d = 2.500Linear mixing (ours): k d = 2.500 (a) Wine dataset 10 1 100 DP 0.0025 0.0050 0.0075 0.0100 0.0125 0.0150 0.0175 0.0200 0.0225T...

work page 2009

[4] [9]

We usually denote our dataset {xi}n i=1 where each xi ∈ Rd in the matrix form X = (x1, . . . , xn)⊤. Then, we denote the j’th entry of xi by xi(j). The determinant of a matrix A is denoted by det (A). The set of integer numbers from 1 to n is denoted by [ n]. The all zeros column vector of size d is denoted by ⃗0d := (0 , . . . ,0)⊤. We denote by N (0, Ik...

work page 2013

[5] [11]

We define the discriminant to be ∆H = 1 + 2γ + γ2 log 1 − 1 γ 2 − 8γ 1 + γ + γ2 log 1 − 1 γ which is non-negative

Moreover, G′(α) = 2α − 1 − γ2 log 1 − 1 γ − γ2 γ − α , and multiplying by ( γ − α) > 0 (recall that α < γ) shows G′(α) has the same sign as the quadratic H(α) := (γ − α)G′(α) = (2α − 1)(γ − α) − γ2(γ − α) log 1 − 1 γ − γ2 = −2α2 + 1 + 2γ + γ2 log 1 − 1 γ α − γ 1 + γ + γ2 log 1 − 1 γ . We define the discriminant to be ∆H = 1 + 2γ + γ2 log 1 − 1 γ 2 − 8γ 1 ...

work page 2017

[6] [12]

The first case (when γ ≤ τ ) trivially satisfies this

log (1− 1/α) − log(α) α − 1 . The first case (when γ ≤ τ ) trivially satisfies this. However, for the second case (whenever γ > τ), this is satisfied only if eη2 + λmin(X ⊤X) ≥ γ, which by using the inequality eη2 + λmin(X ⊤X) = γ − λmin(X ⊤X) + ηC2 X τ − ηC2 X z + λmin(X ⊤X) = γ + ηC2 X τ − ηC2 X z corresponds to having z ≥ τ (we note that the case eλ = ...

work page 2014

[7] [13]

H Algorithms: Linear Regression H.1 AdaSSP Algorithm 3 AdaSSP [Wang, 2018] Input: Dataset (X, Y); Privacy parameters ε, δ; Bounds: max i∈[n] ∥xi∥2 ≤ C2 X , max i∈[n] |yi|2 ≤ C2 Y

When we take χ ≪ 1, the bound acquires an extra 2 q term in the excess empirical risk relative to the bound obtained in the linear regression case, introduced by the polynomial approximation. H Algorithms: Linear Regression H.1 AdaSSP Algorithm 3 AdaSSP [Wang, 2018] Input: Dataset (X, Y); Privacy parameters ε, δ; Bounds: max i∈[n] ∥xi∥2 ≤ C2 X , max i∈[n]...

work page 2018

[8] [14]

1: Compute λmin := λmin((X, Y)⊤(X, Y))

Algorithm 4 Sheffet’s Algorithm [Sheffet, 2017, Algorithm 1] Input: Dataset ( X, Y); Privacy parameters ε, δ; Bounds: max i∈[n] ∥xi∥2 ≤ C2 X , max i∈[n] |yi|2 ≤ C2 Y ; Hyperparameter k. 1: Compute λmin := λmin((X, Y)⊤(X, Y)). 2: Set γ ← 4(C2 X +C2 Y ) ε q 2k log 8 δ + 2 log 8 δ . 3: Sample S ∼ N (0, Ik×n). 4: if λmin > γ+ z + 4(C2 X +C2 Y ) log(1/δ) ε for...

work page 2017