# Personalized Differential Privacy for Ridge Regression

Krishna Acharya  Georgia Institute of Technology  Franziska Boenisch  CISPA
Helmholtz Center for Information Security  Rakshit Naidu  Georgia Institute of
Technology  Juba Ziani  Georgia Institute of Technology

( 1{krishna.acharya, rakshitnaidu<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
)

###### Abstract

The increased application of machine learning (ML) in sensitive domains
requires protecting the training data through privacy frameworks, such as
differential privacy (DP). DP requires to specify a uniform privacy level
$\varepsilon$ that expresses the maximum privacy loss that each data point in
the entire dataset is willing to tolerate. Yet, in practice, different data
points often have different privacy requirements. Having to set one uniform
privacy level is usually too restrictive, often forcing a learner to guarantee
the stringent privacy requirement, at a large cost to accuracy. To overcome
this limitation, we introduce our novel Personalized-DP Output Perturbation
method (PDP-OP) that enables to train Ridge regression models with individual
per data point privacy levels. We provide rigorous privacy proofs for our PDP-
OP as well as accuracy guarantees for the resulting model. This work is the
first to provide such theoretical accuracy guarantees when it comes to
personalized DP in machine learning, whereas previous work only provided
empirical evaluations. We empirically evaluate PDP-OP on synthetic and real
datasets and with diverse privacy distributions. We show that by enabling each
data point to specify their own privacy requirement, we can significantly
improve the privacy-accuracy trade-offs in DP. We also show that PDP-OP
outperforms the personalized privacy techniques of Jorgensen et al. (2015).

##  1 Introduction

Over the last decade, the amount of private data collected about individuals
has experienced an exponential growth. As the data is used for computing
statistics, training recommender systems, and automated decision-making in
sensitive domains, such as medicine, privacy concerns around this data are
growing. The gold standard for analyzing the data with privacy guarantees is
Differential Privacy (DP) Dwork et al. (2006). DP allows to perform meaningful
analyses of the entire dataset while protecting the privacy of individuals. It
guarantees that if any single individual in a dataset were to change their
data point, the (distribution of) outcomes of the differentially private
mechanism remains roughly the same. The closeness of the outcomes is
parametrized by a privacy parameter $\varepsilon$ that captures the level of
privacy. This $\varepsilon$ represents the maximal privacy loss that any
individual contributing data to the dataset is willing to accept, with small
$\varepsilon$ indicating high levels of privacy.

However, DP comes with a major limitation: It requires to set the privacy
level $\varepsilon$ uniformly for the entire dataset. Implicitly, this
suggests that all individuals whose data is present in the dataset have the
same privacy requirements. Yet, this is not accurate as individuals were shown
to have diverse privacy requirements Jensen et al. (2005); Berendt et al.
(2005); Acquisti and Grossklags (2005). By setting a uniform privacy budget in
DP, this budget must match the individual whose privacy requirements are the
strongest. This means that $\varepsilon$ has to correspond to the highest
privacy requirement in the dataset. Thereby—since the implementation of DP
usually relies on the addition of noise with higher privacy requiring higher
amounts of noise being added—DP often yields unfavorable privacy-accuracy
trade-offs Li and Li (2009); Tramer and Boneh (2020); Bagdasaryan et al.
(2019).

In this paper, we argue standard DP is overly conservative and propose a new
algorithm to train ridge regression with per-individual personalized privacy
guarantees.111In the remainder of this work, we will, without loss of
generality, assume that each data point is contributed by a different
individual. We provide rigorous privacy proofs and accuracy guarantees for our
algorithm, thereby, distinguishing ourselves from prior work on machine
learning with personalized guarantees Alaggan et al. (2015); Jorgensen et al.
(2015); Boenisch et al. (2023b, a) that solely provides empirical evaluations.
Our personalized privacy techniques also differ from that of Boenisch et al.
(2023b, a), as we describe in more details in Section 2.

In summary, we make the following contributions:

  * •

We propose the first personalized DP algorithm specialized to the case of
Ridge regression in Section 3, Algorithm (1).

  * •

We provide rigorous privacy proofs in Section 3.1 and accuracy guarantees in
Section 3.2.

  * •

We perform extensive empirical evaluations in Section 4. We highlight that i)
our algorithm significantly outperforms standard output perturbation-based DP
ridge regression in terms of privacy-accuracy trade-offs on multiple datasets
and diverse privacy distributions in Section 4.1 and Appendix B.1. We also
show that we outperform the personalized privacy technique of Jorgensen et al.
(2015) in Section 4.2 and Appendix B.2.

##  2 Preliminaries and Related Work

#### Differential Privacy.

An algorithm $M$ satisfies $\boldsymbol{(\varepsilon)}$-DP Dwork et al.
(2006), if for any two datasets $D,D^{\prime}\subseteq\mathcal{D}$ that differ
in any one data point $x$, and any set of outputs $R$

$\displaystyle\mathbb{P}\left[M(D)\in R\right]\leq
e^{\varepsilon}\cdot\mathbb{P}\left[M(D^{\prime})\in R\right].$ (1)

This definition provides a theoretical upper bound on the influence that a
single data point can have on the outcome of the analysis over the whole
dataset. The value $\varepsilon\in\mathbb{R}_{+}$ denotes the privacy level;
with lower values corresponding to stronger privacy guarantees.

#### Personalized Privacy.

Personalizing privacy guarantees are highly relevant, given that studies
showed how society consists at least of three different groups of individuals,
requiring strong, average, or weak privacy protection Jensen et al. (2005);
Berendt et al. (2005); Acquisti and Grossklags (2005). Without
personalization, when applying DP to datasets that hold data from individuals
with different privacy requirements, $\varepsilon$ needs to be set to the
lowest $\varepsilon$ encountered among all individuals whose data we choose to
use in our computation. This can often yield unfavorable privacy-utility
trade-offs, due to having to throw away too much data or to have to use a
stringent value of $\varepsilon$ for everyone. Instead, several previous works
concurrently introduced the concept of _personalized_ DP. It was introduced
formally in Alaggan et al. (2015) and Jorgensen et al. (2015) in the context
of central DP; it was also used informally by Cummings et al. (2015) in the
context of mechanism design for data acquisition with local DP. Formally, the
definition of personalized DP is the following:

######  Definition 2.1 ($i$-neighboring).

Two datasets $D$ and $D^{\prime}$ are neighboring with respect to data point
$i$ (or “i-neighbors”) if they differ only in data point $i$.

######  Definition 2.2 (Personalized DP).

A randomized algorithm $\mathcal{M}$ is $\varepsilon_{i}$-differentially
private with respect to data point $i$, if for any outcome set $O\subset
Range\left(\mathcal{M}\right)$ and for all $i$-neighboring databases
$D,D^{\prime}$

$\Pr\left[\mathcal{M}(D)\in
O\right]\leq\exp(\varepsilon_{i})\Pr\left[\mathcal{M}(D^{\prime})\in
O\right].$

Two of the most prevalent techniques for personalized DP are personalized data
sampling and sensitivity pre-processing.

Both methods change how much the output of a computation depends on a
particular data point: the lesser the dependency on a given data point, the
more privacy this point gets. The idea of data sampling for personalized
privacy was introduced by Jorgensen et al. (2015), and later used in the works
of Niu et al. (2021); Boenisch et al. (2023b, a). Data sampling introduces
randomness in the dataset: each data point can be sub-sampled or up-sampled
before being fed into a standard DP algorithm.

Sensitivity pre-processing, which is the approach used in this work, in
contrast, can be implemented deterministically. It modifies the query of
interest to have different sensitivities for different data points, where
sensitivity is a standard notion in DP on how much a computation can change
across neighbouring datasets.

Sensitivity pre-processing for personalized privacy was originally introduced
by Alaggan et al. (2015) through linear pre-processing or “stretching” of the
input data; a caveat of this method is that it requires strong assumptions on
how changing the data changes per-user sensitivity. A general-purpose method
for manipulating the sensitivity of a query while maintaining accuracy is
provided by Cummings and Durfee (2020), but is unfortunately NP-hard to
implement in the general case and is constructive, rather than given in closed
form. Specializations of this method for the case of moment estimation have
been recently used in Fallah et al. (2022); Cummings et al. (2023): both
papers rely on weighted moment estimation, where the weight is lower for data
points with stronger privacy requirements. A difficulty with such re-
weightings is that they often need to be tailored to the specific learning
task at hand. This is the approach we take and challenge we face in this work.
Finally, Li et al. (2017) proposed two partitioning algorithms that first
separate the data in different groups according to privacy requirements, and
then process these groups separately. This approach was shown sub-optimal for
learning-based applications Boenisch et al. (2023b).

#### Private Empirical Risk Minimization.

There has been a significant line of work on making linear regression,
generalized linear models, and empirical risk minimization (ERM)
differentially-private (Chaudhuri and Monteleoni, 2008; Chaudhuri et al.,
2011; Kifer et al., 2012; Bassily et al., 2014; Jain and Thakurta, 2014; Wang,
2018; Bassily et al., 2019; Chen et al., 2020; Song et al., 2020; Cai et al.,
2021; Song et al., 2021; Alabi et al., ; Arora et al., 2022). These papers
focus on standard DP, as opposed to personalized DP, and span a relatively
large number of different techniques. Most relevant to us are the initial
works in this space by Chaudhuri and Monteleoni (2008); Chaudhuri et al.
(2011). In particular, they analyze obtaining DP in regression and ERM through
an _output perturbation_ technique: ERM is first performed non-privately, then
noise is added directly to the non-private estimator. We similarly rely on
output perturbation in this paper, noting that this is a good starting point
to the study of personalized DP in the context of regression. Most recently,
output perturbation saw a new analysis for generalized linear models by Arora
et al. (2022).

##  3 Algorithms and Guarantees for Personalized Privacy in Ridge Regression

#### Our Setup.

Consider a dataset
$\mathcal{D}=\\{(x_{i},y_{i})\in\mathcal{X}\times\mathcal{Y}:i=1,2,\cdots,n\\}$
consisting of a total $n$ data points. We assume that features are bounded;
without loss of generality, we work with $x_{i}\in[0,1]^{d}$ for all
$i\in[n]$. We also assume that the labels are bounded, and w.l.o.g. set
$y_{i}\in[-1,1]$ for all $i\in[n]$. Beyond this, each data point $i\in[n]$ has
a _privacy requirement_ , in the form of a DP parameter $\varepsilon_{i}>0$.
The lower the value of $\varepsilon_{i}$, the more stringent the privacy
requirement of data point $i$, as per Definition 2.2.

Our main focus is Ridge regression. I.e., we are aiming to find a linear model
$x^{\top}\bar{\theta}$, parametrized by $\bar{\theta}$, that predicts the
labels as accurately as possible. Our goal is to find the $\bar{\theta}$ that
minimizes the Ridge loss

$L(\theta,\lambda)=\frac{1}{n}\sum_{i=1}^{n}\left(y_{i}-\theta^{\top}x_{i}\right)^{2}+\lambda\|\theta\|^{2}_{2}.$

However, we cannot release $\bar{\theta}$, as it encodes information about the
dataset ${(x_{i},y_{i})}$. Instead, we provide an estimator $\hat{\theta}$
whose performance on our Ridge loss is good, while at the same time ensuring
that we satisfy DP with parameter $\varepsilon_{i}$ for all data points
$i\in[n]$ _simultaneously_.

#### Our Main Algorithm.

The main idea of our algorithm, “Personalized-Differentially-Private Output
Perturbation” (or “PDP-OP”) is as follows: if we wanted to obtain traditional,
non-personalized DP, we could first compute a non-private estimate
$\bar{\theta}$, then add well-chosen noise $Z$ for privacy with density
$\nu(b)\propto\exp(-\eta\norm{b}_{2})$. This takes inspiration from Chaudhuri
and Monteleoni (2008); Chaudhuri et al. (2011); however, our analysis exhibits
differences due to differences in our estimators to incorporate personalized
DP. Here, to instead obtain personalized DP, we rely on an idea studied by
Cummings and Durfee (2020): manipulating or pre-processing the sensitivity
(i.e., how much a given data point can change the outcome) of our query with
respect to each data point $i$. Our techniques for sensitivity pre-processing
are very different from that of Cummings and Durfee (2020): their method
algorithmically constructs a “good” query with the desired sensitivities (but
is intractable in the general case), while we obtain such a query efficiently
and in closed-form through carefully manipulating the weight given to each
data point in our loss function.

More precisely, our sensitivity pre-processing technique re-weights each data
point $i$ by a weight $w_{i}$. The smaller the weight $w_{i}$, the smaller the
impact the $i$-th data point has on the output model. Intuitively, this means
that lower $w_{i}$’s correspond to less information encoded in the output
$\hat{\theta}$ about data point $i$, and better privacy for $i$. When giving
different $w_{i}$ to different data points, we can then ensure different,
personalized privacy levels for different data points. Our algorithm is given
formally in Algorithm 1. We then show formally in Section 3.1 how to choose
the weights $w_{i}$ and the noise parameter $\eta$ in order to guarantee
personalized DP with respect to privacy preferences
$\varepsilon_{1},\ldots,\varepsilon_{n}$.

Algorithm 1 Personalized-Differentially-Private Output Perturbation (PDP-OP)

Inputs: Dataset
$\mathcal{D}=\\{\left(x_{i},y_{i}\right)~{}\text{for}~{}i\in[n]\\}$; weights
vector $\textbf{w}\geq 0$ with $\sum_{i=1}^{n}w_{i}=1$; noise parameter
$\eta$.
Output: Private estimator $\hat{\theta}$

1: Compute non-private estimate $\bar{\theta}$ as follows:
$\displaystyle\bar{\theta}=\arg\min_{\theta}\sum_{i=1}^{n}w_{i}\left(y_{i}-\theta^{\top}x_{i}\right)^{2}+\lambda\|\theta\|^{2}_{2}.$
(2)

2: Sample $Z$ as a random variable with probability density function
$\propto\exp(-\eta\norm{b}_{2})$

3: Return private estimate $\hat{\theta}=\bar{\theta}+Z$

######  Remark 3.1 (How to sample $Z$).

It is known that for probability density function
$\nu(b)\propto\exp(-\eta\norm{b}_{2})$ for $Z$:

  * •

$\|Z\|_{2}$ follows a Gamma$(\alpha,\beta)$ distribution with $\alpha=d$ and
$\beta=\eta$, which has density $f(r)\propto r^{d-1}\exp{-\eta r}.$222An easy
way to see this informally is the following: the total mass on $\|Z\|_{2}=r$
is proportional to the total mass on all $Z$’s with norm $r$—which is
proportional to $\frac{2\pi^{d/2}}{\Gamma(d/2)}r^{d-1}$ (the surface area of
the $d$-dimensional $\ell_{2}$-sphere)—multiplied by the mass on any single
$Z$ of norm $r$—which is proportional to $\exp{-\eta r}$. A more formal proof,
omitted here, consists in writing the integration for $P[\|Z\|_{2}\leq R]$,
then doing a change of variable to hyper-spherical coordinates in the
corresponding integral.

  * •

For any given value $r\triangleq\|Z\|_{2}$, $Z$ is uniform on the
$\ell_{2}$-sphere of radius $r$. This can be seen immediately as the density
only depends on $\|Z\|$, so all realizations $z$ with the same norm have the
same density.

In turn, to sample $Z$, it suffices to i) sample the radius $R$ from
Gamma$(d,\eta)$, then ii) sample $Y$ uniformly at random from the
$\ell_{2}$-sphere of radius $1$, and set $Z=RY$.

###  3.1 Privacy Guarantees

We now state the personalized privacy guarantee obtained by our algorithm. We
remind the reader that this privacy guarantee relies on the observations being
normalized such that $x_{i}\in[0,1]^{d}$ and $y_{i}\in[-1,1]$ for all
$i\in[n]$:

######  Theorem 3.2.

Fix privacy specifications $\varepsilon_{1},\ldots,\varepsilon_{n}>0$. Let
$B(\lambda)=\min\left(\frac{1}{\sqrt{\lambda}},\frac{\sqrt{d}}{\lambda}\right)$.
Algorithm 1 with parameters
$w_{i}=\frac{\varepsilon_{i}}{\sum_{j=1}^{n}\varepsilon_{j}}$ for all $i$ and
$\eta=\frac{\lambda}{2\sqrt{d}\left(1+\sqrt{d}B(\lambda)\right)}\sum_{j=1}^{n}\varepsilon_{j}$
is $\varepsilon_{i}$-personalized differentially private with respect to data
point $i$ for every $i\in[n]$.

Additionally, we show another version of our privacy guarantee that uses
additional assumptions on the data and on the best regression parameter absent
regularization, when such information is available:

######  Assumption 3.3 (Bounded $\bar{\theta}$).

Let
$\bar{\theta}_{0}=\operatorname*{arg\,min}_{\theta}\sum_{i=1}^{n}w_{i}\left(y_{i}-\theta^{\top}x_{i}\right)^{2}$,
when $\lambda=0$. There is a known constant $B$ such that
$\norm{\bar{\theta}_{0}}_{2}\leq B$.

We incorporate such boundedness assumptions as they have also been used in
previous work, such as Wang (2018); Arora et al. (2022). Our privacy
guarantee, under additional Assumption 3.3, is given by:

######  Theorem 3.4.

Suppose Assumption 3.3 holds. Fix privacy specifications
$\varepsilon_{1},\ldots,\varepsilon_{n}>0$. Algorithm 1 with parameters
$w_{i}=\frac{\varepsilon_{i}}{\sum_{j=1}^{n}\varepsilon_{j}}$ for all $i$ and
$\eta=\frac{\lambda}{2\sqrt{d}(B\sqrt{d}+1)}\sum_{j=1}^{n}\varepsilon_{j}$ is
$\varepsilon_{i}$-personalized differentially private with respect to data
point $i$ for every $i\in[n]$.

We can easily see that if $B\leq
B(\lambda)=\min\left(\frac{1}{\sqrt{\lambda}},\frac{\sqrt{d}}{\lambda}\right)$,
this bound adds noise $Z$ with a bigger parameter $\eta$ compared to in
Theorem 3.2, which corresponds to adding _less_ noise. This will lead to
better accuracy guarantees in regimes in which we put little weight on the
regularization parameter, provided that we know or can estimate such a bound
$B$.

###### Proof Sketch.

The full proof is given in Appendix A.1. The idea of the proof is similar to
that of the output perturbation technique of Chaudhuri et al. (2011), adapted
to Ridge regression and personalized DP. A major difference comes in the fact
that we use different weights $w_{i}$ for different data points. We examine
the first order condition satisfied by $\bar{\theta}$ and note that
$\bar{\theta}$ has a bounded gradient difference across two $i$-neighbouring
datasets. However, unlike Chaudhuri et al. (2011), the gradient difference
here is bounded by a term that is proportional to $w_{i}$ when the databases
are neighbouring in data point $i$. Combined with the fact that the loss
function is strongly convex with strong convexity parameter $2\lambda$,
$\bar{\theta}$ cannot change too much across two neighbouring databases by a
standard argument and bound its $\ell_{2}$-sensitivity by a term proportional
to $w_{i}/\lambda$. Adding well-tailored noise for privacy concludes the
proof. ∎

###  3.2 Accuracy Guarantees

We now provide theoretical bounds on the accuracy of our framework. We note
that we are the first to provide such theoretical accuracy bounds for ridge
regression with personalized DP. The framework of Jorgensen et al. (2015) is
relatively general, but said generality prevents them from obtaining worst-
case theoretical accuracy bounds, and they focus on an empirical evaluation of
the performance (in terms of loss or accuracy) of their sampling framework.

We make the assumption that the label generating process is in fact
approximately linear, which is the main use case in which linear regression
should be used in the first place. This assumption is common in the
literature; it is found for example in the seminal high-dimensional
probability book of Vershynin (2018). Importantly, note that this assumption
is only made in order to characterize the theoretical accuracy of our
framework. Our personalized DP bounds of Section 3.1 crucially do not rely on
Assumption 3.5.

######  Assumption 3.5.

Given a feature vector $x_{i}$, the label $y_{i}$ is given by
$y_{i}=x_{i}^{\top}\theta^{*}+Z_{i}$ where $\theta^{*}\in\mathbb{R}^{d}$ and
the $Z_{i}$’s are independent and identically distributed Gaussian variables
with mean $0$ and standard deviation $\sigma>0$.

We now provide a bound on how well we recover $\theta^{*}$, the true data
generating process, as closely as possible as a function of our dataset and
our choice of privacy parameters. We bound the distance between our estimate
$\hat{\theta}$ and the true data generating parameter $\theta^{*}$ below:

######  Theorem 3.6 (Accuracy of $\hat{\theta}$).

Let $\eta$ be chosen as per Theorems 3.2 absent assumptions, and Theorem 3.4
under Assumption 3.3. For any $\delta>0$, with probability at least
$1-\delta$, we have that for any $\lambda>0$,

$\displaystyle\|\theta^{*}-\hat{\theta}\|_{2}\leq\frac{\norm{\theta^{*}}}{1+\frac{\lambda_{min}\left(\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)}{\lambda}}+\frac{1}{\eta}\left(d+\sqrt{\frac{2d}{\delta}}\right)+\frac{\sigma}{\lambda}\sqrt{\frac{2d}{\delta}}\|\vec{w}\|$

for all $\lambda>0$, where $\vec{w}=(w_{1},\ldots,w_{n})$.

###### Proof.

The proof of Theorem 3.6 is in Appendix A.2. ∎

Our bound starts with a bias term:
$\norm{\theta^{*}}\big{/}\left(1+\lambda_{min}\left(\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)/\lambda\right)$.
This term controls the bias due to Ridge regression itself, independently of
the noise added for privacy and from the noise in the labels, and is
unavoidable due to the nature of Ridge regression. First, in the worst case in
which $\lambda$ grows larger and larger, Ridge regression recovers
$\hat{\theta}\to 0$, and the bias due to regression alone, absent noise and
privacy, would converge to $\theta^{*}$; this is exactly what our bound shows.
Second, when
$\lambda_{min}\left(\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)=0$,
observations are not full-rank, and bias is unavoidable due to the fact that
the unregularized regression problem has several solutions, some of which need
not be close to $\theta^{*}$. However, when
$\lambda_{min}\left(\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)$ becomes
larger, the regression problem absent regularization becomes better
conditioned and easier, and the impact of the Ridge regression parameter
$\lambda$ on the recovered non-private $\bar{\theta}$ is reduced. This is
reflected in our expression, as we see that when
$\lambda_{min}\left(\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)/\lambda$
increases (i.e. $\lambda$ decreases), this bias term starts becoming smaller.
The bias term disappears completely in this case as $\lambda\to 0$; this is to
be expected, as in case we are running unregularized regression under full
rank observations, in which case we know the minimizer is both unique and
unbiased.

The second term, $\frac{1}{\eta}\left(d+\sqrt{\frac{2d}{\delta}}\right)$, is
due to the noise added for privacy with parameter $\eta$. Importantly, note
that this $\eta$ is proportional to $\sum_{j=1}^{n}\varepsilon_{j}$, giving us
an accuracy bound where the privacy dependency that evolves with
$1/\sum_{j=1}^{n}\varepsilon_{j}$. Absent personalization, instead, we would
have to use a common, stringent privacy level of $\min_{j}\varepsilon_{j}$ for
all agents $i$; to so, one would typically weight all data points equally and
add noise with parameter scaling in $\eta\sim n\min_{j}\varepsilon_{j}$ to
guarantee privacy under output perturbation. This would lead to a bound
evolving in $1/n\min_{j}\varepsilon_{j}$. The accuracy bound for personalized
privacy could then be significantly worse when some agents have very stringent
privacy levels: i.e., when $\min_{j}\varepsilon_{j}$ small, but at the same
time the average-case privacy level $\frac{1}{n}\sum_{j}\varepsilon_{j}$ is
more lenient. We show in Section 4 that this effect is not only observed in
toy examples and in our theoretical accuracy bound, but also consistently
across our experimental results.

Further, in the second term, $\eta$—as seen in Theorems 3.2 and 3.4—is an
increasing function of $\lambda$, and the second term is therefore decreasing
in $\lambda$. This is in contrast with the bias term, which increases when
$\lambda$ increase. The idea is that increasing $\lambda$ increases the weight
on the regularization hence increases the bias of our estimator; however, at
the same time, it decreases the amount of noise we need to add for privacy
(bigger $\eta$ means less noise), leading to a smaller variance term due to
the addition of differential privacy. One can in practice pick $\lambda$ to
trade-off these two terms, both experimentally or based on our theoretical
accuracy bound.

Finally, the third term
$\frac{\sigma}{\lambda}\sqrt{\frac{2d}{\delta}}\norm{\vec{w}}$ is due to the
fact that labels are noisy hence there are inaccuracies introduced due to the
fact that linear regression is not a perfectly accurate model for our setting.
As $\sigma$ decreases, the label noise also decreases, the observations become
closer to forming a line, and this term grows smaller. The bigger the value of
$\lambda$, the less the regression estimator depends on the data, and the
lesser the impact of this label noise. Finally, the term has a dependency on
the weights $\vec{w}$: the smaller the norm of $\vec{w}$, the better the
weights are spread out (with the norm being minimized when
$w_{1}=\ldots=w_{n}=1/n$) across data points, and the better the accuracy as
we incorporate information about more and more of the data in our estimator.

##  4 Experiments

In this section, we evaluate the performance of our algorithm experimentally.
Importantly, we highlight that our goal _is not_ to evaluate the performance
of “output perturbation” (which first computes a non-private estimator then
adds noise for privacy) for private regression, as this has been done
extensively in previous work Chaudhuri and Monteleoni (2008); Chaudhuri et al.
(2011). Rather, we highlight the performance of our re-weighting technique, in
particular compared to the absence of data reweighting (which gives the same
level of privacy to all data points) and to the sampling-based technique for
personalized privacy of Jorgensen et al. (2015). For this reason and to
isolate the performance of our re-weighting technique versus the sampling of
Jorgensen et al. (2015), we fix our experimental evaluation to have all
baselines be based on output perturbation techniques333The code is available
at https://github.com/krishnacharya/pp-ridge.

We divide this section into two parts: i) we show how much the addition of
personalized privacy improves accuracy compared to non-personalized privacy;
ii) we compare our results to Jorgensen et al. (2015), and show improvement
both in terms of accuracy and variance of the estimator.

#### Choice of Privacy Budgets.

To validate our personalized privacy setting, we follow a similar segregation
scheme as Alaggan et al. (2015); Jorgensen et al. (2015). We categorize data
points into 3 segments, in order of most stringent to less stringent privacy
requirements: _conservatives_ (high privacy), _mediums_ or _pragmatists_
(medium privacy), and _liberals_ (low privacy). The fraction of conservatives,
mediums, and liberals in the population is denoted by $f_{c}$, $f_{m}$ and
$f_{l}=1-(f_{c}+f_{m})$ respectively. Each segment has their own privacy
parameter denoted respectively $\varepsilon_{c}$, $\varepsilon_{m}$ and
$\varepsilon_{l}$, where $\varepsilon_{c}<\varepsilon_{m}<\varepsilon_{l}$
(remember that lower $\varepsilon$, means stronger privacy requirement). In
our experiments, we assign the personalized privacy budgets to the
conservatives and mediums by uniformly sampling from the ranges
$[\varepsilon_{c},\varepsilon_{m}],[\varepsilon_{m},\varepsilon_{l}]$
respectively. As for the liberals, they all receive the same single highest
privacy budget $\varepsilon_{l}$. This follows Niu et al. (2020); Jorgensen et
al. (2015).

As default values, we set $f_{c}=0.34,f_{m}=0.43,f_{l}=0.23$,
$\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{l}=1.0$ unless
otherwise specified. We provide experiments in Appendix B where we show how
our insights extend as we change these privacy parameters.

#### Synthetic Data Generation.

For the synthetic data, we draw $\theta^{*}$ uniformly over the unit sphere
$S^{d-1}$. Each feature $x$ is drawn uniformly over support $[0,1]^{d}$, and
its corresponding label $y=\frac{x^{\top}\theta^{*}}{\sqrt{d}}$: the label
then satisfies $|y|\leq\frac{1}{\sqrt{d}}\norm{x}_{2}\norm{\theta^{*}}_{2}\leq
1$. We consider perfect linear relationships between $x$ and $y$ with no noise
in the labels (i.e., $\sigma=0$ as per the notations of Section 3.2); we do so
to decouple the effect of linear models being an imperfect hypothesis class
from the performance of our method. We rely on our real dataset described
below, both in the main body and in Appendix B, for situations in which the
relationship between features and labels can only approximately be captured by
a linear model.

#### Real Dataset.

For our experiments on real data, we use the “Medical Cost” dataset Lantz
(2013) which looks at an individual medical cost prediction task. Each
individual’s features are split into three numeric {age, BMI, #children} and
three categorical features {sex, smoker, region}. The dataset also has a real-
valued medical charges column that we use as our label.

Data pre-processing. We use min-max scaling to normalize the numeric features
as well as the label to the range $[0,1]$. For any categorical features, we
use standard one-hot-encoding. To deal with affine rather than simply linear
relationships in the data, we add a $d+1$-th feature to each feature vector
$x$, that corresponds to our model’s intercept.

Metrics. We evaluate the performance of $\hat{\theta}$ on a held-out test set
of size $N_{test}$, using the following metrics : (1) Unregularized test loss:
$\sum_{i=1}^{N_{test}}\frac{1}{N_{test}}(y_{i}-x_{i}^{\top}\hat{\theta})^{2}$
and (2) Regularized test loss:
$\sum_{i=1}^{N_{test}}\frac{1}{N_{test}}(y_{i}-x_{i}^{\top}\hat{\theta})^{2}+\lambda\norm{\hat{\theta}}_{2}^{2}\text{.}$
The $\lambda$ we use in our evaluation is the same $\lambda$ that we use in
our training loss and in Algorithm 1.

###  4.1 Improvements over standard Differential Privacy

Our first results show the improvements in accuracy when we use personalized
DP as opposed to standard (or non-personalized) DP. To do so, we compare to
what we call the _non-personalized_ baseline which provides the same privacy
level $\varepsilon$ to all data points. We let
$\varepsilon^{*}=\min_{i}\varepsilon_{i}$ is chosen to satisfy the most
stringent privacy preferences (remember that smaller $\varepsilon$ means more
privacy) among all data points. To implement this baseline, we simply use
Algorithm 1, but with the privacy preference profile being
$(\varepsilon^{*},\ldots,\varepsilon^{*})$. Note that the weights are all the
same and equal to $1/n$ and the added noise scales as a function of
$\varepsilon^{*}$. Hence our baseline implementation just follows the standard
regression algorithm with output perturbation of Chaudhuri and Monteleoni
(2008) and Chaudhuri et al. (2011).

Table 1 shows the performance of our algorithm versus the non-personalized
baseline across varying regularization $\lambda$, while fixing the other
parameters $f_{c},f_{m},\varepsilon_{c},~{}\varepsilon_{m}$. We note that we
get consistent improvements of several order of magnitudes across all values
of $\lambda$. The improvement is, for example, roughly of an order of
magnitude of $100$ when it comes to both unregularized and regularized mean-
squared error on the test set. This shows that leveraging differing privacy
preferences across differing data points can lead to huge improvements in
terms of privacy-accuracy trade-offs for differential privacy. Table 2 shows
that significant improvements also occur on the real dataset.

| Regularization
---
parameter
Lambda ($\lambda$)
| Unregularized
---
test loss
(PDP-OP)
| Unregularized
---
test loss
(non-personalized)
| Regularized
---
test loss
(PDP-OP)
| Regularized
---
test loss
(non-personalized)
1.00 | $\mathbf{8.54\crossproduct 10^{2}}$ | $4.60\crossproduct 10^{5}$ | $\mathbf{3.32\crossproduct 10^{3}}$ | $1.77\crossproduct 10^{6}$
3.00 | $\mathbf{3.88\crossproduct 10^{1}}$ | $2.08\crossproduct 10^{4}$ | $\mathbf{3.82\crossproduct 10^{2}}$ | $2.03\crossproduct 10^{5}$
5.00 | $\mathbf{9.78}$ | $5.20\crossproduct 10^{3}$ | $\mathbf{1.50\crossproduct 10^{2}}$ | $8.08\crossproduct 10^{4}$
7.00 | $\mathbf{3.81}$ | $2.06\crossproduct 10^{3}$ | $\mathbf{8.36\crossproduct 10^{1}}$ | $4.46\crossproduct 10^{4}$
10.00 | $\mathbf{1.49}$ | $8.18\crossproduct 10^{2}$ | $\mathbf{4.58\crossproduct 10^{1}}$ | $2.45\crossproduct 10^{4}$
15.00 | $\mathbf{5.30\crossproduct 10^{-1}}$ | $2.75\crossproduct 10^{2}$ | $\mathbf{2.34\crossproduct 10^{1}}$ | $1.26\crossproduct 10^{4}$
20.00 | $\mathbf{2.54\crossproduct 10^{-1}}$ | $1.29\crossproduct 10^{2}$ | $\mathbf{1.49\crossproduct 10^{1}}$ | $8.01\crossproduct 10^{3}$
25.00 | $\mathbf{1.44\crossproduct 10^{-1}}$ | $7.45\crossproduct 10^{1}$ | $\mathbf{1.07\crossproduct 10^{1}}$ | $5.63\crossproduct 10^{3}$
50.00 | $\mathbf{2.28\crossproduct 10^{-2}}$ | $1.11\crossproduct 10^{1}$ | $\mathbf{3.06}$ | $1.64\crossproduct 10^{3}$
75.00 | $\mathbf{9.35\crossproduct 10^{-3}}$ | 3.78 | $\mathbf{1.56}$ | $8.29\crossproduct 10^{2}$
100.00 | $\mathbf{5.82\crossproduct 10^{-3}}$ | 1.80 | $\mathbf{1.01}$ | $5.36\crossproduct 10^{2}$
125.00 | $\mathbf{4.39\crossproduct 10^{-3}}$ | 1.06 | $\mathbf{7.37\crossproduct 10^{-1}}$ | $3.91\crossproduct 10^{2}$
150.00 | $\mathbf{3.68\crossproduct 10^{-3}}$ | $6.79\crossproduct 10^{-1}$ | $\mathbf{5.73\crossproduct 10^{-1}}$ | $3.05\crossproduct 10^{2}$
175.00 | $\mathbf{3.33\crossproduct 10^{-3}}$ | $4.76\crossproduct 10^{-1}$ | $\mathbf{4.67\crossproduct 10^{-1}}$ | $2.49\crossproduct 10^{2}$
200.00 | $\mathbf{3.09\crossproduct 10^{-3}}$ | $3.64\crossproduct 10^{-1}$ | $\mathbf{3.97\crossproduct 10^{-1}}$ | $2.10\crossproduct 10^{2}$

Table 1: Loss of PDP-OP compared to standard DP on the synthetic dataset with
$d=30,n=100$, keeping
$\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{l}=1.0,f_{c}=0.34,f_{m}=0.43,f_{l}=0.23$.

| Regularization
---
parameter
Lambda ($\lambda$)
| Unregularized
---
test loss
(PDP-OP)
| Unregularized
---
test loss
(non-personalized)
| Regularized
---
test loss
(PDP-OP)
| Regularized
---
test loss
(non-personalized)
0.01 | $\mathbf{1.19\crossproduct 10^{5}}$ | $2.18\crossproduct 10^{8}$ | $\mathbf{1.22\crossproduct 10^{5}}$ | $2.31\crossproduct 10^{8}$
0.05 | $\mathbf{1.03\crossproduct 10^{3}}$ | $1.89\crossproduct 10^{6}$ | $\mathbf{1.16\crossproduct 10^{3}}$ | $2.12\crossproduct 10^{6}$
0.10 | $\mathbf{1.34\crossproduct 10^{2}}$ | $2.49\crossproduct 10^{5}$ | $\mathbf{1.70\crossproduct 10^{2}}$ | $3.08\crossproduct 10^{5}$
0.50 | $\mathbf{1.30}$ | $2.40\crossproduct 10^{3}$ | $\mathbf{3.03}$ | $5.52\crossproduct 10^{3}$
0.60 | $\mathbf{8.10\crossproduct 10^{-1}}$ | $1.47\crossproduct 10^{3}$ | $\mathbf{2.02}$ | $3.65\crossproduct 10^{3}$
0.70 | $\mathbf{5.29\crossproduct 10^{-1}}$ | $9.26\crossproduct 10^{2}$ | $\mathbf{1.47}$ | $2.61\crossproduct 10^{3}$
0.80 | $\mathbf{3.78\crossproduct 10^{-1}}$ | $6.36\crossproduct 10^{2}$ | $\mathbf{1.11}$ | $1.98\crossproduct 10^{3}$
0.90 | $\mathbf{2.78\crossproduct 10^{-1}}$ | $4.59\crossproduct 10^{2}$ | $\mathbf{8.79\crossproduct 10^{-1}}$ | $1.54\crossproduct 10^{3}$
1.00 | $\mathbf{2.15\crossproduct 10^{-1}}$ | $3.45\crossproduct 10^{2}$ | $\mathbf{7.12\crossproduct 10^{-1}}$ | $1.24\crossproduct 10^{3}$
2.00 | $\mathbf{6.80\crossproduct 10^{-2}}$ | $5.18\crossproduct 10^{1}$ | $\mathbf{2.26\crossproduct 10^{-1}}$ | $3.19\crossproduct 10^{2}$
3.00 | $\mathbf{5.52\crossproduct 10^{-2}}$ | $1.73\crossproduct 10^{1}$ | $\mathbf{1.39\crossproduct 10^{-1}}$ | $1.52\crossproduct 10^{2}$
5.00 | $\mathbf{5.54\crossproduct 10^{-2}}$ | 4.49 | $\mathbf{9.65\crossproduct 10^{-2}}$ | $6.25\crossproduct 10^{1}$

Table 2: Loss of PDP-OP compared to standard DP on the Medical cost dataset,
keeping
$\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{l}=1.0,f_{c}=0.34,f_{m}=0.43,f_{l}=0.23$.

Appendix B.1 provides more experiments where we vary parameters
$f_{c},~{}\varepsilon_{c},~{}\varepsilon_{m},~{}n$ on the synthetic and real
datasets.

###  4.2 Comparison to Jorgensen et al. (2015)

| Regularization
---
parameter
Lambda ($\lambda$)
| Unregularized
---
test loss
(PDP-OP)
| Unregularized
---
test loss
(Jorgensen max)
| Unregularized
---
test loss
(Jorgensen mean)
| Unregularized
---
non-private
test loss
| Regularized
---
test loss
(PDP-OP)
| Regularized
---
test loss
(Jorgensen max)
| Regularized
---
test loss
(Jorgensen mean)
| Regularized
---
non-private
test loss
1.00 | $\mathbf{8.54\crossproduct 10^{2}}$ | $1.09\crossproduct 10^{3}$ | $1.89\crossproduct 10^{3}$ | $5.73\crossproduct 10^{-32}$ | $\mathbf{3.32\crossproduct 10^{3}}$ | $4.16\crossproduct 10^{3}$ | $7.55\crossproduct 10^{3}$ | $2.01\crossproduct 10^{-3}$
3.00 | $\mathbf{3.88\crossproduct 10^{1}}$ | $4.82\crossproduct 10^{1}$ | $8.64\crossproduct 10^{1}$ | $5.73\crossproduct 10^{-32}$ | $\mathbf{3.82\crossproduct 10^{2}}$ | $4.79\crossproduct 10^{2}$ | $8.64\crossproduct 10^{2}$ | $2.11\crossproduct 10^{-3}$
5.00 | $\mathbf{9.78}$ | $1.21\crossproduct 10^{1}$ | $2.15\crossproduct 10^{1}$ | $5.73\crossproduct 10^{-32}$ | $\mathbf{1.50\crossproduct 10^{2}}$ | $1.89\crossproduct 10^{2}$ | $3.40\crossproduct 10^{2}$ | $2.17\crossproduct 10^{-3}$
7.00 | $\mathbf{3.81}$ | 4.81 | 8.85 | $5.73\crossproduct 10^{-32}$ | $\mathbf{8.36\crossproduct 10^{1}}$ | $1.05\crossproduct 10^{2}$ | $1.89\crossproduct 10^{2}$ | $2.20\crossproduct 10^{-3}$
10.00 | $\mathbf{1.49}$ | 1.88 | 3.44 | $5.73\crossproduct 10^{-32}$ | $\mathbf{4.58\crossproduct 10^{1}}$ | $5.75\crossproduct 10^{1}$ | $1.03\crossproduct 10^{2}$ | $2.24\crossproduct 10^{-3}$
15.00 | $\mathbf{5.30\crossproduct 10^{-1}}$ | $6.61\crossproduct 10^{-1}$ | 1.16 | $5.73\crossproduct 10^{-32}$ | $\mathbf{2.34\crossproduct 10^{1}}$ | $2.97\crossproduct 10^{1}$ | $5.33\crossproduct 10^{1}$ | $2.28\crossproduct 10^{-3}$
20.00 | $\mathbf{2.54\crossproduct 10^{-1}}$ | $3.12\crossproduct 10^{-1}$ | $5.64\crossproduct 10^{-1}$ | $5.73\crossproduct 10^{-32}$ | $\mathbf{1.49\crossproduct 10^{1}}$ | $1.87\crossproduct 10^{1}$ | $3.39\crossproduct 10^{1}$ | $2.31\crossproduct 10^{-3}$
25.00 | $\mathbf{1.44\crossproduct 10^{-1}}$ | $1.81\crossproduct 10^{-2}$ | $3.27\crossproduct 10^{-1}$ | $5.73\crossproduct 10^{-32}$ | $\mathbf{1.07\crossproduct 10^{1}}$ | $1.31\crossproduct 10^{1}$ | $2.39\crossproduct 10^{1}$ | $2.33\crossproduct 10^{-3}$
50.00 | $\mathbf{2.28\crossproduct 10^{-2}}$ | $2.82\crossproduct 10^{-2}$ | $4.92\crossproduct 10^{-2}$ | $5.73\crossproduct 10^{-32}$ | $\mathbf{3.06}$ | 3.83 | 6.95 | $2.37\crossproduct 10^{-3}$
75.00 | $\mathbf{9.35\crossproduct 10^{-3}}$ | $1.12\crossproduct 10^{-2}$ | $1.81\crossproduct 10^{-2}$ | $5.73\crossproduct 10^{-32}$ | $\mathbf{1.56}$ | 1.95 | 3.56 | $2.39\crossproduct 10^{-3}$
100.00 | $\mathbf{5.82\crossproduct 10^{-3}}$ | $6.61\crossproduct 10^{-3}$ | $1.01\crossproduct 10^{-2}$ | $5.73\crossproduct 10^{-32}$ | $\mathbf{1.01}$ | 1.26 | 2.28 | $2.40\crossproduct 10^{-3}$
200.00 | $\mathbf{3.09\crossproduct 10^{-3}}$ | $3.25\crossproduct 10^{-3}$ | $3.92\crossproduct 10^{-3}$ | $5.73\crossproduct 10^{-32}$ | $\mathbf{3.97\crossproduct 10^{-1}}$ | $4.97\crossproduct 10^{-1}$ | $9.02\crossproduct 10^{-1}$ | $2.42\crossproduct 10^{-3}$
300.00 | $\mathbf{2.68\crossproduct 10^{-3}}$ | $2.76\crossproduct 10^{-3}$ | $3.04\crossproduct 10^{-3}$ | $5.73\crossproduct 10^{-32}$ | $\mathbf{2.42\crossproduct 10^{-1}}$ | $3.02\crossproduct 10^{-1}$ | $5.46\crossproduct 10^{-1}$ | $2.42\crossproduct 10^{-3}$
400.00 | $\mathbf{2.56\crossproduct 10^{-3}}$ | $2.60\crossproduct 10^{-3}$ | $2.76\crossproduct 10^{-3}$ | $5.73\crossproduct 10^{-32}$ | $\mathbf{1.75\crossproduct 10^{-1}}$ | $2.16\crossproduct 10^{-1}$ | $3.92\crossproduct 10^{-1}$ | $2.42\crossproduct 10^{-3}$
500.00 | $\mathbf{2.51\crossproduct 10^{-3}}$ | $2.54\crossproduct 10^{-3}$ | $2.62\crossproduct 10^{-3}$ | $5.73\crossproduct 10^{-32}$ | $\mathbf{1.36\crossproduct 10^{-1}}$ | $1.70\crossproduct 10^{-1}$ | $3.06\crossproduct 10^{-1}$ | $2.43\crossproduct 10^{-3}$

Table 3: Lower loss compared to Jorgensen et al. (2015) on the synthetic
dataset with $d=30,~{}n=100$, keeping
$\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{l}=1.0,f_{c}=0.34,f_{m}=0.43,f_{l}=0.23$.

| Regularization
---
parameter
Lambda ($\lambda$)
| Unregularized
---
test loss
(PDP-OP)
| Unregularized
---
test loss
(Jorgensen max)
| Unregularized
---
test loss
(Jorgensen mean)
| Unregularized
---
non-private
test loss
| Regularized
---
test loss
(PDP-OP)
| Regularized
---
test loss
(Jorgensen max)
| Regularized
---
test loss
(Jorgensen mean)
| Regularized
---
non-private
test loss
0.01 | $\mathbf{1.19\crossproduct 10^{5}}$ | $1.50\crossproduct 10^{5}$ | $2.87\crossproduct 10^{5}$ | $9.43\crossproduct 10^{-3}$ | $\mathbf{1.22\crossproduct 10^{5}}$ | $1.52\crossproduct 10^{5}$ | $2.93\crossproduct 10^{5}$ | $1.08\crossproduct 10^{-2}$
0.05 | $\mathbf{1.03\crossproduct 10^{3}}$ | $1.26\crossproduct 10^{3}$ | $2.43\crossproduct 10^{3}$ | $9.43\crossproduct 10^{-3}$ | $\mathbf{1.16\crossproduct 10^{3}}$ | $1.42\crossproduct 10^{3}$ | $2.75\crossproduct 10^{3}$ | $1.51\crossproduct 10^{-2}$
0.10 | $\mathbf{1.34\crossproduct 10^{2}}$ | $1.66\crossproduct 10^{2}$ | $3.14\crossproduct 10^{2}$ | $9.43\crossproduct 10^{-3}$ | $\mathbf{1.70\crossproduct 10^{2}}$ | $2.11\crossproduct 10^{2}$ | $4.00\crossproduct 10^{2}$ | $1.90\crossproduct 10^{-2}$
0.50 | $\mathbf{1.30}$ | $1.67$ | 3.10 | $9.43\crossproduct 10^{-3}$ | $\mathbf{3.03}$ | 3.80 | 7.19 | $3.46\crossproduct 10^{-2}$
0.60 | $\mathbf{8.10\crossproduct 10^{-1}}$ | $9.89\crossproduct 10^{-1}$ | 1.85 | $9.43\crossproduct 10^{-3}$ | $\mathbf{2.02}$ | 2.50 | 4.76 | $3.67\crossproduct 10^{-2}$
0.70 | $\mathbf{5.29\crossproduct 10^{-1}}$ | $6.55\crossproduct 10^{-1}$ | 1.23 | $9.43\crossproduct 10^{-3}$ | $\mathbf{1.47}$ | 1.80 | 3.43 | $3.86\crossproduct 10^{-2}$
0.80 | $\mathbf{3.78\crossproduct 10^{-1}}$ | $4.65\crossproduct 10^{-1}$ | $8.71\crossproduct 10^{-1}$ | $9.43\crossproduct 10^{-3}$ | $\mathbf{1.11}$ | 1.39 | 2.63 | $4.02\crossproduct 10^{-2}$
0.90 | $\mathbf{2.78\crossproduct 10^{-1}}$ | $3.42\crossproduct 10^{-1}$ | $6.30\crossproduct 10^{-1}$ | $9.43\crossproduct 10^{-3}$ | $\mathbf{8.79\crossproduct 10^{-1}}$ | 1.08 | 2.03 | $4.17\crossproduct 10^{-2}$
1.00 | $\mathbf{2.15\crossproduct 10^{-1}}$ | $2.61\crossproduct 10^{-1}$ | $4.76\crossproduct 10^{-1}$ | $9.43\crossproduct 10^{-3}$ | $\mathbf{7.12\crossproduct 10^{-1}}$ | $8.70\crossproduct 10^{-1}$ | 1.62 | $4.30\crossproduct 10^{-2}$
2.00 | $\mathbf{6.80\crossproduct 10^{-2}}$ | $7.53\crossproduct 10^{-2}$ | $1.06\crossproduct 10^{-1}$ | $9.43\crossproduct 10^{-3}$ | $\mathbf{2.26\crossproduct 10^{-1}}$ | $2.65\crossproduct 10^{-1}$ | $4.59\crossproduct 10^{-1}$ | $5.19\crossproduct 10^{-2}$
3.00 | $\mathbf{5.52\crossproduct 10^{-2}}$ | $5.72\crossproduct 10^{-2}$ | $6.87\crossproduct 10^{-2}$ | $9.43\crossproduct 10^{-3}$ | $\mathbf{1.39\crossproduct 10^{-1}}$ | $1.59\crossproduct 10^{-1}$ | $2.52\crossproduct 10^{-1}$ | $5.69\crossproduct 10^{-2}$
5.00 | $\mathbf{5.54\crossproduct 10^{-2}}$ | $5.61\crossproduct 10^{-2}$ | $5.89\crossproduct 10^{-2}$ | $9.43\crossproduct 10^{-3}$ | $\mathbf{9.65\crossproduct 10^{-2}}$ | $1.05\crossproduct 10^{-1}$ | $1.43\crossproduct 10^{-1}$ | $6.27\crossproduct 10^{-2}$

Table 4: Lower loss compared to Jorgensen et al. (2015) on the MedicalCost
dataset, keeping
$\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{l}=1.0,f_{c}=0.34,f_{m}=0.43,f_{l}=0.23$.

((a))

((b))

Figure 1: Lower standard deviation compared to Jorgensen et al. (2015) on the
synthetic dataset, while varying the regularization parameter $\lambda$,
keeping
$\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{l}=1.0,f_{c}=0.34,f_{m}=0.43,f_{l}=0.23$.

((a))

((b))

Figure 2: Lower standard deviation compared to Jorgensen et al. (2015) on the
Medical cost dataset, while varying the regularization parameter $\lambda$,
keeping
$\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{l}=1.0,f_{c}=0.34,f_{m}=0.43,f_{l}=0.23$.

#### Experimental setup.

We compare our approach to that of Jorgensen et al. (2015), who proposed the
first algorithm for personalized differential privacy in the central privacy
model. Their approach is the following: first, they pick a threshold $t$.
Then, they sample each data point $i$ in $D$ with probability
$\frac{\exp{\varepsilon_{i}}-1}{\exp{t}-1}$ if $\varepsilon_{i}<t$, and
probability $1$ otherwise. Lastly, they run a standard non-personalized
algorithm that is $t$-differentially private. We fix the non-personalized
algorithm to follow the output perturbation technique described in Chaudhuri
and Monteleoni (2008); Chaudhuri et al. (2011) to keep comparisons apple-to-
apple and only compare the impact of our re-weighting versus the thresholding
then sub-sampling approach of Jorgensen et al. (2015). We implement the non-
personalized estimator as per the baseline described in Section 4.1. For the
choice of $t$, we try out both $t=\max_{i}\varepsilon_{i}$ (that we refer to
as “Jorgensen max” or “max threshold”) and
$t=\frac{1}{n}\sum_{i}\varepsilon_{i}$ (that refer to as “Jorgensen mean” or
“mean threshold”). Both these choices of $t$ were proposed by Jorgensen et al.
(2015) itself.

In the rest of this section, we present our experimental results. We note that
our framework consistently leads to improved performance over Jorgensen et al.
(2015). This is seen in two ways: first, our unregularized and regularized
losses are consistently lower than those of Jorgensen for the vast majority of
choices of instance parameters and of regularization parameter $\lambda$. This
show that our re-weighting method is consistently more accurate compared to
the subsampling method of Jorgensen et al. (2015) when it comes to accuracy.
Beyond this, we also note that our results are more consistent: the standard
deviation of the loss of our technique is also lower than that of Jorgensen et
al. (2015). I.e., our results are more consistent across different runs of the
algorithms and different realizations of the noise.

Intuitively, one of the advantages of our technique over that of Jorgensen et
al. (2015) is that by re-weighting instead of sampling, we do not discard any
of our dataset; we believe this is one potential source of improvement.
Another, more subtle reason, may be that our framework adds all noise $Z$
centrally, at the end of the computation, while Jorgensen et al. (2015) adds
noise both locally (when sub-sampling data points) and centrally. It is well
understood that adding noise centrally (i.e., within the computation) in
differential privacy leads to better privacy-accuracy trade-offs than adding
noise locally (i.e., at the level of each data point), which may be another
reason for our improvements.

#### Improvements in loss.

Table 3 provides a snapshot of our performance versus that of the baseline of
Jorgensen et al. (2015), for our default choice of privacy parameters. We
perform consistently better than Jorgensen et al. (2015) across both our
metrics (unregularized and regularized loss), with improvements in loss of up
to roughly $20$ percent under the max threshold. Jorgensen et al. (2015)’s
results when using the mean threshold instead are consistently worse. Table 4
shows that similar insights hold on our real dataset. We provide additional
experiments where we change the parameters of the problem such as
$f_{c},~{}\varepsilon_{c},~{}\varepsilon_{m},~{}n$ and when we consider our
real dataset in Appendix B.2.

#### Improvements in variability of the results.

Figure 1 and 2 show the standard deviation of our loss compared to that of
Jorgensen et al. (2015), estimated across $10,000$ runs for each technique on
the synthetic and real datasets respectively. The figure clearly highlights
how our method exhibits less variability, leading to more consistent results
across different runs and realizations of the noise.

We also provide additional experiments where we change the parameters of the
problem such as $f_{c},~{}\varepsilon_{c},~{}\varepsilon_{m},~{}n$ and when we
consider our real dataset in Appendix B.2, and note there that our insights
still hold across these experiments.

##  5 Conclusion and Future Work

We proposed a new algorithm, Personalized-DP Output Perturbation (PDP-OP),
which allows to train Ridge regression models with individual per-data point
privacy requirements. We formally prove PDP-OP’s personalized privacy
guarantees and provide rigorous and theoretical results for the accuracy
guarantees of our framework. We are in fact the first to provide a theoretical
accuracy guarantee for personalized-DP methods in machine learning, to the
best of our knowledge. Our empirical evaluation on synthetic and real datasets
highlights that PDP-OP significantly outperforms non-personalized DP,
highlighting the need for personalized DP to vastly improve privacy-accuracy
trade-offs in private ML. We also show that we outperform previous techniques
for personalized DP, showing the advantages of using re-weighting over sub-
sampling techniques.

The current paper aims to provide initial algorithms for personalized DP
tailored to the case of Ridge regression. We chose to use _output
perturbation_ as a simple starting point to provide initial insights and
algorithms into personalized DP, and the benefits of data re-weighting over
data sub-sampling. We, however, believe that there is still some leeway to
improve the privacy-accuracy trade-offs of linear regression with personalized
DP. In future work, we will incorporate our re-weighting technique with more
advanced techniques for private regression, such as _objective perturbation_ ,
_summary statistic perturbation_ , or _private gradient descent_ (see related
work for more details and examples).

## References

  * Acquisti and Grossklags (2005) A. Acquisti and J. Grossklags.  Privacy and rationality in individual decision making.  _IEEE Security & Privacy_, 3(1):26–33, 2005.  doi: 10.1109/MSP.2005.22.
  * (2) Daniel Alabi, Audra McMillan, Jayshree Sarathy, Adam Smith, and Salil Vadhan.  Differentially private simple linear regression.  _Proceedings on Privacy Enhancing Technologies_ , 2022(2):184–204.
  * Alaggan et al. (2015) Mohammad Alaggan, Sébastien Gambs, and Anne-Marie Kermarrec.  Heterogeneous differential privacy.  _arXiv preprint arXiv:1504.06998_ , 2015.
  * Arora et al. (2022) Raman Arora, Raef Bassily, Cristóbal Guzmán, Michael Menart, and Enayat Ullah.  Differentially private generalized linear models revisited.  _Advances in Neural Information Processing Systems_ , 35:22505–22517, 2022.
  * Bagdasaryan et al. (2019) Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov.  Differential privacy has disparate impact on model accuracy.  _Advances in neural information processing systems_ , 32, 2019.
  * Bassily et al. (2014) Raef Bassily, Adam Smith, and Abhradeep 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.
  * Bassily et al. (2019) Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta.  Private stochastic convex optimization with optimal rates.  _Advances in neural information processing systems_ , 32, 2019.
  * Berendt et al. (2005) Bettina Berendt, Oliver Günther, and Sarah Spiekermann.  Privacy in e-commerce: Stated preferences vs. actual behavior.  _Communications of the ACM_ , 48(4):101–106, 2005.
  * Boenisch et al. (2023a) Franziska Boenisch, Christopher Mühl, Adam Dziedzic, Roy Rinberg, and Nicolas Papernot.  Have it your way: Individualized privacy assignment for dp-sgd.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023a.  URL https://openreview.net/forum?id=XXPzBhOs4f.
  * Boenisch et al. (2023b) Franziska Boenisch, Christopher Mühl, Roy Rinberg, Jannis Ihrig, and Adam Dziedzic.  Individualized pate: Differentially private machine learning with individual privacy guarantees.  In _23rd Privacy Enhancing Technologies Symposium (PoPETs)_ , 2023b.
  * Cai et al. (2021) T Tony Cai, Yichen Wang, and Linjun Zhang.  The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy.  _The Annals of Statistics_ , 49(5):2825–2850, 2021.
  * Chaudhuri and Monteleoni (2008) Kamalika Chaudhuri and Claire Monteleoni.  Privacy-preserving logistic regression.  _Advances in neural information processing systems_ , 21, 2008.
  * Chaudhuri et al. (2011) Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate.  Differentially private empirical risk minimization.  _Journal of Machine Learning Research_ , 12(3), 2011.
  * Chen et al. (2020) Xiangyi Chen, Steven Z Wu, and Mingyi Hong.  Understanding gradient clipping in private sgd: A geometric perspective.  _Advances in Neural Information Processing Systems_ , 33:13773–13782, 2020.
  * Cummings and Durfee (2020) Rachel Cummings and David Durfee.  Individual sensitivity preprocessing for data privacy.  In _Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 528–547. SIAM, 2020.
  * Cummings et al. (2015) Rachel Cummings, Katrina Ligett, Aaron Roth, Zhiwei Steven Wu, and Juba Ziani.  Accuracy for sale: Aggregating data with a variance constraint.  In _Proceedings of the 2015 conference on innovations in theoretical computer science_ , pages 317–324, 2015.
  * Cummings et al. (2023) Rachel Cummings, Hadi Elzayn, Vasilis Gkatzelis, Emmanouil Pountourakis, and Juba Ziani.  Optimal data acquisition with privacy-aware agents.  In _First IEEE Conference on Secure and Trustworthy Machine Learning_ , 2023.
  * Dwork et al. (2006) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In _Theory of cryptography conference_ , pages 265–284. Springer, 2006.
  * Fallah et al. (2022) Alireza Fallah, Ali Makhdoumi, Azarakhsh Malekian, and Asuman Ozdaglar.  Optimal and differentially private data acquisition: Central and local mechanisms.  In _Proceedings of the 2022 ACM Conference on Economics and Computation_ , page 1141, 2022.
  * Jain and Thakurta (2014) Prateek Jain and Abhradeep Guha Thakurta.  (near) dimension independent risk bounds for differentially private learning.  In _International Conference on Machine Learning_ , pages 476–484. PMLR, 2014.
  * Jensen et al. (2005) Carlos Jensen, Colin Potts, and Christian Jensen.  Privacy practices of internet users: Self-reports versus observed behavior.  _International Journal of Human-Computer Studies_ , 63(1-2):203–227, 2005.
  * Jorgensen et al. (2015) Zach Jorgensen, Ting Yu, and Graham Cormode.  Conservative or liberal? personalized differential privacy.  In _2015 IEEE 31st International Conference on Data Engineering_ , pages 1023–1034, 2015.  doi: 10.1109/ICDE.2015.7113353.
  * Kifer et al. (2012) Daniel Kifer, Adam Smith, and Abhradeep Thakurta.  Private convex empirical risk minimization and high-dimensional regression.  In _Conference on Learning Theory_ , pages 25–1. JMLR Workshop and Conference Proceedings, 2012.
  * Lantz (2013) Brett Lantz.  Medical Cost Personal Datasets — kaggle.com, 2013.  URL https://www.kaggle.com/datasets/mirichoi0218/insurance.
  * Li et al. (2017) Haoran Li, Li Xiong, Zhanglong Ji, and Xiaoqian Jiang.  Partitioning-based mechanisms under personalized differential privacy.  In _Pacific-Asia Conference on Knowledge Discovery and Data Mining_ , pages 615–627. Springer, 2017.
  * Li and Li (2009) Tiancheng Li and Ninghui Li.  On the tradeoff between privacy and utility in data publishing.  In _Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 517–526, 2009.
  * Niu et al. (2020) Ben Niu, Yahong Chen, Boyang Wang, Jin Cao, and Fenghua Li.  Utility-aware exponential mechanism for personalized differential privacy.  In _2020 IEEE Wireless Communications and Networking Conference (WCNC)_ , pages 1–6, 2020.  doi: 10.1109/WCNC45663.2020.9120532.
  * Niu et al. (2021) Ben Niu, Yahong Chen, Boyang Wang, Zhibo Wang, Fenghua Li, and Jin Cao.  Adapdp: Adaptive personalized differential privacy.  In _IEEE INFOCOM 2021-IEEE Conference on Computer Communications_ , pages 1–10. IEEE, 2021.
  * Song et al. (2020) Shuang Song, Om Thakkar, and Abhradeep Thakurta.  Characterizing private clipped gradient descent on convex generalized linear problems.  _arXiv preprint arXiv:2006.06783_ , 2020.
  * Song et al. (2021) Shuang Song, Thomas Steinke, Om Thakkar, and Abhradeep Thakurta.  Evading the curse of dimensionality in unconstrained private glms.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2638–2646. PMLR, 2021.
  * Tramer and Boneh (2020) Florian Tramer and Dan Boneh.  Differentially private learning needs better features (or much more data).  In _International Conference on Learning Representations_ , 2020.
  * Vershynin (2018) Roman Vershynin.  _High-dimensional probability: An introduction with applications in data science_ , volume 47.  Cambridge university press, 2018.
  * Wang (2018) Yu-Xiang Wang.  Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain.  _arXiv preprint arXiv:1803.02596_ , 2018.

##  Appendix A Proof of Main Results

###  A.1 Full Proof of Theorems 3.2 and 3.4

#### Preliminaries: Bound on $\|\bar{\theta}\|$ for Algorithm 1

First, we show that the norm of $\bar{\theta}$ is bounded for Algorithm 1.
This bound will be useful in bounding the gradient difference across two
neighbouring databases in the proof of the privacy guarantee of Algorithm 1.

######  Lemma A.1.

For any $\sum_{i=1}^{n}w_{i}=1,w_{i}\geq 0$, the unconstrained minimizer of
(2), $\bar{\theta}$, satisfies:

$\norm{\bar{\theta}}_{2}\leq\frac{1}{\sqrt{\lambda}}.$

###### Proof.

Let the weighted loss be defined as:

$L_{w}(\theta)\triangleq\sum_{i=1}^{n}w_{i}\left(y_{i}-\theta^{\top}x_{i}\right)^{2}+\lambda\|\theta\|^{2}_{2}.$

For any $\theta\in\mathbb{R}^{d}$, $L_{w}(\bar{\theta})\leq L_{w}(\theta)$.
Therefore,

$\lambda\norm{\bar{\theta}}^{2}\leq L_{w}(\bar{\theta})\leq
L_{w}(0)=\sum_{i=1}^{n}w_{i}y_{i}^{2}\leq 1.$

∎

######  Lemma A.2.

For any $\sum_{i=1}^{n}w_{i}=1,w_{i}\geq 0$, the unconstrained minimizer of
(2), $\bar{\theta}$, satisfies
$\norm{\bar{\theta}}_{2}\leq\frac{\sqrt{d}}{\lambda}$.

###### Proof.

We first find the closed form for $\bar{\theta}$. $\bar{\theta}$ is simply the
unique solution to the unconstrained minimization problem

$\operatorname*{arg\,min}_{\theta\in\mathbb{R}^{d}}\sum_{i=1}^{n}w_{i}\left(y_{i}-\theta^{\top}x_{i}\right)^{2}+\lambda\|\theta\|^{2}_{2}.$

Therefore,

$\bar{\theta}=\operatorname*{arg\,min}_{\theta\in\mathbb{R}^{d}}\sum_{i=1}^{n}w_{i}\left(y_{i}-\theta^{\top}x_{i}\right)^{2}+\lambda\|\theta\|^{2}_{2}.$

Taking the first order-condition, we note that we must have

$-2\sum_{i=1}^{n}w_{i}x_{i}\left(y_{i}-x_{i}^{\top}\bar{\theta}\right)+2\lambda\theta=0.$

This can be rewritten as

$2\left(\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}+\lambda
I\right)\bar{\theta}=2\sum_{i=1}^{n}w_{i}x_{i}y_{i}.$

Because $\lambda>0$ and $\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}$ is positive
semi-definite, $\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}+\lambda I$ is invertible,
and we obtain the following closed-form expression for $\bar{\theta}$:

$\bar{\theta}=\left(\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}+\lambda
I\right)^{-1}\sum_{i=1}^{n}w_{i}x_{i}y_{i}.$

Taking the $\ell_{2}$-norm of both sides, we obtain, letting
$\lambda_{min}(M),~{}\lambda_{max}(M)$ respectively denote the lowest and
highest eigenvalues of any given matrix $M$:

$\displaystyle\norm{\bar{\theta}}_{2}$
$\displaystyle\leq\lambda_{max}\left(\left(\lambda
I+\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)^{-1}\right)\norm{\sum_{i=1}^{n}w_{i}y_{i}x_{i}}_{2}$
(3) $\displaystyle\leq\lambda_{max}\left(\left(\lambda
I+\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)^{-1}\right)\cdot\sqrt{d}$ (4)
$\displaystyle\leq\frac{1}{\lambda_{min}\left(\lambda
I+\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)}\cdot\sqrt{d}$ (5)
$\displaystyle\leq\frac{\sqrt{d}}{\lambda},$ (6)

where the second inequality follows from $\norm{x_{i}}_{2}\leq\sqrt{d}$ ∎

Under additional Assumption 3.3, note that
$\norm{\bar{\theta}}\leq\norm{\bar{\theta}_{0}}$: indeed, if not,
$\bar{\theta}_{0}$ is a better solution to the Ridge problem with parameter
$\lambda$, noting that it has both i) lower—and in fact optimal—unregularized
loss and ii) lower $\ell_{2}$-penalization. Then, we have
$\|\bar{\theta}\|\leq B$. In the rest of the proof, we let
$B(\lambda)\triangleq\min\left(\frac{1}{\sqrt{\lambda}},\frac{\sqrt{d}}{\lambda}\right)$
absent assumptions, and $B(\lambda)\triangleq B$ under Assumption 3.3. Now, in
both cases, we have $\norm{\bar{\theta}}\leq B(\lambda)$.

#### Sensitivity analysis of $\bar{\theta}$ through strong convexity and
bounded gradients

We start with the following lemma that will help us bound the gradient
different over two minimization problem: one over loss function $G(\theta)$
and one over modified loss function $G(\theta)+g(\theta)$, corresponding to
the losses on neighboring databases $X^{\prime}$ and $X$. The lemma is a
slight modification from Lemma 7 of Chaudhuri et al. [2011] that works with
the gradient of $g(\theta)$ evaluated at a specific well-chosen point, instead
of the maximum norm for the gradient of $g(\theta)$ over $\mathbb{R}^{d}$

######  Lemma A.3.

Let $G(\theta)$ and $g(\theta)$ be two vector valued, continuous,
differentiable functions with $G(\theta)$ and $G(\theta)+g(\theta)$ both
$\gamma$-strongly convex. Let
$\theta_{1}=\operatorname*{arg\,min}_{\theta}G(\theta)+g(\theta)$,
$\theta_{2}=\operatorname*{arg\,min}_{\theta}G(\theta)$, then

$\norm{\theta_{1}-\theta_{2}}_{2}\leq\frac{1}{\gamma}\norm{\nabla
g(\theta_{1})}_{2}.$

###### Proof.

Note that $\theta_{1}$ and $\theta_{2}$ must satisfy the first order
conditions, i.e.

$\displaystyle\nabla G(\theta_{2})=0=\nabla G(\theta_{1})+\nabla
g(\theta_{1}).$ (7)

Further, by strong convexity of $G$ with parameter $\gamma$, we have

$\displaystyle\gamma\norm{\theta_{1}-\theta_{2}}^{2}$
$\displaystyle\leq\left(\nabla G(\theta_{2})-\nabla
G(\theta_{1})\right)^{\top}(\theta_{2}-\theta_{1})$ $\displaystyle=\nabla
g(\theta_{1})^{\top}(\theta_{2}-\theta_{1})$ $\displaystyle\leq\norm{\nabla
g(\theta_{1})}\cdot\norm{\theta_{1}-\theta_{2}},$

where line 2 follows from Equation (7) and line 3 follows from Cauchy-Schwarz.
∎

This allows us to bound the sensitivity with respect to agent $i$ of the non-
private Ridge regression minimizer $\bar{\theta}$ as a function of $w_{i}$.
Note that we define the $\ell_{2}$ sensitivity of $\bar{\theta}$ with respect
to agent $i$ as

$\Delta_{i}\bar{\theta}=\max_{D,D^{\prime}~{}\text{i-neighboring}}\|\bar{\theta}(D)-\bar{\theta}(D^{\prime})\|_{2},$

where
$\bar{\theta}(D)=\operatorname*{arg\,min}_{\theta}\sum_{i=1}^{n}w_{i}(y_{i}-\theta^{\top}x_{i})^{2}+\lambda\|\theta\|_{2}^{2}$.
The sensitivity bound is then given by:

######  Theorem A.4.

Let
$\bar{\theta}=\operatorname*{arg\,min}_{\theta\in\mathbb{R}^{d}}\sum_{i=1}^{n}w_{i}\left(y_{i}-\theta^{\top}x_{i}\right)^{2}+\lambda\|\theta\|^{2}_{2}$.
$\bar{\theta}$ has $\ell_{2}$-sensitivity $(\Delta\theta)_{i}$ with respect to
agent $i$ that satisfies
$\Delta_{i}\bar{\theta}\leq\frac{2\sqrt{d}w_{i}}{\lambda}\left(\sqrt{d}B(\lambda)+1\right)$.

###### Proof.

Consider two neighbouring databases $X=((x_{1},y_{1}),\ldots,(x_{n},y_{n}))$
and
$X=((x_{1},y_{1}),\ldots,(x_{i}^{\prime},y_{i}^{\prime}),\ldots,(x_{n},y_{n}))$
that only differ in the data of agent $i$. Let
$G(\theta)+g(\theta)=\sum_{j=1}^{n}w_{j}\left(y_{j}-\theta^{\top}x_{j}\right)^{2}+\lambda\norm{\theta}_{2}^{2}$,
and
$g(\theta)=w_{i}\left(y_{i}-\theta^{\top}x_{i}\right)^{2}-w_{i}\left(y_{i}^{\prime}-\theta^{\top}x_{i}^{\prime}\right)^{2}$.

First, we note that

$G(\theta)+g(\theta)=\sum_{j}w_{j}\left(y_{j}-\theta^{\top}x_{j}\right)^{2}+\lambda\norm{\theta}_{2}^{2}$

is the Ridge loss on database $D$, while

$\displaystyle G(\theta)$
$\displaystyle=\sum_{j}w_{j}\left(y_{j}-\theta^{\top}x_{j}\right)^{2}+\lambda\norm{\theta}_{2}^{2}-g(\theta)$
$\displaystyle=\sum_{j}w_{j}\left(y_{j}-\theta^{\top}x_{j}\right)^{2}-w_{i}\left(y_{i}-\theta^{\top}x_{i}\right)^{2}+w_{i}\left(y_{i}^{\prime}-\theta^{\top}x_{i}^{\prime}\right)^{2}+\lambda\norm{\theta}_{2}^{2}$
$\displaystyle=\sum_{j\neq
i}w_{j}\left(y_{j}-\theta^{\top}x_{j}\right)^{2}+w_{i}\left(y_{i}^{\prime}-\theta^{\top}x_{i}^{\prime}\right)^{2}+\lambda\norm{\theta}_{2}^{2}.$

is the loss on database $D^{\prime}$. Further, both objectives are
$2\lambda$-strongly convex due to $\ell_{2}$-norm penalty term. Now, we have
that $\nabla
g(\theta)=2w_{i}\left((\theta^{\top}x_{i}-y_{i})x_{i}-(\theta^{\top}x_{i}^{\prime}-y_{i}^{\prime})x_{i}^{\prime}\right)=2w_{i}\left(\theta^{\top}x_{i}x_{i}-\theta^{\top}x_{i}^{\prime}x_{i}^{\prime}-y_{i}x_{i}+y_{i}^{\prime}x_{i}^{\prime}\right)$.
Since $|y|\leq 1$ per our model, we have

$\displaystyle\norm{\nabla g(\theta)}_{2}\leq
2w_{i}(|\theta^{\top}x_{i}^{\prime}|\|x_{i}^{\prime}\|+|\theta^{\top}x_{i}|\|x_{i}\|+2\sqrt{d}).$

By the preliminaries section of this proof, we have that $\bar{\theta}(D)$,
the minimizer of $G(\theta)+g(\theta)$, has norm at most $B(\lambda)$. On top
of this, per our model, we have $\norm{x}\leq\sqrt{d}$ (since
$x\in[0,1]^{d})$. Therefore,
$|\bar{\theta}(D)^{\top}x_{i}|,|\bar{\theta}(D^{\prime})^{\top}x_{i}^{\prime}|\leq\sqrt{d}B(\lambda)$
by Cauchy–Schwarz, and we have:

$\displaystyle\norm{\nabla g(\bar{\theta})}_{2}\leq
2w_{i}\left(2dB(\lambda)+2\sqrt{d}\right).$ (8)

From lemma A.3, we have that

$\Delta_{i}\bar{\theta}\leq\frac{1}{2\lambda}\norm{\nabla
g(\bar{\theta})}_{2}.$

which becomes
$\Delta_{i}\bar{\theta}\leq\frac{2w_{i}\sqrt{d}}{\lambda}\left(\sqrt{d}B(\lambda)+1\right)$.
∎

#### Implications for privacy

######  Lemma A.5.

Algorithms 1 is $\varepsilon_{i}$-differentially private for agent $i$ for all
$i$ with

$\varepsilon_{i}=\frac{2w_{i}\eta\sqrt{d}}{\lambda}(\sqrt{d}B(\lambda)+1).$

###### Proof.

Let $D,D^{\prime}$ be two datasets differing only in agent $i$’s data. Let us
call out mechanism $M$. Let $L(\theta,D)$ be the Ridge regression loss on
database $D$ evaluated at $\theta$, and let
$\bar{\theta}(D)=\operatorname*{arg\,min}_{\theta}L(\theta,D)$. For any given
outcome $o$, we have that

$\frac{P\left[M(D)=o\right]}{P\left[M(D^{\prime})=o\right]}=\frac{P\left[\bar{\theta}(D)+Z=o\right]}{P\left[\bar{\theta}(D^{\prime})+Z=o\right]}=\frac{P\left[Z=o-\bar{\theta}(D)\right]}{P\left[Z=o-\bar{\theta}(D^{\prime})\right]}.$

Noting that the probability density function is proportional to
$f(z)\propto\exp\left(-\eta\|z\|_{2}\right)$, this can be written as

$\displaystyle\frac{P\left[M(D)=o\right]}{P\left[M(D^{\prime})=o\right]}$
$\displaystyle=\exp\left(-\eta\norm{o-\bar{\theta}(D)}+\eta\norm{o-\bar{\theta}(D^{\prime})}_{2}\right)$
$\displaystyle\leq\exp\left(\eta\norm{\bar{\theta}(D^{\prime})-\bar{\theta}(D)}_{2}\right)$
$\displaystyle\leq\exp\left(\eta\cdot\Delta_{i}\bar{\theta}\right).$

where the second-to-last step comes from the triangle inequality and the last
step comes from the definition of $\ell_{2}$-sensitivity with respect to agent
$i$. ∎

We can now conclude the proof. Picking
$w_{i}=\frac{\varepsilon_{i}}{\sum_{j=1}^{n}\varepsilon_{j}}$ and
$\eta=\frac{\lambda}{2\sqrt{d}(\sqrt{d}B(\lambda)+1)}\sum_{j=1}^{n}\varepsilon_{j}$,
we get the result. Indeed:

  * •

The weights are positive and immediately satisfy, $\sum_{i}w_{i}=1$, as
required per our algorithm.

  * •

The level of privacy obtained by agent $i$ is

$\frac{2w_{i}\eta}{\lambda}\sqrt{d}(\sqrt{d}B(\lambda)+1)=\frac{2}{\lambda}\frac{\varepsilon_{i}}{\sum_{j=1}^{n}\varepsilon_{j}}\cdot\frac{\lambda}{2\sqrt{d}(\sqrt{d}B(\lambda)+1)}\left(\sum_{j=1}^{n}\varepsilon_{j}\right)\cdot\sqrt{d}(\sqrt{d}B(\lambda)+1)=\varepsilon_{i}.$

###  A.2 Proof of Theorem 3.6

We start by deriving a closed-form expression for $\bar{\theta}$. Note that
for Algorithm 1, $\bar{\theta}$ is simply the unique solution to the
unconstrained minimization problem

$\operatorname*{arg\,min}_{\theta\in\mathbb{R}^{d}}\sum_{i=1}^{n}w_{i}\left(y_{i}-\theta^{\top}x_{i}\right)^{2}+\lambda\|\theta\|^{2}_{2}.$

Therefore,

$\bar{\theta}=\operatorname*{arg\,min}_{\theta\in\mathbb{R}^{d}}\sum_{i=1}^{n}w_{i}\left(y_{i}-\theta^{\top}x_{i}\right)^{2}+\lambda\|\theta\|^{2}_{2}.$

Taking the first order-condition, we note that we must have

$-2\sum_{i=1}^{n}w_{i}x_{i}\left(y_{i}-x_{i}^{\top}\bar{\theta}\right)+2\lambda\theta=0.$

This can be rewritten as

$2\left(\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}+\lambda
I\right)\bar{\theta}=2\sum_{i=1}^{n}w_{i}x_{i}y_{i}.$

Because $\lambda>0$ and $\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}$ is positive
semi-definite, $\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}+\lambda I$ is invertible,
and we obtain the following closed-form expression for $\bar{\theta}$:

$\bar{\theta}=\left(\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}+\lambda
I\right)^{-1}\sum_{i=1}^{n}w_{i}x_{i}y_{i}.$

We now rewrite this closed-form expression as a function of $\theta^{*}$,
leveraging the fact that $y_{i}=x_{i}^{\top}\theta^{*}+Z_{i}$ for $Z_{i}\sim
N(0,\sigma^{2})$ for all observations $i\in[n]$. This yields:

$\displaystyle\bar{\theta}$ $\displaystyle=\left(\lambda
I+\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)^{-1}\sum_{i=1}^{n}w_{i}x_{i}y_{i}$
$\displaystyle=\left(\lambda
I+\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)^{-1}\sum_{i=1}^{n}w_{i}x_{i}(x_{i}^{\top}\theta^{*}+Z_{i})$
$\displaystyle=\left(\lambda
I+\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)^{-1}\left(\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\theta^{*}+\sum_{i=1}^{n}w_{i}x_{i}Z_{i}\right)$
$\displaystyle=\left(\lambda
I+\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)^{-1}\left(\left(\lambda
I+\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)\theta^{*}+\sum_{i=1}^{n}w_{i}x_{i}Z_{i}-\lambda\theta^{*}\right)$
$\displaystyle=\theta^{*}+\left(\lambda
I+\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)^{-1}\left(\sum_{i=1}^{n}w_{i}x_{i}Z_{i}-\lambda\theta^{*}\right).$

In turn, we have that the distance between $\theta^{*}$ and $\hat{\theta}$
satisfies, where $Z$ is the random variable added for privacy as per
Algorithms 1:

$\displaystyle\left\|\hat{\theta}-\theta^{*}\right\|$
$\displaystyle=\left\|\left(\lambda
I+\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)^{-1}\left(\sum_{i=1}^{n}w_{i}x_{i}Z_{i}-\lambda\theta^{*}\right)+Z\right\|$
$\displaystyle\leq\left\|\left(\lambda
I+\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)^{-1}\left(\sum_{i=1}^{n}w_{i}x_{i}Z_{i}-\lambda\theta^{*}\right)\right\|+\left\|Z\right\|$
$\displaystyle\leq\frac{1}{\lambda+\lambda_{min}\left(\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)}\left\|\left(\sum_{i=1}^{n}w_{i}x_{i}Z_{i}-\lambda\theta^{*}\right)\right\|+\left\|Z\right\|$
$\displaystyle\leq\frac{1}{1+\frac{\lambda_{min}\left(\sum_{i=1}^{n}w_{i}x_{i}x_{i}^{\top}\right)}{\lambda}}\cdot\norm{\theta^{*}}+\frac{1}{\lambda}\left\|\sum_{i=1}^{n}w_{i}x_{i}Z_{i}\right\|+\left\|Z\right\|.$

To conclude the proof, we write concentration inequalities on
$\left\|\sum_{i=1}^{n}w_{i}x_{i}Z_{i}\right\|$ and on $\left\|Z\right\|$:

  * •

For $Z$: we know per Remark 3.1 that $\|Z\|_{2}$ follows a gamma distribution
with parameters $d$ and $\eta$; therefore, it has mean $\frac{d}{\eta}$ and
variance $\frac{d}{\eta^{2}}$. By Chebyshev, we obtain that with probability
at most $\delta/2$,
$\|Z\|\geq\frac{d}{\eta}+\sqrt{\frac{2}{\delta}}\cdot\frac{\sqrt{d}}{\eta}$

  * •

For $\left\|\sum_{i=1}^{n}w_{i}x_{i}Z_{i}\right\|$: first note that
$S=\sum_{i=1}^{n}w_{i}x_{i}Z_{i}$ is a multivariate Gaussian random variable.
It has mean $0$ since the $Z_{i}$’s have mean $0$, and covariance

$\Sigma=\sum_{i=1}^{n}\sum_{j}w_{i}w_{j}Cov(Z_{i},Z_{j})x_{i}x_{j}^{\top}=\sigma^{2}\sum_{i=1}^{n}w_{i}^{2}x_{i}x_{i}^{\top},$

where the equality comes from $Cov(Z_{i},Z_{i})=\sigma^{2}$ and
$Cov(Z_{i},Z_{j})=0$ for $i\neq j$ by independence. Note that then since
$S(k)$ has mean $0$ for all $k\in[d]$,

$E\left[\|S\|^{2}\right]=\sum_{k=1}^{d}E\left[S(k)^{2}\right]=\sum_{k=1}^{d}Cov(S(k),S(k))=\sum_{k=1}^{d}\Sigma_{kk}=Tr(\Sigma).$

Now, by Markov’s inequality, we have that
$P\left[\|S\|^{2}\geq\frac{2Tr(\Sigma)}{\delta}\right]\leq\delta/2$, or
equivalently
$P\left[\|S\|\geq\sqrt{\frac{2Tr(\Sigma)}{\delta}}\right]\leq\delta/2$. To
conclude the proof, we simply need to compute the trace of covariance matrix
$\Sigma$. We have that

$Tr(\Sigma)=\sigma^{2}\sum_{i=1}^{n}w_{i}^{2}Tr(x_{i}x_{i}^{\top})=\sigma^{2}\sum_{i=1}^{n}w_{i}^{2}\sum_{k=1}^{d}x_{ik}^{2}=\sigma^{2}\sum_{i=1}^{n}w_{i}^{2}\|x_{i}\|^{2}\leq
d\sigma^{2}\sum_{i=1}^{n}w_{i}^{2},$

using that $\|x\|\leq\sqrt{d}$. This directly implies that

$P\left[\|S\|\geq\sqrt{\frac{2d\sigma^{2}\|\vec{w}\|^{2}}{\delta}}\right]\leq
P\left[\|S\|\geq\sqrt{\frac{2Tr(\Sigma)}{\delta}}\right]\leq\delta/2.$

Therefore, we have that
$\frac{1}{\lambda}\|\sum_{i=1}^{n}w_{i}x_{i}Z_{i}\|\geq\frac{\sigma}{\lambda}\sqrt{\frac{2d}{\delta}}\|\vec{w}\|$
with probability at most $\delta/2$.

The result follows by union bound over the randomness of both $Z$ and
$\sum_{i=1}^{n}w_{i}x_{i}Z_{i}$.

##  Appendix B Additional Experiments

###  B.1 Comparison to non-personalized differential privacy

In Tables 5 and 6 (respectively on our synthetic and real dataset) where we
change the privacy level $\varepsilon_{c}$ for the conservative users. We
observe that using personalized privacy still performs significantly better,
but the performance improvements diminish as $\varepsilon_{c}$ increases. This
is not surprising: as $\varepsilon_{c}$ increases, there is less and less
variability across users’ privacy levels, leading to less of a need for
personalized privacy. Non-personalized privacy estimators start working better
as the amount of noise they must add, which scales as a function of
$\varepsilon_{c}$, starts largely decreasing.

| Privacy level
---
of Conservatives
($\varepsilon_{c}$)
| Unregularized
---
test loss
(PDP-OP)
| Unregularized
---
test loss
(non-personalized)
| Regularized
---
test loss
(PDP-OP)
| Regularized
---
test loss
(non-personalized)
0.01 | $\mathbf{1.44\crossproduct 10^{-2}}$ | 3.38 | $\mathbf{1.15}$ | $1.05\crossproduct 10^{3}$
0.05 | $\mathbf{1.41\crossproduct 10^{-2}}$ | $2.09\crossproduct 10^{-1}$ | $\mathbf{1.05}$ | $6.08\crossproduct 10^{1}$
0.10 | $\mathbf{1.39\crossproduct 10^{-2}}$ | $4.76\crossproduct 10^{-2}$ | $\mathbf{1.00}$ | $1.16\crossproduct 10^{1}$
0.20 | $\mathbf{1.41\crossproduct 10^{-2}}$ | $3.40\crossproduct 10^{-2}$ | $\mathbf{1.03}$ | 7.21
0.30 | $\mathbf{1.34\crossproduct 10^{-2}}$ | $2.08\crossproduct 10^{-2}$ | $\mathbf{8.74\crossproduct 10^{-1}}$ | 1.20
0.40 | $\mathbf{1.32\crossproduct 10^{-2}}$ | $1.65\crossproduct 10^{-2}$ | $\mathbf{8.29\crossproduct 10^{-1}}$ | 1.84
0.50 | $\mathbf{1.29\crossproduct 10^{-2}}$ | $1.45\crossproduct 10^{-2}$ | $\mathbf{7.26\crossproduct 10^{-1}}$ | 1.20

Table 5: Lower loss compared to standard DP on the synthetic dataset, while
varying $\varepsilon_{c}$ (privacy level of the conservative users), keeping
$f_{c}=0.54,f_{m}=0.37,\varepsilon_{m}=0.5$ (same parameters as shown in
Jorgensen et al. [2015]) and $\lambda=100$.

| Privacy level
---
of Conservatives
($\varepsilon_{c}$)
| Unregularized
---
test loss
(PDP-OP)
| Unregularized
---
test loss
(non-personalized)
| Regularized
---
test loss
(PDP-OP)
| Regularized
---
test loss
(non-personalized)
0.01 | $\mathbf{2.27\crossproduct 10^{-1}}$ | $2.76\crossproduct 10^{2}$ | $\mathbf{7.43\crossproduct 10^{-1}}$ | $9.87\crossproduct 10^{2}$
0.05 | $\mathbf{2.28\crossproduct 10^{-1}}$ | $2.00\crossproduct 10^{1}$ | $\mathbf{7.32\crossproduct 10^{-1}}$ | $7.19\crossproduct 10^{1}$
0.10 | $\mathbf{2.12\crossproduct 10^{-1}}$ | 5.05 | $\mathbf{6.92\crossproduct 10^{-1}}$ | $1.80\crossproduct 10^{1}$
0.20 | $\mathbf{1.97\crossproduct 10^{-1}}$ | 1.28 | $\mathbf{6.42\crossproduct 10^{-1}}$ | 4.54
0.30 | $\mathbf{1.83\crossproduct 10^{-1}}$ | $5.84\crossproduct 10^{-1}$ | $\mathbf{5.75\crossproduct 10^{-1}}$ | 2.06
0.40 | $\mathbf{1.66\crossproduct 10^{-1}}$ | $3.48\crossproduct 10^{-1}$ | $\mathbf{5.26\crossproduct 10^{-1}}$ | 1.17
0.50 | $\mathbf{1.55\crossproduct 10^{-1}}$ | $2.33\crossproduct 10^{-1}$ | $\mathbf{4.90\crossproduct 10^{-1}}$ | $7.61\crossproduct 10^{-1}$

Table 6: Lower loss compared to standard DP on the Medical cost dataset while
varying $\varepsilon_{c}$ (privacy level of the conservative users), keeping
$f_{c}=0.54,f_{m}=0.37,\varepsilon_{m}=0.5$ (same parameters as shown in
Jorgensen et al. [2015]) and $\lambda=1$(analogous to Table 5)

In Tables 7 and 8, we change the privacy level $\varepsilon_{m}$ for the
pragmatist (or medium privacy) users. We observe once again that using
personalized privacy performs significantly better. The performance
improvements are consistent across the board, noting that there is still a
need for personalized privacy as we still have significant variability across
user privacy preferences, with $34$ percent of users requiring a stringent
privacy level of $0.01$ and $23$ percent a privacy level of $1$.

| Privacy level
---
of pragmatists
($\varepsilon_{m}$)
| Unregularized
---
test loss
(PDP-OP)
| Unregularized
---
test loss
(non-personalized)
| Regularized
---
test loss
(PDP-OP)
| Regularized
---
test loss
(non-personalized)
0.05 | $\mathbf{2.11\crossproduct 10^{-2}}$ | 9.68 | $\mathbf{3.23}$ | $2.95\crossproduct 10^{3}$
0.10 | $\mathbf{1.88\crossproduct 10^{-2}}$ | 5.76 | $\mathbf{2.55}$ | $1.76\crossproduct 10^{3}$
0.15 | $\mathbf{1.89\crossproduct 10^{-2}}$ | 8.46 | $\mathbf{2.56}$ | $2.60\crossproduct 10^{3}$
0.20 | $\mathbf{1.79\crossproduct 10^{-2}}$ | 4.84 | $\mathbf{2.25}$ | $1.49\crossproduct 10^{3}$
0.25 | $\mathbf{1.66\crossproduct 10^{-2}}$ | 3.17 | $\mathbf{1.83}$ | $9.78\crossproduct 10^{2}$
0.30 | $\mathbf{1.57\crossproduct 10^{-2}}$ | 1.48 | $\mathbf{1.53}$ | $4.52\crossproduct 10^{2}$
0.35 | $\mathbf{1.58\crossproduct 10^{-2}}$ | $6.45\crossproduct 10^{-1}$ | $\mathbf{1.61}$ | $1.97\crossproduct 10^{2}$
0.40 | $\mathbf{1.48\crossproduct 10^{-2}}$ | 2.44 | $\mathbf{1.33}$ | $7.56\crossproduct 10^{2}$
0.45 | $\mathbf{1.47\crossproduct 10^{-2}}$ | 3.21 | $\mathbf{1.25}$ | $9.86\crossproduct 10^{2}$
0.50 | $\mathbf{1.44\crossproduct 10^{-2}}$ | 3.38 | $\mathbf{1.15}$ | $1.05\crossproduct 10^{3}$

Table 7: Lower loss compared to standard DP on the synthetic dataset, while
varying $\varepsilon_{m}$ (privacy level of the pragmatists), keeping
$f_{c}=0.54,f_{m}=0.37,\varepsilon_{c}=0.01$ (same parameters as shown in
Jorgensen et al. [2015]) and $\lambda=100$.

| Privacy level
---
of Conservatives
($\varepsilon_{m}$)
| Unregularized
---
test loss
(PDP-OP)
| Unregularized
---
test loss
(non-personalized)
| Regularized
---
test loss
(PDP-OP)
| Regularized
---
test loss
(non-personalized)
0.05 | $\mathbf{5.66\crossproduct 10^{-1}}$ | $4.99\crossproduct 10^{2}$ | $\mathbf{1.94}$ | $1.75\crossproduct 10^{3}$
0.10 | $\mathbf{5.18\crossproduct 10^{-1}}$ | $4.99\crossproduct 10^{2}$ | $\mathbf{1.76}$ | $1.78\crossproduct 10^{3}$
0.15 | $\mathbf{4.50\crossproduct 10^{-1}}$ | $5.02\crossproduct 10^{2}$ | $\mathbf{1.55}$ | $1.76\crossproduct 10^{3}$
0.20 | $\mathbf{4.00\crossproduct 10^{-1}}$ | $4.81\crossproduct 10^{2}$ | $\mathbf{1.38}$ | $1.71\crossproduct 10^{3}$
0.25 | $\mathbf{3.60\crossproduct 10^{-1}}$ | $4.80\crossproduct 10^{2}$ | $\mathbf{1.22}$ | $1.70\crossproduct 10^{3}$
0.30 | $\mathbf{3.27\crossproduct 10^{-1}}$ | $3.94\crossproduct 10^{2}$ | $\mathbf{1.10}$ | $1.43\crossproduct 10^{3}$
0.35 | $\mathbf{2.85\crossproduct 10^{-1}}$ | $4.82\crossproduct 10^{2}$ | $\mathbf{9.75\crossproduct 10^{-1}}$ | $1.75\crossproduct 10^{3}$
0.40 | $\mathbf{2.69\crossproduct 10^{-1}}$ | $4.83\crossproduct 10^{2}$ | $\mathbf{9.05\crossproduct 10^{-1}}$ | $1.71\crossproduct 10^{3}$
0.45 | $\mathbf{2.53\crossproduct 10^{-1}}$ | $4.36\crossproduct 10^{2}$ | $\mathbf{8.28\crossproduct 10^{-1}}$ | $1.61\crossproduct 10^{3}$
0.50 | $\mathbf{2.27\crossproduct 10^{-1}}$ | $2.76\crossproduct 10^{2}$ | $\mathbf{7.43\crossproduct 10^{-1}}$ | $9.87\crossproduct 10^{2}$

Table 8: Lower loss compared to standard DP on the Medical cost dataset, while
varying $\varepsilon_{m}$ (privacy level of the pragmatists), keeping
$f_{c}=0.54,f_{m}=0.37,\varepsilon_{c}=0.01$ (same parameters as shown in
Jorgensen et al. [2015]) and $\lambda=1$. (analogous to Table 7)

In Tables 9 and 10, we change the fraction of conservative users $f_{c}$. We
note that even then, our personalized privacy framework still yields
consistent and significant improvements over non-personalized privacy. This is
because the existence of users with $\varepsilon_{c}=0.01$ forces the non-
personalized privacy estimate to still add noise that scales with this most
stringent privacy requirement.

| Fraction of
---
Conservative
Users
($f_{c}$)
| Unregularized
---
test loss
(PDP-OP)
| Unregularized
---
test loss
(non-personalized)
| Regularized
---
test loss
(PDP-OP)
| Regularized
---
test loss
(non-personalized)
0.1 | $\mathbf{9.02\crossproduct 10^{-3}}$ | $7.87\crossproduct 10^{-1}$ | $\mathbf{4.91\crossproduct 10^{-1}}$ | $2.43\crossproduct 10^{2}$
0.2 | $\mathbf{9.41\crossproduct 10^{-3}}$ | $3.80\crossproduct 10^{-1}$ | $\mathbf{6.51\crossproduct 10^{-1}}$ | $1.14\crossproduct 10^{2}$
0.3 | $\mathbf{1.02\crossproduct 10^{-2}}$ | 4.56 | $\mathbf{8.76\crossproduct 10^{-1}}$ | $1.41\crossproduct 10^{3}$
0.4 | $\mathbf{1.14\crossproduct 10^{-2}}$ | 3.82 | 1.27 | $1.17\crossproduct 10^{3}$
0.5 | $\mathbf{1.30\crossproduct 10^{-2}}$ | 7.00 | 1.75 | $2.14\crossproduct 10^{3}$
0.6 | $\mathbf{1.69\crossproduct 10^{-2}}$ | 9.59 | 2.92 | $2.90\crossproduct 10^{3}$

Table 9: Lower loss compared to standard DP on the synthetic dataset, while
varying $f_{c}$ (fraction of conservative users) for
$f_{m}=0.37,~{}f_{l}=1-f_{c}-f_{m},~{}\varepsilon_{c}=0.01,~{}\varepsilon_{m}=0.2$,
$\varepsilon_{l}=1.0,\lambda=100$

| Fraction of
---
Conservative
Users
($f_{c}$)
| Unregularized
---
test loss
(PDP-OP)
| Unregularized
---
test loss
(non-personalized)
| Regularized
---
test loss
(PDP-OP)
| Regularized
---
test loss
(non-personalized)
0.1 | $\mathbf{1.17\crossproduct 10^{-1}}$ | $4.95\crossproduct 10^{2}$ | $\mathbf{3.47\crossproduct 10^{-1}}$ | $1.77\crossproduct 10^{3}$
0.2 | $\mathbf{1.45\crossproduct 10^{-1}}$ | $4.89\crossproduct 10^{2}$ | $\mathbf{4.46\crossproduct 10^{-1}}$ | $1.74\crossproduct 10^{3}$
0.3 | $\mathbf{1.82\crossproduct 10^{-1}}$ | $5.00\crossproduct 10^{2}$ | $\mathbf{5.78\crossproduct 10^{-1}}$ | $1.79\crossproduct 10^{3}$
0.4 | $\mathbf{2.35\crossproduct 10^{-1}}$ | $4.80\crossproduct 10^{2}$ | $\mathbf{7.71\crossproduct 10^{-1}}$ | $1.73\crossproduct 10^{3}$
0.5 | $\mathbf{3.45\crossproduct 10^{-1}}$ | $4.93\crossproduct 10^{2}$ | $\mathbf{1.16}$ | $1.80\crossproduct 10^{3}$
0.6 | $\mathbf{5.61\crossproduct 10^{-1}}$ | $4.19\crossproduct 10^{2}$ | $\mathbf{1.92}$ | $1.51\crossproduct 10^{3}$

Table 10: Lower loss compared to standard DP on the Medical cost dataset,
while varying $f_{c}$(fraction of conservative users)
$f_{m}=0.37,f_{l}=1\scalebox{0.75}[1.0]{$-$}f_{c}\scalebox{0.75}[1.0]{$-$}f_{m},\varepsilon_{c}=0.01,\varepsilon_{m}=0.2$,
$\varepsilon_{l}=1.0,\lambda=1$.

Finally, in Tables 11 and 12, we fix a single value of the regularization
parameter $\lambda$ and of the distribution of privacy requirements of the
users and show how our results evolve as the number of samples we feed our
algorithm increases. Unsurprisingly, the more samples we have access to, the
better the performance of both our personalized privacy approach as well as
the non-personalized baseline. Our approach continues to see significant and
consistent improvements compared to the non-personalized baseline.

| Fraction of
---
training samples
($n$)
| Unregularized
---
test loss
(PDP-OP)
| Unregularized
---
test loss
(non-personalized)
| Regularized
---
test loss
(PDP-OP)
| Regularized
---
test loss
(non-personalized)
0.1 | $\mathbf{4.28\crossproduct 10^{-1}}$ | $1.22\crossproduct 10^{1}$ | $\mathbf{1.32\crossproduct 10^{2}}$ | $3.73\crossproduct 10^{3}$
0.2 | $\mathbf{1.41\crossproduct 10^{-1}}$ | $1.15\crossproduct 10^{2}$ | $\mathbf{4.02\crossproduct 10^{1}}$ | $3.45\crossproduct 10^{4}$
0.3 | $\mathbf{5.01\crossproduct 10^{-2}}$ | 8.97 | $\mathbf{1.46\crossproduct 10^{1}}$ | $2.89\crossproduct 10^{3}$
0.4 | $\mathbf{4.64\crossproduct 10^{-2}}$ | 2.37 | $\mathbf{1.27\crossproduct 10^{1}}$ | $7.24\crossproduct 10^{2}$
0.5 | $\mathbf{3.49\crossproduct 10^{-2}}$ | $2.14\crossproduct 10^{1}$ | $\mathbf{8.11}$ | $6.61\crossproduct 10^{3}$
0.6 | $\mathbf{2.12\crossproduct 10^{-2}}$ | $1.59\crossproduct 10^{1}$ | $\mathbf{5.16}$ | $5.06\crossproduct 10^{3}$
0.7 | $\mathbf{2.00\crossproduct 10^{-2}}$ | 7.97 | $\mathbf{4.66}$ | $2.52\crossproduct 10^{3}$
0.8 | $\mathbf{1.64\crossproduct 10^{-2}}$ | $1.03\crossproduct 10^{1}$ | $\mathbf{3.36}$ | $2.95\crossproduct 10^{3}$
0.9 | $\mathbf{1.10\crossproduct 10^{-2}}$ | 6.36 | $\mathbf{2.52}$ | $1.93\crossproduct 10^{3}$
1.0 | $\mathbf{1.01\crossproduct 10^{-2}}$ | 1.98 | $\mathbf{2.16}$ | $6.17\crossproduct 10^{2}$

Table 11: Lower loss compared to standard DP on the synthetic dataset, while
varying the fraction of the training set samples we use. For example, here
$n=0.3$ means that we use a 0.3 fraction of the training set. We fix
$f_{c}=0.34,f_{m}=0.43,f_{l}=0.23,\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{l}=1.0$
and $\lambda=100$.

| Fraction of
---
training samples
($n$)
| Unregularized
---
test loss
(PDP-OP)
| Unregularized
---
test loss
(non-personalized)
| Regularized
---
test loss
(PDP-OP)
| Regularized
---
test loss
(non-personalized)
0.1 | $\mathbf{1.83\crossproduct 10^{1}}$ | $1.45\crossproduct 10^{4}$ | $\mathbf{6.64\crossproduct 10^{1}}$ | $5.21\crossproduct 10^{4}$
0.2 | $\mathbf{4.63}$ | $6.62\crossproduct 10^{3}$ | $\mathbf{1.65\crossproduct 10^{1}}$ | $2.37\crossproduct 10^{4}$
0.3 | $\mathbf{2.05}$ | $5.23\crossproduct 10^{3}$ | $\mathbf{7.29}$ | $1.85\crossproduct 10^{4}$
0.4 | $\mathbf{1.21}$ | $1.60\crossproduct 10^{3}$ | $\mathbf{4.28}$ | $5.77\crossproduct 10^{3}$
0.5 | $\mathbf{7.85\crossproduct 10^{-1}}$ | $1.96\crossproduct 10^{3}$ | $\mathbf{2.75}$ | $6.98\crossproduct 10^{3}$
0.6 | $\mathbf{5.40\crossproduct 10^{-1}}$ | $1.36\crossproduct 10^{3}$ | $\mathbf{1.84}$ | $4.91\crossproduct 10^{3}$
0.7 | $\mathbf{4.02\crossproduct 10^{-1}}$ | $9.64\crossproduct 10^{2}$ | $\mathbf{1.38}$ | $3.47\crossproduct 10^{3}$
0.8 | $\mathbf{3.16\crossproduct 10^{-1}}$ | $7.26\crossproduct 10^{2}$ | $\mathbf{1.06}$ | $2.60\crossproduct 10^{3}$
0.9 | $\mathbf{2.53\crossproduct 10^{-1}}$ | $6.15\crossproduct 10^{2}$ | $\mathbf{8.56\crossproduct 10^{-1}}$ | $2.24\crossproduct 10^{3}$
1.0 | $\mathbf{2.14\crossproduct 10^{-1}}$ | $3.82\crossproduct 10^{2}$ | $\mathbf{6.99\crossproduct 10^{-1}}$ | $1.36\crossproduct 10^{3}$

Table 12: Lower loss compared to standard DP on the Medical cost dataset,
while varying the number of samples we use. For example, here $n=0.3$ means
that we use a $0.3$ fraction of the training set. We fix
$f_{c}=0.34,f_{m}=0.43,f_{l}=0.23,\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{l}=1.0$
and $\lambda=1$.

###  B.2 Comparison to Jorgensen et al. [2015]

We provide additional experimental results that further the comparison of our
PDP-OP algorithm with that of Jorgensen et al. [2015].

#### Improvements in loss.

In Figure 3 and Figure 4 we vary the privacy level $\varepsilon_{c}$ for the
conservative users, and observe that our algorithm always leads to a lower
loss compared to Jorgensen et al. [2015]. We further note that the performance
improvements diminish as $\varepsilon_{c}$ increases, as there is less
variability in the users’ privacy levels and we get closer to the non-
personalized case.

((a))

((b))

Figure 3: Lower loss compared to Jorgensen et al. [2015] on the synthetic
dataset while varying $\varepsilon_{c}$ (privacy level of the conservative
users) , keeping
$\varepsilon_{m}=0.5,~{}\varepsilon_{l}=1.0,~{}f_{c}=0.54,~{}f_{m}=0.37,f_{l}=0.09$.

((a))

((b))

Figure 4: Lower loss compared to Jorgensen et al. [2015] on the Medical costs
dataset while varying $\varepsilon_{c}$ (privacy level of the conservative
users), keeping
$\varepsilon_{m}=0.5,\varepsilon_{l}=1.0,f_{c}=0.54,f_{m}=0.37,f_{l}=0.09$.

Figures 5 and 6 show similar insights when varying the parameter
$\varepsilon_{m}$, that controls the privacy level of medium-privacy (or
pragmatic) users.

((a))

((b))

Figure 5: Lower loss compared to Jorgensen et al. [2015] on the synthetic
dataset while varying $\varepsilon_{m}$ (privacy level of pragmatists),
keeping
$\varepsilon_{c}=0.01,\varepsilon_{l}=1.0,f_{c}=0.54,f_{m}=0.37,f_{l}=0.09$.

((a))

((b))

Figure 6: Lower loss compared to Jorgensen et al. [2015] for the Medical costs
dataset while varying $\varepsilon_{m}$ (privacy level of pragmatists),
keeping
$\varepsilon_{c}=0.01,\varepsilon_{l}=1.0,f_{c}=0.54,f_{m}=0.37,f_{l}=0.09$.

In Figures 7 and 8 we vary the fraction of users with strong privacy
requirements. We remark that our relative performance improvement compared to
Jorgensen et al. [2015] becomes bigger as a larger fraction of users has high
privacy requirements, highlighting the benefit of our framework in stringent
privacy regimes.

((a))

((b))

Figure 7: Lower loss compared to Jorgensen et al. [2015] on the synthetic
dataset while varying $f_{c}$(fraction of conservative users), keeping
$\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{l}=1.0,f_{m}=0.37,f_{l}=1-f_{m}-f_{c}=0.63-f_{c}$.

((a))

((b))

Figure 8: Lower loss compared to Jorgensen et al. [2015] on the Medical costs
dataset while $f_{c}$ (fraction of conservative users), keeping
$\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{l}=1.0,f_{m}=0.37,f_{l}=1-f_{m}-f_{c}=0.63-f_{c}$.

Finally, Figures 9 and 10 vary the fraction of the training set used. We note
that our loss improvements compared to Jorgensen et al. [2015] become less
noticeable as $n$ increases. This is perhaps unsurprising, as the more data
points we use, the lesser the impact of adding noise for privacy is, and there
is much less leeway for improvement across different techniques for privacy.

#### Improvements in variability.

We start with Figures 11 and 12 where we vary the privacy level
$\varepsilon_{c}$ for the conservative users. Then, on Figures 13 and 14, we
focus on the case of varying $\varepsilon_{m}$. On Figures 15 and 16, we vary
the fraction of users that have high privacy requirements. Finally, on Figures
17 and 18, we vary the fraction of the training set used. On all figures, we
note that the standard deviation of the loss of our PDP-OP algorithm is lower
than Jorgensen et al. [2015].

((a))

((b))

Figure 9: Lower loss compared to Jorgensen et al. [2015] on the synthetic
dataset while varying the parameter $n$ (the fraction of training samples
used), keeping
$\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{c}=1.0,f_{c}=0.34,f_{m}=0.43,f_{l}=0.23$.

((a))

((b))

Figure 10: Lower loss compared to Jorgensen et al. [2015] on the Medical costs
dataset while varying $n$ (the fraction of training samples used), keeping
$\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{c}=1.0,f_{c}=0.34,f_{m}=0.43$.

((a))

((b))

Figure 11: Lower standard deviation compared to Jorgensen et al. [2015] on the
synthetic dataset, while varying the $\varepsilon_{c}$ (the privacy level of
conservative users), keeping
$\varepsilon_{m}=0.5,\varepsilon_{l}=1.0,f_{c}=0.54,f_{m}=0.37,f_{l}=0.09$.

((a))

((b))

Figure 12: Lower standard deviation compared to Jorgensen et al. [2015] on the
Medical cost dataset, while varying the $\varepsilon_{c}$ (the privacy level
of conservative users), keeping
$\varepsilon_{m}=0.5,\varepsilon_{l}=1.0,f_{c}=0.54,f_{m}=0.37,f_{l}=0.09$.

((a))

((b))

Figure 13: Lower standard deviation compared to Jorgensen et al. [2015] on the
synthetic dataset, while varying $\varepsilon_{m}$ (privacy level privacy
level of the pragmatists), keeping
$\varepsilon_{c}=0.01,\varepsilon_{l}=1.0,f_{c}=0.54,f_{m}=0.37,f_{l}=0.09$.

((a))

((b))

Figure 14: Lower standard deviation compared to Jorgensen et al. [2015] on the
Medical cost dataset, while varying $\varepsilon_{m}$ (privacy level privacy
level of the pragmatists), keeping
$\varepsilon_{c}=0.01,\varepsilon_{l}=1.0,f_{c}=0.54,f_{m}=0.37,f_{l}=0.09$.

((a))

((b))

Figure 15: Lower standard deviation compared to Jorgensen et al. [2015] on the
synthetic dataset, while varying $f_{c}$ (the fraction of conservative users),
keeping
$\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{l}=1.0,f_{m}=0.37,f_{l}=1-f_{c}-f_{m}=0.63-f_{c}$.

((a))

((b))

Figure 16: Lower standard deviation compared to Jorgensen et al. [2015] on the
Medical cost dataset, while varying $f_{c}$ (the fraction of conservative
users), keeping
$\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{l}=1.0,f_{m}=0.37,f_{l}=1-f_{c}-f_{m}=0.63-f_{c}$.

((a))

((b))

Figure 17: Lower standard deviation compared to Jorgensen et al. [2015] on the
synthetic dataset, while varying the parameter $n$ (the fraction of training
samples used), keeping
$\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{l}=1.0,f_{c}=0.34,f_{m}=0.43,f_{l}=0.23$.

((a))

((b))

Figure 18: Lower standard deviation compared to Jorgensen et al. [2015] on the
Medical cost dataset, while varying the parameter $n$ (the fraction of
training samples used), keeping
$\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{l}=1.0,f_{c}=0.34,f_{m}=0.43,f_{l}=0.23$.

| Regularization
---
parameter
Lambda ($\lambda$)
| Unregularized
---
test loss
(PDP-OP)
| Unregularized
---
test loss
(Jorgensen max)
| Unregularized
---
test loss
(Jorgensen mean)
| Regularized
---
test loss
(PDP-OP)
| Regularized
---
test loss
(Jorgensen max)
| Regularized
---
test loss
(Jorgensen mean)
1.00 | $\mathbf{9.69\crossproduct 10^{2}}$ | $1.34\crossproduct 10^{3}$ | $2.19\crossproduct 10^{3}$ | $\mathbf{1.53\crossproduct 10^{3}}$ | $2.01\crossproduct 10^{3}$ | $3.47\crossproduct 10^{3}$
3.00 | $\mathbf{4.33\crossproduct 10^{1}}$ | $5.63\crossproduct 10^{1}$ | $9.98\crossproduct 10^{1}$ | $\mathbf{1.45\crossproduct 10^{2}}$ | $1.99\crossproduct 10^{2}$ | $3.39\crossproduct 10^{2}$
5.00 | $\mathbf{1.13\crossproduct 10^{1}}$ | $1.41\crossproduct 10^{1}$ | $2.52\crossproduct 10^{1}$ | $\mathbf{5.65\crossproduct 10^{1}}$ | $7.69\crossproduct 10^{1}$ | $1.30\crossproduct 10^{2}$
7.00 | $\mathbf{4.43}$ | $5.50$ | $1.02\crossproduct 10^{1}$ | $\mathbf{3.15\crossproduct 10^{1}}$ | $4.20\crossproduct 10^{1}$ | $7.14\crossproduct 10^{1}$
10.00 | $\mathbf{1.74}$ | 2.18 | 4.09 | $\mathbf{1.72\crossproduct 10^{1}}$ | $2.32\crossproduct 10^{1}$ | $3.98\crossproduct 10^{1}$
15.00 | $\mathbf{6.14\crossproduct 10^{-1}}$ | $7.69\crossproduct 10^{-1}$ | 1.30 | $\mathbf{8.73}$ | $1.20\crossproduct 10^{1}$ | $2.03\crossproduct 10^{1}$
20.00 | $\mathbf{2.88\crossproduct 10^{-1}}$ | $3.66\crossproduct 10^{-1}$ | $6.44\crossproduct 10^{-1}$ | $\mathbf{5.52}$ | 7.43 | $1.29\crossproduct 10^{1}$
25.00 | $\mathbf{1.59\crossproduct 10^{-1}}$ | $2.15\crossproduct 10^{-1}$ | $3.79\crossproduct 10^{-1}$ | $\mathbf{3.91}$ | 5.22 | 9.15
50.00 | $\mathbf{2.37\crossproduct 10^{-2}}$ | $3.10\crossproduct 10^{-2}$ | $5.50\crossproduct 10^{-2}$ | $\mathbf{1.13}$ | 1.53 | 2.62
75.00 | $\mathbf{8.54\crossproduct 10^{-3}}$ | $1.11\crossproduct 10^{-2}$ | $1.88\crossproduct 10^{-2}$ | $\mathbf{5.73\crossproduct 10^{-1}}$ | $7.85\crossproduct 10^{-1}$ | 1.34
100.00 | $\mathbf{4.70\crossproduct 10^{-3}}$ | $5.64\crossproduct 10^{-3}$ | $9.85\crossproduct 10^{-3}$ | $\mathbf{3.72\crossproduct 10^{-1}}$ | $5.08\crossproduct 10^{-1}$ | $8.75\crossproduct 10^{-1}$
200.00 | $\mathbf{1.33\crossproduct 10^{-3}}$ | $1.56\crossproduct 10^{-3}$ | $2.40\crossproduct 10^{-3}$ | $\mathbf{1.45\crossproduct 10^{-1}}$ | $1.99\crossproduct 10^{-1}$ | $3.41\crossproduct 10^{-1}$
300.00 | $\mathbf{7.59\crossproduct 10^{-4}}$ | $8.62\crossproduct 10^{-4}$ | $1.26\crossproduct 10^{-3}$ | $\mathbf{8.77\crossproduct 10^{-2}}$ | $1.21\crossproduct 10^{-1}$ | $2.07\crossproduct 10^{-1}$
400.00 | $\mathbf{5.41\crossproduct 10^{-4}}$ | $6.14\crossproduct 10^{-4}$ | $8.72\crossproduct 10^{-4}$ | $\mathbf{6.38\crossproduct 10^{-2}}$ | $8.48\crossproduct 10^{-2}$ | $1.48\crossproduct 10^{-1}$
500.00 | $\mathbf{4.23\crossproduct 10^{-4}}$ | $4.79\crossproduct 10^{-4}$ | $6.45\crossproduct 10^{-4}$ | $\mathbf{4.92\crossproduct 10^{-2}}$ | $6.74\crossproduct 10^{-2}$ | $1.16\crossproduct 10^{-1}$

Table 13: Improvements in variability of the test loss: Standard deviation of
our algorithm is always lower, results on synthetic dataset with
$d=30,~{}n=100)$, while varying the regularization parameter $\lambda$,
keeping
$\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{l}=1.0,f_{c}=0.34,f_{m}=0.43$.

| Regularization
---
parameter
Lambda ($\lambda$)
| Unregularized
---
test loss
(PDP-OP)
| Unregularized
---
test loss
(Jorgensen max)
| Unregularized
---
test loss
(Jorgensen mean)
| Regularized
---
test loss
(PDP-OP)
| Regularized
---
test loss
(Jorgensen max)
| Regularized
---
test loss
(Jorgensen mean)
0.01 | $\mathbf{1.25\crossproduct 10^{5}}$ | $1.58\crossproduct 10^{5}$ | $3.12\crossproduct 10^{5}$ | $\mathbf{1.25\crossproduct 10^{5}}$ | $1.56\crossproduct 10^{5}$ | $3.01\crossproduct 10^{5}$
0.05 | $\mathbf{1.08\crossproduct 10^{3}}$ | $1.32\crossproduct 10^{3}$ | $2.60\crossproduct 10^{3}$ | $\mathbf{1.13\crossproduct 10^{3}}$ | $1.37\crossproduct 10^{3}$ | $2.76\crossproduct 10^{3}$
0.10 | $\mathbf{1.38\crossproduct 10^{2}}$ | $1.75\crossproduct 10^{2}$ | $3.28\crossproduct 10^{2}$ | $\mathbf{1.54\crossproduct 10^{2}}$ | $1.96\crossproduct 10^{2}$ | $3.75\crossproduct 10^{2}$
0.50 | $\mathbf{1.35}$ | 1.78 | 3.26 | $\mathbf{2.10}$ | 2.73 | 4.99
0.60 | $\mathbf{8.33\crossproduct 10^{-1}}$ | 1.02 | 1.96 | $\mathbf{1.36}$ | 1.63 | 3.21
0.70 | $\mathbf{5.31\crossproduct 10^{-1}}$ | $6.89\crossproduct 10^{-1}$ | 1.26 | $\mathbf{9.54\crossproduct 10^{-1}}$ | 1.16 | 2.25
0.80 | $\mathbf{3.64\crossproduct 10^{-1}}$ | $4.66\crossproduct 10^{-1}$ | $8.96\crossproduct 10^{-1}$ | $\mathbf{6.93\crossproduct 10^{-1}}$ | $9.05\crossproduct 10^{-1}$ | 1.73
0.90 | $\mathbf{2.67\crossproduct 10^{-1}}$ | $3.43\crossproduct 10^{-1}$ | $6.46\crossproduct 10^{-1}$ | $\mathbf{5.39\crossproduct 10^{-1}}$ | $6.82\crossproduct 10^{-1}$ | 1.28
1.00 | $\mathbf{1.98\crossproduct 10^{-1}}$ | $2.45\crossproduct 10^{-1}$ | $4.71\crossproduct 10^{-1}$ | $\mathbf{4.35\crossproduct 10^{-1}}$ | $5.27\crossproduct 10^{-1}$ | 1.00
2.00 | $\mathbf{3.96\crossproduct 10^{-2}}$ | $5.00\crossproduct 10^{-2}$ | $8.04\crossproduct 10^{-2}$ | $\mathbf{1.06\crossproduct 10^{-1}}$ | $1.28\crossproduct 10^{-1}$ | $2.43\crossproduct 10^{-1}$
3.00 | $\mathbf{2.11\crossproduct 10^{-2}}$ | $2.33\crossproduct 10^{-2}$ | $3.84\crossproduct 10^{-2}$ | $\mathbf{4.80\crossproduct 10^{-2}}$ | $6.15\crossproduct 10^{-2}$ | $1.17\crossproduct 10^{-1}$
5.00 | $\mathbf{1.11\crossproduct 10^{-2}}$ | $1.27\crossproduct 10^{-2}$ | $1.78\crossproduct 10^{-2}$ | $\mathbf{2.02\crossproduct 10^{-2}}$ | $2.50\crossproduct 10^{-2}$ | $4.77\crossproduct 10^{-2}$

Table 14: Improvements in variability of the test loss: Standard deviation of
our algorithm is always lower, results on Medical cost dataset, while varying
the regularization parameter $\lambda$, keeping
$\varepsilon_{c}=0.01,\varepsilon_{m}=0.2,\varepsilon_{l}=1.0,f_{c}=0.34,f_{m}=0.43$.