Introduction
Graphs that record relationships between individuals, such as social, financial, or communication networks, often contain sensitive information. Differential privacy [3 ] provides a rigorous framework for publishing statistics of such graphs; we use edge-level privacy, which protects the presence and weight of individual relationships while treating the vertex set as public. A central problem in this setting is to release a synthetic graph that approximately preserves every cut. Cut values underlie cut maximization, balanced partitioning, and clustering, and the released graph can be postprocessed freely, at no additional privacy cost.
Formally, we consider a graph G = ( V , w G ) G=(V,w_G) G = ( V , w G ) on a public vertex set V = [ n ] V=[n] V = [ n ] with nonnegative edge weights w G ∈ R ≥ 0 ( n 2 ) w_G\in\mathbb{R}_{\geq0}^{\binom{n}{2}} w G ∈ R ≥ 0 ( 2 n ) . For disjoint sets S , T ⊆ V S,T\subseteq V S , T ⊆ V , we write w G ( S , T ) w_G(S,T) w G ( S , T ) for the total weight of edges between them, so the cut defined by S S S has weight w G ( S , V ∖ S ) w_G(S,V\setminus S) w G ( S , V ∖ S ) . Two inputs G , G ′ G,G' G , G ′ are adjacent if ∥ w G − w G ′ ∥ 1 ≤ 1 \|w_G-w_{G'}\|_1\leq1 ∥ w G − w G ′ ∥ 1 ≤ 1 , so privacy protects every change of total edge weight at most one, whether concentrated on one edge or spread over many. The weights may be arbitrary nonnegative reals; neither their support nor a bound on their magnitude is public. Given a relative error γ > 0 \gamma>0 γ > 0 , we seek a polynomial-time differentially private mechanism that releases a nonnegative weighted graph H = ( V , w H ) H=(V,w_H) H = ( V , w H ) satisfying, simultaneously for every cut S S S ,
∣ w G ( S , V ∖ S ) − w H ( S , V ∖ S ) ∣ ≤ γ w G ( S , V ∖ S ) + B , (1) |w_G(S,V\setminus S)-w_H(S,V\setminus S)|\leq\gamma w_G(S,V\setminus S)+B, \tag*{(1)} ∣ w G ( S , V ∖ S ) − w H ( S , V ∖ S ) ∣ ≤ γ w G ( S , V ∖ S ) + B , (1)
with additive error B B B as small as possible. The relative term makes the guarantee uninformative for sparse graphs: with purely additive error (γ = 0 \gamma=0 γ = 0 ), an error of order n 3 / 2 n^{3/2} n 3/2 , up to logarithmic factors, is unavoidable in the worst case over graphs with Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) edges [6 , 12 ] . This error can exceed every cut value of a sparse graph.
Table 1 summarizes the known bounds. In the purely additive setting, independent noise on every edge weight gives additive error O ~ ( n 3 / 2 / ϵ ) \widetilde{O}(n^{3/2}/\epsilon) O ( n 3/2 / ϵ ) , where O ~ \widetilde{O} O hides logarithmic factors, including the dependence on δ \delta δ . Following earlier work by Gupta, Roth, and Ullman [9 ] and Eliáš, Kapralov, Kulkarni, and Lee [6 ] , Liu, Upadhyay, and Zou [12 ] obtained O ~ ( m n / ϵ ) \widetilde{O}(\sqrt{mn}/\epsilon) O ( mn / ϵ ) additive error for graphs with m m m weighted edges, which is tight for dense graphs up to logarithmic factors. With relative error, Blocki, Blum, Datta, and Sheffet [2 ] obtained nearly linear additive error by applying the exponential mechanism to the exponentially large family of sparse graphs; no polynomial-time implementation is known. Aamand et al. [1 ] gave the first polynomial-time mechanism below the n 3 / 2 n^{3/2} n 3/2 scale, with additive error n 5 / 4 + o ( 1 ) n^{5/4+o(1)} n 5/4 + o ( 1 ) for constant γ \gamma γ and ϵ \epsilon ϵ , using a private expander decomposition, and Fan et al. [7 ] reduced the additive error to n 13 / 12 + o ( 1 ) n^{13/12+o(1)} n 13/12 + o ( 1 ) for unweighted inputs through degree-sensitive private spectral primitives.
Table 1. Error bounds for private all-cut release on n n n -vertex graphs, with m = ∥ w G ∥ 0 m = \lVert w_G\rVert_0 m = ∥ w G ∥ 0 . We fix constant ϵ \epsilon ϵ , γ \gamma γ and δ = β = n − c \delta= \beta= n^{-c} δ = β = n − c for constant c ≥ 2 c \ge2 c ≥ 2 ; O ~ \widetilde{O} O hides polylogarithmic factors. *Information-theoretic exponential mechanism. †Unweighted inputs.
Most recently, Eliáš et al. [5 ] gave the first polynomial-time algorithm with nearly linear additive error, B = O ( ϵ − 1 γ − 1 n log 7 ( n / ( γ ϵ δ β ) ) ) B = O(\epsilon^{-1}\gamma^{-1}n\log^7(n/(\gamma\epsilon\delta\beta))) B = O ( ϵ − 1 γ − 1 n log 7 ( n / ( γ ϵδ β ))) for arbitrary nonnegative weighted graphs. They also prove a lower bound of Ω ( ( n / ϵ ) min { n , 1 / γ } ) \Omega((n/\epsilon)\min\{\sqrt{n},1/\gamma\}) Ω (( n / ϵ ) min { n , 1/ γ }) for 0 < γ ≤ 1 / 4 0 < \gamma\le1/4 0 < γ ≤ 1/4 , δ ≤ ϵ / 100 \delta\le\epsilon/100 δ ≤ ϵ /100 , and β ≤ 1 / 40 \beta\le1/40 β ≤ 1/40 . For fixed γ \gamma γ and ϵ \epsilon ϵ and inverse-polynomial δ \delta δ and β \beta β , the optimal additive error was therefore known to lie between Ω ( n ) \Omega(n) Ω ( n ) and O ( n log 7 n ) O(n\log^7 n) O ( n log 7 n ) . We show that it is Θ ( n log n ) \Theta(n\log n) Θ ( n log n ) : a single logarithmic factor is both sufficient, in polynomial time, and necessary.
Our results
Theorem 1.1 (Weighted cut release). Fix a constant c ≥ 1 c \ge1 c ≥ 1 . Let n ≥ 2 n \ge2 n ≥ 2 , n − c ≤ γ ≤ 1 / 4 n^{-c} \le\gamma\le1/4 n − c ≤ γ ≤ 1/4 , n − c ≤ ϵ ≤ 1 n^{-c} \le\epsilon\le1 n − c ≤ ϵ ≤ 1 , and n − c ≤ δ , β < 1 / 10 n^{-c} \le\delta, \beta< 1/10 n − c ≤ δ , β < 1/10 . There is an ( ϵ , δ ) (\epsilon,\delta) ( ϵ , δ ) -differentially private algorithm that, given any nonnegative weighted graph G = ( V , w G ) G = (V,w_G) G = ( V , w G ) on V = [ n ] V = [n] V = [ n ] , outputs a nonnegative weighted graph H = ( V , w H ) H = (V,w_H) H = ( V , w H ) satisfying, with probability at least 1 − β 1-\beta 1 − β , simultaneously for all S ⊆ V S \subseteq V S ⊆ V ,
∣ w G ( S , V ∖ S ) − w H ( S , V ∖ S ) ∣ ≤ γ w G ( S , V ∖ S ) + O ( n log n ϵ γ ) . (2) \lvert w_G(S,V \setminus S)-w_H(S,V \setminus S)\rvert\le\gamma w_G(S,V \setminus S)+O\left(\frac{n\log n}{\epsilon\gamma}\right). \tag*{(2)} ∣ w G ( S , V ∖ S ) − w H ( S , V ∖ S )∣ ≤ γ w G ( S , V ∖ S ) + O ( ϵ γ n log n ) . (2) The implied constant depends only on c c c . For rational inputs, the running time is polynomial in n n n and the input encoding length.
The inverse-polynomial assumptions allow the additive error to be written as O ( ( n / ( ϵ γ ) ) log n ) O((n/(\epsilon\gamma))\log n) O (( n / ( ϵ γ )) log n ) . Without these assumptions, the analysis gives the more general bound in (25) , which makes the dependence on γ , ϵ , δ , β \gamma,\epsilon,\delta,\beta γ , ϵ , δ , β explicit.
Theorem 1.2 (Lower bound). Fix a constant κ ∈ ( 0 , 1 / 2 ) \kappa\in(0,1/2) κ ∈ ( 0 , 1/2 ) . For sufficiently large n n n , let n − 1 / 2 + κ ≤ γ ≤ 1 / 4 n^{-1/2+\kappa} \le\gamma\le1/4 n − 1/2 + κ ≤ γ ≤ 1/4 , 0 < ε ≤ 1 0 < \varepsilon\le1 0 < ε ≤ 1 , 0 ≤ δ ≤ ε / n 2 0 \le\delta\le\varepsilon/n^2 0 ≤ δ ≤ ε / n 2 , and 0 ≤ β ≤ 1 / 4 0 \le\beta\le1/4 0 ≤ β ≤ 1/4 . Any ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -differentially private mechanism that, on every nonnegative weighted input graph G G G on [ n ] [n] [ n ] , outputs a nonnegative weighted graph H H H satisfying (1) simultaneously for all cuts with probability at least 1 − β 1-\beta 1 − β must have
B = Ω ( n log n ε γ ) . (3) B = \Omega\left(\frac{n\log n}{\varepsilon\gamma}\right). \tag*{(3)} B = Ω ( ε γ n log n ) . (3) The implied constant depends only on κ \kappa κ .
Together, Theorems 1.1 and 1.2 determine the optimal additive error Θ ( n log n / ( ε γ ) ) \Theta(n\log n/(\varepsilon\gamma)) Θ ( n log n / ( ε γ )) under their common parameter assumptions. In particular, the optimal error is Θ ( n log n ) \Theta(n\log n) Θ ( n log n ) for constant γ \gamma γ , ε \varepsilon ε and δ = β = n − 10 \delta=\beta=n^{-10} δ = β = n − 10 . § 5 gives a more general lower bound.
Technical overview
The logarithm in our bound reflects the cost of making many noisy decisions accurate simultaneously while keeping the total privacy loss small. We account for these costs, together with the logarithm in the initial entropy potential, through the parameter
σ = Θ ( 1 ε log n γ ε δ β ) . \sigma= \Theta\left(\frac{1}{\varepsilon}\log\frac{n}{\gamma\varepsilon\delta\beta}\right). σ = Θ ( ε 1 log γ ε δ β n ) .
The guiding principle of the design is to pay this logarithm only once: neither the number of degree layers nor the number of trials should introduce another logarithmic factor. In the parameter range of Theorem 1.1 , our mechanism achieves a total additive error of O ( n σ / γ ) O(n\sigma/\gamma) O ( nσ / γ ) . We first recall the framework we build on and then describe the three ideas that achieve this.
Private multiplicative weights with a semidefinite oracle. Our mechanism is a private multiplicative-weights search [11 ] . It maintains a public candidate graph h h h , repeatedly looks for a cut on which h h h is inaccurate, and then scales the edges of h h h across that cut up or down, depending on whether h h h underestimates or overestimates the cut. Progress is measured by the relative entropy between the private graph and h h h , which decreases with every good update. The most violated cut cannot be used directly: finding it is NP-hard, and small input changes can change the maximizing cut abruptly, making its direct release incompatible with privacy. As in [6 , 7 , 5 ] , we instead solve a semidefinite relaxation of the cut problem regularized by λ log det X \lambda\log\det X λ log det X . Its optimizer X X X is a covariance matrix, and a Gaussian vector z ∼ N ( 0 , X ) z\sim N(0,X) z ∼ N ( 0 , X ) assigns each pair u v uv uv a nonnegative score ( z u − z v ) 2 / 4 (z_u-z_v)^2/4 ( z u − z v ) 2 /4 , giving a random update direction. The log-determinant term makes X X X insensitive to small changes of the private graph, so the sample z z z can be released at a cost of O ( α / λ 2 ) O(\alpha/\lambda^2) O ( α / λ 2 ) in Rényi divergence of order α \alpha α , provided α / λ \alpha/\lambda α / λ is sufficiently small (Lemma 4.3).
The price of this stability is accuracy. The regularization blurs the cut that the oracle finds, and Lemma 4.2 shows that the resulting error is a sum over the vertices, in which a vertex of effective degree d d d in the oracle contributes about λ 2 / ( λ + γ d ) \lambda^2/(\lambda+\gamma d) λ 2 / ( λ + γ d ) . A vertex whose degree is large compared with λ / γ \lambda/\gamma λ / γ thus contributes little, whereas a vertex of small degree contributes about λ \lambda λ . The regularization parameter therefore governs a trade-off: a large λ \lambda λ makes each sample cheap in privacy, and a small λ \lambda λ makes the cut accurate.
Degree layers. Since the error of a vertex depends on its degree, no single value of λ \lambda λ suits all vertices. We therefore decompose the graph by degree and release each part with its own regularization parameter. A private peeling procedure repeatedly removes the vertices whose remaining degree falls below a threshold, where the thresholds D 0 < D 1 < ⋯ D_0 < D_1 < \cdots D 0 < D 1 < ⋯ double from stage to stage. The vertices removed at stage j j j form the layer L j L_j L j , and each edge is assigned to the lower layer of its endpoints. Layer j j j is released with λ j = σ D j \lambda_j = \sqrt{\sigma D_j} λ j = σ D j , a choice that balances privacy and accuracy within the layer. On the accuracy side, every vertex of a layer j ≥ 1 j \ge1 j ≥ 1 has degree at least D j / 4 D_j/4 D j /4 , so it contributes O ( λ j 2 / ( γ D j ) ) = O ( σ / γ ) O(\lambda_j^2/(\gamma D_j)) = O(\sigma/\gamma) O ( λ j 2 / ( γ D j )) = O ( σ / γ ) to the error; in layer zero, λ 0 = Θ ( σ / γ ) \lambda_0 = \Theta(\sigma/\gamma) λ 0 = Θ ( σ / γ ) is small enough by itself. The corresponding privacy balance is explained below.
One difficulty remains: a vertex of a higher layer also belongs to the vertex sets of the lower layers, where its degree may be small and its error contribution large. We release the layers from the top down and add to the oracle a public prior built from the already released higher layers, with geometrically decreasing weights. The prior supplies these vertices with enough degree that a vertex k − j k-j k − j layers above layer j j j contributes only a ( 2 / 3 ) k − j (2/3)^{k-j} ( 2/3 ) k − j fraction of O ( σ / γ ) O(\sigma/\gamma) O ( σ / γ ) , so the total error remains O ( n σ / γ ) O(n\sigma/\gamma) O ( nσ / γ ) .
The oracle’s error also contains a term proportional to the degree discrepancy between the candidate and the true layer. We release noisy degrees of each layer and confine the search for layer j j j to a public convex confidence set K j K_j K j of graphs whose degrees, mass, and minimum degrees are consistent with this information. With high probability, K j K_j K j contains the true layer, which therefore remains a valid target for the relative-entropy potential, and the total degree discrepancy over all layers is only O ( n σ ) O(n\sigma) O ( nσ ) . Finally, since the oracle needs bounded edge weights and no bound on the input weights is public, a thresholded Laplace mechanism first releases the part of every edge weight above a cap U = Θ ( σ / γ ) U = \Theta(\sigma/\gamma) U = Θ ( σ / γ ) , which costs relative error at most γ / 2 \gamma/2 γ /2 .
One sample per trial, checked before use. Within a layer, the search proceeds in trials. A trial draws a single Gaussian sample from the oracle and turns the resulting edge scores into a bounded multiplicative update of the candidate. A single sample is a noisy direction: it makes progress only with constant probability (Lemma 4.4 ), and averaging many samples to obtain a reliable direction would multiply the privacy cost of a trial by their number. Instead, we check each sample before using it. The decrease of the potential caused by the update has an exact closed form in terms of the sample and the private graph, and it depends linearly on the latter. The trial adds Laplace noise to this decrease and applies the update only if the noisy value is large; otherwise the candidate stays unchanged. On the high-probability event that all validation noises are bounded, every accepted update makes definite progress. Rejected proposals leave the potential unchanged. Since the potential of a layer of mass M M M is initially at most O ( M log n ) O(M\log n) O ( M log n ) , only a bounded number of updates can be accepted, while a candidate with a large error is improved with constant probability in every trial. An accurate candidate therefore appears within a bounded number of trials, and the exponential mechanism selects one at the end (Lemma 4.5 ).
Privacy accounting. A trial reveals both the Gaussian sample and the noisy validation. The sample is private by the stability of the oracle. For the validation, the point is that the updates are gentle: before projection, their multiplicative factors lie in [ 1 / 2 , 2 ] [1/2,2] [ 1/2 , 2 ] , and the absolute values of their logarithms are at most the step size times the sampled edge scores. A change of the private graph therefore moves the validated quantity by at most the step size times a weighted average of the sampled edge scores. The validation noise has scale proportional to the step size times λ \lambda λ . We control the exponential moments of this random shift and analyze the sample and its validation jointly. For an input change of total edge weight s ≤ 1 s \le1 s ≤ 1 , a trial costs O ( α s 2 / λ 2 ) O(\alpha s^2/\lambda^2) O ( α s 2 / λ 2 ) in Rényi divergence of order α \alpha α , whether or not its proposal is accepted (Lemma 4.6 ). Rejected proposals thus need no separate accounting.
A layer with threshold D j D_j D j uses O ( ε D j ) O(\varepsilon D_j) O ( ε D j ) trials, each costing O ( α s j 2 / ( σ D j ) ) O(\alpha s_j^2/(\sigma D_j)) O ( α s j 2 / ( σ D j )) , where s j s_j s j is the total edge-weight change in that layer. Its total trial cost is therefore O ( α ε s j 2 / σ ) O(\alpha\varepsilon s_j^2/\sigma) O ( α ε s j 2 / σ ) . Conditional on the preprocessing transcript, each edge belongs to exactly one layer, so a unit change of the input satisfies ∑ j s j ≤ 1 \sum_j s_j \le1 ∑ j s j ≤ 1 and hence ∑ j s j 2 ≤ 1 \sum_j s_j^2 \le1 ∑ j s j 2 ≤ 1 . Thus composition incurs no extra factor for the number of layers. Composing all trials in Rényi divergence and converting to approximate differential privacy once at the end proves privacy (Proposition 4.8 ). The accuracy guarantees add up in the same way: every vertex contributes O ( σ / γ ) O(\sigma/\gamma) O ( σ / γ ) , the remaining error terms of the layers grow geometrically with λ j \lambda_j λ j and give the second term of (4.8), and the relative errors add up because the discounted priors have total weight at most three times that of the released graph (§ 4.4 ).
The lower bound. The lower bound shows that one logarithm is the unavoidable price of hiding which edges are present. Consider random bipartite graphs with n ˉ = ⌊ n / 2 ⌋ \bar n=\lfloor n/2\rfloor n ˉ = ⌊ n /2 ⌋ vertices on each side, in which every left vertex has d d d neighbors and every edge has weight W W W . We decode the private output to a graph in the same family. If we delete a random edge, its missing endpoint is uniform among about n ˉ \bar n n ˉ positions, so the decoder, run on the graph without this edge, recovers the endpoint with probability O ( d / n ˉ ) O(d/\bar n) O ( d / n ˉ ) . Restoring the edge is a change of W W W units, and group privacy raises this probability by at most a factor e ε W e^{\varepsilon W} e ε W , plus a δ \delta δ -dependent additive term. Taking W W W to be a sufficiently small constant multiple of ε − 1 min { log ( n ˉ / d ) , log ( ε / δ ) } \varepsilon^{-1}\min\{\log(\bar n/d),\log(\varepsilon/\delta)\} ε − 1 min { log ( n ˉ / d ) , log ( ε / δ )} therefore leaves most edges unrecovered; the second logarithm is infinite when δ = 0 \delta=0 δ = 0 . Accurate cut values would rule this out: random signs on the right vertices, with the left signs chosen to maximize the discrepancy, give a random cut with expected discrepancy of order W n ˉ d W\bar n\sqrt{d} W n ˉ d , while the expected combined cut value is W n ˉ d W\bar n d W n ˉ d . Choosing d = Θ ( min { n , γ − 2 } ) d=\Theta(\min\{n,\gamma^{-2}\}) d = Θ ( min { n , γ − 2 }) , with a sufficiently small constant, prevents the relative term γ W n ˉ d \gamma W\bar n d γ W n ˉ d from absorbing this discrepancy. The additive error must therefore be Ω ( W n ˉ d ) \Omega(W\bar n\sqrt{d}) Ω ( W n ˉ d ) , yielding (5.1) and hence (1.3).
Comparison with Eliáš et al.
Like [5 ] , we release the heavy part of each edge weight by a thresholded Laplace mechanism, find violated cuts with a log-determinant-regularized semidefinite program accessed through Gaussian samples [6 , 7 ] , and check sampled proposals with noise before using them. The difference lies in how progress is organized. Their mechanism follows the PREM framework [GKK+25]: with L = Θ ( log ( n / ( γ ε δ ) ) ) L=\Theta(\log(n/(\gamma\varepsilon\delta))) L = Θ ( log ( n / ( γ ε δ ))) , it runs O ( L ) O(L) O ( L ) rounds of O ( L / γ 2 ) O(L/\gamma^2) O ( L / γ 2 ) multiplicative-weights steps, and each step uses an aggregate witness built from many fractional witnesses, each estimated by averaging O ( L ) O(L) O ( L ) Gaussian samples. Their analysis [5 Section 5.2] incurs two factors of L L L from the rounds, through error accumulation and privacy composition, one from composition over the steps, and two from success-charged composition within an aggregation. The high-probability bound on the privacy loss of the Gaussian samples and the certificate term of order λ n log n \lambda n\log n λn log n each contribute another factor, giving additive error O ( n L 7 / ( γ ε ) ) O(nL^7/(\gamma\varepsilon)) O ( n L 7 / ( γ ε )) .
We replace the rounds with a single degree decomposition whose layers add up in both error and privacy without a factor for their number. Each trial uses one Gaussian sample and tests a noisy estimate of its entropy decrease before projection, ensuring with high probability that every accepted update makes definite progress without aggregation. Since a trial has the same Rényi cost whether or not it is accepted, all trials are composed in Rényi divergence and converted to approximate differential privacy once. Together with our degree-sensitive certificate, which has no n log n n\log n n log n term, this ensures that the only logarithm in our bound is the one in the noise scale σ \sigma σ .
Organization. § 2 gives preliminaries, § 3 the mechanism, § 4 its analysis and the proof of Theorem 1.1 , and § 5 the proof of Theorem 1.2 and its consequences. Appendix § 6 describes a finite-precision implementation.
Preliminaries
We fix notation and recall the semidefinite relaxation, the privacy primitives, and the relative entropy used as our potential. All logarithms are natural. Unless stated otherwise, asymptotic notation hides absolute constants, and the letters C , c C,c C , c denote positive absolute constants whose values may change from one occurrence to the next; the algorithmic constants are fixed in the order specified below. Products x ⊙ y x \odot y x ⊙ y , powers, and logarithms of vectors are taken coordinatewise, and ⟨ x , y ⟩ \langle x,y\rangle ⟨ x , y ⟩ denotes the usual inner product.
Graphs and cuts. We identify a weighted graph on the public vertex set V V V with its edge vector in R ( V 2 ) \mathbb{R}^{\binom{V}{2}} R ( 2 V ) and write w = w G w=w_G w = w G for the input weights in the algorithm and its analysis. Edge vectors on subsets of V V V are extended by zero when needed. For any edge vector x x x , we use x ( S ) x(S) x ( S ) as shorthand for ∑ u ∈ S , v ∈ V ∖ S x u v \sum_{u\in S,v\in V\setminus S}x_{uv} ∑ u ∈ S , v ∈ V ∖ S x uv ; in particular, w ( S ) = w G ( S , V ∖ S ) w(S)=w_G(S,V\setminus S) w ( S ) = w G ( S , V ∖ S ) . For a signed edge vector w w w , such as a difference of two graphs, let A w A_w A w be its symmetric adjacency matrix with zero diagonal, deg ( w ) \operatorname{deg}(w) deg ( w ) its degree vector, and L w : = diag ( deg ( w ) ) − A w L_w:=\operatorname{diag}(\operatorname{deg}(w))-A_w L w := diag ( deg ( w )) − A w its Laplacian. We write deg w ( v ) \operatorname{deg}_w(v) deg w ( v ) for the coordinate of deg ( w ) \operatorname{deg}(w) deg ( w ) at v v v . For w ≥ 0 w\ge0 w ≥ 0 , the mass of w w w is ∥ w ∥ 1 = 1 2 ∑ v deg w ( v ) \lVert w\rVert_1=\frac{1}{2}\sum_v\operatorname{deg}_w(v) ∥ w ∥ 1 = 2 1 ∑ v deg w ( v ) .
For a symmetric matrix X X X , define the fractional cut vector q ( X ) q(X) q ( X ) by
q u v ( X ) : = 1 4 ( e u − e v ) T X ( e u − e v ) , so that ⟨ w , q ( X ) ⟩ = 1 4 tr ( L w X ) q_{uv}(X):=\frac{1}{4}(e_u-e_v)^{\mathsf T}X(e_u-e_v),\qquad\text{so that}\qquad\langle w,q(X)\rangle=\frac{1}{4}\operatorname{tr}(L_wX) q uv ( X ) := 4 1 ( e u − e v ) T X ( e u − e v ) , so that ⟨ w , q ( X )⟩ = 4 1 tr ( L w X )
for every signed edge vector w w w . If X ⪰ 0 X\succeq0 X ⪰ 0 and X v v ≤ 1 X_{vv}\le1 X v v ≤ 1 for every v v v , then q e ( X ) ∈ [ 0 , 1 ] q_e(X)\in[0,1] q e ( X ) ∈ [ 0 , 1 ] for every pair e e e . For a cut vector s ∈ { − 1 , 1 } V s\in\{-1,1\}^{V} s ∈ { − 1 , 1 } V , the vector q ( s s T ) q(ss^{\mathsf T}) q ( s s T ) is the incidence vector of the corresponding cut. We use the semidefinite relaxation of Goemans and Williamson [10 ] ,
SDP ( w ) : = max { ⟨ w , q ( X ) ⟩ : X ⪰ 0 , diag X = 1 } . \operatorname{SDP}(w):=\max\{\langle w,q(X)\rangle:X\succeq0,\ \operatorname{diag}X=1\}. SDP ( w ) := max {⟨ w , q ( X )⟩ : X ⪰ 0 , diag X = 1 } .
It is nonnegative (take X = 11 T X=11^{\mathsf T} X = 1 1 T ), dominates every cut value (take X = s s T X=ss^{\mathsf T} X = s s T ), and is 1-Lipschitz in ℓ 1 \ell_1 ℓ 1 , that is, ∣ SDP ( w ) − SDP ( w ′ ) ∣ ≤ ∥ w − w ′ ∥ 1 \lvert\operatorname{SDP}(w)-\operatorname{SDP}(w')\rvert\le\lVert w-w'\rVert_1 ∣ SDP ( w ) − SDP ( w ′ )∣ ≤ ∥ w − w ′ ∥ 1 , because q ( X ) ∈ [ 0 , 1 ] ( V 2 ) q(X)\in[0,1]^{\binom{V}{2}} q ( X ) ∈ [ 0 , 1 ] ( 2 V ) for every feasible $X.
Differential privacy. Inputs w , w ′ ≥ 0 w,w'\ge0 w , w ′ ≥ 0 are adjacent if ∥ w − w ′ ∥ 1 ≤ 1 \lVert w-w'\rVert_1\le1 ∥ w − w ′ ∥ 1 ≤ 1 ; they may differ in many coordinates. A mechanism M M M is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -differentially private if, for every ordered pair ( w , w ′ ) (w,w') ( w , w ′ ) of adjacent inputs and every measurable event A A A ,
Pr [ M ( w ) ∈ A ] ≤ e ε Pr [ M ( w ′ ) ∈ A ] + δ . \Pr[M(w)\in A]\le e^\varepsilon\Pr[M(w')\in A]+\delta. Pr [ M ( w ) ∈ A ] ≤ e ε Pr [ M ( w ′ ) ∈ A ] + δ .
The case δ = 0 \delta=0 δ = 0 is called pure privacy. We use postprocessing and adaptive composition in their standard forms [3 , 4 ] . Group privacy is needed only for the lower bound of § 5 : if two inputs w , w ′ w,w' w , w ′ are joined by k k k unit changes, then
Pr [ M ( w ) ∈ A ] ≤ e k ε Pr [ M ( w ′ ) ∈ A ] + δ ∑ i = 0 k − 1 e i ε . \Pr[M(w)\in A]\le e^{k\varepsilon}\Pr[M(w')\in A]+\delta\sum_{i=0}^{k-1}e^{i\varepsilon}. Pr [ M ( w ) ∈ A ] ≤ e k ε Pr [ M ( w ′ ) ∈ A ] + δ i = 0 ∑ k − 1 e i ε .
The mechanism of § 3 draws on three standard purely private primitives. The Laplace distribution Lap ( ζ ) \operatorname{Lap}(\zeta) Lap ( ζ ) with scale ζ > 0 \zeta>0 ζ > 0 has density e − ∣ x ∣ / ζ / ( 2 ζ ) e^{-\lvert x\rvert/\zeta}/(2\zeta) e − ∣ x ∣ / ζ / ( 2 ζ ) , and adding independent Lap ( Δ / ε ) \operatorname{Lap}(\Delta/\varepsilon) Lap ( Δ/ ε ) noise to the coordinates of a vector query of ℓ 1 \ell_1 ℓ 1 sensitivity Δ \Delta Δ is pure ε \varepsilon ε -differentially private; we use it for the heavy-edge and degree releases of § 3.1 . To choose among a public set of N N N candidates, the exponential mechanism [14 ] samples each candidate x x x with probability proportional to exp ( − ε score ( x ) / ( 2 Δ ) ) \exp(-\varepsilon\operatorname{score}(x)/(2\Delta)) exp ( − ε score ( x ) / ( 2Δ )) , where Δ \Delta Δ is the sensitivity of the score. It is pure ε \varepsilon ε -differentially private and, with probability at least 1 − β 1-\beta 1 − β , returns a candidate whose score is within 2 Δ log ( N / β ) / ε 2\Delta\log(N/\beta)/\varepsilon 2Δ log ( N / β ) / ε of the minimum; each layer selects its output in this way.
The third primitive, the one-positive AboveThreshold algorithm [4 ] , performs the degree comparisons of the peeling step. We state it for a generic privacy parameter ε ′ > 0 \varepsilon' > 0 ε ′ > 0 : it uses threshold zero, threshold noise Lap ( 2 / ε ′ ) \operatorname{Lap}(2/\varepsilon') Lap ( 2/ ε ′ ) , and independent query noise Lap ( 4 / ε ′ ) \operatorname{Lap}(4/\varepsilon') Lap ( 4/ ε ′ ) . It answers a sequence of possibly adaptive queries and stops at the first positive comparison. The density-shift proof of its privacy bounds the likelihood ratio of its transcript by e ε ′ Δ e^{\varepsilon'\Delta} e ε ′ Δ whenever every query changes by at most Δ \Delta Δ , for any real Δ ≥ 0 \Delta\ge0 Δ ≥ 0 . Fractional values of Δ \Delta Δ arise because a unit change of the input may change many degrees, each by less than one.
The trials within each layer are not of this pure form: they release Gaussian samples, and we account for the privacy of the layer releases through Rényi divergence. For α > 1 \alpha> 1 α > 1 , the Rényi divergence of order α \alpha α is
D α ( P ∥ Q ) : = 1 α − 1 log E x ∼ P [ ( d P d Q ( x ) ) α − 1 ] . D_\alpha(P\mathbin{\|}Q) := \frac{1}{\alpha-1}\log\mathbb{E}_{x\sim P}\left[\left(\frac{dP}{dQ}(x)\right)^{\alpha-1}\right]. D α ( P ∥ Q ) := α − 1 1 log E x ∼ P [ ( d Q d P ( x ) ) α − 1 ] .
A mechanism is ( α , ρ ) (\alpha,\rho) ( α , ρ ) -RDP if this divergence between its output distributions is at most ρ \rho ρ for every ordered pair of adjacent inputs; it is then ( ρ + log ( 1 / δ ) / ( α − 1 ) , δ ) (\rho+\log(1/\delta)/(\alpha-1),\delta) ( ρ + log ( 1/ δ ) / ( α − 1 ) , δ ) -differentially private for every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) [13 ] . We apply this conversion only once, to all layer releases together (Proposition 4.8 ).
Relative entropy. For nonnegative edge vectors f , h f,h f , h , define the unnormalized relative entropy by
D K L ( f ∥ h ) : = ∑ e [ f e log f e h e − f e + h e ] . D_{\mathrm{KL}}(f\mathbin{\|}h) := \sum_e\left[f_e\log\frac{f_e}{h_e}-f_e+h_e\right]. D KL ( f ∥ h ) := e ∑ [ f e log h e f e − f e + h e ] .
We allow f f f and h h h to have different total masses and use the usual conventions at zero. Each summand is nonnegative, so D K L ( f ∥ h ) ≥ 0 D_{\mathrm{KL}}(f\mathbin{\|}h)\ge0 D KL ( f ∥ h ) ≥ 0 .
The algorithm
We now specify the mechanism outlined in § 1.2 ; § 4 analyzes it. The mechanism first releases the part of every edge weight above a public cap, peels the remaining capped graph into degree layers, and builds a public confidence set for each layer (§ 3.1 ). It then releases the layers one at a time, in decreasing order, by the entropy search of § 3.2 .
All releases draw on a common privacy and failure budget. We set ε 0 = ε / 10 \varepsilon_0=\varepsilon/10 ε 0 = ε /10 and β 0 = β / 10 \beta_0=\beta/10 β 0 = β /10 . Each preprocessing release and the final selection use privacy budget ε 0 \varepsilon_0 ε 0 ; the trials and the numerical implementation use the remaining allowance. Each preprocessing accuracy event has failure probability at most β 0 \beta_0 β 0 , and each layer uses ζ = β 0 / ( J + 1 ) \zeta=\beta_0/(J+1) ζ = β 0 / ( J + 1 ) , where J J J is the peeling horizon (3.3). The calibration parameter, the relative slack, the cap, the degree thresholds, and the regularization parameters are
σ : = C σ ε log n γ ε δ β , a : = γ 40 , U : = C U σ γ , D j : = 2 j C D σ γ 2 , λ j : = σ D j . (4) \begin{aligned}
\sigma&:= \frac{C_\sigma}{\varepsilon}\log\frac{n}{\gamma\varepsilon\delta\beta}, \qquad
a := \frac{\gamma}{40}, \qquad
U := \frac{C_U\sigma}{\gamma},\\
D_j &:= \frac{2^j C_D\sigma}{\gamma^2}, \qquad
\lambda_j := \sqrt{\sigma D_j}. \tag*{(4)}
\end{aligned} σ D j := ε C σ log γ ε δ β n , a := 40 γ , U := γ C U σ , := γ 2 2 j C D σ , λ j := σ D j . (4)
We choose the absolute constants in the order C σ , C U , C D C_\sigma,C_U,C_D C σ , C U , C D , with C D C_D C D sufficiently large that λ j ≥ 5 U \lambda_j\ge5U λ j ≥ 5 U for every j j j and the noise bounds below hold.
Each of these parameters has a distinct role. The calibration parameter σ \sigma σ carries the single logarithmic factor of the final bound, a a a is the relative slack of each layer, and U U U is the cap above which weights are released directly. The condition λ j ≥ 5 U \lambda_j \ge5U λ j ≥ 5 U keeps the edge weights seen by the oracle below λ j \lambda_j λ j , as Lemma 4.2 requires. Finally, the choice λ j 2 = σ D j \lambda_j^2 = \sigma D_j λ j 2 = σ D j balances the Rényi cost of a trial, which scales as 1 / λ j 2 1/\lambda_j^2 1/ λ j 2 (Lemma 4.6 ), against the harmonic error term of the oracle, which carries a factor λ j 2 \lambda_j^2 λ j 2 (§ 4.4 ).
Degree decomposition
The mechanism begins by separating the heavy part of every edge, so that all later steps see bounded weights. We keep the capped weights b e = min { w e , U } b_e = \min\{w_e,U\} b e = min { w e , U } private and release the excess above the cap by a thresholded Laplace mechanism,
Y e : = ( ( w e − U ) + + Z e − t h ) + , t h : = 1 ε 0 log 2 ( n 2 ) β 0 , (5) Y_e := \left((w_e-U)_+ + Z_e-t_{\mathrm{h}}\right)_+,\qquad t_{\mathrm{h}} := \frac{1}{\varepsilon_0}\log\frac{2\binom{n}{2}}{\beta_0}, \tag*{(5)} Y e := ( ( w e − U ) + + Z e − t h ) + , t h := ε 0 1 log β 0 2 ( 2 n ) , (5)
where the noise variables Z e ∼ Lap ( 1 / ε 0 ) Z_e \sim\operatorname{Lap}(1/\varepsilon_0) Z e ∼ Lap ( 1/ ε 0 ) are independent. The excess map is an ℓ 1 \ell_1 ℓ 1 contraction, so this release is pure ε 0 \varepsilon_0 ε 0 -DP. With probability at least 1 − β 0 1-\beta_0 1 − β 0 , all ∣ Z e ∣ ≤ t h |Z_e| \le t_{\mathrm{h}} ∣ Z e ∣ ≤ t h . Then Y e Y_e Y e underestimates the excess by at most 2 t h 2t_{\mathrm{h}} 2 t h and vanishes when the excess is zero. Since U ≥ 4 t h / γ U \ge4t_{\mathrm{h}}/\gamma U ≥ 4 t h / γ , every cut satisfies ∣ Y ( S ) + b ( S ) − w ( S ) ∣ ≤ ( γ / 2 ) w ( S ) |Y(S)+b(S)-w(S)| \le(\gamma/2)w(S) ∣ Y ( S ) + b ( S ) − w ( S ) ∣ ≤ ( γ /2 ) w ( S ) .
We next partition the vertices by their degrees in b b b . The peeling uses the public horizon, query bound, and noise threshold
J : = max { 0 , ⌈ log 2 2 ( n − 1 ) U D 0 ⌉ } , Q c : = n ( n + J + 1 ) , τ c : = C ε 0 log C ( n + Q c ) β 0 . (6) J := \max\left\{0,\left\lceil\log_2\frac{2(n-1)U}{D_0}\right\rceil\right\},\qquad Q_c := n(n+J+1),\qquad\tau_c := \frac{C}{\varepsilon_0}\log\frac{C(n+Q_c)}{\beta_0}. \tag*{(6)} J := max { 0 , ⌈ log 2 D 0 2 ( n − 1 ) U ⌉ } , Q c := n ( n + J + 1 ) , τ c := ε 0 C log β 0 C ( n + Q c ) . (6)
Thus D J ≥ 2 ( n − 1 ) U D_J \ge2(n-1)U D J ≥ 2 ( n − 1 ) U , twice the largest possible degree in b b b ; Q c Q_c Q c bounds the number of threshold queries, and τ c \tau_c τ c bounds the error of all threshold comparisons with high probability. Our parameter choices ensure D 0 ≥ 16 τ c D_0 \ge16\tau_c D 0 ≥ 16 τ c and U ≥ τ c U \ge\tau_c U ≥ τ c .
The comparisons themselves are made by AboveThreshold. We give each vertex an independent, persistent one-positive AboveThreshold instance (§ 2 ) with privacy ε 0 / 2 \varepsilon_0/2 ε 0 /2 , threshold zero, threshold-noise scale 4 / ε 0 4/\varepsilon_0 4/ ε 0 , and query-noise scale 8 / ε 0 8/\varepsilon_0 8/ ε 0 . Initially, W = V W=V W = V . At stage j = 0 , … , J j=0,\ldots,J j = 0 , … , J , we scan the active set W W W in a public order, querying D j − deg b [ W ] ( v ) D_j-\deg_{b[W]}(v) D j − deg b [ W ] ( v ) for each vertex v v v . A positive answer removes v v v permanently and restarts the scan. A complete scan without removal ends the stage; the instances persist across stages. Let L j L_j L j contain the vertices removed at stage j j j , with any remaining vertices assigned to L J L_J L J . Put V j = ⋃ k ≥ j L k V_j=\bigcup_{k\ge j}L_k V j = ⋃ k ≥ j L k , the active set at the start of stage j j j , and n j = ∣ L j ∣ n_j=|L_j| n j = ∣ L j ∣ . We assign each edge to the minimum layer of its endpoints and write b = ∑ j b j b=\sum_j b_j b = ∑ j b j , so that b j b_j b j is a graph on V j V_j V j . Thus, b j b_j b j consists of the edges of b [ V j ] b[V_j] b [ V j ] with at least one endpoint in L j L_j L j .
The layers determine what degree information is released. We release the concatenated degree vectors of the b j b_j b j by adding independent Lap ( 2 / ε 0 ) \operatorname{Lap}(2/\varepsilon_0) Lap ( 2/ ε 0 ) noise, then clamp each coordinate to [ 0 , ( n − 1 ) U ] [0,(n-1)U] [ 0 , ( n − 1 ) U ] , obtaining y ( j ) y^{(j)} y ( j ) . With m j = ( ∣ V j ∣ 2 ) m_j=\binom{|V_j|}{2} m j = ( 2 ∣ V j ∣ ) , the degree radius and the mass bound of layer j j j are
R j : = C r ε 0 ( ∣ V j ∣ + log C ( J + 1 ) β 0 ) , M j : = min { 2 n j D j , m j U } , R_j := \frac{C_r}{\varepsilon_0}\left(|V_j|+\log\frac{C(J+1)}{\beta_0}\right),\qquad M_j := \min\{2n_jD_j,m_jU\}, R j := ε 0 C r ( ∣ V j ∣ + log β 0 C ( J + 1 ) ) , M j := min { 2 n j D j , m j U } ,
and the confidence set of layer j j j consists of the graphs h h h on V j V_j V j that are consistent with the released degrees and with the peeling,
K j : = { 0 ≤ h ≤ U : ∥ deg ( h ) − y ( j ) ∥ 1 ≤ R j , ∥ h ∥ 1 ≤ M j , \mathcal{K}_j := \left\{0\le h\le U:\|\deg(h)-y^{(j)}\|_1\le R_j,\ \|h\|_1\le M_j,\right. K j := { 0 ≤ h ≤ U : ∥ deg ( h ) − y ( j ) ∥ 1 ≤ R j , ∥ h ∥ 1 ≤ M j ,
deg h ( v ) ≥ D j 4 for all v ∈ L j if j ≥ 1 } . (7) \left.\deg_h(v)\ge\frac{D_j}{4}\ \text{for all }v\in L_j\text{ if }j\ge1\right\}. \tag*{(7)} deg h ( v ) ≥ 4 D j for all v ∈ L j if j ≥ 1 } . (7)
The mass and lower-degree constraints come directly from the peeling guarantees in the following lemma, which collects the properties of the decomposition used in the analysis.
Lemma 3.1 (Degree decomposition). The layer and degree releases are pure 2 ε 0 2\varepsilon_0 2 ε 0 -DP. For a fixed preprocessing transcript, adjacent inputs satisfy
∑ j s j ≤ 1 , where s j : = ∥ b j − b j ′ ∥ 1 . (8) \sum_j s_j \le1, \qquad\text{where } s_j := \lVert b_j-b'_j\rVert_1. \tag*{(8)} j ∑ s j ≤ 1 , where s j := ∥ b j − b j ′ ∥ 1 . (8) The construction makes at most Q c Q_{\mathrm{c}} Q c threshold queries. With probability at least 1 − 2 β 0 1-2\beta_0 1 − 2 β 0 , every b j ∈ K j b_j\in\mathcal{K}_j b j ∈ K j , and every h ∈ K j h\in\mathcal{K}_j h ∈ K j satisfies ∥ deg ( h ) − deg ( b j ) ∥ 1 ≤ 2 R j \lVert\deg(h)-\deg(b_j)\rVert_1\le2R_j ∥ deg ( h ) − deg ( b j ) ∥ 1 ≤ 2 R j . Moreover,
∑ j R j ≤ C ε 0 [ n ( J + 1 ) + ( J + 1 ) log C ( J + 1 ) β 0 ] = O ( n σ ) . (9) \sum_j R_j \le\frac{C}{\varepsilon_0}\left[n(J+1)+(J+1)\log\frac{C(J+1)}{\beta_0}\right]=O(n\sigma). \tag*{(9)} j ∑ R j ≤ ε 0 C [ n ( J + 1 ) + ( J + 1 ) log β 0 C ( J + 1 ) ] = O ( nσ ) . (9) Proof. We begin with the privacy of peeling. Fix a transcript and put Δ v = ∑ e ∋ v ∣ b e − b e ′ ∣ \Delta_v=\sum_{e\ni v}|b_e-b'_e| Δ v = ∑ e ∋ v ∣ b e − b e ′ ∣ . The transcript fixes the active sets and queries, and each query of v v v changes by at most Δ v \Delta_v Δ v . The AboveThreshold density-shift proof therefore bounds the likelihood ratio of the transcript at vertex v v v by e ε 0 Δ v / 2 e^{\varepsilon_0\Delta_v/2} e ε 0 Δ v /2 , including when Δ v < 1 \Delta_v<1 Δ v < 1 . The instances use independent randomness, so multiplying these bounds and using ∑ v Δ v = 2 ∥ b − b ′ ∥ 1 \sum_v\Delta_v=2\lVert b-b'\rVert_1 ∑ v Δ v = 2 ∥ b − b ′ ∥ 1 proves privacy. Each scan makes at most n n n queries, and there are at most n n n removals and J + 1 J+1 J + 1 completed scans. Conditional on the partition, the concatenated degree query has sensitivity two: each edge contributes to two coordinates of one layer. Clamping is postprocessing. The same edge partition gives (8) .
For accuracy, except with probability β 0 \beta_0 β 0 , removals have current degree at most D j + τ c D_j+\tau_{\mathrm{c}} D j + τ c and rejections at least D j − τ c D_j-\tau_{\mathrm{c}} D j − τ c . Since D J ≥ 2 ( n − 1 ) U D_J\ge2(n-1)U D J ≥ 2 ( n − 1 ) U , all vertices are removed by the last stage. The final rejection scan at stage j − 1 j-1 j − 1 has active set V j V_j V j , and all of the degree of a vertex v ∈ L j v\in L_j v ∈ L j in b [ V j ] b[V_j] b [ V j ] belongs to b j b_j b j . Charging each edge to its first removed endpoint gives
deg b j ( v ) ≥ D j 4 for all v ∈ L j if j ≥ 1 , ∥ b j ∥ 1 ≤ 2 n j D j for all j ≥ 0. \deg_{b_j}(v)\ge\frac{D_j}{4}\text{ for all }v\in L_j\text{ if }j\ge1,\qquad\lVert b_j\rVert_1\le2n_jD_j\text{ for all }j\ge0. deg b j ( v ) ≥ 4 D j for all v ∈ L j if j ≥ 1 , ∥ b j ∥ 1 ≤ 2 n j D j for all j ≥ 0. Laplace ℓ 1 \ell_1 ℓ 1 tail bounds give, simultaneously, ∥ y ( j ) − deg ( b j ) ∥ 1 ≤ R j \lVert y^{(j)}-\deg(b_j)\rVert_1\le R_j ∥ y ( j ) − deg ( b j ) ∥ 1 ≤ R j , except with probability β 0 \beta_0 β 0 . Clamping cannot increase this error. Together with the peeling bounds, this proves b j ∈ K j b_j\in\mathcal{K}_j b j ∈ K j ; the degree-discrepancy bound follows by the triangle inequality. Summing R j R_j R j gives (9) , using J = O ( log n ) J=O(\log n) J = O ( log n ) and log ( n / β ) = O ( ε σ ) \log(n/\beta)=O(\varepsilon\sigma) log ( n / β ) = O ( ε σ ) .
Each confidence set also supplies the starting point of the entropy search in its layer. We omit empty layers, and output zero for a layer when K j \mathcal{K}_j K j is empty or m j = 0 m_j=0 m j = 0 . Otherwise, we solve a separate LP for each edge coordinate, maximizing that coordinate over K j \mathcal{K}_j K j . Let h j 0 ∈ K j h_j^0\in\mathcal{K}_j h j 0 ∈ K j be the average of the resulting optimizers. Since the solution for coordinate e e e has e e e th coordinate at least h e h_e h e for every h ∈ K j h\in\mathcal{K}_j h ∈ K j , and every h ∈ K j h\in\mathcal{K}_j h ∈ K j has mass at most M j M_j M j , every h ∈ K j h\in\mathcal{K}_j h ∈ K j satisfies
h j , e 0 ≥ h e m j for every pair e , D K L ( h ∥ h j 0 ) ≤ M j ( log m j + 1 ) ≤ M j log ( 2 n 2 ) . h_{j,e}^0\ge\frac{h_e}{m_j}\text{ for every pair }e,\qquad D_{\mathrm{KL}}(h\Vert h_j^0)\le M_j(\log m_j+1)\le M_j\log(2n^2). h j , e 0 ≥ m j h e for every pair e , D KL ( h ∥ h j 0 ) ≤ M j ( log m j + 1 ) ≤ M j log ( 2 n 2 ) . We remove the coordinates with h j , e 0 = 0 h_{j,e}^0=0 h j , e 0 = 0 , which vanish on all of K j \mathcal{K}_j K j ; if none remain, we output zero for the layer.
It remains to fix the order in which the layers are released and the error each may incur. We process the remaining layers in decreasing order of j j j . Layer j j j uses a prior P j P_j P j formed from the public outputs h k h_k h k of the higher layers and a public error allowance A j A_j A j ,
P j : = ∑ k > j ( 3 / 4 ) k − j h k , A j : = C A ( σ ω j γ + R j ) , P_j:=\sum_{k>j}(3/4)^{k-j}h_k,\qquad A_j:=C_A\left(\frac{\sigma\omega_j}{\gamma}+R_j\right), P j := k > j ∑ ( 3/4 ) k − j h k , A j := C A ( γ σ ω j + R j ) , ω 0 : = n , ω j : = n j + ∑ k > j ( 2 / 3 ) k − j n k for j ≥ 1. (10) \omega_0:=n,\qquad\omega_j:=n_j+\sum_{k>j}(2/3)^{k-j}n_k\quad\text{for }j\ge1. \tag*{(10)} ω 0 := n , ω j := n j + k > j ∑ ( 2/3 ) k − j n k for j ≥ 1. (10)
We choose C A C_A C A after the preceding constants. The prior compensates for the vertices of V j V_j V j that lie in higher layers: such a vertex in L k L_k L k may have small degree in b j b_j b j , but it has degree at least D k / 4 D_k/4 D k /4 in h k h_k h k , which the prior supplies to the oracle. The effective vertex counts satisfy ∑ j ω j ≤ 4 n \sum_j \omega_j \le4n ∑ j ω j ≤ 4 n , and ∑ j P j ≤ 3 ∑ j h j \sum_j P_j \le3\sum_j h_j ∑ j P j ≤ 3 ∑ j h j coordinatewise. § 4.4 shows that A j A_j A j suffices for the oracle error. All parameters except the prior are fixed by preprocessing.
Releasing a degree layer
We now release a single block, dropping the layer index. The layer mechanism takes as input a public nonempty compact convex set K \mathcal{K} K of nonnegative graphs of mass at most M M M , a public initializer h 0 ∈ K h_0 \in\mathcal{K} h 0 ∈ K positive on the relative support of K \mathcal{K} K and satisfying
D K L ( h ∥ h 0 ) ≤ M log ( 2 n 2 ) for all h ∈ K , (11) D_{\mathrm{KL}}(h\Vert h_0) \le M\log(2n^2) \qquad\text{for all } h \in\mathcal{K}, \tag*{(11)} D KL ( h ∥ h 0 ) ≤ M log ( 2 n 2 ) for all h ∈ K , (11)
and public parameters P ≥ 0 P \ge0 P ≥ 0 and A , λ > 0 A,\lambda> 0 A , λ > 0 ; in the full mechanism, these are K j \mathcal{K}_j K j , M j M_j M j , h j 0 h_j^0 h j 0 , P j P_j P j , A j A_j A j , and λ j \lambda_j λ j . The accuracy proof assumes that the private input b b b belongs to K \mathcal{K} K ; privacy does not require this event.
The search is guided by the log-determinant oracle. For a signed edge vector E E E and a nonnegative edge vector T T T on the current vertex set, we define
X ( E , T ) : = arg max Z ≻ 0 , Z i i ≤ 1 { 1 4 tr ( A E Z ) − a ⟨ T , q ( Z ) ⟩ + λ log det Z } . (12) X(E,T) := \mathop{\arg\max}_{Z\succ0,\; Z_{ii}\le1} \left\{ \frac{1}{4}\operatorname{tr}(A_E Z) - a\langle T,q(Z)\rangle+ \lambda\log\det Z \right\}. \tag*{(12)} X ( E , T ) := arg max Z ≻ 0 , Z ii ≤ 1 { 4 1 tr ( A E Z ) − a ⟨ T , q ( Z )⟩ + λ log det Z } . (12)
For a candidate h h h , we put E = h − b E=h-b E = h − b and T = h + b + P T=h+b+P T = h + b + P , and set
X θ : = X ( θ E , T ) , V ( h ) : = max θ ∈ { − 1 , 1 } SDP ( θ E − a T ) . (13) X_\theta:= X(\theta E,T), \qquad V(h) := \max_{\theta\in\{-1,1\}}\operatorname{SDP}(\theta E-aT). \tag*{(13)} X θ := X ( θ E , T ) , V ( h ) := θ ∈ { − 1 , 1 } max SDP ( θ E − a T ) . (13)
Since SDP dominates every cut value, every cut satisfies ∣ h ( S ) − b ( S ) ∣ ≤ a T ( S ) + V ( h ) |h(S)-b(S)| \le aT(S)+V(h) ∣ h ( S ) − b ( S ) ∣ ≤ a T ( S ) + V ( h ) , so a candidate with small V ( h ) V(h) V ( h ) is accurate. The oracle relates V ( h ) V(h) V ( h ) to the covariance score
Q θ ( h ) : = θ ⟨ E , q ( X θ ) ⟩ − a 4 ⟨ T , q ( X θ ) 2 ⟩ . Q_\theta(h) := \theta\langle E,q(X_\theta)\rangle-\frac{a}{4}\langle T,q(X_\theta)^2\rangle. Q θ ( h ) := θ ⟨ E , q ( X θ )⟩ − 4 a ⟨ T , q ( X θ ) 2 ⟩ .
Lemma 4.2 will give the certificate
SDP ( θ E − a T ) ≤ 4 Q θ ( h ) + A for all h ∈ K and θ ∈ { − 1 , 1 } . (14) \operatorname{SDP}(\theta E-aT) \le4Q_\theta(h)+A \qquad\text{for all } h\in\mathcal{K}\text{ and }\theta\in\{-1,1\}. \tag*{(14)} SDP ( θ E − a T ) ≤ 4 Q θ ( h ) + A for all h ∈ K and θ ∈ { − 1 , 1 } . (14)
A large cut discrepancy therefore yields a covariance with a large score.
To act on such a covariance, we turn a Gaussian sample into a bounded multiplicative update and validate its exact entropy decrease. We set τ = a / 2880 \tau=a/2880 τ = a /2880 and, for z ∼ N ( 0 , X θ ) z\sim N(0,X_\theta) z ∼ N ( 0 , X θ ) , put
g : = q ( z z ⊤ ) , r e : = 1 + 2 τ g e 1 + τ g e , Δ θ : = ⟨ h , 1 − r − θ ⟩ − θ ⟨ b , log r ⟩ . (15) g:=q(zz^\top), \qquad r_e:=\frac{1+2\tau g_e}{1+\tau g_e}, \qquad\Delta_\theta:=\langle h,1-r^{-\theta}\rangle-\theta\langle b,\log r\rangle. \tag*{(15)} g := q ( z z ⊤ ) , r e := 1 + τ g e 1 + 2 τ g e , Δ θ := ⟨ h , 1 − r − θ ⟩ − θ ⟨ b , log r ⟩ . (15)
The vector g g g has mean q ( X θ ) q(X_\theta) q ( X θ ) , and 1 ≤ r e ≤ 2 1\le r_e\le2 1 ≤ r e ≤ 2 . When b ∈ K b\in\mathcal{K} b ∈ K , the decrease in D K L ( b ∥ h ) D_{\mathrm{KL}}(b\Vert h) D KL ( b ∥ h ) before projecting u = h ∘ r − θ u=h\circ r^{-\theta} u = h ∘ r − θ onto K \mathcal{K} K is exactly Δ θ \Delta_\theta Δ θ , and Lemma 4.4 shows that Δ θ ≥ τ Q θ ( h ) \Delta_\theta\ge\tau Q_\theta(h) Δ θ ≥ τ Q θ ( h ) with constant probability. The oracle score Q θ ( h ) Q_\theta(h) Q θ ( h ) thus links the cut violation V ( h ) V(h) V ( h ) to potential progress, while a noisy check of Δ θ \Delta_\theta Δ θ determines whether the proposal is accepted. For fixed h , r , θ h,r,\theta h , r , θ , the input b b b enters Δ θ \Delta_\theta Δ θ only through − θ ⟨ b , log r ⟩ -\theta\langle b,\log r\rangle − θ ⟨ b , log r ⟩ . Since 0 ≤ log r e ≤ τ g e 0\le\log r_e\le\tau g_e 0 ≤ log r e ≤ τ g e , the validation noise below has scale proportional to τ \tau τ .
The number of trials and the acceptance threshold are calibrated so that, with high probability, every accepted update makes definite progress. For a failure allocation ζ ∈ ( 0 , 1 / 4 ) \zeta\in(0,1/4) ζ ∈ ( 0 , 1/4 ) , we take a sufficiently large absolute C N C_N C N and set
N : = ⌈ C N [ M log ( 2 n 2 ) τ A + log 6 ζ ] ⌉ . (16) N:=\left\lceil C_N\left[\frac{M\log(2n^2)}{\tau A}+\log\frac{6}{\zeta}\right]\right\rceil. \tag*{(16)} N := ⌈ C N [ τ A M log ( 2 n 2 ) + log ζ 6 ] ⌉ . (16)
The first term is the initial potential bound (11) divided by the minimum entropy decrease τ A \tau A τ A of an accepted update. We fix an absolute c v ≥ 2 c_{\mathrm{v}} \ge2 c v ≥ 2 and define
ℓ N : = log 6 ( N + 1 ) ζ , Γ : = τ ( A + c v λ ℓ N ) . (17) \ell_N := \log\frac{6(N+1)}{\zeta}, \qquad\Gamma:= \tau(A+c_{\mathrm{v}}\lambda\ell_N). \tag*{(17)} ℓ N := log ζ 6 ( N + 1 ) , Γ := τ ( A + c v λ ℓ N ) . (17)
When every validation noise has magnitude at most c v τ λ ℓ N c_{\mathrm{v}}\tau\lambda\ell_N c v τ λ ℓ N , which a union bound over the trials provides with high probability, the acceptance threshold 2 Γ 2\Gamma 2Γ ensures that every accepted update has Δ t ≥ Γ ≥ τ A \Delta_t \ge\Gamma\ge\tau A Δ t ≥ Γ ≥ τ A .
Algorithm 1 ReleaseLayer( b ) (b) ( b )
Require: Private block b b b ; public layer data K \mathcal{K} K , h 0 h_0 h 0 , P P P , M M M , A A A , λ \lambda λ ; parameters a a a , τ \tau τ , ε 0 \varepsilon_0 ε 0 , ζ \zeta ζ
Ensure: A graph in K \mathcal{K} K
Compute N N N , ℓ N \ell_N ℓ N , and Γ \Gamma Γ by (16) and (17)
Store the initial candidate h 0 h_0 h 0
for t = 0 , … , N − 1 t=0,\ldots,N-1 t = 0 , … , N − 1 do
Draw θ t \theta_t θ t uniformly from { − 1 , 1 } \{-1,1\} { − 1 , 1 } ; compute X θ t X_{\theta_t} X θ t at h t h_t h t by (13)
Draw z t ∼ N ( 0 , X θ t ) z_t \sim N(0,X_{\theta_t}) z t ∼ N ( 0 , X θ t ) ; form r t r_t r t and Δ t \Delta_t Δ t by (15) ▹ \triangleright ▹ proposal
Draw an independent ξ t ∼ Lap ( c v τ λ ) \xi_t \sim\operatorname{Lap}(c_{\mathrm{v}}\tau\lambda) ξ t ∼ Lap ( c v τ λ )
if Δ t + ξ t ≥ 2 Γ \Delta_t+\xi_t \ge2\Gamma Δ t + ξ t ≥ 2Γ then ▹ \triangleright ▹ validation
h t + 1 ← arg min h ∈ K D K L ( h ∥ h t ⊙ r t − θ t ) h_{t+1} \leftarrow\underset{h\in\mathcal{K}}{\arg\min}\ D_{\mathrm{KL}}(h\mathbin\Vert h_t\odot r_t^{-\theta_t}) h t + 1 ← h ∈ K arg min D KL ( h ∥ h t ⊙ r t − θ t ) ▹ \triangleright ▹ entropy projection
else
h t + 1 ← h t h_{t+1} \leftarrow h_t h t + 1 ← h t ▹ \triangleright ▹ rejection
end if
Store h t + 1 h_{t+1} h t + 1
end for
Draw I ∈ { 0 , … , N } I\in\{0,\ldots,N\} I ∈ { 0 , … , N } with Pr [ I = i ] ∝ exp ( − ε 0 V ( h i ) / ( 2 ( 1 + a ) ) ) \Pr[I=i]\propto\exp(-\varepsilon_0V(h_i)/(2(1+a))) Pr [ I = i ] ∝ exp ( − ε 0 V ( h i ) / ( 2 ( 1 + a ))) ▹ \triangleright ▹ exponential mechanism
return h I h_I h I
Algorithm 1 assembles these steps, writing r t r_t r t and Δ t \Delta_t Δ t for the quantities (15) of trial t t t . It projects each accepted update back onto K \mathcal{K} K in relative entropy, which cannot increase the divergence from b ∈ K b\in\mathcal{K} b ∈ K . The final selection score V V V has sensitivity 1 + a 1+a 1 + a , since SDP is 1-Lipschitz in ℓ 1 \ell_1 ℓ 1 and θ E − a T \theta E-aT θ E − a T changes by at most ( 1 + a ) ∥ b − b ′ ∥ 1 (1+a)\lVert b-b'\rVert_1 ( 1 + a ) ∥ b − b ′ ∥ 1 .
The full mechanism releases Y Y Y by (5) , constructs the layers and the confidence sets (7) , and calls Algorithm 1 in decreasing layer order, using zero outputs in the cases specified above. It returns the graph H H H with edge-weight vector w H = Y + ∑ j h j w_H=Y+\sum_j h_j w H = Y + ∑ j h j .
Analysis
We analyze the log-determinant oracle in § 4.1 , establish accuracy for a single layer in § 4.2 , and prove privacy of the full mechanism in § 4.3 . We then combine the layer guarantees in § 4.4 to prove Theorem 1.1 .
The log-determinant oracle
The log-determinant term makes the optimizer stable (Lemma 4.3) at the price of the harmonic error term in Lemma 4.2 . Throughout this subsection, we fix the current vertex set V V V and parameters a , λ > 0 a,\lambda>0 a , λ > 0 , and we analyze the optimizer X ( E , T ) X(E,T) X ( E , T ) defined in (12) . The diagonal constraint ensures that q ( X ) ∈ [ 0 , 1 ] ( V ) q(X)\in[0,1]^{(V)} q ( X ) ∈ [ 0 , 1 ] ( V ) . The adjacency objective differs from the cut objective by a degree term, which appears explicitly in the accuracy bound below. We begin with the optimality conditions; the spectral bounds in the next lemma are needed for the implementation in Appendix § 6 .
Lemma 4.1 (Optimality and conditioning). The maximizer X = X ( E , T ) X=X(E,T) X = X ( E , T ) exists and is unique. There is a vector ν ≥ 0 \nu\ge0 ν ≥ 0 such that
X − 1 = diag ( ν ) + a L T + A E 4 λ , ν i ( X i i − 1 ) = 0 , ( X − 1 ) i i ≥ 1. X^{-1}=\operatorname{diag}(\nu)+\frac{aL_T+A_E}{4\lambda},\qquad\nu_i(X_{ii}-1)=0,\qquad(X^{-1})_{ii}\ge1. X − 1 = diag ( ν ) + 4 λ a L T + A E , ν i ( X ii − 1 ) = 0 , ( X − 1 ) ii ≥ 1. Moreover,
( ∣ V ∣ + ∥ E ∥ 1 + a ∥ T ∥ 1 2 λ ) − 1 I ⪯ X ⪯ ∣ V ∣ I . \left(|V|+\frac{\lVert E\rVert_1+a\lVert T\rVert_1}{2\lambda}\right)^{-1}I\preceq X\preceq|V|I. ( ∣ V ∣ + 2 λ ∥ E ∥ 1 + a ∥ T ∥ 1 ) − 1 I ⪯ X ⪯ ∣ V ∣ I .
Proof. The closure of the domain is compact, and log det X \log\det X log det X tends to − ∞ -\infty − ∞ at its singular boundary, so a positive definite maximizer exists. Strict concavity gives uniqueness, and the strictly feasible point I / 2 I/2 I /2 gives the KKT conditions. Cauchy–Schwarz yields ( X − 1 ) i i X i i ≥ 1 (X^{-1})_{ii}X_{ii}\ge1 ( X − 1 ) ii X ii ≥ 1 , hence ( X − 1 ) i i ≥ 1 (X^{-1})_{ii}\ge1 ( X − 1 ) ii ≥ 1 . Multiplying the KKT equation by X X X , taking traces, and using complementary slackness, we obtain
tr ( X − 1 ) = ∣ V ∣ − tr ( A E X ) 4 λ + a λ ∑ e T e ( 1 / 2 − q e ( X ) ) ≤ ∣ V ∣ + ∥ E ∥ 1 + a ∥ T ∥ 1 2 λ . \operatorname{tr}(X^{-1})=|V|-\frac{\operatorname{tr}(A_EX)}{4\lambda}+\frac{a}{\lambda}\sum_e T_e(1/2-q_e(X))\le|V|+\frac{\lVert E\rVert_1+a\lVert T\rVert_1}{2\lambda}. tr ( X − 1 ) = ∣ V ∣ − 4 λ tr ( A E X ) + λ a e ∑ T e ( 1/2 − q e ( X )) ≤ ∣ V ∣ + 2 λ ∥ E ∥ 1 + a ∥ T ∥ 1 .
This bounds the smallest eigenvalue of X X X , and tr X ≤ ∣ V ∣ \operatorname{tr}X\le|V| tr X ≤ ∣ V ∣ bounds the largest.
The quadratic term a ⟨ T , q ( X ) 2 ⟩ a\langle T,q(X)^2\rangle a ⟨ T , q ( X ) 2 ⟩ in the next lemma accounts for the second-order loss in the analysis of the sampled update in Lemma 4.4 . Including this term in the oracle bound yields the certificate (14) for Q θ Q_\theta Q θ .
Lemma 4.2 (Oracle accuracy). Let λ > 0 \lambda>0 λ > 0 and 0 < a ≤ 1 0<a\le1 0 < a ≤ 1 . For a signed edge vector E E E and an edge vector T T T satisfying 0 ≤ T e ≤ λ 0\le T_e\le\lambda 0 ≤ T e ≤ λ , let X = X ( E , T ) X=X(E,T) X = X ( E , T ) . Then
SDP ( E − a T ) + a ⟨ T , q ( X ) 2 ⟩ ≤ 4 ⟨ E , q ( X ) ⟩ + 15 λ 2 ∑ v ∈ V 1 λ + a deg T ( v ) + 3 4 ∥ deg ( E ) ∥ 1 . \operatorname{SDP}(E-aT)+a\langle T,q(X)^2\rangle\le4\langle E,q(X)\rangle+15\lambda^2\sum_{v\in V}\frac{1}{\lambda+a\deg_T(v)}+\frac{3}{4}\lVert\deg(E)\rVert_1. SDP ( E − a T ) + a ⟨ T , q ( X ) 2 ⟩ ≤ 4 ⟨ E , q ( X )⟩ + 15 λ 2 v ∈ V ∑ λ + a deg T ( v ) 1 + 4 3 ∥ deg ( E ) ∥ 1 .
To prove the lemma, we normalize X − 1 X^{-1} X − 1 by its diagonal K K K and bound a single nonnegative trace in two ways: from above by the adjacency signal, by completing the square, and from below by the degree-corrected SDP value, through the KKT conditions. The remaining terms are O ( tr ( K − 1 ) ) O(\operatorname{tr}(K^{-1})) O ( tr ( K − 1 )) , which yields the harmonic sum.
Proof. Set d i = deg T ( i ) d_i=\deg_T(i) d i = deg T ( i ) and K = diag ( ( X − 1 ) i i ) K=\operatorname{diag}((X^{-1})_{ii}) K = diag (( X − 1 ) ii ) . Lemma 4.1 gives K i i = ν i + a d i / ( 4 λ ) ≥ max { 1 , a d i / ( 4 λ ) } K_{ii}=\nu_i+ad_i/(4\lambda)\ge\max\{1,ad_i/(4\lambda)\} K ii = ν i + a d i / ( 4 λ ) ≥ max { 1 , a d i / ( 4 λ )} . We normalize by this diagonal:
Q = K − 1 / 2 X − 1 K − 1 / 2 = I + B ≻ 0 , R = a 4 λ K − 1 / 2 A T K − 1 / 2 , t = ∥ R ∥ F 2 . Q=K^{-1/2}X^{-1}K^{-1/2}=I+B\succ0,\qquad R=\frac{a}{4\lambda}K^{-1/2}A_TK^{-1/2},\qquad t=\lVert R\rVert_F^2. Q = K − 1/2 X − 1 K − 1/2 = I + B ≻ 0 , R = 4 λ a K − 1/2 A T K − 1/2 , t = ∥ R ∥ F 2 .
Both B B B and R R R have zero diagonal, and ∥ R ∥ o p ≤ 1 \lVert R\rVert_{\mathrm{op}}\le1 ∥ R ∥ op ≤ 1 because ∣ x ⊤ A T x ∣ ≤ ∑ i d i x i 2 \lvert x^\top A_Tx\rvert\le\sum_i d_ix_i^2 ∣ x ⊤ A T x ∣ ≤ ∑ i d i x i 2 and K ⪰ ( a / ( 4 λ ) ) diag ( d ) K\succeq(a/(4\lambda))\operatorname{diag}(d) K ⪰ ( a / ( 4 λ )) diag ( d ) . The edge cap T e ≤ λ T_e\le\lambda T e ≤ λ and the inequality 2 / ( K i i K j j ) ≤ K i i − 2 + K j j − 2 2/(K_{ii}K_{jj})\le K_{ii}^{-2}+K_{jj}^{-2} 2/ ( K ii K j j ) ≤ K ii − 2 + K j j − 2 give
t ≤ a 2 16 λ 2 ∑ i d i K i i 2 ≤ a 4 λ tr ( K − 1 ) ≤ 1 4 tr ( K − 1 ) . (18) t\le\frac{a^2}{16\lambda^2}\sum_i\frac{d_i}{K_{ii}^2}\le\frac{a}{4\lambda}\operatorname{tr}(K^{-1})\le\frac{1}{4}\operatorname{tr}(K^{-1}). \tag*{(18)} t ≤ 16 λ 2 a 2 i ∑ K ii 2 d i ≤ 4 λ a tr ( K − 1 ) ≤ 4 1 tr ( K − 1 ) . (18)
In these coordinates, the normalized adjacency signal F F F and the matrix G G G are
F : = − tr ( A E X ) 4 λ = tr ( ( B 2 + R B ) Q − 1 ) , G : = B 2 Q − 1 ⪰ 0 , F:=-\frac{\operatorname{tr}(A_EX)}{4\lambda}=\operatorname{tr}\left((B^2+RB)Q^{-1}\right),\qquad G:=B^2Q^{-1}\succeq0, F := − 4 λ tr ( A E X ) = tr ( ( B 2 + R B ) Q − 1 ) , G := B 2 Q − 1 ⪰ 0 ,
where the equality uses tr ( B + R ) = 0 \operatorname{tr}(B+R)=0 tr ( B + R ) = 0 . We next bound tr ( ( I − R ) G ) \operatorname{tr}((I-R)G) tr (( I − R ) G ) by 2 ( F + t ) 2(F+t) 2 ( F + t ) through the following square completion:
4 ( F + t ) − 2 tr ( ( I − R ) G ) = ∥ Q − 1 / 2 [ B + ( Q + I ) R ] ∥ F 2 + tr ( G ( I − R 2 ) ) ≥ 0. 4(F+t)-2\operatorname{tr}((I-R)G)=\left\|Q^{-1/2}[B+(Q+I)R]\right\|_{F}^{2}+\operatorname{tr}(G(I-R^{2}))\ge0. 4 ( F + t ) − 2 tr (( I − R ) G ) = Q − 1/2 [ B + ( Q + I ) R ] F 2 + tr ( G ( I − R 2 )) ≥ 0.
To verify the identity, use B = Q − I B=Q-I B = Q − I , so that B B B commutes with Q Q Q , and cyclicity of the trace. To relate the SDP value to G G G , define M = K − 1 / 2 G K − 1 / 2 ⪰ 0 M=K^{-1/2}GK^{-1/2}\succeq0 M = K − 1/2 G K − 1/2 ⪰ 0 . The identity G = Q − 1 − 2 I + Q G=Q^{-1}-2I+Q G = Q − 1 − 2 I + Q gives
X ⪯ M + 2 K − 1 , M i i = X i i − K i i − 1 . X\preceq M+2K^{-1},\qquad M_{ii}=X_{ii}-K_{ii}^{-1}. X ⪯ M + 2 K − 1 , M ii = X ii − K ii − 1 .
Let V ^ = SDP ( E − a T ) − 1 4 ∑ i deg E ( i ) \widehat{V}=\operatorname{SDP}(E-aT)-\frac{1}{4}\sum_i\deg_E(i) V = SDP ( E − a T ) − 4 1 ∑ i deg E ( i ) . Testing the KKT equation against a unit-diagonal matrix gives V ^ ≤ λ ∑ i ν i \widehat{V}\le\lambda\sum_i\nu_i V ≤ λ ∑ i ν i , and complementary slackness together with ( 1 − K i i − 1 ) 2 ≥ 0 (1-K_{ii}^{-1})^2\ge0 ( 1 − K ii − 1 ) 2 ≥ 0 implies
ν i ≤ 2 ν i M i i + ν i / K i i 2 , V ^ ≤ 2 λ tr ( diag ( ν ) M ) + λ ∑ i ν i K i i 2 . \nu_i\le2\nu_iM_{ii}+\nu_i/K_{ii}^{2},\qquad\widehat{V}\le2\lambda\operatorname{tr}(\operatorname{diag}(\nu)M)+\lambda\sum_i\frac{\nu_i}{K_{ii}^{2}}. ν i ≤ 2 ν i M ii + ν i / K ii 2 , V ≤ 2 λ tr ( diag ( ν ) M ) + λ i ∑ K ii 2 ν i .
For the quadratic term, note that for 0 ≤ u ≤ 1 0\le u\le1 0 ≤ u ≤ 1 and v , w ≥ 0 v,w\ge0 v , w ≥ 0 , u ≤ v + w u\le v+w u ≤ v + w implies u 2 ≤ 2 v + w 2 u^2\le2v+w^2 u 2 ≤ 2 v + w 2 (consider w ≥ u w\ge u w ≥ u and w < u w<u w < u ). Applying this with u = q E ( X ) u=q_E(X) u = q E ( X ) , v = q E ( M ) v=q_E(M) v = q E ( M ) , and w = 2 q E ( K − 1 ) w=2q_E(K^{-1}) w = 2 q E ( K − 1 ) , we obtain
a ⟨ T , q ( X ) 2 ⟩ ≤ 2 a ⟨ T , q ( M ) ⟩ + a 2 ∑ i d i K i i 2 . a\langle T,q(X)^2\rangle\le2a\langle T,q(M)\rangle+\frac{a}{2}\sum_i\frac{d_i}{K_{ii}^{2}}. a ⟨ T , q ( X ) 2 ⟩ ≤ 2 a ⟨ T , q ( M )⟩ + 2 a i ∑ K ii 2 d i .
The two residual sums combine to at most 2 λ tr ( K − 1 ) 2\lambda\operatorname{tr}(K^{-1}) 2 λ tr ( K − 1 ) , since ν i + a d i / ( 4 λ ) = K i i \nu_i+ad_i/(4\lambda)=K_{ii} ν i + a d i / ( 4 λ ) = K ii . Moreover,
λ tr ( diag ( ν ) M ) + a ⟨ T , q ( M ) ⟩ = λ tr ( ( I − R ) G ) . \lambda\operatorname{tr}(\operatorname{diag}(\nu)M)+a\langle T,q(M)\rangle=\lambda\operatorname{tr}((I-R)G). λ tr ( diag ( ν ) M ) + a ⟨ T , q ( M )⟩ = λ tr (( I − R ) G ) .
Consequently,
V ^ + a ⟨ T , q ( X ) 2 ⟩ ≤ 2 λ tr ( ( I − R ) G ) + 2 λ tr ( K − 1 ) \widehat{V}+a\langle T,q(X)^2\rangle\le2\lambda\operatorname{tr}((I-R)G)+2\lambda\operatorname{tr}(K^{-1}) V + a ⟨ T , q ( X ) 2 ⟩ ≤ 2 λ tr (( I − R ) G ) + 2 λ tr ( K − 1 )
≤ 4 λ F + 3 λ tr ( K − 1 ) \le4\lambda F+3\lambda\operatorname{tr}(K^{-1}) ≤ 4 λ F + 3 λ tr ( K − 1 )
≤ 4 λ F + 15 λ 2 ∑ i 1 λ + a d i . \le4\lambda F+15\lambda^2\sum_i\frac{1}{\lambda+ad_i}. ≤ 4 λ F + 15 λ 2 i ∑ λ + a d i 1 .
where the second inequality uses the completed square and (18) and the third uses 5 K i i ≥ 1 + a d i / λ 5K_{ii}\ge1+ad_i/\lambda 5 K ii ≥ 1 + a d i / λ . Finally, λ F = ⟨ E , q ( X ) ⟩ − 1 4 ∑ i deg E ( i ) X i i \lambda F=\langle E,q(X)\rangle-\frac{1}{4}\sum_i\deg_E(i)X_{ii} λ F = ⟨ E , q ( X )⟩ − 4 1 ∑ i deg E ( i ) X ii , so converting back to the cut objective adds
∑ i ( 1 / 4 − X i i ) deg E ( i ) ≤ 3 4 ∥ deg ( E ) ∥ 1 , \sum_i(1/4-X_{ii})\deg_E(i)\le\frac{3}{4}\|\deg(E)\|_1, i ∑ ( 1/4 − X ii ) deg E ( i ) ≤ 4 3 ∥ deg ( E ) ∥ 1 ,
which proves the lemma.
We turn to stability: Gaussian sampling from the optimizer changes little under small changes of the input.
Lemma 4.3 (Gaussian Rényi stability). Let X i = X ( E i , T i ) X_i=X(E_i,T_i) X i = X ( E i , T i ) , i ∈ { 0 , 1 } i\in\{0,1\} i ∈ { 0 , 1 } , for the same a , λ > 0 a,\lambda>0 a , λ > 0 , and put
χ = ∥ E 1 − E 0 ∥ 1 / 2 + a ∥ T 1 − T 0 ∥ 1 λ . \chi=\frac{\|E_1-E_0\|_{1/2}+a\|T_1-T_0\|_1}{\lambda}. χ = λ ∥ E 1 − E 0 ∥ 1/2 + a ∥ T 1 − T 0 ∥ 1 . There are absolute constants c , C > 0 c,C>0 c , C > 0 such that, for every α > 1 \alpha>1 α > 1 with α χ ≤ c \alpha\chi\le c α χ ≤ c ,
D α ( N ( 0 , X 0 ) ∥ N ( 0 , X 1 ) ) ≤ C α χ 2 , (19) D_\alpha(N(0,X_0)\|N(0,X_1))\le C\alpha\chi^2, \tag*{(19)} D α ( N ( 0 , X 0 ) ∥ N ( 0 , X 1 )) ≤ C α χ 2 , (19) and the same bound holds with the inputs exchanged.
Proof. Write Δ X = X 1 − X 0 \Delta X = X_1 - X_0 Δ X = X 1 − X 0 , Δ E = E 1 − E 0 \Delta E = E_1 - E_0 Δ E = E 1 − E 0 , Δ T = T 1 − T 0 \Delta T = T_1 - T_0 Δ T = T 1 − T 0 , and Z = X 0 − 1 / 2 Δ X X 1 − 1 / 2 Z = X_0^{-1/2}\Delta X X_1^{-1/2} Z = X 0 − 1/2 Δ X X 1 − 1/2 . Adding the two first-order optimality inequalities gives
λ ∥ Z ∥ F 2 = λ tr ( ( X 0 − 1 − X 1 − 1 ) Δ X ) ≤ ∣ 1 4 tr ( A Δ E Δ X ) + a ⟨ Δ T , q ( Δ X ) ⟩ ∣ . \lambda\|Z\|_{F}^{2} = \lambda\operatorname{tr}\left((X_0^{-1}-X_1^{-1})\Delta X\right) \le\left|\frac{1}{4}\operatorname{tr}(A_{\Delta E}\Delta X) + a\langle\Delta T,q(\Delta X)\rangle\right|. λ ∥ Z ∥ F 2 = λ tr ( ( X 0 − 1 − X 1 − 1 ) Δ X ) ≤ 4 1 tr ( A Δ E Δ X ) + a ⟨ Δ T , q ( Δ X )⟩ .
Factoring Δ X \Delta X Δ X through Z Z Z gives ∣ Δ X u v ∣ ≤ ∥ Z ∥ F |\Delta X_{uv}| \le\|Z\|_{F} ∣Δ X uv ∣ ≤ ∥ Z ∥ F and ∣ q u v ( Δ X ) ∣ ≤ ∥ Z ∥ F q u v ( X 0 ) q u v ( X 1 ) ≤ ∥ Z ∥ F |q_{uv}(\Delta X)| \le\|Z\|_{F}\sqrt{q_{uv}(X_0)q_{uv}(X_1)} \le\|Z\|_{F} ∣ q uv ( Δ X ) ∣ ≤ ∥ Z ∥ F q uv ( X 0 ) q uv ( X 1 ) ≤ ∥ Z ∥ F . Hence ∥ Z ∥ F ≤ χ \|Z\|_{F} \le\chi ∥ Z ∥ F ≤ χ .
It remains to convert this bound into a Rényi bound. The eigenvalues t i > 0 t_i > 0 t i > 0 of X 0 − 1 / 2 X 1 X 0 − 1 / 2 X_0^{-1/2}X_1X_0^{-1/2} X 0 − 1/2 X 1 X 0 − 1/2 satisfy ∑ i ( t i − 1 ) 2 / t i = ∥ Z ∥ F 2 ≤ χ 2 \sum_i(t_i-1)^2/t_i = \|Z\|_{F}^{2} \le\chi^2 ∑ i ( t i − 1 ) 2 / t i = ∥ Z ∥ F 2 ≤ χ 2 . For χ ≤ 1 / 2 \chi\le1/2 χ ≤ 1/2 , this implies t i ∈ [ 1 / 2 , 2 ] t_i \in[1/2,2] t i ∈ [ 1/2 , 2 ] and ∑ i ( t i − 1 ) 2 ≤ 2 χ 2 \sum_i(t_i-1)^2 \le2\chi^2 ∑ i ( t i − 1 ) 2 ≤ 2 χ 2 . Taking c c c sufficiently small ensures ∣ α ( t i − 1 ) ∣ ≤ 1 / 4 |\alpha(t_i-1)| \le1/4 ∣ α ( t i − 1 ) ∣ ≤ 1/4 , so the Gaussian density integral is finite and
D α ( N ( 0 , X 0 ) ∥ N ( 0 , X 1 ) ) = 1 2 ( α − 1 ) ∑ i f α ( t i − 1 ) , f α ( u ) = α log ( 1 + u ) − log ( 1 + α u ) . D_\alpha\left(N(0,X_0)\|N(0,X_1)\right) = \frac{1}{2(\alpha-1)}\sum_i f_\alpha(t_i-1), \qquad f_\alpha(u) = \alpha\log(1+u)-\log(1+\alpha u). D α ( N ( 0 , X 0 ) ∥ N ( 0 , X 1 ) ) = 2 ( α − 1 ) 1 i ∑ f α ( t i − 1 ) , f α ( u ) = α log ( 1 + u ) − log ( 1 + α u ) .
Since f α ( 0 ) = 0 f_\alpha(0)=0 f α ( 0 ) = 0 and f α ′ ( u ) = α ( α − 1 ) u / ( ( 1 + u ) ( 1 + α u ) ) f_\alpha'(u)=\alpha(\alpha-1)u/((1+u)(1+\alpha u)) f α ′ ( u ) = α ( α − 1 ) u / (( 1 + u ) ( 1 + α u )) , integration gives 0 ≤ f α ( u ) ≤ C α ( α − 1 ) u 2 0 \le f_\alpha(u) \le C\alpha(\alpha-1)u^2 0 ≤ f α ( u ) ≤ C α ( α − 1 ) u 2 on ∣ α u ∣ ≤ 1 / 4 |\alpha u| \le1/4 ∣ α u ∣ ≤ 1/4 . Substitution proves (19) , and exchanging the inputs gives the reverse direction. □ \square □
In a layer, the sign θ \theta θ and the public quantities h h h and P P P are fixed, and the private input enters only through E = θ ( h − b ) E=\theta(h-b) E = θ ( h − b ) and T = h + b + P T=h+b+P T = h + b + P . The perturbation parameter of Lemma 4.3 is therefore χ = ( 1 / 2 + a ) ∥ b − b ′ ∥ 1 / λ \chi=(1/2+a)\|b-b'\|_1/\lambda χ = ( 1/2 + a ) ∥ b − b ′ ∥ 1 / λ .
Accuracy of a layer
We analyze a single layer in the notation of § 3.2 . The next lemma shows that the sampled score of a Gaussian proposal is at least τ \tau τ times its covariance score with constant probability, and that it equals the exact entropy decrease before projection.
Lemma 4.4 (Sampled update). Fix a candidate h h h positive on the relative support of K \mathcal{K} K and a sign θ \theta θ . The sampled score in (15) satisfies Pr [ Δ θ ≥ τ Q θ ( h ) ] ≥ 1 / 120 \Pr[\Delta_\theta\ge\tau Q_\theta(h)] \ge1/120 Pr [ Δ θ ≥ τ Q θ ( h )] ≥ 1/120 . For arbitrary edge factors r e ∈ [ 1 , 2 ] r_e \in[1,2] r e ∈ [ 1 , 2 ] , define Δ θ \Delta_\theta Δ θ by the same formula and let h + = arg min f ∈ K D K L ( f ∥ h ⊙ r − θ ) h^+ = \operatorname*{arg\,min}_{f\in\mathcal{K}}D_{\mathrm{KL}}(f\|h\odot r^{-\theta}) h + = arg min f ∈ K D KL ( f ∥ h ⊙ r − θ ) . Then every f ∈ K f\in\mathcal{K} f ∈ K satisfies
D K L ( f ∥ h + ) − D K L ( f ∥ h ) ≤ − Δ θ + ( log 2 ) ∥ f − b ∥ 1 . (20) D_{\mathrm{KL}}(f\|h^+) - D_{\mathrm{KL}}(f\|h) \le-\Delta_\theta+ (\log2)\|f-b\|_1. \tag*{(20)} D KL ( f ∥ h + ) − D KL ( f ∥ h ) ≤ − Δ θ + ( log 2 ) ∥ f − b ∥ 1 . (20) In particular, if b ∈ K b\in\mathcal{K} b ∈ K , the entropy D K L ( b ∥ ⋅ ) D_{\mathrm{KL}}(b\|\cdot) D KL ( b ∥ ⋅ ) decreases by at least Δ θ \Delta_\theta Δ θ .
Proof. For x ≥ 0 x\ge0 x ≥ 0 and r = ( 1 + 2 x ) / ( 1 + x ) r=(1+2x)/(1+x) r = ( 1 + 2 x ) / ( 1 + x ) , we have
x − 3 2 x 2 ≤ log r = ∫ x 2 x d t 1 + t ≤ x , 1 − r − 1 ≥ x − 2 x 2 , r − 1 ≤ x . x-\frac{3}{2}x^2 \le\log r = \int_x^{2x}\frac{dt}{1+t} \le x,\qquad1-r^{-1}\ge x-2x^2,\qquad r-1\le x. x − 2 3 x 2 ≤ log r = ∫ x 2 x 1 + t d t ≤ x , 1 − r − 1 ≥ x − 2 x 2 , r − 1 ≤ x .
Applying these inequalities with x e = τ g e x_e=\tau g_e x e = τ g e gives
Δ + ≥ τ ⟨ h − b , g ⟩ − 2 τ 2 ⟨ h , g 2 ⟩ , Δ − ≥ τ ⟨ b − h , g ⟩ − 3 2 τ 2 ⟨ b , g 2 ⟩ . \Delta_+ \ge\tau\langle h-b,g\rangle- 2\tau^2\langle h,g^2\rangle,\qquad\Delta_- \ge\tau\langle b-h,g\rangle- \frac{3}{2}\tau^2\langle b,g^2\rangle. Δ + ≥ τ ⟨ h − b , g ⟩ − 2 τ 2 ⟨ h , g 2 ⟩ , Δ − ≥ τ ⟨ b − h , g ⟩ − 2 3 τ 2 ⟨ b , g 2 ⟩ .
Put μ = q ( X θ ) \mu=q(X_\theta) μ = q ( X θ ) , F = θ ⟨ h − b , g ⟩ F=\theta\langle h-b,g\rangle F = θ ⟨ h − b , g ⟩ , Z = ⟨ T , g 2 ⟩ Z=\langle T,g^2\rangle Z = ⟨ T , g 2 ⟩ , and B = ⟨ T , μ 2 ⟩ B=\langle T,\mu^2\rangle B = ⟨ T , μ 2 ⟩ . Since h , b ≤ T h,b\le T h , b ≤ T ,
Δ θ ≥ τ F − 2 τ 2 Z , E F = Q θ + a 4 B , E Z = 3 B . \Delta_\theta\ge\tau F - 2\tau^2 Z,\qquad\mathbb{E}F = Q_\theta+ \frac{a}{4}B,\qquad\mathbb{E}Z = 3B. Δ θ ≥ τ F − 2 τ 2 Z , E F = Q θ + 4 a B , E Z = 3 B .
The centered quadratic form F 0 = F − E F F_0=F-\mathbb{E}F F 0 = F − E F has the law ∑ i c i ( G i 2 − 1 ) \sum_i c_i(G_i^2-1) ∑ i c i ( G i 2 − 1 ) for independent standard normal G i G_i G i . Hence
v 2 : = E F 0 2 = 2 ∑ i c i 2 , E F 0 4 = 12 ( ∑ i c i 2 ) 2 + 48 ∑ i c i 4 ≤ 15 v 4 . v^2 := \mathbb{E}F_0^2 = 2\sum_i c_i^2,\qquad\mathbb{E}F_0^4 = 12\left(\sum_i c_i^2\right)^2 + 48\sum_i c_i^4 \le15v^4. v 2 := E F 0 2 = 2 i ∑ c i 2 , E F 0 4 = 12 ( i ∑ c i 2 ) 2 + 48 i ∑ c i 4 ≤ 15 v 4 .
If v > 0 v>0 v > 0 , interpolation gives E ∣ F 0 ∣ ≥ v / 15 \mathbb{E}|F_0| \ge v/\sqrt{15} E ∣ F 0 ∣ ≥ v / 15 . Since E ( F 0 ) + = E ∣ F 0 ∣ / 2 \mathbb{E}(F_0)_+ = \mathbb{E}|F_0|/2 E ( F 0 ) + = E ∣ F 0 ∣/2 , Cauchy–Schwarz implies Pr [ F 0 > 0 ] ≥ ( E ( F 0 ) + ) 2 / E ( F 0 ) + 2 ≥ 1 / 60 \Pr[F_0>0] \ge(\mathbb{E}(F_0)_+)^2/\mathbb{E}(F_0)_+^2 \ge1/60 Pr [ F 0 > 0 ] ≥ ( E ( F 0 ) + ) 2 / E ( F 0 ) + 2 ≥ 1/60 . If v = 0 v=0 v = 0 , then F = E F F=\mathbb{E}F F = E F almost surely. If B > 0 B>0 B > 0 , Markov’s inequality gives Pr [ Z > 360 B ] ≤ 1 / 120 \Pr[Z>360B]\le1/120 Pr [ Z > 360 B ] ≤ 1/120 . Thus F ≥ E F F\ge\mathbb{E}F F ≥ E F and Z ≤ 360 B Z\le360B Z ≤ 360 B hold together with probability at least 1 / 120 1/120 1/120 ; since 720 τ = a / 4 720\tau=a/4 720 τ = a /4 , they imply Δ θ ≥ τ Q θ \Delta_\theta\ge\tau Q_\theta Δ θ ≥ τ Q θ . If B = 0 B=0 B = 0 , every edge charged by T T T has g e = 0 g_e=0 g e = 0 almost surely, and both scores vanish.
For the entropy bound, put u = h ⊙ r − θ u=h\odot r^{-\theta} u = h ⊙ r − θ . The initializer and the entropy projections keep the iterates positive on the relative support. The unnormalized entropy identity gives
D K L ( f ∥ u ) − D K L ( f ∥ h ) = θ ⟨ f , log r ⟩ + ⟨ h , r − θ − 1 ⟩ = − Δ θ + θ ⟨ f − b , log r ⟩ . D_{\mathrm{KL}}(f\mathbin\Vert u)-D_{\mathrm{KL}}(f\mathbin\Vert h)=\theta\langle f,\log r\rangle+\langle h,r^{-\theta}-1\rangle=-\Delta_\theta+\theta\langle f-b,\log r\rangle. D KL ( f ∥ u ) − D KL ( f ∥ h ) = θ ⟨ f , log r ⟩ + ⟨ h , r − θ − 1 ⟩ = − Δ θ + θ ⟨ f − b , log r ⟩ .
Bregman projection onto K \mathcal{K} K cannot increase the divergence from any f ∈ K f\in\mathcal{K} f ∈ K . Since 0 ≤ log r e ≤ log 2 0\le\log r_e\le\log2 0 ≤ log r e ≤ log 2 , this proves (20) , including the case f = b f=b f = b .
When validation is accurate, the entropy bound (20) limits the number of accepted updates, while at a candidate with a large violation each trial is accepted with constant probability. Hence, with high probability, an accurate candidate appears within the horizon, and the exponential mechanism selects a nearly accurate one.
Lemma 4.5 (Accuracy of a layer). In the layer setup of Section § 3.2 , suppose that b ∈ K b\in\mathcal{K} b ∈ K and that (14) holds for every candidate and sign. With probability at least 1 − ζ 1-\zeta 1 − ζ , Algorithm 1 1 1 returns a graph h ^ \hat{h} h ^ satisfying
V ( h ^ ) ≤ A + 12 Γ τ + 2 ( 1 + a ) ε 0 log 3 ( N + 1 ) ζ . (21) V(\hat{h})\le A+\frac{12\Gamma}{\tau}+\frac{2(1+a)}{\varepsilon_0}\log\frac{3(N+1)}{\zeta}. \tag*{(21)} V ( h ^ ) ≤ A + τ 12Γ + ε 0 2 ( 1 + a ) log ζ 3 ( N + 1 ) . (21) Consequently, simultaneously for every cut S S S ,
∣ h ^ ( S ) − b ( S ) ∣ ≤ a [ h ^ ( S ) + b ( S ) + P ( S ) ] + O ( A + ( λ + ε 0 − 1 ) log N + 1 ζ ) . (22) \left|\hat{h}(S)-b(S)\right|\le a\left[\hat{h}(S)+b(S)+P(S)\right]+O\left(A+\left(\lambda+\varepsilon_0^{-1}\right)\log\frac{N+1}{\zeta}\right). \tag*{(22)} h ^ ( S ) − b ( S ) ≤ a [ h ^ ( S ) + b ( S ) + P ( S ) ] + O ( A + ( λ + ε 0 − 1 ) log ζ N + 1 ) . (22) All implicit constants are absolute.
Proof. Except with probability ζ / 6 \zeta/6 ζ /6 , all validation noises have magnitude at most c V τ λ ε N c_V\tau\lambda\varepsilon_N c V τ λ ε N . On this event, acceptance gives Δ t ≥ Γ ≥ τ A \Delta_t\ge\Gamma\ge\tau A Δ t ≥ Γ ≥ τ A . By (20) , each accepted step decreases Φ ( h ) = D K L ( b ∥ h ) \Phi(h)=D_{\mathrm{KL}}(b\mathbin\Vert h) Φ ( h ) = D KL ( b ∥ h ) by at least τ A \tau A τ A , so (11) and Φ ≥ 0 \Phi\ge0 Φ ≥ 0 bound the number of acceptances by J 0 = M log ( 2 n 2 ) / ( τ A ) J_0=M\log(2n^2)/(\tau A) J 0 = M log ( 2 n 2 ) / ( τ A ) .
Call h h h good if V ( h ) ≤ A + 12 Γ / τ V(h)\le A+12\Gamma/\tau V ( h ) ≤ A + 12Γ/ τ . By (14) , at a bad candidate one sign has Q θ > 3 Γ / τ Q_\theta>3\Gamma/\tau Q θ > 3Γ/ τ . By Lemma 4.4, the event that the trial chooses this sign, obtains Δ θ ≥ 3 Γ \Delta_\theta\ge3\Gamma Δ θ ≥ 3Γ , and draws ξ t ≥ − Γ \xi_t\ge-\Gamma ξ t ≥ − Γ has conditional probability at least p 0 = ( 1 / 2 ) ( 1 / 120 ) ( 1 / 2 ) = 1 / 480 p_0=(1/2)(1/120)(1/2)=1/480 p 0 = ( 1/2 ) ( 1/120 ) ( 1/2 ) = 1/480 . This statement conditions only on the past. Let I ~ t \widetilde{I}_t I t be the acceptance indicator of trial t t t , padded with ones after the first good candidate; the conditional means of these padded indicators are at least p 0 p_0 p 0 . A sufficiently large C N C_N C N in (16) ensures J 0 ≤ p 0 N / 2 J_0\le p_0N/2 J 0 ≤ p 0 N /2 and
Pr [ ∑ t = 0 N − 1 I ~ t ≤ p 0 N / 2 ] ≤ e − p 0 N / 8 ≤ ζ / 6. \Pr\left[\sum_{t=0}^{N-1}\widetilde{I}_t\le p_0N/2\right]\le e^{-p_0N/8}\le\zeta/6. Pr [ t = 0 ∑ N − 1 I t ≤ p 0 N /2 ] ≤ e − p 0 N /8 ≤ ζ /6.
If no stored candidate is good and all validation noises are small, the sum counts actual acceptances and is therefore at most J 0 ≤ p 0 N / 2 J_0\le p_0N/2 J 0 ≤ p 0 N /2 . Thus a good candidate is stored except with probability ζ / 3 \zeta/3 ζ /3 . Conditional on the list, the exponential mechanism adds the last term of (21) , with failure probability at most ζ / 3 \zeta/3 ζ /3 . Every cut is feasible for SDP; substituting the value of Γ \Gamma Γ from (17) therefore proves (22) .
Privacy of the mechanism
The private input enters a trial through the covariance X θ X_\theta X θ , which Lemma 4.3 handles, and through the part − θ ⟨ b , log r ⟩ -\theta\langle b,\log r\rangle − θ ⟨ b , log r ⟩ of the sampled score. The bound log r e ≤ τ g e \log r_e \le\tau g_e log r e ≤ τ g e matches the sensitivity of the latter to the noise scale c v τ λ c_v\tau\lambda c v τ λ after averaging over the Gaussian sample, so we analyze the sample and the validation jointly.
Lemma 4.6 (Privacy of a trial). Conditional on any common public history, let s = ∥ b − b ′ ∥ 1 ≤ 1 s=\lVert b-b'\rVert_1\le1 s = ∥ b − b ′ ∥ 1 ≤ 1 . For α > 1 \alpha>1 α > 1 and α / λ ≤ c \alpha/\lambda\le c α / λ ≤ c , a complete trial satisfies
D α ( t r i a l b ∥ t r i a l b ′ ) ≤ C α s 2 / λ 2 D_\alpha(\mathrm{trial}_b\Vert\mathrm{trial}_{b'})\le C\alpha s^2/\lambda^2 D α ( trial b ∥ trial b ′ ) ≤ C α s 2 / λ 2 in either direction. This holds for the transcript consisting of the sign, the Gaussian vector, the full noisy validation, and the updated candidate, including rejected proposals. The covariance is not released, and neither input needs to belong to K K K .
By Cauchy–Schwarz, the likelihood moment of the joint release splits into a Gaussian factor, which Lemma 4.3 controls, and a Laplace factor. We control the location shift of the Laplace factor through exponential moments of a weighted average g π g_\pi g π of the coordinates of g g g .
Proof. Fix the sign; the case s = 0 s=0 s = 0 is immediate. Let P P P , Q Q Q be the Gaussian laws under b , b ′ b,b' b , b ′ . Lemma 4.3 applies with perturbation ( 1 / 2 + a ) s / λ (1/2+a)s/\lambda ( 1/2 + a ) s / λ . Put π e = ∣ b e − b e ′ ∣ / s \pi_e=\lvert b_e-b'_e\rvert/s π e = ∣ b e − b e ′ ∣ / s and g π = ∑ e π e g e g_\pi=\sum_e\pi_e g_e g π = ∑ e π e g e , an average of the coordinates of g g g with weights π e ≥ 0 \pi_e\ge0 π e ≥ 0 summing to one. The standardized shift of the conditional Laplace location satisfies
x ( z ) = ∣ Δ θ ( z ; b ) − Δ θ ( z ; b ′ ) ∣ c v τ λ ≤ ∑ e ∣ b e − b e ′ ∣ log r e c v τ λ ≤ s g π λ . x(z)=\frac{\lvert\Delta_\theta(z;b)-\Delta_\theta(z;b')\rvert}{c_v\tau\lambda}\le\frac{\sum_e\lvert b_e-b'_e\rvert\log r_e}{c_v\tau\lambda}\le\frac{s g_\pi}{\lambda}. x ( z ) = c v τ λ ∣ Δ θ ( z ; b ) − Δ θ ( z ; b ′ )∣ ≤ c v τ λ ∑ e ∣ b e − b e ′ ∣ log r e ≤ λ s g π .
We first bound the Laplace factor at order p = 2 α − 1 p=2\alpha-1 p = 2 α − 1 , the order arising from Cauchy–Schwarz below. For equal-scale Laplace laws at standardized distance x ≥ 0 x\ge0 x ≥ 0 , direct integration gives the likelihood moment of order p p p ,
M p ( x ) = p 2 p − 1 e ( p − 1 ) x + p − 1 2 p − 1 e − p x ≤ 1 + 1 2 p ( p − 1 ) x 2 e ( p − 1 ) x , M_p(x)=\frac{p}{2p-1}e^{(p-1)x}+\frac{p-1}{2p-1}e^{-px}\le1+\frac{1}{2}p(p-1)x^2e^{(p-1)x}, M p ( x ) = 2 p − 1 p e ( p − 1 ) x + 2 p − 1 p − 1 e − p x ≤ 1 + 2 1 p ( p − 1 ) x 2 e ( p − 1 ) x ,
where the inequality follows from M p ( 0 ) = 1 M_p(0)=1 M p ( 0 ) = 1 , M p ′ ( 0 ) = 0 M'_p(0)=0 M p ′ ( 0 ) = 0 , and M p ′ ′ ( x ) ≤ p ( p − 1 ) e ( p − 1 ) x M''_p(x)\le p(p-1)e^{(p-1)x} M p ′′ ( x ) ≤ p ( p − 1 ) e ( p − 1 ) x . Under either Gaussian law, g e g_e g e has distribution μ e Z 2 \mu_e Z^2 μ e Z 2 , where Z ∼ N ( 0 , 1 ) Z\sim N(0,1) Z ∼ N ( 0 , 1 ) and 0 ≤ μ e ≤ 1 0\le\mu_e\le1 0 ≤ μ e ≤ 1 . Convexity of u 2 e k u u^2e^{ku} u 2 e k u and Jensen’s inequality give
E g π 2 e k g π ≤ ∑ e π e E g e 2 e k g e ≤ E Z 4 e k Z 2 = 3 ( 1 − 2 k ) − 5 / 2 ( 0 ≤ k < 1 / 2 ) . \mathbb{E}g_\pi^2e^{k g_\pi}\le\sum_e\pi_e\mathbb{E}g_e^2e^{k g_e}\le\mathbb{E}Z^4e^{kZ^2}=3(1-2k)^{-5/2}\qquad(0\le k<1/2). E g π 2 e k g π ≤ e ∑ π e E g e 2 e k g e ≤ E Z 4 e k Z 2 = 3 ( 1 − 2 k ) − 5/2 ( 0 ≤ k < 1/2 ) .
Consequently, if ( p − 1 ) / λ ≤ 1 / 4 (p-1)/\lambda\le1/4 ( p − 1 ) / λ ≤ 1/4 , then
E P M p ( x ( z ) ) ≤ exp { C p ( p − 1 ) s 2 / λ 2 } . (23) \mathbb{E}_P M_p(x(z))\le\exp\{Cp(p-1)s^2/\lambda^2\}. \tag*{(23)} E P M p ( x ( z )) ≤ exp { C p ( p − 1 ) s 2 / λ 2 } . (23)
We now combine the two factors. Let Λ G = d P / d Q ( z ) \Lambda_G=dP/dQ(z) Λ G = d P / d Q ( z ) , and let Λ V \Lambda_V Λ V be the likelihood ratio of the conditional Laplace laws. With expectations under the joint law of the first input, Cauchy–Schwarz gives
E ( Λ G Λ V ) α − 1 ≤ ( E Λ G p ) 1 / 2 ( E Λ V p ) 1 / 2 = exp { ( α − 1 ) D p ( P ∥ Q ) } ( E P M p ( x ( z ) ) ) 1 / 2 . \mathbb{E}(\Lambda_G\Lambda_V)^{\alpha-1}\le\left(\mathbb{E}\Lambda_G^p\right)^{1/2}\left(\mathbb{E}\Lambda_V^p\right)^{1/2}=\exp\{(\alpha-1)D_p(P\Vert Q)\}\left(\mathbb{E}_P M_p(x(z))\right)^{1/2}. E ( Λ G Λ V ) α − 1 ≤ ( E Λ G p ) 1/2 ( E Λ V p ) 1/2 = exp {( α − 1 ) D p ( P ∥ Q )} ( E P M p ( x ( z )) ) 1/2 .
The left side is the order-α \alpha α likelihood moment of the joint Gaussian and validation release. Applying the Gaussian stability bound and (4.6), taking logarithms, and dividing by α − 1 \alpha-1 α − 1 gives D α ≤ C α s 2 / λ 2 D_\alpha\le C\alpha s^2/\lambda^2 D α ≤ C α s 2 / λ 2 . Since p ≤ 2 α p\le2\alpha p ≤ 2 α , a sufficiently small c c c ensures both moment conditions. Exchanging the inputs gives the reverse bound. Finally, the sign is independent of the data, and the updated candidate is postprocessing.
To compose the trials, we need four properties of the schedule (4) , which are also used in § 4.4 . Let N t o t N_{\mathrm{tot}} N tot denote the total number of trials over all layers.
Lemma 4.7 (Schedule bounds). On every execution, for every layer j j j ,
λ j ≥ c σ , N j λ j 2 = O ( ε / σ ) , N t o t = O ( ε σ [ J + 1 + n / γ ] ) , log ( N j + 1 ) ( J + 1 ) β = O ( ε σ ) . (24) \lambda_j \ge c\sigma,\qquad\frac{N_j}{\lambda_j^2}=O(\varepsilon/\sigma),\qquad N_{\mathrm{tot}}=O\left(\varepsilon\sigma[J+1+n/\gamma]\right),\qquad\log\frac{(N_j+1)(J+1)}{\beta}=O(\varepsilon\sigma). \tag*{(24)} λ j ≥ c σ , λ j 2 N j = O ( ε / σ ) , N tot = O ( ε σ [ J + 1 + n / γ ] ) , log β ( N j + 1 ) ( J + 1 ) = O ( ε σ ) . (24) where the implicit constants are independent of C σ C_\sigma C σ .
Proof. The first bound follows from (4) , since λ j ≥ λ 0 = C D σ / γ \lambda_j\ge\lambda_0=\sqrt{C_D}\,\sigma/\gamma λ j ≥ λ 0 = C D σ / γ and γ ≤ 1 / 4 \gamma\le1/4 γ ≤ 1/4 . For the second, the bounds M j ≤ 2 n j D j M_j\le2n_jD_j M j ≤ 2 n j D j and ω j ≥ n j \omega_j\ge n_j ω j ≥ n j give
λ j 2 A j ≥ C A σ 2 D j ω j / γ ≥ c σ 2 M j / γ . \lambda_j^2 A_j\ge C_A\sigma^2D_j\omega_j/\gamma\ge c\sigma^2M_j/\gamma. λ j 2 A j ≥ C A σ 2 D j ω j / γ ≥ c σ 2 M j / γ .
Together with λ j ≥ c σ \lambda_j\ge c\sigma λ j ≥ c σ and (16) , this gives N j / λ j 2 = O ( ε / σ ) N_j/\lambda_j^2=O(\varepsilon/\sigma) N j / λ j 2 = O ( ε / σ ) and N j = O ( ε ( σ + D j ) ) N_j=O(\varepsilon(\sigma+D_j)) N j = O ( ε ( σ + D j )) . The geometric sum ∑ j = 1 J D j ≤ C n U \sum_{j=1}^{J}D_j\le CnU ∑ j = 1 J D j ≤ C n U includes an empty sum when J = 0 J=0 J = 0 . For layer zero, A 0 ≥ c n σ / γ A_0\ge cn\sigma/\gamma A 0 ≥ c nσ / γ and M 0 ≤ C n 2 U M_0\le Cn^2U M 0 ≤ C n 2 U give N 0 = O ( ε σ [ 1 + n / γ ] ) N_0=O(\varepsilon\sigma[1+n/\gamma]) N 0 = O ( ε σ [ 1 + n / γ ]) directly. Summing proves the bound on N t o t N_{\mathrm{tot}} N tot , whose logarithm is O ( ε σ ) O(\varepsilon\sigma) O ( ε σ ) , and the last bound follows. □
The first bound keeps the Rényi order chosen below in the range of Lemma 4.6 , and the second makes the N j N_j N j trials of layer j j j cost O ( α ε s j 2 / σ ) O(\alpha\varepsilon s_j^2/\sigma) O ( α ε s j 2 / σ ) . The third bound enters the running time, and the last makes the logarithmic factor of Lemma 4.5 , at ζ = β 0 / ( J + 1 ) \zeta=\beta_0/(J+1) ζ = β 0 / ( J + 1 ) , of order ε σ \varepsilon\sigma ε σ .
Proposition 4.8 (Privacy of the mechanism). The full mechanism is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -differentially private.
Proof. Fix a common preprocessing output. The distances s j s_j s j and the schedules N j , λ j N_j,\lambda_j N j , λ j are then fixed, whereas the priors may depend on earlier releases. Lemma 4.6 and adaptive Rényi composition bound the divergence of the trials in layer j j j by C α N j s j 2 / λ j 2 C\alpha N_js_j^2/\lambda_j^2 C α N j s j 2 / λ j 2 , including rejected trials. Conditional on the candidate list, V V V has sensitivity ( 1 + a ) s j (1+a)s_j ( 1 + a ) s j , so the final selection has pure privacy cost ε 0 s j \varepsilon_0s_j ε 0 s j . Since ∑ j s j ≤ 1 \sum_j s_j\le1 ∑ j s j ≤ 1 by (8) ,
D α ≤ O ( α ε σ ) ∑ j s j 2 + ε 0 ∑ j s j ≤ O ( α ε σ ) + ε 0 . D_\alpha\le O\left(\frac{\alpha\varepsilon}{\sigma}\right)\sum_j s_j^2+\varepsilon_0\sum_j s_j\le O\left(\frac{\alpha\varepsilon}{\sigma}\right)+\varepsilon_0. D α ≤ O ( σ α ε ) j ∑ s j 2 + ε 0 j ∑ s j ≤ O ( σ α ε ) + ε 0 .
This holds in both directions, at every preprocessing output and subsequent history. We choose α = 1 + 4 log ( 2 / δ ) / ε \alpha=1+4\log(2/\delta)/\varepsilon α = 1 + 4 log ( 2/ δ ) / ε . Equation (24) ensures α / λ j ≤ c \alpha/\lambda_j\le c α / λ j ≤ c . Rényi conversion with failure parameter δ / 2 \delta/2 δ /2 costs ε / 4 \varepsilon/4 ε /4 , and taking C σ C_\sigma C σ sufficiently large bounds the trial term by another ε / 4 \varepsilon/4 ε /4 . The three pure-DP preprocessing releases cost 3 ε 0 3\varepsilon_0 3 ε 0 , so the ideal mechanism is ( 9 ε / 10 , δ / 2 ) (9\varepsilon/10,\delta/2) ( 9 ε /10 , δ /2 ) -DP. Appendix § 6 uses the remaining allowance for the numerical implementation. □
Proof of the upper bound
We now combine the layers and prove Theorem 1.1 . The proof first establishes a bound that holds for all n ≥ 2 n\ge2 n ≥ 2 , 0 < γ ≤ 1 / 4 0<\gamma\le1/4 0 < γ ≤ 1/4 , 0 < ε ≤ 1 0<\varepsilon\le1 0 < ε ≤ 1 , and 0 < δ , β < 1 / 10 0<\delta,\beta<1/10 0 < δ , β < 1/10 , with no lower bounds on these parameters: the mechanism of § 3 is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -differentially private and, with probability at least 1 − β 1-\beta 1 − β , its output H H H on input G G G satisfies simultaneously for every S ⊆ V = [ n ] S\subseteq V=[n] S ⊆ V = [ n ]
∣ w G ( S , V ∖ S ) − w H ( S , V ∖ S ) ∣ ≤ γ w G ( S , V ∖ S ) \left|w_G(S,V\setminus S)-w_H(S,V\setminus S)\right|\le\gamma w_G(S,V\setminus S) ∣ w G ( S , V ∖ S ) − w H ( S , V ∖ S ) ∣ ≤ γ w G ( S , V ∖ S )
+ O ( n ε γ log n γ ε δ β + 1 + n γ ε γ log 2 n γ ε δ β ) . (25) {}+O\left(\frac{n}{\varepsilon\gamma}\log\frac{n}{\gamma\varepsilon\delta\beta}+\frac{1+\sqrt{n\gamma}}{\varepsilon\gamma}\log^2\frac{n}{\gamma\varepsilon\delta\beta}\right). \tag*{(25)} + O ( ε γ n log γ ε δ β n + ε γ 1 + nγ log 2 γ ε δ β n ) . (25)
with an absolute constant in O ( ⋅ ) O(\cdot) O ( ⋅ ) . The lower bounds γ , ε , δ , β ≥ n − c \gamma,\varepsilon,\delta,\beta\ge n^{-c} γ , ε , δ , β ≥ n − c of Theorem 1.1 are used only at the end, to simplify (25) to (2) .
The main step is to verify the certificate (14) in each layer. Here the prior supplies the degree that keeps the harmonic sum of Lemma 4.2 small (§ 1.2 ).
Lemma 4.9 (The certificate in each layer). Let C A C_A C A be sufficiently large. On the accuracy event of Lemma 3.1 , the certificate (14) holds in every layer j j j , that is, with b = b j b=b_j b = b j , P = P j P=P_j P = P j , λ = λ j \lambda=\lambda_j λ = λ j , and A = A j A=A_j A = A j , for every h ∈ K j h\in\mathcal{K}_j h ∈ K j and both signs θ \theta θ .
Proof. On this event, every released layer lies in its confidence set and has edge weights at most U U U . Since P j ≤ 3 U P_j\leq3U P j ≤ 3 U coordinatewise as well, we have T = h + b j + P j ≤ 5 U ≤ λ j T=h+b_j+P_j\leq5U\leq\lambda_j T = h + b j + P j ≤ 5 U ≤ λ j and ∥ deg ( h − b j ) ∥ 1 ≤ 2 R j \lVert\deg(h-b_j)\rVert_1\leq2R_j ∥ deg ( h − b j ) ∥ 1 ≤ 2 R j . The degree floors of the confidence sets, applied to h h h when k = j k=j k = j and to the summand ( 3 / 4 ) k − j h k (3/4)^{k-j}h_k ( 3/4 ) k − j h k of P j P_j P j when k > j k>j k > j , show that for v ∈ L k v\in L_k v ∈ L k with k ≥ j ≥ 1 k\geq j\geq1 k ≥ j ≥ 1 ,
deg T ( v ) ≥ { D j / 4 , k = j , ( 3 / 4 ) k − j D k / 4 , k > j . \deg_T(v)\geq
\begin{cases}
D_j/4, & k=j,\\
(3/4)^{k-j}D_k/4, & k>j.
\end{cases} deg T ( v ) ≥ { D j /4 , ( 3/4 ) k − j D k /4 , k = j , k > j .
Since D k = 2 k − j D j D_k=2^{k-j}D_j D k = 2 k − j D j , the second bound equals ( 3 / 2 ) k − j D j / 4 (3/2)^{k-j}D_j/4 ( 3/2 ) k − j D j /4 ; this is the source of the weights ( 2 / 3 ) k − j (2/3)^{k-j} ( 2/3 ) k − j in ω j \omega_j ω j . Consequently,
∑ v ∈ V j 1 λ j + a deg T ( v ) ≤ C ω j a D j ( j ≥ 1 ) , ∑ v ∈ V 0 1 λ 0 + a deg T ( v ) ≤ n λ 0 . \sum_{v\in V_j}\frac{1}{\lambda_j+a\deg_T(v)}\leq\frac{C\omega_j}{aD_j}\quad(j\geq1),\qquad
\sum_{v\in V_0}\frac{1}{\lambda_0+a\deg_T(v)}\leq\frac{n}{\lambda_0}. v ∈ V j ∑ λ j + a deg T ( v ) 1 ≤ a D j C ω j ( j ≥ 1 ) , v ∈ V 0 ∑ λ 0 + a deg T ( v ) 1 ≤ λ 0 n .
Since λ j 2 = σ D j \lambda_j^2=\sigma D_j λ j 2 = σ D j and λ 0 = Θ ( σ / γ ) \lambda_0=\Theta(\sigma/\gamma) λ 0 = Θ ( σ / γ ) , the harmonic term in Lemma 4.2 is O ( σ ω j / γ ) O(\sigma\omega_j/\gamma) O ( σ ω j / γ ) , and its degree term is O ( R j ) O(R_j) O ( R j ) . As 4 Q θ ( h ) = 4 θ ⟨ E , q ( X θ ) ⟩ − a ⟨ T , q ( X θ ) 2 ⟩ 4Q_\theta(h)=4\theta\langle E,q(X_\theta)\rangle-a\langle T,q(X_\theta)^2\rangle 4 Q θ ( h ) = 4 θ ⟨ E , q ( X θ )⟩ − a ⟨ T , q ( X θ ) 2 ⟩ , Lemma 4.2 , applied to θ E \theta E θ E and T T T , therefore gives (14) with the allowance in (10) for sufficiently large C A C_A C A . □ \square □
Proof of Theorem 1.1 . We first establish (25) . Privacy follows from Proposition 4.8 . For accuracy, we work on the accuracy event of Lemma 3.1 . On this event, b j ∈ K j b_j\in\mathcal{K}_j b j ∈ K j for every j j j , and Lemma 4.9 provides the certificate in every layer. Lemma 4.5 therefore applies in every layer with ζ = β 0 / ( J + 1 ) \zeta=\beta_0/(J+1) ζ = β 0 / ( J + 1 ) , and its logarithmic factor is O ( ϵ σ ) O(\epsilon\sigma) O ( ϵ σ ) by (24) . Hence, simultaneously for all layers and cuts,
∣ h j ( S ) − b j ( S ) ∣ ≤ a [ h j ( S ) + b j ( S ) + P j ( S ) ] + B j , B j = O ( A j + ϵ σ λ j + σ ) . |h_j(S)-b_j(S)|\leq a\left[h_j(S)+b_j(S)+P_j(S)\right]+B_j,\qquad B_j=O(A_j+\epsilon\sigma\lambda_j+\sigma). ∣ h j ( S ) − b j ( S ) ∣ ≤ a [ h j ( S ) + b j ( S ) + P j ( S ) ] + B j , B j = O ( A j + ϵ σ λ j + σ ) .
The zero outputs are exact on this event, and the layer failure probabilities sum to at most ( J + 1 ) ζ = β 0 (J+1)\zeta=\beta_0 ( J + 1 ) ζ = β 0 .
It remains to sum over the layers. The sums ∑ j ω j ≤ 4 n \sum_j\omega_j\leq4n ∑ j ω j ≤ 4 n and ∑ j R j = O ( n σ ) \sum_jR_j=O(n\sigma) ∑ j R j = O ( nσ ) give ∑ j A j = O ( n σ / γ ) \sum_jA_j=O(n\sigma/\gamma) ∑ j A j = O ( nσ / γ ) , and the geometrically growing regularization parameters satisfy ∑ j λ j ≤ C σ ( γ − 1 + n / γ ) \sum_j\lambda_j\leq C\sigma(\gamma^{-1}+\sqrt{n/\gamma}) ∑ j λ j ≤ C σ ( γ − 1 + n / γ ) . It follows that
∑ j B j = O ( σ γ [ n + ϵ σ ( 1 + n γ ) ] ) (26) \sum_j B_j=O\left(\frac{\sigma}{\gamma}\left[n+\epsilon\sigma(1+\sqrt{n\gamma})\right]\right) \tag*{(26)} j ∑ B j = O ( γ σ [ n + ϵ σ ( 1 + nγ ) ] ) (26)
The relative slacks add up as well: with h c = ∑ j h j h_c=\sum_jh_j h c = ∑ j h j and ∑ j P j ≤ 3 h c \sum_jP_j\leq3h_c ∑ j P j ≤ 3 h c , we obtain
∣ h c ( S ) − b ( S ) ∣ ≤ a [ 4 h c ( S ) + b ( S ) ] + ∑ j B j . |h_c(S)-b(S)|\leq a\left[4h_c(S)+b(S)\right]+\sum_jB_j. ∣ h c ( S ) − b ( S ) ∣ ≤ a [ 4 h c ( S ) + b ( S ) ] + j ∑ B j .
Rearranging gives a relative excess of at most 5 a / ( 1 − 4 a ) ≤ γ / 2 5a/(1-4a)\leq\gamma/2 5 a / ( 1 − 4 a ) ≤ γ /2 , a relative deficit no larger than this, and an absolute constant multiplying ∑ j B j \sum_jB_j ∑ j B j .
Finally, the heavy-edge release contributes at most γ w ( S ) / 2 \gamma w(S)/2 γ w ( S ) /2 , with failure probability at most β 0 \beta_0 β 0 , and b ( S ) ≤ w ( S ) b(S)\leq w(S) b ( S ) ≤ w ( S ) . Substituting σ \sigma σ from (4) into (26) proves (25) . The preprocessing, layer, and numerical failure probabilities fit within β \beta β .
Under the hypotheses of Theorem 1.1 , L = log ( n / ( γ ϵ δ β ) ) ≤ ( 4 c + 1 ) log n L=\log(n/(\gamma\epsilon\delta\beta))\leq(4c+1)\log n L = log ( n / ( γ ϵδ β )) ≤ ( 4 c + 1 ) log n . Since 1 + n γ ≤ 2 n 1+\sqrt{n\gamma}\leq2\sqrt n 1 + nγ ≤ 2 n and log n ≤ n \log n\leq\sqrt n log n ≤ n , we have ( 1 + n γ ) L 2 = O ( n log n ) (1+\sqrt{n\gamma})L^2=O(n\log n) ( 1 + nγ ) L 2 = O ( n log n ) , with a constant depending only on c c c . Thus (25) implies (2) .
For the running time, there are O ( ( n / γ ) log ( n / ( γ ε δ β ) ) ) O((n/\gamma)\log(n/(\gamma\varepsilon\delta\beta))) O (( n / γ ) log ( n / ( γ ε δ β ))) private trials and O ( N t o t + J + 1 ) O(N_{\mathrm{tot}}+J+1) O ( N tot + J + 1 ) final SDP evaluations. Each trial uses a log-determinant optimization, a Gaussian sample, and a feasible entropy update. Appendix § 6 implements these operations in time polynomial in the input encoding length, n n n , 1 / γ 1/\gamma 1/ γ , 1 / ε 1/\varepsilon 1/ ε , log ( 1 / δ ) \log(1/\delta) log ( 1/ δ ) , and log ( 1 / β ) \log(1/\beta) log ( 1/ β ) , which is polynomial in n n n and the input encoding length under the hypotheses of Theorem 1.1 .
Lower bound
We prove Theorem 1.2 by establishing a more general bound. Let n n n be sufficiently large, 0 < ε ≤ 1 0<\varepsilon\le1 0 < ε ≤ 1 , 0 ≤ δ ≤ ε / 100 0\le\delta\le\varepsilon/100 0 ≤ δ ≤ ε /100 , 0 ≤ β ≤ 1 / 4 0\le\beta\le1/4 0 ≤ β ≤ 1/4 , and 0 < γ ≤ 1 / 4 0<\gamma\le1/4 0 < γ ≤ 1/4 , and consider an ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -differentially private mechanism that, on every nonnegative weighted input graph G G G on V = [ n ] V=[n] V = [ n ] , outputs a nonnegative weighted graph H H H satisfying (1) simultaneously for every cut with probability at least 1 − β 1-\beta 1 − β . We show that
B = Ω ( n ε min { n , γ − 1 } min { log ( 2 + n γ 2 ) , log ( ε / δ ) } ) , (27) B=\Omega\left(\frac{n}{\varepsilon}\min\left\{\sqrt{n},\gamma^{-1}\right\}\min\left\{\log(2+n\gamma^2),\log(\varepsilon/\delta)\right\}\right), \tag*{(27)} B = Ω ( ε n min { n , γ − 1 } min { log ( 2 + n γ 2 ) , log ( ε / δ ) } ) , (27)
with an absolute implied constant and log ( ε / δ ) = + ∞ \log(\varepsilon/\delta)=+\infty log ( ε / δ ) = + ∞ when δ = 0 \delta=0 δ = 0 . Compared with Theorem 1.2 , this bound holds for every relative error γ ≤ 1 / 4 \gamma\le1/4 γ ≤ 1/4 , and its logarithmic factor is capped at log ( ε / δ ) \log(\varepsilon/\delta) log ( ε / δ ) , reflecting the limited reach of group privacy when δ > 0 \delta>0 δ > 0 .
The proof follows the reconstruction outline at the end of § 1.2 . We run the mechanism on a random sparse bipartite graph whose edges have a common weight W W W and decode from its output a graph that is consistent with it on every cut. Privacy prevents the decoder from recovering most edges, and random signs turn the missed edges into a cut on which the input and the decoded graph differ by more than the relative term can absorb.
Throughout, we fix parameters and a mechanism as above. Put n ˉ = ⌊ n / 2 ⌋ \bar n=\lfloor n/2\rfloor n ˉ = ⌊ n /2 ⌋ and
d = ⌊ min { n ˉ 256 , 1 16 γ 2 } ⌋ , ℓ = min { log n ˉ d , log ε δ } , W = ⌊ ℓ 4 ε ⌋ . d=\left\lfloor\min\left\{\frac{\bar n}{256},\frac{1}{16\gamma^2}\right\}\right\rfloor,\qquad
\ell=\min\left\{\log\frac{\bar n}{d},\log\frac{\varepsilon}{\delta}\right\},\qquad
W=\left\lfloor\frac{\ell}{4\varepsilon}\right\rfloor. d = ⌊ min { 256 n ˉ , 16 γ 2 1 } ⌋ , ℓ = min { log d n ˉ , log δ ε } , W = ⌊ 4 ε ℓ ⌋ .
with the second logarithm infinite when δ = 0 \delta=0 δ = 0 . For sufficiently large n n n , these choices give d ≥ 1 d\ge1 d ≥ 1 , γ d ≤ 1 / 4 \gamma\sqrt{d}\le1/4 γ d ≤ 1/4 , and ℓ / ( 8 ε ) ≤ W ≤ ℓ / ( 4 ε ) \ell/(8\varepsilon)\le W\le\ell/(4\varepsilon) ℓ / ( 8 ε ) ≤ W ≤ ℓ / ( 4 ε ) .
Let F d \mathcal{F}_d F d consist of the simple bipartite graphs on two fixed n ˉ \bar n n ˉ -vertex sets in which every left vertex has degree exactly d d d . Right degrees are unrestricted, and any vertex outside the two sets is isolated. For G ∈ F d G\in\mathcal{F}_d G ∈ F d , let w G w_G w G be its 0 0 0 –1 1 1 edge vector, and write W G WG W G for the graph with edge weights W w G Ww_G W w G . We draw G G G uniformly from F d \mathcal{F}_d F d and run the mechanism on W G WG W G , whose m = n ˉ d m=\bar n d m = n ˉ d edges each have weight W W W . From the output H H H , we decode the first F ∈ F d F\in\mathcal{F}_d F ∈ F d , in a fixed order, satisfying
∣ W w F ( S , V ∖ S ) − w H ( S , V ∖ S ) ∣ ≤ γ W w F ( S , V ∖ S ) + B for all S ⊆ V , (28) \left|Ww_F(S,V\setminus S)-w_H(S,V\setminus S)\right|
\le\gamma Ww_F(S,V\setminus S)+B
\quad\text{for all }S\subseteq V, \tag*{(28)} ∣ W w F ( S , V ∖ S ) − w H ( S , V ∖ S ) ∣ ≤ γ W w F ( S , V ∖ S ) + B for all S ⊆ V , (28)
or a fixed member of F d \mathcal{F}_d F d if no such graph exists. This decoder need not be efficient, and it always returns a graph with m m m edges. We write ∣ G ∩ F ∣ = ∣ E ( G ) ∩ E ( F ) ∣ |G\cap F|=|E(G)\cap E(F)| ∣ G ∩ F ∣ = ∣ E ( G ) ∩ E ( F ) ∣ for the number of correctly recovered edges, and let U \mathcal{U} U be the accuracy event for the input W G WG W G , so that Pr [ U ] ≥ 1 − β \Pr[\mathcal{U}]\ge1-\beta Pr [ U ] ≥ 1 − β . On U \mathcal{U} U , G G G is compatible with H H H , so the decoded graph F F F is compatible as well.
The first claim bounds the expected fraction of recovered edges, without conditioning on the output being accurate.
Claim 5.1. Over the choice of G G G and the randomness of the mechanism, E ∣ G ∩ F ∣ < m / 16 \mathbb{E}|G\cap F|<m/16 E ∣ G ∩ F ∣ < m /16 .
Proof. The ratio E ∣ G ∩ F ∣ / m \mathbb{E}|G\cap F|/m E ∣ G ∩ F ∣/ m is the probability that a uniform edge of G G G belongs to F F F . Delete a uniform edge ( i , j ) (i,j) ( i , j ) of G G G . Conditional on its left endpoint i i i and the remaining graph G − G^{-} G − , the missing neighbor is uniform among n ˉ − d + 1 \bar n-d+1 n ˉ − d + 1 positions by symmetry. On input W G − WG^{-} W G − , the decoded neighbor set of i i i has size d d d and is independent of the missing position, so it contains that position with probability at most d / ( n ˉ − d + 1 ) d/(\bar{n}-d+1) d / ( n ˉ − d + 1 ) . The inputs W G − WG^{-} W G − and W G WG W G differ by W W W unit weight changes, and group privacy (§ 2 ) therefore gives
E ∣ G ∩ F ∣ m ≤ e ε W d n ˉ − d + 1 + δ e ε W − 1 e ε − 1 ≤ ( d / n ˉ ) 3 / 4 1 − d / n ˉ + ( δ / ε ) 3 / 4 < 1 16 . \frac{\mathbb{E}|G \cap F|}{m} \le e^{\varepsilon W}\frac{d}{\bar{n}-d+1}+\delta\frac{e^{\varepsilon W}-1}{e^\varepsilon-1}\le\frac{(d/\bar{n})^{3/4}}{1-d/\bar{n}}+(\delta/\varepsilon)^{3/4}<\frac{1}{16}. m E ∣ G ∩ F ∣ ≤ e ε W n ˉ − d + 1 d + δ e ε − 1 e ε W − 1 ≤ 1 − d / n ˉ ( d / n ˉ ) 3/4 + ( δ / ε ) 3/4 < 16 1 .
The second inequality uses e ε W ≤ e ℓ / 4 = min { ( n ˉ / d ) 1 / 4 , ( ε / δ ) 1 / 4 } e^{\varepsilon W}\le e^{\ell/4}=\min\{(\bar{n}/d)^{1/4},(\varepsilon/\delta)^{1/4}\} e ε W ≤ e ℓ /4 = min {( n ˉ / d ) 1/4 , ( ε / δ ) 1/4 } and e ε − 1 ≥ ε e^\varepsilon-1\ge\varepsilon e ε − 1 ≥ ε , and the last uses d / n ˉ ≤ 1 / 256 d/\bar{n}\le1/256 d / n ˉ ≤ 1/256 and δ / ε ≤ 1 / 100 \delta/\varepsilon\le1/100 δ / ε ≤ 1/100 . The additive privacy term is zero when δ = 0 \delta=0 δ = 0 .
The next claim turns missed edges into a cut discrepancy after subtracting the relative error allowance.
Claim 5.2. For every G , F ∈ F d G,F\in\mathcal{F}_d G , F ∈ F d , there is a cut S ⊆ [ n ] S\subseteq[n] S ⊆ [ n ] such that
w G ( S , V ∖ S ) − w F ( S , V ∖ S ) − γ ( w G ( S , V ∖ S ) + w F ( S , V ∖ S ) ) ≥ 2 ( m − ∣ G ∩ F ∣ ) 5 d − γ m . w_G(S,V\setminus S)-w_F(S,V\setminus S)-\gamma\bigl(w_G(S,V\setminus S)+w_F(S,V\setminus S)\bigr)\ge\frac{2(m-|G\cap F|)}{5\sqrt{d}}-\gamma m. w G ( S , V ∖ S ) − w F ( S , V ∖ S ) − γ ( w G ( S , V ∖ S ) + w F ( S , V ∖ S ) ) ≥ 5 d 2 ( m − ∣ G ∩ F ∣ ) − γ m . Proof. Let A = G − F A=G-F A = G − F and Q = G + F Q=G+F Q = G + F be the difference and the sum of the bipartite adjacency matrices of G G G and F F F , with rows indexed by the left vertices. Draw independent fair signs y j y_j y j on the right vertices, set x i = − sign ( ( A y ) i ) x_i=-\operatorname{sign}((Ay)_i) x i = − sign (( A y ) i ) on the left vertices with independent fair ties, and let S S S be the set of vertices with positive sign. An edge i j ij ij is cut exactly when x i y j = − 1 x_i y_j=-1 x i y j = − 1 , so
w G ( S , V ∖ S ) = 1 2 ( m − x ⊤ G y ) , w_G(S,V\setminus S)=\frac{1}{2}(m-x^\top Gy), w G ( S , V ∖ S ) = 2 1 ( m − x ⊤ G y ) , and likewise for F F F . If row i i i of A A A has k i k_i k i nonzeros, then k i ≤ 2 d k_i\le2d k i ≤ 2 d and ∑ i k i = 2 ( m − ∣ G ∩ F ∣ ) \sum_i k_i=2(m-|G\cap F|) ∑ i k i = 2 ( m − ∣ G ∩ F ∣ ) . The variable ( A y ) i (Ay)_i ( A y ) i has second moment k i k_i k i and fourth moment at most 3 k i 2 3k_i^2 3 k i 2 , so Hölder interpolation gives
E ∣ ( A y ) i ∣ ≥ k i / 3 ≥ 2 k i 5 d , \mathbb{E}|(Ay)_i|\ge\sqrt{k_i/3}\ge\frac{2k_i}{5\sqrt{d}}, E ∣ ( A y ) i ∣ ≥ k i /3 ≥ 5 d 2 k i , including for zero rows.
It remains to show that E [ x i ( Q y ) i ] = 0 \mathbb{E}[x_i(Qy)_i]=0 E [ x i ( Q y ) i ] = 0 for every left vertex i i i . The positive and negative supports of row i i i of A A A have equal size, since G G G and F F F both have left degree d d d . Exchanging the signs y j y_j y j within pairs of positions from these two supports negates ( A y ) i (Ay)_i ( A y ) i and preserves ( Q y ) i (Qy)_i ( Q y ) i . This exchange preserves the law of the signs, and together with the fair ties it gives E [ x i ( Q y ) i ] = 0 \mathbb{E}[x_i(Qy)_i]=0 E [ x i ( Q y ) i ] = 0 . Since x i ( A y ) i = − ∣ ( A y ) i ∣ x_i(Ay)_i=-|(Ay)_i| x i ( A y ) i = − ∣ ( A y ) i ∣ , the cut identities therefore yield
E S [ w G ( S , V ∖ S ) − w F ( S , V ∖ S ) ] = 1 2 ∑ i E ∣ ( A y ) i ∣ ≥ 2 ( m − ∣ G ∩ F ∣ ) 5 d , \mathbb{E}_S[w_G(S,V\setminus S)-w_F(S,V\setminus S)]=\frac{1}{2}\sum_i\mathbb{E}|(Ay)_i|\ge\frac{2(m-|G\cap F|)}{5\sqrt{d}}, E S [ w G ( S , V ∖ S ) − w F ( S , V ∖ S )] = 2 1 i ∑ E ∣ ( A y ) i ∣ ≥ 5 d 2 ( m − ∣ G ∩ F ∣ ) , E S [ w G ( S , V ∖ S ) + w F ( S , V ∖ S ) ] = m − 1 2 ∑ i E [ x i ( Q y ) i ] = m . \mathbb{E}_S[w_G(S,V\setminus S)+w_F(S,V\setminus S)]=m-\frac{1}{2}\sum_i\mathbb{E}[x_i(Qy)_i]=m. E S [ w G ( S , V ∖ S ) + w F ( S , V ∖ S )] = m − 2 1 i ∑ E [ x i ( Q y ) i ] = m . Subtracting γ \gamma γ times the second expectation from the first shows that some cut satisfies the claimed inequality.
Proof of ((27) ). On U \mathcal{U} U , both G G G and F F F satisfy ((28) ), so the triangle inequality gives
W [ w G ( S , V ∖ S ) − w F ( S , V ∖ S ) − γ ( w G ( S , V ∖ S ) + w F ( S , V ∖ S ) ) ] ≤ 2 B W\bigl[w_G(S,V\setminus S)-w_F(S,V\setminus S)-\gamma(w_G(S,V\setminus S)+w_F(S,V\setminus S))\bigr]\le2B W [ w G ( S , V ∖ S ) − w F ( S , V ∖ S ) − γ ( w G ( S , V ∖ S ) + w F ( S , V ∖ S )) ] ≤ 2 B
for every cut S S S .
Applying Claim 5.2, multiplying by 1 U \mathbf{1}_{\mathcal{U}} 1 U , and taking expectations over G G G and the mechanism gives
2 B ≥ 2 W 5 d ( m ( 1 − β ) − E ∣ G ∩ F ∣ ) − γ m W ≥ m W 40 d , 2B\ge\frac{2W}{5\sqrt{d}}\bigl(m(1-\beta)-\mathbb{E}|G\cap F|\bigr)-\gamma mW\ge\frac{mW}{40\sqrt{d}}, 2 B ≥ 5 d 2 W ( m ( 1 − β ) − E ∣ G ∩ F ∣ ) − γ mW ≥ 40 d mW ,
where we use Pr [ U ] ≥ 1 − β \Pr[\mathcal{U}]\ge1-\beta Pr [ U ] ≥ 1 − β and E [ 1 U ∣ G ∩ F ∣ ] ≤ E ∣ G ∩ F ∣ \mathbb{E}[\mathbf{1}_{\mathcal{U}}|G\cap F|]\le\mathbb{E}|G\cap F| E [ 1 U ∣ G ∩ F ∣ ] ≤ E ∣ G ∩ F ∣ , followed by Claim 5.1, β ≤ 1 / 4 \beta\le1/4 β ≤ 1/4 , and γ d ≤ 1 / 4 \gamma\sqrt{d}\le1/4 γ d ≤ 1/4 . Since m = n ˉ d m=\bar{n}d m = n ˉ d , we obtain B ≥ n ˉ W d / 80 B\ge\bar{n}W\sqrt{d}/80 B ≥ n ˉ W d /80 .
It remains to evaluate this bound. Since t / 2 ≤ ⌊ t ⌋ ≤ t t/2 \le\lfloor t \rfloor\le t t /2 ≤ ⌊ t ⌋ ≤ t for t ≥ 1 t \ge1 t ≥ 1 , the choice of d d d gives
d = Θ ( min { n , γ − 1 } ) , log n ˉ d = Θ ( log ( 2 + n γ 2 ) ) . \sqrt{d} = \Theta\left(\min\{\sqrt{n},\gamma^{-1}\}\right), \qquad\log\frac{\bar{n}}{d} = \Theta\left(\log(2+n\gamma^2)\right). d = Θ ( min { n , γ − 1 } ) , log d n ˉ = Θ ( log ( 2 + n γ 2 ) ) .
Together with W ≥ ℓ / ( 8 ε ) W \ge\ell/(8\varepsilon) W ≥ ℓ / ( 8 ε ) , these estimates turn B ≥ n ˉ W d / 80 B \ge\bar{n}W\sqrt{d}/80 B ≥ n ˉ W d /80 into (27) . □
Proof of Theorem 1.2. For sufficiently large n n n , the theorem’s hypotheses imply δ ≤ ε / 100 \delta\le\varepsilon/100 δ ≤ ε /100 , so (27) applies. Since γ ≥ n − 1 / 2 + κ \gamma\ge n^{-1/2+\kappa} γ ≥ n − 1/2 + κ and δ ≤ ε / n 2 \delta\le\varepsilon/n^2 δ ≤ ε / n 2 , the first minimum in (27) equals γ − 1 \gamma^{-1} γ − 1 , while both logarithms in the second are at least 2 κ log n 2\kappa\log n 2 κ log n . This proves (3) , with a constant depending only on κ \kappa κ . □
Theorems 1.1 and 1.2 give the optimal additive error Θ ( n log n / ( ε γ ) ) \Theta(n\log n/(\varepsilon\gamma)) Θ ( n log n / ( ε γ )) under their common parameter assumptions, with constants depending only on c c c and κ \kappa κ . The same conclusion extends to β ≤ 1 / 4 \beta\le1/4 β ≤ 1/4 by running the upper-bound algorithm with failure parameter min { β , 1 / 20 } \min\{\beta,1/20\} min { β , 1/20 } . More generally, for fixed γ \gamma γ , ε \varepsilon ε and δ = n − c δ \delta= n^{-c_\delta} δ = n − c δ , β = n − c β \beta= n^{-c_\beta} β = n − c β with fixed c δ , c β > 0 c_\delta,c_\beta> 0 c δ , c β > 0 , (27) and Theorem 1.1 give the optimal error Θ ( n log n ) \Theta(n\log n) Θ ( n log n ) .
AI Disclosure. The main results and proofs presented here were obtained in August 2026 through interactions with GPT-5.6 Sol. After becoming aware of the work of Eliáš et al. [5 ] , we used GPT-6 Astra to improve the exposition and to assist with the Lean formalization. The authors take full responsibility for the mathematical claims and the final manuscript.
Implementation
The analysis of § 4 concerns an ideal mechanism that computes exact entropy projections and log-determinant optimizers and draws continuous Gaussian and Laplace samples. We sketch a polynomial-time finite-precision implementation that satisfies (25) , and hence Theorem 1.1 . Two points need care: approximate entropy projections must still make progress, and approximate sampling must not invalidate the privacy analysis. We handle the first directly (Section A.1) and the second by coupling the implementation to a quantized reference mechanism in total variation (Section A.2).
Throughout, candidates and bounded inputs have mass at most M ‾ = C n 2 U \overline{M} = Cn^{2}U M = C n 2 U on every execution, and priors have mass at most 3 M ‾ 3\overline{M} 3 M . We use rational public parameters satisfying the calibration inequalities; in particular, we approximate λ j = σ D j \lambda_j = \sqrt{\sigma D_j} λ j = σ D j within a constant factor while retaining λ j ≥ 5 U \lambda_j \ge5U λ j ≥ 5 U , and absorb this factor in C A C_A C A . Equation (24) bounds the number of trials by a polynomial. We fix a public polynomial bound Q ∗ ≥ 1 + Q c Q_* \ge1 + Q_c Q ∗ ≥ 1 + Q c on the number of sampling and score calls on every execution.
Approximate entropy updates
To approximate the entropy gradient uniformly, we keep candidates bounded away from zero on the relative support by restricting each nonempty domain to K ψ = { h ∈ K : h e ≥ ψ ( h 0 ) e for all e } K_\psi= \{h \in K : h_e \ge\psi(h_0)_e \text{ for all } e\} K ψ = { h ∈ K : h e ≥ ψ ( h 0 ) e for all e } with ψ = c ψ γ / n 2 \psi= c_\psi\gamma/n^2 ψ = c ψ γ / n 2 . The private block need not lie in K ψ K_\psi K ψ , so the analysis uses the comparator b ψ = ( 1 − ψ ) b + ψ h 0 b^\psi= (1-\psi)b + \psi h_0 b ψ = ( 1 − ψ ) b + ψ h 0 , while the oracle and the scores still use b b b . On the accuracy event, b ψ ∈ K ψ b^\psi\in K_\psi b ψ ∈ K ψ and ∥ b ψ − b ∥ 1 ≤ 2 ψ M \lVert b^\psi-b\rVert_1 \le2\psi M ∥ b ψ − b ∥ 1 ≤ 2 ψ M ; the bounds A j ≥ c σ / γ A_j \ge c\sigma/\gamma A j ≥ c σ / γ and M j ≤ C n 2 σ / γ M_j \le Cn^2\sigma/\gamma M j ≤ C n 2 σ / γ give 2 ψ M j ≤ c τ A j 2\psi M_j \le c\tau A_j 2 ψ M j ≤ c τ A j for sufficiently small c ψ c_\psi c ψ , and convexity preserves the initial entropy bound (11) for b ψ b^\psi b ψ .
Set ℓ = ψ min e : ( h 0 ) e > 0 ( h 0 ) e > 0 \ell= \psi\min_{e:(h_0)_e>0}(h_0)_e > 0 ℓ = ψ min e : ( h 0 ) e > 0 ( h 0 ) e > 0 , so the coordinates of every h ∈ K ψ h \in K_\psi h ∈ K ψ on the relative support lie in [ ℓ , U ] [\ell,U] [ ℓ , U ] . Let μ = min { 1 / 8 , c τ A / M } \mu= \min\{1/8,c\tau A/M\} μ = min { 1/8 , c τ A / M } . On a geometric mesh of [ ℓ , U ] [\ell,U] [ ℓ , U ] with ratio 1 + μ / 4 1+\mu/4 1 + μ /4 , approximate log t \log t log t by rational values within μ / 4 \mu/4 μ /4 and take their running maxima. Integrating the resulting nondecreasing step function gives a rational convex piecewise-linear function φ \varphi φ with O ( ( 1 + M / ( τ A ) ) [ 1 + log ( U / ℓ ) ] ) O((1+M/(\tau A))[1+\log(U/\ell)]) O (( 1 + M / ( τ A )) [ 1 + log ( U / ℓ )]) pieces of polynomial bit length and subgradients within μ \mu μ of log t \log t log t . For the update center u = h ⊙ r − θ u=h\odot r^{-\theta} u = h ⊙ r − θ , we approximate each − log u e -\log u_e − log u e by a rational c e c_e c e within μ \mu μ and solve the rational LP
h + ∈ arg min h ∈ K ψ ∑ e [ φ ( h e ) + c e h e ] . h^+ \in\mathop{\arg\min}_{h\in K_\psi} \sum_e [\varphi(h_e)+c_eh_e]. h + ∈ arg min h ∈ K ψ e ∑ [ φ ( h e ) + c e h e ] .
Within a layer, these LPs share their constraint matrix, so their optimal vertices have a uniform polynomial encoding bound. Optimality supplies a subgradient s s s of the objective with ⟨ s , h − h + ⟩ ≥ 0 \langle s,h-h^+\rangle\ge0 ⟨ s , h − h + ⟩ ≥ 0 on K ψ K_\psi K ψ , and ∥ s − ∇ F ( h + ) ∥ ∞ ≤ 2 μ \lVert s-\nabla F(h^+)\rVert_\infty\le2\mu ∥ s − ∇ F ( h + ) ∥ ∞ ≤ 2 μ for F ( h ) = D K L ( h ∥ u ) F(h)=D_{\mathrm{KL}}(h\Vert u) F ( h ) = D KL ( h ∥ u ) . Hence
sup h ∈ K ψ ⟨ ∇ F ( h + ) , h + − h ⟩ ≤ 4 M μ ≤ c τ A . \sup_{h\in K_\psi}\langle\nabla F(h^+),h^+-h\rangle\le4M\mu\le c\tau A. h ∈ K ψ sup ⟨ ∇ F ( h + ) , h + − h ⟩ ≤ 4 M μ ≤ c τ A .
By the Bregman identity and ∥ log r ∥ ∞ ≤ log 2 \lVert\log r\rVert_\infty\le\log2 ∥ log r ∥ ∞ ≤ log 2 , the numerical update and the smoothing b ↦ b ψ b\mapsto b^\psi b ↦ b ψ cost at most c τ A + 2 ψ M log 2 c\tau A+2\psi M\log2 c τ A + 2 ψ M log 2 in (20) . Since an accepted update has Δ t ≥ τ A \Delta_t\ge\tau A Δ t ≥ τ A on the validation-noise accuracy event, every accepted update still decreases the potential by Ω ( τ A ) \Omega(\tau A) Ω ( τ A ) .
Finite precision and privacy
A finite-bit sampler cannot reproduce a continuous law. We therefore use a reference mechanism with exact continuous sampling followed by randomized rounding. We first check how rounding affects privacy and progress, then couple the finite-bit implementation to this reference.
For dyadic Δ > 0 \Delta> 0 Δ > 0 , a power of two K K K , and a fresh seed υ \upsilon υ uniform on { 0 , 1 / K , … , ( K − 1 ) / K } \{0,1/K,\ldots,(K-1)/K\} { 0 , 1/ K , … , ( K − 1 ) / K } , we use the randomized rounding Q Δ ( x , υ ) = Δ ⌊ x / Δ + υ ⌋ Q_{\Delta}(x,\upsilon)=\Delta\lfloor x/\Delta+\upsilon\rfloor Q Δ ( x , υ ) = Δ ⌊ x /Δ + υ ⌋ , applied coordinatewise with independent seeds. It has error at most Δ \Delta Δ and preserves nonnegativity. If random vectors z ~ , z ~ ∈ R d \widetilde{z},\widetilde{z}\in\mathbb{R}^{d} z , z ∈ R d can be coupled so that ∥ z − z ~ ∥ ∞ ≤ ρ ≤ Δ \lVert z-\widetilde{z}\rVert_{\infty}\leq\rho\leq\Delta ∥ z − z ∥ ∞ ≤ ρ ≤ Δ except with probability η \eta η , and the seeds are independent of ( z , z ~ ) (z,\widetilde{z}) ( z , z ) , then
d T V ( Q Δ ( z , υ ) , Q Δ ( z ~ , υ ) ) ≤ η + d ( ρ Δ + 1 K ) . (29) d_{\mathrm{TV}}\left(Q_{\Delta}(z,\upsilon),Q_{\Delta}(\widetilde{z},\upsilon)\right)\leq\eta+d\left(\frac{\rho}{\Delta}+\frac{1}{K}\right). \tag*{(29)} d TV ( Q Δ ( z , υ ) , Q Δ ( z , υ ) ) ≤ η + d ( Δ ρ + K 1 ) . (29)
because, with shared seeds, a coordinate can round differently only if its seed falls in an interval of length at most ρ / Δ \rho/\Delta ρ /Δ modulo one. We reserve a total-variation budget ν \nu ν and take Δ \Delta Δ to be the largest power of two satisfying
Δ ≤ c γ ν Q ∗ , where 0 < ν ≤ c min { δ 1 + e ε , β , 1 } . (30) \Delta\leq\frac{c\gamma\nu}{Q_*},
\qquad\text{where}\qquad0<\nu\leq c\min\left\{\frac{\delta}{1+e^{\varepsilon}},\beta,1\right\}. \tag*{(30)} Δ ≤ Q ∗ c γ ν , where 0 < ν ≤ c min { 1 + e ε δ , β , 1 } . (30)
Since Q ‾ ∗ ≥ Q ‾ c ≥ n 2 \overline{Q}_*\geq\overline{Q}_c\geq n^2 Q ∗ ≥ Q c ≥ n 2 , τ = Θ ( γ ) \tau=\Theta(\gamma) τ = Θ ( γ ) , A j ≥ c σ / γ A_j\geq c\sigma/\gamma A j ≥ c σ / γ , M ‾ = O ( n 2 σ / γ ) \overline{M}=O(n^2\sigma/\gamma) M = O ( n 2 σ / γ ) , and λ j ≥ 5 U \lambda_j\geq5U λ j ≥ 5 U , this gives M ‾ Δ ≪ τ A j \overline{M}\Delta\ll\tau A_j M Δ ≪ τ A j , Δ ≪ τ λ j \Delta\ll\tau\lambda_j Δ ≪ τ λ j , and Q c Δ ≤ c ν Q_c\Delta\leq c\nu Q c Δ ≤ c ν .
Clamping rounded degrees to [ 0 , ( n − 1 ) U ] [0,(n-1)U] [ 0 , ( n − 1 ) U ] and replacing R j R_j R j by R j + ∣ V j ∣ Δ R_j+|V_j|\Delta R j + ∣ V j ∣Δ in K j \mathcal{K}_j K j and A j A_j A j restores the confidence-set guarantees; rounding heavy-edge values changes each cut by at most ( n 2 ) Δ \binom{n}{2}\Delta ( 2 n ) Δ .
Rounding a released value is postprocessing, but validation uses rounded Gaussian coordinates. Their features satisfy g ‾ e ≤ 2 g e + 2 Δ 2 \overline{g}_e\leq2g_e+2\Delta^2 g e ≤ 2 g e + 2 Δ 2 and log r ‾ e ≤ τ g ‾ e \log\overline{r}_e\leq\tau\overline{g}_e log r e ≤ τ g e . The standardized validation shift is therefore at most C s ( g π + Δ 2 ) / λ C s(g_\pi+\Delta^2)/\lambda C s ( g π + Δ 2 ) / λ , with g π g_\pi g π as in the proof of Lemma 4.6 , and since E [ ( g π + Δ 2 ) 2 e t ( g π + Δ 2 ) ] ≤ C \mathbb{E}[(g_\pi+\Delta^2)^2e^{t(g_\pi+\Delta^2)}]\leq C E [( g π + Δ 2 ) 2 e t ( g π + Δ 2 ) ] ≤ C for 0 ≤ t ≤ c 0\leq t\leq c 0 ≤ t ≤ c , that proof retains the privacy cost C α s 2 / λ 2 C\alpha s^2/\lambda^2 C α s 2 / λ 2 .
For progress, the maps t ↦ log r ( t ) t\mapsto\log r(t) t ↦ log r ( t ) and t ↦ 1 − r ( t ) − θ t\mapsto1-r(t)^{-\theta} t ↦ 1 − r ( t ) − θ , where r ( t ) = 1 + τ t 2 / ( 4 + τ t 2 ) r(t)=1+\tau t^2/(4+\tau t^2) r ( t ) = 1 + τ t 2 / ( 4 + τ t 2 ) , are C τ C\sqrt{\tau} C τ -Lipschitz, so rounding changes a score by O ( M ‾ Δ ) ≪ τ A O(\overline{M}\Delta)\ll\tau A O ( M Δ ) ≪ τ A ; a slightly larger threshold constant absorbs this loss.
We now approximate each sampling step of the reference mechanism to total-variation error O ( ν / Q ∗ ) O(\nu/Q_*) O ( ν / Q ∗ ) , given the common history. By Lemma 4.1 , the mass bounds, and λ j ≥ 5 U \lambda_j\geq5U λ j ≥ 5 U , the oracle optimizer satisfies c n − 2 I ⪯ X ⪯ n I cn^{-2}I\preceq X\preceq nI c n − 2 I ⪯ X ⪯ n I ; on the relaxed range ( c / 2 ) n − 2 I ⪯ Z ⪯ n I (c/2)n^{-2}I\preceq Z\preceq nI ( c /2 ) n − 2 I ⪯ Z ⪯ n I , the negative objective is λ / n 2 \lambda/n^2 λ / n 2 -strongly convex, so certified convex optimization [15 ] computes a rational X ~ \widetilde{X} X with ∥ X ~ − X ∥ F ≤ c ν / ( Q ∗ n 2 ) \lVert\widetilde{X}-X\rVert_F\leq c\nu/(Q_*n^2) ∥ X − X ∥ F ≤ c ν / ( Q ∗ n 2 ) , which changes the Gaussian law by O ( ν / Q ∗ ) O(\nu/Q_*) O ( ν / Q ∗ ) by Pinsker’s inequality.
We sample N ( 0 , X ~ ) N(0,\widetilde{X}) N ( 0 , X ) by an approximate Cholesky factor and Box–Muller transforms, and Laplace noise by its inverse CDF, using midpoint seeds with O ( log ( n Q ∗ / ( ν Δ ) ) + log ( 1 + scale ) ) O(\log(nQ_*/(\nu\Delta))+\log(1+\text{scale})) O ( log ( n Q ∗ / ( ν Δ )) + log ( 1 + scale )) random bits per uniform and certified arithmetic; midpoint seeds keep every sample bounded by a polynomial on every execution. Outside endpoint intervals of probability η = c ν / Q ∗ \eta=c\nu/Q_* η = c ν / Q ∗ , these maps have polynomially bounded derivatives, which yields coordinate error ρ = η Δ / d \rho=\eta\Delta/d ρ = η Δ/ d , and (A.1) with K ≥ d / η K\geq d/\eta K ≥ d / η bounds the error of each rounded sample by 3 η 3\eta 3 η . The validation center involves logarithms, which we compute to error c ν λ / Q ∗ c\nu\lambda/Q_* c ν λ / Q ∗ ; this changes the Laplace law of scale c ν λ c\nu\lambda c ν λ by O ( ν / Q ∗ ) O(\nu/Q_*) O ( ν / Q ∗ ) .
The final selection of each layer samples from scores computed to accuracy c ν / Q ∗ c\nu/Q_* c ν / Q ∗ in log weight, through cumulative probabilities floored to a dyadic grid of step O ( ν / ( ( N + 1 ) Q ∗ ) ) O(\nu/((N+1)Q_*)) O ( ν / (( N + 1 ) Q ∗ )) . The AboveThreshold instances need a separate argument, because their hidden threshold noise persists across queries: under a coupling of the continuous and rounded threshold noises within Δ \Delta Δ , each comparison differs with probability O ( ε 0 Δ ) O(\varepsilon_0\Delta) O ( ε 0 Δ ) , since the fresh query noise has density O ( ε 0 ) O(\varepsilon_0) O ( ε 0 ) .
Summing over at most Q ∗ Q_* Q ∗ calls and using (A.2), an adaptive coupling places the output law of the implementation within total variation ν \nu ν of the reference law. Consequently, if the reference mechanism is ( ε , δ 0 ) (\varepsilon,\delta_0) ( ε , δ 0 ) -DP, the implementation is ( ε , δ 0 + ( 1 + e ε ) ν ) (\varepsilon,\delta_0+(1+e^\varepsilon)\nu) ( ε , δ 0 + ( 1 + e ε ) ν ) -DP, and its utility failure probability is larger by at most ν \nu ν . The choice of ν \nu ν in (A.2) fits within the budgets left by Proposition 4.8 , and all operations have polynomial bit complexity, as required by Theorem 1.1 .