# Private Regression via Data-Dependent Sufficient Statistic Perturbation

Cecilia Ferrando, Daniel Sheldon

Manning College of Information and Computer Sciences
University of Massachusetts, Amherst
<EMAIL_ADDRESS>

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

##  1 Introduction

Differential privacy (DP) [13] is an established mathematical framework for
protecting user privacy while analyzing sensitive data. A differentially
private algorithm injects calibrated random noise into the data analytic
process to mask the membership of single records in 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 a wide range of machine learning algorithms, including objective
perturbation [7, 8, 26, 24], with applications to models trained via empirical
risk minimization; gradient perturbation [3, 1], which is commonly used in
deep learning and any models learning via gradient descent; one-posterior
sampling (OPS) [9, 49] with applications in private Bayesian inference; and
finally, sufficient statistic perturbation (SSP) [47, 37, 12, 56, 17, 48, 5,
15], with natural applications in exponential family estimation and linear
regression.

SSP adds calibrated random noise to the sufficient statistics of the problem
of interest and uses the noisy sufficient statistics downstream to retrieve
the target estimate. SSP is 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 [16]. For many models, like
linear regression and exponential family distributions, their sensitivity is
easy to quantify or bound, simplifying the DP analysis. Finally, they can be
privatized via simple additive mechanisms, like the Laplace or Gaussian
mechanism [14].

Existing SSP methods are _data-independent_ , meaning they add noise to the
sufficient statistics in a 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 [21, 54, 18, 2, 32, 36]. In this paper, we develop DD-SSP, a
data-dependent SSP method that uses private linear query answering to release
DP sufficient statistics for linear regression. We use AIM [36] as our query
answering algorithm and show experimentally that DD-SSP outperforms the state-
of-the-art data-independent SSP method AdaSSP [48] (for discrete numerical
data, as AIM requires discrete data).

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. Our results show that for logistic regression tasks, DD-SSP achieves
better results than the widely used objective perturbation baseline.

Finally, we 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) [13] 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
algorithmic output in order to safeguard personal privacy.

######  Definition 2.1 (Neighboring datasets).

Two datasets $D$ and $D^{\prime}$ are considered neighbors ($D\sim
D^{\prime}$) if $D^{\prime}$ can be created by adding or deleting a single
record from $D$.

Based on the concept of neighboring datasets, we can define the _sensitivity_
of a function:

######  Definition 2.2 ($L_{2}$ sensitivity).

Given a vector-valued function of the data
$f:\mathcal{D}\rightarrow\mathbb{R}^{p}$, the $L_{2}$ sensitivity of $f$ is
defined as $\Delta(f)=\max_{D\sim
D^{\prime}}\left\|f(D)-f\left(D^{\prime}\right)\right\|_{2}$.

Differential privacy can be achieved via different mechanisms of addition of
calibrated random noise, with slightly different definitions. In this paper,
we adopt $(\epsilon,\delta)$-DP, which can be achieved via the Gaussian
Mechanism.

######  Definition 2.3 ($(\epsilon,\delta)$-Differential Privacy).

A randomized mechanism $\mathcal{M}$ : $\mathcal{D}\rightarrow\mathcal{R}$
satisfies $(\epsilon,\delta)$-differential privacy if for any neighbor
datasets $D\sim D^{\prime}\in\mathcal{D}$, and any subset of possible outputs
$S\subseteq\mathcal{R}$

$\displaystyle\operatorname{Pr}[\mathcal{M}(D)\in
S]\leq\exp(\epsilon)\operatorname{Pr}\left[\mathcal{M}\left(D^{\prime}\right)\in
S\right]+\delta$

######  Definition 2.4 (Gaussian mechanism).

Let $f:\mathcal{D}\rightarrow\mathbb{R}^{p}$ be a vector-valued function of
the input data. The Gaussian mechanism is given by

$\displaystyle\mathcal{M}(D)=f(D)+\nu$

where $\nu$ is random noise drawn from $\mathcal{N}(0,\sigma^{2}I_{p})$ with
variance $\sigma^{2}=2\ln(1.25/\delta)\cdot\Delta(f)^{2}/\epsilon^{2}$ and
$\Delta(f)$ is the $L_{2}$-sensitivity of $f$. That is, the Gaussian mechanism
adds i.i.d. Gaussian noise to each entry of $f(D)$ with scale $\sigma$
dependent on the privacy parameters.

######  Definition 2.5 (Post-processing property of DP).

[14] If $\mathcal{M}(D)$ is $(\epsilon,\delta)$-DP, then for any deterministic
or randomized function $g$, $g(\mathcal{M}(D))$ satisfies
$(\epsilon,\delta)$-DP.

###  2.2 Differentially private synthetic data

One of the most appealing applications of differential privacy is the creation
of synthetic data, which is designed to be representative of the original data
while maintaining privacy [21, 54, 51, 25, 33, 42, 45, 32, 2, 35, 46, 36]. In
this line of work, instead of perturbing the data or data analytic process, a
model capturing the data distribution is estimated and used to sample new
surrogate data, which can be safely used for the analytic tasks of interest.
Research on differentially private synthetic data is ongoing, and two
dedicated competitions have been hosted by the U.S. National Institute of
Standards and Technology (NIST) [38, 39], propelling advances in this area.
Private synthetic data has many advantages, including fitting into existing
data processing workflows and enabling users to answer multiple queries while
maintaining privacy. Depending on the characteristics of the data captured in
generative mechanism, the resulting synthetic data will be accurate
specifically for tasks where those characteristics are relevant.

The key goal is therefore to tailor synthetic data to perform well on select
classes of queries (workload) that are relevant to the problem of interest.
The subject of generative synthetic data for machine learning tasks has
recently gained traction in the literature [44, 57], with the focus so far
limited to benchmarking different synthetic data methods and bounding the
empirical error it incurs when used for training machine learning models.
However, an end-to-end analysis of the characteristics that make DP synthetic
data suitable for machine learning tasks is needed. The following definitions
allow us to formally elaborate on differentially private synthetic data.

######  Definition 2.6 (Dataset).

A dataset $D$ is defined as a collection of $n$ potentially sensitive records.
Each record $\chi^{(i)}\in D$ is a $d$-dimensional vector
$(\chi^{(i)}_{1},\ldots,\chi^{(i)}_{d})$.

######  Definition 2.7 (Domain).

The domain of possible values for attribute $\chi^{(i)}_{j}$ is
$\Omega_{j}=\\{1,\ldots,m_{j}\\}$. The full domain of possible values for
$\chi^{(i)}$ is thus $\Omega=\Omega_{1}\times\cdots\times\Omega_{d}$ which has
size $\prod_{j}m_{j}=m$.

We will later talk about numerical encodings of attributes (Section 3.1).

######  Definition 2.8 (Marginals).

Let $r\subseteq[d]$ be a subset of features, $\Omega_{r}=\prod_{j\in
r}\Omega_{j},m_{r}=\left|\Omega_{r}\right|$, and
$\chi_{r}=\left(\chi_{j}\right)_{j\in r}$. The marginal on $r$ is a vector
$\mu_{r}\in\mathbb{R}^{m_{r}}$ indexed by domain elements $t\in\Omega_{r}$
such that each entry is $\mu_{r}[t]=\sum_{\chi\in
D}\mathds{1}\left[\chi_{r}=t\right]$ (i.e., counts).

With marginal queries, one record can only contribute a count of one to a
single cell of the output vector. For this reason, the $L_{2}$ sensitivity of
a marginal query $M_{r}$ is 1, regardless of the attributes in $r$. This
facilitates the differential privacy analysis for marginal queries.

######  Definition 2.9 (Workload).

A marginal workload $W$ is defined as a set of marginal queries
$r_{1},\ldots,r_{K}$ where $r_{k}\subseteq[d]$.

The goal of workload-based synthetic data generation models to minimize the
approximation error on workload queries.

###  2.3 PrivatePGM and AIM

_Marginal-based_ approaches and _select-measure-reconstruct_ methods have
generally emerged as effective methods for DP linear query answering and
synthetic data generation [22, 29, 10, 50, 28, 52, 53, 30, 40, 55, 31, 34].
The _select-measure-reconstruct_ paradigm operates by selecting a set of
queries to measure using a noise addition mechanism to ensure their privacy.
The noisy measurements can be used to estimate a target set of queries, called
the _workload_. Many differentially private synthetic data generation
strategies use Private-PGM [33] to post-process the noise-perturbed marginals
and generate a synthetic dataset that respects them. Private-PGM can be used
in the context of select-measure-reconstruct paradigms. Among these, AIM [36]
has emerged as state-of-the-art by implementing a few key features. First, AIM
uses an intelligent initialization step to estimate one-way marginals. This
results in a model where all one-way marginals are preserved well, and higher-
order marginals can be estimated under an independence assumption. Second, AIM
uses a carefully chosen subset of the marginal queries and leverages the
observation that lower-dimensional marginals exhibit a better signal-to-noise
ratio than marginals with many attributes and low counts, and at the same time
they can be used to estimate higher-dimensional marginal queries in the
workload. Third, the quality score function for selecting marginals to measure
ensures that the selection is “budget-adaptive”, i.e. it measures larger
dimensional marginals only when the available privacy budget is large enough.
In this work, we use AIM as our query-answering algorithm of choice. Note that
AIM uses zero-concentrated differential privacy (zCDP) [6], an alternative
privacy definition; the Gaussian mechanism as defined in Section 2.1 satisfies
$\frac{1}{2\sigma^{2}}$-zCDP [6]. In our experiments, we work with
$(\epsilon,\delta)$-DP and the conversion to zCDP is handled internally in
AIM.

##  3 Methods

Figure 1: Diagram representing the SSP data-independent workflow (left) vs the
data-dependent linear query answering mechanism for marginal release/synthetic
data workflow (right). Quantities indicated in blue follow privacy noise
injection and are differentially private.

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 a data-dependent linear query answering algorithm (AIM)
to estimate sufficient statistics. We call this set of methods DD-SSP. The
main advantage of DD-SSP is that it is _data-dependent_. Our approach stems
from the insight that, while data-independent noise addition is a simple and
established approach to SSP, many sufficient statistics can be expressed as
linear queries, creating an opportunity to improve utility by using data-
dependent query-answering DP mechanisms, which often achieve higher accuracy
than simple additive noise mechanisms [36]. In fact, using private synthetic
data to train certain 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 a 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 estimation. For other models, 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 [23] allows us to propose an
_approximate_ version of the learning objective based on approximate
sufficient statistics that can be expressed as 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 implementation it to output marginals directly, with
no 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 a _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 all based on post-processing DP
workload query answers, the differential privacy analysis is straightforward
(Definition 2.5).

###  3.1 Numerical encoding

We assume discrete (or discretized) input data, which is a common format for
tabular data and required by AIM and other marginal-based approaches. However,
for machine learning, each record $\chi$ must be mapped to a numerical vector
$z=(x,y)$ where $x\in\mathbb{R}^{p}$ is a feature vector and $y\in\mathbb{R}$
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
$\|x\|$, which is used in sensitivity calculations of a number of DP ML
methods, with tighter bounds leading to higher utility. Second, the encoding
is a key part of recovering sufficient statistics from marginals.

Let $\psi_{j}(\chi_{j})\in\mathbb{R}^{m_{j}}$ be the one-hot encoding of
$\chi_{j}$, i.e., the vector with entries
$\psi_{j,s}(\chi_{j})=\mathbf{1}[\chi_{j}=s]$ for each $s\in\Omega_{j}$. We
consider any numerical encoding of the form $\chi_{j}\mapsto
A_{j}\psi_{j}(\chi_{j})$ where $A_{j}\in\mathbb{R}^{p_{j}\times m_{j}}$ 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_{j}=v_{j}^{T}$ for a vector $v_{j}\in\mathbb{R}^{m_{j}}$ that specifies the
numerical value for each $s\in\Omega_{j}$. In this case the mapping simplifies
to $\chi_{j}\mapsto v_{j}(\chi_{j})$. The second special case of interest is
when $\Phi_{j}=I_{j}$ is the $m_{j}\times m_{j}$ identity matrix, so the
mapping simplifies to $\chi_{j}\mapsto\psi_{j}(\chi_{j})$ to give the one-hot
encoding itself. Another common variation is a reduced one-hot encoding where
$\Phi_{j}=\tilde{I}_{j}\in\mathbb{R}^{(m_{j}-1)\times m_{j}}$ is equal to
$I_{j}$ with one row dropped to avoid redundant information in the one-hot
encoding.

The full encoded record is $z=(z_{[j]})_{j=1}^{d}$ where
$z_{[j]}=A_{j}\psi_{j}(\chi_{j})\in\mathbb{R}^{p_{j}}$ is the encoding of the
$j$th attribute and these column vectors are concatenated vertically. A single
entry of $z$ is selected as the target variable $y$ leaving a feature vector
$x$ of dimension $p:=(\sum_{j=1}^{d}p_{j})-1$. Later, we will also use
indexing expressions like $(\cdot)_{[j]}$ and $(\cdot)_{[j,k]}$ to refer to
blocks of a vector or matrix corresponding to the encoding of the $j$th and
$k$th attributes.

Let $z^{(i)}=(x^{(i)},y^{(i)})$ denote the encoding of record $\chi^{(i)}$ and
let $X\in\mathbb{R}^{n\times p}$ be the matrix with $i$th row equal to
$(x^{(i)})^{T}$ and $y\in\mathbb{R}^{n}$ be the vector with $i$th entry equal
to $y^{(i)}$. Many DP ML methods require bounds on the magnitude of the
encoded data. Let $\|\mathcal{X}\|=\sup_{x\in\mathcal{X}}\|x\|$ and
$\|\mathcal{Y}\|=\sup_{y\in\mathcal{Y}}|y|$ be bounds provided by the user
where $\mathcal{X}\subset\mathbb{R}^{p}$ and $\mathcal{Y}\subset\mathbb{R}$
are guaranteed to contain all possible encoded feature vectors $x$ and target
values $y$, respectively. For example, a typical bound is
$\|\mathcal{X}\|=\|x^{+}\|$ where $x^{+}_{k}\geq\sup|x_{k}|$ bounds the
magnitude of a single feature. If $x_{k}$ is the scalar encoding of $\chi_{j}$
we can take $x_{k}^{+}=\max_{s\in\Omega_{j}}|v_{j}(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\in\mathbb{R}^{a}$ satisfies
$\|u\|\leq\|\mathcal{U}\|$ and $w\in\mathbb{R}^{b}$ contains the one-hot
encodings (either reduced or not reduced) of $c$ attributes. Then
$\|\mathcal{X}\|:=\sqrt{\|\mathcal{U}\|^{2}+c}$ is an upper bound on $\|x\|$.

###### Proof.

$\|x\|^{2}=\|u\|^{2}+\|w\|^{2}\leq\|\mathcal{U}\|^{2}+c$ where $\|w\|^{2}\leq
c$ because $w$ is the concatenation of $c$ vectors each with at most a single
entry of 1 and all other entries equal to 0. ∎

Suppose $u$ consists of scalar features and $\|\mathcal{U}\|$ is obtained by
bounding each one separately as described above. This bound is tighter than
the naive one of $\sqrt{\|\mathcal{U}\|^{2}+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 $X\theta$ in a linear
model with $\theta\in\mathbb{R}^{p}$. The ordinary least squares (OLS)
estimator is obtained by minimizing the squared error loss function
$\|y-X\theta\|^{2}$. Mathematically, the OLS estimator is given by
$\hat{\theta}=(X^{T}X)^{-1}X^{T}y$. In this context, the sufficient statistics
are $T(X,y)=\\{X^{T}X,X^{T}y\\}$. In DD-SSP, we approximate $T(X,y)$ using
linear queries. Specifically, we show that each entry of $X^{T}X$ and $X^{T}y$
can be obtained from pairwise marginals. The sufficient statistics we 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,y]\in\mathbb{R}^{n\times(p+1)}$. The matrix $Z^{T}Z$ has blocks that
contain our sufficient statistics of interest:

$Z^{T}Z=\begin{bmatrix}X^{T}X&X^{T}y\\\ y^{T}X&y^{T}y\end{bmatrix}.$ (1)

However, we will see that we can also construct $Z^{T}Z$ directly from
marginals.

######  Proposition 3.2.

Let $(Z^{T}Z)_{[j,k]}$ be the block of $Z^{T}Z$ with rows corresponding to the
$j$th attribute encoding $z_{[j]}=A_{j}\psi_{j}(\chi_{j})$ and columns
corresponding to the $k$th attribute encoding
$z_{[k]}=A_{j}\psi_{k}(\chi_{k})$. Then

$\displaystyle(Z^{T}Z)_{[j,k]}=A_{j}\langle\mu_{j,k}\rangle A_{k}^{T}$

where $\langle\mu_{j,k}\rangle\in\mathbb{R}^{m_{j}\times m_{k}}$ is the
$(j,k)$-marginal shaped as a matrix with $(s,t)$ entry
$\mu_{j,k}[s,t]=\sum_{i=1}^{n}\mathbf{1}[\chi^{(i)}_{j}=s,\chi^{(i)}_{k}=t]$.
Note that according to this definition
$\langle\mu_{j,j}\rangle=\text{diag}(\mu_{j})$.

This shows that we can reconstruct the sufficient statistic matrix $Z^{T}Z$
directly from the set of all single-attribute and pairwise marginals. Note
that single-attribute marginals $\mu_{j}$ can be constructed from any
$\mu_{j,k}$ with $k\neq j$.

###### Proof.

The sufficient statistic matrix can be written as
$Z^{T}Z=\sum_{i=1}^{n}z^{(i)}(z^{(i)})^{T}$. Indexing by blocks gives

$\displaystyle(Z^{T}Z)_{[j,k]}$
$\displaystyle=\sum_{i=1}^{n}z_{[j]}^{(i)}(z_{[k]}^{(i)})^{T}$
$\displaystyle=\sum_{i=1}^{n}A_{j}\psi_{j}(\chi_{j}^{(i)})\psi_{k}(\chi_{k}^{(i)})^{T}A_{k}^{T}$
$\displaystyle=A_{j}\Big{(}\sum_{i=1}^{n}\psi_{j}(\chi_{j}^{(i)})\psi_{k}(\chi_{k}^{(i)})^{T}\Big{)}A_{k}^{T}$
$\displaystyle=A_{j}\langle\mu_{j,k}\rangle A_{k}^{T},$

In the last line, we used that
$\psi_{j}(\chi_{j}^{(i)})\psi_{k}(\chi_{k}^{(i)})^{T}$ is a matrix with
$(s,t)$ entry equal to $\mathbf{1}[\chi_{j}^{(i)}=s,\chi_{k}^{(i)}=t]$, so
summing over all $i$ gives the matrix $\langle\mu_{j,k}\rangle$. ∎

Algorithm 1 outlines how to retrieve approximate sufficient statistics
$\widetilde{X^{T}X}$ and $\widetilde{X^{T}y}$ from marginals privately
estimated by AIM.

1: $M\leftarrow\texttt{AIM}{}(\mathcal{D},\epsilon,\delta)$ is the collection
of privately computed pairwise marginal tables $\mu_{j,k}$ for all attribute
pairs $(j,k)$.

2: $(\widetilde{Z^{T}Z})_{[j,k]}\leftarrow A_{j}\langle\mu_{j,k}\rangle
A_{k}^{T}$ for all attribute pairs $(j,k)$ (see Proposition 3.2)

3: Extract $\widetilde{X^{T}X}$ and $\widetilde{X^{T}y}$ from
$\widetilde{Z^{T}Z}$ using the block structure of Equation (1)

Algorithm 1 DD-SSP

This implies we can solve DP linear regression by i) retrieving
$\widetilde{X^{T}X}$ and $\widetilde{X^{T}y}$ as outlined in Algorithm 1, and
ii) finding
$\hat{\theta}_{\text{DP}}=\widetilde{X^{T}X}^{-1}\widetilde{X^{T}y}$.

######  Proposition 3.3.

DD-SSP is ($\epsilon,\delta$)-DP.

The proof follows directly from the $(\epsilon,\delta)$-DP properties of the
marginal-releasing algorithm (in our case, AIM), and the fact that all
subsequent steps are post-processing of a DP result (Definition 2.5).

###  3.3 Logistic regression

Logistic regression predicts the probability a binary label $y\in\\{-1,+1\\}$
takes value $+1$ as $p=1/(1+\exp(-x\cdot\theta))$, where
$\theta\in\mathbb{R}^{p}$ is a coefficient vector and $x\cdot\theta$ is the
dot-product. The log-likelihood function is

$\displaystyle\ell(\theta)$
$\displaystyle=\sum_{i=1}^{n}\phi(x^{(i)}\cdot\theta y^{(i)})$

where $\phi(s):=-\log(1+e^{-s})$. Optimizing this log-likelihood is a convex
optimization problem solvable numerically via standard optimizers. The log-
likelihood does not have _finite_ sufficient statistics. However, [23] offers
a polynomial strategy to obtain _approximate_ sufficient statistics for
generalized linear models (GLMs), including logistic regression. Kulkarni et
al. [27] used a similar polynomial approximation for private Bayesian GLMs. We
propose a novel DP logistic regression method that combines two ideas: i) we
use a Chebyshev approximation of the logistic regression log-likelihood based
on [23], which allows us 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 of
the input workload for AIM depends on the characterization of the approximate
log-likelihood. Based on our derivation below, we find that the best workload
input for logistic regression is all pairwise marginals.

Huggins et al. [23] propose to approximate $\ell(\theta)$ by using an
degree-$M$ polynomial approximation of the function $\phi$:

$\displaystyle\phi(s)\approx\phi_{M}(s):=\sum_{m=0}^{M}{b_{m}}^{(M)}s^{m}$

where $b_{j}^{(M)}$ are constants. There are different choices for the
orthogonal polynomial basis, and as in [23], we focus on Chebyshev
polynomials, which provide uniform quality guarantees over a finite interval
$[-R,R]$ for a positive $R$. We can then write

$\displaystyle\ell(\theta)$
$\displaystyle\approx\sum_{i=1}^{n}\sum_{m=0}^{M}b_{m}^{(M)}(x^{(i)}\cdot\theta
y^{(i)})^{m}$

We choose to work with a degree-2 Chebyshev approximation over range $[-6,6]$
(Figure 2).

Figure 2: Degree 2 Chebyshev approximation of the logit function $\phi$, where
$\phi(s):=-\log(1+e^{-s})$

######  Proposition 3.4.

The logistic regression log-likelihood is approximated by second order
Chebyshev polynomial $\tilde{\ell}(\theta)\approx
nb_{0}^{(2)}+b_{1}^{(2)}\theta\widetilde{X^{T}y}+b_{2}^{(2)}\cdot(\theta^{T}\widetilde{X^{T}X}\theta)$,
where $b_{0}^{(2)},b_{1}^{(2)},b_{2}^{(2)}$ are constants, and
$\widetilde{X^{T}X}$ and $\widetilde{X^{T}y}$ can be retrieved from pairwise
marginals as in Proposition 3.2.

The proof is provided in Appendix A. This allows us to define a logistic
regression objective where $\widetilde{X^{T}X}$ and $\widetilde{X^{T}y}$ are
obtained via Algorithm 1, which is DP by post-processing (Proposition 3.3).
The objective can then be optimized directly via standard (non-private)
procedures.

###  3.4 Baselines

We compare DD-SSP to synthetic data method AIM-Synth, 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. As seen in Figure 1, 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.

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 [48] for its competitive performance. As
other SSP methods, AdaSSP uses limited data-adaptivity to add a ridge penalty
based on an estimated bound on the eigenvalues of $X^{T}X$, but then adds
independent noise to each entry of the sufficient statistics, unlike fully
data-adaptive query-answering mechanisms. The AdaSSP algorithm is described in
detail in Appendix B. For logistic regression, objective perturbation
(ObjPert) is a widely adopted solution originally proposed by [8], and further
refined by [26] where it is extended to $(\epsilon,\delta)$-DP, with more
general applicability and improved guarantees. The algorithm and details are
provided in Appendix C.

Both AdaSSP and ObjPert determine how much noise to add based on
$\|\mathcal{X}\|$, which is the upper bound to the $L_{2}$-norm of any row $x$
of $X$ (Section 3.1). For example, in AdaSSP, $X^{T}X$ is noise-perturbed
proportionally to $\|\mathcal{X}\|^{2}$. From Proposition 3.1, we can set
$\|\mathcal{X}\|^{2}=\|\mathcal{U}\|^{2}+c$ where $\|\mathcal{U}\|$ is a bound
on the numerically-encoded features and $c$ is the number of one-hot-encoded
attributes to obtain a tight sensitivity bound for these baselines.

###  3.5 Limitations

DD-SSP takes privatized marginals as input. When choosing AIM as the mechanism
for outputting 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
discretization. For the logistic regression approximation, we use Chebyshev
second order polynomials; other approximation functions and/or degrees of
precision could be evaluated, but are outside the scope of this paper. As
shown in section D, DD-SSP demonstrates overall gains in regression accuracy
compared to baseline methods, however this improvement comes at the cost of
increased computational time, which is tied to the choice of AIM as our
private marginal releasing method. AIM’s runtime increases with the size of
the data domain and with $\epsilon$ (see Appendix D for more detail). While
our methods do introduce an increased computational burden, this tradeoff is
justified by the substantial gains in accuracy. In terms of experimentation
(see Section 4 below), for computational viability we study the variability of
our results across 5 trials.

##  4 Experiments

In our experiments we evaluate the effectiveness of DD-SSP for linear and
logistic regression against AdaSSP and ObjPert respectively. Additionally, we
assess the similarity between the performance of DD-SSP and that of AIM
synthetic data (AIM-Synth), suggesting that data-dependent estimation (or
approximation) of sufficient statistics explains the operational mechanisms
that make marginal-based synthetic data suitable for machine learning
tasks.111All experiment code is available at
https://github.com/ceciliaferrando/DD-SSP.

We run linear regression on real datasets Adult [4], ACSIncome [11], Fire
[41], and Taxi [20]. For Adult, we choose ‘num-education’ (number of education
years) as the predicted variable. For ACSIncome, we queried the source
database for the state of California and survey year 2018. The target variable
is ‘PINCP’ (income), discretized into 20 bins. For Fire, the target is
‘Priority’ (of the call), and for Taxi it is ‘totalamount’ (total fare amount
of the ride).222The ACS data is sourced from
https://github.com/socialfoundations/folktables. All other datasets are
sourced from https://github.com/ryan112358/hd-datasets. For every dataset,
data is shuffled and split between $1,000$ data points as test set and the
rest as the training set, capped at a maximum of $50,000$ train data points.
AIM is trained with model size 200MB, maximum number of iterations 1,000, and
a workload of all pairwise marginals. Other than AIM, which uses the original
feature levels, for training purposes non-numerical features are one-hot
encoded as outlined in 3.1, dropping the first level to avoid multi-
collinearity, and discrete numerical features keep the encoding from $1$ to
$m_{j}$. To calibrate the sensitivity accordingly, and avoid unnecessarily
penalizing AdaSSP, the bound $\|\mathcal{X}\|$ is computed as described in
Sections 3.1 and 3.4. Numerical features are also rescaled to domain $[-1,1]$
so that DP noise is allocated roughly evenly across statistics of different
features. We compare the Mean Squared Error (MSE) of DP query-based methods
DD-SSP and AIM-Synth against DP baseline AdaSSP and the public baseline for
$\epsilon\in\\{0.05,0.1,0.5,1.0,2.0\\}$, with a fixed $\delta=1e-5$. The plots
in Figure 3 show that DD-SSP and AIM-Synth have nearly identical performance
and both improve significantly upon the DP baseline AdaSSP on all datasets
except ACSincome, where the performance is similar.

Figure 3: Linear regression MSE results (first row) and logistic regression
AUC results (second row). Standard error bars are computed over 5 trials.

We run the same set of experiments for logistic regression on Adult, and four
ACS datasets [11], ACSincome (target binary ‘PINCP’ with cutoff at 50k),
ACSmobility (‘MIG’), ACSemployment (‘ESR’), and ACSPublicCoverage (‘PUBCOV’).
All datasets are for the state of California and survey year 2018. The results
in Figure 3 show that the performance of DD-SSP closely matches AIM-Synth,
surpassing it slightly in the case of Adult and ACSincome. Both methods
display overall improved AUC performance with respect to the ObjPert baseline,
with clear improvements in the low-$\epsilon$ regime, and close performance at
higher $\epsilon$.

Based on these results, we observe that: i) DD-SSP is a competitive option for
DP linear and logistic regression, with better performance than data-
independent SSP for linear regression and ObjPert for logistic regression; ii)
the same good performance can be achieved by training AIM-Synth with a
workload of two-way marginals, which corresponds to estimating problem-
specific data-dependent sufficient statistics. This suggests that the query-
based sufficient statistics approximation explains the suitability of AIM
synthetic data for machine learning. At the same time, it implies DD-SSP is a
convenient and effective DP option to solve linear and logistic regression
whenever pairwise marginals are available; iii) the approximate DD-SSP method
for logistic regression constitutes a novel DP algorithm for solving logistic
regression privately as an alternative to privatized ERM procedures.

##  5 Discussion

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-independent SSP on linear regression and objective
perturbation for logistic regression. Notably, the approximate DD-SSP logistic
regression algorithm is the first DP logistic regression method that allows
analysts to 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 synthetic data: this
suggests that with the appropriate workload, training these machine learning
models on query-based DP synthetic data corresponds to data-dependent SSP.
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 a workload that supports the estimation of their sufficient
statistics. Future work can focus on developing approximate loss functions
with finite sufficient statistics for a broader class of other models,
including generalized linear models (GLMs). This will open the door to novel
DD-SSP methods that directly minimize the approximate loss functions, and
improve utility by adding privacy noise in a data-dependent way. Additionally,
methods targeting encoded workload $A_{j}\langle\mu_{j,k}\rangle A_{k}^{T}$
instead of $\mu_{j,k}$ can be explored and combined with advanced data-
independent mechanisms like the matrix mechanism, potentially leading to a new
class of encoding-aware SSP methods.

## Acknowledgements

This material is based upon work supported by the National Science Foundation
under Grant No. 1749854, and by Oracle through a gift to the University of
Massachusetts Amherst in support of academic research.

## References

  * Abadi et al. [2016] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang.  Deep learning with differential privacy.  In _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , pages 308–318, 2016.
  * Aydore et al. [2021] S. Aydore, W. Brown, M. Kearns, K. Kenthapadi, L. Melis, A. Roth, and A. A. Siva.  Differentially private query release through adaptive projection.  In _International Conference on Machine Learning_ , pages 457–467. PMLR, 2021.
  * Bassily et al. [2014] R. Bassily, A. Smith, and A. Thakurta.  Private empirical risk minimization: Efficient algorithms and tight error bounds.  In _2014 IEEE 55th annual symposium on foundations of computer science_ , pages 464–473. IEEE, 2014.
  * Becker and Kohavi [1996] B. Becker and R. Kohavi.  Adult.  UCI Machine Learning Repository, 1996.  DOI: https://doi.org/10.24432/C5XW20.
  * Bernstein and Sheldon [2019] G. Bernstein and D. R. Sheldon.  Differentially private bayesian linear regression.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Bun and Steinke [2016] M. Bun and T. Steinke.  Concentrated differential privacy: Simplifications, extensions, and lower bounds.  In _Theory of Cryptography Conference_ , pages 635–658. Springer, 2016.
  * Chaudhuri and Monteleoni [2008] K. Chaudhuri and C. Monteleoni.  Privacy-preserving logistic regression.  _Advances in neural information processing systems_ , 21, 2008.
  * Chaudhuri et al. [2011] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate.  Differentially private empirical risk minimization.  _Journal of Machine Learning Research_ , 12(3), 2011.
  * Dimitrakakis et al. [2017] C. Dimitrakakis, B. Nelson, Z. Zhang, A. Mitrokotsa, and B. I. Rubinstein.  Differential privacy for bayesian inference through posterior sampling.  _Journal of machine learning research_ , 18(11):1–39, 2017.
  * Ding et al. [2011] B. Ding, M. Winslett, J. Han, and Z. Li.  Differentially private data cubes: optimizing noise sources and consistency.  In _Proceedings of the 2011 ACM SIGMOD International Conference on Management of data_ , pages 217–228, 2011.
  * Ding et al. [2021] 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.
  * Dwork and Smith [2010] C. Dwork and A. Smith.  Differential privacy for statistics: What we know and what we want to learn.  _Journal of Privacy and Confidentiality_ , 1(2), 2010.
  * Dwork et al. [2006] C. Dwork, F. McSherry, K. Nissim, and A. Smith.  Calibrating noise to 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.
  * Dwork et al. [2014] C. Dwork, A. Roth, et al.  The algorithmic foundations of differential privacy.  _Foundations and Trends® in Theoretical Computer Science_ , 9(3–4):211–407, 2014.
  * Ferrando et al. [2022] 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.
  * Fisher [1922] R. A. Fisher.  On the mathematical foundations of theoretical statistics.  _Philosophical transactions of the Royal Society of London. Series A, containing papers of a mathematical or physical character_ , 222(594-604):309–368, 1922.
  * Foulds et al. [2016] J. Foulds, J. Geumlek, M. Welling, and K. Chaudhuri.  On the theory and practice of privacy-preserving bayesian data analysis.  _arXiv preprint arXiv:1603.07294_ , 2016.
  * Gaboardi et al. [2014] 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.
  * Gower and Bach [2019] R. M. Gower and F. Bach.  Properties and examples of convexity and smoothness, February 2019.  URL https://gowerrobert.github.io/pdf/M2_statistique_optimisation/exe_convexity_smoothness_solution.pdf.
  * Grégoire et al. [2021] 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.
  * Hardt et al. [2012] M. Hardt, K. Ligett, and F. McSherry.  A simple and practical algorithm for differentially private data release.  _Advances in neural information processing systems_ , 25, 2012.
  * Hay et al. [2009] M. Hay, V. Rastogi, G. Miklau, and D. Suciu.  Boosting the accuracy of differentially-private histograms through consistency.  _arXiv preprint arXiv:0904.0942_ , 2009.
  * Huggins et al. [2017] J. Huggins, R. P. Adams, and T. Broderick.  Pass-glm: polynomial approximate sufficient statistics for scalable bayesian glm inference.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Jain and Thakurta [2013] P. Jain and A. Thakurta.  Differentially private learning with kernels.  In _International conference on machine learning_ , pages 118–126. PMLR, 2013.
  * Jordon et al. [2019] J. Jordon, J. Yoon, and M. Van Der Schaar.  Pate-gan: Generating synthetic data with differential privacy guarantees.  In _International conference on learning representations_ , 2019.
  * Kifer et al. [2012] 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.
  * Kulkarni et al. [2021] T. Kulkarni, J. Jälkö, A. Koskela, S. Kaski, and A. Honkela.  Differentially private bayesian inference for generalized linear models.  In _International Conference on Machine Learning_ , pages 5838–5849. PMLR, 2021.
  * Li and Miklau [2012] C. Li and G. Miklau.  An adaptive mechanism for accurate query answering under differential privacy.  _arXiv preprint arXiv:1202.3807_ , 2012.
  * Li et al. [2010] 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 SIGMOD-SIGACT-SIGART symposium on Principles of database systems_ , pages 123–134, 2010.
  * Li et al. [2014] C. Li, M. Hay, G. Miklau, and Y. Wang.  A data-and workload-aware algorithm for range queries under differential privacy.  _arXiv preprint arXiv:1410.0265_ , 2014.
  * Li et al. [2015] 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.
  * Liu et al. [2021] 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.
  * McKenna et al. [2019] R. McKenna, D. Sheldon, and G. Miklau.  Graphical-model based estimation and inference for differential privacy.  In _International Conference on Machine Learning_ , pages 4435–4444. PMLR, 2019.
  * McKenna et al. [2021a] R. McKenna, G. Miklau, M. Hay, and A. Machanavajjhala.  Hdmm: Optimizing error of high-dimensional statistical queries under differential privacy.  _arXiv preprint arXiv:2106.12118_ , 2021a.
  * McKenna et al. [2021b] R. McKenna, G. Miklau, and D. Sheldon.  Winning the nist contest: A scalable and general approach to differentially private synthetic data.  _arXiv preprint arXiv:2108.04978_ , 2021b.
  * McKenna et al. [2022] R. McKenna, B. Mullins, D. Sheldon, and G. Miklau.  Aim: An adaptive and iterative mechanism for differentially private synthetic data.  _arXiv preprint arXiv:2201.12677_ , 2022.
  * McSherry and Mironov [2009] 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 on Knowledge discovery and data mining_ , pages 627–636, 2009.
  * [38] NIST 2018 Differential Privacy Synthetic Data Challenge.  https://www.nist.gov/ctl/pscr/open-innovation-prize-challenges/past-prize-challenges/2018-differential-privacy-synthetic, 2018.
  * [39] NIST 2020 Differential Privacy Temporal Map Challenge.  https://www.nist.gov/ctl/pscr/open-innovation-prize-challenges/past-prize-challenges/2020-differential-privacy-temporal, 2020.
  * Qardaji et al. [2014] W. Qardaji, W. Yang, and N. Li.  Priview: practical differentially private release of marginal contingency tables.  In _Proceedings of the 2014 ACM SIGMOD international conference on Management of data_ , pages 1435–1446, 2014.
  * Ridgeway et al. [2021] D. Ridgeway, M. F. Theofanos, T. W. Manley, and C. Task.  Challenge design and lessons learned from the 2018 differential privacy challenges.  _NIST technical note_ , 2151, 2021.
  * Rosenblatt et al. [2020] L. Rosenblatt, X. Liu, S. Pouyanfar, E. de Leon, A. Desai, and J. Allen.  Differentially private synthetic data: Applied evaluations and enhancements.  _arXiv preprint arXiv:2011.05537_ , 2020.
  * Sheffet [2017] O. Sheffet.  Differentially private ordinary least squares.  In _International Conference on Machine Learning_ , pages 3105–3114. PMLR, 2017.
  * Tao et al. [2021] Y. Tao, R. McKenna, M. Hay, A. Machanavajjhala, and G. Miklau.  Benchmarking differentially private synthetic data generation algorithms.  _arXiv preprint arXiv:2112.09238_ , 2021.
  * Vietri et al. [2020] G. Vietri, G. Tian, M. Bun, T. Steinke, and S. Wu.  New oracle-efficient algorithms for private synthetic data release.  In _International Conference on Machine Learning_ , pages 9765–9774. PMLR, 2020.
  * Vietri et al. [2022] 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.07400_ , 2022.
  * Vu and Slavkovic [2009] D. Vu and A. Slavkovic.  Differential privacy for clinical trial data: Preliminary evaluations.  In _2009 IEEE International Conference on Data Mining Workshops_ , pages 138–143. IEEE, 2009.
  * Wang [2018] Y.-X. Wang.  Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain.  _arXiv preprint arXiv:1803.02596_ , 2018.
  * Wang et al. [2015] Y.-X. 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.
  * Xiao et al. [2012] Y. Xiao, L. Xiong, L. Fan, and S. Goryczka.  Dpcube: Differentially private histogram release through multidimensional partitioning.  _arXiv preprint arXiv:1202.5358_ , 2012.
  * Xie et al. [2018] L. Xie, K. Lin, S. Wang, F. Wang, and J. Zhou.  Differentially private generative adversarial network.  _arXiv preprint arXiv:1802.06739_ , 2018.
  * Xu et al. [2013] J. Xu, Z. Zhang, X. Xiao, Y. Yang, G. Yu, and M. Winslett.  Differentially private histogram publication.  _The VLDB journal_ , 22:797–822, 2013.
  * Yaroslavtsev et al. [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.
  * Zhang et al. [2017] J. Zhang, G. Cormode, C. M. Procopiuc, D. Srivastava, and X. Xiao.  Privbayes: Private data release via bayesian networks.  _ACM Transactions on Database Systems (TODS)_ , 42(4):1–41, 2017.
  * Zhang et al. [2014] X. Zhang, R. Chen, J. Xu, X. Meng, and Y. Xie.  Towards accurate histogram publication under differential privacy.  In _Proceedings of the 2014 SIAM international conference on data mining_ , pages 587–595. SIAM, 2014.
  * Zhang et al. [2016] Z. 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.
  * Zhou et al. [2024] Y. Zhou, M. Liang, I. Brugere, D. Dachman-Soled, D. Dervovic, A. Polychroniadou, and M. Wu.  Bounding the excess risk for linear models trained on marginal-preserving, differentially-private, synthetic data.  _arXiv preprint arXiv:2402.04375_ , 2024.

##  Appendix A Logistic Regression log-likelihood approximation

###### Proof.

The log-likelihood for logistic regression can be expressed as

$\displaystyle\ell(\theta)$
$\displaystyle=\sum_{i=1}^{n}\phi(x^{(i)}\cdot\theta y^{(i)})$

where $\phi(s):=-\log(1+e^{-s})$. Based on [23], we can approximate the
logistic regression log-likelihood with a Chebyshev polynomial approximation
of degree $M$:

$\displaystyle\phi(s)\approx\phi_{M}(s):=\sum_{m=0}^{M}{b_{m}}^{(M)}s^{m}$

where $b_{j}^{(M)}$ are constants. Then,

$\displaystyle\ell(\theta)$
$\displaystyle\approx\sum_{i=1}^{n}\sum_{m=0}^{M}b_{m}^{(M)}(x^{(i)}\cdot\theta
y^{(i)})^{m}$

If we choose $M=2$,

$\displaystyle\ell(\theta)$
$\displaystyle\approx\sum_{i=1}^{n}b_{0}^{(2)}+b_{1}^{(2)}\cdot(x^{(i)}\cdot\theta
y^{(i)})+b_{2}^{(2)}\cdot(x^{(i)}\cdot\theta y^{(i)})^{2}$

The quadratic term is

$\displaystyle\sum_{i=1}^{n}(x^{(i)}\cdot\theta y^{(i)})^{2}$
$\displaystyle=\sum_{i=1}^{n}{y^{(i)^{2}}}\sum_{j,k=1}^{d}x^{(i)}_{j}x^{(i)}_{k}\theta_{j}\theta_{k}=\sum_{j,k=1}^{d}\theta_{j}\theta_{k}\sum_{i=1}^{n}{y^{(i)^{2}}}x^{(i)}_{j}x^{(i)}_{k}$

Therefore we can rewrite the approximate log-likelihood as

$\displaystyle\ell(\theta)$ $\displaystyle\approx
nb_{0}^{(2)}+b_{1}^{(2)}\sum_{i=1}^{n}x^{(i)}\cdot\theta
y^{(i)}+b_{2}^{(2)}\sum_{j,k=1}^{d}\theta_{j}\theta_{k}\sum_{i=1}^{n}{y^{(i)}}^{2}x^{(i)}_{j}x^{(i)}_{k}$
$\displaystyle\approx
nb_{0}^{(2)}+b_{1}^{(2)}y^{T}X\theta+b_{2}^{(2)}\sum_{j,k=1}^{d}\theta_{j}\theta_{k}\sum_{i=1}^{n}x^{(i)}_{j}x^{(i)}_{k}$
$\displaystyle\approx
nb_{0}^{(2)}+b_{1}^{(2)}y^{T}X\theta+b_{2}^{(2)}\theta^{T}X^{T}X\theta$

where the simplification in the last line follows from the fact that we work
with $y^{(i)}\in\\{1,-1\\}$ and ${y^{(i)}}^{2}=1$ for any $i$.

$X^{T}X$ in the third term and $y^{T}X$ can be derived following the same
proposed strategies as in linear regression (Section 3.2), obtaining marginal
query-based estimates $\widetilde{X^{T}X}$ and $\widetilde{y^{T}X}$. We can
then express the log-likelihood as

$\displaystyle\ell(\theta)$ $\displaystyle\approx
nb_{0}^{(2)}+b_{1}^{(2)}\widetilde{y^{T}X}\theta+b_{2}^{(2)}\cdot(\theta^{T}\widetilde{X^{T}X}\theta)$

∎

##  Appendix B Linear regression baseline

Algorithm 2 outlines the AdaSSP method for linear regression [48].

1: Input: Data $X$, $\boldsymbol{y}$. Privacy budget: $\epsilon$, $\delta$.
Bounds: $\|\mathcal{X}\|$, $\|\mathcal{Y}\|$, $\rho\in(0,1)$ (0.05 in the
paper)

2: 1. Calculate the minimum eigenvalue $\lambda_{\min}\left(X^{T}X\right)$.

3: 2. Privately release
$\tilde{\lambda}_{\min}=\max\left\\{\lambda_{\min}+\frac{\sqrt{\log(6/\delta)}}{\epsilon/3}\|\mathcal{X}\|^{2}Z-\frac{\log(6/\delta)}{\epsilon/3}\|\mathcal{X}\|^{2},0\right\\}$,
where $Z\sim\mathcal{N}(0,1)$.

4: 3. Set
$\lambda=\max\left\\{0,\frac{\sqrt{d\log(6/\delta)\log\left(2d^{2}/\rho\right)}\|\mathcal{X}\|^{2}}{\epsilon/3}-\tilde{\lambda}_{\min}\right\\}$.

5: 4. Privately release
$\widehat{X^{T}X}=X^{T}X+\frac{\sqrt{\log(6/\delta)}\|\mathcal{X}\|^{2}}{\epsilon/3}Z$
for $Z\in\mathbb{R}^{d\times d}$ is a symmetric matrix and every element from
the upper triangular matrix is sampled from $\mathcal{N}(0,1)$.

6: 5. Privately release
$\widehat{X^{T}y}=X^{T}y+\frac{\sqrt{\log(6/\delta)}\|\mathcal{X}\|\|\mathcal{Y}\|}{\epsilon/3}Z$
for $Z\sim\mathcal{N}\left(0,I_{d}\right)$.

7: Output: $\tilde{\theta}=\left(\widehat{X^{T}X}+\lambda
I\right)^{-1}\widehat{X^{T}y}$.

Algorithm 2 AdaSSP [48]

To reason about the sensitivity of $X^{T}X$, consider two neighboring datasets
$X\in\mathbb{R}^{n\times d}$ and $X^{\prime}\in\mathbb{R}^{(n+1)\times d}$
differing by one data entry $v\in\mathcal{X}$, where $v$ is a $d\times 1$
vector. Then,

$\displaystyle\Delta_{X^{T}X}=\text{sup}_{X\sim
X^{\prime}}\|f(X^{\prime})-f(X)\|_{F}$

Since $X$ and $X^{\prime}$ only differ by one row ($v$), then
$f(X^{\prime})-f(X)=vv^{T}$ [43].

So the sensitivity is maximum over $v$ of
$\|\text{vec}(vv^{T})\|=\|vv^{T}\|_{F}$. We have

$\displaystyle\Delta_{X^{T}X}^{2}$
$\displaystyle=\sup_{v\in\mathcal{X}}\|vv^{T}\|_{F}^{2}$
$\displaystyle=\sup_{v\in\mathcal{X}}\sum_{i=1}^{d}\sum_{j=1}^{d}(v_{i}v_{j})^{2}$
$\displaystyle=\sup_{v\in\mathcal{X}}\left(\sum_{i=1}^{d}v_{i}^{2}\right)\left(\sum_{j=1}^{d}v_{j}^{2}\right)$
$\displaystyle=\sup_{v\in\mathcal{X}}\|v\|^{4}$
$\displaystyle=\|\mathcal{X}\|^{4}$

where $\|\mathcal{X}\|$ is the greatest possible norm of a vector in the
domain $\mathcal{X}$. Therefore,

$\displaystyle\Delta_{X^{T}X}=\|\mathcal{X}\|^{2}.$

The sensitivity of $X^{T}y$ can be similarly derived. Given neighboring
datasets $X\in\mathbb{R}^{n\times d},y\in\mathbb{R}^{n}$, and
$X^{\prime}\in\mathbb{R}^{(n+1)\times d},y^{\prime}\in\mathbb{R}^{n+1}$, where
$v\in\mathcal{X}\subset\mathbb{R}^{d}$ is the new row, and
$w\in\mathcal{Y}\subset\mathbb{R}$ is the new value in $y^{\prime}$. Then,

$\displaystyle\|f\left(X^{\prime},y^{\prime}\right)-f(X,y)\|=\|X^{\prime
T}y^{\prime}-X^{T}y\|=\|wv\|$

Since $\|\mathcal{X}\|=\sup_{x\in\mathcal{X}}\|x\|$ and
$\|\mathcal{Y}\|=\sup_{y\in\mathcal{Y}}|y|$, we have

$\displaystyle\Delta_{X^{T}y}$
$\displaystyle=\sup_{(X,y)\sim\left(X^{\prime},y^{\prime}\right)}\left\|f\left(X^{\prime},y^{\prime}\right)-f(X,y)\right\|$
$\displaystyle=\sup_{w\in\mathcal{Y},v\in\mathcal{X}}|w|\cdot\|v\|=\|\mathcal{Y}\|\cdot\|\mathcal{X}\|$

##  Appendix C Logistic regression baseline

Our DP logistic regression baseline is based on the generalized objective
perturbation algorithm in [26] (Algorithm 3). In this section, to match the
notation in [26] $\ell\left(\theta;z\right)=\log(1+\exp(-x\cdot\theta y))$ is
the loss for a single datum and
$\hat{\mathcal{L}}(\theta;\mathcal{D})=\frac{1}{n}\sum_{i=1}^{n}\ell(\theta;z^{(i)})$
is the average loss over the dataset.

Algorithm 3 Generalized Objective Perturbation Mechanism (ObjPert) [26]

0: dataset $\mathcal{D}=\left\\{z^{(1)},\ldots,z^{(n)}\right\\}$, where
$z^{(i)}=(x^{(i)},y^{(i)})$, privacy parameters $\epsilon$ and $\delta$
($\delta=0$ for $\epsilon$-differential privacy), bound $\|\mathcal{X}\|$ on
the $L_{2}$ norm of any $x$ entry, convex regularizer $r$, a convex domain
$\mathbb{F}\subseteq\mathbb{R}^{d}$, convex loss function
$\hat{\mathcal{L}}(\theta;\mathcal{D})=\frac{1}{n}\sum_{i=1}^{n}\ell\left(\theta;z^{(i)}\right)$,
with continuous Hessian, $\|\nabla\ell(\theta;z)\|\leq\|\mathcal{X}\|$ (for
all $z\in\mathcal{D}$ and $\theta\in\mathbb{F}$), and the eigenvalues of
$\nabla^{2}\ell(\theta;z)$ bounded by $\frac{\|\mathcal{X}\|^{2}}{4}$ (for all
$z$ and for all $\theta\in\mathbb{F}$).

1: Set $\Delta\geq\frac{\|\mathcal{X}\|^{2}}{2\epsilon}$.

2: Sample $b\in\mathbb{R}^{d}$ from
$\nu_{2}(b;\epsilon,\delta,\|\mathcal{X}\|)=\mathcal{N}\left(0,\frac{\|\mathcal{X}\|^{2}\left(8\log\frac{2}{\delta}+4\epsilon\right)}{\epsilon^{2}}I_{d}\right)$.

3:
$\hat{\theta}_{\text{DP}}\equiv\arg\min_{\theta\in\mathbb{F}}\hat{\mathcal{L}}(\theta;\mathcal{D})+\frac{1}{n}r(\theta)+\frac{\Delta}{2n}\|\theta\|^{2}+\frac{b^{T}\theta}{n}$.

The algorithm requires the following bounds for the gradient and Hessian of
$\ell$:

$\displaystyle\|\nabla\ell(\theta;z)\|$ $\displaystyle\leq\|\mathcal{X}\|$
$\displaystyle\lambda_{\max}(\nabla^{2}\ell(\theta;z))$
$\displaystyle\leq\frac{\|\mathcal{X}\|^{2}}{4}$

To reason about the sensitivity bounds, let $\phi(s)=\log(1+e^{s})$. Then we
can write $\ell(\theta;z)=\phi(-x\cdot\theta y)$. Following [19], it is
straightforward to derive that

$\displaystyle\phi^{\prime}(s)$ $\displaystyle=\frac{e^{s}}{1+e^{s}}\leq 1$
$\displaystyle\phi^{\prime\prime}(s)$
$\displaystyle=\frac{e^{s}}{(1+e^{s})^{2}}\leq\frac{1}{4}$

and clear that both quantities are non-negative. Then the gradient of $\ell$
is:

$\displaystyle\nabla\ell(\theta;z)=\nabla_{\theta}\phi(-x\cdot\theta
y)=\phi^{\prime}(-x\cdot\theta y)\cdot-yx$

The norm is bounded as

$\displaystyle\|\nabla\ell(\theta;z)\|=|\phi^{\prime}(-x\cdot\theta
y)|\cdot|y|\cdot\|x\|\leq\|\mathcal{X}\|$

where the inequality holds since $|\phi^{\prime}(s)|\leq 1$ for all $s$ and
$|y|=1$.

By differentiating the gradient again and using the fact that $y^{2}=1$, we
can derive the Hessian as:

$\displaystyle\nabla^{2}\ell(\theta;z)=\phi^{\prime\prime}(-x\cdot\theta
y)xx^{T}$

The maximum eigenvalue is

$\displaystyle\lambda_{\max}(\nabla^{2}\ell(\theta;z))$
$\displaystyle=\phi^{\prime\prime}(-x\cdot\theta y)\lambda_{\max}(xx^{T})$
$\displaystyle=\phi^{\prime\prime}(-x\cdot\theta y)\|x\|^{2}$
$\displaystyle\leq\frac{\|\mathcal{X}\|^{2}}{4}$

In the second line, we used the fact that $\lambda_{\max}(xx^{T})=\|x\|^{2}$.
To see this, note that $xx^{T}$ is rank one and $(xx^{T})x=\|x\|^{2}x$,
therefore $x$ is an eigenvector with eigenvalue $\|x\|^{2}$ and this is the
largest eigenvalue. In the last line we used that
$\|\phi^{\prime\prime}(s)\|\leq\frac{1}{4}$ for all $s$ and that
$\|x\|\leq\|\mathcal{X}\|$.

##  Appendix D Experiment details

Table 1: Dataset information Dataset | Size |  # Attributes |  Attributes |  Target
---|---|---|---|---
Adult | 48,842 |  15 |  [’age’, ’workclass’, ’fnlwgt’, ’education’, ’marital-status’, ’occupation’, ’relationship’, ’race’, ’sex’, ’capital-gain’, ’capital-loss’, ’hours-per-week’, ’native-country’, ’income$>$50K’, ’education-num’] |  ’income$>$50K’ (logistic), ’education-num’ (linear)
ACSIncome | 195,665 |  9 |  [’AGEP’, ’COW’, ’SCHL’, ’MAR’, ’RELP’, ’WKHP’, ’SEX’, ’RAC1P’, ’PINCP’] |  ’PINCP’
Fire | 305,119 |  15 |  [’ALS Unit’, ’Battalion’, ’Call Final Disposition’, ’Call Type’, ’Call Type Group’, ’City’, ’Final Priority’, ’Fire Prevention District’, ’Neighborhooods - Analysis Boundaries’, ’Original Priority’, ’Station Area’, ’Supervisor District’, ’Unit Type’, ’Zipcode of Incident’, ’Priority’] |  ’Priority’
Taxi | 1,048,575 |  11 |  [’VendorID’, ’passengercount’, ’tripdistance’, ’RatecodeID’, ’PULocationID’, ’DOLocationID’, ’paymenttype’, ’fareamount’, ’tipamount’, ’tollsamount’, ’totalamount’] |  ’totalamount’
ACSEmployment | 378,817 |  17 |  [’AGEP’, ’SCHL’, ’MAR’, ’RELP’, ’DIS’, ’ESP’, ’CIT’, ’MIG’, ’MIL’, ’ANC’, ’NATIVITY’, ’DEAR’, ’DEYE’, ’DREM’, ’SEX’, ’RAC1P’, ’ESR’] |  ’ESR’
ACSPublicCoverage | 138,550 |  19 |  [’AGEP’, ’SCHL’, ’MAR’, ’SEX’, ’DIS’, ’ESP’, ’CIT’, ’MIG’, ’MIL’, ’ANC’, ’NATIVITY’, ’DEAR’, ’DEYE’, ’DREM’, ’PINCP’, ’ESR’, ’FER’, ’RAC1P’, ’PUBCOV’] |  ’PUBCOV’

Information about the datasets used in the Experiments section is reported in
Table 1.

All experiments are run on an internal cluster using Xeon Gold 6240 CPU @
2.60GHz, 192GB RAM and 240GB local SSD disk. Experiment runtime varies
depending on multiple factors. Our method is based on private marginals
released by AIM and is therefore tied to AIM’s runtime, which is significantly
longer than the runtime of our DP baselines. For AIM, runtime increases with
the domain size and $\epsilon$. In the following runtime analysis, we refer to
a full experiment as one trial for each $\epsilon$ in
$[0.05,0.1,0.5,1.0,2.0]$, at 200MB model size and 1,000 maximum iterations for
AIM, and running on the internal cluster specified above. For linear
regression, the longest AIM experiment is for dataset Fire, taking
approximately 29 hours. The shortest linear regression experiment with the
same setting is ACSincome, at approximately 50 minutes runtime. By comparison,
AdaSSP completes the corresponding experiments in approximately 5 seconds
(Fire) and 1 second (ACSincome). For logistic regression, the longest AIM
experiment is for ACSPublicCoverage, with a runtime of approximately 43 hours,
and the shortest is ACSincome at approximately 10 hours. The corresponding
runtime for DP baseline ObjPert is approximately 2 seconds in both cases. AIM
computation time grows with $\epsilon$. For example, in the case of linear
regression on Adult, running AIM takes approximately 8 minutes with
$\epsilon=0.05$, and approximately 18 hours for $\epsilon=2.0$.