Private Regression via Data-Dependent Sufficient Statistic Perturbation
Authors: Cecilia Ferrando
Daniel Sheldon
Venue: Accepted by TMLR ()

Abstract: Sufficient statistic perturbation (SSP) is a widely used method for differentially private linear regression. SSP adopts a data-independent approach where privacy noise from a simple distribution is added to sufficient statistics. However, sufficient statistics can often be expressed as linear queries and better approximated by data-dependent mechanisms. In this paper we introduce data-dependent SSP for linear regression based on post-processing privately released marginals, and find that it outperforms state-of-the-art data-independent SSP. We extend this result to logistic regression by developing an approximate objective that can be expressed in terms of sufficient statistics, resulting in a novel and highly competitive SSP approach for logistic regression. We also make a connection to synthetic data for machine learning: for models with sufficient statistics, training on synthetic data corresponds to data-dependent SSP, with the overall utility determined by how well the mechanism answers these linear queries.

Published in Transactions on Machine Learning Research (08/2025)
Private Regression via Data-Dependent Sufficient Statistic Perturbation
Cecilia Ferrando
cferrando umass.
Manning College of Information and Computer Sciences University of Massackusetts Amherst
Daniel Sheldon
sheldon Dcs. wmass, edu
Manning College of Information and Computer Sciences University of Massachusetts Amherst
Reviewed on OpenReview: https: // openreveew. net/ pert/formm id= gdt gtCfDKm9ME
Abstract
Sufficient statistic perturbation (SSP) is a widcly used mothod for differentially private linear regression. SSP adopts a date-inde approach where privacy noise from a simple distribution added to sufficient statistics. However, sufficient statistics can often be expressed linear queries and better approximated by data-dependent mechanisms. In this paper introduce data-dependent SSP for linear regression based on post-processing privately released marginals, and find that it outperforms state-of-the-ar data-independent SSP. We extend this result to logistic regression by developing approximate objective that can be expressed in terms of sufficient statistics, resulting in a novel and highly competitive SSP approach for logistic regression. We also make a connection to synthetic data for machine learning: for models with sufficient statistics, training on synthetic data corresponds to data-dependent SSP, with the overall utility determined by how well the mechanism answers these linear queries.
1 Introduction
Differential privacy (DP) (Doork et al.) 2006) is an established mathematical framework for protecting user privacy while analyzing sensitive data. differentially private algorithm injects calibrated random noise into the data analytic process mask the membership of single records the data, limiting the information revealed about them in the output of the privatized algorithm. The literature encompasses numerous methods for achieving differential privacy across wide range of machine learning algorithms, including objective
perturbation (Chaudhuri and Monteleoni 2008 Chaudhuri et al. 2011 Kifer et al. 2012 Jain and Thakurta 2013), with applications to models trained via empirical risk minimization; gradient perturbation (Bassily et al. 2014 Abadi et al.) 20166), which is commonly used in deep learning and models trained via gradient descent; one-posterior sampling (Wang et al.) 2015 Dimitrakakis et al.] [017)] with applications in private
Bayesian inference; and finally, sulficient statistic perturbation (SSP) (Vu and Slavkovic 2009 McSherry and
Mironov 2009
Dwork and Smith 2010 Zhang al.) 2016 Foulds al.] 2016 Wang 2018 Bernstein and
Sheldon 2019
Ferrando et. al. 2022), with natural applications in exponential family est.imation and linear
regression.
SSP adds calibrated random noise to the sufficient statistics of the problem of interest and uses the noisy sufficient statisties downstream to retrieve the target estimate. It appealing for a number of reasons. Sufficient statistics are by definition an information bottleneck, in that they summarize all the information about the model parameters (Fisher) 1922p. For many models, like lincar regression and exponential family distributions, their sensitivity is easy quantify or bound, simplifying the DP analysis. Finally, they can be privatized via simple additive mechanisms, like the Laplace Gaussian mechanism (Dwork al. 2014

---

Published in Transactions on Machine Learning Research (08/2025)
Existing SSP methods are dato-independent, meaning they add noise to the sufficient statistics in way that does not depend on the underlying data distribution. In a different branch of DP research, recent work has shown that data-dependent mechanisms are the most effective for query answering and synthetic data (Hardt
ct al. 2012: Gaboardi et al. 2014 Zhang et al.) 2017 Aydore et al. 2021 Liu et al. 2021 McKenna et al. 2022
In this paper, we introduce DD-SSP, a data-dependent SSP method that leverages private linear query answering to release differentially private (DP) sufficient statistics. Its most immediate application is to linear regression, where finite sufficient statistics exist and, demonstrate, can be estimated privately through simple transformations of DP pairwise marginals. Furthermore, we extend the application of DD-SSP to models without defined finite sufficient statistics by proposing a novel framework for logistic regression, where approximate sufficient statistics are derived and released in a data-dependent way to train the model by optimizing an approximate loss function.
The proposed framework can be used with virtually any DP query answering algorithm. In this paper, we use AIM (McKenna et all 2022 as our primary method, but show the overall method is robust to different choices. The main advantage of AIM is its demonstrated accuracy at preserving marginal queries, albeit at the cost of restriction to discrete data (a requirement in AIM). We show experimentally that DD-SSP outperforms the state-of-the-art data-independent SSP method AdaSSP (Wang) 2018) for linear regression, and for logistic regression tasks, DD-SSP achieves better results than the widely used objective perturbation baseline. We also compare DD-SSP with DP-SGD (Abadi et al.) 2016), known to achieve excellent performance when hyperparameters are properly fine-tuned. Our results show that the proposed method is competitive with DP-SGD when the privacy cost of hyperparameter tuning taken into account.
Finally, elaborate on the significance of our results with respect to the increasingly popular practice of training machine learning models on DP synthetic data. Our results support the observation that for these models training on synthetic data generated by linear-query preserving mechanisms effectively corresponds to a form of data-dependent SSP.
2 Background
2.1 Differential privacy
Differential privacy (DP) (Dwork et al. 2006) has become the preferred standard for preserving user privacy in data analysis, and it has been widely adopted by private and governmental organizations. Differential privacy allows many data computations (including statistical summaries and aggregates, and the training of various predictive models) to be performed while provably meeting privacy constraints. The concept of neighboring datasets is integral to differential privacy, which aims to limit the influence of any one individual on the higi output in order to safeguard personal privacy.
Definition 2.1 (Neighboring datasets). Two datasets D and D' are considered neighbors (D ~ D') D can be created by adding or deleting single record from D.
Based on the concept of neighboring dalasets, we can define the sensilivily of a function:
Definition 2.2 (L2 sensitivity). Given a vector-valued function of the data f - 12, the Le sensitivity of f is defined A(f) maxp~D' (D) - (D)
Differential privacy can be achieved via different mechanisms of addition of calibrated random noise, with slightly different definitions. In this paper, we adopt (e, which can be achieved via the Gaussian Mechanism.
Definition 2.3 ((e, Diffferrtttt Privacy). A randomized mechanism M: D + R satisfies (e, -differrenll privacy if for any neighbor datasets D ~ D' E D, and any subset of possible outputs S C R
Pr(M(D) E S] < exp(c) Pr E
2

---

Published in Transactions on Machine Learning Research (08/2025)
Definition 2.4 (Gaussian mechanism). Let f: R2 be vector-valued function of the input data. The Gaussian mechanism is given by
f(D)
where v is random noise drawn from o0) with variance o² 2 (1.12//6)) A()) and A()) is the Le-sensitivity of f. That is, the Gaussian mechanism adds i.d.. Gaussian noise to each entry of f(D) with scale a dependent on the privacy parameters.
Proposition 2.5. (Dwork et al. 2014) The Gaussian mechanism in Definition 2.4
satisfies (c, (c,5)-DP.
Proposition 2.6 (Post-processing property of DP). (worrk al. 2014) If M(D) is (c, then for any deterministic or randomized function 9, g(M(D)) satisfies (c.6)-DP.
2.2 Data-independent sufficient statistic perturbation
Sufficient Statistic Perturbation (SSP) is widely used differential privacy mechanism that introduces privacy noise the level of summary statistics. For example, differentially private linear regression is commonly achieved by directly perturbing the sufficient statistics x and X via an additive noise mechanism, such as the Gaussian mechanism, where X E 1xd is the feature matrix and y E R is the response vector. The noise is added independently to each entry of these statistics based on the privacy parameters and the global sensitivity: the sensitivity of X X is bounded by || and that of X y by || ||]]], where ||*||| and || are bounds on the feature and target vectors respectively (for detailed derivation of the scnsitivity bounds, see Appendix D). Specifically, SSP for linear regression is usually performed by splitting the privacy budget. into (1) and 02) that 61 E2 and 81 62 = 6, and computing the following:
d is a symmetric matrix with upper-triangular entries sampled from \(0, 1), and the noise scale is x2 21/(1.2/66))1111
X = X + vZ1 where Z1 E dxdd
Xyy= = x + 22n where Ze ~ NO, Ia), and the noise scale is v² 21n(1.25/88 2
The privatized estimates XTX and X are then used to compute the private estimator θ = (XTX) X y. This approach is simple and effective, but treats all entries in the sufficient statistics uniformly, adding entry-wise noise components calibrated to the same scale that only depends on the data through measures of global sensitivity. This implies that the noise mechanism does not exploit. the structure of the underlying data to determine how the privacy noise is allocated. We call this mechanism data- independent SSP.
Later in this paper, we will instead leverage data- detendeennddnt privacy mechanisms for estimating sufficient statistics. Data-dependent mechanisms have gained traction in the field of differentially private data generation the most effective mechanisms for query answering and synthetic data. The next section introduces the relevant background on differentially private synthetic data to introduce the context and motivation for our proposed data-dependent SSP methods.
2.3 Differentially private synthetic data and query- mechanisms
Differentially private synthetic data generation aims to produce surrogate data that preserves key statistical
propertics of the original data while ensuring privacy (Hardt et al. 2012 Zhang et al. 2017 Xie et al. 2018
Jordon et al.) 2019 McKenna et al. 2019 Rosenblatt et al. 2020 Vietri et al. 2020 Liu et al. 2021 Aydore
et al.) 2021 McKenna et al. 22021b Vietri et al.) 2022 McKenna et al., 2022 p. Rather than perturbing the
data or downstream model directly, these methods fit a generative model to privatized statistics of the
data, then sample from the model to produce surrogate data. This synthetic data can then be used for wide range of analytical lasks without further privacy cost.
The following definitions allow us to formally elaborate on differentially private synthetic data. Definition 2.7 (Dataset). A dataset is defined as a collection of n potentially sensitive records. Each
record (9) D d-dimensional vector (x ..... (()) (0))
3

---

Published in Transactions on Machine Learning Research (08/2025)
SSP
Linear Query Answering/Synthetic Data
DP noise
DP noise
DD-SSP
X X
X7X X
X XTy
X, y
X, Sensitive Data
M
X,
X
Sensitive Data
Sufficient Statistics
DP Sufficient Statistics
DP Marginals
DP Synthetic Data
DP Sufficient Statistics
Figure 1: Diagram of the SSP data-independent workflow (left) vs the data-dependent linear query answering mechanism for marginal release/ release/synthees syythhtic data workflow (right). Quantities indicated in blue follow privacy noise injection and are differentially private.
Definition 2.8 (Domain). The domain of possible values for attribute X, is 22 "h.....mhh The full domain of possible values for (+) is thus . Ω2 X ... x Pg which has size II, my = m.
We will later talk about numerical encodings of attributes (Section 3.1
Definition 2.9 (Marginals). Let [d] be a subset of features, Q, = Iljer 2z. m, 10pl and Xr (xi) The marginal is vector 14r E Rm, indexed by domain elements t E Q2 such that each entry is m+14 ExeD 1 Ix+ = t] (i.e., counts).
With marginal queries, one record can only contribute a count of one single cell of the output vector. For this reason, the L2 sensitivity of a marginal query M, is 1, regardless of the attributes in This facilitates the differential privacy analysis for marginal queries.
Definition 2.10 (Workload). A marginal workload W is defined as a set marginal queries Ti...., TK where T% S [d].
The goal of workload-based synthetic data generation models to minimize the approximation error on workload queries.
A widely used framework in this space the selett-meensurr-eeeossssss paradigm (Hay al. 2009 Li al,
2010 Ding al. 2011 Xiao al. 2012 Li and Miklau 2012
Xu al. 2013 Yaroslavtsev et al. 2013
Li et al. 2014 Qardaji et al. 2014
Zhang al. 2014 Li al. 2015
McKenna et al. 2021a). in which
workload of marginal queries is selected, privately measured, and then used to reconstruct either the full data distribution or synthetic dataset. Many algorithms in this class are data-dependent: the choice of which queries to measure is based on the data itself, leading to better utility for a fixed privacy budget.
One example palecd-measurre-rrronnttrr AIM (MeKenna et al., (022). AIM (Adaptive and Iterative Mechanism) method that selects marginal queries to measure via scoring function that assesses the expected utility of the measurements based on the data. This data-awareness allows AIM to focus the privacy budget where it matters most, depending on the data distribution. Note that AIM uses zero-concentrated differential privacy (zCDP) [Bun and Steinke 2016), an alternative privacy definition; the Gaussian mechanism as defined in Section 2.1 sa satisfies 20z CDP (Bun and Steinke 2016). our experiments, we work with (c, 5)-DP and the conversion to zCDP is handled internally in AIM.
method, and the one we use primarily this paper, is stato-of-the-art data-dependent
In our experiments, we use AIM directly to release marginals without sampling synthetic data, treating as a general-purpose, data-dependent linear query release mechanism.
4

---

Published in Transactions on Machine Learning Research (08/2025)
3 Methods
In this paper, we propose methods to privately estimate sufficient statistics in a data-dependent way. Specifically, our methods leverage privately released marginals computed by data-dependent linear query answering algorithm to estimate sufficient statistics. We call this set of methods DD-SSP. The main advantage of DD-SSP is that it is dala-dependent. Our approach stems from the insight that, while data-independent noise addition is a simple and established approach to SSP, many sufficient statisties can be expressed as linear queries, creating an opportumity to improve utility by using data-dependent query-answering DP mechanisms, which often achieve higher accuracy than simple additive noise mechanisms [McKenna et al. 2022p. In fact,
using private synthetic data to train cerlain models is already a form of SSP. Figure 1 compares a standard SSP workflow and our proposed DD-SSP workflows. As seen in the figure, the pipeline of releasing synthetic data and then training a model via sufficient statistics can be viewed as specific way of privatizing sufficient. statistics for model training.
For linear regression, the application is straightforward: the problem has finite sufficient statistics and we demonstrate that two-way marginal queries are sufficient for their cstimation. For other modcls, finite sufficient statistics are not available, but a polynomial approximation of the loss functions provides approximate sufficient statistics. This is the case for logistic regression, where finite sufficient statistics do not exist, but a Chebyshev polynomial approximation based on [Huggins et al. (2017) allows us to propose an approzimate version of the learning objective based approximate sufficient statistics that can be expressed linear queries, again retrievable via two-way marginal tables.
We use the synthetic data mechanism AIM as our private query answering algorithm and modify its imple- mentation to output marginals directly, without the need to execute the synthetic data generation step. Depending on the input workload, AIM will privately release marginals that preserve certain linear queries more accurately. We find that two-way marginal workload is sufficient for estimating or approximating the sufficient statistics for both linear and logistic regression. The proposed method is amenable to generalization beyond these classes of problems and can be potentially extended to others by i) identifying or approximating their sufficient statistics and ii) customizing the workload passed on as input in AIM accordingly. Since our proposed methods are based on post-processing DP workload query answers, the differential privacy analysis is straightforward (Definition 2.6
3.1 Numerical encoding
We assume discrete (or discretized) input data, which is common format for tabular data and is required by AIM and other marginal- based approaches. However, for machine learning, each record x must be mapped to a numorical vector x = (x. y) where x E IR is a feature vector and y E IR is a target. While the details of this encoding are often overlooked, they are important here for two reasons. First, they are needed to tightly bound ||>/]], which used in sensitivity calculations of a number of DP MT. methods, with tighter bounds leading to higher utility. Second, the encoding is a key part of recovering sufficient statistics from marginals.
Let bhy (x,) E R be the ooe encoding of Xj, i... the vector with entries (gG( 1[x = s] for each E Qz. We consider any numerical encoding of the form X; + (xy) where A3 E IRP; is a fixed linear transformation applied to the one-hot vector. This covers two special cases of interest. The first is the scalar encoding with A, = u.. for a vector By E Rm that specifies the numerical value for each s E 2y. In this case the mapping simplifies to X₁ + vz(x,). The second special case of interest is when A, = T, is the my x mj identity matrix, so the mapping simplifies to X; + Ay(x;) to give the one-hot encoding itself. Another common variation is reduced one-hot encoding where A; = I, E (m)xm)) is equal to I with one row dropped to avoid redundant information in the one-hot encoding. We include simple example of the encoding strategy in Appendix B
The full encoded record is = (= where ²b = Az)) E Rp, is the encoding of the jth altribute and these column vectors are concatenated vertically. A single entry of z is selected as the target variable y leaving feature vector x of dimension p = (2) p,) - Later, we will also use indexing expressions like (g) and ()p.)) to refer to blocks of a vector or matrix corresponding to the encoding of the jth and kth attributes.
5

---

Published in Transactions on Machine Learning Research (08/2025)
Let 200) (x(1) (x)) denote the encoding of record ( and let X E Rxx be the matrix with ith equal to (a!(0)² and y E I be the vector with ith entry equal to y() Many DP MT. methods require bounds on the magnitude of the encoded data. Let || = supzex || and ||||| = supyey lel be bounds provided by the user where X' C Iº and y C R are guaranteed to contain all possible encoded feature vectors z and target values y, respectively. For example, a lypical bound || = ||=+|| where =x 2 sup |xx] bounds the magnitude of a single feature. 3y is the scalar encoding of Xj we can take =x = max [s)(s)] The following proposition describes how to tightly bound a feature vector that combines scalar features and one-hot encoded features.
Proposition 3.1. Suppose x = (u, w) where u E R satisfies ||u] S |[T]]] and w E R contains the one-hol encodings (either reduced or not reduced) of c attributes. Then ||||| := / 2 + an upper bound on ||
Proof. ||=||2 ||u| + ||w||2 < | e where || I c because is the concatenation of vectors each with at most single entry of 1 and all other entries equal to O.
Suppose u consists of scalar features and | is obtained by bounding each one separately described above. This bound is tighter than the naive one of V|V + b that would be obtained by bounding each entry of the one-hot vectors separately.
3.2 Linear regression
The goal of linear regression is to minimize the sum of squared differences between the observed values y and predicted values X0 in linear model with 0 e Rº. The ordinary least squares (OLS) estimator is obtained by minimizing the squared error loss function lly x0|1.. Mathematically, the OLS estimator is given by i = xX" 'XTy, y. In this context, the sufficient statistics are T(X, {X" X, XX,TT y). In DD-SSP, we approximate T(X, y) using linear queries. Specifically; we show that each entry of X and X"y y can be obtained from pairwise marginals. The sufficient statistics will consider all have the form of empirical second moments of the encoded attributes.
3.2.1 Sufficient Statistics from Pairwise Marginals
Let Z = [X, v] E R2x(x+1), The matrix 7 has blocks that contain our sufficient statistics of interest:
x y
XTy
zzz
(1)
yTy
However, we will see that we can also construct z Z directly from marginals.
Proposition 3.2. Let (Z p) be the block of z Z with rows corresponding to the jth attribute encoding =Ul (xs) and columns corresponding to the kih altribule encoding Z Axvx(xa). Then
(2 2)EM = AN
where (Pj,)) E mm is the (j, k.)-mrgginall shaped as a matrix with (s, entry [g,a(s,t] = Et 1 8, Xx =].. Note that according to this definition (195) diag(uy).
This shows that we can reconstruct the sufficient statistic matrix Z Z directly from the set of all single- altribute and pairwise marginals. Note that single-attribule marginals Jt can be constructed from any Hi,k with k #
Proof. The sufficient statistic matrix can be written as 2T = Eh. (=)0)) Indexing by blocks gives
(Z 2)
(9 1
(
6

---

Published in Transactions on Machine Learning Research (08/2025)
A ( )
Σ (x(()))(()xx))))
A,
In the last line, used that (xy(x) ① (a(((e)) summinn over all gives the matrix (uga).
(0 yT is matrix with (s,t) entry equal to 1(x) (0)
8, Xx
(6)
t]. 0
Algorithm _ outlines how to retrieve approximate sufficient statistics X X and X from marginals privately estimated by AIM. This implies
solve DP linear regression by retrieving X and X y outlined
in Algorithm and ii) finding 0pp = X XTy.
Algorithm DD-SSP
M +- DPQuery(DD, e, 6) is the collection of privately computed pairwise marginal tables My.a attribute pairs ki computed by DP query release algorithm of choice DPQuery.
(ZTZ) t A, A for all attribute pairs (j. k) (see Proposition 3.2
3: Extract XTX and XTy from Z using the block structure of Equation
Proposition 3.3. DD-SSP is (e, D.D..
The proof follows directly from the (c, 6D-DP properties of the marginal-rcleasing algorithm (in our case, AIM), and the fact that all subsequent steps are post- proseprroessing of DP result (Definition 2.6
3.3 Logistic regression
Logistic regression predicts the probability a binary label y E (11 takes value +1 as p = (ex(x+x((==x))) where 0 IRP coefficient vector and 0 is the dot-product. The log-likelihood function is
(()) = Σ () ())
1=1
where d(s) ;= - log(1+ Optimizing this ligeliiel is convex optimization problem solvable numer- ically via standard optimizers. The log-likelihood does not have finite sufficient statistics. However, Huggins ltt al. (2017) offers a polynomial strategy to obtain approzimale sufficient statistics for generalized linear models (GLMs), including logistic regression. Kulkarni et al. 2021 used a similar polynomial approximation for private Bayesian GLMs.
We propose a novel DP logistic regression method that combines two ideas:
use a Chebyshev approxi- mation of the logistic regression log- likeliool based on Huggins et al. (0177) which allows to write the objective in terms of approximate sufficient statistics, and then ii) use AIM privately released marginals to estimate the approximate sufficient statistics without accessing the sensitive data. This gives us the option to directly optimize an approximate log-likelihood based on privatized linear queries computed by AIM. The choice the input workload for AIM depends on the characterization the approximate likeliooddood. Based on our derivation below, we find that suitable workload input for logistic regression is all pairwise marginals.
Huggins et al. (2017) propose to approximate {(f) by using degree-M polynomial approximation of the function Φ:
M (M)
Φ(s) = (MM(s))=
bm
gm
7

---

Published in Transactions on Machine Learning Research (08/2025)
-1-
-2-
-3-
5-
(s))
6-
22(5)
-6
-4
-2
2
4
1og(1++ - The inner products (1()) 0) tend to be concentrated in the range [-4, 4] across many datasets (Huggins al. 2017).
Figure 2: Degree 2 Chebyshev approximation of the logit function d, where ((8) : -
We conservatively choose range [-6,6 6] based the inner DP products of the chosen datasets.
where b. (M) are constants. There are different choices for the orthogonal polynomial basis, and as in Huggins et al. 2017). we focus on Chebyshev polynomials, which provide uniform quality guarantees over a limite
interval R. R] for positive (Figure 2 We can then write
{(O)
(1.) (0)00
Based on the distribution of noisy inner products obtained through objective perturbation (Figure 4 Appendix C), we choose to work with a degree-2 Chebyshev approximation over the range [-6, 6, 6), leading to a precise approximation over a range that encompasses most of the observed inner product values.
Proposition 3.4. The logistic regression log-likelihood is approzimated by second order Chebyshev polynomial [(0) zs (2) + (12) 0XT + b12). XT where b/2) ((2) and 662) are conslands, and XT X and XTy can The mazimizer of this approsimate log-likelihood
be retrieved from pairwise marginals as in Proposition Y.
is available in closed form as Opr-chicb = 2
(XT
XTy
The proof is provided in Appendix This allows us to define logistic regression objective where X and X are obtained via Algorithm | which is DP by post-processing (Proposition 3.3). Further, the optimal solution this objective is a simple rescaling of the DD-SSP linear regression solution using these features
and labels. It can be shown that the Chebyshev coefficients for d(s) satisfy b(2) 0 and b < 0, so the
rescaling factor (2) is positive.
28
3.4 Connections synthetic data
Based the insight that sufficient statistics (or their approximations) can be expressed as linear queries, the proposed framework highlights novel connection between differentially private synthetic data generation and SSP (Figure D. Query answering algorithms are often used in synthetic data generation procedures. Many such procedures follow the selectmncauur--rennsruee approach to synthetic data, where lincar queries are privately estimated from noisy measurements,, and integrated into a model from which synthetic data can be sampled. This process ensures that the output synthetic data supports the selected linear queries. The synthotic data can then be used downstream to compute any statistic of interest, or in the example of lincar regression, we could fit the model by training on the synthetic data. This workflow differs from DD-SSP only in that it consolidates the noisy measurements into model and samples synthetic data from it.
8

---

Published in Transactions on Machine Learning Research (08/2025)
By training celect-measuur--rcoonstttt synthetic generative models to preserve the appropriate workload of queries, synthetic data can therefore be "tuned" for specific machine learning tasks; for example, based on the findings in 3.2 and 3.3, we expect synthetic data that preserves pairwise marginals to perform well on linear and logistic regression, as it implicitly computes the relevant sufficient statistics (or approximate sufficient statistios). These findings provide a new perspective that enhances the understanding and utility of private synthetic data, especially as related synthetic data for machine learning tasks.
3.5 Generality of the approach
The proposed approach is amenable to generalization on two fronts: i) the flexibility with respect to the choice of private linear query answering method, and ii) the applicability to a variety of models.
Query-answering methods are oflen used in synthetic data generation algorithms. Virtually any private query answering algorithm, such as Vietri et al. (2020); McKenna et al. (2021b); Aydore et al. (2021), D. could be adopted in the context of DD-SSP. To give a concrete example, we run supplementary experiments using MST (McKenna et al. 2021b) instead of AIM within our framework (Appendix H. Private-PGM can also be replaced with different methods for model estimation from the private measurements. In Appendix [H]] we show results for experiments where AIM is combined with the mixture inference step from RAP (Aydore et al. 2021
The DD-SSP approach can be extended to any model where sufficient statistics can be linked to marginal queries either directly (as we demonstrate for linear regression in 3.2 or via polynomial approximation (as in logistic regression, 3.3 More detailed extensions of the method are discussed in Section 5
3.6 Baselines
We compare DD-SSP to synthetic data method AIM-Syuth, where private measurements are used to estimate the underlying distribution, and surrogate data is sampled from it. We train AIM-Synth with an input workload of all pairwise marginals to match the workload utilized for DD-SSP. Since marginal-based synthetic data is designed to preserve the same linear queries that are sufficient to solve linear regression, or approximately sufficient for logistic regression, the expectation is that DD-SSP will closely match the performance of AIM-Synth. The difference between these approaches is whether linear queries for sufficient statistics are computed directly from marginals estimated by the mechanism, or computed from synthetic data (Figure D.
We also compare both methods against established DP baselines. Since our methods are based on privately reconstructing sufficient statistics, for DP linear regression sufficient statistic perturbation (SSP) is the natural baseline choice. We choose AdaSSP (Wang 2018) for its competitive performance. AdaSSP uses limited data-adaptivity to add a ridge penalty based on an estimated bound on the cigenvalues of x but then adds independent. noise to each entry of the sufficient statistiics, unlike fully data-adaptive query-answering mechanisms. The AdaSSP algorithm is detailed in Appendix DD For logistic regression, objective perturbation (ObjPert) is widely adopted solution originally proposed by Chaudhuri et al. (2011), and further refined by Kifer et al. (2012) where it is extended to (c, 6)-D,, with more general applicability and improved guarantees. Algorithm and details are provided in Appendix [.] Both AdaSSP and ObjPert determine how much noise to add based on || which is the upper bound to the L2-norm of any row of X (Section 3.1]. For example, in AdaSSP, x X is noise-perturbed proportionally to || From Proposition 3.1 we can set || = ||2/|/2 where ||44|| a bound on the mumerically-encodeed features and e the number of one-hot-encoded attributes to obtain tight scnsitivity bound for these basclines.
In addition to our proposed methods, we compare against DP-SGD (Abadi al., 2016), widely adopted algorithm for differentially private training. DP-SGD is highly sensitive to the choice of hyperparameters and requires extensive tuning to achieve optimal performance. To accurately account for the privacy loss incurred during hyperparameter luming, advanced privacy accounting techniques must. be applied (Ponomareva el al., 2023). To illustrate the variability in DP-SGD's performance, our plots depict a shaded region representing the range between two versions of DP-SGD: an "optimistic" bascline that disregards the privacy cost of hyperparameter tuning, artificially inflating performance, and a more realistic version that incorporates this cost using advanced composition (Steinke) 2022). The effective performance of DP-SCD in practical scenarios,
9

---

Published in Transactions on Machine Learning Research (08/2025)
including with more advanced privacy accounting (Papernot and Steinke 2021 is expected to lie within this range.
3.7 Limitations
When choosing AIM as the mechanism for DP marginals, we are limited to working with discrete data, which is a requirement in AIM itself. Thus, our comparisons to other regression methods are scoped to discrete numerical data. Future work may consider DD-SSP with other mechanisms that support continuous data without discrctization. For the logistic regression approximation, we use Chebyshev sccond-order polynomials; other approximation functions and/or degrees of precision could be evaluated. As shown in section DDPSSP demonstrates overall gains in regression accuracy compared to baseline methods, however this improvement comes at the cost of increased computational time tied to the complexity involved in privately releasing private marginals for large domains with high utility. This cost can be significantly reduced by replacing AIM with faster marginal-releasing methods, which we demonstrate in Appendix [H] More detail on the computational G including few accessible strategies to mitigate the computational costs
runtime is discussed in Appendix in real-world applications.
4 Experiments
In our experiments, we evaluate the effectiveness of DD-SSP on both linear and logistic regression tasks) D For linear regression, our main goal is to demonstrate the effectiveness of data-dependence for SSP. We therefore compare primarily against AdaSSP, a standard SSP baseline. For reference, we also compare
the public solution and to DP-SCD (Abadi et al. 2016), widely used non-SSP method, as reprosentative of this class of methods; several other non-SSP approaches have been recently proposed for differentially private linear regression, including model selection via approximate Tukey depth (Amin el al. 2022)) and iterative private gradient descent (Brown et al.) (024).. For SSP, Tang et al. (2024) recently integrated gradient boosting and clipping with AdaSSP with the primary goal of mitigating the performance impacts due to data clipping when tight bounds on the range of the data are not known in advance; this is largely orthogonal to our goal of improving SSP via data-dependence in selecting and measuring queries. For logistic regression, we benchmark DD-SSP against ObjPert and DP-SGD. Both are widely adopted methods for logistic regression under differential privacy, with the caveat that DP-SGD has strong dependence hyperparameter tuning - as we later further discuss. We also assess the performance of AIM-generated synthetic data (AIM-Synth), observing that it closcly mirrors DD-SSP across tasks, reinforcing our hypothosis that data-dependent estimation of sufficient statistics underlies the strong performance of harginal-baser synthetic data in machine learning settings.
We compare the Mcan Squared Error (MSE) of DP query-based methods DD-SSP and AIM-Synth against the DP baseline AdaSSP and the public baseline for E (0.05, 0.1, 0.5, 2.0), with a fixed d = 10-3 Figure 3 shows that DD-SSP and AIM-Synth have nearly identical performance and both improve significantly upon AdaSSP on all datascts except ACSIncome, where performance is similar. For logistic regression, DD-SSP closely matches AIM-Synth and surpasses ObjPert in low-c regimes while being competitive at higher e values. Assessing DD-SSP vs. DP-SGD is more challenging due to its reliance on hyperparameter fine-tuning. We represent this variability with a shaded region spanning the case where DP-SGD accounts for the privacy cost of hyperparametor tuning via advanced composition (Stcinke) 2002). and the case where this cost is ignored. Our results show that DD-SSP competitive with DP-SGD under advanced composition, with performance varying across datasets. Additional details on experimental setup, datasets, and implementation can be found in Appendix G
Based on these results, we observe the following:
DD-SSP is a competitive option for DP lincar and logistic regression, surpassing data-independent SSP and Objtert baselines specific cases, and being competilive with DP-SGD overall.
All experiment code available at httpe://gthbb..a/cccllaafferrrre
10

---

Published in Transactions on Machine Learning Research (08/2025)
adult
taxi
14
Public
DD-SSP
AlM-Synth
MSE
10-4
DP-SGD
AdaSSP
10
10
10
10a
10a4
16P
ACSincome-LIN
40-0-
10
10
10
10a
10
10'
(a) Linear regression MSE results.
adult
ACSincome
9x10
Public
DD-SSP
80-1
AUC
AIM-Synth
DP-SGD
8x 10
ObjPert
7x
x-4
ACSmobility
ACSemployment
ACSPublicCoverage
-x
9x 10-1
7 10
6x10-
10-1
x.5
10a4
107
10-3
100
5x10
10-1
107
(b) Logistic regression AUC results.
Figure 3: Performance comparison across linear and logistic regression. Standard error bars are computed over 5 trials. For DP-SGD, the shaded region spans the range between an optimistic baseline ignoring hyperparameter tuning cost, and a realistic baseline using advanced composition to account. for this cost (this line is highlighted by star markers). The advanced composition curve starts further to the right the lowest. achievable by DP-SGD in those cases is 0.005.
11

---

Published in Transactions on Machine Learning Research (08/2025)
The performance of AIM-Syuth suggests that estimating problem-specific data-dependent sufficient statistics explains the suitability of AIM synthetic data for machine learning tasks. This implies DD-SSP is effective whenever pairwise marginals are available.
The approximate DD-SSP method for logistic regression constitules a novel DP algorithm alternative to privatized ERM procedures.
5
Future work
We imagine extensions to two sets models. Beyond linear regression, all exponential family distributions, including graphical models like Naive Bayes, have finite sufficient. statistics, and for such models we can devise similar DD-SSP solutions, or tailor synthetic data, by identifying workload that supports the estimation of their sufficient statistics. Additionally, future work can focus on developing approximate loss functions with finite sufficient statistics for broader class of other models, including generalized linear models (GLMs), where our results for logistic regression can be extended to obtain approximate sufficient statistics from k-way marginals by making a k-degree polynomial approximation to the GLM mapping function following the reasoning of [Huggins et al. (2017). This will open the door to novel DD-SSP methods that directly minimize the approximate loss functions, and improve utility by adding privacy noise a data-dependent way, Examples of such extensions are outlined Appendix F Additionally, methods targeting encoded workload Ay (pg.))A Af instead of Pj,k be explored and combined with advanced data-independent mechanisms like the matrix mechanism, potentially leading to new class of encoding-aweer aware SSP methods.
6 Conclusions
We introduce methods for data-dependent sufficient statistic perturbation (DD-SSP). Our methods use privately released marginal tables to solve linear and logistic regression via sufficient statistics. We find that DD-SSP performs better than data-indeppndent SSP on linear regression and objective perturbation for logistic regression, and is competitive with DP-SGD, known to achieve excellent results under fine-tuned hyperparameter setting.
Notably, the approximate DD-SSP logistic regression algorithm is the first DP logistic regression method that allows analysts lo solve logistic regression via a SSP algorithm, directly minimizing the approximate loss function. Additionally, we find that the performance of DD-SSP is almost indistinguishable from that of AIM synthotic data: this suggests that with the appropriate workload, training these machine learning modols on query-based DP synthetic data corresponds to data-dependen SSP.
References
M. Abadi, Chu, I. Goodfellow, H. B. McMahan, Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on compuler and communications security, pages 308-318, 318, 2016.
Amin, M. Joseph, M. Ribero, and S. Vassilvitskii. Easy differentially private linear regression. arXiv preprint ar arXi:2208..0 07355, 2022.
S. Aydore, W. Brown, M. Kearns, Kenthapadi, L. Melis, A. Roth, and A. Siva. Differentially private query release through adaptive projection. In International Conference on Machine Learning, pages 457-467. PMLR, 2021.
Bassily, A. Smith, and A. Thakurta. Private empirical risk minimization: Efficient algorithms and tight bounds. In 2014 IEFE 55th annual symposium on foundations of computer science, pages 464-473. IEEE, 2014.
Becker and R. Kohavi. hutp://dd..orr/102243///
Adult.
UCI
Machine
Learning Repository, 1996.
DOL:
12

---

Published in Transactions on Machine Learning Research (08/2025)
G. Bernstein and D. R. Sheldon. Differentially private bayesian linear regression. Advonces in Newral Information Processing Systems, 32, 2019.
G. Brown, K. Dvijotham, G. Evans, D. Liu, A. Smith, and A. Thakurta. Private gradient descent for linear regression: Tighter error bounds and instance-specifie uncertainty estimation. arXiv preprint 240: 0.t.2422.135994 13531, 2024.
M. Bun and T. Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635-658. Springer, 2016.
K. Chaudhuri and C. Montelconi. Privacy-preserving logistic regression. Advances neural information processing systems, 21, 2008.
K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
C. Dimitrakakis, B. Nelson, Z. Zhang, A. Mitrokotsa, and B. 1. Rubinstein. Differential privacy for bayesian inference through posterior sampling. Journal of machine learning research, 18(11):1-39, 2017.
B. Ding, M. Winslett, J. Han, and Z. Li. Diffcrentially private data cubes: optimizing noise sources and consistency. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of dola, pages 217-228, 2011.
F. Ding, M. Hardt, J. Miller, and L. Schmidt. Retiring adult: New datasets for fair machine learning. Advances in neural information processing systems, 34:6478 6490, 2021.
C. Dwork and A. Smith. Differential privacy for statisties: What we know and what want to learn. Journal of Privacy and Confidentialityy, 122), 2010.
C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265 284. Springer, 2006.
C. Dwork, A. Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3 ((3-4):211-407, 2014.
C. Ferrando, S. Wang, and D. Sheldon. Parametric bootstrap for differentially private confidence intervals. In International Conference on Artificial Intelligence and Statistics, pages 1598-1618, PMLR, 2022.
R. A. Fisher. On the mathematical foundations of thcoretical statistics. Philosophical transactions of the Royal Sociely of London. Series A, containing papers of mathematioul or physical characler, 222(594-004): 309 368, 1922.
J. Foulds, J. Geumlek, M. Welling, and K. Chaudhuri. On the theory and practice of privacy-preserving bayesian data analysis. arXiv preprint arxiv:1603. 172216603.0794 2016.
M. Gaboardi, E. J. G. Arias, J. Hsu, A. Roth, and Z. S. Wu. Dual query: Practical private query release for high dimensional data. In International Conference on Machine Learning, pages 1170-1178. PMLR, 2014.
R. M. Gower and F. Bach. Properties and examples of convexity and smoothness, February 2019. URL https:///goeerrbbrt.ggigg smoothness solution.ppiioo pdf
L. Grégoire, C. Task, I. Slavitt, G. Nicolas, K. Bhagat, D. Streat, and G. Howarth. Sdnist: Benchmark data and evaluation tools for data sythesizers, Dec. 2021.
M. Hardt, K. Ligett, and F. McSherry. A simple and practical algorithm for differentially private data release. Advances in neurol information processing systems, 25, 2012.
M. Hay, V. Rastogi, G. Miklau, and D. Suciu. Boosting the accuracy of differentially-priveer histograms through consistency. Xiv preprint arXin:0904.09. 2009.
13

---

Published in Transactions on Machine Learning Research (08/2025)
J. Huggins, R. P. Adams, and T. Broderick. Pass-glm: polynomial approximate sufficient statistics for scalable bayesian glm inference. Aduances in Neural Information Processing Systems, 30, 2017.
P. Jain and A. Thakurta. Differentially private learning with kernels. In International conference on machine learning, pages 118-126. PMLR, 2013.
J. Jordon, J. Yoon, and M. Van Der Schaar. Pate-gan: Generating synthetic data with differential privacy guarantees. In International conference learning represenlations, 2019.
D. Kifer, A. Smith, and A. Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, pages 25-1. JMLR Workshop and Conference Proceedings, 2012.
T. Kulkarni, J. Jälkö, A. Koskela, S. Kaski, and A. Honkela, Differentially private bayesian inference for generalized lincar models. In International Conference on Machine Learning, pages 5838-5849. PMLR, 2021.
C. and G. Miklau. An adaptive mechanism for accurale query answering under differential privacy. arXiv preprint 170.::1202.3807, 2012.
C. Li, M. Hay, V. Rastogi, G. Miklau, and A. McGregor. Optimizing linear counting queries under differential privacy. In Proceedings of the twenty-ninth ACM SICMOD-SIGACTTSSCARR symposium on Principles of dalabase systems, pages 123 134, 2010.
C. Li, M. Hay, G. Miklau, and Y. Wang. data-and workload-aware algorithm for range queries under differential privacy. Xiv preprint orXin: 10.00265, 2014.
C. Li, G. Miklau, M. Hay, A. McGregor, and V. Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB journal, 24:757- 781, 2015.
T. Liu, G. Vietri, and S. Z. Wu. Iterative methods for private synthetic data: Unifying framework and new methods. Advances in Neural Information Processing Systems, 34:690-702, 2021.
R. McKenna, D. Sheldon, and G. Miklau. Graphical-modeel based estimation and inference for differential privacy. In International Conference on Machine Learning, pages 4435-4444. PMLR, 2019.
R. McKenna, G. Miklau, M. Hay, and A. Machanavajjhala. Hdmm: Optimizing error high- nigh-dimensional statistical queries under differential privacy. arXiv preprint arXiv:2106. 12118, 2021a.
R. McKenna, G. Miklau, and D. Sheldon. Winning the nist contest: A scalable and general approach to diffcrentially private synthetic data. arXiv preprint 211:22008.0478, 2021b.
R. McKenna, B. Mullins, D. Sheldon, and G. Miklau. Aim: An adaptive and itcrative mechanism for differentially private synthetic data. ar preprind arXi::2001 12677, 2022.
F. McSherry and I. Mironov. Differentially private recommender systems: Building privacy into the netflix prize contenders. In Proceedings of the 15th ACM SIGKDD international conference Knowledge discovery and data mining, pages 627-636, 2009.
Papernot and T. Steinke. Hyperparameter tuning with renyi differential privacy. arXiv preprint 0rXiv:2110.03620 2021.
N. Ponomareva, H. Hazimeh, A. Kurakin, Z. Xu, C. Denison, H. B. McMahan, S. Vassilvitskii, S. Chien, and A. G. Thakurta. How to dp-fy ml: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 77:1113 1201, 2023.
W. Qardaji, W. Yang, and N. Li. Priview: practical diffcrentially private release of marginal contingency tables. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pages 1435- 1446, 2014.
14

---

Published in Transactions on Machine Learning Research (08/2025)
D. Ridgeway, M. F. Theofanos, T. W. Manley, and C. Task. Challenge design and lessons learned from the 2018 differential privacy challenges. NTST technical note, 2151, 2021.
L. Rosenblatt, X. Liu, S. Pouyanfar, E. de Leon, A. Desai, and J. Allen. Differentially private synthetic data: Applied evaluations and enhancements. arxiv preprint urXi:2211.0055% 2020.
O. Sheffet. Differentially private ordinary least squares. In International Conference on Machine Learning, pages 3105 3114. PMLR, 2017.
T. Steinke. Composition of differential privacy & privacy amplification by subsampling. ar preprint arXiv:2210.00599 2022.
S. Tang, S. Aydore, M. Kearns, S. Rho, A. Roth, Y. Wang, Y.-X. Wang, and Z. S. Wu. Improved differentially private regression via gradient boosting. In 2024 IEEE Conference Secure and Trustworthy Machine Learning (SaTML), pages 33-56. TEEE, 2024.
G. Vietri, G. Tian, M. Bun, T. Steinke, and S. Wu. New oracle-efficient algorithms for privale synthetic data release. In International Conference on Machine Learning, pages 9765 9774. PMLR, 2020.
G. Vietri, C. Archambeau, S. Aydore, W. Brown, M. Kearns, A. Roth, A. Siva, S. Tang, and Z. S. Wu. Private synthetic data for multitask learning and marginal queries. arXiv preprint arXiv:2209. Nii::2209.07400, 2022.
D. Vu and A. Slavkovie. Differential privacy for clinical trial data: Preliminary evaluations. In 2009 IEEE International Conference on Data Mining Workshops, pages 138-143. IEEE, 2009.
Y.-X. Wang. Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain. ar preprint arXiv: 1803.02596, 2018.
Y.-. Wang, S. Fienberg, and A. Smola. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In International Conference on Machine Learning, pages 2493 2502. PMLR, 2015.
Y. Xiao, L. Xiong, L. Fan, and S. Goryezka. Dpcube: Differentially private histogram release through multidimensional partitioning. arXiv preprint arXiv:1202.588: 2012.
L. Xie, K. Lin, S. Wang, F. Wang, and J. Zhou. Differentially private generative adversarial network. arXiv preprint XrXie:1802.061 06739, 2018.
J. Xu, Z. Zhang, X. Xiao, Yang, G. Yu, and M. Winslett. Differentially private histogram publication. The VLDB journal, 22:797-822, 2013.
G. Yaroslavtsev, G. Cormode, C. M. Procopiuc, and D. Srivastava. Accurate and efficient private release of datacubes and contingency tables. In 2013 IEEE 29th International Conference on Data Engineering (ICDE), pages 745 756. IEEE, 2013.
J. Zhang, G. Cormode, C. M. Procopiue, D. Srivastava, and X. Xiao. Privbayes: Private data release via bayesian networks. ACM Transactions on Database Systems (TODS), 42(4):1-41, 2017.
X. Zhang, R. Chen, J. Xu, X. Meng, and Y. Xie. Towards accurate histogram publication under differential privacy. In Proceedings of the 2014 STAM international conference on data måningg, pages 587-595. STAM, 2014.
7. Zhang, B. Rubinstein, and C. Dimitrakakis. On the differential privacy of bayesian inference. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30,1, 2016.
15

---

Published in Transactions on Machine Learning Research (08/2025)
Appendix
A AIM
For AIM, we follow the original algorithm McKenna al. (2022). AIM uses an intelligent initialization step estimate one-way marginals. This results in model where all one-way marginals are preserved well, and higher-order marginals can be estimated under independence assumption. Additionally, AIM uses carefully chosen subset of the marginal queries and leverages the observation that lower-dimensional marginals exhibit a better dignal-o-noise ratio than marginals with many attributes and low counts, and at marginal queries in the workload. Finally, the
the same time they can be used to estimate quality score function for selecting marginals to mcasure ensures that the selection is "budget-adaptive" i.c. it measures larger dimensional marginals only when the available privacy budget is large enough.
Algorithm AIM McKKnnn al. 2022)
Input: Dataset D, workload W, privacy paramcter p
Output: Synthetic Dataset D
ParameParamtters: MAX-SIZE=8OMB, T 16d, 0.9
d0 vT/(2ap)
5: Pused =
6: 1=0
7: Initialize Pe (using Amgorithm
w, = E.ew C, rrss
0++1 60 6++1 - / 881 a/p/T
10: while Pused < p do
11:
t=t+1
12:
Pused t Pased + g 207
13: G =T= E W+
Prenttionrre-SIIE(n....
Puxed MAX-SIZE
14: sclect rt E C2 using the exponential mechanism with:
gr (D) = wr W,IM - M,, - 22/T m/ of m.
15: measure marginal on Tz:
Ú = M,, + (N(000))
16: estimate data distribution using Private-PGM:
D. arg min PES
|M, (p) -
17: anneal 6411 and det1 using Algorithm
18: end while
19: generate synthetic data D from P. using Private-PGM
20: return D
16

---

Published in Transactions on Machine Learning Research (08/2025)
Algorithm Initialize Pt (Subroutine of Algorithm for fr W+ |r] 1) do
(McKenna et al. 2022
++1+1
0+t00
Trtr
5: Ve - M,(D) + +N100
6: Pused + Pused + 2
end for
argminpes Ei=1 ai || (p) 0z
Algorithm Budget Annealing (Subroutine of Algorithm
(MeKenna et al. 2022
if (f,) Mr, (Pr-1))l $ V 2 og ny, then
2: 6x+1 t- ce
3: Ø+1 t 01/2
4: else
c++1 t Et
a++1 at
end if
8: if (p- Pusedl 5 20141
(et+1) then
61+1 - V8 (1a))
aa). (p Pused)
10: Ø++1 V 2-c-(p-Prued
end if
B Encoding example
The following example demonstrates the application of the encoding strategy in 3.1 The mapping is:
Xj (xt)
For concrete example, suppose there are 5 levels (i.e., mÚ = 5) and the feature value is X; = 3, then the one-hot encoding vector
0
(G,)
1
0
0
For the numerical encoding A₂ of. For example, suppose of 21,2,4,8, then in our example we have
0
X1 + o = (1,2,,,,
=
0
It easy to see that the numerical value is always equal to my [yys i.., value vector vy index Xy- In other words, the vector by enumerates the numerical values for each level. For the one-hot encoding case, we use A₁ Ijs the identity matrix. In our example, this gives
Xi + Im, km,bs(x)) b(6))=
17

---

Published in Transactions on Machine Learning Research (08/2025)
It is clear that this gives the one-hot encoding. The reduced one-hot encoding is similar.
C Logistic Regression log-likelihood approximation
Proof. The log-likelihood for logistic regression be expressed
(()) Σ p(r()) (1) 1=1
where <(s) = - log(1 + +e*). Based on Huggins et al. (017), we can approximate the logistic regression log-likelihood with Chebyshev polynomial approximation of degree M:
M Σ
((s) = @ar(s)
bm
(M)
===
where b( are constants. Then,
M
((0) 2
(M) (M (x()) mmm
m
i=1 m=0
If we choose M = 2,
{(0)
00
(2) b1 (1. 0g (0.0)
The quadratic term is
d
10 By
16 0,0
Σ
0,0g
(8)
(1) (
Ik
j.k=1
jk=1
Therefore we can rewrite the approximate log-likelihood as
{(0) Rs (2) + +b(2) ()
r
+ 62
0,0 Σ y
1=1
j,k=1
d
= nb
+ 1 (2) X8
b2
8 0
I
nb
(2) + b T x0
b2
0T
x
where the simplification in the second line follows from the fact that work with o E (1,-1) and y0)² for any i.
After moving constants, an equivalent objective for maximization w.r.t. 0 is:
ē(0) x x + 8 x + const.
(
For comparison, the finerr-rerosssion log- likelihood under Gaussian noise model is:
1 x x + 8T XT y + const.
fiuear (0)
18

---

Published in Transactions on Machine Learning Research (08/2025)
It be shown that the Chebyshev coeflicients for ((s) satisfy 61²) concave and quadratic, with terms having the same signs, and the only difference being the relative weighting of the quadratic and linear terms. A simple derivation (set the gradient of to zero and solve for assuming
and b3²) 0, both functions are
x is invertible) shows that {(0) has the following minimizer, which is positive rescaling of the OLS solution:
( xx
Jchcb = 2 2
The sufficient statistics X and X can be derived following the same proposed strategics lincar regression (Section 3.20, obtaining marginal query-based estimates X and X We can then express the closed-form solution of the approximate log-likelihood with approximate sufficient statistics
)(2)
0 DP-cheb
(X*X)-
262 (2)
Figure shows the distribution of the inner DP products for the datascts used in the experiments, supporting the choice of [-6, 6] for the range of the Chebyshev approximation.
adult
ACSincome
ACSmobility
3000
2500
1500
2500
Frequency
2000
1500
1500
1000
1000
1000
500
500
Inner Product Values
Inner Product Values
Inner Product Values
ACSemployment
ACSPublicCoverage
3000
Prequency
1300
2000
500
1000
-5
Inner Product Values
Inner Product Values
Figure 4: Distribution of the inner DP products (y ODp) for the datasets of interest. Opp is computed
using the objective perturbation method with e = 1 and 8 10 10 The dashed vertical lines represenent the [-6, bounds chosen for the Chebyshev approximation.
19

---

Published in Transactions on Machine Learning Research (08/2025)
D Linear regression baseline
Algorithm 5 outlines the AdaSSP method for linear regression
(Wang 2018
Algorithm AdaSSP (Wang) 2018
1: Input: Data X, y. Privacy budget: 6. Bounds: || |D (0, 1) (0.05 in the paper)
2: 1. Calculate the minimum eigenvalue Amiin (x*x).
3: 2. Privately release Amin max Amin c/3
/lg(6/6))
12
log(6/8) c/3
| P.... where Z Z~ ~~0(0.
4: 3. Set == max fo, /dlog(6/6) loglgg/ 1og(22
Xmin
c/3
5: 4. Privately release x = X"X /1og16/8)111111
Z for Z E Iddd is a symmetric matrix and every element from the upper triangular matrix is sampled from (O, 1).
e/3
v /1og(//8||x]|111 for Z N (0, Ia).
6: 5. Privately release XTy = x y +
c/3
7: Output: = (XTX+N) yTy.
To reason about the scnsitivity of X consider two neighboring datascts X Rexd and X R(++ljxd differing by one data entry E X, where is a d 1 vector. Then,
AxTx = -uPxxxx (lxxx))l(((()))) - f(X)IFF
Since X and X' only differ by one row (v), then f(X') - s(X) vv Sheffet 2017 the sensitivity is maximum over v ||vec(ve")) ||| = 1100 || We have
4
sup |
vEX
sup v
(2
d Σ
?
Σ
sup e
sup
||/||2
v
||
where ||||||| is the greatest possible norm of a vector in the domain X. Therefore,
A |
The sensitivity of XT, y can be similarly derived. Given neighboring datasets X E Raxd, y R" and X' e 1)x-d)xd yf Ba++1, where X Rdd is the new row, and ) c R is the new value in y'. Then,
(x v/)
xFyll yll = ||we||
Since ||||| = supxex ||ж||| and || = supyey 181, we have
Axt, = sup If 3/) f(x. x)ll
(Xa))(X(a))
sup |w| ||a|||
||
||
wEY.EE
20

---

| Published in Transactions on Machine Learning Research (08/2025)
E Logistic regression baseline
Our DP logistic regression baseline is based on the generalized objective perturbation algorithm in Kifer et al. (2012) (Algorithm (). In this scction, to match the notation in Kifer et al. (2012). (6; 2) = log 1og(1+cxpp cepp 1xxpp=xx-00) -x-8x)-)))))))))) By))
is the loss for a single datum and É(0; = n E [(0; (() is the average loss over the dataset.
Algorithm Generalized Objective Perturbation Mechanism (ObjPert) (Kiler el al. 2012)
Require:
dataset D {=(1)... ,...., ).)) where 2(0) (x11), ,y(),, privacy parameters and ō (6 0 for c-differential privacy), bound || on the Lę norm of any x entry, convex regularizer r, convex domain
IF S R4, convex loss function L(0; D) + Ei= 8 (0; z()), with continuous Hessian, [[ve(0;=) =) S ||]]] (for all and for all 0 F). |
(for all E D and 0 IF), and the eigenvalues of v²e(0; z) bounded by 4
Set A 2
2x
Sample b E nd from (2(6; e, 6, |[]1] /V (0. (1 La
3: ÖDp = arg minger ((0; + (0) 10112 b-
The algorithm requires the following bounds for the gradient and Hessian of
[[V((0;)) - |||
Amax [(((2=2) < |
To reason about the sensitivity bounds, let d(s) = log(1 + e*). Then we can write E(0;2) = 6(-x -0y) Following Gower and Bach (2019), is straightforward to derive that
ex
(s(s)
1 S
1
d"(s) (1 + e5)z
ed)2
4
and clear that both quantities are non-negative. Then the gradient of é is:
The norm is bounded v((0;2) = veo(-I 0y) = d'(-x: 0y) - yx
[=(00=)]|=
0y)l lyl ||ج||| s ||
where the inequality holds since (0'(s) < for all and lyl
By differentiating the gradient again and using the fact that y² = we can derive the Hessian as:
v²((0==) = (-x 0y))x""
The maximum eigenvalue is
Amax (V2((0:2)) (-x (ry))max((xx) = 6-x |x
|
4
In the second line, we used the fact that Amax(xx))) ||0||| To see this, note that xx rank one and (axT)x || therefore an eigenvector with eigenvalue || and this is the largest eigenvalue. In the last line we used that [[Ø"(s)]] < 1/2 for all and that ||a||| < ||
21

---

Published in Transactions on Machine Learning Research (08/2025)
F Examples of Extensions to GLMs and Higher-Order Approximations
F.1 Degree-k Polynomials from k-way Marginals
In this Section, we show that in general loss function approximated by degree-k polynomial can be computed from the set of all k-way marginals.
Consider a loss function (()) -i= o(x10,0) where ((x, 0) is degree-three polynomial in æ. By breaking the polynomial into monomials, the loss function can be broken into sum of terms, generic one of which is Σ C. -. x0""""= x for some constant C and indices a, b, into the encoded feature vector. Recall that encoded features arise from linear transformations of one-hot encoded attributes via the mappings Xj + Ax))(Xi)) Suppose features Ta, Tb, Te come from attributes Xj, X&, Xe, respectively. Then there are constant vectors E R E R W E R (each a row of Aj, As, Ar, respectively) such that
Ia = {5((ss)
= v T (x(a))
Te w To (e(e))
We can now rewrite the term from the loss function (ignoring the constant) as
(u T (5((xz ()) (v (x(xx")) Tee(x()))
a
1=1
1x ( =r) r1 ) m2
( 11 ( =sl =3)
me
we wx
(
=t]
Mh
ma
U ur,,Wr 50) M| (1) s]U[x (0)
my
Uy Wt Σ Exe (0) r, -r, 8, Xi
(0) 10)
my my ΣΣΣ
ur we (p5,k,))ss
(w@v@w, (1),),))
In the second-to-last line, we introduced the notation (uj,a,e E Xmm for the array containing the three-dimensional data marginal, with entries
(1g.t)rss = Σ TX (1) =r, =r, = x, =
2=1
In the last line, we rewrote the sum an inner product between the constant tensor & w, derived from the feature encoding, and the marginal (ug,kee), to emphasize the general form of the operation. More generally, loss function term that depends at most k features, like degree-k monomial, can be rewritten as tensor inner product between a constant tensor and k-way marginal. Thus, if the overall loss function is a degree-k polynomial, it can be computed from the set of all k-way marginals.
F.2 Poisson Regression (Degree-2 2 Chebyshev Approximation, Log-Link)
Consider a Poisson GLM with canonical log-link function:
(+) () (1), (7()) (og(((()) (1) 0.
22

---

Published in Transactions on Machine Learning Research (08/2025)
The standard Poisson regression log- eigllikelhhood is:
{(0)
y (z(()) -) -0g
Ignoring the constant term l0 (which does not depend on 0), we have:
((0) ( (z. 0) (00
If we approximate the exponential function e" using a second degree Chebyshev polynomial approximation around chosen interval (c.g- [-6,6) as
+ c -22 (2)
(2)
where - , are Chebyshev polynomial coofficients determined numerically, then, substituting this approximation into the Poisson log- likeikeeliood gives:
(()) Rd
y (x(0 0) - - +c (x (2-()))))))))) 0) + 02 (z(0 0}
(2)
Expanding explicitly and simplifying, obtain:
{(0) = (x" y) 1 (x=00000x0(((xx)X))
where X X y, and 1s X can be computed from all pairwise marginals (see Section F.1
F.3 Logistic Regression (Degree-4 Chebyshev Approximation)
The logistic regression log- likellhooho (with labels (()) (1,,1)) is:
log [ + -00-000)))))
(()) log 11e-
1=1
We approximate the logistic function ((s) = - log(1 + +e using degree-4 Chebyshev polynomial:
((8) ~
(4)) sm
m==
where the constants ( are determined numerically by fitting Chebyshev polynomials over chosen interval (e.g. [-6,6]. Substituting this approximation into the log-likelihood, we obtain:
ε(0) bm (2l0)) (gy"))))))))
1=1 m=0
Expanding explicitly, this yields:
?(() bon + b, (xT)) by0 (XTX) + by Σ (8T x 00) ba (T (0).
The required sufficient statistics are TT y, from 4-way marginals (see Section F.1
n (1) (z()) and Σn= (x(1))84 These can be computod X
23

---

Published in Transactions on Machine Learning Research (08/2025)
Note that measuring higher-order marginals under differential privacy poses both computational and statistical challenges. From computational standpoint, the domain size of marginal grows exponentially with its order, making both private measurement and post-processing increasingly expensive. Statistically, higher-order marginals tend to suffer from lower signal-to-noise ratios, as the added noise (due to higher sensitivity and larger out put space) can overwhelm the utility of the measurement. As noted in the AIM paper (McKenna) ct al. 2022), lower-order marginals often provide better trade-off, and can still be leveraged estimate higher-order interactions via structured inference methods, such graphical models.
G Experiment details
G.1 Datasets and Preprocessing
We the following datasets
The target variable 'num-education' (numberr of education years) for linear regression and 'incom>>50K" for logistic regression.
Adult (Becker and Kohavi 1996):
Fire RRiggeway et al.
2021
The target variable is 'Priority' (of the call).
Taxi Grégoire et al.
2021
The target variable is 'totalamount (total fare amount).
ACS Datasets Ding et al. 2021 Data is queried for California (2018). Includes binary classification tasks for 'PINCP" (income above $50k), 'MI' (mobility), 'ESR' (employment), and 'PUBCOV' (public coverage). ACSincome is also used for linear regression with the target variable 'PINCP"
(income) discretized into 20 bins.
More detail on the datasets is included in Table Data is shuffled and split into 1,000 test points and up to 50,000 training points. Non-mumerical features one-hot encoded, dropping the first level to avoid multi-collinearity, and numerical features are rescaled to [-1,1] for noise allocation (see Section 3.1 for more detail on data encoding).
G.2 Methodology
AIM training: AIM is trained with model size of 200MB, a maximum of 1,000 iterations, and a workload of all pairwise marginals. For AdaSSP, sensitivity is calibrated described in Sections 3.1 and 3.6
DP-SGD fine tuning and training: DP-SGD's hyperparameters are fine-tuned by running gridsearch for the best parameter. The search space spans the following values:
Batch size: (n. 1024, 256]
Gradient clipping norm: (0.01,0.1,00)
Number or epochs: [1, 10, 20]
Learning rate: [0.001, 0.01, 0.1,
Advanced composition is used to account for hyperparameter tuning costs as per Theorem 22 in Steinke The optimistic baseline ignores this cost entiroly.
2022
TTh ACS data is sourced from http://p/./...ti.acaacaaaaaaaata Sttps://githhn http://gthhuu.cccoaaatttaa con/ryan112358//tt -
other datasets sourced from
24

---

Published in Transactions on Machine Learning Research (08/2025)
Table 1: Dataset information
Dataset
Size
#
At-
Attributes
Target
tributes
Adult
48,842
15
lage', 'workelass', 'fnlwgt', 'educa- Cincom>55KK tion', 'marital-status' 'occupation', 'relationship', 'race', 'sex', 'capital- gain', 'capital-loss', thours-per-werr 'native-country', 'income>50K"; 'education-num"
(logistic),
edducation-
num' (linear)
ACSIncome
195,665
9
['AGEP', 'COW" 'SCHL', 'MAR; 'RELP", 'WKHP', 'SEX, 'RACIP' 'PINCP"
PINCPP'
Fire
305,119
15
[ALS Unit', 'Battalion', CCall Fi- nal Disposition', 'Call Type', 'Call Type Group', 'City', 'Final Priority', 'Fire Prevention District', 'Neigh- borhooods Analysis Boundaries', OOiginal Priority', 'Station Area', 'Supervisor District', 'Unit Type', "Zipcode of Incident', 'Priority"]
'Priority'
Taxi
1,048,575
11
|VendorlDD, "passengercount' 'totalamount"
tripdistance', 'RatecodelD', PUU- LocationID', 'DOLocationID's 'pay- menttype', 'farcamoun'', 'tipamount', 'tolsamount', 'totalamount"
ACSmobility
29,358
20
FAGEP" 'SCHL', 'MAR', 'SEX DIS' 'CIT', 'MIL', 'ANC', WKKP. NATIVITY' 'RELP' DDEAR' DEYE', 'REMM, 'RACIP, 'GCL' COW", 'ESR' 'WMNPP' PINCP" AGEP,, 'SCHL', 'AR', 'ELPP' DIS' 'ESP, 'CIT, 'MI', 'MIL' ANC", 'NATIVITY', DDEAR, DEYE', DREMM, 'SEX, 'RACIP" ESR"
'MG'
ACSEmployment
378,817
17
'ESR'
ACSPublicCoverage
138,550
19
FAGEP', SCHL' 'MAR. SEX', DIS, 'ESP' 'CIT' 'MIG, 'MIL' 'ANC. 'NATIVITY,, 'DEAR' DEYE', 'DEMM, PINCP", ESR'. FER,, 'RACIP, *PUBCOV]
PUBCOV
25

---

Published in Transactions on Machine Learning Research (08/2025)
G.3 Computational runtime
All experiments were conducted an internal cluster equipped with Xeon Gold 6240 CPUs @ 2.60GHZ, 192GB RAM, and 240GB local SSD storage. The runtime of our method is influenced by several factors, including datasct size, domain size, and the privacy paramcter c. Since our method relies on private marginals released by AIM, its runtime is inherently tied to AIM's computational demands, which are significantly higher than those of the DP baselines.
For clarity, focus the detailed runtime analysis on the Adult dataset it is representative of general trends observed across all datasets. On this dataset, AIM runtime increases significantly with c. For linear regression, AIM requires approximately 8 minutes at = 0.05, scaling up to 18 hours at 2.0. In comparison, the DP baseline AdaSSP completes the same experiment in approximately 5 seconds regardless of Similar trends are observed for logistic regression, with AIM runtime increasing from 12 minutes to 21 hours as grows, while the corresponding DP baseline ObjPert completes these experiments approximately 2 seconds.
For DP-SGD, the runtime of the hyperparameter search phase varies across datasets, tasks and between around hour and 17 hours; once the best. hyperparameters have been determined, the runtime of DP-SGD, taking the case of linear regression the Adult dataset as example, varies between 2 minutes for 0.05 and 10 minutes for c = 2.0.
G.4 Runtime mitigation strategies
While AIM's runtime is substantial, it is direct consequence of the complexity involved in accurately computing privale marginals for large domains and high utility. A few factors miligale the runtime of the proposed methods: i) AIM is much faster for low e values; ii) AIM model size can be reduced to 100MB for a significant runtime cut, without significantly sacrificing the accuracy of the method. In the context of this paper, we choose to prioritize accuracy, which is consistent with the motivation of synthetic data, where computation is spent up front to release a data set that can be used downstreams many ways; iii) other faster query answering mechanisms can be used in place of AIM, such as MST (see 3.5p which runs in approximately 18 minutes for full experiment across all values Adult. Various ways improve the accuracy running-time trade-offs for use in specific settings can be explored, which is beyond the scope of this paper. In terms of experimentation (sec Scction 4 for computational viability we study the variability of our results across 5 trials.
26

---

Published in Transactions on Machine Learning Research (08/2025)
H Additional experiments
DD-SSP can accommodate different DP marginal query releasing methods. For our main results we use AIM (see Appendix which uses Private-PGM (McKenna et al. 2019) for the "generate" step. In this section, we briefly demonstrate the use of the DD-SSP framework with alternative methods. In particular, we consider two alternative settings: i) replacing AIM with MST (McKenna et al. 2021b); ii) replacing the Private-PGM close approximation of the relaxed projection methods in (Aydore 2021 and (Liu et. al. 2021 Results shown in Figure and Figure respectively.
step in AIM with MixtureInference
al.
From the ablation studies in (McKenna et al., 2022 privacy) and AIM to outperform it at higher values. MST performs a domain compression operation, and we hypothesize this benefits some cases (e.g. low e), but hurts in others. Based on the same ablation studies, we expect Private-PGM to yicld lower workload errors with respect to overall metric scores for the tasks of interest. Consistently with the findings in (McKenna el al, 2022 we find that AIM using Private-PGM has the most reliable performance overall.
expect MST to perform well at low values (high
resulting in better
fre
ACSincome
10"
76
MSE
3x
All--Syrth DO SSP (MST)
NET--lyrhh
CNPPeT
10
10
2x100
10
90
10
10
odult
AC3
ACSmobllly
ACBemoloyment
ACBPudleeCoverape
7x
6x100
AUD
7x110
7.5x
7.4x10
6x100
10"
10"
10"
10"
10
10"
2021b vs. AIM (McKenna et al. 2022 as a query answering algorithm. Top: linear regression. Bottom: logistic regression, Standard error bars are computed over 5 trials.
Figure 5: MST (McKenna
27

---

Published in Transactions on Machine Learning Research (08/2025)
ACSincome
10
16"
4x100"
Pittic
D0-S6P
KISE
10"
10"
All-Symt
DO-SBP (Mat)
Mod-Syrth
10"
10"
2x 1x
10
10
10"
ACSncamm
ACSmmbilly
ACBenclaymert
ACSPPudisCCwwrrpp
8x10"
AMC
8x10"
7x:10
7,4x10
6x100
10"
70"
10"
10"
10"
Figure AIM using MixtureInference (Aydore al. 2021 Liu et al. et al. 2019) for model estimation and synthetic data generation. Top: linear regression. Bottom: logistic regression, Standard error bars computer over 5 trials.
2021 vs. Private-PGM MMcKenna
28


Reviews:
[{"review_id": "tPTwQwy5BQ", "reviewer": "Reviewer_1Mct", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The authors demonstrate that the data-dependent SSP (DD-SSP) outperforms the data-independent SSP (DI-SSP). This result is **intuitive** since having knowledge of the data distribution generally enables better design of differential privacy mechanisms. However, the authors should clarify under what specific assumptions or types of data distributions their proposed method achieves significant improvements.\n\n2. The current paper seems focus on discrete data, which entails encoding for numericalization. What if the dataset contains numerical and ordinal data? The current method seems restricted to categorical data.\n\n\n3. The authors employ polynomial approximation for logistic regression. Naturally, it can be also extended to generalized linear models. The authors should add some discussions on this for increasing the contributions of this paper.\n\n4. The current paper fails to compare DI-SSP and DD-SSP in details. At least, I do not see how the proposed method differ in DI-SSP. The authors should prepare an additional section for highlighting the difference.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a **data-dependent Sufficient Statistic Perturbation** (DD-SSP) for differentially private linear regression by post-processing privately released marginals, achieving improved accuracy over traditional data-independent SSP. A key extension is logistic regression by designing an approximate objective expressible via sufficient statistics, leading to a novel and competitive SSP method. Furthermore, this paper also establishes a connection between SSP and synthetic data generation, showing that for models with sufficient statistics, training on synthetic data corresponds to data-dependent SSP, with utility determined by the accuracy of answering associated linear queries.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Some citation formats in the paper are improperly placed. For instance, on Page 2, the phrase “AIM McKenna et al. (2022)” should be formatted as “AIM (McKenna et al., 2022).” The authors are encouraged to review the entire manuscript to ensure citation style consistency throughout.\n\n2. The full name of AIM is not provided in the paper. It would improve clarity to define this acronym upon its first use. \n\n3. In Figure 3, it should be (left) and (right) instead of (top) and (bottom). The M in Figure 1 is also confusion. It would be better to provide its definition since DP marginals can mean a lot of things.\n\n4. The details of AIM should be given in the main text for enhancing clarity.\n\n5 On page 8, the reference seems wrong. There is no Figure 2.1 in this paper.", "broader_impact_concerns": "no", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eRZIRaemfG", "reviewer": "Reviewer_YXx9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths :\n\n- Despite the approach essentially consisting in combining existing blocks, I like its generality. \n- The authors compare DD-SSP against strong baselines (AdaSSP, ObjPert, DP-SGD) across multiple datasets, providing robust evidence of its performance.\n- The framework’s flexibility to accommodate different query-answering algorithms and its potential extension to other models (e.g., exponential family distributions) suggest a strong and easy applicability in practice.\n\nWeaknesses :\n\n- The writing could be more concise and clear. The introduction of synthetic data generation early in the paper feels tangential to the main focus on regression, potentially confusing readers about the paper’s primary contribution. If I understand correctly, the general idea that the authors are trying to convey is that from a private data generator or private information of the data distribution, it should be possible to solve many downstream tasks by post-processing. However, as it is currently stated in the article, one might understand that the  \n- The notations are often overly intricate, which may hinder accessibility. Simplifying mathematical expressions and definitions could improve readability.\n- The plots are difficult to interpret due to overlapping curves, particularly for DP-SGD, and the absence of ObjPert in some logistic regression plots is not explained.\n- The choice of a degree-2 Chebyshev approximation for logistic regression leads to an optimization problem resembling a quadratic form, but the authors do not discuss its implications, such as the relationship to linear regression solutions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission introduces a novel data-dependent sufficient statistic perturbation (DD-SSP) method for differentially private linear and logistic regression. Unlike traditional data-independent SSP, DD-SSP leverages privately released marginals to estimate sufficient statistics, achieving improved utility for linear regression compared to state-of-the-art baselines like AdaSSP. For logistic regression, the authors propose a Chebyshev polynomial approximation to derive approximate sufficient statistics, enabling a competitive SSP-based approach. Experimental results demonstrate that DD-SSP outperforms AdaSSP for linear regression and is competitive with objective perturbation and DP-SGD for logistic regression, particularly in low-$\\epsilon$ regimes.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Mandatory changes :\n\n- Clarify the relation with data generation and how you problem articulates around it.\n- Explain the relations (if any) between the solution of the degree-2 Chebyshev approximation for logistic regression and the solution of the ordinary least-squares problem.\n\nMinor problems :\n\n- Definition 2.4 should be a Definition-Proposition\n- Definition 2.5 should be a Proposition", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cjditTmkAH", "reviewer": "Reviewer_jNnR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The framework is easy to extend in terms of query answering scheme.\n- The motivation and logical flow are clear and well explained. The idea of using queries to approximate sufficient statistics seems quite intuitive.\n- The experimental results show consistent improvements over existing methods.\n\nWeaknesses:\n\n- No utility analysis is provided. \n- The current analysis only covers simple models of linear regression and logistic regression, and there is no evident generalization towards more complex model. Based on the polynomial approximation, it appears that high-order polynomials may sometimes be necessary for other machine learning problems. I suggest that the authors add a comment regarding the challenges of approximating high-order polynomials using linear queries.\n- Some relevant literature, such as [1,2,3], which proposes tailored solutions for differentially private linear regression, is missing.\n- In the experiments, the method ObjPert uses $\\delta=0$, which is in fact not a fair comparison and should be stated clearly. \n\n\n[1] Amin K, Joseph M, Ribero M, et al. Easy Differentially Private Linear Regression[C], The Eleventh International Conference on Learning Representations.\n\n[2] Tang, S., Aydore, S., Kearns, M., Rho, S., Roth, A., Wang, Y., ... & Wu, Z. S. (2024, April). Improved differentially private regression via gradient boosting. In 2024 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) (pp. 33-56). IEEE.\n\n[3] Brown, G., Dvijotham, K., Evans, G., Liu, D., Smith, A., & Thakurta, A. (2024). Private gradient descent for linear regression: Tighter error bounds and instance-specific uncertainty estimation. arXiv preprint arXiv:2402.13531.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces Data-Dependent Sufficient Statistic Perturbation (DD-SSP), a new framework for differentially private regression analysis. It departs from traditional data-independent sufficient statistic perturbation (SSP) methods by leveraging private, data-dependent linear query answering to estimate sufficient statistics more accurately. Algorithms for both linear regression and logistic regression is derived. Experiments show that DD-SSP outperforms existing SSP methods and is competitive with fine-tuned DP-SGD baselines, particularly when accounting for the privacy cost of hyperparameter tuning. Also, the proposed framework is extentive to other models with either exact or approximate sufficient statistics.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Could the authors provide a utility analysis or at least evidence supporting why the proposed query answering scheme is superior to previous approaches? A privacy-utility trade-off discussion would be valuable.\n- Could the authors comment on the challenges of approximating high-order polynomials using linear queries?\n- Please expand the literature review to include relevant works. Also, is it possible to evaluate it in the experiments?\n- I am curious about the difference between DD-SSP and AIM-Synth in the experimental results. Most of the time, their performances are almost exactly aligned, but there are noticeable gaps on certain datasets. What causes these gaps, given that the authors stated that \"marginal-based synthetic data is designed to preserve the same linear queries that are sufficient to solve linear regression\"? Also, the original AIM-Synth involves a marginal selection step. When DD-SSP and AIM-Synth exhibit similar performance, does this imply that the selection step does not waste any privacy budget?\n\n\nMinor points:\n\n- In the caption of Figure 1, the subfigures are referred to using \"top\" and \"bottom,\" which may be a typo. \n- Please ensure the correct usage of \\cite, \\citep, and \\citet. Note that the formatting of citations may vary depending on the LaTeX template used.\n- There is a typo in the first line of Section 5.", "broader_impact_concerns": "No concerns. This is a theoretical work that may have societal impacts in the future.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)