Posthoc Privacy guarantees for neural network queries
Authors: Abhishek Singh
Praneeth Vepakomma
Vivek Sharma
Ramesh Raskar
Venue: Submitted to ICLR 2023 (2023)
Keywords: data privacy
differential privacy
privacy preserving machine learning
adversarial learning

Abstract: Cloud based machine learning inference is an emerging paradigm where users share their data with a service provider. Due to increased concerns over data privacy, recent works have proposed using Adversarial Representation Learning (ARL) to learn a privacy-preserving encoding of sensitive user data before it is shared with an untrusted service provider. Traditionally, the privacy of these encodings is evaluated empirically as they lack formal guarantees. In this work, we develop a new framework that provides formal privacy guarantees for an arbitrarily trained neural network by linking its local Lipschitz constant with its local sensitivity. To utilize local sensitivity for guaranteeing privacy, we extend the Propose-Test-Release(PTR) framework to make it tractable for neural network based queries. We verify the efficacy of our framework experimentally on real-world datasets and elucidate the role of ARL in improving the privacy-utility tradeoff.

Under review as a conference paper at ICLR 2023
POSTHOC PRIVACY GUARANTEES FOR NEURAL NET- WORK QUERIES
Anonymous authors Paper under double-blind review
ABSTRACT
Cloud based machine learning inference is an emerging paradigm where users share their data with a service provider. Due increased concerns over data privacy, recent works have proposed using Adversarial Representation Learning (ARI.) learn a arivacy-preserving encoding of sensitive user data before it is shared with an untrusted service provider. Traditionally, the privacy of these encodings is evaluated empirically as they lack formal guarantees. In this work, we develop a new framework that provides formal privacy guarantees for an arbitrarily trained neural network by linking its local Lipschitz constant with its local sensitivity. To utilize local sensitivity for guaranteeing privacy, we extend the Propose- -est- Release (PTR) framework to make tractable for neural network based queries. We verify the efficacy of our framework experimentally on real-world datasets and elucidate the role of ARL in improving the privacy-utility tradeoff.
INTRODUCTION
The ethical and regulatory concerns around data privacy have become increasingly important with the adoption of machine learning (ML) across various sectors such as health, finance, and mobility. Although training ML models privately has seen tremendous progress(Abare et al.) (2016); Papernot ct al. (2016): : Du et al. (202T) y; Jordon et al. (2018) in the last few years, protecting privacy during the inference phase remains a challenge as these models get deployed by cloud based service providers. Cryptographic techniques Ohrrimens et al. (20 20; Knott et al. (2021); Mishra et al. (2000) Juvekar al. (018)) address this challenge by performing computation over encrypted data. However, to combat the high computational cost of encryption techniques, alternative works have used ARL to suppress task irrelevant information from data. While ARL based techniques have shown promising empirical results, they lack formal privacy guarantees over obfuscated representations due to their use of Deep Neural Networks (DNNs) for achieving privacy. For the first time, we show how to give formal privacy guarantees for inference queries over arbitrarily trained (including ARL) DNNs.
The key aspect of any ARL algorithm is an obfuscator which is trained to encode a user's private data such that attacker can not recover the original data from its encoding. Achieving formal privacy guarantees for an obfuscator has remained elusive due to the non-convexity of the training objective of DNNs. In this work, we take posthoc approach to guaranteeing privacy, where the privacy of data is evaluated after the obfuscator is learned. Because the obfuscator is trained for non-invertibility. we hypothesize that the obfuscator network should act as contractive mapping, and hence, increase the stability of the function in its local neighborhood, i.e., reduce sensitivity. Therefore, we measure the stability of an adversarially learned obfuscator neural network, using Lipschitz constants, and link it with privacy properties. To exactly compute the local Lipschitz constant of a non-linear (ReLU) DNNs, we use LipMippJordan & Dimakis (2020). a mixed-integer programming based technique, and re-formulate the ARL pipeline to ensure the computational feasibility of calculating the Lipschitz constant. To draw a connection between the local Lipschitz constant and reconstruction privacy, we introduce a privacy definition that is a specific instantiation of a general dx-privacy framework by Chatzikokolakis et al. 2..3). Instead of evaluating the global Lipschitz constant of DNNs, we evaluate the Lipschitz constant only in the local neighborhood of the user's sensitive data. We extend the Propose- Test-Releat Release (Dwork & Lei (2009) framework to formalize our local neighborhood based measurement of the Lipschitz constant.

---

Under review as a conference paper at ICLR 2023
The scope of our paper is provide privacy guarantees against reconstruction attacks for existing ARL techniques, i.c., our goal is not to develop new ARL technique but rather to develop a formal privacy framework compatible with existing ARL techniques. A Majority of the ARL techniques protect either a sensitive attribute or reconstruction of the input. We only consider sensitive input in this work. We adopt different threat model from that of traditional differential privacy (DP))Dwork) ett al. (2014)) because, as we explain later, protecting membership inference is at odds with private inference. Our threat model for the reconstruction attack is motivated by the use cases where user may be willing to disclose coarse -arriieg information about their data but wants to prevent leakage of fine ane-grained information. Alternate threat models have been widely used in the privacy literature(Chatzian Chatzikokolakis et al. (2013); Kifer & Machanavarjhala (2014); (Andéé et al. (2013); Hannun et al. (2021)). Furthermore, we only focus on protecting the privacy of data during the inference stage, and assume that MI. models can be frained privately.
Typically ARL techniques evaluate the privacy of their representations by empirically measuring the information leakage using proxy adversary. Existing works et al. (2019); Guo et al. (20TT: ; Singh et al. (202T)) show that a proxy adversary's 's performance as a measure of protection
could be unreliable. Some of the existing ARL techniques have used theoretical tools(Hamm (2017)
Zhao et al. (2020b); Basciftci Bascifficc et al. (016);; Zhao et al. (2020a); Wang et al. (2017); Bertran et al. (2019); Mireshghallah al. (202 for measuring information leakage empirically. However, most of these works analyze specific obfuscation techniques and lack formal privacy definitions. In contrast, our work is agnostic the design of the obfuscator as long as it is differentiable, and our definition is built upon a variant of DP a widely used formal privacy framework. Our privacy definition and mechanism built upon dx-privacy SrrrrayyChatziooolllan (2009). Existing instantiations of dx-privacy include geo-indisting reo-indistinguiie inniininnuuushabblly.. lasisiiiitttyyyddrs et al. (2013)) and location -eeeedeend privacy (Konooooioiisinss & Pappas] (2016) that share a similar goal as ours of sharing coarse grained information. Our work differs in its usage of neural network queries and high dimensional data modality. We refer the reader to Appendix Sec A a detailed literature review.
al. (2013)) and PTR(Dwork & Lei
In Sec 2 we begin with the preliminaries of DP and its variant for metric spaces. Then, we motivate our ML inference setup and introduce our privacy definition in Sec Next, we construct our posthoc framework by extending PTR and proving its privacy guarantees in Sec In Sec we experimentally demonstrate the feasibility of our framework and understand the dynamics ARL algorithms. Our contributions be summarized as follows:
We introduce (c, 6, Reighbooordd privacy definition to formalize reconstruction privacy for ARL based inference.
We extend the PTR framework to make it tractable for neural network based queries. Our extension bridges the gap between formal privacy frameworks and empirical techniques in private ML inference.
We perform extensive experimental analysis ARL techniques and provide insight into how ARL improves the privacy-utility tradeoff by reducing the local sensitivity of DNNs.
2 PRELIMINARIES
Differential privacy (DPr) et al. (2014) is widely used framework for answering query, f. on a dataset x E X by applying a mechanism M(.) such that the probability distribution of the output of the mechanism M(x) is similar regardless the presence or absence of any individual in the dataset x. More formally, M satisfies (e, 8D if Vx, x' E X such that di (x, x') S 1, and for all (measurable) output S over the range of M
P(M(x) E S) S <'F(M(X') E S) +
where du is the hamming distance. This definition is based on a trusted central server model, where a trusted third party collects sensitive data and computes M(x) to share with untrusted parties. In et al. 1))1.)). this model has been extended such that each user shares M and the service provider is untrusted. Our threat model is a special case local DP which we refer to single-instance sharing. In this setup, the client queries every data instance independently with the service provider and there is no aggregation or summary statistic involved. For ex-- a user shares face image to receive age prediction from the service provider. While our setup
Decal-DP(Kasiviswaaattn
2

---

Under review as a conference paper at ICLR 2023
Trusted Device
Servic Proviler
Dog
Chassifier
Cat
Postoo Privary Frmnwwrrk
Inge Spoce
Enbeeder
Invetiiee Nap
Emhedder
Oblisazer
Obluseator
Podlox
Fearewidk
Eubboldingg
Oidteccted
Figure Posthoc Privacy framework: We project high dimensional data instance lower dimensional embedding. The goal of the embedder is to measure a semantically relevant distance between different instances. The embedding is fed the Obfuscator that compresses similar inputs in small volume. In traditional ARL, the obfuscated instance is shared with the untrusted service provider without any formal privacy guarantee. In this work, by analyzing the stability of the obfuscator network, we perturb the obfuscated instance to provide a formal privacy guarantee.
similar to item-level local DP, the answer the query depends exactly on single input. We note that du (x)x) < 1, Vx, X, whenever single-instance sharing is involved. Informally, this notion of neighboring databases under the DP definition would suggest that the outcome of two individuals should be similar matter how different their datum is. This privacy definition could be too restrictive for our ML inference application where data instance necessarily needs a certain degree of distinguishability to obtain utility from the service provider. This observation is formalized the impossibility result of instance encoding( et al. (2020)) for private learning. To subside this fundamental conflict between the privacy definition and our application, look at the definition of dx ------aayyChaazioookoni Chatzikokollkiss et al. (2013)) that generalizes the DP definition to a general distance metric beyond hamming distance follows:
P(M((x) E) < (xxx E S),
here (x,x,, x') is function that gives level indistinguishabiiity between two datasets x and x'. DP can be viewed special of dx-privacy by keeping dx dx(xx'') ed (x, Choosing different distance metric yields stronger or weaker privacy guarantec.
3 PRIVACY DEFINITION
In order to formalize reconstruction privacy, we hypothesize that semantically similar points are close each other data manifold, i.c. semantically similar samples are closer in space where distances are defined as geodesic on the manifold. Therefore, one way to bound the reconstruction of x is by making indistinguishable among semantically similar points. The extent of reconstruction privacy would therefore depend upon the radius of the neighborhood. We formalize it by introducing a privacy parameter R that allows user control how big this indistinguishable neighborhood should be. This formulation leads to two additional constraints i) distance metric that models low dimensional manifold space data; ii) a privacy definition that incorporates the privacy parameter R as well as the distance metric. We propose to embedding based manifold learning techniques(rrchmer & Cranmer 2020); Horvat & Pfister (202I) for the first constraint because we do not have a closed form expression for the manifold chart for real world data. We refer to the distance metric as dy (x, x'), where the parameter 0 is learned to model the data manifold and 3 is standard norm such as e, lz. Intuitively, we want to compute distances a space where semantically similar data points are closer and semantically different data points are farther apart. For high dimensional datasets that lie
3

---

Under review as a conference paper at ICLR 2023
over low dimensional manifold (such as images), traditional distance metrics like f1. l2 norms do not capture the semantic similarity. This idea has been used in perceptual similarity for computer vision Zhang al. (2018)) as well as manifold and metric learning techniques(Brehmer & Cranmer
(200)) Horvat & Pfister (202T); Kha Vul (202T). Hence, we instantiate dx-privacy by keeping
(x(x, edg x x') such that,
P(M(x) E S) S (xx)' (((e(xx)((((()))) P(M(x') E S) +
(2)
The privacy parameter describes the extent of indistinguishabiity and the parameter R describes the neighborhood which we obtain this indistinguishabiiity. We note that dx-privacy, unlike DP, does not use the notion of a neighborhood (dg (x, x') < R) because the guarantee holds for any possible pair of x,x' E X and smoothly decays with distance. Finally, slightly weaken the dx-privacy instantiation by defining neighborhood as (x(xx') S and keeping fixed levels of indistinguishabiliyy dg (x, x') S R.
Definition 1. A mechanism M satisfies (e, R)-semantic meighborhood privacy if x' E X S.J. dg (x, x') S R and 8 S Range(M)
P(M(X) E S < E ES)+ +
(3)
Note that the above equation is exactly the same as (e, 6D-DP except for the definition of neigh- boring databases. In this way, our privacy definition can be seen as a mix of standard DP and dx-prviacy. A key characteristic of Eq that points closer to a given x than R enjoy higher indistinguishability while in Eq 3g]]ll all points in the neighborhood of x, similar to DP, get the same level of indistinguishabiiity.
3.1 COMPARISON WITH DIFFERENTIAL PRIVACY
Conceptually, usage of hamming distance in DP for neighboring databases provides level of protection such that the output does not change significantly regardless of the chosen sample. Such a privacy requirement can be odds with the goal of prediction that necessarily requires discrimination between samples belonging to different concept classes. Our privacy definition relaxes this dichotomy by using distance metric in the embedding space and guarantees privacy only within a neighborhood. The size of the neighborhood is privacy parameter R such that higher value of R provides higher privacy. This privacy parameter is equivalent to the group sizrrDwork al. (2014) used sometimes in the DP literature. By deffaul,, this value is kept I in DP but can be kept higher if group of individuals (family, community) have to be privatized instead of single individual. There is an equivalence between the group privacy definition and standard DP definition which we state informally Lemma 2.2 in Vadhan (2017): Any (f. d)-differentially private mechanism is (Re, ()))))))))- differentially private for groups of size R. This lemma also applies to our proposed definition. However, we emphasize that privacy parameters of (e, dD mechanism can not be compared trivially with a (e, d, R)-semantic neighborhood privacy mechanism because same value of and 5 provide different levels of protection due to different definitions of neighboring databases. We experimentally demonstrate this claim in Sec
4 PRIVACY MECHANISM
Our goal is design a framework that can provide formal privacy guarantee for single data instance sharing that is informally privatized using ARL. However, ARL algorithms use non- linear neural networks trained on non-convex objectives making difficult to perform any worst-case analysis. Therefore, we take posthoc approach where the formal privatization is performed after the model trained. Specifically, we apply propse-test-releas (PTR) mechanism by Dwork & Lei (2009). Applying PTR directly to our query (ARL) is not computationally feasible because PTR requires estimating local sensitivity at multiple points whereas evaluating local sensitivity of a neural network query is not even feasible utilizes local lipschitz constant estimator to compute privacy related parameters. We refer the reader to Appendix for detailed discussion on the lipschitz constant estimation and PTR.
single point. Therefore, we design a tractable variant of PTR that
Conventionally, ARL algorithms have three computational blocks during the training stage: 1) obfuscator (f(-) that generates (informally private) representation (%) of data, 2) proxy adversary
4

---

Under review as a conference paper at ICLR 2023
that reconstructs the data from the representation produced by the obfuscator, and 3) classifier that performs the given task using the obfuscated representation. The classifier and proxy adversary are trained to minimize the task loss and reconstruction loss, respectively. The obfuscator is trained to minimize the task loss but maximize the reconstruction loss. This setup results in a min-max optimization where the trade-off' between task performance and reconstruction is controlled by hyper-parameter a. Note that some techniques et al. (2016); Osia et al.) (2020); Vepakomma et al. (202T) do not require a proxy adversary but still learn an obfuscator model using other regularizers. We propose to use an embedder (g) to learn semantic similarity using VAE(Kingma & Welling (2013)). The key idea of using the embedder
to embed the original sample (x) to a lower dimensional space (z- g()) such that the distance metric in z space captures semantic similarity as shown in Fig and motivated in See 3 Since z can be (almost) loss-lessly inverted to x, is fed to the obfuscator to get 2 = (2).
Our framework applies the mechanism M such that the final released data MMx) has a privacy guarantee discussed in Eq 3 Like PTR, we start with proposal (A),s) on the upper bound of the local sensitivity of x. To test the validity of Ai.s we compute the size of the biggest possible neighborhood such that the local Lipschitz constant of the obfuscator network in the neighborhood is lesser than the proposed bound. Next, we privately verify the correctness of the proposed bound for the given data instance. We do not release the data (denoted by 1) if the proposed bound is invalid. Otherwise, we perturb the data using Laplace distribution calibrated by the proposed bound. Next, we discuss the framework and privacy guarantees in more detail.
Global Sensitivity and Lipschitz constant of a query f ; -X - Y are essentially same in the dx-privacy framework. Global sensitivity of a query f(-) is the smallest value of Á (if it exists) such that Vx, x' E X. (x), (xx)) I Adx x'). While global sensitivity is a measure over all possible pairs of data in the data domain X, local sensitivity (ALs) is defined with respect to a given dataset x such that Vx E X, dx(f()), S Ar,s(x)dx x'). ). We integrate the notion of semantic similarity in a neighborhood (described in S by defining the local sensitivity of a neighborhood Nxx, R) around x of radius R such that NN R) = [x'|dx [xxxxxxxxxx (x,x') I R, Vx E X). Therefore, the local sensitivity of query f on x in the R-neighborhood is defined Vx E N(x, R) such that
(x(f f(x)) S ALs(x, R)dx(x,x'),
(4)
We note that if dy is hamming distance and R is then this formulation is exactly same as local sensitivity in DDDrk et al. (2014)). The equation above can be re- we-ttitten as:
dx()(x),((x))) dx(xxx))
ALS(X, R) = sup
(5)
x(E((x88
This formulation of local sensitivity is similar to the definition of the local Lipschitz. constant. The local Lipschitz constant L of for given open neighhorhood. N S X is defined as follows:
(x5(x') f(x")lla
L (F.N)
sup x'XxENN
(x'*x")
(6)
-x
We note that while the local sensitivity of x is described around the neighborhood of x, the Lipschitz constant is defined for every possible pair of points in a given neighborhood. Therefore, in Lemma 4.1 we show that the local Lipschitz in the neighborhood of x is an upper bound on the local sensitivity. Lemma 4.1. For a given I and for dy + la and dx Egg, (xs(x) S L(J,N((x Proof in Appendix B.1
Since local sensitivity is upper bounded by the Lipschitz constant, evaluating the Lipschitz constant suffices as an alternative to evaluating local sensitivity.
Lower bound on testing the validity of Ai, The PTR algorithm(Dwork & Lei 2009) suggests a proposal on the upper bound (A)ss of local sensitivity and then finds the distance between the given dataset (x) and the closest dataset for which the proposed upper bound is not valid. Let 7()) be a
distance query and AL.( be the local sensitivity defined as per the DP framework with respect to x such that
7x) = min (d (x, x') s.l. Ars(x') > A
x'EX
In our framework, the query 7(x, R) can be formulated in the semantic neighborhood follows:
7x, R) min (dx (x,x') s.t. ALs(x', RR) A.
(8)
5

---

Under review as a conference paper at ICLR 2023
We note that keeping dx dæ and R 1, makes the query exactly same defined in the eq 7 In our setup, computing 7(-) is intractable due to local sensitivity estimation required for every x' E X (which depends upon non-linear neural network). We emphasize that this step is intractable at two levels, first we require estimating local sensitivity of a neural network query. Second, we require this local sensitivity over all samples in the data domain. Therefore,
make it tractable by computing a lower bound over 7(x, R) by designing a function Φ(.) s.t. 6(x, < 7(x, R). Intuitively, <(-) finds the largest possible neighborhood around x such that the local Lipschitz constant of the neighborhood is smaller than the proposed local sensitivity. Because the subset of points around whose neighborhood does not violate ALs is half of the size of the original neighborhood in the worst case, we return half of the size of neighborhood as the output. We describe its computation Algorithm [ More formally,
(xx R) 2
arg max (exxx(C(f////// & Ais)
R2R
If there is no solution to the equation above, then we return
Lemma 4.2, R) S (xx,)) R). Proof in Appendix B.2
The next step in the PTR algorithm requires testing if (xx) I ln(t)/e. If the condition is true, then no-answer (11) is released instead of data. Since the 7 query depends upon x, PTR privatizes it by applying laplace mechanism, i.e. fx) = query has sensitivity of since the y could differ at most by I for any two neighboring databases. In our framework, we compute Φ(x, R) to lower bound the value of yxx, R). Therefore, we need to privatize the & query. For general distance metrics in dx -p-iriiy the global sensitivity of the ((x) query is 1.
Privately testing the lower bound:
The
Lemma 4.3. The query Φ(-) has a global sensitivity of i.e. Vx, E X, (o(x, o(x',)) S dx xx)x))). Proof in Appendix B.3
After computing (xx, R), we add noise sampled from a laplace distribution, i.e. q(x, R) = o(xx R)
Lap(R/e). Next, we check if Φ(x, I ln(3)) R/e, then we release 1. otherwise we release
2 = fx(()) + Las(A))ss/e). Next, we prove that the mechanism Mi described above satisfies semantic neighborhood privacy..
Theorem 4.4. Mechanism Mi satisfies uniform (2e,8/2. R) -emanntic neighborhood privacy Eq. i.e. Vx, x' E s.t. dx(xxx' x') S
8
P(M(() =(PM)))) E
Proof Sketch: Our proof is similar to the proof for the PTR (aanework(Dwork al. (2014)) except the peculiarity introduced due to our metric space formulation. First, we show that not releasing the answer (1) satisfies the privacy definition. Next, we divide the proof into two parts, when the proposed bound is incorrect (i.e. A A R) query Ø.
AEs) and when it is correct. Let Å be the output of
Pl R) = R] P x R) R]
(pp(-(1(xx8)) exp(- [((xx.) RI
R c))
exp( (xx'' R) < exp(1x(x,, H(x R) : < exp((x(xxx)) R
exple)
Therefore, using the post-processing property . P[M(x) = 1T S M( = 1]. Here, the first inequality is due to triangle inequality, the second one is due to Lemma 4.3 and the third inequality follows from dx(x, x') I Note that when ( R) > ALs. o(x,)) = Therefore, the probability for the test to release the answer in this case is
PlM(x)+ + 1] Plp(x, R) Lap( R
R
R - P\Lap
log 1 R - {)
log( {
-
Based the CDF of Laplace distribution, PxM((x= # 1|= 4. Therefore, if A R) A AL for any S _ 1Rd U in the output space of M
PP(((x) S) PP((()) E Sn (1)

---

Under review as a conference paper at ICLR 2023
MNIST
0, 0.100))
0c,
0.93)
PMNIST
0, (.0010) (r
oc, 0.781)
UTKFace (r
0, 0,0.002, (r
0c, 0.732)
Informal
<-
<-5 < 10
Informal
[-
[-
[--
c-
Informal
c-
c
Enoder
0.93
0.428
0.673
0.883
0.921
0.779
0.228
0.355
0.605
0.722
0.724
0.617
0.673
0.717
0.721
ARL
0.917
0.329
0.532
0.792
0.882
0.747
0.214
0.319
0.557
0.685
0.605
0.649
0.691
0.707
C
0.926
0.443
0.684
| 0.881
0.917
0.781
0.158
0.225
[0.422
0.608
0.73
0.623
| 0.673
0.718
0.724
N
0.923
0,279
0.496
0.816
0.902
0.559
0.136
0.177
0.310
0,462
0,725
0.614
0.667
0,708
0.715
ARL-C
0.896
0.424
0.648
0.839
0.883
0.761
0.196
0.314
0.537
0.682
0.709
0.632
0.684
0.70
0.705
ARL-N
0.88
0.118
0.139
0.21
0.325
0.717
0.294
0.467
006657
0.705
0.71
0.628
0.674
0.701
0.708
C-N 0,929
0.574
0.844
0.913
0.774
0.161
0.224
00:411
0.559
0.727
0,712
0.722
ARL-C-N
0.921
0.514
0.751
0.891
0.912
0.706
0.371
0.554
0.678
0.695
0.712
0.650
0.690
0,700
0.700
Table 1: Performance comparison for different baselines: Our posthoe framework enables com- parison between different obfuscation techniques by fixing the privacy budget (c). First four rows are different approaches to protect against data reconstruction and the remaining rows below are combinations of different approaches. The top row refers to the accuracy corresponding to different datasets under two extremes of epsilons. ARL refers to widely used adversarial representation learning approach for regularizing representation based a proxy attacker(Li et al. (2021): I); Liu jet al. (2019); Xiao et al. (2020); [Singh et al. (202T)). Contrastive refers to contrastive learning based informally privatizing mechanism introduced in Osia et al. (2020).
E E 8
< E (L)) +
If ALs(x, R) S Ass then the mechanism is a composition of two (c, R)-semantic neighborhood private algorithm where the first algorithm (ø(x, R)) is (c. 5/2, R)-smantic neighborhood private and the second algorithm is (c, O, Rpprvivtte. Using composition, the algorithm is (2c, 6/2, R) - neighborhood private. We describe Mi step by step in Algorithm | To summarize, we designed the posthoc privacy framework that extends the PTR framework by making it tractable to get (e, ó, R)- semantic neighborhood privacy. The exact local Lipschitz constant of the neural network based obfuscator is estimated using mixed-integed programming based optimization developed by Jordan &
Dimakis (020))
Computational feasibility: Our key idea is to add extra computation on the client side to formally reason about the privacy of shared data. This extra computational cost is due to the estimation of the local Lipschitz constant of the obfuscator network. However, three key factors of our framework make it practically feasible-
1.
We compute the local Lipschitz constant (i.e. in small neighborhood around given point): Our extension of the propose-test-relasee framework only requires us to operate in a small local neighborhood instead of estimating the global Lipschitz constant which would be much more computationally expensive.
2. Low number of parameters for obfuscator: Instead of estimating the Lipschitz constant of the whole prediction model, we only require estimation of the obfuscator a neural network that has significantly lower number of parameters in comparison to the prediction model.
3. Lower dimension of input embedding: Since we measure distance in the embedding space. the dimensions over which the local Lipschitz constant is estimated are significantly lower than the ambient data dimension.
We performed an ablation study on all three aspects mentioned above in Sec 6 The fact that the local Lipschitz constant is being computed over the same obfuscator allows room for optimizing performance by caching. Our goal is demonstrate the feasibility of bridging formal privacy guarantees and ARL-based mechanisms, hence, we did not explore such performance speedups.
5 EXPERIMENTS
Experimental Setup: We evaluate different aspects of our proposed framework i) E1: compar- ison between different adversarial appraches, ii) E2: comparison with local differential privacy (LDP). iii) E3: computational tractability of our proposed framework, and iv) E4: investigating role of ARL in achieving privacy. We use MNIST(LeCun (1998)) FMNIST(Xiao et al. (2017))
7

---

Under review as a conference paper at ICLR 2023
and UTKFaace (Zhang al. (0117) dataset for all experiments. All of them contain samples with extremely high ambient dimensions (MNIST-784, FMNIST-784 and UTKFFace40966, We use a deep CNN based 3- B-VAE B-VAE(Higgins et al. ) for the embedder. We use LipMip[Jordan & Dimakis (2020) for computing Lipschitz constant over fee norm in the input space and & norm in the output smaller space. We baseline with simple Encoder based approach where the data is projected dimensions using a neural network. This encoder type approach has been used in the literature as Split Learning Gupta & Raskar (2018). For ARL, we use the proxy-adversary based min-max optimization used by several ARL techniques (oian et al. (2020); (Singh et al. (202T); Liu et al. (2019); : [i et al. (aan (202I)) and adversarial contrastive learning Osia et al. (2020)) which we denote as C. We use noisy
regularization (denoted by N) to improve classifier performance. We refer the reader to sec F for detailed experimental setup, codebase and hyper-parameters.
Since our framework enables comparison between different obfus- cation techniques under same privacy budget, we evaluate test set accuracy on three image datasets in Table Our results indicate that ARL complemented with contrastive and noise regularization helps in attaining overall best performance among all possible combinations. We note that the SoTA performance on all three datasets is higher than experimental setup because of the usage of embedder that can be further improved to yield higher accuracy.
E1: Privacy-Uttiset Utility Trade-off:
E2: Comparison between ARL and LDP: While c-LDP definition provides different and stronger privacy guarantee than our proposed privacy definition, we compare the performance between ARL and LDP and report results in the Table 2 in the Appendix for the sake of completeness. Results indicate that for low value of e, LDP techniques do not yield any practical utility. This observation corroborates with impossibility result of instance encoding Carlini al. (2020) and our discussion in Sec about applicability of traditional DP in the context of ARL.
E3: Computational feasibility: Our framework relies upon the exact computation of Lipschitz constant of ReLU networks (obfuscator in our case) that has been shown to be a NP-hard prob- lem(Jordan & Dimakis (2020). Our end-to-end runtime evaluation on CPU based client results in a runtime of 2 sec/image (MNIST) and 3.5 sec/image (UTKFace). While plenty of room ex- ists for optimizing this runtime, we believe current numbers serve as a reasonable starting point for providing formal privacy in ARL. As discussed in See 4 we compare computation time of the obfuscator across three factors relevant to our setup - i) Dimensionality of the input, ii) Size of the neighborhood, and iii) Number of layers in the Obfuscator. Figure 4 shows performance evaluation. While the running time quickly grows exponentially with input size, we emphasize that the obfuscator network requires only small number of dimensions due to its input residing on the embedding space. Results demonstrate that not only the framework is computationally tractable but it can be executed real-time speed for our inference use-case.
E4: What role does ARL play in achieving privacy? In this experiment, we assess the contribution of adversarial training in improving privacy-utility trade-off. We train obfuscator models with different values of (weighing factor) for adversarial training. Our results in Fig 2 indicate that higher weighing of adversarial regularization reduces the local lipschitz constant, hence reducing the local sensitivity of the neural network. Furthermore, for high values of o, the change in local lipschitz constant reduces significantly for different size (R) of the neighborhood. These two observations can potentially explain that ARL improves reconstruction privacy by reducing the sensitivity of the obfuscator. However, as we observe in Table D the classifier can reduce its utility if ARL not complemented with noisy and contrastive regularization. We believe this finding could be of independent interest for the adversarial defense community where the goal is to reduce misclassification performance of neural networks.
6 DISCUSSION
How to select privacy parameter R? One of the key difference between (c, 6, R) neighborhoddd privacy and (e, 6)- is the additional parameter R. The choice of R depends upon the neighborhood in which a user wishes to get level of indistinguishabiitty We perform reconstruction attacks on privatized encoding obtained from our framework by training an ML model to reconstruct original images. We compare reconstruction results for different values of c and R four distinct metrics for images in Table 3 To assess the level of indistinguishabilit. we look at Fig 3 where project the original images into embedding space and sample points from the boundary of
8

---

Under review as a conference paper at ICLR 2023
25
20
Local lipschitz constant
6.5
0.16
(0.01.001,02.00333..44
Figure 2: Local sensitivity comparison for different values of a: The five bars for each a represent different neighhorhood radii. Increase in the value of a decreases the local Lipschitz constant (upper bound on local sensitivity) indicating lesser amount of noise be added for the same level of privacy.
neighborhoods of different R. We observe that as the boundary of the neighborhood increases, the images become perceptually different from the original image. For extremely large radii, the images change significantly enough that their corresponding label may change too. Such visualization can be used semantically understand different values of R.
How to propose DE.² Our framework requires proposal on the upper bound of local sensitivity in a private manner. One possible way to obtain Ai is by using the Lipschitz constant of training data samples used in training the obfascator. To incorporate this notion of average, choose A L.s by first computing the mean (J)) and standard deviation (a) of local sensitivity on the training dataset where allows
(assumed to be known under our threat model), then keep A μ + trade-off between the likelihood of releasing the samples under PTR and adding extra noise to data. We used 3 in our experiments. Since empirically, the value of local sensitivity appears to be following gaussian, using confidence interval serves as a good proxy. Fig [igg2shon shows that for higher values of a, the variability in the local Lipschitz constant decreases indicating the validity of the bound would hold for a large number of samples. We emphasize that privacy parameters should be chosen independently the private data otherwise the guarantees do not hold.
Limitations: i) The distance metric (d (x, x')) is currently learned from data and could lead to irrelevant privacy guarantees if semantically similar points farther apart in the embedding space. We believe this limitation could be addressed by understanding the convergence of these learned distance metrics. Furthermore, these learned distance metrics might be better than not assessing privacy formally at all or using distance metrics like ( f2 norm in the ambient dimension of data. ii) Since utilize the PTR framework, outlier samples may not get released due to high sensitivity, this is expected since these outlier samples are likely to be misclassified anyway. iii) Lipschitz constant computation is limited ReLU networks, therefore more sophisticated obfuscator architectures currently not compatible with our proposed framework.
CONCLUSION
ML based approaches to private inference have been on a rise in the past few years owing to the powerful representational capacity of neural networks, especially for complex real-world datasets. Their main drawback the lack of formal privacy guarantees. Our work has taken the first steps towards formal privacy guarantee for a broad class of existing empirical techniques for privacy. We believe that our framework would foster more research in ARL techniques by improving privacy- utility evaluation and take them closer real world adoption.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Miguel E Andrés, Nicolás E Bordenabe. Konstantinos Chatzikokolakis, and Catuscia Palamidessi. tee-iidistinguishabbltt: Differential privacy for location based systems. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pp. 901-914 2013.
Yuksel Ozan Basciftci, Ye Wang. and Prakash Ishwar. On privacy-utility tradeoff's for constrained data release mechanisms. In 2016 Information Theory and Applications Workshop (ITA), pp. 1-6. IEEE, 2016.
Martin Bertran, Natalia Martinez, Afroditi Papadaki, Qiang Qiu, Miguel Rodrigues, Galen Reeves, and Guillermo Sapiro. Adversarially learned representations for information obfuscation and inference. In International Conference on Machine Learning, pp. 614-623. PMLR, 2019.
Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. Protec- tion against reconstruction and its applications in private federated learning. arXiv preprint arXiv:1812.00984, 2018.
Johann Brehmer and Kyle Cranmer. Flows for simultaneous manifold learning and density estimation. Advances in Neural Information Processing Systems. 33:442-444 453, 2020.
Nicholas Carlini, Samuel Deng, Sanjam Garg, Somesh Jha, Saeed Mahloujifar, Mohammad Mah- moody, Shuang Song, Abhradeep Thakurta, and Florian Tramer. private learning possible with instance encoding? arXiv preprint arXiv:201 2020.
Konstantinos Chatzikokolakis, Miguel E Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi. Broadening the scope of differential privacy using metries. In International Sympo- sium on Privacy Enhancing Technologies Symposium, pp. 82-102. Springer, 2013.
Jian Du, Song Li, Moran Feng, and Siheng Chen. Dynamic differential-privacy preserving sgd. arXiv preprint arXiv:2111.000 1100073,, 2021.
Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the forty-fustt annual ACM symposium on Theory of computing, pp. 371-380, 2009.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4)2111-40) 2014.
Cynthia Dwork, Adam Smith, Thomas Steinke, and Jonathan Ullman. Exposed! a survey of attacks on private data. Annual Review of Statistics and Its Application, 4:61-84, 2017.
Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Vitaly Feldman and Tijana Zrnic. Individual privacy accounting via renyi filter. Advances in Neural Information Processing Systems, 34, 2021.
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael Cree. Regularisation of neural networks by enforcing lipschitz continuity. arxiv e-prints, page. arXiv preprint arXiv:1804.0433 2018.
Hao Guo, Brian Dolhansky, Eric Hsin, Phong Dinh, Cristian Canton Ferrer, and Song Wang. Deep poisoning: Towards robust image data sharing against visual disclosure. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 686-696, 2021.
Otkrist Gupta and Ramesh Raskar. Distributed learning of deep neural network over multiple agents.
Journal of Network and Computer Applications, 116:1-8, 2018.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022. URL https: www gurobi ccm
10

---

Under review as a conference paper at ICLR 2023
Jihun Hamm. Minimax filter: Learning to preserve privacy from inference attacks. The Journal of Machine Learning Research, 18(1):4704-477 4734, 2017.
Awni Hannun, Chuan Guo, and Laurens van der Maaten. Measuring data leakage in machine-learning models with fisher information. In Uncertainty in Artificial Intelligence, pp. 760-770. PMLR, 2021.
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with constrained variational framework. 2016.
Christian Horvat and Jean-Pasee Pfister. Denoising normalizing flow. Advances in Neural Information Processing Systems, 34, 2021.
Yujia Huang, Huan Zhang, Yuanyuan Shi, Zico Kolter, and Anima Anandkumar, Training certifiably robust neural networks with efficient local lipschitz bounds. Advances in Neural Information Processing Systems, 34, 2021.
Matt Jordan and Alex Dimakis. Provable lipschitz certification for generative models, In International Conference on Machine Leurning, pp. 5118-5126 PMLR, 2021.
Matt Jordan and Alexandros G Dimakis. Exactly computing the local lipschitz constant of relu networks. Advances in Neural Information Processing Systems, 33:7344-7353, 2020.
James Jordon, Jinsung Yoon, and Mihaela Van Der Schaar. Pate-gan: Generating synthetic data with differential privacy guarantees. In International conference learning representations, 2018.
Chiraag Juvekar, Vinod Vaikuntanathan, and Anantha Chandrakasan. {GAZELLE): A low latency framework for secure neural network inference. In 27th USENIX Security Symposium (USENIX Security 18), pp. 1651-1669, 2018
Shiva Prasad Kasiviswanathan, Homin Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 10(3):793-822 2011.
Chan Kha Vu. Deep metric learning: A (long) survey, 2021. URL hhu hto/aat.cclee/eeep-mettt...eeeee
Daniel Kifer and Ashwin Machanavajjhala. No free lunch in data privacy. In Proceedings of the 2011
ACM SIGMOD International Conference on Management of data, pp. 193-204, 2011.
Daniel Kifer and Ashwin Machanavajjhala. Pufferfish: A framework for mathematical privacy definitions. ACM Transactions on Database Systems (TODS), 39(1):1-36, 2014.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 1412:v:412.699000 2014.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint 1312.61 14, 2013.
Brian Knott, Shobha Venkataraman, Awni Hannun, Shubho Sengupta, Mark Ibrahim, and Laurens van der Maaten. Crypten: Secure multi-party computation meets machine learning, Advances in Neural Information Processing Systems, 34, 2021.
Fragkiskos Koufogiannis and George Pappas. Location-dependent privacy. 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 7586-7591. IEEE, 2016.
Fabian Latorre, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. arXiv preprint arXiv:2004.08688, 2020.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/nmist// 1998.
Ang Li, Jiayi Guo, Huanrui Yang, Flora D Salim, and Yiran Chen. Deepobfuscator: Obfuscating intermediate representations with privacy-preserving adversarial learning smartphones. In Proceedings of the International Conference on Internet-off Things Design and Implementation, pp-
28 28-39, 2021.
11

---

Under review as a conference paper at ICLR 2023
Yitong Li, Timothy Baldwin, and Trevor Cohn. Towards robust and tations. arXiv preprint arXiv: 06093, 2018.
text represen-
Katrina Ligett, Seth Neel, Aaron Roth, Bo Waggoner. and Steven Z Wu, Accuracy first: Selecting differential privacy level for accuracy constrained erm. Advances in Neural Information Processing Systems, 30, 2017.
Sicong Liu, Junzhao Du, Anshumali Shrivastava, and Lin Zhong. Privacy adversarial network: representation learning for mobile data privacy. Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies, 3(4):1-18, 2019.
Fatemehsadat Mireshghallah, Mohammadkazem Taram, Ali Jalali, Ahmed Taha Taha Elthakeb, Dean Tullsen, and Hadi Esmaeilzadeh. Not all features are equal: Discovering essential features for preserving prediction privacy. In Proceedings of the Web Conference 2021, pp. 669-680, 2021.
Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srinivasan, Wenting Zheng. and Raluca Ada Popa. Delphi: A cryptographic inference service for neural networks. In 29th USENIX Security Sympo- sium (USENIX Security 20), pp. 1505-2522 2020.
Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing.
pp. 75- 25-84,22 2007.
Seong Joon Oh, Rodrigo Benenson, Mario Fritz, and Bernt Schiele. Faceless person recognition: Privacy implications in social media. In European Conference on Computer Vision, pp. 19-35. Springer, 2016.
Olga Ohrimenko, Felix Schuster, Cédric Fournet, Aastha Mehta, Sehastian Nowozin, Kapil Vaswani, and Manuel Costa. Oblivious (Multi-Party) machine learning on trusted processors. In 25th USENIX Security Symposium (USENIX Security 16), pp. 619-636, 2016.
Seyed Ali Osia, Ali Shahin Shamsabadi, Sina Sajadmanesh, Ali Taheri, Kleomenis Katevas, Hamid R Rabiee, Nicholas D Lane, and Hamed Haddadi. A hybrid deep learning architecture for privacy- preserving mobile analytics. IEEE Internet of Things Journal, 7(5):4505-4518, 2020.
Nicolas Papernot, Martín Abadi, Ulfar Erlingsson, Ian Goodfellow, and Kunal Talwar. Semi- supervised knowledge transfer for deep learning from private training data. arXiv preprint arXiv:1610.05755. 2016.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer. F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024 8035. Curran Associates, Inc., 2019. URL /ttp:/ http:pppwrrrrrrrr.ececeeeeeeeeee cctpppprrccppppepepcppppppppp an
www.aaniinnniibarr...... library.
pdf
Hai Phan, My T Thai, Han Hu, Ruoming Jin, Tong Sun, and Dejing Dou. Scalable differential privacy with certified robustness in adversarial learning. In International Conference on Machine Learning.
pp. 7683-7694. PMLR, 2020.
Rafael Pinot, Florian Yger, Cédric Gouy-Pailler, and Jamal Atif. A unified view on differential privacy and robustness to adversarial examples. arXiv preprint arXiv:1906.00 079982, 2019.
Ryan M Rogers, Aaron Roth, Jonathan Ullman, and Salil Vadhan. Privacy odometers and filters: Pay-as-you-go composition. Advances in Neural Information Processing Systems, 29, 2016.
Proteck Chandan Roy and Vishnu Naresh Boddeti. Mitigating information leakage in image represen- tations: A maximum entropy approach. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2594, 2019.
12

---

Under review as a conference paper at ICLR 2023
Bashir Sadeghi and Vishnu Boddeti. On the fundamental trade-offs in learning invariant representa- tions. arXiv preprint Stt1:22009003886 2021.
Mohammad Samragh, Hossein Hosseini, Aleksei Triasteyn, Kambiz Azarian, Joseph Soriaga, and Farinaz Koushanfar. Unsupervised information obfuscation for split inference of neural networks. arXiv preprint arXiv:2104.11413, 2021.
Kevin Scaman and Aladin Virmaux. Lipschitz regularity of deep neural networks: Analysis and efficient estimation. Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 3839-3848, Red Hook, NY, USA, 2018. Curran Associates Inc.
Yonadav Shavit and Boriana Gjura. Exploring the use of lipschitz neural networks for automating the design of differentially private mechanisms. 2019.
Abhishek Singh, Ayush Chopra, Ethan Garza, Emily Zhang, Praneeth Vepakomma, Vivek Sharma, and Ramesh Raskar. Disco: Dynamic and invariant sensitive channel obfuscation for deep neural networks, In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 12125-12135, 2021.
Brij Mohan Lal Srivastava, Aurélien Bellet, Marc Tommasi, and Emmanuel Vincent. Privacy- preserving adversarial representation learning in asr: Reality or illusion? arXiv preprint arXiv:1911.04913, 2019.
Pierre Stock, Igor Shilov, Ilya Mironov, and Alexandre Sablayrolles. Defending against reconstruction attacks with r\ 'enyi differential privacy. arXiv preprint arXiv:220..07623, 2022.
Nurislam Tursynbek, Aleksandr Petiushko, and Ivan Oseledets. Robustness threats of differential privacy. arXiv preprint arXiv:2012.07828, 2020.
Salil Vadhan. The complexity of differential privacy. In Tutorials on the Foundations of Cryptography, pp. 347-450. Springer, 2017.
Praneeth Vepakomma, Abhishek Singh, Emily Zhang, Otkrist Gupta, and Ramesh Raskar. Nopeek- infer: Preventing face reconstruction attacks distributed inference after on- on-premise training. In 2021 16th IEEE International Conference on Automatic Face and Gesture Recognition (FG 2021), pp. 1-8. IEEF, 2021.
Ye Wang, Yuksel Ozan Basciftei, and Prakash Ishwar. Privacy-utility tradeoffs under constrained data release mechanisms. arXiv preprint arXiv:1710.0929: 2017.
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference on Machine Learning, pp. 5276-5285. PMLR, 2018.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking
machine learning algorithms, 2017.
Taihong Xiao, Yi-Hsuan Tsai, Kihyuk Sohn, Manmohan Chandraker, and Ming-Hsuan Hsuan Yang. Adver- and task-oriented representations. In Proceedings of the AAAI
sarial learning of Conference on Artificial Intelligence, volume 34, pp. 12441, 2020.
Richard Zhang, Phillip Isola, Alexei A Efros, Eli Shechtman, and Oliver Wang. The unreasonable effectiveness of deep features as a perceptual metric. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 586-595, 2018.
Zhifei Zhang, Yang Song, and Hairong Qi. Age progressionnregressoon by conditional adversarial autoencoder. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2017.
Han Zhao, Jianfeng Chi, Yuan Tian, and Geoffrey J Gordon. Trade-offs and guarantees of adversarial representation learning for information obfuscation. Advances in Neural Information Processing Systems, 33:9485-9499, 2020a.
Han Zhao, Chen Dan, Bryon Aragam, Tommi S Jaakkola, Geoffrey J Gordon, and Pradeep Raviku- mar. Fundamental limits and tradeoffs in invariant representation learning. arXiv preprint 1071:,, 2020b.
13

---

Under review as a conference paper at ICLR 2023
A RELATED WORK
ARL techniques aim to learn task-oriented privacy preserving encoding of data. Majority of the works in this area either protect against sensitive attribute leakage Hamm (2017); Roy & Boddeti (2019); Bertran et al. (2019;
: Li et al. (2018) or input reconstruction Samragh et al. (2021); |ingh et al. 2021) ); Mireshghallah et al. 2021 Li et al. (202T); Liu et al. (2019). These techniques usually evaluate their privacy using empirical attacks since the mechanism is learned using gradient based min-max optimization making it infeasible for the worst-case privacy analysis. The goal of our work is make them amenable to formal privacy analysis. While theoretical analyses Zhao et al. (2020a b); Sadeghi & Boddeti (202T) ARL objectives have identified fundamental trade-offs between utility and attribute leakage, they are difficult to formalize worst-case privacy guarantee especially for deep neural networks.
Privacy definitions that extend the DP definition to incorporate some of its limitations Kifer & Machanavaijhalal (2011) include dx-Privacy Chatzikokolakis et al. (2013), and Pufferfish Kifer Machanavaijhala (2014). Our privacy definition is a specific instantiation of the dx- Privacy Chatzikokolaki et al. (2013) framework that extends DP to general metric spaces. Our instantiation is focused on reconstruction privacy for individual samples instead of membership inference attacks Dwork et al. (2017). Existing works in DP for reconstruction attacks Bhowmick
al. 2018); Stock et al. (2022) focus on the privacy of training data.
Lipschitz constant estimation for neural networks has been used to guarantee network's 's stability to perturbatioon. Existing works either provide an upper bound Weng et al. (2018); Latorre al. (2020): Fazlyab et al. (2019). exact Lipschitz constant Jordan & Dimakis (2020) (021) or Lipschitz constant regularization Scaaman & Virmaux (20T8); Huann et al. (202T) during the training stage. Some existing works have explored the relationship between adversarial robustness and DP model training Phan et al. (2020); Pinot et al. (2019); 9): Tursynbek et al. (2020). We utilize similar ideas of perturbation stability but for privacy. Shavit and Giura[Shavit Shavit & Gjura (2019) Lipschitz neural networks Gouk et al. (018) to learn a private mechanism design for summary statistics such as median, however their mechanism design lack privacy guarantee.
Posthoc approach to privacy applies privacy preserving mechanism a data dependent manner. Smooth sensitivity Nissim et al. (2007) and PTR Dwork & Lei (2009) reduce the noise magnitude since local sensitivity is only equal to global sensitivity in the worst case. Privacy odometer Rogers
al. (2016), Ex-post privacy loss Ligett et al. (2017) and Rényi privacy filter/eelmaa & Zrnic (2021) track privacy loss as the query is applied over data. Our works builds upon the PTR framework in order give high privacy for less sensitive data. However, as we show in Sec our framework reformulates the PTR algorithm to make it tractable under our setup.
B PROOFS
Lemma B.1. For given f for dy la and dx t lg, Ais(x, < C(f.N(x, R)).
Proof. Local sensitivity (A for sample x in a radius R for a query f defined
f(((()),f(x))
ALs(X,
sup xxE.(xx))
dx (x(x'))
Local Lipschitz constant (L) for function f and neighborhood A is defined as:
[If(x') f(x" X'E' ||x'
ca.3(f.N)
sup
(x' x'' xx")
If L is defined around neighborhood, (x R) then the set over which local sensitivity is computed subset of the over which local Lipschitz constant is estimated. Intuitively, local Lipschitz condition is for all possible pair of samples in the neighborhood while local sensitivity is for all samples with respect to the given sample. Since both conditions require suprememum over the set, ALS(X, R) < C(f.N(x, R)).
Lemma B.2. Algorithm ó gives lower bound the query 7). That is, Φ(x, R) S 7(x,H) R).
14

---

Under review as a conference paper at ICLR 2023
Proof. The y query is defined as
>(x, R) min fix (x,xxxxxxxxx s.t. ALS(X(R) > ALs).
(10)
x'EX
The @ query is defined
x R)
arg (x - Ls)
(11)
2
R2R
For any given sample and privacy parameters (R, Lss) such that = o(xx , R), we know that Vx'' E (x)
,(x's)) c Nx,, 2s)
[(f.N(x', 8)) S [x, 2x)
Based eq 10 we know that (xx 2s)) I A and hence Vx' E (x(, 8). L(S.N 8)) v L.
Therefore, A R) S AEs and hence,
8 S 7x)
For the cases when there not any feasible solution, Φ returns which is exactly the same answer for y query. This completes the proof.
Lemma B.3. The query of-) has global sensitivity of I, i.e.
o(x', R)) S dx (x, x')
Proof. We will prove the above argument through contradiction. We will prove that for fixed radius R and any arbitrary point x E X, the neighborhood spanned by Φ(x, R) can not be proper superset for any neighborhood spanned by any other point ((x', RR). More formally, we will prove, Vx, x X, (xx, ø(x, x, R)) & [x',,, ø(x', R)) and N(x', (oxx,)) & Nxx, (xx R)). Once proven, this argument allows to specify the distance between and x' with respect to o(x, R) and (xx', R). Since the function (xx, R) returns the maximum possible value such that
C(J,N(x, ((x, S 2L.
Therefore, for any
C(f.N(x, 6(x, R) + ()) > ALs
(12)
For contradiction, we assume that 3x, x' E X s.t. Nix, o(xx R)) C NNxx, $(x,,
in > 0 s.t. (xx, 0 x R) + n) S CN((x, R))
(13)
L(N(x, @xx, R
+ n)) I Ais
(14)
This leads to a contradiction between eq 12 and eq 14 Therefore, Vx, x' E X,
o(x, R) S o(x', R)
+ dx (x,,')
Using symmetry argument, we can show that
dats( o(x' R)) < dx dx(xxx)
This completes the proof.
C
DP mechanisms typically add noise based on the global sensitivity of a query. However, for several queries over various data distributions, average local sensitivity might be much lower than the global sensitivity. However, local sensitivity is data dependent hence the amount of noise introduced by mechanism based on local sensitivity itself can reveal private information. Therefore. to add noise based on local sensitivity in privacy preserving manner, Dwork & Lei (2009) introduced PTR. Conceptually, the idea behind PTR is propose an arbitrary upper bound on the true value of local sensitivity. This upper bound should be obtained privately otherwise the choice of upper bound itself can reveal private information. To test whether the proposed bound is correct, the mechanism performs privacy-preserre due to privacy requirements. Therefore, it can have false positives and false negatives. If the test fails, the mechanism returns 1 (no-answer). Otherwise, standard DP mechanism (ex. Laplace) is applied to the query based on the proposed sensitivity (and not true local sensitivity). More formally, the algorithm proceeds in the following steps
testing of the upper bound. The test itself is randomized algorithm
15

---

Under review as a conference paper at ICLR 2023
1. A proposal upper bound of query is fed imput for data x. Let us call A
2. The algorithm finds the closest point x' such that ALs(x') ALs- Here As refers to local sensitivity for the query q-
3. Let 7 = (x x') and 7 = 7 + Lap(1/e)
4. i S ln(1/0)/e; return 1.
5. Else share data x + (aps(
Computational Cost: Depending on the query, this algorithm can incur significant computation cost. Especially in the Step 2, finding closest x' can be impractical if the data space is high dimensional. Finally, for queries such as neural networks evaluating local sensitivity itself not practical since it requires giving exact and correct solution to non-convex optimization problem. Therefore, framework relies on computing local lipschitz constant over a small neighborhood instead of local sensitvity over the complete data space.
Algorithm 1: Extended PTR algorithm for (e, ó, R)-semantic neighborhood privacy
Data: x E
Inputs: CE R 8 E R+ RER AL, E
Init: CERt;
xN For numerical stability, typically very small x/
Init: Rmin = R, R Raaz E IR+
while Riaax Rmin + do
Rmid- = (Rmin + R2aa)/2;
r [(,,N(x, R));
/* Compute local Lipschitz constant */
if ALs then Rmin Rmidi else Rmax Rmidi end
end
P Rmin:
+- 7+ Lap(1/c);
R < lm(1/8)/e then return 1; else return f(z) + end
D LIPSCHITZ CONSTANT ESTIMATION
We use the mixed integer programming based algorithm LipMip by Jordan & Dimakis 2020 for computing the local Lipschitz constant. Their technique allows exactly computing the local Lipschitz constant neural network with ReL.U non-linearities. Their key idea is to estimate the supremal norm of the jacobian of the neural network. Since ReI.U networks do not allow for differentiability. LipMip uses clark jacobian circumvent the issue and encode the optimization objective obtaining local Lipschitz constant over pre-defined neighborhood as a mixed integer programming problem. The neighborhood is specified as a hypercube with same dimension as points in the neighborhood. Their algorithm searches for feasible regions and minimizes the gap between lower and upper bound on the Lipschitz constant.
E EXPERIMENTAL DETAILS
Our experimental setup operates in three stages i) Embedder training, ii) Obfuscator training, and iii) Private inference. Our codebase available httplaaee/tttpss//rdeeeee.oooo
com/ drive/ here for reprodu- cability. We will release the code and all trained models publicly after the reviews. For all our experiments
Eolders/ 1DpHhh99u Mat.ssuu-pppp----- Ttop3TVmmYia wBteetKKKKKKSSS Ttw.TT/LLeeEElKK.aaaaaeereeeeear
PyTorchPaszkke et al. (2019) with Nvidia-GeForce GTX TITAN GPU. We use 3-VAE with 3 = 5 for the design of the embedder.
1. Embedder Training: We use embedding dimension for MNIST and FMNIST dataset. For the UTKFace dataset, we use embedding size as 10. We use Adam optimizer Kingma & Bal (2014)) with constant learning rate of 0.001. The VAE architecture for MNIST and
16

---

Under review as a conference paper at ICLR 2023
==2
==5
==T
30
LDP- Impelmage
0.1
0.1
0.1
0.3
0.99
MNIST
L.D-Embeddinn
0.1075
0.1319
0.1927
0.3107
0.9096
Adversarial
0.514
0.751
0.891
0.912
0.9291
JDP-Image
0.1
0.1
0.92
FMNIST
L.D-Fmmbedding
0.1012
0.1251
0.1708
0.2420
0.7798
Adversarial
0.371
0.554
0.678
0.722
0.781
LDP- Image
0.52
0.52
0.52
0.52
0.89
UTKFace
LDD-Embedding
0.5040
0,535
0.5757
0.6375
0.7246
Adversarial 0.65
0.69
0.718
0.724
0.73
Table Comparison between LDP and Adversarial Representation Learning: Using proposed framework we compare the utility of LDP and ARL across different values of the privacy parameter
A
A
Original Imuge
Original Image
Original Imagre
Figure 3: Neighborhood for different image datasets. The center image (in translucent red) is the reconstruction of the original image with nearby images sampled from the embedding space. Note that there are multiple dimensions and we have illustrated interpolation for only one here.
FMNIST dataset is composed of three fully connected layers with non-lineal activations and dropout.
2. Obfuscator Training:
For ARL,,
0.99, for noisy regularization,
a = 0.01 and for contrastive regularization, we use X = 1.0 with a margin of 25. All of these regularizations trained jointly using Adam optimizer(Kingman & Ba (0144)).
3. Private Inference: In the this stage use LipMip[Jordan & Dimakis (220)) which is built upon Gurobi Optimizer(Guung Guurobi Optimization, LLC (2022)) for solving the Mixed-Integer programming formulation of local lipschitz constant estimation. For the metries,
dx as infinity norm and dy as E -nomm.. For the privacy parameters, we use d = 0.05 and R 0.5 for MNIST, R 0.2 for FMNIST and R 0.1 for UTKFace. The choice of different R was based on visualizing samples from the training set and evaluating how far similar looking samples lie in the embedding space.
SSIM
MNIST
UTKe
0.1
0.2
0.4
0.6
0.8
1.0
0.1
0.2
0.4
0.6
0.8
1.0
0.558
0.427
0.287
0.231
0.201
0.179
0.481
0.443
0.426
0.425
0.422
0.421
0.648
0.553
0.414
0.328
0.275
0.229
0.475
0.442
0.439
0.428
5=5
0.702
0.655
0.580
0.499
0.434
0.380
0.519
0,5037
0.481
0.465
0.451
0.447
10
0.710
0.700
0.656
0.610
0.560
0.517
0.519
0.5169
0.507
0.494
0.485
0.476
Table 3: SSIM metric for reconstruction attack with varying R and
17

---

Under review as a conference paper at ICLR 2023
dims 6 dims
Burtine [s]
Neighhorfhodd radius
Input Dimensions
0.25
0.2
0.5
Runtime
0.15
0.10
0.00
Layers
Figure 4: Runtime evaluation of local lipschitz computation for different (a) neighborhood radius, (b) input dimensions, and (c) number of layers. While the runtime increases exponentially with dimensions, it plateaus with increase in neighborhood radius. Since the input dimensions same as emhedding dimensions making the algorithm favorable to our analysis.
MNIST
UTKFace
0.1
0.2
0.4
1.0
0.1
0.2
0.4
0.6
0.8
1=1
0,0775
0.0968
0.1145
0.1204
0.1232
0.1249
0.1304
0.1532
0.1
0.1731
0.1776
0.1782
2
0,0642
0.078
0.0983
0.1091
0.1153
0.1196
0.1126
0.1312
0.1543
0.1645
0.1699
0.1732
0.0565
0.0634
0.0749
040859
0.0959
0.1031
0.1017
0.1089
0.125
0.1 388
0.148
0.1546
10
0.0549
0.0569
0.0631
0.0697
0.0771
0.0837
0.1001
0.1027
0.1091
0.1182
0.1255
0.1321
Table 4: metric for reconstruction attack with varying and
P2
MNIST
UTKC
0.1
0.2
0.4
0.6
0.8
1.0
0.1
0.2
0.4
0.6
0.8
1.0
[=1
0.0471
0.0613
0.0762
0.0817
0.0847
0.0867
0.029
0.0385
0.0464
0.0476
0.0492
0.0498
c=2
0.0363
0.0478
0.0631
0.0716
0.0773
0.0814
0.0223
0.029
0.0387
0.0433
0.0454
0.0471
0.0354
0.0449
0.0537
0.0618
0.0672
0.0189
0.021
10
0.0291
0.0305
0.0352
0.0407
0.0467
0.0518
0.0184
0.0192
0.0212
0.0243
0.0271
0.0294
Table 5: l2 metric for reconstruction attack with varying R and
PSNR
MNIST
F'Cce
0.1
0.2
0.4
0.6
0.8
1.0
0.1
0.2
0.4
0.6
0.8
1.0
61.87
60.70
59.74
59.45
59.29
59.19
64.42
63.18
62.36
62.25
62.10
62.05
63.04
61.80
60.57
60.02
59.68
59.47
65.59
64.43
63.16
62.66
62.45
62.29
5=5
63.88
63.15
62.09
61.28
60.67
60.29
66.30
65.84
64.75
63.99
63.50
63.15
c
64.06
63.82
63.19
62.54
61.91
61.44
66.43
66.25
65,80
65.21
64.72
64.36
Table PSNR metric for reconstruction attack with varying R and
18


Reviews:
[{"review_id": "sZ3TZEvwlJ7", "reviewer": "Reviewer_82bi", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper utilizes a method called Adversarial Representation Learning (ARL) as a base. ARL \nlearns a privacy-preserving encoding of sensitive user data before it is shared, but lacks formal guarantees. The authors link the local Lipschitz constant of a neural network in ARL (obfuscation layer) with its local sensitivity. Local sensitivity was used by the Propose-Test-\nRelease (PTR) framework to provide privacy guarantee, which the authors modify to work with the Lipschitz constant.\nExperimentally on datasets verify the role of ARL in improving the privacy-utility tradeoff.", "summary_of_the_review": "Good work, though simple extension. The writing can be better. ", "strength_and_weaknesses": "Overall, I think this is a good paper with decent results, though the core of paper is a rather simple idea of relating Lipschitz constant to local sensitivity, other techniques are mostly borrowed from other papers.\nThere are terms used in Alg 1, which are defined after the algorithm, as as N. I feel the part after the algorithm can be stated first and then the algorithm.\nFig. 2 could have better legend for the colors for R.\nI do not understand what the epsilon values are on the very first heading in Table 1\nWhat is the encoder row?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "H4KvCvUsiTa", "reviewer": "Reviewer_KPwN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a novel framework for providing post-hoc privacy for queries on models trained using Adversarial Representation Learning (or representation learning in general). The authors draw inspiration on traditional differential privacy (DP) based approaches and are able to provide formal post-hoc privacy guarantees under certain very strong assumptions. ", "summary_of_the_review": "While the proposed approach is somewhat well motivated, I think there are many potential issues with the proposed framework that significantly limit the utility of the framework to some very specific situations (low dimensional embeddings where the embedding space is sufficiently smooth). To their credit, the authors are quite upfront about the limitations of their framework but they overstate the utility in my opinion. ", "strength_and_weaknesses": "Strengths: \n1) The paper presents a novel theoretically motivated approach to provide a privacy guarantee for queries on pre-trained representation learning models. \n2) The proposed framework is very similar to DP based approaches and has some properties similar to DP. \n3) The mathematical claims of the paper seem correct (based on my reading). \n\nWeakness: \n1) Definition of privacy: In Definition 1, semantic neighborhood privacy is also a function of $\\theta$. So, it should be included in the definition. This unfortunately significantly weakens this notion of privacy. \n2) Identifying appropriate value of R: The authors state \"To assess the level of indistinguishability, we look at Fig 3 where\nwe project the original images into embedding space and sample points from the boundary of\nneighborhoods of different R. \". This simply isn't a reasonable approach to select a privacy parameter especially since it relies on humans perception of similarity. \n3) The authors don't really propose a practical way to select $\\Delta_{LS}^p$. \n4) The authors state that the runtime exponentially increases as a function of embedding dimension, which is problematic. \n5) Related to weakness 4, the authors evaluate their runtimes on relatively small embedding dimensions. However, there are many use cases when the embedding dimensions are much higher (>1000). What is the feasibility of this approach for such embedding dimensions? I also have significant concerns about how meaningful the privacy guarantees are in the case of high dimensional embeddings. \n6) I would be interested in a privacy/utility comparison with DP based model training. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5DIjQylcqJ", "reviewer": "Reviewer_yTGh", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a formal way to capture obfuscation of an image using adversarial representation. The paper does so by using a metric-based differential privacy notion. Since the metric is difficult to compute, the paper proposes a way to estimate Lipschitz constant using an estimation technique from DP. The paper then evaluates several obfuscation techniques on their utility.", "summary_of_the_review": "Given that there were unsuccessful attempts before on adhoc techniques to obtain image privacy by changing/randomizing the enbedding, this paper makes an attempt to provide formal guarantees to capture it. However, the method may not protect against all attacks and seems to rely on the knowledge of the classifier defeating the purpose of sending data for classification.", "strength_and_weaknesses": "Strength:\n- formalising privacy guarantees of obfuscators is an important research problem to avoid erroneous methods\n- metric DP and PTR framework build on existing work\n\nWeaknesses:\n- adversarial model is not given\n- the method relies on knowledge of the classifier which seems at odds with the usefulness of the approach (i.e., why call the classifier)\n- metric-DP may not capture all privacy vulnerabilities (i.e., the privacy guarantee is as good as the metric that is used)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject