Differential Privacy of Gradient Descent on Perturbed Objectives

Differential Privacy of Gradient Descent on Perturbed Objectives

arXiv:2610.02716v1 [cs.LG] 2 Oct 2026

Austin Watkins Johns Hopkins University Baltimore, MD 21218 awatki29@jhu.edu

Raman Arora Johns Hopkins University Baltimore, MD 21218 arora@cs.jhu.edu

Abstract Objective perturbation adds a random linear term to a regularized empirical risk and releases the exact perturbed minimizer. We study the finite computation obtained by releasing the N th iterate of deterministic gradient descent on w 7→ F (w; S) + ⟨z, w⟩, where z ∼ N (0, σ 2 Id ) is drawn once before optimization. For strongly convex and smooth objectives with Lipschitz Hessian, we prove an explicit condition under which the map z 7→ wN is a C 1 -diffeomorphism on the bounded domains used in the privacy argument, with a quantitative lower bound on the smallest singular value of its Jacobian. This permits a direct change-of-variables analysis of the finite iterate. For generalized linear models, the resulting privacy-profile bound has no explicit ambient-dimension factor once the iteration condition holds, and its finite-iteration correction decreases geometrically. By letting the free truncation parameter grow slowly with N , we recover the corresponding exact-minimizer certificate in the limit. We also bound the expected excess empirical risk by dσ 2 /(2µ) plus a geometrically decreasing optimization term, and transfer the result to population risk without an additional multiplicative condition-number factor in the leading statistical terms.

1

Introduction

Objective perturbation is one of the earliest mechanisms for differentially private empirical risk minimization (ERM): draw a random vector z, add the linear term ⟨z, w⟩ to a regularized empirical objective, and release its minimizer [Chaudhuri and Monteleoni, 2008, Chaudhuri et al., 2011]. Its appeal is structural as well as algorithmic. Randomness is injected once, before optimization, and for generalized linear models (GLMs) the privacy analysis can avoid an explicit dependence on the ambient dimension. Modern analyses have sharpened the privacy accounting and computational treatment of the exact objective-perturbation mechanism [Redberg et al., 2023]. The classical privacy proof, however, is tied to the exact perturbed minimizer. If  w∗ (z) ∈ arg min F (w; S) + ⟨z, w⟩ , w

then the first-order condition ∇F (w∗ (z); S) + z = 0 recovers the perturbation from the released point and enables a change-of-variables argument. A numerical optimizer instead produces a finite iterate. Existing approaches to this gap typically certify an approximate solution by adding a second randomization at release, as in Approximate Minima Perturbation (AMP) [Iyengar et al., 2019] and Approximate Objective Perturbation [Bassily et al., 2019], or inject noise throughout the optimization and analyze the resulting noisy iteration [Bassily et al., 2014, Feldman et al., 2018, Chourasia et al., 2021, Altschuler et al., 2024]. Quadratic objective perturbation has recently provided a different perturbation mechanism, including guarantees for inexact solves under its own assumptions [Cortild and Cartis, 2026]. 1

Can we instead certify a useful finite gradient-descent iterate using only the original linear objective perturbation, without per-step noise or an additional output perturbation? We seek a privacy guarantee that approaches the corresponding exact-minimizer guarantee as optimization converges. We answer this question for gradient descent on strongly convex, smooth GLM objectives with Lipschitz Hessian. Draw z ∼ N (0, σ 2 Id ) once, run
wk+1 = wk − η ∇F (wk ; S) + z , from the fixed initialization w0 = 0, and release wN . To analyze the privacy of this release, we study the finite-time map MS : z 7−→ wN instead of the exact-minimizer map z 7→ w∗ (z). Differentiating with respect to the perturbation gives sums of ordered products of curvature matrices evaluated along the optimization trajectory. These matrices need not commute, so controlling the Jacobian requires accounting for their ordered products. We compare the Jacobian with a frozen-Hessian recursion and obtain an explicit condition under which MS is a C 1 -diffeomorphism on the bounded convex domains used in the privacy proof, with a uniform lower bound on the smallest singular value of its Jacobian. We develop this comparison in Section 4.2. Once this inverse is available, the classical change-of-variables argument can be applied at finite time. At a shared output, the privacy loss separates into a Gaussian density ratio between the two perturbation preimages and a ratio of Jacobian determinants. For GLMs, the gradient difference between neighboring datasets lies in the span of the two differing feature vectors, and Hessian perturbations are sums of controlled rank-one matrices. These two properties remove an explicit ambient-dimension factor from the privacy bound. The finite-iteration corrections vanish as N → ∞; we may let the free truncation radius grow slowly with N while these corrections still vanish, giving the corresponding exact-minimizer certificate in the limit (Remarks 4.6 and C.16). Contributions. • A composition-free privacy certificate for the released iterate (Theorem 4.1). We derive an explicit upper bound on the privacy profile of S 7→ MS (Z). For every ϵ ≥ ϵ0 , the release is (ϵ, δ(ϵ))-differentially private, with 2

δ(ϵ) ≤ e−u /2 +

q

2 G −σ 2 (ϵ−ϵ0 )2 /(2G2 ) , π σ e

ϵ0 =

 G2 ∆H  + cN , + log 1 + 2σ 2 2nµ

where u controls the truncation probability, G is the neighboring-dataset gradient sensitivity, ∆H is the Hessian scale defined in Section 3.1, and cN ≥ 0 contains finite-iteration corrections that decay geometrically. Once the explicit threshold (7) is satisfied, the displayed privacy budget has no explicit dependence on the ambient dimension. When we solve the sufficient condition for N , d appears only through d⋆ = min{d, n + 1} inside a logarithm. • Quantitative invertibility of the finite-time perturbation map (Corollary 4.4). We compare the Jacobian recursion for MS with a frozen-Hessian recursion that can be solved in closed form. From this comparison we obtain an explicit negative-definiteness margin for the symmetric part of the true Jacobian. We then use that margin to prove global injectivity and a uniform lower bound on the smallest singular value over the truncation domains used in the privacy proof. 2

• Utility with an explicit finite-optimization correction (Theorems 4.7 and 4.10). The expected excess empirical risk satisfies the standard objective-perturbation term dσ 2 /(2µ) plus an optimization correction Eopt (N ) that decays geometrically. For GLMs, a uniformconvergence argument transfers this to population risk without an additional multiplicative condition-number factor in the leading statistical terms. In particular, for every comparator w̄, with probability at least 1 − δS over the sample, √ √ √ p  
Lℓ  Ez R0 (wN ) − R0 (w̄) ≤ ∥w̄∥ 2 σ d + 32 + 4 2 log(1/δS ) √ + 2 Eopt (N ). n The high-probability statement here is over the sample; the displayed risk is averaged over the perturbation. Our result gives a finite-trajectory change-of-variables certificate for ordinary deterministic gradient descent after a single objective perturbation. This complements analyses of the exact minimizer [Chaudhuri et al., 2011, Kifer et al., 2012, Redberg et al., 2023], approximate solves followed by output noise [Iyengar et al., 2019, Bassily et al., 2019], quadratic objective perturbation with inexact solves [Cortild and Cartis, 2026], and noisy iterative algorithms [Bassily et al., 2014, Feldman et al., 2018, Chourasia et al., 2021, Altschuler et al., 2024]. Section 3 presents the notation, assumptions, and mechanism; Section 4 states the main results with proof sketches; and Section 5 compares the guarantee with objective perturbation and composition-free analyses of noisy iterations and discusses computational cost. Complete proofs are given in Appendices A to D.

2

Related work

We relate our results to four lines of work: objective perturbation, private optimization by gradient perturbation, composition-free privacy analyses of noisy iterations, and invertibility results for gradient methods. Objective perturbation. Chaudhuri and Monteleoni [2008] introduced objective perturbation for logistic regression, and Chaudhuri et al. [2011] developed the regularized-ERM analysis for GLMs. The mechanism adds a random linear term ⟨z, w⟩ to the empirical objective and releases the exact perturbed minimizer. Kifer et al. [2012] extended the mechanism to approximate differential privacy by using Gaussian noise and nondifferentiable regularizers via a limit argument and smooth approximation. Regarding the dimensional utility cost, Jain and Thakurta [2014] showed that unconstrained GLMs with strongly convex regularization admit excess risk with no explicit dependence on d, controlled instead by the norms of the risk minimizer and the data. These exact-minimizer guarantees leave a numerical-certification question when optimization is stopped at finite accuracy. Approximate Minima Perturbation (AMP), introduced by Iyengar et al. [2019], addresses this by obtaining an approximate minimizer, measured by its gradient norm, on the perturbed (and additionally regularized) objective and then adding Gaussian output noise to certify the released point. Similar to the approximation scheme above, Bassily et al. [2019] show that stochastic variance-reduced gradient descent (SVRG) on the perturbed objective followed by the Gaussian mechanism attains the optimal population loss in O(n log n) gradient evaluations. If the domain is discrete, Neel et al. [2020] show that only boundedness of the loss is sufficient for privacy in the constrained setting via a modified algorithm that normalizes candidates onto a sphere in one higher dimension. They also provide a continuous-domain algorithm requiring boundedness and Lipschitz continuity, with a d5/4 factor in its stated utility bound. 3

Redberg et al. [2023] provide the modern privacy accounting baseline for objective perturbation, developing tighter analyses through privacy profiles and Rényi differential privacy and treating both exact objective perturbation and AMP. They emphasize that the perturbation and released minimizer are dependent random variables and show that, without GLM structure, objective perturbation can incur dimension-dependent privacy terms. Cortild and Cartis [2026, v2] study random quadratic objective perturbation under smoothness and Hessian-rank assumptions, together with a bounded-diameter condition on the per-sample gradients at a publicly known, data-independent point. Interpolation is one special case of this condition. For inexact solves, they add Gaussian output noise calibrated to the optimization error. Gradient perturbation and private optimization. Bassily et al. [2014] established optimal rates for constrained differentially private empirical risk minimization (DP-ERM) via noisy stochastic gradient descent (DP-SGD) run for T √ = n2 steps and accounted per step through amplie d/(nϵ)) excess empirical risk for Lipschitz convex fication by sampling and strong composition: Θ( e losses under (ϵ, δ)-differential privacy, and Θ(d/(n2 ϵ2 )) under strong convexity.1 In follow-up work, Bassily et al. [2019] characterize the optimal private stochastic convex optimization rate, up to logarithmic factors, √ for convex Lipschitz losses; in the standard Euclidean setting the rate has the √ form O(1/ n + d/(ϵn)). Song et al. [2021] sharpened the picture for gradient perturbation with rank-based rates and the first lower bound for unconstrained ERM. Composition-free privacy for iterative methods. A separate line of work keeps the per-step noise of DP-SGD but only releases the final iterate. Privacy amplification by iteration [Feldman et al., 2018] provides utility and bounded Rényi differential privacy for noisy SGD on smooth convex Lipschitz losses with a random stopping time. Altschuler et al. [2024] gave a tight analysis of the same method, showing that the privacy loss need not grow with the iteration count for projected noisy SGD on smooth convex Lipschitz losses over a bounded domain. Bok et al. [2024] recast amplification by iteration in f -differential privacy, which yields an exact characterization for strongly convex losses and covers constrained and unconstrained, full-batch, cyclic, and stochastic variants alike. Under a quantified logarithmic Sobolev inequality, a tight last-iterate analysis was provided by Chourasia et al. [2021], which shows the Rényi privacy loss saturates exponentially in the iteration count for smooth and strongly convex loss functions. Ye and Shokri [2022] carry the hidden-state analysis to mini-batch gradient descent, in shuffle-and-partition and sample-withoutreplacement schemes, folding in amplification by subsampling, with bounds that again converge exponentially fast. Chien and Li [2025] significantly extend the generality of hidden-state noisySGD by showing that over a bounded domain, a Hölder-continuous gradient alone suffices for a convergent Rényi bound, with a strictly better bound in the smooth strongly convex case. Brown et al. [2024] show that for linear regression an explicit law of the iterates can be obtained; privacy itself is still accounted per step. Diffeomorphisms in optimization. Daskalakis and Panageas [2018] prove that the gradient descent–ascent update is a local diffeomorphism whenever the step size satisfies α < 1/L, and likewise its optimistic variant; this is what admits the Center-Stable Manifold Theorem, from which they conclude that the dynamics avoid unstable critical points from almost every initialization. For a fixed objective, Bolte et al. [2026] show that the k-step gradient-descent map from the initialization w0 to the final iterate is a global diffeomorphism when the step size satisfies α < 1/L, 1 Here and in Section 5.2, the rates are stated after accounting for the normalizing factor of n that gives the average of the per-sample losses, as in (1), instead of Bassily et al.’s sum.

4

under their stated regularity assumptions. Our change-of-variables argument uses a different map: we fix the initialization and vary the perturbation z. Differentiation with respect to w0 gives a product of the single-step factors I − α∇2 g, whereas differentiation with respect to z gives the affine recursion (5), which adds −ηI at every step. We therefore need quantitative invertibility for the map z 7→ wN rather than for the initialization map.

3

Setup

3.1

Notation and assumptions

We equip Rd with the Euclidean inner product ⟨·, ·⟩ and the induced norm ∥ · ∥. For a matrix A, the symbol ∥A∥ denotes the spectral (operator) norm, ∥A∥∗ the nuclear (trace) norm, and σmin (A) the smallest singular value. We write Asym := 12 (A + A⊤ ) for the symmetric part of A; it satisfies ⟨Av, v⟩ = ⟨Asym v, v⟩ for every v ∈ Rd and ∥Asym ∥ ≤ ∥A∥. For symmetric matrices we write A ⪯ B to mean that B − A is positive semidefinite, and I denotes the identity. We work with regularized generalized linear models. Each sample is a pair (xi , yi ) consisting of a feature vector xi ∈ Rd and a label yi ; a dataset collects n samples into a tuple S = ((x1 , y1 ), . . . , (xn , yn )), and two datasets are neighboring if one is obtained from the other by replacing at most one sample. We write neighboring datasets as S and S ′ = ((x1 , y1 ), . . . , (xn−1 , yn−1 ), (x′n , yn′ )), placing the differing sample last, abbreviate FS (·) := F (· ; S), and take the regularized empirical risk to be n
µ 1X FS (w) = ℓ ⟨xi , w⟩, yi + ∥w∥2 , (1) n 2 i=1

where the loss ℓ is twice continuously differentiable in its first argument. Let C := span{x1 , . . . , xn−1 , xn , x′n },

dim C ≤ d⋆ := min{d, n + 1},

(2)

carry every feature either dataset holds; it is the same subspace for S and S ′ . The guarantee is stated with the upper bound d⋆ , which is fixed by d and n alone. We impose the following structural conditions. Assumption 1 (Bounded features). ∥xi ∥ ≤ ζ for every feature vector appearing in S or S ′ . Assumption 2 (Bounded loss derivatives). |ℓ′ (t, y)| ≤ L1 and 0 ≤ ℓ′′ (t, y) ≤ L2 for all t, y, so in particular each per-sample loss is convex in its first argument. Assumption 3 (Lipschitz second derivative of the loss). |ℓ′′ (s, y) − ℓ′′ (t, y)| ≤ L3 |s − t| for all s, t, y. The logistic loss satisfies Assumptions 2 and 3. Assumptions 1 and 2 make every FS in (1) µ-strongly convex and L-smooth for any L ≥ µ+L2 ζ 2 , uniformly in S (Lemma B.1); Assumptions 1 and 3 make the Hessian M -Lipschitz for any M ≥ L3 ζ 3 (Lemma B.2); writing ∆H := 2L2 ζ 2 , Assumptions 1 and 2 further bound the rank-one Hessian term a single sample contributes by L2 ζ 2 /n = ∆H /(2n), in operator and nuclear norm alike, the two coinciding on a rank-one matrix. Finally, the first-derivative bound of Assumption 2 bounds the per-sample gradient by Lℓ := L1 ζ, the gradient sensitivity between neighboring datasets by P G := 2L1 ζ/n (Appendix B), and the gradient at the origin by ∥∇FS (0)∥ = ∥ n1 i ℓ′ (0, yi ) xi ∥ ≤ L1 ζ, uniformly in S. For the utility results, the samples are n independent draws from a distribution D, with the feature bound of Assumption 1 holding D-almost surely. The population risk is Rµ (w) := 5

  E(x,y)∼D ℓ(⟨x, w⟩, y) + µ2 ∥w∥2 , and it inherits µ-strong convexity and L-smoothness by the same computation; R0 is the unregularized population risk. We write w∗ := argminw Rµ (w) for its minimizer and wS∗ := argminw FS (w) for the empirical minimizer. In the main text we work with regularized GLMs. For the diffeomorphism argument itself, we use only strong convexity, smoothness, and a Lipschitz Hessian (Appendix A.1). GLM structure enters when we obtain the dimension-free privacy bound and when we transfer the utility guarantee to population risk (Section 5.2). A randomized mechanism M, mapping a dataset S to a random output MS (Z), is (ϵ, δ)differentially private if Pr[MS (Z) ∈ E] ≤ eϵ Pr[MS ′ (Z) ∈ E] + δ for every ordered pair of neighboring datasets (S, S ′ ) and every Borel E ⊆ Rd . At each ϵ ≥ 0 the smallest such δ is the hockey-stick divergence, maximized over neighboring pairs: Z  S
′ p − e ϵ pS + , (3) δM (ϵ) := sup sup Pr[MS (Z) ∈ E] − eϵ Pr[MS ′ (Z) ∈ E] = sup S,S ′

S,S ′

E

′

the last expression valid when the output laws have densities pS , pS . The map ϵ 7→ δM (ϵ) is the privacy profile of the mechanism [Balle et al., 2018].

3.2

The mechanism

Fix a step size η with 0 < η ≤ 1/L and ηµ < 1; as 1/L ≤ 1/µ, the second condition excludes only the endpoint η = 1/µ, and only when µ = L. Given a perturbation z ∈ Rd , we run gradient descent on the perturbed objective w 7→ F (w) + ⟨z, w⟩ from the origin, w0 = 0:
wk+1 = wk − η ∇F (wk ) + z . (4) For a fixed number of iterations N ≥ 1, the mechanism M : Rd → Rd is the map M(z) := wN . ′ When emphasizing the dataset we write MS , MS ′ for the mechanisms and wkS , wkS for the iterates under S and S ′ . We write κ := L/µ for the condition number. For the main privacy certificate, the sufficient count in (7) is 2κ log(·) at η = 1/L, with a logarithmic argument polynomial in n, d⋆ , and the problem constants. Since F ∈ C 2 , each iterate wk is continuously differentiable in z. Writing Jk := ∂wk /∂z and Ak := I − η∇2 F (wk ), differentiation of (4) gives Jk+1 = Ak Jk − ηI,

J0 = 0,

(5)

so that ∇M(z) = JN . The matrix Ak is symmetric because ∇2 F (wk ) is, and its eigenvalues lie in [1 − ηL, 1 − ηµ]; since ηL ≤ 1 that interval sits in [0, ρ] with ρ := 1 − ηµ ∈ (0, 1), so Ak ⪰ 0 and ∥Ak ∥ ≤ ρ.

4

Main results

We first state the privacy guarantee, then the quantitative invertibility result used in its proof, and finally the utility bounds for the released iterate.

4.1

Privacy

The classical privacy analysis of objectiveperturbation is a change-of-variables argument anchored to the exact minimizer w∗ (z) := argminw F (w) + ⟨z, w⟩ of the tilted objective (Lemma A.2): the 6

optimality condition ∇F (w∗ (z)) + z = 0 inverts the map z 7→ w∗ (z) in closed form, and from this inverse the ratio of output densities under neighboring datasets factors into a noise-density ratio and a ratio of Jacobian determinants [Chaudhuri et al., 2011, Redberg et al., 2023]. For a finite iterate wN , this exact optimality-condition inverse is unavailable. Once M : z 7→ wN is certified as a diffeomorphism on a suitable domain (Section 4.2), the output density at y = M(z) is pZ (z)/| det JN (z)| by the change of variables, and the privacy loss at an output attained under both datasets, with preimages zS and zS ′ , splits into two terms: ′

log

S (z ′ )| pSY (y) | det JN pZ (zS ) S = log , + log ′ S (z )| pZ (zS ′ ) | det JN pSY (y) S | {z } | {z } Gaussian ratio

(6)

Jacobian ratio

where pZ is the noise density, pTY the output density under dataset T restricted to the domain T its Jacobian at the corresponding preimage; the version with the domain of invertibility, and JN bookkeeping explicit is (23) in Appendix C. We apply the change-of-variables argument on two nested balls in the feature span C of (2). By Lemma B.6, the C ⊥ component follows the same affine recursion under both neighboring datasets and cancels 0 = {z ∈ C : ∥z∥ ≤ ru } with √ from the privacy loss. For a free parameter u ≥ 0, let Ω−u 2 ru = σ( d⋆ + u). Gaussian concentration gives Pr(∥ΠC Z∥ > ru ) ≤ e /2 . We also use the larger ball Ω′ = {z ∈ C : ∥z∥ ≤ r′ } with r′ = ru + 2LG/µ. Under (7), every output produced from Ω0 has the required MS ′ -preimage in Ω′ ; Appendix C.3 proves this by path lifting. Increasing u reduces the truncation probability and changes the required iteration count only through the logarithm in (7). Theorem 4.1 (Differential privacy of gradient descent on perturbed objectives). Let Assumptions 1 to 3 hold, and let the step size satisfy 0 < η ≤ 1/L and ηµ < 1 (Section 3.2). Fix u ≥ 0 and set ru := σ

p
d⋆ + u ,

r′ := ru +

2LG , µ

R̄ :=

r ′ + L1 ζ , µ

together with B := 1/µ (item 2 of Lemma A.9). Suppose the iteration count satisfies n 2µR̄ r′ o 2 8LM B R̄ log max , , 4 . ηµ Gσ eρµ min{1, M G/L}

(7)

 eηµ ∆H  τ ⋆ := log 1 + + min{1, M G/L} N ρN/2 , 2nµ 2

(8)

N≥ Writing

and setting ϵ0 :=

2 G N/2 G2 ρ + 2 1 + ρN/2 + τ ⋆ , σ 2σ

(9)

the mechanism S 7→ MS (Z) with Z ∼ N (0, σ 2 Id ), σ > 0, is (ϵ, δ(ϵ))-differentiallyR private for every ∞ ϵ ≥ ϵ0 , where, for a standard Gaussian W , we define the integrated tail Q1 (t) := t Pr(W > s) ds, 2

δ(ϵ) = e−u /2 +

σ  2G Q1 (ϵ − ϵ0 ) , σ G

(10)

an explicit upper bound on the privacy profile (3). Once (7) holds, the displayed privacy budget has no explicit dependence on the ambient dimension. In the sufficient condition for N , the dimension appears only through d⋆ = min{d, n + 1}. 7

Over the range covered by (7), we obtain ϵ0 ↓ G2 /(2σ 2 ) + log(1 + ∆H /(2nµ)) as N → ∞. The Gaussian-ratio calculation gives the first two contributions in (9), and the log-determinant calculation gives τ ⋆ . Since G = 2L1 ζ/n (Lemma B.5), the limiting expression decreases with the sample size for fixed problem parameters. The sufficient iteration count depends on dimension only through d⋆ = min{d, n + 1} inside a logarithm. We choose the third condition in (7) so that N ρN/2 decreases over the stated range. Remark C.16 gives the exact-minimizer limit of the full certificate, including the truncation contribution to δ. Remark 4.2 (The iteration threshold). We use the three entries in (7) for three estimates: to bound the finite-time inversion residual in the Gaussian-ratio calculation, to make the Jacobian error smaller than the spectral floor of the frozen-Hessian reference, and to restrict attention to the range where N ρN/2 is decreasing. The second estimate also gives the uniform inverse-Jacobian bound used on the truncation domain. In that estimate, we retain the factor min{1, M G/L} to bound the determinant correction by a quantity proportional to G when M G/L ≤ 1, while capping the coefficient at one. Proof sketch of Theorem 4.1. We condition on perturbations in Ω0 and charge the Gaussian mass outside that ball to δ. For an output produced from Ω0 , we lift the segment from MS ′ (zS ) to the shared output through M−1 S ′ . The inverse-Jacobian bound controls the speed of this lift by G(1 − ρN )/(µαΩ′ ), and the choice of r′ keeps the lifted path inside Ω′ . The change-of-variables formula then separates the privacy loss into the Gaussian ratio and the Jacobian ratio in (6). We integrate the remaining one-dimensional Gaussian projection directly in the hockey-stick divergence 2 (Lemma C.12), while the truncation event contributes e−u /2 to δ. For the Gaussian ratio, Lemma C.1 gives z = −∇F (wN ) + ξ with ∥ξ∥ ≤ ρN ∥∇F (0) + z∥. Hence the two preimages of a shared output differ by the neighboring-dataset gradient difference plus a residual of order ρN (Corollary C.2). In a GLM, that gradient difference lies in span{xn , x′n }, so the leading random contribution depends only on the two scalar projections ⟨Z, xn ⟩ and ⟨Z, x′n ⟩. We bound the residual contribution in Theorem C.4. For the Jacobian ratio we use the frozen-Hessian determinant comparison summarized in Section 4.2 and proved in Theorem C.9. Remark 4.3 (Initialization). We state Theorem 4.1 for w0 = 0. The same argument applies to any fixed public initialization after replacing the trajectory-scale constants by their values at that point. For a public w0 , bounded per-sample gradients give sup ∥∇FS (w0 )∥ ≤ L1 ζ + µ∥w0 ∥, S

R̄w0 :=

r′ + L1 ζ + µ∥w0 ∥ = R̄ + ∥w0 ∥. µ

We use R̄w0 in place of R̄ in (7). In the optimization correction (12), we use aR = ∥∇FS (w0 )∥/µ and retain bR = 1/µ. Dependence on the perturbation is different: a start w0 = αz can destroy privacy for every α > 0. Take the linear loss ℓ(t, y) = −ty with labels y ∈ {±1}, which satisfies Assumptions 2 and 3 with L1 = 1 and ℓ′′ ≡ 0, so that (1) reads FS (w) = µ2 ∥w∥2 + ⟨bS , w⟩ with P bS := − n1 ni=1 yi xi , and every dataset gives the Hessian µI. For this instance we may take L = µ. At the step size η = (1 − (1 + αµ)−1/N )/µ, admissible at every N , the perturbation carried by the start and the perturbation carried by the minimizer w∗ (z) = −(bS + z)/µ cancel exactly in wN = a w0 + (1 − a) w∗ (z) at a = 1/(1 + αµ): the release is the deterministic wN = −αbS /(1 + αµ), neighboring datasets differ in bS , and two distinct point masses admit no (ϵ, δ)-differential privacy with δ < 1. For α ≤ 0 the cancellation has no admissible step size at any N .

8

4.2

The map is a diffeomorphism

Fix a bounded convex domain D. To prove quantitative invertibility on D, we compare the true Jacobian with a frozen-Hessian recursion. Set H ∗ := ∇2 F (wN ) and A∗ := I − ηH ∗ . Replacing the iterate-dependent curvature matrices by A∗ gives a recursion whose solution J˜N is explicit. Unrolling (5) from J0 = 0 gives JN = −ηSN ,

SN :=

N −1 X

AN −1 AN −2 · · · AN −j ,

(11)

j=0 sym where the j = 0 term is I. A lower bound on SN gives both injectivity on a convex domain and a lower bound on the smallest singular value. Products of distinct positive semidefinite curvature factors need not be symmetric, and their symmetric parts can have negative eigenvalues. Since AN −1 ⪰ 0 and ∥AN −1 · · · AN −j ∥ ≤ ρj , a direct norm estimate gives   N −1 X sym ⪰ 1 − SN ρj  I. j=2

This estimate gives a uniform positive floor only when ρ2 /(1 − ρ) < 1. The frozen-Hessian comparison uses the contraction of the trajectory to obtain a positive floor for all sufficiently large N under the standing assumptions. We quantify the comparison using the frozen-Hessian spectral floor γN = (1 − (1 − ηL)N )/L and the Jacobian error. If RD := supz∈D ∥∇F (0) + z∥/µ and CD := Proposition A.11 P ηM RD /µ,Nthen −k N −1 ˜ gives ∥JN − JN ∥ ≤ CD ν̃N ρ uniformly on D, where ν̃N = k<N (1 − ρ )(1 − ρk ) ≤ N . We N −1 therefore obtain the margin αD := γN − CD ν̃N ρ . Since γN → 1/L and ν̃N ρN −1 → 0, this margin is positive for all sufficiently large N . Corollary 4.4 (Diffeomorphism onto the image). Let F : Rd → R be twice continuously differentiable, µ-strongly convex, and L-smooth, with an M -Lipschitz Hessian. With step size 0 < η ≤ 1/L and ηµ < 1 (Section 3.2), let D ⊂ Rd be a bounded convex open set with αD > 0. Then M(D) is open and M : D → M(D) is a C 1 -diffeomorphism. Proof sketch of Corollary 4.4. The frozen recursion has the closed form J˜N = −(H ∗ )−1 (I −(A∗ )N ). In an eigenbasis of H ∗ , its eigenvalues are −(1 − (1 − ηhi )N )/hi for hi ∈ [µ, L] (Lemmas A.8 and A.9). Hence J˜N is negative definite for every N ≥ 1, with smallest singular value at least γN = (1 − (1 − ηL)N )/L. As N → ∞, wN → w∗ (z) and J˜N → −(H ∗ )−1 , which is the derivative of the exact-minimizer map obtained from its optimality condition. Using the Lipschitz Hessian and the contraction of gradient descent, we bound the deviation from the frozen-Hessian recursion by ∥JN − J˜N ∥ ≤ C(z)ν̃N ρN −1 with ν̃N ≤ νN ≤ N (Proposisym tion A.11). Since J˜N is symmetric and negative definite, the same estimate gives JN ⪯ −αD I on D (Theorem A.12). Integrating this inequality along a line segment proves global injectivity (Theorem A.13), while ∥JN v∥ ≥ |⟨JN v, v⟩| gives σmin (∇M) ≥ αD > 0. Together these facts give the C 1 -diffeomorphism in Corollary 4.4. T = p (H ∗ ) denote the frozen-Hessian Jacobian up Proof sketch of Theorem C.9. Let PNT = −J˜N N T T T T . Feasibility gives a uniform bound to sign, and write −JN = PN (I − ΨT ) with ΨT = (PNT )−1 δN ∥ΨT ∥ < 1, so the determinant separates into a frozen-Hessian factor and a finite-N error factor. At a shared output, the two frozen reference Hessians are evaluated at the same point. Each has the common contribution from the regularizer and the n − 1 shared samples, plus one rank-one

9

term from the differing sample. Writing ϕN = log pN , Lemma C.5 shows that ϕ′N (h) = −gN (h)/h with 0 ≤ gN (h) ≤ ḡN . The common-anchor rank-one comparison in Lemma C.6 then gives   det PNS ∆H . log ′ ≤ ḡN log 1 + 2nµ det PNS ′

S and δ S using the rankFor the finite-N factors, Lemma B.4 bounds the nuclear norms of δN N one GLM Hessian structure. Applying log | det(I + K)| ≤ ∥K∥∗ and the inverse bound supplied by feasibility gives the correction τ (corr) in Definition C.8. Adding the frozen-Hessian and finite-N contributions yields (42).

Remark 4.5 (Common-anchor determinant comparison). At a shared output, write HS∗ = H0 + uu⊤ and HS∗ ′ = H0 + u′ u′⊤ , where H0 ⪰ µI contains the regularizer and the n − 1 shared samples. The matrix determinant lemma compares each Hessian with the same H0 . Since each rank-one addition changes the relevant log determinant by a value in an interval of length log(1 + ∆H /(2nµ)), the difference between the two log determinants has absolute value at most that same quantity. This is the common-anchor calculation used in Lemma C.6. Remark 4.6 (Classical determinant slack). As N → ∞, both τ in Theorem C.9 and τ ⋆ in (8) converge to log(1 + ∆H /(2nµ)); see Remark C.16. In the notation of Chaudhuri et al. [2011], their determinant calculation gives 2 log(1 + ∆H /(2nµ)): their curvature bound c corresponds to L2 ζ 2 = ∆H /2, and their regularization strength Λ corresponds to µ in the branch with no additional regularization. The common-anchor calculation in Remark 4.5 yields the single logarithmic factor above.

4.3

Utility

We compare the unregularized population risk of the released iterate with that of an arbitrary comparator. The bound includes the comparator’s regularization term and holds for every N ≥ 1. The same finite-optimization correction appears throughout this subsection, √
√
L 2N 2 2 ρ bR dσ + 2aR bR σ d + a2R + ρN bR dσ 2 + aR σ d , 2 ∥∇F (0; S)∥ 1 aR := , bR := . µ µ

Eopt (N ) :=

(12)

Stopping after N steps introduces the correction in (12). The distance to the perturbed minimizer decreases as ρN , which produces the ρ2N smoothness term and the ρN inner-product term involving the residual gradient −z. Thus Eopt (N ) decreases geometrically with N . Theorem 4.7 (Unregularized excess risk). Under Assumptions 1 to 3, let z ∼ N (0, σ 2 Id ) and let wN be the output of (4). Then for every comparator w̄ ∈ Rd , with probability at least 1 − δS over S, h dσ 2 i 16 L2 32 + log(1/δ )
µ   S ℓ + Eopt (N ) + + ∥w̄∥2 . Ez R0 (wN ) − R0 (w̄) ≤ 2 2µ µn 2 Proof. Since R0 = Rµ − µ2 ∥ · ∥2 , at every realization of z,   µ   µ µ R0 (wN ) − R0 (w̄) = Rµ (wN ) − Rµ (w̄) − ∥wN ∥2 + ∥w̄∥2 ≤ Rµ (wN ) − Rµ (w∗ ) + ∥w̄∥2 , 2 2 2 dropping − µ2 ∥wN ∥2 ≤ 0 and using Rµ (w̄) ≥ Rµ (w∗ ), since w∗ minimizes Rµ . Taking Ez and applying Theorem 4.9 on its event bounds the first bracket and gives the claim. 10

For the algebraic comparison below, fix the noise scale σ and optimize the public regularization coefficient µ. We evaluate the privacy certificate at the selected value of µ; choosing that value from public information requires no separate composition step. This choice incurs no additional privacy loss. For a prescribed target (ϵ, δ), however, µ, σ, and N are coupled through Theorem 4.1 and should be calibrated jointly. We give an
explicit joint choice in Corollary 4.13. Writing A := dσ 2 + 16L2ℓ 32 + log(1/δS ) /n, the right side equals A/µ + µ2 ∥w̄∥2 up to the geometrically decaying 2 Eopt (N ). Ignoring that √optimization correction for √ this algebraic comparison, the expression is minimized over µ at µ = 2A/∥w̄∥, with value ∥w̄∥ √ 2A, the sample-complexity √ √ form in which Chaudhuri et al. [2011] state their guarantee. Applying a + b ≤ a + b twice, p √ √ √ √ √ √ √ √ p

√ √ 2A ≤ 2 σ d + 4 2 32 + log(1/δS ) Lℓ / n = 2 σ d + 32 + 4 2 log(1/δS ) Lℓ / n, the form displayed among the contributions. Example 4.8. For a numerical illustration, take regularized logistic regression with features normalized to ζ = 1, sample size n = 106 , dimension d =√104 , and regularization µ = 10−2 . The loss constants are L1 = 1, L2 = 1/4, and L3 = 1/(6 3), so L = µ + L2 ζ 2 = 0.26, κ = 26, G = 2/n = 2 × 10−6 , and ∆H = 1/2 (Section 3.1). Run the mechanism at step size η = 1/L, noise scale σ = 5G = 10−5 , and truncation parameter u = 6. The threshold (7) evaluates to N ≥ 1319, and we run N = 1500: a cost of nN = 1.5 × 109 individual-gradient evaluations, or 1500 full-batch passes. At that count the finite-N corrections are negligible: ρN/2 = 1.7 × 10−13 , so the floor (9) is its G2 ⋆ = 0.0200 + 2.5 × 10−5 . At budget ϵ = 1 the certified limit to the displayed digits, ϵ0 = 2σ 2 + τ −8 profile (10) evaluates to δ(1) = 5.16 × 10 (truncation mass e−18 = 1.52 × 10−8 plus divergence term 3.64 × 10−8 ), so the release is (1, 10−7 )-differentially private with room to spare. With the same (σ, N ), the utility bound gives Eopt (N ) ≤ 3 × 10−27 , perturbation cost dσ 2 /µ = 10−4 , and sample term 16L2ℓ (32 + log 100)/(µn) = 0.0586 at δS = 10−2 . With probability 0.99 over the sample, the expected excess risk of the released point is at most 0.059; the zero predictor has risk log 2 ≈ 0.69. Using Theorem 4.7, we also obtain an unregularized excess-risk bound of 0.064 relative to every unit-norm comparator. We can also evaluate the more precise certificate of Theorem C.13 with the same public radii r = ru and r′ = ru + 2LG/µ. For these radii, the first integer that certifies (1, 10−7 ) privacy is N = 519. The comparison is Certificate Theorem 4.1, smallest admissible count Theorem 4.1, count used above Theorem C.13, fixed radii

Iterations

Certified δ(1)

1319 1500 519

5.16 × 10−8 5.16 × 10−8 9.90 × 10−8

At N = 519, the regularized population excess-risk bound remains 0.0586. We give the radius check and the certificate calculation in Appendix C.4; all quantities used in this comparison are determined by the public problem constants. To obtain the population bound, we first control the regularized excess Rµ (wN ) − Rµ (w∗ ) and then apply the uniform-convergence guarantee of Sridharan et al. [2008, Theorem 1], stated in the form used here as Theorem E.10. Theorem 4.9 (Excess population risk). Under Assumptions 1 to 3, let z ∼ N (0, σ 2 Id ) and let wN be the output of (4). Then for δS ∈ (0, 1), with probability at least 1 − δS over S, i 16 L2 32 + log(1/δ )
h dσ 2   S ℓ ∗ Ez Rµ (wN ) − Rµ (w ) ≤ 2 + Eopt (N ) + . 2µ µn 11

Proof sketch of Theorem 4.9. We first decompose the empirical excess risk into the effect of the linear perturbation and the finite optimization error. Strong convexity bounds the first contribution by ∥z∥2 /(2µ), and gradient descent controls the second through Eopt (N ). We then apply uniform convergence to transfer the empirical bound to population risk. This route does not introduce an additional multiplicative factor of L/µ in the leading statistical terms. Theorem 4.10 (Excess empirical risk). Under Assumptions 1 to 3, let z ∼ N (0, σ 2 Id ) and let wN be the output of (4). With Eopt (N ) as in (12),   dσ 2 Ez F (wN ; S) − F (wS∗ ; S) ≤ + Eopt (N ). 2µ As N → ∞ the bound tends to dσ 2 /(2µ), the standard objective-perturbation rate (Remark D.2). The preceding results average over the Gaussian perturbation. The same pointwise estimates also give a guarantee for the model produced in a single run. Corollary 4.11 (Utility of a single release). Under Assumptions 1 to 3, fix N ≥ 1 and β ∈ (0, 1). Define √  p Lℓ + rβ rβ = σ d + 2 log(1/β) , Rβ = , µ UN (β) =

rβ2 2µ

+

L 2N 2 ρ Rβ + ρN rβ Rβ . 2

For every fixed sample S, with probability at least 1 − β over the Gaussian perturbation, F (wN ; S) − F (wS∗ ; S) ≤ UN (β). Under the sampling assumptions of Theorem 4.9, for δS ∈ (0, 1), with probability at least 1 − δS − β over (S, Z), 16L2ℓ (32 + log(1/δS )) Rµ (wN ) − Rµ (w∗ ) ≤ 2UN (β) + . µn On this same event, simultaneously for every w̄ ∈ Rd , R0 (wN ) − R0 (w̄) ≤ 2UN (β) +

16L2ℓ (32 + log(1/δS )) µ + ∥w̄∥2 . µn 2

Remark 4.12 (Comparison with AMP). Approximate Minima Perturbation (AMP) [Iyengar et al., 2019] releases an approximate minimizer of the perturbed objective together with Gaussian output P noise calibrated to a gradient-norm tolerance γ. Let F0 (w; S) = n1 ni=1 ℓ(⟨xi , w⟩, yi ) and let ŵ minimize F0 . For GLM losses, their utility theorem gives s ! p p   Lℓ γ d log(1/δ) ∥ŵ∥ Lℓ d log(1/δ) E F0 (wout ; S) − F0 (ŵ; S) = O + ∥ŵ∥ . nϵ ϵ The first term is the objective-perturbation contribution, while the second depends on the optimization tolerance and becomes lower order when γ = O(1/n2 ). In our bound, finite optimization appears through Eopt (N ), which decreases geometrically with the number of gradient steps. AMP accounts for the composition of objective perturbation and the Gaussian output mechanism [Redberg et al., 2023, Remark 4.2]; our mechanism releases the deterministic N -th iterate after the single objective perturbation. 12

We next combine the privacy and utility bounds to choose the parameters for a prescribed privacy pair and a public comparator norm bound. Corollary 4.13 (Calibration to a target privacy budget). Under Assumptions 1 to 3, use G = 2Lℓ /n > 0. Fix 0 < ϵ ≤ 1, δ, δS ∈ (0, 1), and a public radius W > 0. Set 4Gu L2 ζ 2 , µpriv = , ϵ n(eϵ/4 − 1) √ 16L2ℓ (32 + log(1/δS )) 2A 2 A = dσ + , µutil = , µ = max{µutil , µpriv }. n W u=

p 2 log(2/δ),

σ=

After choosing µ, take public bounds L ≥ µ + L2 ζ 2 and M > 0 with M ≥ L3 ζ 3 , and choose a step size satisfying 0 < η ≤ 1/L and ηµ < 1. Choose a public integer N satisfying (7) and cN :=

G2 G N/2 ρ + 2 2ρN/2 + ρN σ 2σ eηµ ϵ + min{1, M G/L} N ρN/2 ≤ . 2 4

Such an integer exists. The release wN is (ϵ, δ)-differentially private. Moreover, with probability at least 1 − δS over the sample, simultaneously for all w̄ with ∥w̄∥ ≤ W , √ µpriv W 2 Ez [R0 (wN )] − R0 (w̄) ≤ W 2A + + 2Eopt (N ). 2 If µutil ≥ µpriv , the term µpriv W 2 /2 may be omitted. We use only public quantities to choose the parameters. For the leading term, we obtain p √ √ √ √ 8 2 W Lℓ u d 4 2 W Lℓ 32 + log(1/δS ) √ + . W 2A ≤ nϵ n We obtain separate terms for privacy, sampling, regularization, and finite optimization.

5

Discussion

We compare the privacy certificate with composition-free analyses of noisy iterations, explain where the GLM and unconstrained assumptions enter, and then give the resulting computational cost.

5.1

Three approaches to composition-free privacy

We compare our result with two lines of last-iterate privacy analysis for noisy optimization. Privacy amplification by iteration was introduced by Feldman et al. [2018], sharpened for projected noisy SGD by Altschuler et al. [2024], and formulated in f -differential privacy by Bok et al. [2024]. Chourasia et al. [2021] analyze privacy-loss dynamics for noisy gradient descent, and Ye and Shokri [2022] extend the hidden-state analysis to mini-batch schemes. Chien and Li [2025] further treat nonconvex objectives with Hölder-continuous gradients. The table summarizes the assumptions and iteration dependence of the corresponding certificates.

13

Amplification by iteration

Privacy-loss dynamics

Analytical tool

shifted Rényi divergence

Noise Released object

Gaussian, per step last noisy iterate Lipschitz loss, contractive updates

Fokker–Planck equation, log-Sobolev inequality Gaussian, per step last noisy iterate smoothness, strong convexity

rises, then plateaus

plateaus (exp. fast)

Requires Certified bound

This work change of variables Gaussian, one draw wN , deterministic in z smoothness, strong convexity, Lipschitz Hessian, GLM finite-N correction decays geometrically

Privacy amplification by iteration and privacy-loss dynamics both study algorithms that add noise during the iteration. In our setting the randomness enters once through the linear objective perturbation, after which the updates are deterministic. For amplification by iteration, the certified privacy loss rises and then plateaus; for the privacy-loss dynamics it converges exponentially to a plateau. Over the range covered by (7), our finite-iteration correction decreases with N and the certificate approaches the exact-minimizer bound. All three analyses can give certified bounds without an explicit ambient-dimension factor. In our setting this follows from the GLM structure: neighboring gradients differ in a two-dimensional feature span, Hessian changes have rank-one structure, and the orthogonal complement of the data span evolves identically under neighboring datasets (Section 5.2). The assumptions differ across these analyses. Privacy amplification by iteration uses a Lipschitz loss and contractive updates, while the privacy-loss dynamics use smoothness and strong convexity. Our change-of-variables proof uses smoothness, strong convexity, a Lipschitz Hessian, and GLM structure. The Lipschitz-Hessian assumption supports the frozen-Hessian comparison, and the GLM structure gives the subspace and nuclear-norm bounds used in the privacy analysis.

5.2

The role of GLM structure and the constrained–unconstrained distinction

The GLM structure enters the privacy bound in three places. First, the gradient difference between neighboring datasets lies in span{xn , x′n }, so the leading Gaussian-ratio term depends on two scalar projections of the perturbation. Second, Hessian changes are sums of rank-one matrices, which gives the required nuclear-norm bounds without a factor of d. Third, the data-span decomposition makes the C ⊥ block identical under neighboring datasets, so only the feature span enters the truncation argument. The frozen-Hessian invertibility argument itself uses strong convexity, smoothness, and a Lipschitz Hessian. We analyze unconstrained gradient descent on Rd . This preserves the smooth map z 7→ wN and the contraction estimates used throughout the proof. In the constrained setting, Bassily et al. √ [2014] proved excess-risk lower bounds of Ω(min(1, d/(nϵ))) for convex losses and Ω(d/(n2 ϵ2 )) for strongly √ convex losses. For unconstrained GLMs, Song et al. [2021] obtained excess empirical e ℓ rank/(ϵn)), where rank ≤ min{n, d} is the rank of the feature matrix. Our change-ofrisk O(L variables analysis operates in this unconstrained setting.

5.3

Computational cost

Running N full-batch gradient steps requires nN individual-gradient evaluations. At step size 1/L, the sufficient condition (7) has order κ log(·), giving O(nκ log(·)) individual-gradient evaluations. Under the public calibration in Corollary 4.13, fix ϵ, δ, δS , W and the loss constants. When dσ 2 = O(1/n) and µutil ≥ µpriv , we choose µ = Θ(n−1/2 ). Taking L = µ + L2 ζ 2 with L2 ζ 2 > 0 then gives √ √ κ = Θ( n). In this regime, O( n log n) iterations suffice for the explicit privacy certificate and 14

for an optimization correction of order n−1/2 or smaller. The resulting sufficient gradient count is O(n3/2 log n). For comparison, DP-SGD [Bassily et al., 2014] attains the optimal constrained-ERM rates after T = n2 steps. Bassily et al. [2019] obtain O(n log n) gradient complexity for smooth GLMs by using SVRG to solve the perturbed objective to a prescribed accuracy and then adding Gaussian output noise to certify the remaining optimization error. For private stochastic convex optimization, Feldman et al. [2020] attain optimal population-risk rates with at most linear gradient complexity under their smoothness assumptions. Our result analyzes the deterministic full-batch gradient-descent iterate after a single objective perturbation.

Acknowledgements This work was supported, in part, by NSF BIGDATA award IIS-1838139 and NSF CAREER award IIS-1943251.

References Jason M. Altschuler, Jinho Bok, and Kunal Talwar. On the privacy of noisy stochastic gradient descent for convex optimization. SIAM Journal on Computing, 53(4):969–1001, 2024. Preliminary version by J. M. Altschuler and K. Talwar: Privacy of noisy stochastic gradient descent: More iterations without more privacy loss, Advances in Neural Information Processing Systems 35, 2022. Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Advances in Neural Information Processing Systems 31, 2018. Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2014. Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems 32, pages 11279–11288, 2019. Jinho Bok, Weijie J. Su, and Jason M. Altschuler. Shifted interpolation for differential privacy. In Proceedings of the 41st International Conference on Machine Learning (ICML), 2024. Jérôme Bolte, Quoc-Tung Le, Edouard Pauwels, and Samuel Vaiter. Bilevel gradient methods and the Morse parametric qualification condition. Mathematics of Operations Research, 2026. To appear. doi:10.1287/moor.2025.0914. Gavin Brown, Krishnamurthy Dvijotham, Georgina Evans, Daogao Liu, Adam Smith, and Abhradeep Thakurta. Private gradient descent for linear regression: Tighter error bounds and instance-specific uncertainty estimation. In International Conference on Machine Learning (ICML), 2024. Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3–4):231–357, 2015.

15

Kamalika Chaudhuri and Claire Monteleoni. Privacy-preserving logistic regression. In Advances in Neural Information Processing Systems 21, 2008. Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12:1069–1109, 2011. Eli Chien and Pan Li. Convergent privacy loss of noisy-SGD without convexity and smoothness. In International Conference on Learning Representations (ICLR), pages 12238–12260, 2025. Rishav Chourasia, Jiayuan Ye, and Reza Shokri. Differential privacy dynamics of Langevin diffusion and noisy gradient descent. In Advances in Neural Information Processing Systems 34, pages 14771–14781, 2021. Daniel Cortild and Coralia Cartis. Quadratic objective perturbation: Curvature-based differential privacy. arXiv preprint arXiv:2605.05905, 2026. Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems 31, 2018. Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian differential privacy. Journal of the Royal Statistical Society, Series B, 2022. Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 521–532, 2018. Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in linear time. In Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC), pages 439–449, 2020. Gerald B. Folland. Real Analysis: Modern Techniques and Their Applications. John Wiley & Sons, second edition, 1999. Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, second edition, 2013. Roger Iyengar, Joseph P. Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards practical differentially private convex optimization. In IEEE Symposium on Security and Privacy (SP), 2019. Prateek Jain and Abhradeep Guha Thakurta. (Near) dimension independent risk bounds for differentially private learning. In Proceedings of the 31st International Conference on Machine Learning (ICML), pages 476–484, 2014. Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory (COLT), JMLR Workshop and Conference Proceedings, pages 25.1–25.40, 2012. Seth Neel, Aaron Roth, Giuseppe Vietri, and Zhiwei Steven Wu. Oracle efficient private non-convex optimization. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 7243–7252. PMLR, 2020. Yurii Nesterov. Lectures on Convex Optimization. Springer, second edition, 2018. 16

Rachel Redberg, Antti Koskela, and Yu-Xiang Wang. Improving the privacy and practicality of objective perturbation for differentially private linear learners. In Advances in Neural Information Processing Systems 36, 2023. Walter Rudin. Principles of Mathematical Analysis. McGraw-Hill, third edition, 1976. Shuang Song, Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimensionality in unconstrained private GLMs. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2638–2646. PMLR, 2021. Karthik Sridharan, Nathan Srebro, and Shai Shalev-Shwartz. Fast rates for regularized objectives. In Advances in Neural Information Processing Systems 21, 2008. Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019. Jiayuan Ye and Reza Shokri. Differentially private learning needs hidden state (or much faster convergence). In Advances in Neural Information Processing Systems 35, pages 703–715, 2022.

17

The map M is a diffeomorphism

A

On any bounded convex set and for all sufficiently large N (with the threshold depending on the set), the restriction of M to the set is a C 1 -diffeomorphism onto its image (Corollary 4.4). The argument combines two ingredients: local invertibility, from a lower bound on the smallest singular value of the Jacobian JN , and global injectivity, from negative definiteness of its symmetric part sym JN . We obtain both by comparing JN to the Jacobian J˜N of the frozen-Hessian model —the map obtained by freezing the Hessian at its value at the released iterate wN , equivalently by replacing F with its quadratic Taylor expansion there—whose spectrum we compute in closed form.

A.1

General setting

We prove the structural results below under assumptions that do not require the generalized linear form. The GLM setting of Section 3.1 satisfies these assumptions with the constants derived there. Let F : Rd → R be twice continuously differentiable. Our analysis rests on two regularity assumptions on F . Assumption 4 (Strong convexity and smoothness). F is µ-strongly convex and L-smooth: µI ⪯ ∇2 F (w) ⪯ LI for all w ∈ Rd , where 0 < µ ≤ L. Assumption 5 (Lipschitz Hessian). The Hessian of F is M -Lipschitz with M > 0: ∥∇2 F (w) − ∇2 F (v)∥ ≤ M ∥w − v∥ for all w, v ∈ Rd . For the differential-privacy analysis we consider a family of functions {F (· ; S)} indexed by datasets S. Two datasets S and S ′ are neighboring if they differ in at most one data point. We require Assumptions 4 and 5 to hold for every member of the family with common constants µ, L, M (that is, uniformly in S), and impose the following cross-dataset condition. Assumption 6 (Gradient sensitivity). Neighboring datasets perturb the gradient by at most G > 0: ∥∇F (w; S) − ∇F (w; S ′ )∥ ≤ G for all w ∈ Rd and all neighboring S, S ′ . Lemma A.1 (Averaged derivative). Let K : Rd → Rd be continuously differentiable. For a, b ∈ Rd set Z 1
∇K(a, b) := ∇K b + t(a − b) dt, (13) 0

The fundamental theorem of calculus along the segment reads K(a) − K(b) =
R 1 from b to a then ∇K(a, b) (a−b). At K = ∇F we abbreviate H̄(a, b) := 0 ∇2 F b+t(a−b) dt. Under Assumption 4: 1. ∇F (a) − ∇F (b) = H̄(a, b) (a − b), with H̄(a, b) symmetric and µI ⪯ H̄(a, b) ⪯ LI; 2. ∥I − ηH∥ ≤ ρ for every symmetric H with µI ⪯ H ⪯ LI; in particular ∥Ak ∥ ≤ ρ at every iterate, and ∥I − η H̄(a, b)∥ ≤ ρ for all a, b. Proof. The map t 7→ K(b+t(a−b)) is continuously differentiable on [0, 1]Rwith derivative ∇K(b+t(a− 1 b)) (a−b), so the fundamental theorem of calculus gives K(a)−K(b) = 0 ∇K(b+t(a−b)) (a−b) dt, out of which the constant vector a − b factors. For item 1, each integrand ∇2 F (b + t(a − b)) is symmetric with spectrum in [µ, L] (Assumption 4), and averaging preserves both properties: H̄(a, b) R1 is symmetric, and ⟨H̄(a, b) v, v⟩ = 0 ⟨∇2 F (b + t(a − b)) v, v⟩ dt lies between µ∥v∥2 and L∥v∥2 for every v. For item 2, I − ηH is symmetric with eigenvalues in [1 − ηL, 1 − ηµ], an interval of nonnegative numbers since ηL ≤ 1, so ∥I − ηH∥ ≤ 1 − ηµ = ρ; the two instances are H = ∇2 F (wk ), for which I − ηH = Ak , and H = H̄(a, b). 18

A.2

The trajectory

We use the perturbed minimizer as the reference point for the utility analysis and control its distance from the iterates through the trajectory bounds below. Lemma A.2 (Perturbed minimizer). For each z ∈ Rd there is a unique w∗ (z) ∈ Rd satisfying ∇F (w∗ (z)) + z = 0, namely the minimizer of w 7→ F (w) + ⟨z, w⟩.   Proof. The linear term has zero Hessian, so ∇2 F (w) + ⟨z, w⟩ = ∇2 F (w) ⪰ µI by Assumption 4; the perturbed objective is therefore µ-strongly convex. Existence, uniqueness, and the first-order characterization of the minimizer of a strongly convex function are standard (Lemma E.1). The trajectory estimates all compare two runs of (4) driven by nearly the same gradient: the step map contracts by ρ, so a run driven within β of the exact one stays within β/µ of it. Lemma A.3 (Comparison of runs). Fix z ∈ Rd , let (wk )k≥0 be the iterates (4), and let (wk′ )k≥0 ′ satisfy wk+1 = wk′ − η uk for vectors uk obeying
≤ β for every k ≥ 0. uk − ∇F (wk′ ) + z Then, for every k ≥ 0, ∥wk − wk′ ∥ ≤ ρk ∥w0 − w0′ ∥ +

β 1 − ρk . µ

(14)

Proof. Subtracting the two recursions and splitting the driver difference at wk′ ,

′ = (wk − wk′ ) − η ∇F (wk ) − ∇F (wk′ ) − η ∇F (wk′ ) + z − uk . wk+1 − wk+1 By item 1 of Lemma A.1 the first gradient difference is H̄(wk , wk′ )(wk − wk′ ), so the first two terms
together are I − η H̄(wk , wk′ ) (wk − wk′ ), of norm at most ρ ∥wk − wk′ ∥ by item 2; the last term ′ ∥ ≤ ρ ∥wk − wk′ ∥ + ηβ, and iterating from has norm at most ηβ by hypothesis. Hence ∥wk+1 − wk+1 k = 0, k−1 X
β ρj = ρk ∥w0 − w0′ ∥ + ∥wk − wk′ ∥ ≤ ρk ∥w0 − w0′ ∥ + ηβ 1 − ρk , µ j=0

using 1 − ρ = ηµ. The minimizer is the run that stands still, so comparing the iterates with it drives them to w∗ (z) at the rate ρ. Lemma A.4 (Convergence of the iterates). For every z ∈ Rd and every k ≥ 0, ∥wk − w∗ (z)∥ ≤ ρk ∥w0 − w∗ (z)∥. ′ Proof. By Lemma A.2, ∇F (w∗ (z)) + z = 0, so the constant sequence wk′ ≡ w∗ (z) satisfies wk+1 =
′ ′ wk − η ∇F (wk ) + z : it is the run of (4) started at the minimizer, and it never moves. Lemma A.3 at β = 0 with w0′ = w∗ (z) is the claim. This is the standard contraction estimate for gradient descent in the strongly convex, smooth regime; Bubeck [2015, §3.4.2] states it at η = 1/L, and the argument above gives it for every η ∈ (0, 1/L].

The minimizer also depends stably on the perturbation, and its distance from any point is controlled by the perturbed gradient there.

19

Lemma A.5 (Sensitivity of the perturbed minimizer). For all z, z ′ ∈ Rd , ∥w∗ (z) − w∗ (z ′ )∥ ≤

1 ∥z − z ′ ∥, µ

and consequently ∥w∗ (z) − w∥ ≤ µ1 ∥∇F (w) + z∥ for every w ∈ Rd . Proof. Run (4) at z and at z ′ , writing (wk ) and (wk′ ) for the two trajectories; both start at w0 , so each is the iterate sequence to which Lemma A.4 applies. The second is driven by uk = ∇F (wk′ )+z ′ , so ∥uk − (∇F (wk′ ) + z)∥ = ∥z − z ′ ∥ for every k, and Lemma A.3 with w0′ = w0 and β = ∥z − z ′ ∥ gives
∥z − z ′ ∥ ∥z − z ′ ∥ ∥wk − wk′ ∥ ≤ 1 − ρk ≤ for every k ≥ 0. µ µ By Lemma A.4 the two trajectories converge to w∗ (z) and w∗ (z ′ ), so the bound passes to the limit. For the second bound, fix w and take z ′ = −∇F (w); then ∇F (w) + z ′ = 0, so w∗ (−∇F (w)) = w by Lemma A.2, and the Lipschitz bound yields ∥w∗ (z) − w∥ ≤ µ1 ∥∇F (w) + z∥. The scale every subsequent bound is measured against is set by the iteration itself: the length of its first step. Since consecutive steps contract, that one length bounds every later step and the distance to the minimizer. Lemma A.6 (Trajectory scale). Set R(z) :=

∥∇F (w0 ) + z∥ ∥w1 − w0 ∥ = . µ ηµ

(15)

Then, for every z ∈ Rd : 1. R(z) ≤ bR ∥z∥ + aR , with bR := µ1 and aR := ∥∇Fµ(w0 )∥ ; 2. ∥wk+1 − wk ∥ ≤ ηµ ρk R(z) for every k ≥ 0, and consequently
∥wk − wN ∥ ≤ ρk − ρN R(z), 0 ≤ k ≤ N;

(16)

3. ∥w0 − w∗ (z)∥ ≤ R(z). For a bounded set D ⊂ Rd we write RD := supz∈D R(z), which is finite. Proof. The second expression in (15) is the first step of (4), w1 − w0 = −η(∇F (w0 ) + z), and item 1 is the triangle inequality. For item 2, the shifted sequence wk′ := wk+1 is the run of (4) started at w1 instead of w0 , so Lemma A.3 at β = 0 compares the trajectory with its own time shift: ∥wk − wk+1 ∥ ≤ ρk ∥w0 − w1 ∥ = ηµ ρk R(z), the equality by (15). This is the per-step bound; summing it over j = k, . . . , N − 1 and using 1 − ρ = ηµ, ∥wk − wN ∥ ≤

N −1 X

∥wj+1 − wj ∥ ≤ ηµ R(z)

j=k

N −1 X

ρj = R(z) ρk − ρN .

j=k

Item 3 is the second bound of Lemma A.5 at w = w0 . Since D is bounded, supz∈D ∥z∥ < ∞, and item 1 gives RD ≤ bR supz∈D ∥z∥ + aR < ∞. 20

Two runs from the shared initialization, under neighboring datasets and the same z, are driven within G of each other at every step, so they never separate by more than G/µ. Lemma A.7 (Map sensitivity). For any z ∈ Rd and any k ≥ 0, ′

∥wkS − wkS ∥ ≤

G G 1 − ρk ≤ ; µ µ

in particular, at the final iterate, ∥MS (z) − MS ′ (z)∥ ≤

G G 1 − ρN ≤ . µ µ ′

Proof. The two runs share the initialization, w0S = w0S = w0 . Read against F (· ; S), the run under ′ S ′ is driven by uk = ∇F (wkS ; S ′ ) + z, and ′

uk − ∇F (wkS ; S) + z

′

′

= ∇F (wkS ; S ′ ) − ∇F (wkS ; S) ≤ G

by Assumption 6. Lemma A.3 for F (· ; S), with w0′ = w0 and β = G, gives the first bound, and S and the second follows from 1 − ρk ≤ 1. Taking k = N gives the final display, since MS (z) = wN ′ S . MS ′ (z) = wN

A.3

The frozen-Hessian model

To analyze the Jacobian JN = ∇M(z), we compare it with what we call the frozen-Hessian model : the mechanism run with the Hessian held fixed at its value at the point the mechanism releases. The model solves in closed form, and at every N ≥ 1 each eigenvalue of its Jacobian is at most −γN , with γN = (1 − (1 − ηL)N )/L → 1/L (Lemma A.9)—the floor the true Jacobian will inherit. Fix z ∈ Rd and a horizon N , and set
H ∗ := ∇2 F M(z) = ∇2 F (wN ), A∗ := I − ηH ∗ , so that H ∗ is symmetric with eigenvalues in [µ, L] by Assumption 4—which holds at every point, so the anchor may be any one—hence invertible. Freezing the Hessian at H ∗ amounts to replacing F with its quadratic Taylor expansion at wN ; the Jacobian recursion (5) then runs with the iteratedependent Ak replaced by the constant matrix A∗ . Writing J˜k for the resulting Jacobian, an auxiliary sequence indexed by k ≤ N at the anchor the horizon N fixes, J˜k+1 = A∗ J˜k − ηI,

J˜0 = 0.

(17)

Here we evaluate H ∗ at the fixed base perturbation z and hold it constant throughout the auxiliary recursion. Because A∗ is constant, this affine recursion unrolls into a geometric sum. Its fixed point is −(H ∗ )−1 , since substituting J˜ = −(H ∗ )−1 into (17) returns it unchanged. Lemma A.8 (Closed form of J˜N ). For all N ≥ 0, J˜N = −η

N −1 X

(A∗ )j = −(H ∗ )−1 I − (A∗ )N .

j=0

21

(18)

Proof. The first equality is an induction on N . The sum is empty at N = 0, matching J˜0 = 0; and if it holds at N , then (17) gives −1 N N  NX  X X J˜N +1 = A∗ −η (A∗ )j − ηI = −η (A∗ )j − η(A∗ )0 = −η (A∗ )j . j=0

j=1

j=0

P −1 ∗ j For the second equality, I − A∗ = ηH ∗ , so the telescoping identity I − (A∗ )N = (I − A∗ ) N j=0 (A ) PN −1 ∗ j ∗ N ∗ ∗ −1 reads I − (A ) = ηH and negating gives the j=0 (A ) ; multiplying on the left by (H ) claim. Because every term is a power of the symmetric matrix A∗ , we can read off the symmetry, spectrum, operator-norm bound, and singular-value floor directly in an eigenbasis of H ∗ . Lemma A.9 (Spectrum and norms of J˜N ). Let h1 , . . . , hd ∈ [µ, L] be the eigenvalues of H ∗ . 1. J˜N is symmetric, with eigenvalues λ̃i (N ) = −η

N −1 X

(1 − ηhi )j = −

j=0

1 1 − (1 − ηhi )N , hi

i = 1, . . . , d.

2. For all N ≥ 0, ∥J˜N ∥ ≤

1 − ρN 1 =: BN ≤ =: B. µ µ

3. For every N ≥ 1 every eigenvalue of J˜N is negative, and σmin (J˜N ) ≥

1 − (1 − ηL)N =: γN ≥ η > 0, L

with equality in the first inequality whenever L is an eigenvalue of H ∗ . Proof. Item 1. Each (A∗ )j is a power of the symmetric matrix A∗ , hence symmetric, so (18) makes J˜N symmetric. Fix an orthonormal eigenbasis v1 , . . . , vd of H ∗ , with H ∗ vi = hi vi . Then A∗ vi = (1 − ηhi )vi , so vi is an eigenvectorPof every (A∗ )j with eigenvalue (1 − ηhi )j , and by (18) an eigenvector of J˜N with eigenvalue −η j<N (1 − ηhi )j . Because hi ∈ [µ, L] and ηL ≤ 1, the ratio satisfies 0 ≤ 1 − ηhi ≤ 1 − ηµ = ρ < 1, so summing the geometric series gives the second expression. Ranging over i exhausts the spectrum, and symmetry makes ∥J˜N ∥ = maxi |λ̃i (N )| and σmin (J˜N ) = mini |λ̃i (N )|. Items 2 and 3. By item 1 and symmetry, every singular value of J˜N is the value at some hi of the scalar profile fN (h) := η

N −1 X j=0

(1 − ηh)j =

1 − (1 − ηh)N , h

h ∈ [µ, L].

On this interval 1 − ηh ∈ [1 − ηL, ρ] ⊆ [0, 1), so each summand (1 − ηh)j is a nonnegative power of the nonincreasing map h 7→ 1 − ηh, hence itself nonnegative and nonincreasing in h; the profile is therefore nonincreasing on [µ, L], and both norm bounds are its endpoint values. At the left endpoint the sum is geometric with ratio ρ, so ∥J˜N ∥ = max fN (hi ) ≤ fN (µ) = η i

22

1 − ρN 1 − ρN = = BN , 1−ρ µ

using 1 − ρ = ηµ. Since ρN ≥ 0, BN ≤ 1/µ. For N ≥ 1 the j = 0 summand alone gives fN ≥ η > 0 on all of [µ, L], so every eigenvalue −fN (hi ) is negative, and at the right endpoint N

1 − (1 − ηL) σmin (J˜N ) = min fN (hi ) ≥ fN (L) = i L

= γN ≥ η > 0,

with equality whenever some hi equals L: the floor is the minimum of the profile over the curvature interval, not a relaxation of it.

A.4

Perturbation bounds

We now bound the gap between the true Jacobian JN and the Jacobian J˜N of the frozen-Hessian model. Write δk := Jk − J˜k for the Jacobian error; it is controlled by the operator-norm deviation ∥∇2 F (wk ) − H ∗ ∥ of the Hessian along the trajectory, and ∥δN ∥ will be shown to decay as ν̃N ρN −1 , where the factor ν̃N weights each step by how far the reference Jacobian has grown by then and by how far the iterate still stands from the anchor. Both factors vanish at an end: the Hessian deviation is largest at k = 0 and zero at k = N , while the reference Jacobian starts at zero and grows. Lemma A.10 (Error recursion). The Jacobian error satisfies
δk+1 = Ak δk − η ∇2 F (wk ) − H ∗ J˜k ,

δ0 = 0,

and hence, writing ΘN,k+1 := AN −1 AN −2 · · · Ak+1 for the state-transition product (ΘN,N := I), unrolls to N −1 X
N ≥ 0. (19) δN = −η ΘN,k+1 ∇2 F (wk ) − H ∗ J˜k , k=0

Proof. Subtracting the frozen-Hessian recursion (17) from the Jacobian recursion (5), δk+1 = (Ak Jk − ηI) − (A∗ J˜k − ηI) = Ak Jk − Ak J˜k + Ak J˜k − A∗ J˜k = Ak (Jk − J˜k ) + (Ak − A∗ )J˜k .
The first term is Ak δk . For the second, Ak −A∗ = (I −η∇2 F (wk ))−(I −ηH ∗ ) = −η ∇2 F (wk )−H ∗ , giving −η(∇2 F (wk ) − H ∗ )J˜k . Finally δ0 = J0 − J˜0 = 0 − 0 = 0. Induction on the iterate index, the anchor H ∗ held at ∇2 F (wN ) throughout, gives (19): the sum is empty at index 0, matching δ0 = 0; and applying the recursion once left-multiplies every term present by AN , which turns each ΘN,k+1 into ΘN +1,k+1 , and appends the k = N term with ΘN +1,N +1 = I. The inhomogeneous term contains the Hessian difference ∇2 F (wk )−H ∗ . Since H ∗ = ∇2 F (wN ), the Lipschitz-Hessian assumption and (16) give, for all 0 ≤ k ≤ N ,
∥∇2 F (wk ) − H ∗ ∥ ≤ M ∥wk − wN ∥ ≤ M ρk − ρN R(z). (20) The deviation vanishes at k = N , where the anchor is read. Feeding this decay through the error recursion bounds ∥δN ∥. Proposition A.11 (Jacobian error bound). Let ∥ · ∥⋄ be either the operator norm or the nuclear norm, and suppose the Hessian of F is M -Lipschitz in it: ∥∇2 F (w) − ∇2 F (v)∥⋄ ≤ M ∥w − v∥ for all w, v. Assumption 5 is this hypothesis at the operator norm. Let C(z) := ηM R(z) B and νN :=

N −1 X k=0

1 − ρN , 1 − ρk = N − ηµ 23

0 ≤ νN ≤ N.

(21)

For all N ≥ 1, ∥δN ∥⋄ ≤ C(z) ν̃N ρN −1 , where ν̃N :=

N −1 X

1−ρ

k=0

N −k

1−ρ

k

ρ 1 − ρN , = νN + N ρ − ηµ N

0 ≤ ν̃N ≤ νN ,

(22)

and ν̃1 = ν1 = 0. Proof. Both norms satisfy ∥XY Z∥⋄ ≤ ∥X∥ ∥Y ∥⋄ ∥Z∥: for the operator norm this is submultiplicativity, for the nuclear norm the Schatten–Hölder bound of Lemma E.7. Apply it to each summand of (19), taking Y to be the Hessian-deviation factor. Each Aj satisfies ∥Aj ∥ ≤ ρ (item 2 of Lemma A.1), so submultiplicativity over the N − 1 − k factors gives ∥ΘN,k+1 ∥ ≤ ρN −1−k . With the Hessian deviation bound (20), which the hypothesis gives verbatim in ∥ · ∥⋄ , and ∥J˜k ∥ ≤ Bk = (1 − ρk )/µ (item 2 of Lemma A.9), the k-th summand has ∥ · ∥⋄ at most


1 − ρk η ρN −1−k · M ρk − ρN R(z) · = C(z) ρN −1 1 − ρN −k 1 − ρk , µ

since C(z) = ηM R(z)/µ and ρN −1−k ρk − ρN = ρN −1 1 − ρN −k . Summing over k gives ∥δN ∥⋄ ≤ C(z) ν̃N ρN −1 with ν̃NPthe sum in (22), nonnegative every factor is. closed form,
Pbecause P For itsN −k k ) = ν , while N −k (1 − ρk ) = split the summand: (1 − ρ ρ ρ − ρN = N k<N k<N k<N PN j PN j N N N N j=1 ρ = ρ(1 − ρ )/(1 − ρ) and 1 − ρ = ηµ. That j=1 ρ − N ρ = ρ(1 − ρ )/(ηµ) − N ρ , using second sum, subtracted here rather than added, is a sum of nonnegative terms, giving ν̃N ≤ νN ; at N P = 1 its only term is (1 − ρ)(1 − ρ0 ) = 0, so ν̃1 = 0. The closed form in (21) follows −1 k N k from N k=0 ρ = (1 − ρ )/(1 − ρ) with 1 − ρ = ηµ, and 0 ≤ 1 − ρ ≤ 1 for every k ≥ 0 gives 0 ≤ νN ≤ N .

A.5

Local invertibility, injectivity, and the diffeomorphism

We can now prove that M is a diffeomorphism on a bounded convex set. The perturbation bound transfers the spectral control from J˜N to the symmetric part of JN , and negative definiteness of sym yields both the singular-value floor—hence local invertibility—and global injectivity on convex JN sets. Throughout, ∇M(z) = JN . Theorem A.12 (Negative definiteness and invertibility of the Jacobian). Let D ⊂ Rd be bounded, write CD := ηM RD B, and suppose N satisfies γN > CD ν̃N ρN −1 . Then, with αD := γN − CD ν̃N ρN −1 > 0, for every z ∈ D: 1. JN (z)sym ⪯ −αD I; 2. σmin (∇M(z)) ≥ αD , so ∇M(z) is invertible and M is a local diffeomorphism on D. Since γN → 1/L and CD ν̃N ρN −1 → 0 as N → ∞, the hypothesis holds for all sufficiently large N . Proof. The hypothesis gives γN > CD ν̃N ρN −1 ≥ 0, and γN = (1 − (1 − ηL)N )/L > 0 forces N ≥ 1, the hypothesis of item 3 of Lemma A.9. By items 1 and 3 of that lemma, every eigenvalue of the symmetric J˜N is negative with modulus at least γN , i.e. J˜N ⪯ −γN I. Write JN = J˜N + δN , so sym sym JN = J˜N + δN . For any unit vector v, sym sym sym ⟨JN v, v⟩ = ⟨J˜N v, v⟩ + ⟨δN v, v⟩ ≤ −γN + ∥δN ∥ ≤ −γN + ∥δN ∥ ≤ −γN + CD ν̃N ρN −1 = −αD ,

24

sym using ∥δN ∥ ≤ ∥δN ∥ from Section 3.1 and Proposition A.11 (with C(z) ≤ CD for z ∈ D); as this holds for every unit v, item 1 follows. For item 2, Cauchy–Schwarz and the identity ⟨Av, v⟩ = ⟨Asym v, v⟩ (Section 3.1) give, for every unit v, sym ∥JN v∥ ≥ |⟨JN v, v⟩| = |⟨JN v, v⟩| ≥ αD ,

so σmin (∇M(z)) = σmin (JN ) ≥ αD > 0 and ∇M(z) is invertible; as M ∈ C 1 , the inverse function theorem [Rudin, 1976, Theorem 9.24] makes M a local diffeomorphism at each z ∈ D. Finally γN → 1/L > 0 while ν̃N ρN −1 ≤ N ρN −1 → 0 for ρ ∈ (0, 1), so the hypothesis holds once N is large enough. On a convex domain, negative definiteness of the symmetric part also makes M injective. Theorem A.13 (Injectivity). Let D ⊂ Rd be a bounded convex set satisfying the hypotheses of Theorem A.12. Then for all z1 , z2 ∈ D, ⟨M(z1 ) − M(z2 ), z1 − z2 ⟩ ≤ −αD ∥z1 − z2 ∥2 ; in particular ∥M(z1 ) − M(z2 )∥ ≥ αD ∥z1 − z2 ∥, and M is injective on D. Proof. Let z1 , z2 ∈ D; the claims are trivial for z1 = z2 , so assume z1 ̸= z2 . Since M is C 1 with ∇M = JN , Lemma A.1 at K = M gives M(z1 ) − M(z2 ) = ∇M(z1 , z2 ) (z1 − z2 ), the average taken along the segment z2 + t(z1 − z2 ), which lies in D by convexity. Taking symmetric parts commutes with that average, so item 1 of Theorem A.12 bounds each integrand and Z 1
sym sym ∇M(z1 , z2 ) = JN z2 + t(z1 − z2 ) dt ⪯ −αD I. 0

With the identity ⟨Av, v⟩ = ⟨Asym v, v⟩ (Section 3.1) at v = z1 − z2 , ⟨M(z1 ) − M(z2 ), z1 − z2 ⟩ = ∇M(z1 , z2 )sym (z1 − z2 ), z1 − z2 ≤ −αD ∥z1 − z2 ∥2 < 0, so M(z1 ) ̸= M(z2 ); and Cauchy–Schwarz gives ∥M(z1 ) − M(z2 )∥ ∥z1 − z2 ∥ ≥ αD ∥z1 − z2 ∥2 , which after dividing by ∥z1 − z2 ∥ is the displacement bound. Local invertibility and injectivity together make M a diffeomorphism onto its image. Corollary 4.4 (Diffeomorphism onto the image). Let F : Rd → R be twice continuously differentiable, µ-strongly convex, and L-smooth, with an M -Lipschitz Hessian. With step size 0 < η ≤ 1/L and ηµ < 1 (Section 3.2), let D ⊂ Rd be a bounded convex open set with αD > 0. Then M(D) is open and M : D → M(D) is a C 1 -diffeomorphism. Proof. By Theorem A.12, M is a local diffeomorphism at each point of D; in particular it is an open map, so M(D) is open. By Theorem A.13 it is injective on the convex set D, hence a bijection onto M(D). Near each y ∈ M(D) the global inverse M−1 coincides with the C 1 local inverse furnished by the inverse function theorem [Rudin, 1976, Theorem 9.24] (these agree by injectivity), so M−1 is C 1 on M(D). Thus M : D → M(D) is a C 1 -diffeomorphism.

25

B

GLM structure and rank-one Hessian perturbations

Three features of GLMs remove explicit ambient-dimension factors from the privacy bound. Hessian changes are sums of rank-one matrices with controlled coefficients, so we can bound their nuclear norms directly rather than using the generic inequality ∥A∥∗ ≤ d∥A∥. The gradient difference between neighboring datasets lies in the span of the two differing feature vectors. Finally, the data span separates from its orthogonal complement, where both neighboring mechanisms follow the same affine recursion. Throughout, n

∇2 FS (w) =

1 X ′′ ℓ (⟨xi , w⟩, yi )xi x⊤ i + µI. n i=1

The same rank-one form fixes the range of curvature the analysis meets, supplying the constants µ and L of Assumption 4 for GLMs. Lemma B.1 (GLM curvature range). Under Assumptions 1 and 2, for each dataset T ∈ {S, S ′ } and all w ∈ Rd ,
µI ⪯ ∇2 FT (w) ⪯ µ + L2 ζ 2 I. In particular Assumption 4 holds in the GLM setting for any L ≥ µ + L2 ζ 2 . Proof. Each coefficient ℓ′′ (⟨xi , w⟩, yi ) is nonnegative (Assumption 2) and each xi x⊤ i is positive 2 semidefinite, so the sum ⪰ µI. For the upper bound the Pis positive semidefinite and1 ∇ P FT (w) ⊤ , and the triangle inequality with same two facts give n1 i ℓ′′ (⟨xi , w⟩, yi ) xi x⊤ ⪯ L x x 2 i i i i n 2 2 2 ∥xi x⊤ i ∥ = ∥xi ∥ ≤ ζ (Assumption 1) bounds the operator norm of the second factor by ζ . The same rank-one structure makes the Hessian Lipschitz in nuclear norm. Lemma B.2 (GLM Hessian displacement). Under Assumptions 1 and 3, for each dataset T ∈ {S, S ′ } and all w, w′ ∈ Rd , ∥∇2 FT (w) − ∇2 FT (w′ )∥∗ ≤ L3 ζ 3 ∥w − w′ ∥, and hence the same bound in operator norm, since ∥A∥ ≤ ∥A∥∗ . In particular Assumption 5 holds in the GLM setting for any M ≥ L3 ζ 3 . Proof. The constant regularizer Hessian cancels, leaving n

∇2 FT (w) − ∇2 FT (w′ ) =

1X ci xi x⊤ i , n

ci := ℓ′′ (⟨xi , w⟩, yi ) − ℓ′′ (⟨xi , w′ ⟩, yi ).

i=1

Assumption 3, read at the arguments ⟨xi , w⟩ and ⟨xi , w′ ⟩, followed by Cauchy–Schwarz, gives 2 |ci | ≤ L3 |⟨xi , w − w′ ⟩| ≤ L3 ∥xi ∥ ∥w − w′ ∥. Each ci xi x⊤ i is rank-one, so its nuclear norm is |ci | ∥xi ∥ , and the triangle inequality with ∥xi ∥ ≤ ζ (Assumption 1) gives ∥∇2 FT (w) − ∇2 FT (w′ )∥∗ ≤

n

n

i=1

i=1

1X L3 ∥w − w′ ∥ X |ci | ∥xi ∥2 ≤ ∥xi ∥3 ≤ L3 ζ 3 ∥w − w′ ∥. n n

Remark B.3. Lemma B.2 removes the dimension d from that contribution. For a general symmetric A ∈ Rd×d one has only ∥A∥∗ ≤ d ∥A∥, and this is tight. The GLM Hessian perturbation, being a sum of rank-one terms with individually controlled coefficients, instead obeys in nuclear norm the bound one would expect only in operator norm, eliminating the factor of d. 26

Carrying this through Proposition A.11 bounds the nuclear norm of the Jacobian error by the same quantity as its operator norm—the form the log-determinant analysis of Appendix C.2 requires. We state it per dataset T ∈ {S, S ′ }. Here and below, FT := F (· ; T ); each FT satisfies Assumptions 4 and 5 with the uniform constants of Section 3.1, so every result of Appendix A holds for FT , and we cite those results for FT directly. Likewise RT (z) denotes the trajectory scale (15) of FT , and w∗,T (z) its perturbed minimizer (Lemma A.2)—the objects written R(z) and w∗ (z) when a single dataset is in scope. Lemma B.4 (Nuclear norm of the Jacobian perturbation error). Fix T ∈ {S, S ′ } and a perturbation T := zT , and write RT := RT (zT ) for the trajectory scale (15) of FT , CT := ηM RT B, and δN T T ˜ JN (zT ) − JN for the Jacobian error of Lemma A.10 applied to FT . Under Assumptions 1, 3 and 4, T ∥δN ∥∗ ≤ CT ν̃N ρN −1 ,

with ν̃N as in (22). Proof. Lemma B.2 makes the Hessian of FT M -Lipschitz in nuclear norm for any M ≥ L3 ζ 3 , which is the hypothesis of Proposition A.11 at ∥ · ∥⋄ = ∥ · ∥∗ . Applying that proposition to FT at zT gives the claim, with C(zT ) = CT . A further structural fact, again from the rank-one form of GLM gradients, makes the leading Gaussian-ratio term of Appendix C.1 dimension free: the gradient difference between neighboring datasets is confined to a fixed subspace of dimension at most two. Lemma B.5 (Gradient subspace structure). In the GLM setting, for neighboring datasets S, S ′ differing in the n-th sample, the gradient difference ∇FS (w)−∇FS ′ (w) lies in V := span{xn , x′n }, a subspace of dimension at most 2, for every w ∈ Rd . Moreover Assumption 6 holds with G = 2L1 ζ/n. Proof. The per-sample gradients in (1) agree except at the n-th sample, and the regularizer gradient cancels (the regularizer is dataset-independent), so ∇FS (w) − ∇FS ′ (w) =

 1 ′ ℓ (⟨xn , w⟩, yn ) xn − ℓ′ (⟨x′n , w⟩, yn′ ) x′n , n

which lies in span{xn , x′n }. The triangle inequality with |ℓ′ | ≤ L1 (Assumption 2) and ∥xn ∥, ∥x′n ∥ ≤ ζ (Assumption 1) gives ∥∇FS (w) − ∇FS ′ (w)∥ ≤

2L1 ζ 1 L1 ∥xn ∥ + L1 ∥x′n ∥ ≤ , n n

which is Assumption 6 with G = 2L1 ζ/n. The subspace V confines the gradient difference. The feature span C of (2) confines the mechanism itself, and V ⊆ C. Write dC := dim C ≤ d⋆ and z = zC + zC ⊥ for the orthogonal decomposition of z ∈ Rd . Lemma B.6 (Data-span reduction). Let C be as in (2) and let BN = (1 − ρN )/µ > 0 be as in item 2 of Lemma A.9. For each T ∈ {S, S ′ }: 1. MT (z) = MCT (zC )−BN zC ⊥ , where MCT is the mechanism of Section 3.2 run on the restriction FT |C within C. The second summand is independent of both the dataset and zC . A fixed public initialization w0 ̸= 0 adds the dataset-independent term ρN ΠC ⊥ w0 .

27

T,C T (z) v = J T,C (z ) v − B v d C 2. JN C C N C ⊥ for every v ∈ R , where JN is the Jacobian of MT . N

3. FT |C is again an empirical risk (1), on the features xi read in C and with the same ℓ, ζ, µ; so it satisfies Assumptions 1 to 3, and with them Assumptions 4 and 5 with the same µ, L, M , while the pair FS |C , FS ′ |C satisfies Assumption 6 with the same G. Proof. Throughout, ∇2 FT (w) maps C into C and acts on C ⊥ as µI, at every w: by (1), ∇2 FT (w) = 1 P ′′ ⊤ ⊤ i ℓ (⟨xi , w⟩, yi ) xi xi + µI, and every xi ∈ C, so each xi xi has range in C while ⟨xi , v⟩ = 0 for n ⊥ ⊤ v ∈ C makes xi xi v = 0; µI preserves both subspaces. P ′ (⟨xi , w⟩, yi ) xi + µw. Since xi ∈ C, projecting Item 1. Differentiating (1), ∇FT (w) = n1 i ℓP gives ΠC ⊥ ∇FT (w) = µ ΠC ⊥ w and ΠC ∇FT (w) = n1 i ℓ′ (⟨xi , w⟩, yi ) xi + µ ΠC w, which depends on w only through ΠC w because ⟨xi , w⟩ = ⟨xi , ΠC w⟩. Projecting (4) therefore yields two recursions that do not communicate,
ΠC wk+1 = ΠC wk − η ∇(FT |C )(ΠC wk ) + zC , ΠC ⊥ wk+1 = ρ ΠC ⊥ wk − η zC ⊥ , both started at 0 since w0 = 0. The first is (4) for FT |C within C, so ΠC wN = MCT (zC ). The second
P η(1−ρN ) k zC ⊥ = −BN zC ⊥ , using 1 − ρ = ηµ; started unrolls to ΠC ⊥ wN = −η k<N ρ zC ⊥ = − 1−ρ N instead at w0 , it unrolls to ρ ΠC ⊥ w0 − BN zC ⊥ . As ρ ∈ (0, 1) and N ≥ 1, BN > 0. Item 2. Differentiate item 1 in z, using that z 7→ zC and z 7→ zC ⊥ are the linear maps ΠC and ΠC ⊥ . Item 3. WritingPQ for a matrix whose columns are an orthonormal basis of C, the restriction reads FT |C (·) = n1 i ℓ(⟨Q⊤ xi , ·⟩, yi ) + µ2 ∥ · ∥2 , since ⟨xi , Q ·⟩ = ⟨Q⊤ xi , ·⟩. This is (1) in C, and ∥Q⊤ xi ∥ = ∥xi ∥ ≤ ζ because xi ∈ C, so Assumptions 1 to 3 hold there with the same constants; Lemma B.5 and the bounds of Appendix B follow for the restricted pair, as does ∥∇(FT |C )(0)∥ ≤ L1 ζ. For the general-setting assumptions, fix w, v ∈ C. By the splitting above and symmetry of ∇2 FT (w), the orthogonal splitting Rd = C ⊕ C ⊥ is invariant, so the spectrum of ∇2 (FT |C )(w)—the restriction of ∇2 FT (w) to C—is contained in that of ∇2 FT (w), hence in [µ, L] by Assumption 4: this is Assumption 4 for FT |C . Restricting an operator does not increase its norm, so ∥∇2 (FT |C )(w) − ∇2 (FT |C )(v)∥ ≤ ∥∇2 FT (w)−∇2 FT (v)∥
≤ M ∥w −v∥, which is Assumption 5. Finally ∇(FS |C )(w)− ∇(FS ′ |C )(w) = ΠC ∇FS (w) − ∇FS ′ (w) , and the difference lies in V ⊆ C by Lemma B.5, so ΠC fixes it and its norm is still at most G.

C

Privacy

We analyze the mechanism that releases y = MS (z) for z ∼ N (0, σ 2 Id ). Throughout this section Assumptions 4 and 5 hold uniformly across datasets with common constants µ, L, M , Assumption 6 is a cross-dataset condition by definition, and supS ∥∇F (0; S)∥ < ∞, so that the constants of Lemma A.6 are uniform in S, with aR = µ−1 supS ∥∇F (0; S)∥ and bR = 1/µ. Convention 1 (Closed restriction). For a bounded convex set D, “MT is a C 1 -diffeomorphism on D” abbreviates the statement that MT restricts to D from a C 1 -diffeomorphism on a convex open neighborhood of D, as furnished by Corollary 4.4; for open D this is Corollary 4.4 itself. Fix neighboring datasets S, S ′ and a bounded convex set Ω on which both MS and MS ′ are C 1 -diffeomorphisms (Convention 1). For y ∈ MS (Ω) with preimage zS := M−1 S (y) ∈ Ω, the change-of-variables formula (Lemma E.5) expresses the contribution to the output density from preimages in Ω as pZ (zS ) , pSY (y; Ω) := S (z )| | det JN S 28

where pZ is the N (0, σ 2 Id ) density. When y also has a preimage zS ′ := M−1 S ′ (y) ∈ Ω, the restricted privacy loss splits into two terms: ′

log

S (z ′ )| pSY (y; Ω) | det JN pZ (zS ) S = log . + log ′ S (z )| pZ (zS ′ ) | det JN pSY (y; Ω) S | {z } | {z } Gaussian ratio

(23)

Jacobian ratio

Both terms are already confined to C. If y = MS (zS ) = MS ′ (zS ′ ), item 1 of Lemma B.6 gives BN ΠC ⊥ zS = BN ΠC ⊥ zS ′ and hence ΠC ⊥ zS = ΠC ⊥ zS ′ , so the C ⊥ components cancel from the GausT,C sian ratio (∥zS ′ ∥2 − ∥zS ∥2 )/(2σ 2 ); and item 2 factors each determinant as det JN (zC ) · (−BN ) d−dC , whose second factor is common to the two datasets and cancels from the Jacobian ratio. What (23) measures is therefore the privacy loss of the pair MCS , MCS ′ , which by item 3 is a mechanism of Appendix A.1 within C carrying the same µ, L, M, G, driven by the perturbation ΠC Z ∼ N (0, σ 2 IdC ), again isotropic. Every result of Appendices A and B applies to it with dC in place of d, and the ambient dimension survives only in the C ⊥ block, which multiplies both densities by the same factor. We treat the Gaussian ratio in Appendix C.1 using the two-dimensional gradient subspace from Lemma B.5, and we treat the Jacobian ratio in Appendix C.2 using the nuclear-norm bounds from Appendix B. The residual terms depend on the trajectory scale over the truncation domain and decrease with N . Choosing N according to (7) makes these residual terms small enough to obtain the dimension-free bound in Theorem 4.1. Section C.3 combines the pointwise estimates with Gaussian truncation and the hockey-stick divergence.

C.1

The Gaussian-ratio bound

The Gaussian ratio in (23) is log[pZ (zS )/pZ (zS ′ )] = (∥zS ′ ∥2 − ∥zS ∥2 )/(2σ 2 ), so bounding it amounts to controlling how far the two preimages of a shared output can differ. We build up to a bound whose only randomness is the projection factor of Proposition C.3 (Theorem C.4). The trajectories under neighboring datasets separate by at most G/µ (Lemma A.7); what remains is to invert the relation between z and y = M(z). The next identity expresses the perturbation z through the gradient at the output, up to a residual that decays geometrically in N . We state it for a generic objective F with mechanism M; it applies verbatim to both F (· ; S) and F (· ; S ′ ). Lemma C.1 (One-step residual identity). Let z ∈ Rd , let w0 , w1 , . . . , wN be the iterates (4), and set y := M(z) = wN . With H̄ the averaged Hessian H̄(y, wN −1 ) of Lemma A.1 over the final step, one has   (24) z = −∇F (y) + ξF (z), ξF (z) := η1 I − H̄ (wN −1 − y), and, under Assumption 4, ∥ξF (z)∥ ≤ µ ρN R(z),

R(z) the trajectory scale of Lemma A.6.

(25)

Proof. The final step of (4) reads y = wN −1 − η(∇F (wN −1 ) + z), so ∇F (wN −1 ) + z =

wN −1 − y . η

(26)

By item 1 of Lemma A.1, ∇F (y) − ∇F (wN −1 ) = H̄ (y − wN −1 ). Adding ∇F (wN −1 ) + z to both sides and using (26),   wN −1 − y ∇F (y) + z = + H̄ (y − wN −1 ) = η1 I − H̄ (wN −1 − y), η 29

which rearranges to (24). For (25) we bound the two factors of ξF (z). The second is a single step of the iteration, wN −1 − y = wN −1 − wN , so item 2 of Lemma A.6 at k = N − 1 gives ∥wN −1 − y∥ ≤ ηµ ρN −1 R(z).
The first factor is η1 I − η H̄ , of norm at most ρ/η by item 2 of Lemma A.1. Multiplying the two bounds, ρ ∥ξF (z)∥ ≤ · ηµ ρN −1 R(z) = µ ρN R(z). η To compare the two preimages of a common output we use the conjugacy map. Fix the bounded convex set Ω introduced above, and assume it is chosen so that Ω ⊆ Ω′ and MS (Ω) ⊆ MS ′ (Ω′ ) for some bounded convex set Ω′ on which MS ′ is a C 1 -diffeomorphism (Convention 1); this strengthens the standing assumption to cover Ω′ , and Appendix C.3 constructs such a pair explicitly. Then ′ Φ := M−1 S ′ ◦ MS : Ω → Ω ,

MS ′ (Φ(z)) = MS (z) for all z ∈ Ω,

is well-defined and sends each z to the MS ′ -preimage of the same output MS (z). We abbreviate M := MS , M′ := MS ′ , F := F (· ; S), F ′ := F (· ; S ′ ), and set RΩ′ :=

sup z∈Ω′ , T ∈{S,S ′ }

RT (z),

the largest trajectory scale over Ω′ for either dataset, finite by Lemma A.6 since Ω′ is bounded. As z ∈ Ω ⊆ Ω′ and Φ(z) ∈ Ω′ , both RS (z) and RS ′ (Φ(z)) are at most RΩ′ . We also fix a radius r > 0 with the closed ball {z : ∥z∥ ≤ r} ⊆ Ω. These standing choices constitute the hypotheses of Appendix C.1. Corollary C.2 (Preimage difference). For z ∈ Ω, set z ′ := Φ(z) and y := M(z) = M′ (z ′ ), and define g(y) := ∇F (y) − ∇F ′ (y), ξ∆ := ξF (z) − ξF ′ (z ′ ). Then z − z ′ = −g(y) + ξ∆ ,

(27)

∥ξ∆ ∥ ≤ µρN RS (z) + RS ′ (z ′ ) ≤ 2µρN RΩ′ .

(28)

with ∥g(y)∥ ≤ G by Assumption 6 and

Proof. Lemma C.1 applied to (z, F ) gives z = −∇F (y) + ξF (z), since y = M(z). Applied to (z ′ , F ′ ) it gives z ′ = −∇F ′ (M′ (z ′ )) + ξF ′ (z ′ ) = −∇F ′ (y) + ξF ′ (z ′ ), since M′ (z ′ ) = y by conjugacy. Subtracting,

z − z ′ = − ∇F (y) − ∇F ′ (y) + ξF (z) − ξF ′ (z ′ ) = −g(y) + ξ∆ . The bound ∥g(y)∥ ≤ G is Assumption 6 for the neighboring pair S, S ′ . For (28), the triangle inequality and the residual bound (25)—with the constants L, ρ common to F and F ′ —applied to ξF (z) and to ξF ′ (z ′ ) give ∥ξ∆ ∥ ≤ µρN RS (z) + µρN RS ′ (z ′ ), and both terms are at most µρN RΩ′ by the definition of RΩ′ . We now pass to the random perturbation. Let Z ∼ N (0, σ 2 Id ). On the event {Z ∈ Ω} set := M(Z), so the S- and S ′ -preimages of Y are Z and Z ′ , and the Gaussian ratio in (23) is log[pZ (Z)/pZ (Z ′ )] = (∥Z ′ ∥2 − ∥Z∥2 )/(2σ 2 ). With g, ξ∆ as in Corollary C.2, the Z ′ := Φ(Z) and Y

30

conjugacy applies on {Z ∈ Ω} and gives Z ′ = Z + g(Y ) − ξ∆ . For the exact-minimizer map, the optimality condition gives a preimage difference of exactly g(Y ). We therefore add and subtract Z + g(Y ) in the finite-iterate Gaussian ratio, separating the exact-minimizer contribution from the residual −ξ∆ : Λ(Z) :=

∥Z ′ ∥2 − ∥Z + g(Y )∥2 ∥Z ′ ∥2 − ∥Z∥2 ∥Z + g(Y )∥2 − ∥Z∥2 + , = 2 2 2σ 2 2σ 2σ {z } {z } | | (A)

(29)

(B)

whose terms are (A) = ⟨g(Y ), 2Z + g(Y )⟩/(2σ 2 ), the Gaussian ratio the exact-minimizer displacement alone produces, and (B) = −⟨ξ∆ , 2Z + 2g(Y ) − ξ∆ ⟩/(2σ 2 ), which vanishes with the residual. By Lemma B.5, g(Y ) lies in span{xn , x′n }. We therefore control ⟨Z, g(Y )⟩ through the two scalar projections ⟨Z, xn ⟩ and ⟨Z, x′n ⟩, without introducing an ambient-dimension factor. Proposition C.3 (Bound on Term (A)). Write U := ⟨Z, xn ⟩/σ and U ′ := ⟨Z, x′n ⟩/σ for the two scalars the differing samples read off the perturbation, and put T :=

|U | + |U ′ | . 2ζ

(30)

Then (31) holds on {Z ∈ Ω}: |⟨g(Y ), 2Z + g(Y )⟩| G G2 ≤ T + , 2σ 2 σ 2σ 2

(31)

and, unconditionally, T is the midpoint average of two folded Gaussians whose scales the features bound:  |U | |U ′ | 
∥xn ∥2
∥x′ ∥2 T = 12 + , Var U/ζ = ≤ 1, Var U ′ /ζ = n2 ≤ 1, (32) 2 ζ ζ ζ ζ with no independence of U and U ′ assumed. Proof. The inner product expands as ⟨g(Y ), 2Z + g(Y )⟩ = 2⟨Z, g(Y )⟩ + ∥g(Y )∥2 . Lemma B.5 gives g(Y ) explicitly as n1 [ℓ′ (⟨xn , Y ⟩, yn ) xn − ℓ′ (⟨x′n , Y ⟩, yn′ ) x′n ], so only two scalars of the perturbation are read, and |ℓ′ | ≤ L1 (Assumption 2) with G = 2L1 ζ/n gives |⟨Z, g(Y )⟩| ≤

L1 σ
L1 |⟨Z, xn ⟩| + |⟨Z, x′n ⟩| = |U | + |U ′ | = G σ T . n n

(33)

With ∥g(Y )∥ ≤ G (Corollary C.2), |⟨g(Y ), 2Z + g(Y )⟩| ≤ 2GσT + G2 ; dividing by 2σ 2 gives (31). The two scalars are bounded separately rather than through the norm of the projection of Z onto V (Lemma B.5), which leaves a single Gaussian degree of freedom in play; Cauchy–Schwarz against that norm would charge two. For (32), the first display is (30) rearranged, and U = ⟨Z, xn ⟩/σ is centred Gaussian with Var U = ∥xn ∥2 ≤ ζ 2 (Assumption 1), likewise U ′ . We control Term (B) using ∆Ω′ := 2µρN RΩ′ , which bounds ∥ξ∆ ∥ on {Z ∈ Ω} by (28). We do not have a corresponding low-dimensional representation for ξ∆ , so we bound its inner product using ∥Z∥ and the truncation radius. Assembling the two terms gives the Gaussian-ratio bound, which holds at every point of the ball rather than with high probability. The projection factor T is carried forward as a random variable rather than replaced by a high-probability value, because Appendix C.3 integrates against its law, which for G ≤ σ costs less than charging its tail. 31

Theorem C.4 (Gaussian-ratio bound). Under the hypotheses of Appendix C.1, let Z ∼ N (0, σ 2 Id ) and let T be as in (30). Then, on the event E1 := {∥Z∥ ≤ r}, the point Φ(Z) is defined and r∆Ω′ (G + ∆Ω′ )2 G ∥Φ(Z)∥2 − ∥Z∥2 T + + . ≤ 2σ 2 σ σ2 2σ 2

(34)

Proof. On E1 we have ∥Z∥ ≤ r, hence Z ∈ Ω (as {z : ∥z∥ ≤ r} ⊆ Ω), so Φ(Z) is defined and the decomposition (29) holds. By the triangle inequality, ∥Φ(Z)∥2 − ∥Z∥2 |⟨g(Y ), 2Z + g(Y )⟩| |⟨ξ∆ , 2Z + 2g(Y ) − ξ∆ ⟩| + . = |Λ(Z)| ≤ 2 2σ 2σ 2 2σ 2 Since E1 ⊆ {Z ∈ Ω}, Proposition C.3 bounds the first term by (G/σ)T + G2 /(2σ 2 ). For the second, Corollary C.2 gives ∥ξ∆ ∥ ≤ ∆Ω′ (by (28)) and ∥g(Y )∥ ≤ G, so ∥2Z + 2g(Y ) − ξ∆ ∥ ≤ 2r + 2G + ∆Ω′ by the triangle inequality and |⟨ξ∆ , 2Z + 2g(Y ) − ξ∆ ⟩| ≤ ∆Ω′ (2r + 2G + ∆Ω′ ) by Cauchy–Schwarz; dividing by 2σ 2 and separating the term in r bounds it by r∆Ω′ /σ 2 + (2G∆Ω′ + ∆2Ω′ )/(2σ 2 ). Their sum is (G/σ)T + r∆Ω′ /σ 2 + (G2 + 2G∆Ω′ + ∆2Ω′ )/(2σ 2 ), and the last numerator is (G + ∆Ω′ )2 , which gives (34).

C.2

Log-determinant sensitivity

We now bound the Jacobian ratio in (23) for GLMs. For T ∈ {S, S ′ } and perturbation zT , write T for the frozen-Hessian Jacobian and δ T := J T (z ) − J˜T . Using the geometric-sum form from J˜N N N T N Lemma A.8, we write T T −JN (zT ) = PNT − δN ,

PNT := η

N −1 X

T (A∗T )j = −J˜N = pN (HT∗ ),

(35)

j=0

P −1 j T ∗ −1 ∗ N where pN (h) := η N j=0 (1 − ηh) . The frozen factor also has the form PN = (HT ) (I − (AT ) ) and therefore converges to the exact-minimizer Jacobian (HT∗ )−1 . We bound the remaining error T by O(ν̃ ρN −1 ) through Lemma B.4. The argument below compares the two frozen factors at δN N the shared output and then adds the finite-N correction. Let zS and zS ′ satisfy MS (zS ) = MS ′ (zS ′ ) =: w. Each reference Hessian is read at its own S = M (z ) = w = M ′ (z ′ ) = w S ′ , so H ∗ = dataset’s N -th iterate, and those coincide: wN S S S S S N ∇2 FS (w) and HS∗ ′ = ∇2 FS ′ (w) are the two datasets’ Hessians at one and the same point. The reference Hessians therefore differ only in the sample the datasets do not share, and the determinant comparison is a dataset swap at a fixed point of evaluation. The two Jacobians are compared through the polynomial pN of (35), so what governs the comparison is how log pN responds to the curvature. Its logarithmic derivative factors as a bounded multiple of the logarithmic derivative of h 7→ 1/h, the exact-minimizer case. Lemma C.5 (Log-derivative of the frozen symbol). Let ϕN := log pN on [µ, L], with pN as in (35); for NP≥ 1 it is well defined there, since 1 − ηh ≥ 0 on [µ, L] makes every summand of pN (h) = η j<N (1 − ηh)j nonnegative and its j = 0 term equal to η, so pN ≥ η > 0. Then ϕ′N (h) = −gN (h)/h with 0 ≤ gN (h) ≤ 1 − (1 − ηh)N −1

for all h ∈ [µ, L],

and consequently ḡN := sup gN ≤ 1 − (1 − ηL)N −1 ≤ 1. [µ,L]

32

Proof. Write a := 1 − so that a ∈ [1 − ηL, ρ] ⊆ [0, ρ] for h ∈ [µ, L], by ηL ≤ 1 (Section 3.2). Pηh, N −1 j Abbreviate D(a) := j=0 a , so pN (h) = ηD(a) and, by the chain rule in h, p′N (h) = −η 2 D′ (a). Hence ϕ′N (h) = p′N (h)/pN (h) = −ηD′ (a)/D(a), and since ηh = 1 − a, −h ϕ′N (h) =

(1 − a) D′ (a) =: gN (h). D(a)

Differentiating the identity (1 − a)D(a) = 1 − aN gives (1 − a)D′ (a) = D(a) − N aN −1 , so
PN −1 j N −1 N aN −1 j=0 a − a gN (h) = 1 − = . PN −1 j D(a) j=0 a

(36)

Every summand of the numerator is nonnegative, since a ∈ [0, 1] and j ≤ N −1, and the denominator is positive; this gives gN ≥ 0. For the upper bound, gN ≤ 1 − aN −1 rearranges to aN −1 D(a) ≤ N aN −1 , which holds because D(a) ≤ N , each of its N summands being at most 1. The map a 7→ 1 − aN −1 is nonincreasing on [0, 1], so over h ∈ [µ, L] it is largest at a = 1 − ηL, giving the bound on ḡN , which is at most 1 since (1 − ηL)N −1 ≥ 0. At a shared output, both Hessians are rank-one updates of the same matrix formed by the regularizer and the n − 1 common samples. Comparing each update to this common matrix gives the determinant ratio in one step. Replacing − log h by ϕN (h) = log pN (h) introduces the factor ḡN from Lemma C.5. Lemma C.6 (Reference determinant ratio). Under Assumptions 1 to 3, let zS and zS ′ satisfy MS (zS ) = MS ′ (zS ′ ). Then, for every N ≥ 1, log

 det PNS ∆H  ≤ ḡ log 1 + , N ′ 2nµ det PNS

(37)

with ḡN as in Lemma C.5. Proof. Since PNT = pN (HT∗ ) and ϕN = log pN , we have log det PNT = tr ϕN (HT∗ ), so log

det PNS ∗ ∗ ′ = tr ϕN (HS ) − tr ϕN (HS ′ ), det PNS

(38)

a dataset swap at the shared output w, both Hessians being read there. Every Hessian appearing here has spectrum in [µ, L] (Assumption 4), as does the anchor H0 introduced next. Since S and S ′ agree on the first n−1 samples and share the regularizer, both HS∗ and HS∗ ′ —read at the same point w—are rank-one updates of the common matrix n−1

H0 :=

1 X ′′ ℓ (⟨xi , w⟩, yi ) xi x⊤ i + µI ⪰ µI, n i=1

the sum being positive semidefinite by ℓ′′ ≥ 0 (Assumption 2), so H0 ⪰ µI; and H0 ⪯ LI, since 2 ∇2 FS (w) − H0 = n1 ℓ′′ (⟨xn , w⟩, yn ) xn x⊤ n ⪰ 0, so H0 ⪯ ∇ FS (w) ⪯ LI by Assumption 4. Because both are read at w, the two datasets contribute the same H0 ; explicitly, HS∗ = H0 + uu⊤ and HS∗ ′ = H0 + u′ u′⊤ with q q u′ := n1 ℓ′′ (⟨x′n , w⟩, yn′ ) x′n , u := n1 ℓ′′ (⟨xn , w⟩, yn ) xn , 33

the square roots being real by ℓ′′ ≥ 0. Apply item 2 of Lemma E.9 with ϕ = ϕN , whose derivative has the required form −gN (h)/h with 0 ≤ gN ≤ ḡN by Lemma C.5; with u⊤ H0−1 u ≤ ∥u∥2 /µ ≤ L2 ζ 2 /(nµ) = ∆H /(2nµ), using 0 ≤ ℓ′′ ≤ L2 , ∥xn ∥ ≤ ζ and ∆H = 2L2 ζ 2 ,  ∆H  −ḡN log 1 + ≤ tr ϕN (HS∗ ) − tr ϕN (H0 ) ≤ 0, 2nµ and the same for HS∗ ′ . The right-hand side of (38) is the difference of two quantities lying in that one interval, hence is at most ḡN log(1 + ∆H /(2nµ)) in absolute value, which is (37). Lemma B.4 bounds each error term in nuclear norm: writing βN := (CS + CS ′ ) ν̃N ρN −1 ,

(39)

′

S ∥ + ∥δ S ∥ ≤ β . we have ∥δN ∗ N N ∗ One quantity organizes the final argument: feasibility of N , the single condition under which the analysis runs. We state it uniformly over a bounded set, so that it applies at every preimage in it.

Definition C.7 (Feasibility). For a bounded set D ⊂ Rd , write RD :=

sup z∈D, T ∈{S,S ′ }

RT (z),

CD := ηM RD B,

αD := γN − CD ν̃N ρN −1 ,

extending the single-objective domain constant of Lemma A.6 to range over both datasets (at D = Ω′ this is the RΩ′ of Appendix C.1); the constant of each FT alone is at most RD , so the conclusions of Appendix A applied to FT on D hold a fortiori with CD and αD in place of their single-objective counterparts. We say N is feasible for D if αD > 0; written out this reads CD ν̃N ρN −1 < γN . Since γN → 1/L > 0 and CD ν̃N ρN −1 → 0 as N → ∞, feasibility holds for all sufficiently large N . The estimates assemble into the finite-N correction that, together with the reference term τ (0) of Lemma C.6, enters the Jacobian-ratio bound of Theorem C.9. Definition C.8 (Finite-N correction). For N feasible for a bounded set Ω′ containing the preimages zS , zS ′ , βN τ (corr) := , (40) αΩ′ well-defined since feasibility gives αΩ′ > 0. The dimension dependence of βN and αΩ′ —carried by RΩ′ in both—is controlled in Theorem 4.1. We can now bound the log-determinant sensitivity, with a leading term free of dimension. Theorem C.9 (Dimension-free log-determinant sensitivity). Under Assumptions 1 to 3, with step size satisfying 0 < η ≤ 1/L and ηµ < 1 (Section 3.2), let Ω′ be a bounded convex set, and let N ≥ 1 be feasible for Ω′ , that is αΩ′ > 0 (Definition C.7); the margin αΩ′ > 0 makes MS and MS ′ C 1 -diffeomorphisms onto their images on Ω′ (Lemma C.11). For an output w with preimages −1 ′ zS = M−1 S (w) and zS ′ = MS ′ (w) in Ω , set  ∆H  , τ := τ (0) + τ (corr) (41) τ (0) := ḡN log 1 + 2nµ with τ (corr) as in Definition C.8. Then log

S (z )| | det JN S ≤ τ. S ′ (z ′ )| | det JN S

34

(42)

T = P T −δ T = P T (I −Ψ ) with Ψ := (P T )−1 δ T , for each Proof. Exact factorization. By (35), −JN T T N N N N N T is symmetric with σ T T ∈ {S, S ′ }; the inverse exists because PNT = −J˜N min (PN ) ≥ γN > 0 (item 3 of Lemma A.9). Its eigenvalues are the pN (hi ) ≥ η > 0 of Lemma C.5, which the singular-value floor alone would not sign, so det PNT > 0. The factors (−1)d in the two determinants cancel, and S (z )| det PNS | det(I − ΨS )| | det JN S = . ′ ′ · S (z ′ )| | det JN det PNS | det(I − ΨS ′ )| S

(43)

We bound the frozen-Hessian ratio using Lemma C.6 and the second ratio using the finite-N Jacobian error. Size of the error matrices. For T ∈ {S, S ′ }, by ∥(PNT )−1 ∥ ≤ 1/γN and Proposition A.11, ∥ΨT ∥ ≤

T∥ ∥δN CT ν̃N ρN −1 CΩ′ ν̃N ρN −1 ≤ ≤ =: ψ, γN γN γN

∥ΨT ∥∗ ≤

T∥ ∥δN ∗ , γN

the nuclear bound by Lemma B.4 and ∥XY ∥∗ ≤ ∥X∥ ∥Y ∥∗ (Lemma E.7), and CT ≤ CΩ′ in both. Feasibility is exactly CΩ′ ν̃N ρN −1 < γN , so ψ < 1 and each I − ΨT is invertible with ∥(I − ΨT )−1 ∥ ≤ (1 − ψ)−1 (Lemma E.6 and summation of the geometric series). Moreover γN (1 − ψ) = γN − CΩ′ ν̃N ρN −1 = αΩ′ . ′ Reference factor. Lemma C.6 bounds log(det PNS / det PNS ) by τ (0) . Error factor. Applying (57) of Lemma E.8 to K = −ΨT gives log | det(I − ΨT )| ≤ ∥ΨT ∥∗ , and applying it instead to (I − ΨT )−1 − I = ΨT (I − ΨT )−1 gives − log | det(I − ΨT )| = log det I + ΨT (I − ΨT )−1

≤ ∥ΨT ∥∗ ∥(I − ΨT )−1 ∥ ≤

∥ΨT ∥∗ , 1−ψ

so log | det(I − ΨT )| ≤ ∥ΨT ∥∗ /(1 − ψ) for each T . Summing the two and using the error bounds above, S′ ∥ ∥δ S ∥∗ + ∥δN | det(I − ΨS )| βN ∗ log ≤ ≤ N = τ (corr) , | det(I − ΨS ′ )| γN (1 − ψ) αΩ′ by (39) and γN (1 − ψ) = αΩ′ . Both directions. Taking logarithms in (43) and adding the two bounds gives log

S (z )| | det JN S ≤ τ (0) + τ (corr) = τ, S ′ (z ′ )| | det JN S

which is (42).

C.3

The differential privacy guarantee

We assemble the differential privacy guarantee by combining the Gaussian-ratio bound (Theorem C.4) and the log-determinant bound (Theorem C.9) with two further devices: a truncation confining the perturbation to a bounded domain, and a divergence calculation pricing the projection factor the Gaussian-ratio bound leaves random (Lemma C.12). We first record how the restricted output density enters the accounting. Remark C.10. For a bounded measurable set Ω contained in an open set on which MS is a C 1 diffeomorphism, and y ∈ MS (Ω) with preimage zS = M−1 S (y) ∈ Ω, the change-of-variables formula (Lemma E.5) gives the contribution to the output density from preimages in Ω as pSY (y; Ω) = S (z )|: for every measurable E, the probability Pr[M (Z) ∈ E, Z ∈ Ω] is pS (· ; Ω) pZ (zS )/| det JN S S Y integrated over E ∩ MS (Ω). The truncation in Theorem C.13 works entirely with this restricted density. 35

The margin αD > 0 of Definition C.7 is certified on the domain itself, while Corollary 4.4 requires an open domain; the next lemma bridges the two, and is what the phrase “diffeomorphism on a bounded convex set” of Appendix C rests on. Lemma C.11 (Feasibility yields a diffeomorphism). Let D ⊂ Rd be a bounded convex set with αD > 0 (Definition C.7). Then there is a bounded convex open set B ⊇ D on which MS and MS ′ are C 1 -diffeomorphisms onto their images; in particular, both maps are diffeomorphisms on D in the sense of Convention 1. Proof. For s > 0 let Ds := {z : dist(z, D) < s}, the Minkowski sum of D with the open ball of radius s—a bounded convex open set containing D. For each T ∈ {S, S ′ } the map z 7→ RT (z) is (1/µ)-Lipschitz by (15), and every point of Ds lies within distance s of D, so RDs ≤ RD + s/µ and hence αDs ≥ αD − ηM B µs ν̃N ρN −1 .
If ν̃N ρN −1 = 0 any s > 0 serves; otherwise every s < αD / ηM Bµ−1 ν̃N ρN −1 keeps αDs > 0. Fix such an s and set B := Ds . For each T , the single-objective margin of FT on B is at least αB > 0 (Definition C.7), so Corollary 4.4 applied to FT makes MT a C 1 -diffeomorphism of B onto its image; since D ⊆ B, both maps restrict to D from diffeomorphisms on the convex open neighborhood B. We handle the two random contributions differently. We truncate the perturbation to Ω0 and add the probability of its complement directly to δ. For the projection variable T in (30), we keep the pointwise privacy-loss bound and integrate it in the hockey-stick divergence. Its folded-Gaussian representation in (32) gives the closed-form bound in Lemma C.12. Lemma C.12 (Divergence against a folded-Gaussian average). Let T = 12 (a|W | + a′ |W ′ |) for standard Gaussians W, W ′ under any joint law and constants a, a′ ∈ [0, 1], and let λ > 0 and t ≥ 0. Writing φ for the standard normal density, Q(x) := Pr(N (0, 1) > x), and Z ∞ Q1 (t) := Q(x) dx = φ(t) − t Q(t) (44) t

for the once-integrated tail, h
i E 1 − e−λ(T −t) + ≤ 2λ Q1 (t).

(45)

The constant is attained: at a = a′ = 1 with W ′ = W , the left side is 2λ Q1 (t) (1 + o(1)) as λ → 0, at every t ≥ 0. Proof. For every real v one has (1 − e−v )+ ≤ v+ : at v ≥ 0 this is the elementary 1 − e−v ≤ v, and at v < 0 both sides vanish. With v = λ(T − t), so that v+ = λ(T − t)+ since λ > 0, h
i   (46) E 1 − e−λ(T −t) + ≤ λ E (T − t)+ . Three pointwise facts bound the expectation on the right. Convexity of x 7→ (x − t)+ splits the average, (T − t)+ ≤ 21 (a|W | − t)+ + 12 (a′ |W ′ | − t)+ . Next, (a|W | − t)+ ≤ a (|W | − t)+ for a ∈ [0, 1] and t ≥ 0: if |W | ≤ t both sides vanish, since a|W | ≤ at ≤ t; if |W | > t then a|W | − t ≤ a(|W | − t), and the right side is nonnegative. Finally, for a standard Gaussian the layer cake evaluates exactly, Z ∞ Z ∞   E (|W | − t)+ = Pr(|W | > x) dx = 2 Q(x) dx = 2 Q1 (t), t

t

36

d [φ(a) − aQ(a)] = −aφ(a) − Q(a) + aφ(a) = −Q(a) and the closed form in (44) following from da both sides vanishing at a = ∞. Taking expectations and assembling,

  a + a′ E (T − t)+ ≤ · 2 Q1 (t) ≤ 2 Q1 (t), 2 which against (46) gives (45). No step reads the joint law: the first two facts are pointwise and the third is a computation on one marginal. For the attainment, at a = a′ = 1 and W ′ = W both pointwise inequalities are equalities and E[(T − t)+ ] = 2 Q1 (t) exactly; only the linearization (1 − e−v )+ ≤ v+ then separates the two sides of (45), and it is an equality to leading order as λ → 0. Theorem C.13 (Differential privacy: exact finite-N form). Let Assumptions 1 to 3 hold. Fix a radius r > 0, set Ω0 := {z : ∥z∥ ≤ r}, and let Ω′ := {z : ∥z∥ ≤ r′ } for a radius r′ satisfying, with the uniform trajectory scale R̄ := (r′ + L1 ζ)/µ, the fixed-point inequality r′ ≥ r +

G(1 − ρN ) , µ ᾱ

ᾱ := γN − ηM R̄B ν̃N ρN −1 > 0.

(47)

Such r′ exists for all sufficiently large N (Remark C.14). Write ∆ξ := 2µρN R̄,

τ := τ (0) +

2ηM R̄B ν̃N ρN −1 , ᾱ

(48)

with τ (0) as in (41). Then for every t ≥ 0 the mechanism S 7→ MS (Z) with Z ∼ N (0, σ 2 Id ), σ > 0, is (ϵtotal , δtotal )-differentially private, where r∆ξ (G + ∆ξ )2 G t+ 2 + + τ, σ σ 2σ 2
2G δtotal = Pr ∥Z∥ > r + Q1 (t). σ

ϵtotal =

(49) (50)

Proof. Let (S, S ′ ) be an ordered pair of neighboring datasets, let Z ∼ N (0, σ 2 Id ), and let O ⊆ Rd be a measurable set; we show Pr[MS (Z) ∈ O] ≤ eϵtotal Pr[MS ′ (Z) ∈ O] + δtotal . Domain construction. Since w0 = 0 and ∥∇FT (0)∥ ≤ L1 ζ for every dataset (Section 3.1), item 1 of Lemma A.6 gives RT (z) ≤ (∥z∥ + L1 ζ)/µ ≤ R̄ for every z ∈ Ω′ and T ∈ {S, S ′ }. Hence RΩ′ ≤ R̄, and αΩ′ ≥ ᾱ > 0 makes N feasible for Ω′ (Definition C.7), so Lemma C.11 furnishes a bounded convex open set B ⊇ Ω′ on which MS and MS ′ are C 1 -diffeomorphisms onto their images; every preimage below lies in Ω′ ⊂ B, where the diffeomorphisms and the change-of-variables formula are valid. Preimage existence. Fix zS ∈ Ω0 and set y := MS (zS ). Consider the path yv := (1 − v)MS ′ (zS ) + vy for v ∈ [0, 1], and let I be the set of v ∈ [0, 1] such that yv′ ∈ MS ′ (B) for ′ ′ ′ ′ every v ′ ∈ [0, v] and the lift zv′ := M−1 S ′ (yv ) obeys ∥zv ∥ ≤ r + v (r − r) on [0, v]. The bound S ′ (z ′ ))−1 (y − M ′ (z )) by keeps each zv′ in Ω′ , where the lift moves at controlled speed: żv′ = (JN S v S S ′ )−1 ∥ ≤ 1/α ′ on Ω′ ) and Lemma A.7 (∥y − M ′ (z )∥ = the chain rule, so Theorem A.12 (∥(JN S Ω S ∥MS (zS ) − MS ′ (zS )∥ ≤ G(1 − ρN )/µ) give ∥żv′ ∥ ≤

G(1 − ρN ) G(1 − ρN ) ≤ ≤ r′ − r, µ αΩ′ µ ᾱ

the middle step by αΩ′ ≥ ᾱ and the last by (47). Since [0, 1] is connected, it suffices to check that I is nonempty, relatively open, and relatively closed; then I = [0, 1]. Nonempty: 0 ∈ I, as 37

y0 = MS ′ (zS ) has preimage zS with ∥zS ∥ ≤ r. Open: for v ∈ I with v < 1 the bound at v is strict, ∥zv ∥ < r′ . Since yv = MS ′ (zv ) lies in the open set MS ′ (B), continuity of the path extends the lift to [0, v + ε); shrinking ε keeps ∥zv′ ∥ < r′ , hence zv′ ∈ Ω′ , and integrating the speed bound from 0 restores ∥zv′ ∥ ≤ ∥zS ∥ + v ′ (r′ − r) ≤ r + v ′ (r′ − r) there. So [0, v + ε) ⊆ I. Closed: as v ↑ v ∗ := sup I, the speed bound makes v 7→ zv Lipschitz, so zv converges to some z ∗ in the compact set Ω′ ; continuity gives MS ′ (z ∗ ) = yv∗ and ∥z ∗ ∥ ≤ r + v ∗ (r′ − r), so v ∗ ∈ I. Taking v = 1 and integrating ′ N ′ ′ the speed bound once more yields zS ′ := M−1 S ′ (y) ∈ Ω with ∥zS − zS ∥ ≤ G(1 − ρ )/(µ αΩ ). ′ Density ratio. For zS ∈ Ω0 , set y := MS (zS ) and let zS ′ ∈ Ω be its MS ′ -preimage. The restricted privacy loss (23) splits into the Gaussian and Jacobian ratios. We instantiate the hypotheses of Appendix C.1 with the pair (Ω0 , Ω′ ), scale RΩ′ , and radius r: both maps are C 1 diffeomorphisms on Ω0 , and MS ′ is one on Ω′ (each restricting from B; Convention 1); Ω0 ⊆ Ω′ since r ≤ r′ by (47); the preimage-existence step shows MS (Ω0 ) ⊆ MS ′ (Ω′ )—so the conjugacy map Φ : Ω0 → Ω′ is well-defined, with Φ(zS ) = zS ′ —and the closed ball of radius r is Ω0 itself. Under this instantiation E1 = {∥z∥ ≤ r} = {z ∈ Ω0 }, and Theorem C.4—whose bound (34) holds pointwise on E1 viewed as a deterministic set—bounds the Gaussian ratio
in absolute value by (G/σ)T (zS ) + r∆ξ /σ 2 + (G + ∆ξ )2 /(2σ 2 ), with T (z) = |⟨z, xn ⟩| + |⟨z, x′n ⟩| /(2ζσ) as in (30): its residual scale is ∆Ω′ = 2µρN RΩ′ ≤ ∆ξ , and both terms carrying it are nondecreasing in it. By Theorem C.9 (feasibility on Ω′ ), the Jacobian ratio is at most τ (0) + βN /αΩ′ in absolute value; here ′ RS , RS ≤ RΩ′ ≤ R̄ gives βN ≤ 2ηM R̄B ν̃N ρN −1 , and αΩ′ ≥ ᾱ, so the ratio is at most τ . Adding the two and writing r∆ξ (G + ∆ξ )2 G + + τ, so that ϵtotal = t + s, σ2 2σ 2 σ we obtain, for every zS ∈ Ω0 , pS (y; Ω′ ) G log SY′ ≤ s + T (zS ). ′ σ pY (y; Ω ) s :=

(51)

(52)

Assembly. Since Pr(Z ∈ / Ω0 ) = Pr(∥Z∥ > r), Pr[MS (Z) ∈ O] ≤ Pr[MS (Z) ∈ O, Z ∈ Ω0 ] + Pr(∥Z∥ > r), R and the change of variables (Remark C.10) evaluates the first term as O∩MS (Ω0 ) pSY (y; Ω0 ) dy, the preimage of each such y lying in Ω0 ⊆ Ω′ so that pSY (y; Ω0 ) = pSY (y; Ω′ ) there. By the preimage′ existence step MS (Ω0 ) ⊆ MS ′ (Ω′ ), so pSY (· ; Ω′ ) is defined on that set and integrates over O ∩ MS (Ω0 ) to at most Pr[MS ′ (Z) ∈ O]. ′ Add and subtract eϵtotal pSY and discard the constraint y ∈ O from the nonnegative remainder: Z Z  S  ′ S ′ ϵtotal pY (y; Ω ) dy ≤ e Pr[MS ′ (Z) ∈ O] + pY (y; Ω′ ) − eϵtotal pSY (y; Ω′ ) + dy. O∩MS (Ω0 )

MS (Ω0 )

Factoring pSY out of the last integrand and changing variables back, Z h  S
i ′ pY − eϵtotal pSY + dy = E 1{Z ∈ Ω0 } 1 − eϵtotal −Λtot (Z) + , MS (Ω0 )

  ′ where Λtot (z) := log pSY (MS (z); Ω′ )/pSY (MS (z); Ω′ ) is the restricted privacy loss—the sum of the two ratios of (23), not the Gaussian ratio Λ of (29) alone. The map x 7→ (1 −
eϵtotal −x )+ is nondecreasing, so (52) and (51) bound the integrand on {Z ∈ Ω0 } by 1 − e−(G/σ)(T −t) + ; dropping the indicator, which only enlarges a nonnegative integrand, gives Z h  S
i 2G ′ pY − eϵtotal pSY + dy ≤ E 1 − e−(G/σ)(T −t) + ≤ Q1 (t), σ MS (Ω0 ) 38

the second inequality by Lemma C.12 at λ = G/σ, whose hypothesis on T is the average form (32), with scales ∥xn ∥/ζ and ∥x′n ∥/ζ at most one. Together with the truncation split, these give Pr[MS (Z) ∈ O] ≤ eϵtotal Pr[MS ′ (Z) ∈ O] + Pr(∥Z∥ > r) + (2G/σ)Q1 (t), and the last two terms are δtotal by (50). The two summands of δtotal are charged for different reasons. The first is mass on which no ratio bound is available at all; the second is the divergence contributed by outputs whose ratio bound exceeds eϵtotal . Uniformity. The pair was arbitrary, and (49) and (50) name only r, r′ , t, N and constants common to all datasets, so one (ϵtotal , δtotal ) serves every ordered pair, as the definition of differential privacy requires. Remark C.14 (Existence of the domain radius). Given the radius r of Theorem C.13, a radius r′ satisfying (47) exists for
all sufficiently large N . Throughout, N ≥ 1, so γN > 0. Write ᾱ(r̃) := γN −ηM (r̃+L1 ζ)/µ B ν̃N ρN −1 , the value of ᾱ at r′ =
r̃, and ϕ(r̃) := r+G(1−ρN )/(µ ᾱ(r̃)). Put r̃max := r + 2G/(µγN ) and Cmax := ηM (r̃max + L1 ζ)/µ B. When ν̃N ρN −1 <

γN 2Cmax

(53)

(which holds for all large N , as ν̃N ρN −1 ≤ N ρN −1 → 0 and γN → 1/L), every r̃ ∈ [r, r̃max ] has ᾱ(r̃) ≥ γN − Cmax ν̃N ρN −1 > γN /2 > 0, so ϕ is continuous on [r, r̃max ] with ϕ(r) > r and ϕ(r̃max ) ≤ r + 2G(1 − ρN )/(µγN ) < r̃max . By the intermediate value theorem ϕ has a fixed point r′ ∈ (r, r̃max ), which satisfies (47). The bound (49) is exact but d-dependent, through r and through ∆ξ and τ (both via R̄); the corrections in τ involve the factors N ρN −1 and ν̃N ρN −1 ≤ N ρN −1 , which the following tail bound controls, and which the explicit threshold (7) then meets by spending one ρN/2 on the coefficients. Applied in full, the bound absorbs the factor N and leaves ρN/2 ; applied after that spending, it leaves N ρN/2 . Lemma C.15 (Tail bound). For ρ = 1 − ηµ ∈ (0, 1) (the contraction factor of Section 3.2) and every integer N ≥ 0, e ηµ N ρN/2 ≤ 1, 2

equivalently

N ρN −1 ≤

2 ρN/2 . e ρ ηµ

Proof. For s ∈ (0, 1) the function x 7→ xsx on [0, ∞) is maximized at x = 1/ log(1/s), where it equals 1 1 2 x 1/2 and x = N gives N ρN/2 ≤ e log(1/s) ; hence xs ≤ e log(1/s) for all x ≥ 0. Taking s = ρ e log(1/ρ) , and log(1/ρ) ≥ ηµ—from ρ = 1 − ηµ and − log(1 − v) ≥ v for v ∈ (0, 1)—gives the first form. Multiplying it by ρN/2−1 gives the second. Theorem 4.1 (Differential privacy of gradient descent on perturbed objectives). Let Assumptions 1 to 3 hold, and let the step size satisfy 0 < η ≤ 1/L and ηµ < 1 (Section 3.2). Fix u ≥ 0 and set ru := σ

p
d⋆ + u ,

r′ := ru +

2LG , µ

R̄ :=

r ′ + L1 ζ , µ

together with B := 1/µ (item 2 of Lemma A.9). Suppose the iteration count satisfies n 2µR̄ r′ o 2 8LM B R̄ log max , , 4 . ηµ Gσ eρµ min{1, M G/L}

(7)

 ∆H  eηµ τ ⋆ := log 1 + + min{1, M G/L} N ρN/2 , 2nµ 2

(8)

N≥ Writing

39

and setting ϵ0 :=

2 G N/2 G2 ρ + 2 1 + ρN/2 + τ ⋆ , σ 2σ

(9)

the mechanism S 7→ MS (Z) with Z ∼ N (0, σ 2 Id ), σ > 0, is (ϵ, δ(ϵ))-differentiallyR private for every ∞ ϵ ≥ ϵ0 , where, for a standard Gaussian W , we define the integrated tail Q1 (t) := t Pr(W > s) ds, 2

δ(ϵ) = e−u /2 +

σ  2G Q1 (ϵ − ϵ0 ) , σ G

(10)

an explicit upper bound on the privacy profile (3). Once (7) holds, the displayed privacy budget has no explicit dependence on the ambient dimension. In the sufficient condition for N , the dimension appears only through d⋆ = min{d, n + 1}. Proof. Reduction to the feature span. By Lemma B.6, the two mechanisms differ only in their C blocks MCS , MCS ′ , which form a mechanism pair of Appendix A.1 within C carrying the same µ, L, M, G; their C ⊥ blocks are one shared affine map, which cancels from both ratios of (23) as recorded after that display. Since Z ∼ N (0, σ 2 Id ) is isotropic, ΠC Z ∼ N (0, σ 2 IdC ) independently of ΠC ⊥ Z, so each output law is a product whose second factor, the law of −BN ΠC ⊥ Z, is the same under both datasets. For Borel O ⊆ Rd and each yC ⊥ , applying the (ϵ, δ) inequality for MCS , MCS ′ to the slice {yC ∈ C : yC + yC ⊥ ∈ O} and integrating against that common factor gives the same inequality for MS , MS ′ at O: each output law is the product of its two block laws, the slices of a Borel O are Borel [Folland, 1999, Proposition 2.34], the slice probabilities integrate to the total by Tonelli’s theorem [Folland, 1999, Theorem 2.37], and the δ-term integrates to δ because the common factor is a probability measure. We argue within C for the rest of the proof, so that Theorem C.13 and everything it rests on is applied with dC in place of d, and write z for zC . Set Ω′ := {∥z∥ ≤ r′ } with r′ = ru + 2LG/µ as in the statement, so the R̄ fixed there is the uniform trajectory scale of Theorem C.13 at this r′ . Truncation mass. Gaussian norm (Corollary E.4), applied in C to ΠC Z ∼ √ concentration 2 N (0, σ 2 IdC ), gives Pr(∥ΠC Z∥ ≥ σ( dC + v)) ≤ e−v /2 √ for every v ≥ √ 0. Since dim C = dC ≤ d⋆ by (2), the radius fixed in the statement obeys ru = σ( d⋆ + u) ≥ σ( dC + u), so at v = u this 2 gives Pr(∥ΠC Z∥ > ru ) ≤ e−u /2 , the first term of (10). Only d⋆ enters ru , and it is fixed by d and n before the neighboring pair is named. We verify the remaining hypotheses from the three entries of (7): as ρ = 1 − ηµ ≤ e−ηµ , the condition gives ρN/2 ≤ e−N ηµ/2 ≤ 1/X for each entry X of the maximum. The third entry 1 1 gives ρN/2 ≤ 41 ; squaring, ρN ≤ 16 , and 0 ≤ 1 − ηL ≤ ρ gives (1 − ηL)N ≤ ρN ≤ 16 , so that N

γN = 1−(1−ηL) L

15 12 3 ≥ 16L ≥ 16L = 4L . The second entry gives

eρµ min{1, M G/L} . (54) 8LM B R̄
By (22), ν̃N ≤ νN ≤ N , so with N ρN −1 = ρ−1 ρN/2 N ρN/2 and (54) applied to the isolated ρN/2 , ρN/2 ≤

R̄ ν̃N ρN −1 ≤ R̄ N ρN −1 ≤

min{1, M G/L} min{1, M G/L} · e ηµ N ρN/2 ≤ , 8LM Bη 4LM Bη

the last step by Lemma C.15. Multiplying by ηM B and using min{1, M G/L} ≤ 1, ηM R̄B ν̃N ρN −1 ≤

min{1, M G/L} 1 ≤ . 4L 4L

40

(55)

3 1 1 3 , the singular-value margin is ᾱ = γN − ηM R̄B ν̃N ρN −1 ≥ 4L − 4L = 2L > 0, and With γN ≥ 4L N the fixed-point inequality (47) follows from 1 − ρ ≤ 1:

ru +

G(1 − ρN ) 2LG ≤ ru + = r′ . µ ᾱ µ

Gaussian terms. The first entry of (7) gives ρN/2 ≤ Gσ/(2µR̄r′ ), so ∆ξ = 2µρN R̄ = 2µR̄ ρN/2 · ρN/2 ≤

Gσ N/2 ρ . r′

Since ru ≤ r′ , the second term of (49) obeys ru ∆ξ /σ 2 ≤ (G/σ)ρN/2 ; and r′ ≥ ru ≥ σ gives ∆ξ ≤ GρN/2 , so the third obeys (G + ∆ξ )2 /(2σ 2 ) ≤ G2 (1 + ρN/2 )2 /(2σ 2 ). For the Jacobian ratio, Lemmas C.5 and C.6 give τ (0) ≤ log(1 + ∆H /(2nµ)) because both reference Hessians are evaluated at the shared output. For the finite-N correction, the estimate behind (55), retaining the factor N ρN/2 , gives 2ηM R̄B ν̃N ρN −1 ≤

min{1, M G/L} eηµ N ρN/2 ; 4L

1 the correction term of (48) is at most so with ᾱ ≥ 2L

2L ·

min{1, M G/L} eηµ eηµ N ρN/2 = min{1, M G/L} N ρN/2 . 4L 2

Collecting the two,  ∆H  eηµ τ ≤ log 1 + + min{1, M G/L} N ρN/2 = τ ⋆ . 2nµ 2 Now fix ϵ ≥ ϵ0 and apply Theorem C.13 at the radius r = ru and the threshold t := (σ/G)(ϵ − ϵ0 ) ≥ 0. The released map z 7→ wN depends on neither, so a different t may be taken for each ϵ. Its budget (49) has first term (G/σ)t = ϵ − ϵ0 , while its remaining three are majorized by the three terms of (9)—the first two by the Gaussian-terms step above, the third by τ ≤ τ ⋆ —so ϵtotal ≤ ϵ. Its additive parameter (50) is Pr(∥ΠC Z∥ > ru ) + (2G/σ)Q1 (t) ≤ δ(ϵ) by the truncation-mass step and (10). A mechanism that is (ϵtotal , δtotal )-private with ϵtotal ≤ ϵ and δtotal ≤ δ(ϵ) is a fortiori (ϵ, δ(ϵ))-private. Remark C.16 (Oracle limit). As N → ∞, ∆ξ → 0 and τ (corr) → 0. For every fixed h ∈ [µ, L], (36) gives gN (h) → 1, and therefore ḡN → 1. Hence the nontruncation part of (49), at any fixed threshold t, converges to  G G2 ∆H  t + 2 + log 1 + . σ 2σ 2nµ To recover the full exact-minimizer certificate, choose the free truncation parameter to grow with N ; for example, let uN = N . Then ruN , r′ , and R̄ grow at most linearly in N , so the right-hand side of (7) is O((ηµ)−1 log N ) and the condition holds for all sufficiently large N . At the same time, 2 e−uN /2 → 0, ρN/2 → 0, and N ρN/2 → 0. Thus, for every fixed ϵ > ϵ∞ , where  ∆H  G2 ϵ∞ := 2 + log 1 + , 2σ 2nµ our bound converges to the exact-minimizer certificate obtained from the same Gaussian-ratio and common-anchor determinant bounds. When ∆H /(nµ) ≪ 1, the determinant term is ∆H /(2nµ) + O((∆H /(nµ))2 ); Remark 4.6 compares it with the classical determinant bound. 41

C.4

Evaluation of the finite-iteration certificates

We evaluate Theorems 4.1 and C.13 at the public constants of Example 4.8, with the radii r = ru and r′ = ru + 2LG/µ of Theorem 4.1. Let ᾱ, ∆ξ , and τ be as in (47) and (48). At η = 1/L and N ≥ 2, gN (L) = 1, so ḡN = 1 by Lemma C.5 and τ (0) = log(1 + ∆H /(2nµ)). Write sN :=

(G + ∆ξ )2 r∆ξ + +τ 2 σ 2σ 2

for the part of ϵtotal in (49) that does not depend on t. For a candidate iteration count we check ᾱ > 0 and the radius condition (47). When both hold and ϵ ≥ sN , Theorem C.13 at t = (ϵ−sN )σ/G certifies (ϵ, δN (ϵ))-differential privacy with σ  2G 2 δN (ϵ) := e−u /2 + Q1 (ϵ − sN ) , σ G 2

the truncation mass in (50) being at most e−u /2 at r = ru by Gaussian norm concentration (Corollary E.4). For the parameters of Example 4.8 at N = 519, ᾱ ≃ 3.843548916,

s519 ≃ 0.05209595621,

G(1 − ρN ) ≃ 5.20352425 × 10−5 , r′ − r = 1.04 × 10−4 , µᾱ so the radius condition holds. Evaluating at ϵ = 1 gives δ519 (1) ≤ 9.89505873 × 10−8 , rounded upward, against 1.01736108 × 10−7 at N = 518; checking every smaller count gives 519 as the first passing integer for these radii. For comparison across regularization strengths, we keep n = 106 , d = 104 , σ/G √ = 5, u = 6, ϵ = 1, and the target δ = 10−7 . For each µ, we use L = µ + 1/4, η = 1/L, r = σ( d⋆ + u), and r′ = r + 2LG/µ. µ

κ

Smallest N satisfying (7)

First passing N for Theorem C.13

Certified δ(1) at that count

10−2 10−3

26 251

1319 16148

519 6079

9.89506 × 10−8 9.99539 × 10−8

For the fourth column, we evaluate the more precise certificate with the fixed radii specified above. By using the Jacobian and residual estimates before the simplifications in (7), we certify the same target privacy pair at a smaller iteration count.

C.5

An exact Gaussian benchmark

Linear losses with ridge regularization provide an exact reference for evaluating privacy certificates. For the exact minimizer, the reduction to a Gaussian mechanism appears in Redberg et al. [2023, Example 3.4]. Here we evaluate the full finite-gradient-descent trajectory. Consider µ FS (w) = ∥w∥2 + ⟨bS , w⟩, 2

n

1X bS = − yi x i , n i=1

Starting at zero, we can solve the recursion explicitly, wN = −

1 − ρN (bS + Z). µ 42

yi ∈ {−1, 1}.

For every N ≥ 1, the multiplier is public and nonzero. The release is therefore an invertible rescaling of the Gaussian mechanism bS + Z. For a neighboring pair with ∥bS − bS ′ ∥ = G > 0, the privacy profile for the Gaussian mechanism is     G G ϵσ ϵσ ϵ − e ΦG − , δG (ϵ) = ΦG − − 2σ G 2σ G where ΦG is the standard Gaussian cumulative distribution function [Dong et al., 2022, Theorem 2.7 and Corollary 2.13]. This pairwise privacy profile is the same for every positive iteration count. For this objective, the Jacobian is identical under neighboring datasets. We can therefore compare the exact profile with the integrated-tail certificate using zero log-determinant contribution. At σ/G = 5 and ϵ = 1, the two values are    2G σ G2 −8 δG (1) ≃ 1.75463333 × 10 , 1− 2 ≃ 3.63850762 × 10−8 . Q1 σ G 2σ This gives an exact reference for the Gaussian-ratio accounting, separate from the finite-iteration and truncation terms.

D

Utility

We bound the excess risk of the mechanism MS (z) = wN —both the excess empirical risk and the excess population risk. The analysis is agnostic to the privacy mechanism: it bounds risk as a function of the noise scale σ and the iteration count N , for the same gradient descent on the perturbed objective, and applies for any σ.

D.1

Setting and assumptions

Throughout this section the empirical risk has the sample-average structure n

1X F (w; S) = ℓ(w; si ) + r(w), n i=1

where S = (s1 , . . . , sn ) consists of n independent draws from a distribution D, the per-sample loss is ℓ(· ; s), and r is a convex, dataset-independent regularizer. In addition to Assumption 4 (which supplies the µ-strong convexity and L-smoothness of F (· ; S)), we impose the following. Assumption 7 (Bounded per-sample gradient). ∥∇ℓ(w; s)∥ ≤ Lℓ for all w and s. Under the sample-average structure and Assumption 7, the gradient sensitivity is at most 2Lℓ /n, so Assumption 6 holds with G = 2Lℓ /n: for neighboring datasets S, S ′ differing in a single sample sj → s′j , the regularizer cancels and the triangle inequality gives ∥∇F (w; S) − ∇F (w; S ′ )∥ =

1 2Lℓ ∥∇ℓ(w; sj ) − ∇ℓ(w; s′j )∥ ≤ . n n

Assumption 8 (Population regularity). The population risk Rµ (w) = Es∼D [ℓ(w; s)] + r(w) is µ-strongly convex and L-smooth, with the same constants µ, L as Assumption 4. Throughout, w∗ denotes the population minimizer of Rµ , and wS∗ denotes the empirical minimizer of F (·; S) (equivalently, wS∗ = w∗ (0)). We continue to write w∗ (z) for the perturbed minimizer of Lemma A.2. 43

Remark D.1. Ridge regularization gives the standard instance of Assumptions 4 and 8: take r(w) = µ 2 2 ∥w∥ and assume each per-sample loss is convex and (L − µ)-smooth. Then F (·; S) and Rµ are µ-strongly convex and L-smooth. The utility results below use these properties together with the per-sample gradient bound. For the privacy result, the isotropic ridge term also yields the data-span decomposition in Lemma B.6. Since r is dataset independent, it does not contribute to gradient sensitivity.

D.2

Excess empirical risk

We decompose the excess empirical risk into a perturbation error, from adding the linear term ⟨z, w⟩ to the objective, and an optimization error, from running finitely many gradient steps. Theorem 4.10 (Excess empirical risk). Under Assumptions 1 to 3, let z ∼ N (0, σ 2 Id ) and let wN be the output of (4). With Eopt (N ) as in (12),   dσ 2 + Eopt (N ). Ez F (wN ; S) − F (wS∗ ; S) ≤ 2µ Proof. Write Fz (w) := F (w; S) + ⟨z, w⟩. The linear term does not change the Hessian, so Fz is µstrongly convex and L-smooth with minimizer w∗ (z) (Lemma A.2), and the iterates (4) are exactly gradient descent on Fz from w0 = 0. The excess risk splits at w∗ (z) into the two errors of the decomposition:     F (wN ; S) − F (wS∗ ; S) = F (wN ; S) − F (w∗ (z); S) + F (w∗ (z); S) − F (wS∗ ; S) . | {z } | {z } optimization error

perturbation error

Perturbation error. At w∗ (z), Lemma A.2 gives ∇F (w∗ (z); S) = −z. The strong-convexity lower bound of Lemma E.2 therefore gives F (wS∗ ; S) ≥ F (w∗ (z); S) + ⟨−z, wS∗ − w∗ (z)⟩ +

µ ∗ ∥w − w∗ (z)∥2 . 2 S

Write u := wS∗ − w∗ (z), rearrange, and complete the square: F (w∗ (z); S) − F (wS∗ ; S) ≤ ⟨z, u⟩ −

µ z 2 ∥z∥2 ∥z∥2 µ ∥u∥2 = − u − ≤ . + 2 2 µ 2µ 2µ

Optimization error. By Lemma A.4 applied to Fz and item 3 of Lemma A.6, ∥wN − w∗ (z)∥ ≤ ρN ∥w0 − w∗ (z)∥ ≤ ρN R(z). Since ∇Fz (w∗ (z)) = 0, the smoothness upper bound of Lemma E.2 gives L L Fz (wN ) − Fz (w∗ (z)) ≤ ∥wN − w∗ (z)∥2 ≤ ρ2N R(z)2 . 2 2 As F (w; S) = Fz (w) − ⟨z, w⟩,   F (wN ; S) − F (w∗ (z); S) = Fz (wN ) − Fz (w∗ (z)) − ⟨z, wN − w∗ (z)⟩, and Cauchy–Schwarz with the contraction bound gives |⟨z, wN − w∗ (z)⟩| ≤ ∥z∥ ∥wN − w∗ (z)∥ ≤ ρN ∥z∥ R(z); adding the two displays bounds the optimization error by (L/2)ρ2N R(z)2 +ρN ∥z∥ R(z); with the perturbation error, for every z F (wN ; S) − F (wS∗ ; S) ≤

∥z∥2 L 2N + ρ R(z)2 + ρN ∥z∥ R(z). 2µ 2 44

(56)

Taking expectations. From R(z) ≤ bR ∥z∥+aR (Lemma A.6) we get R(z)2 ≤ b2R ∥z∥2 +2aR bR ∥z∥+ 2 a2R and ∥z∥ R(z) Ez with E∥z∥2 =√dσ 2 p ≤ bR ∥z∥√+ aR ∥z∥. Summing the two error terms and taking L 2N 2 2 bR dσ 2 +2aR bR σ d+ and E∥z∥ ≤ E∥z∥ = σ d (Jensen) bounds the optimization error by 2 ρ √

a2R + ρN bR dσ 2 + aR σ d = Eopt (N ) of (12), which is the stated bound. Remark D.2. As N → ∞ both terms of Eopt (N ) vanish and the bound tends to dσ 2 /(2µ), the standard objective-perturbation rate. The bound holds at every finite N ; here aR = ∥∇F (0; S)∥/µ is the dataset-dependent constant of Lemma A.6 for the fixed S, and the correction’s coefficients depend on d, σ, L, µ.

D.3

Excess population risk

We bound the excess population risk by transferring the empirical bound of Theorem 4.10 to the population through uniform convergence; this avoids the condition-number factor that a curvaturebased decomposition through w∗ would incur (Remark D.3). The vehicle is the fast-rate guarantee of Sridharan et al. [2008, Theorem 1], imported as Theorem E.10 in Appendix E; applying it at the (random) output wN and taking expectations over the perturbation converts the empirical bound into a population bound. Theorem 4.9 (Excess population risk). Under Assumptions 1 to 3, let z ∼ N (0, σ 2 Id ) and let wN be the output of (4). Then for δS ∈ (0, 1), with probability at least 1 − δS over S, h dσ 2 i 16 L2 32 + log(1/δ )
  S ℓ ∗ Ez Rµ (wN ) − Rµ (w ) ≤ 2 + Eopt (N ) + . 2µ µn Proof. Assumptions 1 to 3 verify the hypotheses of Theorem E.10, by the derivations recorded there. On its event (probability at least 1 − δS over S), its bound at a = 1 holds simultaneously for all w, in particular for w = wN at every realization of z. Taking Ez ,
    16 L2ℓ 32 + log(1/δS ) ∗ ∗ Ez Rµ (wN ) − Rµ (w ) ≤ 2 Ez F (wN ; S) − F (wS ; S) + , µn 2

and Theorem 4.10 bounds Ez [F (wN ; S) − F (wS∗ ; S)] ≤ dσ 2µ + Eopt (N ), giving the claim. (The righthand side depends on S through aR = ∥∇F (0; S)∥/µ in Eopt (N ), and the high-probability statement is over the draw of S; this P dependence is benign, as the sample-average structure and Assumption 7 give ∥∇F (0; S)∥ ≤ n1 ni=1 ∥∇ℓ(0; di )∥ + ∥∇r(0)∥ ≤ Lℓ + ∥∇r(0)∥, so aR ≤ (Lℓ + ∥∇r(0)∥)/µ uniformly over S.) Remark D.3. As N → ∞, Eopt (N ) → 0, and the leading statistical terms in Theorem 4.9 scale as 1/µ without an additional multiplicative factor L/µ. A quadratic model illustrates this scaling. Let H be the empirical Hessian, so that w∗ (z) = wS∗ − H −1 z. If H = ∇2 Rµ , then the leading perturbation contribution is
dσ 2 σ2 tr (∇2 Rµ )−1 ≤ . 2 2µ By contrast, bounding H −1 and ∇2 Rµ separately by µ−1 I and LI gives the looser scale Ld/µ2 = κd/µ. The uniform-convergence argument avoids this extra curvature ratio in the leading statistical terms.

45

D.4

Proof of the target-budget calibration

Proof of Corollary 4.13. All quantities used to select µ, σ, and N are public. Fix these quantities and write   L2 ζ 2 . q(µ) = log 1 + nµ By the choice of µpriv and µ ≥ µpriv , we have q(µ) ≤ ϵ/4. Also u2 = 2 log(2/δ) > 1 and 0 < ϵ ≤ 1, so G ϵ G2 ϵ2 ϵ u= , = ≤ . σ 4 2σ 2 32u2 32 The definition of cN gives ϵ0 = G2 /(2σ 2 ) + q(µ) + cN . Applying Theorem 4.1 at b ϵ = ϵ0 + (G/σ)u therefore gives ϵ ϵ ϵ 25ϵ ϵ + + + = < ϵ. b ϵ≤ 32 4 4 4 32 For the additive privacy parameter, let ϕ denote the standard Gaussian density. Since Q1 (u) ≤ ϕ(u) 2 for u ≥ 0 and e−u /2 = δ/2, δ G δ 2G 2 Q1 (u) ≤ + √ < δ, δb = e−u /2 + σ 2 σ 2π where the last inequality uses G/σ = ϵ/(4u) < 1/4. This proves (ϵ, δ)-privacy. For fixed public parameters the right-hand side of (7) is finite, while cN → 0. Hence we can choose a public integer satisfying both iteration conditions. On the sample event used in Theorem 4.9, the argument for Theorem 4.7 applies simultaneously to every comparator. Thus, for every ∥w̄∥ ≤ W , Ez [R0 (wN )] − R0 (w̄) ≤

A µW 2 + + 2Eopt (N ). µ 2

Since µ ≥ µutil and µ ≤ µutil + µpriv , √ µpriv W 2 A µW 2 A µutil W 2 µpriv W 2 + ≤ + + = W 2A + . µ 2 µutil 2 2 2 √ If µutil ≥ µpriv , then µ = µutil and the first two terms are exactly W 2A,√ so no additional √ √ regularization term is needed. Finally, substitute σ = 4Gu/ϵ, G = 2Lℓ /n, and a + b ≤ a + b to obtain the decomposition following the corollary.

D.5

Proof of the realized-release utility corollary

Proof of Corollary 4.11. By Corollary E.4, ∥Z∥ ≤ rβ with probability at least 1 − β. Since ∥∇F (0; S)∥ ≤ Lℓ , the trajectory scale satisfies R(Z) ≤ Rβ on this event, uniformly over S. By (56), the pointwise estimate in the proof of Theorem 4.10, F (wN ; S) − F (wS∗ ; S) ≤

∥Z∥2 L 2N + ρ R(Z)2 + ρN ∥Z∥R(Z) ≤ UN (β). 2µ 2

Intersect this event with the uniform sample event of Theorem E.10 at a = 1. A union bound gives probability at least 1 − δS − β, and the uniform-convergence inequality gives the population bound at the realized wN . Finally use the regularization comparison in the proof of Theorem 4.7, which holds for every comparator on the same event. 46

E

External results

We collect here the external results used in the proofs, stated in the notation needed below. When we use a form that differs from the source statement, we include the short derivation. Lemma E.1 (Minimizer of a strongly convex function). Let f : Rd → R be continuously differentiable and µ-strongly convex with µ > 0. Then f attains its minimum at a unique point x∗ , and a point minimizes f if and only if its gradient vanishes. Existence and uniqueness are Nesterov [2018, Theorem 2.2.10], stated there for the class Sµ1 (Q) with Q closed and convex, applied here at Q = Rd . The characterization is Nesterov [2018, Theorem 2.2.9]: x∗ minimizes f over Q if and only if ⟨∇f (x∗ ), x−x∗ ⟩ ≥ 0 for all x ∈ Q. At Q = Rd , taking x = x∗ − ∇f (x∗ ) makes the left side −∥∇f (x∗ )∥2 , so the condition forces ∇f (x∗ ) = 0; conversely, a zero gradient satisfies it trivially. Lemma A.2 applies this to the perturbed objective w 7→ F (w) + ⟨z, w⟩. Lemma E.2 (Quadratic bounds from two-sided curvature). Let f : Rd → R be twice continuously differentiable with µI ⪯ ∇2 f (w) ⪯ LI for all w ∈ Rd , where 0 < µ ≤ L. Then for all x, y ∈ Rd , µ L ∥y − x∥2 ≤ f (y) − f (x) − ⟨∇f (x), y − x⟩ ≤ ∥y − x∥2 . 2 2 The lower bound is the defining inequality of the class Sµ1 [Nesterov, 2018, Definition 2.1.3, eq. (2.1.20)], to which f belongs by the second-order characterization [Nesterov, 2018, Theorem 2.1.11]. The upper bound is Nesterov [2018, Lemma 1.2.3], valid for functions with L-Lipschitz gradient, a property that −LI ⪯ ∇2 f ⪯ LI supplies [Nesterov, 2018, eq. (1.2.10)]. Theorem E.3 (Lipschitz functions of a Gaussian vector). Let X ∼ N (0, Id ) and let f : Rd → R be 1-Lipschitz with respect to the Euclidean norm. Then for every t ≥ 0,
2 Pr f (X) − E[f (X)] ≥ t ≤ e−t /2 . This is the 1-Lipschitz case of Wainwright [2019, Theorem 2.26], which asserts that f (X) − E[f with parameter at most the Lipschitz constant; in the case at hand,  (X)] is sub-Gaussian  2 E eλ(f (X)−E[f (X)]) ≤ eλ /2 for all λ ∈ R. The one-sided tail follows by the Chernoff bound: for
  2 λ > 0, Markov’s inequality gives Pr f (X) − E[f (X)] ≥ t ≤ e−λt E eλ(f (X)−E[f (X)]) ≤ e−λt+λ /2 , 2 and the choice λ = t yields e−t /2 . The privacy analysis uses the theorem through the following norm bound; the same computation appears as Example 2.28 of Wainwright [2019]. Corollary E.4 (Gaussian norm concentration). Let Z ∼ N (0, σ 2 Id ). For every t ≥ 0, √
2 Pr ∥Z∥ ≥ σ( d + t) ≤ e−t /2 . Proof. Write Z = σX with X ∼ N (0, Id ). ThepEuclidean norm √ is 1-Lipschitz by the triangle 2 inequality, and Jensen’s inequality gives E[∥X∥] ≤ E[∥X∥ ] = d. By Theorem E.3 with f = ∥·∥, √ √


2 Pr ∥Z∥ ≥ σ( d + t) = Pr ∥X∥ ≥ d + t ≤ Pr ∥X∥ − E[∥X∥] ≥ t ≤ e−t /2 . The proof of Theorem 4.1 applies this at t = u, where it evaluates the first summand of (10). The truncation argument of Appendix C.3 computes output densities through the change of variables; we state the formula in the form used, allowing the conditioning set to be smaller than the domain of the diffeomorphism. 47

Lemma E.5 (Densities under a diffeomorphism). Let B ⊆ Rd be open, let G : B → Rd be a C 1 diffeomorphism onto its image, let Ω ⊆ B be Lebesgue measurable, and let Z be a random vector on Rd with density pZ . Then for every Lebesgue measurable E ⊆ Rd , Z   pZ (G−1 (y)) dy, Pr G(Z) ∈ E, Z ∈ Ω = −1 E∩G(Ω) det ∇G(G (y)) Thus E 7→ Pr[G(Z) ∈ E, Z ∈ Ω] defines the restricted measure. On G(Ω) its density is y 7→

pZ (G−1 (y)) . | det ∇G(G−1 (y))|

Proof. By the change-of-variables theorem [Folland, 1999, Theorem 2.47], for a C 1 -diffeomorphism G of the open set B and any measurable f ≥ 0 on G(B), Z Z f (y) dy = f (G(x)) | det ∇G(x)| dx; B

G(B)

part (b) of the same theorem makes G(Ω) Lebesgue measurable. Apply the formula to f (y) := 1E∩G(Ω) (y) pZ (G−1 (y))/| det ∇G(G−1 (y))|, measurable since G−1 and det ∇G are continuous with det ∇G ̸= 0 on B. Since G is a bijection of B onto G(B), for x ∈ B we have G(x) ∈ E ∩ G(Ω) if and only if x ∈ G−1 (E) ∩ Ω, so f (G(x)) | det ∇G(x)| = 1G−1 (E)∩Ω (x) pZ (x), and the right side of the formula equals Pr[Z ∈ G−1 (E) ∩ Ω] = Pr[G(Z) ∈ E, Z ∈ Ω]. In Appendix C we take G = MT and use the neighborhood B furnished by Lemma C.11. The restricted density pSY (· ; Ω) is then the density displayed above. The remaining four results are matrix analysis. Throughout, σ1 (A) ≥ · · · ≥ σd (A) P denote the singular values of A ∈ Rd×d in nonincreasing order, so that ∥A∥ = σ1 (A) and ∥A∥∗ = i σ Pi (A). The −1 first result is the Neumann series, the matrix form of the geometric series (1 − x) = m≥0 xm . Lemma E.6 (Neumann series). Let Ψ ∈ Rd×d satisfy ∥Ψ∥ < 1. Then I − Ψ is nonsingular and ∞ X

(I − Ψ)−1 =

Ψm ,

m=0

the series converging absolutely, as

m m ∥Ψ ∥ ≤

P

m −1 m ∥Ψ∥ = (1 − ∥Ψ∥) .

P

This is Horn and Johnson [2013, Corollary 5.6.16], that a matrix A with ∥I −A∥ < 1 P which states −1 m in some matrix norm is nonsingular with A = m≥0 (I − A) ; take A = I − Ψ in the spectral norm. Lemma E.7 (Trace and nuclear-norm inequalities). For all A, X, Y ∈ Rd×d , |tr A| ≤ ∥A∥∗

and

∥XY ∥∗ ≤ min ∥X∥∗ ∥Y ∥, ∥X∥ ∥Y ∥∗ .

In particular, ∥XY Z∥∗ ≤ ∥X∥ ∥Y ∥∗ ∥Z∥, and ∥K k ∥∗ ≤ ∥K∥∗ ∥K∥k−1 for every integer k ≥ 1. Both displayed inequalities are consequences of the singular-value results of Horn and Johnson [2013, §7.4.1]. PVon Neumann’s trace theorem [Horn and Johnson, 2013, Theorem 7.4.1.1] gives Re tr(AB ∗ ) ≤ i σi (A) σi (B); at B = I every σi (B) = 1 and the trace of the real matrix A is real, so tr A ≤ ∥A∥∗ , and applying this to −A as well gives the absolute value. For the product bound, 48

P P Horn and Johnson [2013, Corollary 7.4.1.3(d)] gives i σi (XB ∗ ) ≤ i σi (X) σi (B); at B = Y ⊤ (so that XB ∗ = XY and σi (B) = σi (Y )),   X X X ∥XY ∥∗ ≤ σi (X) σi (Y ) ≤ min σ1 (Y ) σi (X), σ1 (X) σi (Y ) , i

i

i

which is the stated minimum. The three-factor form follows by applying the product bound twice, ∥XY Z∥∗ ≤ ∥X∥ ∥Y Z∥∗ ≤ ∥X∥ ∥Y ∥∗ ∥Z∥, and the power bound by iterating ∥K k ∥∗ ≤ ∥K k−1 ∥∗ ∥K∥ down to ∥K∥∗ . We use three determinant identities in Appendix C.2: a nuclear-norm bound for log | det(I +K)|, the matrix determinant lemma for a rank-one update, and a trace identity for log p(A) when p is positive on the relevant spectral interval. Lemma E.8 (Determinant estimates). For every K ∈ Rd×d , with the convention log 0 = −∞, log | det(I + K)| ≤ ∥K∥∗ .

(57)

For every symmetric positive definite H ∈ Rd×d , every z ∈ Rd , and every c ∈ R,

(58) det H + c zz ⊤ = det(H) 1 + c z ⊤ H −1 z . P For (57) we first record that i |λi (A)| ≤ ∥A∥∗ for every A ∈ Cd×d , the eigenvalues counted with algebraic multiplicity. Schur triangularization [Horn and Johnson, 2013, Theorem 2.3.1] supplies a unitary U with U ∗ AU = T upper triangular and tii = λi (A). Let D be the diagonal P unitary ∗ AU ) = with d := λ (A)/|λ (A)| when λ (A) = ̸ 0 and d := 1 otherwise, so that tr(DU ii i i i ii i dii tii = P |λ (A)|, the product DT being upper triangular with those diagonal entries. Since |tr B| ≤ ∥B∥∗ i i ∗ (Lemma E.7) and singular values are unitarily invariant, ∥DU AU ∥∗ = ∥A∥∗ , and the record follows. Applying it to K and using that the eigenvalues of I + K are 1 + λi (K), X  Y Y
| det(I + K)| = 1 + λi (K) ≤ 1 + |λi (K)| ≤ exp |λi (K)| ≤ e∥K∥∗ , i

i

i

by 1+t ≤ et ; taking logarithms gives (57). At K = (u/d)I the left side is d log(1+u/d) → u = ∥K∥∗ as d grows,
so the estimate cannot be improved in terms of ∥K∥∗ alone. For (58), write H + czz ⊤ = H I + uv ⊤ with u := cH −1 z and v := z. The matrix uv ⊤ has rank at most one, so at most one of its eigenvalues is nonzero, and that one equals its trace v ⊤ u; the eigenvalues of I + uv ⊤ are therefore 1 + v ⊤ u together with 1 repeated d − 1 times, and det(I + uv ⊤ ) = 1 + v ⊤ u = 1 + c z ⊤ H −1 z. Multiplying by det H gives (58). The next lemma applies the rank-one determinant identity to log p(A) when p is a positive polynomial. We use it in Appendix C.2 with the polynomial that defines the frozen-Hessian Jacobian. Lemma E.9 (Trace of a log-polynomial along a segment). Let p be a real polynomial that is positive on [µ, L] ⊂ (0, ∞) and set ϕ := log p. Let A0 , A1 be symmetric with spectra in [µ, L], and let At := (1 − t)A0 + tA1 , whose spectrum lies in [µ, L] for every t ∈ [0, 1]. Then Z 1 tr ϕ(A1 ) − tr ϕ(A0 ) =

  tr ϕ′ (At ) (A1 − A0 ) dt,

0

with ϕ′ (At ) the matrix function of At built from ϕ′ = p′ /p. Consequently: 1. tr ϕ(A1 ) − tr ϕ(A0 ) ≤ Λ ∥A1 − A0 ∥∗ , where Λ := sup[µ,L] |ϕ′ |. 49

(59)

2. If A1 = A0 + uu⊤ and ϕ′ (h) = −g(h)/h with 0 ≤ g ≤ ḡ on [µ, L], then
−ḡ log 1 + u⊤ A−1 0 u ≤ tr ϕ(A1 ) − tr ϕ(A0 ) ≤ 0.

(60)

Proof. Each At is a convex combination of A0 and A1 , so µI ⪯ At ⪯ LI and every eigenvalue of p(At ) is positive; hence det p(A P t ) > k0 and tr ϕ(At ) = log det p(At ), a smooth function of t. Write Ȧ := A1 − A0 and p(x) = k ck x  . Jacobi’s formula [Horn and Johnson, 2013, §0.8.10] gives d d −1 dt log det p(At ) = tr p(At ) dt p(At ) , and differentiating each power, k−1

X X j d p(At ) = ck . At Ȧ Ak−1−j t dt k

j=0

The matrix p(At )−1 is a function of At and so commutes with every power of it, so cyclicity of the trace moves the trailing Ak−1−j to the front and merges it with Ajt : each of the k summands t Ȧ], independently of j. Summing over k leaves tr[p(At )−1 p′ (At )Ȧ] = contributes tr[p(At )−1 Ak−1 t ′ tr[ϕ (At )Ȧ], and integrating over t ∈ [0, 1] gives (59). Item 1. By |tr X| ≤ ∥X∥∗ and ∥XY ∥∗ ≤ ∥X∥ ∥Y ∥∗ (Lemma E.7), the integrand is at most ∥ϕ′ (At )∥ ∥Ȧ∥∗ in absolute value; and ϕ′ (At ) is symmetric with eigenvalues ϕ′ (λi (At )), so ∥ϕ′ (At )∥ ≤ Λ for every t. Item 2. Here Ȧ = uu⊤ , so the integrand is u⊤ ϕ′ (At )u = −u⊤ g(At )A−1 t u. The matrices g(At ) and A−1 are functions of the same symmetric matrix, hence simultaneously diagonalizable, t −1 −1 −1 and 0 ≤ g ≤ ḡ with At ≻ 0 gives 0 ⪯ g(At )At ⪯ ḡ At . The integrand therefore lies in ⊤ gives det A = det(A )(1 + ts) with s := [−ḡ u⊤ A−1 t 0 t u, 0]. Applying (58) to At = A0 + tuu −1 u⊤ A0 u ≥ 0, and Jacobi’s formula applied to log det At evaluates the same derivative two ways, R 1 ⊤ −1 d u⊤ A−1 t u = dt log det At = s/(1 + ts). Integrating over t ∈ [0, 1] gives 0 u At u dt = log(1 + s), which is (60). Theorem E.10 (Uniform convergence for regularized GLMs). In addition to Assumptions 4 and 8 and the sample-average structure of Appendix D.1, suppose the per-sample loss has the generalized linear form of (1), ℓ(w; (x, y)) = ℓ(⟨x, w⟩, y), with t 7→ ℓ(t, y) convex, |ℓ′ (t, y)| ≤ L1 for all t, y (as in Assumption 2) and ∥x∥ ≤ ζ for D-almost every sample (the distributional analogue of Assumption 1); then Assumption 7 holds with Lℓ = L1 ζ. For any a > 0 and δS ∈ (0, 1), with probability at least 1 − δS over S ∼ Dn the following holds simultaneously for all w ∈ Rd :
  8(1 + 1/a) L2ℓ 32 + log(1/δS ) ∗ ∗ Rµ (w) − Rµ (w ) ≤ (1 + a) F (w; S) − F (wS ; S) + . µn This is the fast-rate guarantee of Sridharan et al. [2008, Theorem 1] for regularized generalized linear objectives, instantiated with scalar Lipschitz constant L1 , feature bound ζ, and the µ-strong convexity of the population risk (Assumption 8); the generalized linear structure is what its Rademacher-contraction argument uses, and we invoke the result only in that form. Its two constants enter as the product L1 ζ = Lℓ , and the guarantee holds for all w ∈ Rd . The result is stated for each fixed a > 0, and its high-probability event depends on a; the applications fix a = 1 in advance.

50

Related documents

• Differential Privacy of Gradient Descent on Perturbed Objectives#1187030
• Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning#609724
• Communication-Efficient Differentially Private Gradient Tracking for Distributed Optimization via Local Updates#1200505
• Stabilizing updates in differentially private stochastic gradient descent with buffered rejection.#150196
• Privacy-Preserving Logistic Regression Training with A Faster Gradient Variant#144165