Minimax Risks and Optimal Procedures for Estimation under Functional Local Differential Privacy
Authors: Bonwoo Lee
Jeongyoun Ahn
Cheolwoo Park
Venue: NeurIPS 2023 poster (2023)
Keywords: Data privacy
Functional local differential privacy
Gaussian mechanism
Minimax risks
Statistical utility
TL;DR: We investigate how functional local differential privacy preserves statistical utility by analyzing the minimax risk for univariate mean estimation and nonparametric density estimation.

Abstract: As concerns about data privacy continue to grow, differential privacy (DP) has emerged as a fundamental concept that aims to guarantee privacy by ensuring individuals' indistinguishability in data analysis. Local differential privacy (LDP) is a rigorous type of DP that requires individual data to be privatized before being sent to the collector, thus removing the need for a trusted third party to collect data. Among the numerous (L)DP-based approaches, functional DP has gained considerable attention in the DP community because it connects DP to statistical decision-making by formulating it as a hypothesis-testing problem and also exhibits Gaussian-related properties. However, the utility of privatized data is generally lower than that of non-private data, prompting research into optimal mechanisms that maximize the statistical utility for given privacy constraints. In this study, we investigate how functional LDP preserves the statistical utility by analyzing minimax risks of univariate mean estimation as well as nonparametric density estimation. We leverage the contraction property of functional LDP mechanisms and classical information-theoretical bounds to derive private minimax lower bounds. Our theoretical study reveals that it is possible to establish an interpretable, continuous balance between the statistical utility and privacy level, which has not been achieved under the $\epsilon$-LDP framework. Furthermore, we suggest minimax optimal mechanisms based on Gaussian LDP (a type of functional LDP) that achieve the minimax upper bounds and show via a numerical study that they are superior to the counterparts derived under $\epsilon$-LDP. The theoretical and empirical findings of this work suggest that Gaussian LDP should be considered a reliable standard for LDP.

Minimax Risks and Optimal Procedures for Estimation under Functional Local Differential Privacy
Bonwoo Lee
Jeongyoun Ahn
Cheolwoo Park
Korea Advanced Institute of Science Technology
Daejeon, 34141 South Korea
righthimOkaist.aar ac.kr, jyahnokaist.
jayaaaaaaaaaa..........aaaaaaaa ac..ssttt............ ac.kr, kr, parkcw20210kaist.ccm
Abstract
As concerns about data privacy continue to grow, differential privacy (DP) has emerged as a fundamental concept that aims to guarantee privacy by ensuring individuals' indistinguishabiiiyy in data analysis. Local differential privacy (LDP) is a rigorous type of DP that requires individual data to be privatized before being sent the collector, thus removing the need for trusted third party collect data. Among the numerous (L)DP-based approaches, functional DP has gained considerable attention in the DP community because it connects DP statistical decision-making by formulating it as hypothesis-testing problem and also exhibits Gaussian-related properties. However, the utility of privatized data is generally lower than that of non-private data, prompting research into optimal mechanisms that maximize the statistical utility for given privacy constraints. In this study, we investigate how functional LDP preserves the statistical utility by analyzing minimax risks of univariate mean estimation as well nonparametric density esti- mation. We leverage the contraction property of functional LDP mechanisms and classical
bounds to derive private minimax lower bounds. Our theoretical study reveals that it is possible to establish an interpretable, contin- uous balance between the statistical utility and privacy level, which has not been achieved under the e-LDP framework. Furthermore, we suggest minimax optimal mechanisms based on Gaussian LDP (a type of functional LDP) that achieve the minimax upper bounds and show via numerical study that they are superior to the counterparts derived under e-LDP. The theoretical and empirical findings of this work suggest that Gaussian LDP should be considered a reliable standard for LDP.
1 Introduction
has been widely accepted that amonymization is insufficient in protecting privacy (Sweeney, 2000, 2002; Dinur and Nissim, 2003). The concerns about data privacy have grown significantly, particularly with the advancement of computer science technology and the rise in data generated by individuals and tech companies. Such concerns shared by politics and industry, leading the adoption of France's "Loi pour une République numérique (Laa for the Digital Republic)" in October 2016 (Algan al., 2016), EU's General Data Protection Regulation May 2018. and the California Consumer Privacy Act (Wang et al., 2022). all of which regulate data protection, collection, and processing. Also, data privacy techniques have been implemented industries such as Google (Erlingsson et al., 2014: Fanti et al., 2016). Apple (Thakurta et al., 2017; Tang et al., 2017), Microsoft (Ding et al., 2017), and SAP (Kessler al., 2019).
"Corresponding authors
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Differential privacy (DP), suggested by Dwork et al. (2006b), has become fundamental foundation of the modemn privacy concept. Its core idea is that privacy can be protected not by how well the sensitive information is hidden but rather by how individuals are indistinguishable in the privatized data. Dwork et al. (2006b) first introduced the notion of c-DP for a randomized mechanism that yields a likelihood ratio between its outputs from 'neighboring' data that is bounded by privacy budget e. Despite its intuitive appeal, e-DP has been found to lack generality in explaining some common privacy mechanisms including the Gaussian mechanism (Mironov, 2017; Dong et al., 2022). A generalized version of e-DP, (e, 6D-DP, is introduced in Definition 1.1. Let X' be the sample space and M x - P (Z) be a randomized mechanism, where P(Z) is family of distributions over 2. Let S ~ S" denote that data sets S and 5' are neighbors, differing only by one individual. The following definition states that the output distribution of M does not heavily depend on the presence of a specific individual. Note that (c, D)-DP reduces to e-DP.
Definition 1.1 ((c, 51,6)--PP Dwork et al. (2006a)). A mechanism M is 6c,5) if the following holds:
sup sup P (M((S) E A) - c'P (M(()) E A) 6.
S,8' AC2
Another type of DP, local differential privacy (Duchi et al., 2013, L.P), provides strong privacy guarantees by privatizing raw data before releasing it data collector. It is commonly used for private statistical inference since it gives the adversary access to privatized data that is the same size as the original data. Note that unlike in Definition 1.1, the inputs of LDP mechanisms are not the whole data set S but each individual observation x; E S.
As expected, the accuracy of statistical analysis performed on privatized data is often worse than that of non-private data. This has prompted researchers to seek a balance between privacy and utility as well as to find the optimal mechanism given privacy constraints. The efforts to balance noise contamination and utility date back to Carroll and Hall (1988), which predated the emergence of DP. Later, Duchi et al. (2013) proposed framework for quantifying the trade-off between privacy and statistical utility using c-LDP and minimax risk analysis. With the minimax framework, one can study the minimum loss that can be attained in the worst-case scenario for statistical utility, given specific privacy constraint. Since then, numerous researchers have explored minimax risks for various inference problems under e-LDP (Li et al., 2022: Chhor and Sentenae, 2023; Rohde and Steinberger, 2020; Butucea et al., 2020).
However, despite the inherent continuity in the definitions of c-LDP and (c, 6)LLP, some studies on LDP mechanisms have revealed an inexplicable discrepancy in the statistical utility achieved by the two techniques (Asoodeh et al., 2021). One possible explanation for this phenomenon is the inefficiency of the composition rule used in (c, 6DD,, which has been found to perform poorly in tracking privacy leakage resulting from the compositions of multiple mechanisms or subsampling, as pointed out by some studies including Dong et al. (2022); Mironov (2017). Since data are frequently reused multiple times in most data analysis scenarios, the privacy level must be calculated by taking the composition of multiple mechanisms into account. An accurate assessment of privacy under such compositions is critical, since underestimating privacy would force mechanism to sacrifice utility to ensure the desired privacy level.
This work explores the trade-off between statistical utility and local privacy under the framework of functional differential privacy (Dong et al., 2022, FDP), which is known to provide more precise privacy control. The core idea of FDP connects the fundamental DP concept, which involves making two outputs based on different inputs indistinguishable, to the concept of statistical decision-making. Since an adversary's 's goal is to identify whether given privatized Z is from S or S' when S ~ S', we consider the following hypothesis testing problem for a given output of mechanism M:
Ho : Z M(S)
vs. H1 : Z ~ MS').
(1)
The difficulty of this hypothesis testing problem is directly related to the privacy level of the given mechanism. A mechanism is said to satisfy f-FD if the above testing problem has a "frade-off"
function f(a), which is the minimum Type II error for a given Type I error greater than E [o, 1]. FDP, particularly in the context of Gaussian differential privacy (GDP) (see Section 2), has been found to provide superior privacy control compared to (c, DDD,, with better interpretation.
Another advantage of the FDP framework is its superiority in composition rules, which regards accurately measuring the privacy level when multiple mechanisms are sequentially applied. Many

---

types of DP, including (r,)),LL) have been criticized for their inefficient composition rules. They tend to overestimate privacy leakage, which, in turn, leads to excessive perturbation of estimations. This is demonstrated in Section 4, in which c-LDP is empirically shown to be inefficient in controlling the privacy of a high-dimensional problem. On the other hand, FDP possesses an effective composition rule that strikes the right balance between privacy protection and estimation accuracy.
1.1 Related Works
Since DP was introduced, the trade-off between privacy and statistical utility has been studied in global DP settings as well as local DP settings. Kamath et al. (2022) and Kamath and Ullman (2020) investigated the trade-off under e-DP by studying sample complexity of covariance matrix estimation of Gaussian distribution and univariate mean estimation, respectively. Cai et al. (2021) es- tablished minimax optimality under (e, 6 for high-dimensional mean estimation of sub-Gaussian distributions.
In the local DP setting, analyzing minimax risks under e-LDP for various estimation problems has been a main focus. Duchi et al. (2018) provided bounds minimax optimal privacy mechanisms for some canonical estimation problems including mean and density estimation and suggested optimal estimators under e-LDP. Other estimation problems that have been investigated under e-LDP include the estimation of functionals of probability distribution (Rohde and Steinberger, 2020), and discrete distribution estimation (Chhor and Sentenac, 2023). Private minimax risk of nonparametric density estimation has been addressed by Butucea et al. (2020) who observed elbow effect in L risk over Besov spaces and by Li et al. (2022) who considered a data contamination scenario. Some efforts have also been made under (e, 8)-LD. Asoodeh et al. (2021) studied minimax risks for mean estimation, while Kroll (2021) considered nonparametric density estimation at fixed points.
Among the existing works, Duchi et al. (2018) and Asoodeh et al. (2021) present work than others, as they also studied the mean estimation and/or nonparametric density estimation. We show that the minimax optimal rates for f-FLDP, local version of f-FDP, equivalent to those for e-LDP, if f satisfies some condition (see Lemma 1). We argue that our result can also be useful for understanding (e,D)-D since f-FLDP includes (e, d-LLD as special case.
relevant to the
1.2 Our Contributions
We derive the minimax risk bounds under the framework of FLDP as well as Gaussian LDP (GLDP) for two classic statistical problems: univariate mean estimation (Section 3.1) and nonparametric density estimation (Section 3.2). We investigate the private minimax risks using Le Cam's 's (Theorem I) and Assouad's bounds (Theorem 3), respectively. To the best of our knowledge, our work is the first to investigate the minimax risk bounds under the FLDP framework.
Our theoretical investigation yields two important results: First, we show that our bounds achieve the same rates under some conditions as those under e-LDP, thereby extending the contraction inequality established by Duchi et al. (2018) under e-LDP FLDP (Theorem 2). Also, as a special case, we show that the established lower bound becomes tight under GLDP. Second, we demonstrate that f-FLDP provides a continuous trade-off between privacy and statistical utility, unlike (c. 8))LDP (Corollaries 1 and 3). In the view of (c, 8).D), one can see that c-LDP and non-private settings are continuously related by a quantity respect to the minimax rate. So far, any slightest privacy measure seems to increase the minimax rate with the increment rate not related to the privacy level. For example, the minimax rate of 25
However, the existing results do not reflect such continuity with
28 nonparametric density estimation worsens from 2#+1 to 2f+2 under c-LDP, where 3 denotes the degree of smoothness. But the change of rate is irrelevant to even though c-LDP becomes non-private if we set co.
We also present optimal mechanisms that attain the minimax upper bounds (Corollaries and 4), and evaluate their utilities compared to optimal mechanisms derived under c-LDP, Our experiments show that the proposed minimax optimal estimators under GLDP achieve better utility for the equivalent level of privacy constraints (Section 4).
2 Backgrounds
We introduce some notations and review key concepts in differential privacy in this section. Let M X" - PZZ) be multivariate randomized mechanism equivalently, collection of
3

---

randomized mechanisms M {M such that Z (z1...., == ( Fn) where 2, (,, for I,...,, n. Here, .M denotes locally private mechanism as it pri- vatizes data set D E X", producing perturbed data with the same size as the original data. Furthermore, M called a sequential mechanism 2; depends only on 2; and 21,..., 1t-1, 80 (1 21,...,, 4-1)).
2.1 Functional Local Differential Privacy
The hypothesis testing aspect of DP expressed in (1) was first discussed by Wasserman and Zhou (2010). Recently Dong al. (2022) gave formal treatment by formulating the difficulty of the lesting as follows, Let ø be the rejection rule and a be the level of the test. Then we define the trade-off function the minimum type II error for given a.
Definition 2.1 (Trade-off function, Dong et al. (2022)), For two distributions P.Q P(Z) and E [0, 1], the trade-off function T(P, Q) [0, 1]
- [0, 1] between P and Q is defined as
T(P, ())) inf {1 11-J2 - d(2)dQ(2)
- [0, d(z)dP(=) (()))P())
It clear that the larger the trade-off function, the smaller the power, and consequently the more private the mechanism. A randomized mechanism is said to satisfy f-FDP if the corresponding trade-off function is at least / for all E [0, 1).
Definition 2.2 (Functional differential privacy, FDP), Dong al. (2022)). Let [0. a trade-off function for some distributions and Q. A given mechanism M is f-FDP if
[0, 1] be
M(M 2 f(a)
for every S S' X and [0, 1].
The following proposition shows that (c defined (1.1) special case of o
f-FDP.
Proposition 1 (Dong al. (2022)). convex conjugate of is defined as (v) supse(o.1] yæ fxx). Then a mechanism M satisfies an f-FDP iff is (e,))(e")))DD for every 0.
According Proposition 1, all information regarding the privacy of the mechanism from the per- spective of (c, 8)-DP is contained in FDP. also indicates that the privacy characterization of a mechanism may require more than just two numbers and 6.
A useful subclass of FDP is the Gaussian differential privacy (GDP), which has the trade-off function G = (O, 1), (n,, 1))- That is, the hypothesis testing problem in (1) compares two normal distributions with respective means and μ with unit variance. It is known that Gz( F(
x) μ1) where F is the cumulative distribution function of the standard normal distribution.
Definition 2.3 (Gaussian differential privacy, GDP). A mechanism M is GDGP if it G,,
In addition to its intuitive interpretation, GDGDP also possesses appealing asymptotic properties regarding compositions of different DP mechanisms. has been shown by Dong et (2022) that the trade-off function of composition of mechanisms converges to G2 under some mild conditions. Due these desirable features, is suggested be used as a standard for the comparison of different DP methods.
In this work, we focus on the utility of estimation under local μ-GDP, i.e., frGLDP. For all DP concepts introduced so far, their corresponding local versions are naturally defined by a locally private sequential mechanism M = {M,), i = 1.... that privatizes the ith observation, respectively, For example, f-LLDP and y-GLDP are characterized by the following:
T(M((x), M(())))) 2 f(a) (or Ga(a))
for every x, x E X and 1,2, ... Some exemplary trade-off functions of j-GLDP as well as those e-LDP are displayed in Fig. la.
not to be confused with the trade-off between privacy and statistical utility.

---

2.2 Private Minimax Risk
Consider an estimation problem in private setting. Suppose n ii.d. observations .i...., Xn E X are drawn from a distribution P in some family of distributions P c P(Z). The data are privatized into (Zi..... Zn) = M X,)) where M is an f-FLDP mechanism. Let 0 = (P)) E θ be parameter of interest where θ is the parameter space and 0 : x + θ be estimator. For metric @ - Rz0 and an increasing function & Rz - + R20, use p as the loss function, we define the private minimax risk:
Definition 2.4 (Private minimax risk).
R2 (0(P), 4 o p.M = inf inf sup Ep to ( MEM, PEP
Here, My is family of f-FLDP mechanism defined over X As long as privacy is guaranteed at a certain level (i.e., given f), one wishes to find an optimal privatizing mechanism M for given estimation problem (i.e., 8) that yields uniformly optimal loss over every distribution in P. One can also use the minimax risk not only to find the optimal achievable estimation risk but to judge the efficiency of the estimator under the given privacy level f-FLDP.
3 Minimax Risk Analysis Under FLDP
Minimax risks of classical, non-private estimation problems have been addressed by numerous approaches including Le Cam, Fano, and Assouad methods, among others (Tsybakov, 2009). In this section, we take Le Cam's 's and Assouad's s approaches and apply them to mean and nonparametric density estimation, respectively, under f-FLDP. All proofs are presented in the supplementary material.
3.1 Le Cam's Bound on Mean Estimation
Le Cam's 's method involves reducing an estimation problem to two-point hypothesis testing problem, in which the minimax risk is bounded by calculating the worst-case risk for only two distributions, Pi and P2, selected from P, as defined Section 2.2.
We first state the private Le Cam's lower bound under f-FLDP in the theorem below. The following quantity represents the contraction factor of the effective sample size due to the privatization:
10
CfNN
2kx (1
(1 #:)= 15)))),
where 0 S S 1 and (t) is the convex conjugate of f, as defined in Proposition 1.
Theorem 1 (Private Le Cam's 's bound). For given < x S and trade- off function f. if So 15-18 (t)dt is finite and p(0(Pi), 0(22)) 2 2n 0 for two distributions P1, P2 P, then
+ (m)
|P] - Polltt
R. Dop,
M2)
1
nCf.s (1 P: P221TTV
where Il-Ilzy denotes total variation.
The minimax lower bound on the right-hand side can serve as an indicator of the trade-off between privacy and utility. Note that Cf.x < Cg.x if f(t) 2 g(t) for all t E [0, 1], which implies higher privacy would yield greater contraction of the effective sample size. That is, the minimax lower bound on the right-hand side would become lower under a loosened privacy constraint, which coincides with the intuition that less privacy would enhance the utility.
Next, we use Le Cam's method to obtain a lower bound of minimax risk for univariate mean estimation with bounded moments under the squared loss. For k > 1, define family of distributions
with bounded kth moment Ps = {P E P (R) EP [X] S 1, E. [| s 1}. The parameter
of interest is O(P) Ep [X] with loss function + a P where p(0,, 02) 10, 0zl and ((1) = 12. Applying Theorem 1, obtain the following result.
5

---

Corollary 1 (Univariate mean estimation). For given 0 S R S 1 and trade-off function f, if So txt ōg (t) dt finite, then
Rr (O(Pk)>HP,, 2 co (no
26 1 14
for n > ej where co only depends k and is and eı depends on Cf.x-
Note that the minimax risk for mean estimation is known to be O (n min(1.2- #) in non-private setting and O ((ne²)
under e-LDP (Duchi et al., 2018). Corollary 1 implies that the minimax lower bound continuously reaches the two scenarios. Specifically, the minimax risk bound of A: = 0 corresponds to that of the non-private setting, and the minimax risk bound of 1 corresponds to that the c-LDP case. Moreover, the fact that for any trade-off function f. there exists f. such that S f-FLDP is equivalent with e-LDP implies that the minimax rate of mean estimation under f-FLDP is O
when Cf is finite. In the following lemma, we further identify which trade-off function f would yield the private minimax risk bound of f-FLDP equivalent to that of e-LDP.
Lemma 1. If a given trade-off function f(z) 2 ca for some > O and E (0.5, 1) on [0, 1), or 85(x) S cgx for x >> Do and some C3, c2, to > O, then So 8y (1) dl is finite.
1.00
1.00
0.4-DPP
Lemma holds Lemma
6.4.DDP
does not hold
1-GLDP
Non-private
0.75
0.75-
0.50
0.50
0.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0t
a
(a) Trade-off functions
(b) Lemma
Figure 1: (a) Trade-off functions e-LDP with e = 0.4 (red), 6.4 (green), 4-GLDP with μ = (blue) and non-private setting (cyan). (b) Example of trade-off functions (not) satisfying Lemma 1.
Under the condition of Lemma 1, the minimax risk of univariate mean estimation under f-FLDP is O(n (n====) by Corollary 1, which is the same rate for c-LDP. Here, note that the assumption of Lemma 1 is quite general. Fig. 1b shows some examples of trade-off functions satisfying Lemma I. can be seen that Lemma I requires the slope
of the trade-off function should not be too steep. Nonetheless, note that there exists a trade-off function requiring k < 1 in order to make Cf.x finite. For example, (xx = 1 - x f+ is a trade-off function with 8y(1) = x [TT)) for t> I++ mechanisms that Corollary 1 cannot guarantee the minimax rate equivalent with the optimal rate under e-LDP. In other words, they may enjoy better minimax rates. In the supplementary material, it shown that G,,, satisfies Lemma for any μ >>
K Therefore, f 8 (t))) does not converge, and neither does Cf.x. Thus, there exist some
Combining it with Corollary 1, we can bound the minimax risk of univariate mean estimation under 4-GLDP. Denote My for family of μ-GLDP mechanisms.
Corollary The minimax risk of univariate mean estimation under μ-GLDP mechanism bounded as follows:
Co (ne2u²) (1- S RR, (B S (c
for n >> C2 where Co C1 are constants depending only on and e2 is constant depending only on and k.

---

We present the following μ-GLDP algorithm that can be shown to be minimax optimal, as it achieves the rate of On - See the supplementary material for proof and empirical comparison of other LDP mechanisms including the minimax optimal c-LDP mechanism Duchi et al. (2018).
1. T n (1 12² |
2. M..,)) m -T, ( T}} + 6, where ef N (0, 47 10=)))
3. 0
Σm_ (X))).
The fact that y-GLDP and e-LDP have the same minimax rate might be unexpected to some, especially considering that the former is a more relaxed concept than the latter. In the following lemma, we present an interesting inequality that can shed light on their connection.
Lemma 2. Let M X + P(Z) be locally private mechanism taking only one data for its input. For P1, P2 E P()), denote my for density of M (P.))
1,2. If M is J-FLDP, then for 2 2,
mi Z
P m222
I 88 1).
(2)
Lemma 2 implies that, for sufficiently small 6e - 1), an /-FLDP mechanism behaves like e-LDP with high probability (1- -5 1)). Moreover, this lemma provides probabilistic interpretation for (e, 6)-LDP the probability that the likelihood ratio between output distributions exceeds ef + bounded by 8. In the DP literature (Mironov, 2017; Meiser, 2018), (c, 6'-DP is often informally explained as "an e-DP with probability 1 - 8," which can cause confusion. In this regard, here we provide an accurate statement specifying the respective roles of and 8.
In addition, the 4-GLDP mechanism possesses a similar contraction ability to c-LDP. The term contraction of mechanism is generally used describe the reduction of distance measures be- tween distributions that is altered by a mechanism. In Duchi et al. (2018). 8), it was shown that the Kullback-Leible (K-L) divergence between privatized distributions un- der e-LDP, is bounded by 2(e - 1) Pall.y- We establish a similar bound under f-FLDP. Following the notations in Lemma 2, the following theorem describes the contraction of F-FLDP mechanism in terms of K-L divergence.
DAI (M)
Theorem 2. For given
and trade-off function f. if J000 tx- 15-18,(t)ddt is finite, then
|| Pallet 1+x
D (m1 (millm²)) := Diamm (m2) + (m(lm)lmma) S Cf.x (1 PP Pa
holds for any f-FLDP mechanism M X - P (Z) and distributions Pi and P2 over X.
In the case of μ-GLDP, the bound comes down to O (I) Palirv) since Je 5 is finite for 6 = 1. Because f-FLDP includes e-LDP, our result is more general than Duchi al. (2018) and further gives an insight into why e-LDP and p-GL.DP have indistinguishable privatizing power. Our analysis also improves the bound found by Asoodeh al. (2021), which is expressed as constant multiple of DRi (Pi)IP?) thus could be unbounded for point distributions. Our result bounds the divergence by total variation between P1 and P2. which is finite for any two arbitrary distributions. See the supplementary material for an elaborated illustration.
3.2 Assouad's Bound for Nomparametric Density Estimation
This section aims to derive the minimax risks of private nonparametric density estimation under f-FLDP and j-GLDD. While Le Cam's method is effective for many problems, it may not be suitable for high-dimensional structured problems. In such cases, Assouad's method offers a solution by reformulating the estimation problem multiple-binary hypothesis testing problem. Given the parameter space O, there exists map V O - +1] and a family of distributions (P. (-1, for d E N such that
2 2m ((p(0,((P.))
Σ ([V( t0²
j=1
7

---

for every v E {-1,+11" We say (Pelve(-1+t1)) induces 3n-HHmming separation under loss o p. Assouad's method establishes a lower bound of minimax risk by assuming not the worst case but randomly selected case in { (E)) We present the Assouad's bound under f-FLDP mechanisms.
Theorem 3 (Private Assouad's bound). For given 0 < S and trade-off function f. if So 15 oy (t) dt is finite and set of distributions ( -1++1 induces 27-Hamming separation under p. then
PP+ P-sllTVV 1+t
R. (op M,) de)
P+s - P-pllrv)
j=1
where P.j Dioy Po.
We use Theorem 3 to obtain the lower bound of minimax risk of private nonparametric density estimation. The true density is assumed to be in the elliptical Sobolev space, as defined below: Definition 3.1 (Elliptical Sobolev space). For given orthonormal basis {Ø of (20, 1)),
smoothness parameter 3 > 2. and radius O, the elliptical Sobolev space is the following set:
Følri h L² 1
2000
Σ
2 S
If the trigonometric basis, then Fs represents of distributions with the bounded norm of (-derivatives with coinciding derivatives of degree< 3 at endpoints of [0, (Tsybakov, 2009).
Applying Theorem 3, we can obtain the following lower bound.
Corollary 3 (Nonparametric density estimation). For given S A S and a trade-of off function f. if Jo gx 15 (t)dt is finite, then
Rn (#(Fa(r)), 1-112, M,) c to (गp
for n > 02 where C1, 02 > are constant depends on
It is known that the minimax risk in the non-private setting is O (n_asee 28-1 (Tsybakov, 2009) and
O (mee)= कगïz under e-LDP (Duchi et al., 2018). Thus according to Corollary 3, the minimax rate of f-FLDP with x = 1 is the same as that c-LDP. As in Section 3.1, we can obtain the bounds of minimax risk of nonparametric density estimation under μ-GLDP, using Lemma 1.
Corollary 4. The minimux risk of nonparametric density estimation under μ-GLDP is bounded as follows:
coreti (netk")
20+2
23 RR (0FF5))))) S cireti (np²) 2842
for n >> Cg where co, C1 are constants depending only on and 02 is constant depending only on and B.
Note that the minimax rate in Corollary 4 is essentially the same that of c-LDP. However, under μ-GLDP, one can find the optimal mechanism in a more straightforward way. This is in contrast to the discussion in Duchi et al. (2018) that the Laplacian mechanism, the canonical mechanism under e- e-LDP, cannot achieve the optimal minimax rate. They instead proposed a complicated mechanism to achieve optimality. Our minimax optimal mechanism and density estimator are presented below:
Suppose that n i.i.d. data X1, X2....,
....,.,, X,, drawn from E Fg [r] are available.
1. Set d = [0.55m 2842 where [x] is the largest integer not exceeding (a(X)))
2. M,(X.) = (6) (X,) ,.()).))(.)))))) where e ~ N(0, Iaxa).
as h := [M 4. Repeat and for i 1, ,n..
3. Define a function h; [0, 1]
5. h E hi is the obtained estimator.

---

Empirical Comparison of Minimax Optimal Mechanisms
In this section, we compare the optimal mechanisms for nonparametric density estimation under e-LDP, μ-GLDP, and non-private mechanisms. The simulation on univariate mean estimation is provided in the supplementary material. Our proposed mechanism in Section 3.2 under j-GLDP compared with the mechanism in Duchi al. (2018) and the non-private mechanism, which is obtained by using d = [(rr2) म with = in our j-GLDP algorithm.
The true underlying density is given the density of Beta(5, 5) distribution. We set (0.4, 0.8, 1.6, 3.2, 6.4] for c-LDP and E {0.5, for μ-GLDP. We vary the sample size from 100 2000. Estimation errors calculated by integrated mean squared errors. We repeat the experiment 100 times for each mechanism.
10
True 1-GLDP Non-orivate 0,4-LDP
10
mean squared eiror
density
2-
10*
10"
10
0.4.DDP
18 GL3P
6.4 LDP
0.5 GLOP
Non pmitte
10*
0.00
0.25
0.50
0.75
1.00
100
200
1000
2000
sample size
(a) Density estimates
(b) Mean squared errors
Figure 2: (a) 95% confidence intervals calculated from private density estimates over 100 repetitions for three LDP and non-private mechanisms. (b) The mean squared errors with one-standard errors of density estimates for various LDP mechanisms and sample sizes.
The trade-off functions in Fig. la show that 6.4-LDP is very close to the non-private setting and 1-GLDP is between 0.4-LDP and 6.4-LDP almost everywhere in terms of privacy levels. However; Fig. 2a, displaying the 95% point-wise confidence intervals obtained from estimated densities by different methods, shows that estimates under 1-GLDP are more in agreement with the true density than 6.4-LDP. The performance under 0.4-LDP is much worse than the others because it is the most private mechanism. The superiority of I-GLDP can also be seen in terms of mean squared errors. In Fig. 2b, 1-GLDP performs better than all other e-LDPs.
The utility of a private mechanism in this density estimation essentially depends on how well approximates the estimates of Fourier coefficients that would be obtained from the original data, This task requires an efficient mechanism to estimate multi cilli--dimensonnll coefficient vector for each observation. The optimal mechanism for this task under e-LDP transforms vector of non- non-private Fourier coefficient estimates into binomial vector, which limits the support in order to reduce variance and achieve privacy. However, due to the inherent variance introduced by discretization, the
mean squared error is bounded by constant multiple of of the c-LDP density estimation mechanism Duchi al. (2018) can derived follows:
[=++1
Explicitly, the optimal error bound
c +
Re - (3 1) (3+1)
PFT
VeTe
-
where R, is the expected eтrоr obtained from the e-LDP density estimation mechanism in Duchi et al. (2018). Hence, even with lenient privacy constraint (i.e., a large e), the estimation error may not decrease significantly. In contrast, our y-GLDP optimal mechanism generates an estimator by adding noise with decreasing variance as y tends to infinity. Again, the explicit optimal error bound given
We use
3 and 408.80 8979 for the proposed mechanism in Section 3.2

---

as
28 R (B+ (0.5,Bn²²)
25+2 -524+
where R₂ is the expected error obtained from our J-GLDP density estimation mechanism. The 28
comparison of the coefficients of 2012, which can be interpreted the cost of privacy, gives the asymptotic error ratio:
RS R.
πEe 2 u
2042
which exceeds when μ = 1. Therefore, the estimation under c-LDP is likely to produce higher enrors than the estimation under 1-GLDP for any This is also evidenced by the result in Fig. 2a. The fact that private estimation error under c-LDP does not approach non-private estimation error implies that e-LDP adds more noise than necessary high-dimensional data compared to μ-GLDP. This highlights the limitation of e-LDP and the advantage of μ-GLDP in achieving privacy for multi-dimensional data, which can be practically beneficial for addressing other private estimation problems.
5 Conclusion
The present work on f-FLDP establishes the private Le Cam and Assouad bounds reflecting the continuous nature of privacy constraints. As the trade-off function f becomes more (less) private, the supremum value satisfying the conditions of Corollaries and 3 increases (decreases), leading to the e-LDP (non-private respectively) minimax rate in terms of n. This is in contrast to the somewhat counter-intuitive minimax lower bounds derived under e-I.P,, whose utility never achieves that of non-private estimation even as approaches infinity. Our simulation study in Section 4 shows that ju- GLDP can offer similar or better privacy level than c-LDP, while achieving higher accuracy in private estimation. This suggests that j-GLDP may be a better option for achieving both privacy and accurate estimation. The results on the contraction inequality reported in Theorem 2 and in the supplementary material provide additional support for this claim based on the privatizing characteristics of the mechanisms. In summary, this work shows that p-GLDP is theoretically comparable in terms of both utility and privatizing ability while enjoying the better practical performance. This supports the suggestion made by Dong et al. (2022) that we use G(L as a reliable standard for (L) both theoretically and empirically.
Possible limitations of this work are as follows: Although we establish lower bounds that connect privacy and utility in continuous manner through к E [0, 1], the suggested optimal mechanisms only achieve the minimax rates for 6 = 1. It will be desirable to identify private mechanisms and estimators that can achieve minimax rates between the non-private and e-LDP minimax rates, if such mechanisms exist. Additionally, the condition in Theorems and does not hold for all possible trade-off functions. Also, the bounds in Corollaries I and 3 require f 1 8 (f)dt to be finite, which restricts the potential application of the theory, even though most commonly used privatization mechanisms, such the Gaussian and Laplace mechanisms, satisfy this condition. Nevertheless, these bounds only coincide with the true minimax rates for only limited categories of privacy. Hence, plan explore whether there exists an optimal mechanism that enjoys better minimax rate for mean and density estimation. Additionally, our theoretical minimax bound for estimations under u-GLDP is tight in terms of the sample size n, but it notably lacks tightness with respect to the privacy parameter μ.. Our lower bound converges to a finite value when goes to 0 incompatible with the upper bound. Hence, further efforts are required to establish a rigorous minimax rate in terms of privacy constraints for local FDP. Finally, our results in Section 3.1 are restricted to univariate mean estimation, and extending them to high-dimensional estimation under non-e-LDP would be non-trivial task.
Acknowledgement
This work was supported by the Institute of Information Communications Technology Planning & Evaluation (IITP) grant funded by the Korean government (MSIT) (No.2022-0-0099 Solving the problem of increasing the usability and usefulness of synthetic data algorithms for statistical data.) The work of Jeongyoun Ahn was partially supported by the National Research Foundation of Korea (NRF-20218) IR A2C1093526, RS-2023-002182311 The work of Cheolwoo Park was partially supported by the National Research Foundation of Korea (NRF-2021R) RI A2C1092925)
10

---

References
Algan, Y., Bacache--eeaeeee Beauvallet, M., and Perrot, A. (2016). Digital administration. Notes du Conseil Danalyse Economique, 34(7):1-12.
Asoodeh, S., Aliakbarpour, M., and Calmon, (2021). Local differential privacy is equivalent contraction of an f-divergence. 202/ IEEE International Symposium on Information Theory (ISIT). pages 545-550.
Butucea, C., Dubois, A., Kroll, M., Saumard, A. (2020), Local differential privacy: Elbow effect in optimal density estimation and adaptation over Besov ellipsoids. Bernoulli, 26(3):172--1764
Cai, T. T., Wang, Y., and Zhang, L. (2021). The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 4965):2825-2850.
Carroll, R. J. and Hall. P. (1988). Optimal rates of convergence for deconvolving density. Journal of the American Statistical Association, 1844446:
Chhor, J. and Sentenac, F. (2023). Robust estimation of discrete distributions under local differential privacy. In Proceedings of The 34th International Conference on Algorithmic Learning Theory, volume 201 of Proceedings of Machine Learning Research, pages 411 411-446. PMLR.
Ding, B., Kulkarni, J., and Yekhanin, S. (2017). Collecting telemetry data privately. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc.
Dinur, 1. and Nissim, K. (2003). Revealing information while preserving privacy. In Proceedings of the Twenty-Second ACM SIGMOD WIGMOD-SIGACT-SS SEA--SSGAAGGGAAAA Symposiun on Principles of Database Systems, PODS '03, pages 202 210. Association for Computing Machinery.
Dong, Roth, A., and Su, W. J. (2022). Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84:3-37.
Duchi, J. C., Jordan, M. I., and Wainwright, M. J. (2013). Local privacy and statistical minimax rates. In 2013 JEEE 54th Annual Symposium on Foundations of Computer Science, pages 429-438.
Duchi, J. C., Jordan, M. I., and Wainwright, M. J. (2018). Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 1136521):122-211.
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. (2006a). Our data, ourselves: Privacy via distributed noise generation. In Advances Cryptolog-EEUROCCYPP 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings 25. Springer.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. (2006b). Calibrating noise to sensitivity private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, Proceedings 3, pages 164. Springer.
Erlingsson. U., Pihur, V., and Korolova, A. (2014). Rappor: Randomized aggregatable privacy- preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC Conference Computer and Communications Security, CCS '14, page 1054 1067. Association for Computing Machinery.
Fanti, G., Pihur, V., and Erlingsson, Ú. (2016). Building rappor with the unknown: of associations and data dictionaries. Proceedings on Privacy Enhuncing Technologies, 3:41-61.
learning
Kamath, G., Mouzakis, A., and Singhal, V. (2022). New lower bounds for private estimation and generalized fingerprinting lemma. In Advances in Neural Information Processing Systems, volume 35, pages 24405-20 -24188. Curran Associates,
Kamath, and Ullman, (2020). primer on private statistics. arXiv preprint arXiv:2005.000
Kessler, S., Hoff, Freytag, (2019), SAP HANA goes private from privacy research privacy aware enterprise analytics. Proc. VLDB Endow. 12(12):1995 2009.
Kroll, M. (2021). On density estimation at fixed point under local differential privacy. Electronic Journal of Statistics, 15(1):1833-181..
Li, M., Berrett, T. B., and Yu, Y. (2022). On robustness and local diffcrential privacy. arXiv preprint arXiv:2201.0075)
Meiser, S. (2018). Approximate and probabilistic differential privacy definitions. Cryptology ePrint Archive.

---

Mironov, 1. (2017). Rényi differential privacy. In 2017 JEEE 30th Computer Security Foundations Symposion (CSF). pages 263-275.
Rohde, A. and Steinberger, L.. (2020). Geometrizing rates of convergence under local differential privacy constraints. The Annals of Statistics, 48(5):2646 2670.
Sweeney, L. (2000). Simple demographics often identify people uniquely. Heaalhh (San Francisco), 671:1-34.
Sweeney, I.. (2002). Achieving k-anonymity privacy protection using generalization and suppression. Interna- tional Journal of Uncertainty, Fuzziness and Knowledge- Systems, 10(05):571-583
Tang. J., Korolova, A., Bai, X., Wang. X., and Wang, X. (2017). Privacy loss in Apple's 's implementation of differential privacy on MacOS 10.12. arXiv preprint ar 1i0iv:7709.027.
Thakurta, A. G., Vyrros, A. H., Vaishampayan, U. S., Kapoor, G., Freudiger, J., Sridhar, V. R., and Davidson, D. (2017). Learning new words. Granted US Patents, 9,645,998 [Online] Available: http://wwww.oogl..oooo//a///////
Tsyhakov, A. B. (2009). Introduction to Nonparametric Estimation, 2009. Springer Series in Statistics.
Wang, S., Luo, X., Qian, Y., Du, J., Lin, W., and Yang. W. (2022). Analyzing preference data with local privacy: Optimal utility and enhanced robustness. IEEE Transactions Knowledge and Data Engincering, pages 1-14.
Wasserman, L. and Zhou, S. (2010). A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375-38.
12


Reviews:
[{"review_id": "iT8j43wMSB", "reviewer": "Reviewer_6GNC", "summary": "This paper investigates the minimax risk achieved under functional local differential privacy (FLDP) constraints, and particularly under Gaussian local differential privacy (GLDP). The authors first introduce lower bounds for univariate mean estimation under FLDP using Le Cam’s method. Under certain assumptions on the threshold function (satisfied by GLDP) this rate matches the one with $\\epsilon$-LDP introduced by Duchi et al (2018). They then use this result to derive upper and lower bounds for GLDP and a mechanism achieving this rate. \n\nSimilarly, they use Assoud’s method to derive lower and upper bounds for non-parametric density estimation, and the corresponding mechanism achieving optimality.\n\nThe authors empirically show their private mean estimation algorithm outperforms the one introduced in Duchi et al. (2018). \n", "questions": "- Could the authors discuss the three main points above? \n", "limitations": "- The authors clearly describe some of the limitations of their work in the conclusion. First, the optimality is only achieved for kappa=1 that corresponds to pure local DP. Second, results only hold for a certain class of threshold functions. And finally, mean estimation is only analyzed in one dimension. The high dimensional case remains an open problem under FLDP.\n\n- Besides these limitations, the condition on threshold functions does not seem easy to verify. Further, it remains unclear if in practice the mechanisms provided will actually have better performance.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is very well written and clear. It introduces simple mechanisms to achieve optimal minimax rates for two important problems, namely (1) univariate mean estimation and (2) non-parametric density estimation. \n\n\n- Further, their theoretical results provide an understanding of the tradeoff between utility and privacy for mean estimation. By analyzing the minimax risk under the lens of FLDP they introduce a continuous measure between privacy and utility, parametrized by a constant kappa, such that kappa=0 corresponds to non-privacy and kappa=1 corresponds to pure local DP. \n", "weaknesses": "1. Constants matter in differential privacy. In the current state of the paper it is clear that asymptotically the rates are the same, however it is hard to get an intuition of the constants. The plots however provide evidence that the suggested approach does provide better results. \n\n2. After Duchi et al. 2018’s paper there have been other papers introducing local DP algorithms, however the paper only compares theoretically and empirically to Duchi et al. 2018. Due to constants these other algorithms could perform better under certain regimes.\n- https://ieeexplore.ieee.org/document/8006630\n- https://proceedings.mlr.press/v162/asi22b/asi22b.pdf\n\n3. Algorithm complexity is only qualified as “less complex” or “more straightforward”.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's thoughtful comments and insightful feedback.\n\n**Q1:** Constants matter in differential privacy. In the current state of the paper it is clear that asymptotically the rates are the same, however it is hard to get an intuition of the constants. The plots however provide evidence that the suggested approach does provide better results.\n\n**A1:** We agree that constants can have substantial meaning in differential privacy, especially in practice. We have attempted to derive the optimal constants for the results in Duchi et al. (2018) to compare with ours. Their result implies that \n\\begin{equation*}\n\\mathcal{R}\\leq(\\beta+1)\\left(\\frac{\\beta}{\\sqrt{2\\pi e}}n\\left(\\frac{e^{\\epsilon}+1}{e^{\\epsilon}-1}\\right)^{-2}\\right)^{-\\frac{2\\beta}{2\\beta+2}}r^{\\frac{2}{\\beta+1}},\n\\end{equation*}\nwhile our risk bound from a similar calculation becomes:  \n\\begin{equation*}\n\\mathcal{R}\\leq(\\beta+1)\\left(0.5\\beta n\\mu^2\\right)^{-\\frac{2\\beta}{2\\beta+2}}r^{\\frac{2}{\\beta+1}}+O\\left(n^{-\\frac{2\\beta+1}{2\\beta+2}}\\right).\n\\end{equation*}\nComparing the coefficients of $n^{-\\frac{2\\beta}{2\\beta+2}}$, we have\n\\begin{equation*}\n \\frac{c_{ours}}{c_{Duchi}}=\\left(\\frac{0.5\\mu^2}{\\frac{1}{\\sqrt{2\\pi e}}\\left(\\frac{e^{\\epsilon}+1}{e^{\\epsilon}-1}\\right)^{-2}}\\right)^{-\\frac{2\\beta}{2\\beta+2}}=\\left(\\sqrt{\\frac{\\pi e}{2}}\\mu^2\\left(\\frac{e^{\\epsilon}+1}{e^{\\epsilon}-1}\\right)^2\\right)^{-\\frac{2\\beta}{2\\beta+2}}.\n\\end{equation*}\nIf $\\mu=1$, as in the experiment, $c_{ours}<c_{Duchi}$ holds for every $\\epsilon>0$, suggesting that our algorithm can potentially achieve a smaller risk, which is also empirically demonstrated in our paper. However, we note that these constants could only reflect the upper bounds of potential risks, rather than the risks themselves.\n\n**Q2:** After Duchi et al. (2018)’s paper, there have been other papers introducing local DP algorithms, however, the paper only compares theoretically and empirically to Duchi et al. (2018). Due to constants, these other algorithms could perform better under certain regimes.\n\nYe and Barg (2017) (https://ieeexplore.ieee.org/document/8006630)  \n\nAsi et al. (2022) (https://proceedings.mlr.press/v162/asi22b/asi22b.pdf) \n\n**A2:**  We agree that other algorithms could perform better under some regimes. However, we want to point out that our settings for the considered estimation problems are different from those works. First, the distribution family that are considered for nonparametric density estimation in both ours and Duchi et al. (2018) is assumed to have a density with smoothness parameter $\\beta>1/2$. However, Ye and Barg (2017) and most other related works deal with either discrete distributions or a discretized version of a continuous density. \n    \nSecond, for the univariate mean estimation, we assume that the random variable is unbounded, but has bounded moments. The majority of related studies including Asi et al. (2022) focus on high-dimensional, bounded variables. This disparity makes the comparison unaccountable. Specifically, when privately estimating the mean of an unbounded random variable, a cut-off procedure is crucial to ensure privacy, and determining the cut-off point plays a significant role in achieving the optimal risk. In contrast, private mechanisms for bounded high-dimensional mean estimation do not need a cut-off, as their data is inherently bounded. The assumed boundedness yields the minimax rates that are comparable (with respect to $n$) to non-private estimation, which is not possible in our setting. \n\n**Q3:** Algorithm complexity is only qualified as “less complex” or “more straightforward”.\n\n**A3:** The computational complexity of both Duchi et al. (2018) and our algorithms is $O(n^{(\\beta+2)/(\\beta+1)})$. However, our algorithm is considered canonical and offers a more straightforward implementation."}, {"review_id": "XkxKnBfP1l", "reviewer": "Reviewer_qJiE", "summary": "The paper proposes a local version of functional differential privacy (FDP), and finds the minimax rate of mean estimation and non-parametric density estimation under local FDP. This paper amounts to an extension of the main results of Duchi et al. (2018) from epsilon-LDP to local FDP.", "questions": "* The role of lower bounds varying continuously with $\\kappa$. If ultimately the matching upper and lower bounds only needed the $\\kappa = 1$ case, what is the purpose of considering this continuous family of lower bounds? For those trade-off functions satisfying Lemma 1, does $\\kappa = 1$ always imply the best minimax rate? Do you know of any trade-off function $f$, possibly violating Lemma 1, such that choosing a $\\kappa$ strictly between 0 and 1 is necessary?\n\n* What technical innovations are needed to extend the epsilon-LDP versions of Le Cam's inequality and Assouad's inequality to local FDP?\n\n* From a DP practitioner's point of view, why might one want to consider local FDP? As the paper reveals, there is hardly evidence that local FDP offers better statistical utility, and the cognitive burden of describing/understanding local FDP is certainly higher than the epsilon-LDP case. Additionally, for non-Gaussian tradeoff functions, it may not be easy to come up with an appropriate privatization method.", "limitations": "Section 5 has comprehensively discussed the limitations from a technical point of view. Discussions on more foundational questions, such as the usefulness of extending FDP to the local setting, or even the technical innovations required, if any, for extending epsilon-LDP theory to local FDP, would be much appreciated.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "Originality: the paper is the first to consider extending functional DP to the local setting, to the best of my knowledge.\n\nQuality and clarity: the technical claims are carefully proved and concisely explained.\n\nSignificance: because FDP offers many advantages over (epsilon, delta)-DP in the central setting, it is useful to understand whether some advantage also exists in the local setting. The comparison between mu-GDP and epsilon-LDP in this paper provides some (perhaps negative?) insight in this regard.", "weaknesses": "* Key concepts such as epsilon-LDP and local FDP are never formally defined in the main paper. As the definition of LDP is not entirely a trivial extension of central DP to begin with (for example, see Duchi et al. (2018)'s treatment of this concept), it is a risky choice to expect readers to extrapolate the (central) FDP definition to local FDP, as understanding the definition of local FDP is essential for reading the rest of the paper.\n\n* High-level contribution of this paper. While I appreciate the neat mathematical arguments and results on local FDP, this paper leaves me wondering why local FDP is a worthwhile notion of privacy to consider. The original FDP paper by Dong et al. provides some convincing arguments for FDP, but this paper seems to be much more interested in deriving minimax rates as a mathematical exercise, without critically thinking about the underlying notion of privacy. I wish the paper had devoted some discussion to this question either before or after its mathematical investigations. From a mathematical point of view, the generalizations of epsilon-LDP Le Cam's and Assouad's inequalities by Duchi et al. can be interesting in their own right, but neither do these generalizations suggest any qualitative difference between epsilon-LDP and local FDP besides different contraction constants.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's thoughtful comments and insightful feedback.\n\n**Answer to Q1 on $\\kappa$:** (i)  We examined a continuous range of lower bounds relative to $\\kappa$ with the purpose of investigating the *gradual shift* in optimal utility associated with privacy constraints. It was motivated by the connection between the trade-off function and the contraction coefficient $c_{f,\\kappa}$, as well as the exponent of the minimax rate. While our findings do not yield an explicit result for $\\kappa<1$, we note that there has not been any research on private nonparametric density estimation in this particular $\\kappa$ regime. Therefore, our work can provide indirect insights into private estimation with privacy constraints $\\kappa<1$.\n\n(ii) It is true that $\\kappa=1$ is optimal with respect to minimax rates for trade-off functions satisfying Lemma 1. Another way to appreciate this is the following: For a trade-off function $f$, there exists a trade-off function $f_{\\epsilon}$ such that $f$-FDP is equivalent to $\\epsilon$-DP for some $\\epsilon>0$ except for the case of $f(x)=1-x$. This allows us to leverage optimal mechanisms designed for $\\epsilon$-LDP, which achieve the minimax rates of $O\\left(n^{-\\frac{2k-2}{2k}}\\right)$ for univariate mean estimation and $O\\left(n^{-\\frac{2\\beta}{2\\beta+2}}\\right)$ for nonparametric density estimation. When $\\kappa=1$, the corresponding lower bound retains the same rate, meaning that the theoretical lower bounds align with the optimal minimax rates.\n\n(iii) There are trade-off functions that contradict Lemma 1 and need $\\kappa< 1$. For example, when $f(x)=1-x^{\\frac{\\kappa}{1+\\kappa}}$ we have \n$\\delta_f(y)=\\sup_{x\\in [0,1]}1-yx-f(x)=\\sup_{x\\in[0,1]}x^{\\frac{\\kappa}{1+\\kappa}}-yx=\\frac{\\kappa^{\\kappa}}{(1+\\kappa)^{1+\\kappa}}y^{-\\kappa}$\nfor large $y>y_0$ for some $y_0>0$. Also $1\\geq f(y)\\geq 1-y\\cdot 0-f(0)\\geq 0$. Thus, $\\int t^{\\kappa-1} \\delta_f(t)dt$ diverges. Therefore, for every $\\kappa_0\\in (0,1)$, there exists a trade-off function requiring $\\kappa$ to be less than $\\kappa_0$.\n\n**Answer to Q2 on technical innovation:** Both Le Cam's and Assouad's inequalities establish minimax lower bounds by considering distributions that are similar but differ in target parameters. When these similar distributions possess substantially distinct parameters, the estimation task becomes challenging and the minimax risk tends to increase. Introducing a privacy constraint to the estimation problem yields that the distributions of observables—outputs of the privacy mechanism—become less distinguishable from one another compared to the original distributions, while the true value of the target parameter stays the same.\n\nTo extend the Le Cam and Assouad methods from non-private settings to private estimation, one needs to establish a connection between the difference in distributions of mechanism outputs, $M(P_1)$ and $M(P_2)$, and the divergence between the original input distributions $P_1$ and $P_2$. Prior approaches achieved this via a uniform bound on the output distribution difference (expressed as the likelihood ratio) over the sample space, under the $\\epsilon$-LDP assumption.\n\nIn our work, we found that most local DP mechanisms tend to exhibit properties akin to $\\epsilon$-LDP for certain values of $\\epsilon$, even if they do not satisfy strict $\\epsilon$-LDP.  In order to extend the $\\epsilon$-LDP versions of Le Cam's and Assouad's inequalities to the local version of $f$-DP, we determined bounds for the probability that an $f$-DP mechanism behaves like $\\epsilon$-DP. \nIn other words, we derived an inequality that governs the likelihood ratio of outputs of mechanisms $\\mathbb{P}\\left(\\frac{f_{M(P_1)}(Z)}{f_{M(P_2)}(Z)}>e^\\epsilon|Z\\sim M(P_2)\\right)$ for distributions $P_1,P_2\\in\\mathcal{P}(\\mathcal{X})$. Considering such probability was critical in order to treat local FDP as if they were $\\epsilon$-LDP and this can be considered as a key technical innovation of our paper.\n\n**Answer to Q3 on local FDP:** We think that there might be a possibility for achieving a better minimax rate through local FDP compared to $\\epsilon$-LDP. Specifically, in our response to the first question from Reviewer 6GNC, we theoretically demonstrate that our FLDP algorithm has an improved constant compared to the LDP algorithm Duchi et al. (2018) in nonparametric density estimation (even though the orders of the minimax rates are the same), which implies a practical advantage of our method. You can find more details regarding this discussion in that response.\n\nIn addition, implementing privacy mechanisms under $\\epsilon$-LDP presents a challenge in managing the privacy budget, particularly when composing multiple mechanisms. Effective composition rules are essential to strike the right balance between privacy protection and estimation accuracy. Inefficient composition rules tend to overestimate privacy leakage, leading to excessive perturbation of estimations. Even when minimax rates remain identical across different privacy schemes, an inefficient composition rule can practically undermine the overall performance. The shortcomings of the composition rule for $(\\epsilon,\\delta)$-DP are widely acknowledged, and other relaxations of DP have also faced criticism for their inefficient composition rules. In that regard, we believe that FDP possesses an effective composition rule.\n\nLastly, we note that Awan et al. (2023) have introduced an additive mechanism that achieves $f$-FDP across a wide array of trade-off functions $f$, and Awan et al. (2022) have developed multivariate $f$-FDP mechanisms as well as log-concave $f$-FDP mechanisms tailored to specific $f$ functions. While we cannot definitively ascertain their suitability as effective privatization methods without further investigation, these approaches offer potential avenues for applying non-Gaussian trade-off functions to achieve privacy objectives."}, {"review_id": "0jysGIjXmF", "reviewer": "Reviewer_fz6L", "summary": "The authors study the problems of mean estimation and density estimation under functional local differential privacy (FLDP). In particular, they are interested in deriving minimax (rate-) optimal estimation procedures and privacy mechanisms for these problems. Their results include analogues to Le Cam's bound and Assouad's bound for the FLDP setting. They then specialize these results to the previously mentioned problems and derive minimax lower bounds as corollaries. They also provide algorithms which match the rates specified by their lower bounds. Finally, numerical experiments confirm empirically that their methods achieve better privacy/utility tradeoffs than existing methods which enforce LDP.", "questions": "1. Can the authors provide more interpretation of the general versions of Le Cam's and Assouad's bounds (Theorems 1 & 3)? Even some simple intuition such as, when would we expect the lower bound to be non-negative, etc. would be helpful.\n\n2. Can you more context for the parameter $\\kappa$ and how it interpolates between the non-private and $\\epsilon$-LDP settings?\n\n3. Can you provide some intuition as to why your techniques for univariate mean estimation can't be easily extended to higher dimensions?", "limitations": "The authors have a nice discussion of the paper’s limitations (as well as possible directions for future work) at the end of their conclusion section. The main limitations include some restrictive technical conditions, as well as the fact that their mechanisms only achieve the minimax rate in limited settings.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This work is the first to address minimax estimation rates for functional local DP. Functional DP was introduced recently and has received a great deal of attention, and understanding its properties and advantages is of great interest to the community. As such, this paper offers a relevant and novel contribution. I did not check all of the proofs, but those I did were technically sound.\n\nThe results in the paper are quite extensive. The authors not only derive the minimax rate for two fundamental estimation problems (univariate mean estimation and density estimation), but also give algorithms which match the minimax rate. In addition to these strong theoretical results, their algorithms also offer practical improvement over existing alternatives, as can be seen from their empirical evaluation.\n\nThe paper is also very well written. I found the background section to be a very helpful introduction to both functional local DP and private minimax estimators for a non-expert. The authors also give helpful intuition and interpretations for many of their technical results, which make this highly technical paper much easier to parse.", "weaknesses": "While the authors did a good job providing interpretation for many of their results to make the paper accessible to non-experts, some results still seemed opaque to me. For instance, the instantiation of the Le Cam's and Assouad's bounds provided some intuition for how these results could be useful, but I did not grasp the intuition for either of the more general results (Theorems 1 & 3). In particular, it seems like for large n, the lower bound in both of these theorems will actually be negative and therefore vacuous. Adding some further interpretation of the general bounds would be helpful.\n\nThe authors also make a point that their results smoothly interpret between private and non-private regimes, a feature which is lacking from existing analyses. This is of course a strength of the paper (mentioned above), but I did not understand the connection with $\\kappa$ in the general lower bounds. In particular, I see that the minimax optimal rates for mean estimation are recovered for $\\kappa = 0,1$, but it was not clear to me why these values of $\\kappa$ correspond to private/non-private settings. A more thorough explanation of this (probably in terms of the relationship between $\\kappa$ and the tradeoff function $f$) would be helpful.\n\nLastly, the experimental section is fairly sparse. Since this is primarily theoretical paper, I think it is a fairly minor point.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's thoughtful comments and insightful feedback.\n\n**Q1:**  Can the authors provide more interpretation of the general versions of Le Cam's and Assouad's bounds (Theorems 1 & 3)? Even some simple intuition such as, when would we expect the lower bound to be non-negative, etc. would be helpful.\n\n**A1:** The general form of Le Cam's and Assouad's inequalities could indeed become trivial, i.e., the risk bound can be negative. For the Le Cam's method as an example, a negative bound can be prevented by carefully choosing the two distributions $P_1$ and $P_2$ with \"similar'' densities (i.e., smaller total variation) for a fixed value of $\\eta$. A proper choice of these distributions will adequately represent the innate challenge regarding the given estimation problem quantified by the minimax risk. The choice of $\\eta$ in relation to $n$ is made deliberately to ensure that the lower bound remains positive and it consequently influences the rate of the lower bound. \n\nThe lower bound itself can be interpreted as the following.  For a given parameter difference $\\eta$, as the dissimilarity between the densities (TV) decreases, the problem becomes difficult so the lower bound increases, and vice versa. \n\n**Q2:** Can you add more context for the parameter $\\kappa$ and how it interpolates between the non-private and $\\epsilon$-LDP settings?\n\n**A2:**  The role of the parameter $\\kappa$ can be understood in the context of the contraction coefficient $c_{f,\\kappa}=(1-\\kappa)^{1-\\kappa}\\kappa^\\kappa\\int (\\kappa+1)t^{\\kappa-1}\\delta_f(t)dt$, which involves $\\delta_f(t)$\n    and $\\kappa$. (Recall: $f$-FLDP is equivalent to $(\\epsilon,\\delta_f(e^\\epsilon))$-LDP.) Our minimax bounds are non-trivial only when $c_{f,\\kappa}$ is finite, and this necessitates $\\delta_f(t)$ to decrease faster than $t^{-\\kappa}$. Consequently, a larger value of $\\kappa$ (close to 1) requires a smaller value of $\\delta_f(t)$, aligning with a more private setting. On the contrary, in a less private setting, $\\delta_f(t)$ grows, compelling $\\kappa$ to decrease in order to uphold the condition $c_{f,\\kappa}<\\infty$.\n\n**Q3:** Can you provide some intuition as to why your techniques for univariate mean estimation can't be easily extended to higher dimensions?\n\n**A3:** The challenge in extending to the high-dimensional mean estimation problem is that we rely on the *probability* that the likelihood ratio is bounded, while in the case of $\\epsilon$-LDP, it regards the pointwise-bounded nature of the likelihood ratio between outputs of mechanisms. This discrepancy introduces a challenging technical aspect, as the meticulous selection of distributions highlighted in A1 must be carried out for each component. Consequently, this entails managing multiple distributions in high-dimensional spaces. We suggest this problem as future research."}, {"review_id": "b6z611ntYD", "reviewer": "Reviewer_H56L", "summary": "The authors consider the a local version of functional DP / Gaussian DP, and establish minimax rates of convergence for mean estimation and density estimation under this privacy paradigm.  They highlight how functional/Gaussian DP is more conducive to LDP than approximate DP given it’s tight compositional properties.   They demonstrate how properties of the tradeoff function play a critical role in the minimax risk. ", "questions": "See weaknesses.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This is a timely work given the recent attention GDP has received.  Understanding minimax rates for LDP in such a setting seems like an important contribution.  The mathematical results are thorough, and translating properties of the tradeoff function into minimax rates is interesting.", "weaknesses": "A seemingly glaring problem with results such as Corollary 2 is the privacy level, $\\mu$, is not made explicit in the rate.  However the constants in the theorem do depend on $\\mu$.  The results of Duchi et al make the dependence on epsilon explicit, and it is quite substantial (i.e. taking substantially smaller values of \\epsilon will substantially reduce the effective sample size).   The authors then discuss how surprising it is that $\\epsilon$ LDP and $\\mu$ GLDP would have the same minimax rate, but the authors didn’t show this since their rate does not include $\\mu$.  I find this unfortunate, as otherwise the paper is quite interesting, but the final comparison with $\\epsilon$ LDP falls flat and unfinished.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q**: A seemingly glaring problem with results such as Corollary 2 is the privacy level, $\\mu$, is not made explicit in the rate. However the constants in the theorem do depend on $\\mu$. The results of Duchi et al make the dependence on epsilon explicit, and it is quite substantial (i.e. taking substantially smaller values of epsilon will substantially reduce the effective sample size). The authors then discuss how surprising it is that LDP and GLDP would have the same minimax rate, but the authors didn’t show this since their rate does not include $\\mu$. I find this unfortunate, as otherwise the paper is quite interesting, but the final comparison with LDP falls flat and unfinished.\n\n**A**: We appreciate the reviewer's thoughtful comments and insightful feedback. As demonstrated in the paper, both LDP and GLDP share the same minimax rate concerning $n$. However, their equivalence does not extend to privacy constraints in our theoretical results. In response to the reviewer's suggestion, we have undertaken additional calculations to determine the minimax rate while incorporating privacy constraints. The derived bounds are as follows: \n\\begin{equation*}\nO\\left(\\left(ne^{\\mu^2}\\right)^{-\\frac{2(k-1)}{2k}\\textbf{or}-\\frac{2\\beta}{2\\beta+2}}\\right)\\leq\\mathcal{R}\\leq O\\left(\\left(n\\mu^2\\right)^{-\\frac{2(k-1)}{2k}\\textbf{or}-\\frac{2\\beta}{2\\beta+2}}\\right)\n\\end{equation*}\nfor both univariate mean estimation or nonparametric density estimation.\nThis analysis highlights that our approach does not yield a unified minimax rate in terms of $\\mu$. Furthermore, the observation that $e^{\\mu^2}\\longrightarrow1$ as $\\mu\\longrightarrow0$ contrasts with the behavior of the lower bounds presented in Duchi et al. (2018), which tend towards infinity as $\\epsilon\\longrightarrow0$.  Hence, further efforts are required to establish a rigorous minimax rate in terms of privacy constraints for local FDP."}]

Author rebuttal:

Meta-review: All reviewers agreed that the paper should be accepted. The reviewers' questions during the discussion period led the authors to refine the constants and rates in their analysis, and they are encouraged to incorporate this discussion into the final version of their paper.
Decision: Accept (poster)