Differentially Private Boxplots
Authors: Kelly Ramsay
Jairo Diaz-Rodriguez
Venue: ICML 2025 poster (2025)
Keywords: differential privacy
data visualization
boxplots
exploratory data analysis
Primary area: social_aspects->privacy
TL;DR: Differentially Private Boxplots

Abstract: Despite the potential of differentially private data visualization to harmonize data analysis and privacy, research in this area remains  underdeveloped. Boxplots are a widely popular visualization used for summarizing a dataset and for comparison of multiple datasets. 
Consequentially, we introduce a differentially private boxplot. We evaluate its effectiveness for displaying location, scale, skewness and tails of a given empirical distribution. In our theoretical exposition, we show that the location and scale of the boxplot are estimated with optimal sample complexity, and the skewness and tails are estimated consistently, which is not always the case for a boxplot naively constructed from a single existing differentially private quantile algorithm. As a byproduct of this exposition, we introduce several new results concerning private quantile estimation. In simulations, we show that this boxplot performs similarly to a non-private boxplot, and it outperforms the naive boxplot. Additionally, we conduct a real data analysis of Airbnb listings, which shows that comparable analysis can be achieved through differentially private boxplot visualization.

Differentially Private Boxplots
Kelly Ramsay"
Jairo Diaz-Rodriguez"
1
Abstract
practitioners, Garrido et al. (2023) found that "most analysts employed aggregations and visualizations to fulfill their use case," rather than machine learning models.
Despite the potential of differentially private data visualization to harmonize data analysis and pri- vacy, research in this area remains underdevel- oped. Boxplots are a widely popular visualization used for summarizing a dataset and for compar- ison of multiple datasets. Consequentially, we introduce differentially private boxplot. We evaluate its effectiveness for displaying location, scale, skewness and tails of a given empirical distribution. In our theoretical exposition, we show that the location and scale of the boxplot are estimated with optimal sample complexity, and the skewness and tails are estimated consistently, which is not always the case for boxplot naively constructed from a single existing differentially private quantile algorithm. As byproduct of this exposition, we introduce several new results concerning private quantile estimation. In simu- lations, we show that this boxplot performs simi- larly to non-pri non-private boxplot, and it outperforms the naive boxplot. Additionally, we conduct a real data analysis of Airbnb listings, which shows that comparable analysis can be achieved through differentially private boxplot visualization.
Differentially private versions of several popular visualiza- tions have been considered in the literature. Nanayakkara et al. (2022) developed a plot to visualize privacy utility trade-offs. Zhou et al. (2022) developed DPVisCreator, visualization system, which relies on publishing syn- thetic dataset. Visualizations in other privacy models were considered by Dasgupta & Kosara (201 1); Dasgupta et al. (2013; 2019), and recently reviewed by Bhattacharjee et al. (2020). There has been substantial study of the differen- tially private histogram (Hay et al., 2010; Li et al., 2010; Acs et al., 2012; Kellaris & Papadopoulos. 2013; Xu et al., 2013; Zhang et al., 2014; Budiu et al., 2022). Visualiza- tions based on clustering (Hongde et al., 2014), for mobility data (He et al., 201 heatmaps (Zhang et al., 2016) and scatterplots (Panavas et al., 2024) have also been considered.
Surprisingly, despite its widespread use, a differentially private boxplot has not been directly studied. Boxplots, invented by Tukey et al. (1977), are used for visualizing the characteristics of univariate sample, as well as for visualizing the relationship between continuous variable and categorical variable. Despite its simplicity, many key distributional characteristics can be evaluated from the boxplot: namely, location, scale, skewness, and tails. This has made it popular among practitioners.
1. Introduction
It is now well established that differential privacy (Dwork et al., 2006) is powerful framework for protecting the privacy of individuals" data. As a result, plethora of differ- entially private data analysis tools have been developed over the last several decades (Dwork, 2008; Ji et al., 2014; Liu et al., 2023). However, one area that has been considerably underdeveloped is that of differentially private visualization. This is despite the fact that data visualization is a key tool in exploratory analysis, which is an essential component of data analysis. In fact, in recent study of data analysts and
In addition, its simplicity is beneficial from privacy stand- point. The boxplot only requires estimating few summary statistics in order convey the distributional characteristics of a univariate sample, making the boxplot efficient in its use of privacy budget. For instance, by contrast, histogram can also be used to convey the same information. However, a histogram is generally a consistent estimate of the popu- lation density, which intuitively, should then require more noise to ensure privacy.
Motivated by these observations, we take the first steps in de- veloping and studying differentially private boxplots. First, one can observe that a boxplot is made up of sample quan- tiles. It is then natural to first consider how well a boxplot constructed from naive applications of existing differentially private quantile algorithms. Succinetly:
'Equal contribution 'Department of Mathematics and Statistics, York University, Toronto, Canada. Correspondence to: Kelly Ramsay 2ornnaaayyyoruu.ca....
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Differentially Private Boxplots
How well does the "naive" private boxplot perform?
lower bound on private medians (Tzamos & Vlatakis- Gkaragkounis, 2020).
On this front, with a combination of new theoretical re- sults and simulations, we demonstrate that this method may fail on data coming from common distribution families. We focus on the state-of-the-art algorithms JointExp (Gillenwater et al., 2021), Privatequantin 2011), ApproxQuantile (Kaplan et al., 2022), and unbounded (Durfee, 2023). Due to limited space, our rationale for this choice, and a full literature review on private quantiles, including how our results build on this literature, is relegated to Appendix D. See also the related problem of differentially private range estimation (Kaplan al., 2020). While range queries can be used compute quantiles (Bun et al., 2015; Kulkarni, 2019; Kaplan et al., 2020), our focus is on more practical methods that estimate differentially private quantiles. In summary:
Given that the naive boxplot not satisfactory, we then sought answer:
(Smith,
Can we develop novel private boxplot, which performs well at generating both the box and whiskers?
To this end, building on the aforementioned results concern- ing private quantiles, we present novel differentially pri- vate boxplot, which we call DPBoxplot. We then evaluate its ability to represent key fcatures-location, scale, skew- ness, and tails-both theoretically and empirically. Figure I provides an informal, graphical illustration of our approach. Specifically, we use Joi Exp for estimating the quartiles and the median to construct the box, and unbounded for determining extreme values necessary for the whiskers and the number of outliers. Instead of revealing the precise loca- tions of outliers, we privately disclose their count using the Laplace mechanism. In summary, our main contributions concerning the new differentially private boxplot are:
We prove that Jo ntExp, pri vateQuant e and ApproxQuants le are (almost always) inconsistent for extreme quantiles (Lemma 4.1), which makes them a poor choice for generating the whiskers in the box- plot. (To our knowledge, no results concerning the consistency of extreme private quantiles previously ex- isted. Lalanne et al. (2023b) proved consistency for inner quantiles, under the assumption of a lower bound on the density, which would not apply to extreme quan- tiles.)
We carefully combine private quantile estimators, en- suring that those used for the location and scale of the boxplot are estimated optimally (Theorem 4.2), while the extreme quantiles required to depict skewness and tails remain consistent (Theorem 4.5).
Extensive simulations demonstrate that DPBoxplot is often more accurate than those constructed naively using existing differentially private quantile methods, see Section 5.
We prove that unbounded is consistent for extreme quantiles (Lemma B.3). This result also confirms an empirical observation of Durfee (2023), which says that the unbounded quantile algorithm performs bet- ter than existing algorithms for estimating extreme quantiles. (To our knowledge, no statistical results concerning unbounded previously existed.)
We conduct differentially private exploratory data analysis, showcasing the practical utility and shortcom- ings of DP Boxplot, see Section 6.
Our simulations reveal that the unbounded al- gorithm does not perform as well as Jxp, ApproxQuantile or PrivateQuantiL for es- timating the inner quantiles of Gaussian data. This makes it a poor choice for generating the box in the plot. We support this finding by providing matching (up to logarithmic factors) upper and lower bounds for the sample complexity of JointExp ApproxQuantiln le and Privatequantic ile for estimating inner quantiles, under general distributional assumptions (Theorem 4.2 and Theorem 4.4). In par- ticular, only assume that the density is positive in neighborhood of the theoretical quantile and bounded everywhere (Condition 1). Previous concentration re- sults for these algorithms assume the population den- sity has bounded support (Lalanne et al., 2023a). The lower bound is new, and does not follow from the
2. Preliminaries
First, we briefly review the boxplot. It is also helpful to in- troduce some notation used throughout the paper. We define dataset of size E N to be set of real numbers. Let D,, be the set of datasets of size n and let X,, = {X,,..., X,, be dataset size n. In this work, we assume the analyst has access to a dataset, denoted by X,, We will also assume that X,, consists of ri independent draws of from a common population distribution or measure, denoted v. We consider the traditional boxplot, which consists of box with a line drawn through it, with two whiskers emanating from the lower and upper bounds of the box, see Figure 1. The box is made up of the median and the quartiles, while the whiskers, represent the tails and skewness of the data. Points beyond the whiskers are explicitly plotted. Together, this 5 number summary describes the empirical distribution of the data,
2

---

Differentially Private Boxplots
outliers
4
DP outliers Laplace mechanism min maximum value) unbounded (DP & + 1.5 DP IQR/
the unbounded algorithm of Durfee (2023) and the JointExp algorithm of Gillenwater et al. (2021). These algorithms are the main focus of our theoretical expo- sition. However, the PrivateQuantile is a special case of JointExp and so our results also apply to PrivateQuantile In addition, combining our results with those of Kaplan et al. (2022) allows our results to also hold for ApproxQuantile We do, however, consider the performance of the naive boxplot constructed from all three of these algorithms in our simulation study, see Sec- tion 5. We now give a brief overview of JointExp and unbounded. JointExp works as follows: Suppose we wish to estimate m E N quantiles of levels 0 < 9i < ... < qm I For an integer k E N, let [K] denote the set fl)...,k). Define the jth quantile gener- ated by Joint for given j E [m]] to be Euz- and let En.). -E
maaimuu value))
Qa 1.51QR
Qa
DP Q:
median
DP median
JopptExp
Q
DP Q
max /minimmm valun)
(DP minimum value) unbounded max Loy 1.5 DE iqR/
Qi 1.5IQR
outliers
DP outliers Laplace mechanism
Figure 1. Graphical illustration of algorithms for the traditional non-private boxplot (left) and our proposed differentially private boxplot DPBoxplot (right).
including its location, scale, skewness and tails. A more detailed review of the boxplot can be seen in Appendix A.
k)).
= (Eq...... the cumulative distribution function (CDF) of μ and, if exists, let Fr be its probability density function. For the dataset Xn. let e be the corresponding empirical measure, so that F& is then the associated empirical CDF. For x E R. with 11 <
For a given l E Mi (R), let F2 be
2.1. Differential privacy
Next, we introduce differential privacy. First, we say that Y, E Da. is adjacent to X,, if x,, and y, differ in exactly one point. Let An, be the set of pairs of adjacent datasets of size n. Next, denote by Px,, a probability measure which depends on X,, For space S, let (S)) denote the Borel sets of S and let (S) be the set of Borel probability measures over S. Formally, Px. is a map from R" to MI for some d E N. We can now define differential privacy.
< Imm define the following utility function: (xx) = ΣØ [Fo( (all))-Feel FF)()))1)() (a--aaa-- -)-1)),, where Zo -0, Im+11 oc, Qo and qm+1 1. Then Eg is a random vector drawn from the density fax. (x) xx exp(-nó(z)/2ee {z [a, b)""), where Qx, is used to denote the distribution of Eg. given X,.. It was shown by Gillenwater al. (2021) that & is e-differentially private. Furthermore, Lalanne et al. (2023b) showed that this algo- rithm is consistent if v is continuous. If one suspects that v contains atoms, then we recommend that one uses the jittering modification proposed by Lalanne et al. (2023b). We show in Section 4 that, for a large class of distributions, this algorithm has optimal sample complexity for estimat- ing single inner quantile, and therefore, for the scale and location of the boxplot. (Here we are only interested in estimating three quantiles, and so, how sample complexity scales in m in not of particular concern.)
Definition 2.1. Given e > O, the quantity 0 ~ Px. is e-differentially private if
Px,(B) Pr, SE.
sup sup (E
(I)
Here, 0 is a d-dimensional differentially private quantity and c is the privacy budget, where values of which are closer to zero enforce stricter privacy constraints.
The proposed differentially private boxplot makes use of existing differentially private algorithms. Specifically, the Laplace mechanism, and algorithms for computing differ- entially private quantiles. The Laplace mechanism (Dwork al., 2006) is fundamental mechanism for constructing differentially private statistics. Let Z be a standard Laplace random variable. Specifically, for statistic T: Dn, - TR, define its global sensitivity to be sup(x... Y.).A, IT(,.)) T.Y.).. If T has global sensitivity bounded by 1, then T TX, + Z/E is a differentially private quantity. This known as the Laplace mechanism.
The original unbounded algorithm produces a private quantile given a lower bound on the data. We present a slightly modified version, which performs better for ex- treme quantiles. For given quantile q E [1/2, 1] and >> O, let Vo, Vi,... be independent, standard exponential random variables and let 8, > 1. Define 1' inf e N: (8 + a - 1) + V, 2 + Vo Here i' is the smallest integer such that a noisy empirical CDF com- puted at 84 + a 1 greater than a noisy version of q. The quantile estimate generated by the unbounded algorithm is given by: 3/ = B + 1. The intuition is that if noisy version of (3 + 1) is close to noisy version of q,
2.2. Private quantiles
Of course, a private boxplot relies on differentially pri- vate quantiles. The proposed private boxplot relies on
Note fex, is only defined for x E R.' with 31 ... < Ima
3

---

Differentially Private Boxplots
then 8h + a should be close to the nonprivate quantile. If q E (0, 1/2) then, we apply the above procedure to the dataset- -X,- --X ........... -X,], with input parameters 1 1-q+ and a = -b. It follows from (Durfee, 2023) that this algorithm is <-differentially private. In the proposed dif- ferentially private boxplot algorithm, we use unbounded to estimate the minimum and maximum of the dataset. For a measure μ E M, (R). let fp.u = inf (2r R: p S (x)) be the associated pth quantile, min(u) = in: Fx > of and max(u) = i=: (x) 13. We show that if X.. is an independent sample from v. then ز is weakly consis- tent for max(v), and ///n is weakly consistent for min (v), see Lemma B.3. By contrast, we show that when the sup- port of fa is bounded below, JointExp is inconsistent for min(v) when q = 1/n, unless min(v), see Lemma 4. Lastly, we note that instead of exponential noise, one could also use Laplace or Gumbel noise (Durfee, 2023). We found this to make little difference in simulation, and so we only present the version which incorporates exponential noise.
by the estimated extreme quantiles w1/n and vh1. Given that estimated extreme quantiles more variable than the esti- mated inner quantiles, we add buffer Xn to account for this, Specifically, we take the upper whisker equal to the extreme quantile 4/ when t/1 is (An x 100)% smaller than 1.5 times the IQR. An analogous procedure is done for the lower whisker. The role of Xn is to account for the fact that the algorithm more prone to erroneously replacing the IQR- based whisker with extreme quantile. This is because the extreme quantiles are more variable than the inner quantiles. To mitigate this, we introduce X as trust parameter that favors the IQR aallowin it to be replaced only when the extreme quantile is smaller in magnitude by at least (A,, x 100)%. We take An, = n 11/4, Simulation results (Appendix C.2) indicate that the performance of the method is not overly sensitive to the choice of this parameter.
The boxplot includes the observations that lie above and be- low the upper and lower whiskers, respectively. We cannot release such data points under the constraints of differential privacy. Instead, we plot a noisy version of the number of points above ū, denoted o, and below L, denoted oz. These are generated via the Laplace mechanism, where is easy to see that the count of observations above below threshold has global sensitivity 1. Lastly, we attribute less privacy bud- get for computing the outliers, as we deem these values to be of less interest than the box itself. We assign each noisy outlyingness number a privacy budget of e/ e/16. Together, these seven values make up the differentially private boxplot: B B(X,,c) c) B(ū,e) e) = (ōe, E, E1/4, /2,2//// û, ō.). The algorithm, which Algorithm 3, see also, Figure 1. It follows from sequential composition that DPBoxp looo ot is e-differentially private.
3. A differentially private boxplot
We can now introduce the differentially private boxplot. Given lower and upper bounds on the data and b, we first generate the minimum and maximum estimates using the unbounded algorithm, v/ and 1/1 with a privacy budget of 3e/16 16 each. If one does not wish to supply input bounds for the data, one can use the "fully unbounded" version of unbounded (Durfee, 2023). However, in simulation, (see Section 5), we have observed that the procedure is still accurate, even when the input bounds are very loose. Critically, we use the unbounded algorithm because JointExp (and, by consequence, PrivateQuant i le and ApproxQuant ile) is often inconsistent for estimat- ing the aforementioned extreme quantiles, unless the in- put bounds a and match min(v) and max(v), respec- tively, see Lemma 4. Next, we run one instance of ExpntExp with a total privacy budget of e/2 to generate 5//..1//..33/, simultaneously to be the lower box bound, center line and upper box bound, respectively. We then cal- culate the private interquartile range 1QR- 15/4-E1/a- Let & f1/4- 1.5 x IQR, ūn E3/4+ 1.5 x IQR and An > be the buffer parameter. The lower and upper whisker are defined as
call Ro ot,, is summarized in
Note that the time and space complexities of DPBoxp at are given by the maximum of those of the differentially private quantile algorithms unbounded and Joint fointExp Exp. Since the unbounded quantile can be computed in linear time (Durfee, 2023), the overall complexity of DPBoxplos is determined by that of Joint which is Onnlog(() (Gillenwater et al., 2021).
4. Theoretical results
In this section, we derive several results concerning private quantiles and the different elements of the private boxplot. Recall that assume that the dataset X,, consists of independent, identically distributed random variables drawn from population measure v E (R). We first present a lemma which says that JointExp is inconsistent for ex- treme quantiles. We then present an upper bound on the sample complexity of the inner quantiles generated from JointExp After which, we present minimax lower bound for privately estimating a quantile from population measure lying in a general set, which matches the upper
Eyn S Am 2 + l 6i/n > Anlēil + ET,
i
and
ū1 E ` - | û-
1 E < نة - Xm [رة
respectively. To elaborate, the role of the minimum and the maximum of the dataset in traditional boxplot is played
4

---

Differentially Private Boxplots
Algorithm 1 DPBoxplot
0 <<<< M -, we have that
Input: data Xn, Sn,e,ar a, b, An
Pr (15g - - 21) 2 - 2g M -
(Construct the private quantiles²}
e1 +-unbounded(), a, b, 3e 16)
b b-a a
d1/n +unbounded(I/nn 6, 3e/ 16)
Eg EJointExp(q a, b, e/2)
In this case, q = n= then the sample complexity is bounded below by infinity, which implies inconsistency, The proof of Lemma 4.1 can be seen in Appendix B.
(Ensure the box contains the median)
f1/ + min(f1/4,$1/2)
Ea/4 + max(f3/4.E1/p
Before getting to our next results, we introduce a condition on the population distribution. For L,r > 0 and E (0, 1]. let GL.r.g be the set of absolutely continuous measures 1 E (R) such that inf -r fu(()) 2 L > O. Therefore, if the population measure V E 92, then has density which is bounded below by L in neighborhood of size around its gth quantile.
(Construct the whiskers and outlyingness counts)
+ f1/1 10aa-1... 1.5(Ea/1 - E1/1)
à t fa/4 + 1..((63/4 - (1144)
if 1/nn > >nlel + then
ft $1/n
oe +0
else
Condition 1. Given p = (Pi...., Pm) with 0 < P1 <... < Pm S 1 then a S Ey < Ep.. S b and there exists Kr I. 0 such that n G and supre[a,8] (x(x) K.
or - Ei= 1 ffzz <t] + Laplace(O, e/16)
end if
if 1
< û - >alā then
This condition has three requirements. First, we require that the interval [a, b] contains the population quantiles we wish to estimate. Our theoretical and simulation results show that this interval can be chosen loosely, as the error in our estimates does not depend strongly on the size of this interval. Thus, this is not strict requirement. Next, require that for each ps, i E [m]. in neighborhood of size of the p,th quantile of v, the density is bounded away from 0. This requirement is standard in quantile estimation, e.g. (Tzamos & Vaatakis-Gkarggkonn
ū + 11
ou +0
else
ou +
Ei= (2;; > 03 + +TaplaceOO,, s/18)
end
Output: c( (ōe, i, Eyy, E1 Ea/1, uw)
2020; Lalanne et al., 2023a). Lastly, we require that the population density is bounded above everywhere. Requiring the density being bounded above is weak restriction, which is satisfied by many distribution families, such as the Gaussian, Beta and Gamma families.
bound up to logarithmic terms. Lastly, we present a re- sult that says the whiskers and outlyingness numbers are consistent for their population counterparts.
We now define a boxplot rigorously, as function of measure on the set of real numbers, which is convenient mathematically. The non-private hoxplot constructed from the data is taken to be the boxplot computed on the empirical measure of the dataset X,,, denoted by D. For u E (R),,, let (p)(p)
We can now state an upper bound on the sam- ple complexity of the private quantiles generated via JointExp, and by consequence. PrivateQuantile and ApproxQuanti le, see Remark 4.3. For q (91...., (m)) such that 0 < Q1 <... < 4m < 1, define Eqp0 = (Em..)..., x V y (z y) for the maximum (minimum) of x and y.
Es/4.y E1/4.u- Now, letting l1 E1/4, - 1.5 x IQR(v) and $1, = Ea/4,0 1.5 IQR(v), the whiskers are defined as Ey = max(f min(v)) and un = min(u1,,, max(v)). Lastly, we can define or.v = (u((e)) - v(fx- = tvt), oup = 11- 11--F (u,). The "population" " boxplot is the following seven number sum- mary B(u)= = (or,,, St// Ea/1.0: uv; Ou,,).
Next, for æ, E R, we write
Theorem 4.2. Given -00 < < 8 and q (Q1...., such that 0 < 91 <... 4m S 1, if Con- dition 1 holds with = g, then there exists a universal
The next lemma says that JointExp (and, by conse- quence, Privatequantile and ApproxQuant le since these algorithms are equivalent for m quantile) is inconsistent for the minimum of / when we set q = O(1/n) if the input bounds do not exactly match those of the sup- port of the population distribution, and the support of the population distribution is bounded.
constant C > O such that for all 0 < 7 < and 0 < t $ r, it holds that 11E., - Eq,il S with probability 7 pro- vided that
n 2 C 5/2 log(1/7) V m log(m/ctl))
L2L
log (1/7) v log
Kib-a)
Lemma 4.1. For -o < a < b < oc, 0 < 5 1, if there exists M3 > a such that v([X= < M)) = 0, then for any
V m
g.A(1 JALL
t.e
5

---

Differentially Private Boxplots
The proof of Theorem 4.2 relies on a general bound for the exponential mechanism detailed by Ramsay et al. (2024), it can be seen in Appendix B. Theorem 4.2 gives an upper bound on the sample complexity of the quantiles generated by Joi Exp for distributions who satisfy Condition with p being the vector of quantile levels to be estimated. Comparing to existing results, Lalanne et al. (2023a) give a concentration result for JxintExp which yields the same upper bound given by Theorem 4.2, when the support of fo is bounded. Therefore, our bound is essentially a gen- eralization of theirs, though we assume that fu is bounded above. The sample complexity of the median of Tzamos & Vlatakis- Vlatakis-Gkaragkoumii Gkaragkounis (2020), which is a different esti- mator, also matches the upper bound given in Theorem 4.2, under similar assumptions. Lastly, we note that by com- bining our techniques used to prove the upper bound given in Theorem 4.2 with the Appr approxQuantile algorithm of Kaplan et al. (2022), one can obtain logarithmic scaling in m. However, in this context, m = 3, and this is not particularly relevant, thought may be interesting for other applications. In simulation, we observe almost identical per- formance between Approxquant le and JointExp for the purposes of DPBoxplot.
differentially private quantile estimation by R(e, L, Inf Su [T) Eg,0l
Theorem 4,4. For all n 2 1, q E (0, 1). L, > 0 such that rL S sup=so l1y(2) it holds that
C2
Cg
n n= Ω
(2)
1,213
Ltc
samples are required for R(e, L, L,r,g) S t to hold.
Theorem 4.4 gives a lower bound on the sample com- plexity for estimating the gth quantile from a distribution whose density is bounded below by L in neighborhood of size around the qth population quantile. That is, ev- ery differentially privacy quantile estimator requires at least Ω TPP bounded above by t. What is important for this context, is that Theorem 4.4 implies a lower bound on the sample complexity for estimating m quantiles from a distribution whose density is bounded below by L in neighborhoods of size around each of the population quantiles. That is, for all q = (qI,..., 4m), n 2 1, I,, > 0 with r S infzejm) Co., it holds that (2) samples are also required for infy, MMM,M (B=) sup (D) - l1 S L. Apply- ing this lower bound in conjunction with Theorem 4.2 yields that the scale and location of the proposed private boxplot are estimated optimally, up to logarithmic factors. Note that Tzamos& & Vlatakis Vlatakis-Gkarakkoun Gkaragkounis (2020) give simi- lar minimax lower bound on differentially private median estimation. However, their proof does not directly extend to estimating an arbitrary quantile, since it relies on a set of uniform distributions that have the property that the median coincides with the mean. The proof of Theorem 4.4 makes use of the differentially private version of Fano's 's inequality (Acharya et al., 2021), it is deferred to Appendix B.
C. samples in order to have minimax risk Ltc
V
Remark 4.3. We now expand on how Theorem 4.2 applies to PrivateQuantile and ApproxQuantile PrivateQuant l algorithm only generates one quan- tile. So, for PrivateQuantile, we would be applying it m times to estimate m quantiles. Given that all three algo- rithms are the same with m 1, Theorem 4.2 applies to Priv Privatequant ill with m 1. Applying Theorem 4.2 m times with = 1/m-//2 yields the same bound that is given in Theorem 4.2. For ApproxQuant ile, if you inspect the ApproxQuantile algorithm, it is made up of successive applications of Privat ile at each level of a tree, with the input bounds depending on the previous levels of the tree. In that case, you can com- bine our bound for Pr Privatequantile with = 1, I 1/(log(m) + 1) and = 7/m. Then you can ap- ply Lemma 3.2 of Kaplan et al. (2022) (Note their notation uses 33 for and gamma for t) and the result follows im- mediately.
The
Next, we show that the whiskers and the outlyingness num- bers, when appropriately normalized, are weakly consistent for their population counterparts.
Theorem 4.5. For -00 < a < b oc, if Xm + O and Bn + 1 as n + oc, and Condition 1 holds for p (1/4,1/2,3/4 4), then it holds that ē Lg lu. û 2, uv ōz/n 2, or, and 6u/n 4 Ou.
Next, we present a minimax lower bound for estimating single quantile subject to differential privacy. Next, for a set S, let M....n (S) be the set of maps from D, to MM (S) that satisfy (1). Note that MM.e... is just formal way of writ- ing the set of all diffcrentially private mechanisms whose output lies in S. Next, we write T. ~ M1.e.n (R) to denote the set of all univariate differentially private estimators." 3 For
Here Pg denotes convergence in probability. Theorem 4.5 says if the population density is bounded below in neighbor- hoods of each of the population median and the population quartiles, the population density is bounded above every- where, and (a, bj contain the quartiles, then the whiskers and outlyingness numbers will be consistent. To our knowledge. this is the first result concerning extreme, private quantiles. Together, Theorems 4.2 and 4.5 imply that, given a large enough sample size, DPBoxpl ot will correctly represent
0 < q < 1, let (x(x) = 2 (- log x - o (2)m//2// and C = argmax s hy (x). Denote the minimax risk for
'To be clear, given an element of he the associated estimator. Given a dataset X, with empirical measure 2, T2( would he draw from Px.,, or T. (0) ~ Px..
say P., Te could
6

---

Differentially Private Boxplots
location
scale
Skewness
tails
normal distioutionn
0.06
nan pri-private
0.03
PrivateQuantile
0.06
unbounded
0.04
2
JointExp
0.02
0.04
ApproxQuantile
0.02
DPBoxplot
0.00
0.00
0.00
skew distributionn
0.08
0.03
0.04
2-
0.02
0.04
0.02
0.01
0.00
0.00
unitom digtibbution
0.06
0.08
0.02
0.04
0.01
0.00
0.00
10f
10a 10 102
107 10*
10a
10a
10"
Figure Average error in each metric with 95% confidence intervals between the different differentially private boxplots and their corresponding population boxplot (y-axis) with 1 and increasing (x-axis), The DPBoxplo ot algorithm is presented, along with the naive method paired with each of the algorithms Joint ApproxQuant. The different generated distributions represented row-wise, and the diffferent metrics: location, scale, skewness and tails presented column-wise. The non - private line is the distance between the non-private boxplot and its corresponding population boxplot.
unbounded and Pri vat vateQuant ile (line color).
the location, scale, skewness and tail of the underlying dis- tribution. Thus, making it statistically valid for one the private boxplot to describe samples in differentially private exploratory data analysis.
11/2 E1/2,zl (location), JIQR IQR())) (scale), I t un (skewness), (ō noe, + now,yl (tails).
Errors for remaining boxplots are defined analogously.
Data were generated from the five distinct distributions parametrized to have mean and variance normal dis- tribution (normal), skew normal distribution (skew), uni- form distribution (uniform), beta distribution (beta), and empirical distribution of 2019 NY airbnb listing prices (ai (airbnbb)*. We considered values of and and each scenario was simulated 1000 times. (For more details, see Appendix I) Results from beta and aira sirbnb dis- tributions, and those with = 0.5 or = 5 did not add additional insights, so we also defer to Appendix C.I. We also assessed DP3oxplot's ability to compare multiple distributions simultaneously, concluding that DPBoxplot also performs well under this setting. For brevity, these results are deferred to Appendix C.3.
5. Simulations
We now assess the empirical performance of DPBoxplot. We compare DPBoxplot to the "naive private boxplot" and the non-pr non-private sample boxplot. The naive private boxplot is one where single differentially private quantile algorithm is used to generate all quantiles that are used in the boxplot. Using these quantiles, the whiskers and outlyingness counts are then constructed in the same manner as that of Algorithm We consider the following quantile estimation methods: P Privatequant. i le, unbounded, ApproxQuant il and JointExp. For all algorithms, we set 50 and b = 50 and An n -114/1 We ran the same simulations with other values of A,, and found it did not alter the conclusions of the study, see Appendix C.2. For the unbounded algorithm, 8 was set to the default value of 1.001 for both the naive boxplot and DP DP Boxplot.
Figure 2 provides a comprehensive summary of the simula- tion results. Each column of figures corresponds to a distinct boxplot component, while each row pertains to a different generating distribution. The sample size is depicted along the x-axis, while the average error represented on the y-axis. The line color within the figures denotes the method used to generate the boxplot.
We assess the boxplots
the four key metries: scale, location, skewness and tails. We consider the error between each boxplot and the population boxplot. For DPBoxple pollo.. errors in each of the components are quantified as follows:
"These data sampled without replacement.

---

Differentially Private Boxplots
Consistent with Theorems 4.2, 4.4, and 4.5, the error for all components of DPBexplot is converging to zero as increases in all scenarios. Further, we see that the er- ror for DPBoxplot is similar to that of the error for non-private. This means that the sampling error is larger than that of the error attributed to privatization.
set a 0 and b 500. We address two distinct business inquiries.
Inquiry 1: Do discernible patterns emerge in Airbnb listing prices across various boroughs in New York City and differing room types?
The dataset encompasses five distinct boroughs within New York City, namely the Bronx, Brooklyn, Manhattan, Queens, and Staten Island, alongside three offered room types: En- tire Home, Private Room, and Shared Room. We present three visualizations: boxplots of prices by borough, room type, and by borough and room type combinations. These generate 5, 3, and 15 boxplots, respectively, totaling 23.
On the other hand, the naive boxplots do not always ex- hibit the same behavior. In particular, the inconsistency of the whiskers for the naive methods based on JointExpp Approxquant ille, and Privatequantill flected through poor performance in the skew metric for the skew and uni forf distributions. On the other hand, though it does well at estimating the extreme quantiles, the unbounded algorithm worse than the other algorithms for estimating scale and location. We see that DP DoBxloo retains the best of both worlds.
is re-
The differentially private boxplots are displayed in Figure 3. juxtaposed with non-private counterparts. Only looking at the differentially private boxplots, Figure 3 reveals that prices predominantly lie in the bottom end of the range [0,500], with a right skew and heavy right tail observed across all boroughs and rooms, except for in the Bronx, and for shared rooms. The distribution of prices in the Bronx still exhibits right skew, but has light tails. The distribution of prices for shared rooms appears be symmetric, with light tails. Notably, prices appear elevated for Manhattan. As expected, entire homes are priced higher than shared spaces. The right-most plot, which displays prices by both borough and room type, affirms previous observations, except shared rooms in Staten Island and the Bronx. Staten Island and the Bronx exhibits higher variability for shared rooms.
In the setting of normally distributed data at small sam- ple sizes, DPBoxplot does perform worse than the naive methods in the skewness metric. This happens because at small sample sizes, the unbounded algorithm tends to un- derestimate the magnitude of the minimum and maximum of the dataset, while the other algorithms overestimate the magnitude of the minimum and maximum. Nevertheless, we can still conclude that overall, DPBoxplo ot exhibits consistently better behavior than the naive methods.
6. Case study
We now conduct an exploratory data analysis via boxplots, within the framework of differential privacy.
It is natural to compare the patterss observed on the differ- entially private boxplots to those observed in the non-private boxplots. As previously mentioned, Figure 3 juxtaposes the differentially private boxplots with the non-private boxplots. Many conclusions derived from the private visualizations persist in the non-private domain. However, there are sev- eral disparities, which are outlined are as follows: In reality, both the listing prices for shared rooms and properties in the Bronx do have a heavy, right tail. The second disparity occurs in the third plot, where non-private plots does not indicate higher prices and variability for properties in Staten Island and the Bronx in shared rooms. These discrepancies can be explained by small sample sizes and our conserva- e
We consider two business inquiries, each with privacy bud- get of c = 1. Each inquiry consists of several visualizations. The privacy budget for each visualization is proportional to the number of boxplots in the visualization. To elaborate, out of the total budget (e = 1), each visualization (and there- fore, as a result of parallel composition, each boxplot) is assigned a privacy budget equal to the number of boxplots in the visualization, divided by the number of boxplots on all generated visualizations. We chose this allocation so that more budget is allotted to visualizations where the data is partitioned more times. The intuition is that if the data is partitioned more times, then each boxplot in the visualiza- tion has a sample size which is smaller. Code for replicating our visualizations has been made publicly accessible O.
tive choice of privacy budget. For instance, the number of shared room listings in Staten Island is only 9. Overall, the patterns observed are generally consistent between the private and non- non-private boxplots. The principal disparities are attributable to sample size, a factor we encourage practi- tioners to consider when conducting differentially private exploratory analyses.
We analyze a dataset containing Airbnb listing prices and associated metrics within New York City (NYC) in 2019 (Kaggle, 2019). After removing listings priced above 500 US dollars (USD) and requiring minimum nights of stay fewer than 10, this dataset has n = 40738 observations and d 4 explanatory variables of business interest.
Inquiry 2:
Are there observable trends in Airbnb listing prices concerning minimum nights required for reserva- tion and the types of rooms offered?
We only consider listings priced below 500 USD, and so we
We create new categorical variable called minimum nights,
8

---

Shared room Differentially Private Boxplots
private
private
Barough
Bronk
5BM
Manhattan
Bronddyn
8
380
1026
on0g
Brank
Bronkyyn
Staten stand
Brans
Brosdyn
Hant Queins
Stamin stard
Entire horeelagt Pitrate riim
Enaire tameaae Prhate room
Sharel mom
Enere homethpt
Private ralm
Sharel mam
Entre hometapt
Shared romm
Private
Borough
Borough
type
Type
typ
Figure 3. Private and non-private boxplots for inquiry 1. The boxplots display listing prices against borough, room type and room type
separated by horoush in columns 1. and resnectivelv. Private boxnlats are ohtained with a total asgresated hudsct of e = non-private
private
private
non-private
500
Minimum nights
785
47.p111
high
1325
low
403798
-100
high
low
high
low Minimum nights
Entire home/apt Private room
Shared mom
Entire home/apt
Private room
Shared room
Minimum nights
Room
Room type
Figure 4. Private and non-private boxplots for inquiry 2. The boxplots display listing prices against minimum nights and room type separated by minimum nights in columns and 2, respectively. Private boxplots are obtained with a total aggregated budget of c = 1.
in which a listing is assigned "low" if it has less than or equal to three minimum nights, and "high" otherwise. For this inquiry. we generate two visualizations: Boxplots of prices by minimum nights, and prices by combinations of minimum nights and room offered. These visualizations require and 6 boxplots, respectively, totaling 8.
mary visual disparity pertains to the positioning of the lower whiskers on the boxplots. This underscores the recognized challenge associated with differentially private estimation of extreme quantiles. However, this discrepancy does not materially impede the analytical value of findings.
The differentially private boxplots are displayed in Figure 4, juxtaposed with their non-private counterparts. Again, we first analyze the patterns in the differentially private box- plots, and compare to those observed in the private boxplots afterward. The differentially private boxplots indicate the emergence of phenomenon akin to Simpson's 's paradox. Specifically, preliminary examination suggests that listings requiring higher minimum number of nights are priced more steeply than their counterparts with lower minimum requirements. However, this trend disappears when the data divided by room type. Listings for entire rooms exhibit no significant price differential based on minimum night requirement, while private rooms slightly favor lower mini- mum nights in terms of price. In shared rooms the median price does not seem to be significantly different.
7. Discussion
We have demonstrated that differentially private boxplots are a theoretically and practically viable standalone tool for private data analysis. Our work concerns differentially pri- vate data visualization, which, despite its impact potential, is severely underexplored. Though some work has been done in this area, deep investigation into the practical as- pects of differentially private exploratory data analysis is still needed, and promising direction of future research. In particular, large barrier for private exploratory analy- sis is optimal budget allocation for sequential and iterative workflows. Addressing this challenge crucial facilitate real-world adoption of differential privacy in data analysis pipelines.
Code. Official implementation is available at https: httttaab.ccoo/aaaaaaaaa/////gog
A comparative analysis with non-private boxplots reaffirms these observations; we observe relatively consistent pat- terns between the private and non-private boxplots. The pri-

---

Differentially Private Boxplots
Acknowledgements
Budiu, M., Thaker, P., Gopalan, P., Wieder, U. and
Zaharia, M. Overlook: Differentially private
This work was supported by the Natural Sciences and En- gineering Research Council of Canada (NSERC); through grants DGECR-2023-0055
exploratory visualization for big data. Jour-
nal of Privacy and Confidentiality, 12. 7 2022.
and DGECR-2022-04531, re- spectively. We thank the anonymous reviewers and session chair for their valuable comments and suggestions, which helped improve the quality of this work.
ISSN 2575-8527. doi: 10.29012/jpe.779. URL
org/index, php/ http:///cc//artcc//veeee////////
Bun, M., Nissim, K., Stemmer, U., and Vadhan, S. Differen-
tially private release and learning of threshold functions. In 2015 IEEE 56th Annual Symposium on Foundations of
Impact statement
Our proposed methodology inherits the extensive implica- tions, both beneficial and detrimental, of differential privacy. Differential privacy significantly enhances data confidential- ity by introducing noise into datasets, which complicates the ability to link specific data points to individual identities. This greatly enhances the privacy awarded to individuals whose information is contained in such datasets. However, this method is not without its drawbacks. The primary chal- lenge lies in the trade-off between privacy protection and data accuracy. The introduction of noise, while safeguarding privacy, may distort the data, potentially yielding inaccurate insights or conclusions. Such inaccuracies are especially problematic in contexts requiring high precision, such as policy development or clinical research, where exact data is erucial.
Computer Science, pp. 634 649. IEEE, 2015.
Dasgupta, A. and Kosara, Adaptive ppreeeeirr visualization using parallel coordinates. IEEE Transac-- tions on Visualization and Computer Graphics, 17(12): 2241-2248, 201 1. doi: 10. 10.1109/TVG..2011.1
Dasgupta, A., Chen, M., and Kosara, R. Mea- suring privacy and utility in privacy-preserving vi- sualization. Computer Graphics Forum, 32:35-47, 12 2013. ISSN 0167-7055. doi: 10.111 12142. URL /onieeiirrr wiley. com/ doi 111.1...111/11111111 htt.1////f............. 12142.
Dasgupta, A., Kosara, R., and Chen, M. Guess me if you can: A visual uncertainty model for transparent evalu- ation of disclosure risks in peeecc-preserving data vi- sualization. In 2019 IEEE Symposium on Visualiza- tion for Cyber Security (VizSec), pp. 1-10, 2019. doi: 10.1 11t.://iiSee4411.211199.19
References
Acharya, J., Sun, Z., and Zhang, H. Differentially pri- vate Assouad, Fano, and Le Cam. In Feldman, V., Ligett, K., and Sabato, S. (eds.), Proceedings of the 32nd International Conference on Algorithmic Learn- ing Theory, volume 132 of Proceedings of Machine Learning Research, pp. 48-78. PMLR, 16-19 Mar 2021. httptttss://rroceeeeeeee wwwpddiinnnm..l.....mmemm www. mlr.press/ v1
Durfee, D. Unbounded diffcrentially private quantile and maximum estimation. In Oh, A., Neumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 77691-77712. Curran Associates, Inc., 2023.
html.
Dwork, C. Differential privacy: A survey of results. In International conference on theory and applications of models of computation, pp. 1-19. Springer, 2008
Acs, G., Castelluccia, C., and Chen, R. Differentially private histogram publishing through lossy compression. In 2012 IEEE 12th International Conference on Data Mining, pp. 1-10. IEEE, 2012.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Cal- ibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, pp. 265-284, 2006.
Alabi, D., Ben-Eliezer, O., and Chaturvedi, A. Bounded space differentially private quantiles, 2022.
Garrido, G. M., Liu, X., Matthes, E. and Song, D. Lessons learned: Surveying the practicality of differential privacy in the industry. Proceed- ings Privacy Enhancing Technologies. 2023:151- 170, 4 2023. ISSN 2299-0984. doi: 10.56553/ popets-2023-0045. URL https::/petssmmosl hzg/popets//200 http://////pppppteeeee
Asi, H. and Duchi, J. C. Near instance-optimaality in differ- ential privacy. arXiv preprint UrXiv:2005.10630. 2020.
Bhattacharjee, K., Chen, M., and Dasgupta, A. Privacy- preserving data visualization: Reflections on the state of the art and research opportunities. Computer Graphics Forum, 39:675-692 6 2020. ISSN 0167-7055. doi: 10. 1111/cff.1403. URL http::://onineeiiaras wi com /o /ttpo//10.10
php.
Gillenwater, J., Joseph, M., and Kulesza, A. Differentially private quantiles. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Conference on Ma- chine Learning, volume 139 of Proceedings of Machine
10

---

Differentially Private Boxplots
Learning Research, pp. 3713-3722. PMLR, 18-24 Jul 2021.
on Machine Learning, volume 202 of Proceedings of Ma- chine Learning Research, pp. 18399-18418, PMLR, 23- 29 Jul 2023a. URL https: htttttppp/proceedinng .mlr. press / /t/p//22222////// http//aaaanee.aaaaa.m
www.dinnns.........mm.ee.eeee.ee mlr, press/ v139/ 1.399/i1lenwater22a.. html.
Hay, M., Rastogi, V., Miklau, G., and Suciu, D. Boosting the accuracy of differentially private histograms through consistency. Proc. VLDB Endow., 3(1-2):1011-1052, sep 2010. ISSN 2150-8097. doi: 10.14778/1920841. 1920970. URL https://don http////i.o///11111//01 1920641. 920970.
Lalanne, C. S., Gastaud, C., Grislain, N., Garivier, A., and Gribonval, R. Private quantiles estimation in the presence of atoms, 2023b.
Li, C., Hay, M., Rastogi, V., Miklau, G., and McGregor, A. Optimizing linear counting queries under differen- tial privacy. In Proceedings of the twenty-ninth ACM SIGMOD-SIGAR SIDD-SGGTT-SSGRRRT symposium Principles of database systems, Pp. 123 123-134, 2010.
He, X., Raval, N., and Machanavajjhala, A. A demon- stration of visdpt. Proceedings of the VLDB Endow- ment, 1:44 9 2016. ISSN 2150-8097. doi: 10.14778833072633300779) URL https: / /dl.. acm. org/doi/100 14778/ 3007263. 3007229...
Liu, W., Zhang, Y., Yang, H., and Meng, Q. A survey on dif- ferential privacy for medical data analysis. Annals of Data Science, 11(2):733-747, June 2023. ISSN 2198-5812. doi: 10. 10.10077:407455-22-000111 doi wtt.:ooo/.1..10///
Hongde, R., Shuo, W., and Hui, L.. Differential privacy data aggregation optimizing method and application to data visualization. 2014 IEEE Workshop on Electronics, Computer and Applications, pp. 54-58, 2014, doi: 10. SA0p/WECAA2214.6845500
URL http: /xx 023 00475-3.
Nanayakkara, P., Bater, J., He, X., Hullman, J., and Rogers, J. Visualizing privacy-utility trade- offs in differentially private data releases. Proceed- ings on Privacy Enhancing Technologies 2022:601- 618, 4 2022. ISSN 2299-0984. doi: 10.2478/ popets-2022-0053 URL org/popets/2coom -200
Ji, Z., Lipton, Z. C., and Elkan, C. Differential privacy and machine learning: survey and review, 2014.
Kaggle.
New york city airbnb open
2022-0052 .pp.......ppp.
data, 2019.
URL. https://www
kaggle, httggle.commcooo wtt.:/ccccaaaataaea watpon/daatttss//eeo ddtpeaasstts//dmmoo/o/oooooo new-york-city ai wwwbbbbbooooo openn
Panavas, L., Crnovrsanin, T., Adams, L.,, Ullman, J., Sargavad, A., Tory, M., and Dunne, C. Investigating the visual utility of differentially private scatterplots. IEEE Transactions on Visualization and Computer Graphics, pp. 1-16, 2024. ISSN 1077-2626. doi: 10.1 10.1109/VVC. 2023.3292391. URL https: org org/ htt///douuen///ee/ meteeen/11113333
Kaplan, H., Ligett, K., Mansour, Y., Naor, M., and Stemmer, U. Privately learning thresholds: Closing the exponential gap. In Conference on learning theory, pp. 2263-2263 PMLR, 2020.
deeeeplloee : leee.
Kaplan, H., Schnapp. S., and Stemmer, U. Differentially private approximate quantiles. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 10751-10761. PMLR, 17-23 Jul 2022.
Ramsay, K., Jagannath, A., and Chenouri, S. Differentially private multivariate medians, 2024.
Smith, A. Privacy-preserving statistical estimation with optimal convergence rates. In Proceedings of the forty- third annual ACM symposium on Theory of computing, STOC'11, 11. ACM, June 2011. doi: 10. 10.1145/1993636. 1993743. URI. http: / //xxxddooos 1993636. 1993743.
1145/
Kellaris, G. and Papadopoulos, S. Practical differential privacy via grouping and smoothing. Proceedings of the VLDB Endowment, 6(5):301-312, 2013.
Tukey, J. W. et al. Exploratory data analysis, volume 2. Springer, 1977.
Kulkarni, T. Answering range queries under local differen- tial privacy. In Proceedings of the 2019 International Conference on Management of Data, pp. 1832-1834, 2019.
Tzamos, C. and Vlatakis-Gkaragkounis Optimal private median estimation under minimal distributional assump- tions. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 3301-3311, 2020.
Lalanne, C., Garivier, A., and Gribonval, R. Private statisti- cal estimation of many quantiles. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, (eds.), Proceedings of the 40th International Conference
Xu, J., Zhang, Z., Xiao, X., Yang, Y., Yu, G., and Winslett,
M. Differentially private histogram publication. The VLDB journal, 22:797-822. 2013.

---

Differentially Private Boxplots
Zhang, D., Hay, M., Miklau, G., and O' O'conoo, B. Chal- lenges of visualizing differentially private data, 2016.
Zhang. X., Chen, R., Xu, J., Meng, X., and Xie, Y. Towards accurate histogram publication under differential privacy. pp. 587-595. Society for Industrial and Applied Mathe- matics, 4 2014. ISBN 978-1-61197-34442 doi: 10.1 1.9786611973440.68.. URL https://eppbs siam. orc//66//00.1137/1.93300 97111177777811111117744444 58.
Zhou, J., Wang, X., Wong. J. K., Wang, H., Wang, Z., Yang, X., Yan, X., Feng, H., Qu, H., Ying, H., and Chen, W. Dpviscreator: Incorporating pattern constraints privacy- preserving visualizations via differential privacy. IEEE Transactions on Visualization and Computer Graphics, pp. 1-11, 8 2022. ISSN 1077-2626. doi: 10.1109/TVC. 2022.3209391. http:htts:///eeeeeee htg//bccmeet/994449/
ieee.
12

---

Differentially Private Boxplots
A. A review of the boxplot
The boxplot consists of a box with a line drawn through it, with two whiskers emanating from the lower and upper bounds of the box. Specific points are sometimes indicated above or below the whiskers. The central line inside the box marks the median of the dataset. The box itself is constructed from the quartiles, detailing the middle 50% of x,, The lower (upper) whisker is constructed from the larger (smaller) of the minimum (maximum) of X,, and the lower (upper) quartile of X,, minus (plus) 1.5 times the interquartile range of X Lastly, any points in X,, falling outside of the whiskers are added to the plot. See Figure for an example. The boxplot describes various characteristics of X The median line approximates the location of X The box itself approximates the spread or scale of X The skewness of X., can be approximated as follows: A median line placed in the center of the box, along with whiskers that are similar in magnitude, suggests a symmetric distribution. median line placed away from the center of the box or asymmetric whiskers indicates skewness. Additionally, the tails can be assessed by the number of points beyond the whiskers. Many such points signify outliers or heavy tails, highlighting data points that deviate significantly from the rest.
B. Technical proofs
Here for a, b E IR, a b (a A b) denotes the maximum (minimum) of a and b.
Proof of Lemma 4.1. We have that
Sa M E
Pr (En. - -ga 21) 2 Pr (E.. S SM- M1)
dx
men M a
2
So e
n Fo(a)
21
vnl
dx
h a
Before presenting the proof of Theorem 4.2, we first prove general sample complexity bound for quantiles. For t 2 0, (q)...., such that 0 < Q1 <... < Qm < 1, -0 < a < b< < cc, and v E (R)),, define:
m+11
all)=
inf axa, Kam <b, || 12 2t
b0 1- - Fu,))) (u
One may wish to recall that inf 1 = 0o, and so (t) is still defined if {a <.1 < < Im < || - Eq,u || 2 (] = 0.
Lemma B.I. For -0 <a < b < co, if E MM (R) is absolutely continuous such that supxela,b) fu(x) K < co. then there exists universal constants C, > 0 such that for all q = (91...., such that O < h1 < < 9m < 1 and a S En. S Egm. S b, all 2 0 and 0- < 7 < 1, it holds that 115 - Eg,ull S l, with probubility 1 - 7, provided that
n 2 Cm= y (1/7) m logm/calf
V m
log (1/7) v log
g1 (MM1--90 4m (aa())
K(b-a)
(3)
(²)
a(t)
Proof of Lemma B.I. Given that E, is draw from the exponential mechanism, the result follows from an application of Corollary 7 of (Ramsay et al., 2024). Corollary 7 of (Ramsay al., 2024) gives upper bound on the sample complexity of draw from the exponential mechanism, provided the utility function meets certain criteria. In order to apply Corollary 7 of (Ramsay et al.. 2024), we must show that the following function
m+11
v(crv)==- =- Σ [b(1,)) Fo(05-1) (gj - [m) [a, co (1 1 ([21, (a, bJ))
and satisfy three conditions. First, we must show that e'xx,, v/) has a maximum, which is easily seen by definition, o' (xc v) is maximized at Eq.- The second requirement is that ø' (I, u) is K-Lipschitz, which follows by assumption. Lastly, Corollary of (Ramsay et al., 2024) requires that (2, v) is a (L, F) regular function for some L > 0 with VC(F) < co, see Definition E.2. It is easy to see that ø (x, v) is (m, regular function with VC(F) = 1. In order to apply the bound given in Corollary of (Ramsay et al., 2024), we must compute the discrepancy function of o', v, which is given by: o' a'(t) & ('(Suun v)- - SuPp)=-,, Φ (xx v). A straightforward calculation yields that a a'(t) = (t). Applying Corollary
13

---

Differentially Private Boxplots
7 of (Ramsay al., 2024), yields that there exists universal constant C 0 such that for any and 0 5 S 15 Eg,ull & with probability least 1 7, if
n C m (llg(1111))) V m logglog//oee / V m
log (1/7) V log 1kg - A/b Fam (aatt/KK
(b-a)
(t)
a(t)c
Define Z (a S 6) if there a universal constant c > 0 such that a 2 cb (a S cb). Next, using the Lipschitz assumption and the mean value theorem, we have that 15gu, a) A 1b Samill 2 [m A (1 - qmm)] // K, which yields the desired result. 7
We prove Theorem 4.2.
Proof of Theorem 4.2. The proof based on an application of Lemma B.1. All of the conditions of Lemma B.1 are satisfied by assumption, and remains lower bound a. To this end, let kg argina, [m]] [xg Ea.el. Using this notation, for 0 s t t r, the definition of in conjunction with the mean value theorem yields that
m+11
inf a(l) a a<m <... Cam || Eg
---1- Fo(x)) + (x(x--1)
==1
h
inf a<#1 <... <... fvoll2
4j 4n-1 - Fu(to)) + Fa(ry-1))
j=1
hx
inf
Σ
95 qi-1 (x( + Fo (x
a<3; <b, fp
==1
inf a<si<.... <.
4k.
(axk))
2 ttL/ym.
Applying this bound, in conjunction with Lemma B.I, yields the desired result.
Next, we prove Theorem 4.4.
Proof of Theorem 4.4. We apply Corollary 4 of (Acharya et al., 2021), of which simpler version restated below for clarity, For P c M1 (R). let n' inf(n: inf (R) supvep f [T. (D) - (.())ddv" =)}.
Corollary B.2 ((Acharya et al., 2021)). For all e, T > 0 and any P C Mi (R), ler Q = ( .Q.............................. Qm) C C. If all i # j. it holds that [T. (Qi) - (T)) 2 3r, KL(Q,, Q2) < Sn. and TV Q,) S then n = Ω (log m(3 V (7))
In order to apply Corollary B.2, we first define a class of Gaussian measures which lie in GL.ngg Recall that we consider v with densities which satisfy: infzes, fu(x) 2 L. Let Pp.ea = N o²) and let hn denote the associated quantile function. We have that for q S 1/2, it holds that
inf (g)
frn (x) 2 (2mo²2- 1/2
cxp2 cxp
-
lerf (2q (2mo²)- -1/2 exp (-r² (enf -2q-1119) 1))²).
Taking a = Cg/ L gives that
exp,exp inf fPa. (x) exp (-lerf- ((2 1))² 2 L3)3))) =Eh..o
Now, note that
erf 22q 1) -- /V)
14

---

Differentially Private Boxplots
which in turn implies that
inf =0)
f(x) Lexp (- (0) PT.) /VT.
Next, we have that
L/C, exp
(-16-1 (=1022 00) L
- exp (-10- - 2 C
① 22))+/2+x+2' L²/L2 S -log C.
r E Coy (-log - - (q)13/2)/T.
We must then have that rL < Cg (- ( which holds by assumption. Define Fr.r [N(H, C2 2 e RR. We find the values of Y and 5 for FL.r. Consider the values Po. and for i=1 or i O, denote Q P C2, Note that for any quantile q, we have that 1g.40 Eq.0, = |no - /2ll That is, the distance between the quantiles just the difference between the means. For some 0, take any Po, M1 such that Ino Ma1 3r. It follows that (Q,Q Q1) & TT2 /C2 and TV(Qo, Q1) (B(cTT//Cg) S Lr/Cg- Therefore,
applying Corollary B.2 gives that
n = (
(G
C2 L272
Cg LTe
V
Before proceeding with the proof of Theorem 4.5, we first prove that the unbounded algorithm estimates extreme quantiles consistently.
Lemma B.3. For all non-increasing sequences 3n 1 and qn. + 0, and all v E MME),, it holds that
ifinn()) < b, then Va.. f min(v).
i if max(p)) > then S.-0. & max(v).
Proof. First, without loss of generality, take = 0. Next, using the fact that Vo is standard exponential random variable.
Pr (2VV//ne > - 9n) = - (1--
(4)
In addition, letting e, = 1/ log n, the Dvoretzky- Kiefere-ooooeewo inequality yields that
Pr
sup (F)(x) Fx(x)] > cn s 2e 22n/(log n)? 2E
(5)
suffices to show that for all > 0, holds that Pr (181 - max(v)) > z) - 0 as n + co. (A symmetric argument
then implies that also, Pr (18g.. - min(v)] > x) + 0s > 20.) Letting i be the integer such that e- = 3/hh 1, we have that
Pr (1o1- max(v)] > Pr (max(v) 3hhh - 1->1>>1 t) + Pr (0h max(p) > t).
for which we can write
log (max(v) - 1)
1)
Pr (max(v) - 8h - >> t) = Pr k
= =Pr Pr < Rt,1),
log 3,
log (max(v) (v) + +1+10 1) log 3n
Pr (3t - - max(v) > 1) 1)= = Pr
=P
k
= Pr > R.2)
suffices to show that Pr (k Rr,1), Pr (k: Re,2) - n - co. To this end, first, note that if
log (max(v) 1) log (max(v) - < log 8n
log 3,,
15

---

Differentially Private Boxplots
then Pr ((k R1,1) (k U R2,2)= 1. However, have that in is decreasing 1. This immediately implies that for all t 0, there exists no > 1 such that for all flg, have that
log (max(v) +t+
log (max (V) - -t-1) 1. log 3n
log Bn
Next, utilizing (5), the fact that Vo > and the definition of V,, we have that
Ra,
Pr < 14,1= =1
II
Pr (Fo
-) +V2 11-10 9n + 1--n
2Vo/ne)
i=1
R.a
< 1
II
Pr (Fu 1) 2V./nee In -cn) 2e. 2e/e-2n/1000 22n/(log
i=1
Br.1
< 1
II 1=1
(1 - ex-e (-ne(1 9n Co. FF(8 - 1))/2)) + 2e 2n/ plog n)?
1 1++0 2e 2n/glo
(6)
Now, using the fact that (1 + x/n)" 2 1 for all n 2 1 and |x| S we have that
Ra.1
(1 exp (-ne(1 - In - -n - Fo - 1))/2)
1=1
2 exp (-ne(1 In Cn - Fo - 1)))/2) Re.1
2 1 R2,1 exp (-ne(1 In Cn -F, (B 1))/2).
Now, applying the preceding inequality in conjunction with (6) yields that
Pr (k < Re,1) S Ru,1 exp (-ne(1 4n Cn Fo 1))/2) 2e 22ogg)) - 00
as 71 + D0. On the other hand, for the term Pr (A: > R1,2), utilizing (4) and (5), we have that
Ri
Pr > R₂,2)
II Pr (Fu 1)) 2V./ne < - <1-9n/2 e. + 2n/(log n/² + -e-el(1-90)1
Pr ffff.. -1) 2V+,2Vn,,/ne
9n/2 2 cx.) 2e 2e 2n// n)²
+ -ne(1-qu))
$ (1 / + - (8 - -1) 2 0} + 2c 22//(lonn) + me(1 9/)21 + 0,
00.
We prove Theorem 4.5.
Proof of Theorem 4.5. We first prove that whiskers are consistent. Theorem 4.2 implies that é, Pg l1, and Lemma B.3 implies that & Ps min(v). Continuous mapping theorem and the fact that Xn - 0 Do yields that i P, ty. The same argument applies the upper whisker.
For the outlyingness number, first, we have that lor,//n- oæl < lor - ōe/n| + lor,v - og,o == 1 + 11. Next, the properties the Laplace distribution give that Pr (lor,6 - öz/n| suPzeR (x) K, we have that F, is KLLipschitz. It follows that o0t,/nn 0r.0/1| S K16, e, + supzeR (x) Fa(x)) Next, the the whiskers are consistent implies that K K|6p - tyl - 0. The same argument can be made for the upper outlyingness number.
5 2 f) S net Therefore P, Next, using the fact that
inequality yields that suPxer (x) Fx(x) P, 0 and the fact that
16

---

Differentially Private Boxplots
location
scale
skewness
tails
hormal distribution
0.100
non con-private
0.06
PrivateQuentile
0.075
0.4
2-
JointExp
0.04
0.2
ApproxQuandlle
0.025
1-
DPBoxplot
0.000
0.00
skew distribution
0.100
0.06
0.075
0.04
0.2
0.025
0.000
0.6
uniform eiatribution
0.06
3-
0.075
2-
0.04
0.050
0.025
0.2
1-
0.02
0.000
10a
10*
10a
10a
10a
Figure 5. Average error in each metric with 95% confidence intervals between the different differentially private boxplots and their population (oracle) counterparts (y-axis) with c = 0.5 and increasing n (x-axis). The DPBoxplot lot algorithm is presented, along with the naive method paired with each of the algorithms Joint Exp, ApproxQuantile unbounded and PrivateQual color). The different generated distributions are represented row-wise, and the different metrics: location, scalc, skewness and tails are presented column- wise, The nen-private line is distance between non-private boxplot population counterpart.
(line
C. Simulation details and additional results
C.1. Single boxplot estimation
This section presents more details on the simulation study described in Section We simulated data from five distributions, each with mean 0 and variance standard normal distribution (normal), skew normal distribution with scale parameter 20 (skew), uniform distribution with interval [- [-v3, v (un form), normalized and mean-centered version of the beta distribution with
3n (beta), and normalized and mean-centered empirical distribution generated from 2019 NY airbnb listing prices. We considered sample sizes of n E (1000, 3500, 10000, 35000, 100000} and privacy budgets of {0.5, 1, 5, 10}. Each scenario was simulated 1000 times, leading to simulated data vectors X,, For each generated dataset, we computed both the non-private boxplot B(X,)) B and the population boxplot. We also calculated differentially private boxplots B(X B(X,;* e) using each of methods. Figure 5 and Figure are analogous to Figure in the manuscript, except under e 0.5 and with lower values, and increases with higher values, reflecting the trade-off between privacy and accuracy. However, the variation in performance is marginal in most of the cases, and the same conclusions those given in Section 5 hold across both privacy levels. In addition, we present Figures and 8, which give comprehensive summary of the results for DP OBBxplot from this simulation study.
respectively. As anticipated, the performance of all methods decreases
C.2. Parameter tuning
We performed simulations under similar settings as those discussed in Section C.I. We varied X, E (1/2 1/1,1 1), fixing = 1 and estimated differentially private boxplots with all methods. Figure 9 summarizes the results for simulated distributions (column-wise
boxplot metrics (row-wise). Variations in the method and A, and are represented with different line colors and line styles, respectively. We observe that none of the methods are highly sensitive to the chosen parameters, except for skewness and tails. Moreover, Dwwoxplocccm ot was generally the best regardless of X Based on this observation
17

---

Differentially Private Boxplots
location
scale
Skewness
tails
normal distribution
0.08
nan private
0.008
0.04
0.06
PrivateQuantile
unbounded
0.04
JointExp
0.004
0.02
ApproxQuantile
0.02
DPBoxplot
0.00
0.000
skew distributtion
0.08
0.008
0.04
0.06
0.006
2-
0.04
0.004
0.02
0.02
0.002
0.00
0.000
unitom distribuation
0.04
0.006
1
0.002
0.000
10f
10a
10 10 107 10*
10a
10
10
Figure 6. Average error in each metric with 95% confidence intervals between the different differentially private boxplots and their population (oracle) counterparts (y-axis) with = and increasing n (x-axis). The DPBoxplot algorithm is presented, along with the naive method paired with each of the algorithms Joint Exp, Approxquanti unbounded and PrivateQuante itl (line color). The different generated distributions are represented row-wise, and the different metrics: location, scalc, skewness and tails are presented column- wise. The men-private line is distance between non-private boxplot and population counterpart.
and to account for better results in small samples, concluded that X, n
1/4 -1/4
reasonable choice for all methods.
C.3. Multiple boxplot estimation
This section presents extensive simulation study assess the differentially private boxplot's ability to describe, and facilitate comparison of multiple samples. Specifically, we analyze whether the metrics (quantified by distances on location, scale, skewness and tails as in Section 5) between differentially private boxplots across distinct datasets mirror the corresponding pairwise distances observed between their population counterparts. The similitude between two distinct differentially private boxplots is anticipated to align closely with the similitude observed between their respective population counterparts, thereby facilitating analogous visual comparisons and interpretation. For the purpose of quantifying this phenomenon, introduce the concept of relative similitude between two differentially private boxplots follows:
d (B(,,,,)) B(Y m: :)) +1 1- d d(B(vx), +1
à
Here, distance is related to the four metrics previously described. order to empirically validate the consistency of our proposed approach with this behavior, we conducted Monte Carlo simulations by generating datasets (z1, z.. z.). and two vectors m and of size sampling from uniform distributions with interval [-1, and [0.5, 2), respectively. Each ny. Here, t plays the role
vector 2; is size n, for {1, 2, . t} where n; is chosen randomly such that n4 + n2 of the number of treatments in an experiment. We replicated this simulation 1000 times for each combination of / 4, 8 and E {500, 5000, 50000} leading to datasets (X,, X2,
X;) such that X; = s,Z, + m, We performed this simulation generating the initial datasets using mixture of the five distributions described in the previous section such that each distribution generates the same amount vectors on each replica. For each dataset we calculated non-pri non-private boxplots B(x,), B(2))... ..., B(X,), and differentially private boxplots using each the quantile estimation methods and for each
18

---

Differentially Private Boxplots
normal
skew
uniform
airbnb
beta
0.06
non-private
0.04
location
5
0.02
0.01
0.00
0.06
0.05
0.04
0.02
0.01
0.00
1.25
Skownnss
0.75
0.25
0.00
0.04
0.03
talls
0.02
0.01
101
10a
10a
10
10a
10a
10a
107
10
10a
Figure 7. Average error in each metric with 95% confidence intervals between estimated differentially private boxplots and oracle boxplot (y-axis) with (0.5, 5, 10) (line colors) and increasing (x-axis); using DPBoxplot for private bexplot estimation; from all sampled distributions (column-wise) comparing location, scale, skewness and tails (row-wise). In the legend, non con-priiate refers the distance between the non-private boxplot and the population boxplot.
E {0.5, 1,5, 10). We then calculated pair-wise relative boxplot distances for every pair of differentially private boxplots.
Figure 10 and 11 offers a detailed overview of the results obtained from various scenarios considered. Each boxplot within these plots represents the average pairwise distances observed among all differentially private boxplots generated a specific scenario. The r-axis on each plot denotes the sample size (n). Variations hue color correspond to different methods and different privacy budgets (6), respectively. The first and last two plots the first row correspond to relative location and relative scale, respectively. The first and last two plots in the second row correspond relative skewness and relative outliers, respectively. For each pair of relative distance plots, the first and second visualization correspond t 5 and 10, respectively. Figure 11 uses
and Figure 10 shows results with DPBoxplot method.
Figure 10 shows that DPBoxplot performs consistently well across different scenarios. All other methods have poor performance in at least one scenario. In Figure 11 relative distances exhibit a diminishing trend with augmented sample sizes and e, consistent with expectations illustrated by the non-private vate boxplot. A marginal increase in the parameter t leads slight augmentation in the relative distances, attributable the partitioning of data smaller subsets and
19

---

Differentially Private Boxplots
normal
skew
uniform
airbnb
beta
non: private
0.06
PrivateQuentle
location
JointExp
0.04
AeproxQuantile
0.02
0.00
0.06
0.04
0.02
0.00
skowness
1-
0.03
tails
0.02
0.01
10a
10a
10
10a
10a
10a
107
10
10a
Figure 8. Average error in each metric with 95% confidence intervals between estimated diffcrentially private boxplots and cracle box- plots (y-axis) with and increasing (X-axis); using boxplot estimation methods JointExp, ApproxQuantiles unbounded. PrivateQuant 1ee and DPBoxplot (line colors): from all sampled distributions (column-wise) comparing location, scale, skewness and tails (row-wise). In the legend, non-private refers to the distance between the non-private boxplot and the population boxplot.
consequent reduction in sample sizes; however, this impact appears be negligible. Hence, our analysis suggests that our proposed methodology effectively maintains the visual coherence of relative similarities among diverse boxplots during the execution of multiple comparisons.
C.4. Computational requirements
All simulations conducted single CPU and did not require significant computational resources. The execution time for the simulations presented in the paper did not exceed 24 hours.
D. Differentially private quantiles
Here, we include a longer review of the differentially private quantile estimation literature. We focus on the existing statistical results for such estimators, statistical results for private quantiles is one of our main contributions, It
20

---

Differentially Private Boxplots
normal
skew
uniform
airbnb
beta
0.07
method
PrivateQuantle
0.06
0.05
JointExp
ApproxQuantile
location
0.04
0.03
-214
0.02
0.08
0.06
scale
0.04
0.02
3.0
2.0
1.0
0.040
0.035
0.030
talis
0.015
0.010
0.005
0.000
10
10
10"
10a
10a
10a
10a
10*
10a
10a
101
10"
10'
10'
10
B
n
0
Figure 9. Average eтror in each metric with 95% confidence intervals between estimated differentially private boxplots (y-axis) and oracle boxplots with e and increasing (x-axis); using various methods (color), with varying A., (line style): from sampled distributions (column-wise comparing location, scale, skewness and tails (row-wise).
also important to mention that range queries can be used to compute quantiles (Bun et al., 2015; Kulkarni, 2019; Kaplan et al., 2020), however, currently, these algorithms may not be very practical, so we do not cover a full review of those. First, Smith (2011) introduced Pri Privatqquantill le based on the empirical CDF and the exponential mechanism, and
21

---

Differentially Private Boxplots
t=5
t 10
t= 10
Aspoonuaatiis Urboephet bostas
10-1
10a
10
20-1
10
20-1
10-1
Figure Average pair-wise wise relative boxplot distances (y-axis) between multiple sample boxplots in of relative location, scale, skewness and outliers, with using different boxplot estimations (color), (500, 5000, 50000) (x-axis) and (columns). Legend non-prin prattete vavt is
{5, 10}
relative similitude non-private boxplots.
107
10F
FAT STRNGC
0.0
30-1
1271
12-1
10
101
0.0
30
10
3002
5029
30003
5200
Figure 11. Average pair-wise wise relative boxplot distances (y-axis) between multiple private boxplots in terms of relative location, scale, skewness outliers, under varying conditions {0.5, 5, 103 (color), (500, 5000, 50000) (x-axis); using DPBoxplot quantile estimation and E (5, 10) (columns). Legend non non-private is the relative similitude between the non-private boxplots.
present finite sample accuracy guarantee, under the assumption that the population distribution is close to the normal distribution. An extension of this algorithm Exp, which can be used estimate multiple quantiles (Gillenwater
22

---

Differentially Private Boxplots
al., 2021). Later, Lalanne et al. (2023b) and Lalanne al. (2023a) considered the statistical properties of Joi Joint Lalanne al. (2023a) show various concentration results, assuming that the population density has bounded support and is positive in neighbourhood of the quantiles being estimated. Lalanne et al. (2023b) show that JointExp is consistent when the population distribution is continuous, and provide a modified algorithm which can be consistent for population distributions with atoms. This algorithm could also be used to generate the box in the boxplot, if atoms are suspected. Earlier, Asi Duchi (2020) provided an instance optimal algorithm for the median, based on the inverse sensitivity mechanism. We do not consider this algorithm here because it was shown by Lalanne et al. (2023b) that the algorithm is very similar to Privatequantia le. Similarly, a multiple quantile version based on the inverse sensitivity mechanism is similar Joint (Lalanne et al., 2023b). Tzamos & Mlttaki-GGkaragkeee private median estimation, which could be used for private quantile estimation, however, their algorithm takes n' time, which may be slow in practice, so we did not consider it here. However, we see no reason it would perform poorly to generate the median line in the box. Recently, (Alabi et al., 2022) present bounded space quantile algorithm, with some concentration bounds that condition on the dataset at hand, and require the sample space to be finite. They also present some statistical guarantees under the assumption of normality. On a related note, some general works imply that no differentially private quantile estimate can have finite sample complexity without making distributional assumptions, .egg (Bun et al., 2015). Recently, Durfee (2023) present the unbounded algorithm for quantile estimation, which is meant to estimate extreme quantiles well. They do not provide statistical guarantees. Recently, Kaplan et al. (2022) introduce clever algorithm for estimating multiple quantiles from existing quantile algorithm, where the statistical error has minimal dependence on the number of quantiles. We call this algorithm paired with PrivateQuant ile the ApproxQuantile. We build on this literature by providing some new statistical results concerning Joint PrivateQuant ile, ApproxQuant ile and unbounded. Specifically, we show consistency of the unbounded algorithm under general distributional assumptions, lower bound on differentiall private quantile estimation for large class of distributions, and that JointExp, Privatequant lle, and ApproxQuantile provide minimax optimal, single quantile estimates. We also show that Joint PrivateQuant le, and ApproxQuant i lle are inconsistent for extreme quantiles.
(2020) also consider
E. Auxiliary results
Lemma E.1. For all n 2 1, a,c E R, we have that n 2 alog + e if 2 2(a log + +c) Va.
Proof. First, note that ((n) = n - a logn- - c is increasing for n 2 a. Now, for n 2 a we can use the fact that log x 2 z/2 for
get h(n) whenever n 2 2a log a + +c).
Let 3 denote the space of Borel functions from Rd to [0, 1]. For a family of functions, S B define pseudometric on M1 (RR),, d (n, v) = supye.5 [ gd(p= v)), where μ4, E M,(RR.
Definition E.2 (RRasaay et al., 2024)). We say that (xx, v) is (K, 3 --reullar if there exists a class of functions c S such that (xx,,) -) is K K-Lipschitz with respect to the & --pseudometric uniformly in x, i... for all μ, v M1
sup apl 14) ol1, v) S kd
23


Reviews:
[{"review_id": "UoS2tjA2iV", "reviewer": "Reviewer_kohb", "summary": "This paper introduces a differentially private algorithm for creating boxplots. The method specializes in the specific quantiles required for a boxplot (median, quartiles, and extremes for whiskers) rather than treating them as a generic sequence of quantiles, as previous differentially private algorithms have done. \n\nThe authors propose combining two algorithms: JointExp for estimating inner quantiles (with a new sample complexity analysis) and the “unbounded” quantile estimator from Durfee (2023) for skewness and tails (whiskers), providing consistency results for the extreme values, which they claim is lacking in prior DP quantile algorithms. They also modify the non-private boxplot by reporting the noisy count of outliers instead of plotting them. The authors claim their approach achieves performance similar to non-private methods and outperforms naive private baselines in experiments, including on Airbnb listings data.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "Thank you for your careful review!\n\nWe are happy to cite the papers on medians and range estimation. \n\n**Weaknesses:**\n\n1.\tDP data visualization poses unique challenges that are not fully addressed by the current literature on DP statistics. For instance, traditional DP statistics focus on numerical accuracy and error bounds, but they do not explore how analysts perceive noisy visualizations. In our paper, in simulation, we consider this by using error metrics based on visuals, and in the case study, where we evaluate what the plots actually look like.  \n2.\tThis is a good point, we can add a discussion of this literature. In general, unbounded is very practical, easy to implement and runs in linear time, so this was our original motivation . In addition, it is also weakly consistent for the extreme quantiles. We are happy to add an overview of the relationship between ApproxQuantile and JointExp to the appendix. In short, ApproxQuantile applies JointExp with $m=1$ repeatedly. We explain how Theorem 4.2 applies to ApproxQuantile in our response to Reviewer VKVL below.\n3.\tWe removed these listings from a data analysis perspective – listings over 500$ a night are idiosyncratic. We only analyze DPBoxplot here to demonstrate its capabilities and see if private exploratory analysis is feasible. The purpose of this section is not to compare the algorithms. \n4.\tIn unreported simulations, we tried Laplace, and the performance was comparable. \n5.\tWe can add the complexities. \n\n**Questions for the Authors**\n\n1.\tWe observe this in simulation, where the bounds are very loose, and the procedure is still accurate. The sample complexity of the unbounded algorithm for extreme quantiles is unknown.\n2.\tWe made this choice based on heuristics, thinking as data analysts. We felt that in practice, it was most important to get the box correct, and so more budget should be allocated to it. The whiskers are more important than the number of outliers, but less than the box. We give the option to change this in our code, depending on the practitioners’ needs, but this would be our recommendation or default parameters. \n3.\tSee comment 2 in the weaknesses section.\n4.\tThis is an interesting question. We have noted that there is a modified algorithm that works for discrete distributions, this was investigated by Lalanne. 2023b. As for the other question, concentrated around the median is fine, but absolutely no density is not fine. When there is no density, this means that we will never sample a point at the quantile, and it cannot be estimated well via empirical quantiles, which are based on sampled points. In that case, we would have to use something other than the empirical distribution or CDF to estimate the quantile, such as a parametric model.  \n5.\tSee the comment below to Reviewer VKVL below in point 1, where if we apply our methods to ApproxQuantile we get poly-logarithmic dependence on $m$. Observe though that these bounds are all stated up to constants, so, while $\\log m +1$ is smaller than $m$, the difference in constants between ApproxQuantile and JointExp may counteract this. \n6.\tWe answer this at the end of Section 6. See the text “These discrepancies...” In terms of remedies, given that the sample size was only 9, there is not much that can be done.", "claims_and_evidence": "- Theorems 4.2 and 4.3 introduce upper and lower bounds for sample complexity of JointExp (proofs are in the appendix) provided that the density is lower bounded in a neighborhoods of the 0.25, 0.5, 0.75 quantiles. This is also supported by Figure 2 that shows estimation improvement of these quantiles with larger sample sizes. \n\n- Theorem 4.4 shows the unbounded algorithm estimator for extreme values is consistent. This is also observed in Figure 2, confirming that their algorithm “retains the best of both worlds”. \n\n- The authors suggest data visualization is underdeveloped in the DP literature; it would be more accurate to state that many DP statistical aggregation techniques can be directly applied to visualization tasks. However, the authors do point out that the specific requirements of common visualizations, like boxplots, have not always been directly addressed with custom algorithms.", "methods_and_evaluation_criteria": "The authors use parallel composition to combine two existing DP quantile algorithms into one that works well for inner quantiles and extreme values. They provide mathematical analysis that justify their claims. \n\nThey evaluate their method by measuring the error to the real distribution statistics. They compare with previous algorithm for different sample complexities (starting at 1000 samples).  This evaluation is performed on simulated data across different types of distribution providing insights across different scenarios. While their evaluation is thorough enough to guide practitioners, realistic evaluation is not comprehensive (only on the AirBnB dataset) and shows that particular settings, e.g. with small sample sizes, might have inaccurate results.", "theoretical_claims": "Theoretical claims cite previous work and all proofs are provided. The results look intuitive to me but I did not check the proofs in the appendix.", "experimental_designs_or_analyses": "Results on simulated data report 95% confidence intervals calculated over 1000 trials for each setting. I inspected the code and it contains all the relevant functions for simulations and plotting.", "relation_to_broader_scientific_literature": "This paper builds upon the literature on differentially private quantile estimation (PrivateQuantile (Smith, 2011) , ApproxQuantile (Kaplan et al. 2022)., JointExp (Gillenwater et al. 2021), and unbounded (Durfee 2023)). These works have focused on efficiently estimating multiple quantiles simultaneously; this paper distinguishes itself by focusing specifically on the quantile set required for a standard boxplot (median, quartiles, and extremes for whiskers).\n\nWhile the unbounded quantile mechanism is used here for estimating the extremes needed for the whiskers, it is worth noting that a separate body of literature exists on differentially private range estimation, such as [1].\n\n[1] Kaplan, H., Ligett, K., Mansour, Y., Naor, M., & Stemmer, U. (2020, July). Privately learning thresholds: Closing the exponential gap. In Conference on learning theory (pp. 2263-2285). PMLR.", "essential_references_not_discussed": "In addition to [1] above, it might be worth citing recent work on DP median estimation (e.g. [2]), and why not using these algorithms, since they're already aggregating several mechanisms. \n\n\n[2] Beimel, A., Moran, S., Nissim, K., & Stemmer, U. (2019, June). Private center points and learning of halfspaces. In Conference on Learning Theory (pp. 269-282). PMLR.", "other_strengths_and_weaknesses": "**Strengths**\n\n1. **Novelty**. The paper's focus on the specific quantiles necessary for boxplots, rather than arbitrary quantiles, which is a novel application and contribution for data visualization. \n\n2. **Theoretical Contributions**:\n- The paper provides a consistency analysis for extreme quantiles, proving the consistency of the unbounded estimator for whiskers and outliers (Lemma C.3).\n- It presents matching (up to logarithmic factors) upper and lower bounds for the sample complexity of JointExp, ApproxQuantile, and PrivateQuantile for inner quantiles under general distributional assumptions (Theorem 4.2 and Theorem 4.3), relaxing previous assumptions of bounded support. The lower bound is novel.\n\n3. **Empirical Evaluation**: The experiments suggest comparable performance to non-private boxplots provided large sample sizes and improvements over naive DP approaches. The application to Airbnb data provides a real-world context.\n\n4. The paper is clearly written, and contributes to the field of differentially private statistics.\n\n**Weaknesses**\n1. Clarity of Novelty Regarding DP Data Visualization: The claim that data visualization is underdeveloped in DP is questionable, as it can be seen as a subset of DP statistics. \n2. Alternative algorithm selection: The use of the unbounded algorithm for estimating the minimum and maximum (for whiskers) could be better justified. For example,  discussing the literature on private range estimation could make the paper stronger. Similarly, the relationship between JointExp and ApproxQuantile results needs clearer explanation, in particular because the authors claim several times that all the results from JointExp directly apply to ApproxQuantiles.  \n3. Experimental Detail Omission: It is not clear to me why the authors removed Airbnb listings above $500. This simplifies the problem for all algorithms, yet, only DP-Boxplot performance is shown in the main body. \n4. Comparison to Laplace/Gumbel Noise: The authors mention that using Laplace or Gumbel noise made little difference (referencing Durfee (2023)). However, a brief discussion of why exponential noise was chosen, possibly referencing top-K private algorithms results, would strengthen the justification. I think this might be because of the small number of items that this choice does not matter. \n5. Complexity Reporting: While the authors mention the time and space complexities are the maximum of the underlying algorithms, explicitly stating these complexities would improve clarity and make the paper self-contained.", "other_comments_or_suggestions": "- The y-axis labels on the plots show the distribution name instead of the error metric.,\n- The paper is missing the code reference in line 403. I assume this is for anonymity reasons.", "questions_for_authors": "1.  Regarding the statement, \"Given lower and upper bounds on the data a and b... the procedure is still accurate, even when the input bounds are very loose,\" could you elaborate on the implications of very loose bounds for the performance (e.g., noise level, utility) of the unbounded estimator?\n2. Can the authors discuss the selection of budget allocation on Algorithm 1? The authors assign a small privacy budget to outliers, as they \"deem these values to be of less interest than the box itself\". However, a very noisy count could change conclusions drawn from a plot, particularly with small sample sizes. \n3. Throughout the paper, it is stated that results hold for JointExp and consequently for ApproxQuantile. Could you provide a more explicit explanation of why this implication holds?\n4. Theorems 4.2 and 4.3 require sufficient distribution mass around q=0.25 and q=0.75. For distributions concentrated around the median, or discrete distributions this might not hold. Do you have suggestions for improving estimation for these quantiles in such (potentially pathological) cases?\n5. Regarding Theorem's 4.2 suboptimal dependency on $m$,  authors state it is not relevant since m=3. However, $3/\\log(3) \\approx 6$ which can be significant in private estimation. Is there a way to match the log(m) bound?\n6. The private estimates for \"room type by borough\" in the Airbnb data show considerable errors. Can you comment on the potential reasons for this and whether any adjustments could mitigate these errors?", "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": "", "extra_scores": {}}, {"review_id": "huHdsiQj4w", "reviewer": "Reviewer_oHSp", "summary": "The paper proposes a new private data visualization in the form of differentially private (DP) boxplots. DP boxplots accomplish this by utilizing three differential privacy mechanisms to privatize the various components of the boxplots – JointExp is used to combute the median and inner quantiles, the unbounded mechanism is used for the whiskers and the Laplace mechanism is used to report outlier counts. The proposed boxplot is benchmarked against the non-private boxplot as the baseline and DP boxplots, where each component is privatized by one of the following DP mechanisms: PrivateQuantile, unbounded, JointExp, ApproxQuantile. The results demonstrate that the proposed private boxplot outperforms all of the other DP boxplot variants on all the statistics (location, scale, skewness and tails).\n\n## Update after rebuttal:\nAfter looking through the other reviews and rebuttals, I concur with the other reviewers that the algorithmic novelty is the primary limitation of this work. Hence, I am staying with my initial score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "Thank you for your careful review. \n\n**Gaps and unexplained notions:**\n\n1.\tWe use weak consistency, otherwise known as convergence in probability. We are happy to clarify this in the paper. This means that if $X_n$ converges in probability to $X$ then for all $t>0$, $Pr(|X_n-X|>t)\\to 0$ as $n\\to\\infty$. This is different from convergence in expectation, otherwise known as $L_1$ convergence. \n2.\tWe made this choice based on heuristics, thinking as data analysts. We felt that in practice, it was most important to get the box correct, and so more budget should be allocated to it. The whiskers are more important than the number of outliers, but less than the box. We give the option to change this in our code, depending on the practitioners’ needs, but this would be our recommendation or default parameters. \n3.\tThe justification for $\\lambda_n$ is as follows: The extreme quantiles are more variable, i.e., estimated less accurately than the inner quantiles. Therefore, without $\\lambda_n$, the algorithm is more likely to mistakenly replace the IQR whisker with the extreme whisker. We want to account for this by placing more “trust” on the IQR whisker. Therefore, we add a buffer $\\lambda_n$, and instead of replacing the IQR whisker when the extreme quantile is smaller in magnitude, we replace it when it is smaller by at least $\\lambda_n$. We can elaborate more in the paper if accepted. \n\n**Other Comments Or Suggestions:**\n\n1.\tWe can remove these. \n2.\tNoted, thank you.\n3.\tHere, we are trying to emphasize that Condition 1 holds, with the $p$ in Condition 1 being the $q$ we are referring to in the \ntheorem. \n4.\tThank you, we can add a mix of markers.\n5.\tTheorem 4.2 is the upper bound and Theorem 4.3 is the lower bound. Theorem 4.2 gives an upper bound on the sample complexity of JointExp. Theorem 4.3 gives a lower bound on the sample complexity of any DP estimator for estimating quantiles. The lower bound says that we need at least $n=\\Omega…$ samples for any DP estimator to have the risk function less than or equal to $t$.  \n6.\tShould be Algorithm 1, sorry about that. \n\n**Questions:**\n\n1.\t$\\nu$ is the measure, or distribution, which generates the sample of observations. \n2.\tThey are defined there. In words, they are the probability that a random draw from $\\nu$ falls below the theoretical lower whisker, and above the theoretical upper whisker, respectively. \n3.\tTheorem 4.3 is concerned with DP mechanisms in general, yes. Theorem 4.3 gives a lower bound on the sample complexity of any DP estimator for estimating quantiles. The lower bound says that we need at least $n=\\Omega…$ samples for any DP estimator to have the risk function less than or equal to $t$. Since the upper bound given in Theorem 4.2 for a specific estimator matches the lower bound in Theorem 4.3, we get that the rate is optimal, and no DP estimator can do better. \n4.\tYes, this is true. To the second question, when we talk about visualizations, we mean one subfigure. For example, in Figure 3, we have three subfigures with 5,3 and 15 boxplots. Therefore, we will assign more budgets to the subfigure that has more boxplots. We can clarify this in the paper if accepted. \n5.\tThis is a good question. Yes, we have considered this, but it is a difficult question that we felt was out of the scope of this work. This is the subject of our next investigation.", "claims_and_evidence": "The primary claim made is that the proposed DPBoxplot is the best way to create a differentially private boxplot visualization. This claim is furthered in the form of theoretical results that demonstrate that the extreme quantile and outlier estimates are weakly consistent, and the inner quantiles are estimated with optimal sample complexity. These are somewhat backed up by the results on simulation where the DPBoxplot estimates approach the true values of the various statistical measures with more data points ($n$).", "methods_and_evaluation_criteria": "In the absence of a dedicated mechanism to privatize boxplots, the authors have devised reasonable benchmarks, where each of the components of the boxplot is privatized with established DP mechanisms. The non-private boxplot is used as a baseline too.\n\nEvaluation is conducted over the estimated location, scale, skewness and tails of the various boxplots. These are logical criteria as they are the key components of a boxplot; a small error on all these measures is desirable and desirable in any DP boxplot.", "theoretical_claims": "I did not check the proofs of the theoretical claims made in this paper. However, they appear to have been included in the supplementary material.", "experimental_designs_or_analyses": "Benchmarking is accomplished with the non-private boxplot as the baseline and DP versions of boxplots, wherein the quantiles for each boxplot was privatized by one of several established DP mechanisms. The performance was measured in terms of the average error in the estimates of location, scale, skewness and tails. This analysis on two vales of the privacy budget ($\\epsilon$) bear out the claim that DPBoxplot is the most effective way of creating a differentially private box plot. In addition to these analyses, a case study on the Airbnb dataset was included to evaluate the utility of DPBoxplot on real data and its potential limitations.", "relation_to_broader_scientific_literature": "Differential privacy is a growing area of research and data visualization is a key component of most practical applications of machine learning. Consequently, if research is to be conducted on private data without formal privacy releases, private data visualizations are an important area of research.", "essential_references_not_discussed": "None that I can think of.", "other_strengths_and_weaknesses": "This paper is largely well-written and contributes novel theoretical results. While there is not much by way of innovation in how the boxplot statistics are estimated privately, the amalgamation of the various DP mechanisms to create a boxplot is in itself a recognizable contribution. I also appreciate the use of Figure 1 as an effective summary of the proposed method and a case study on real data to study the practical utility of the proposed approach.\n\nIn addition to this, the description of the DPBoxplot in Section 3 is easy to understand. The discussion of the results in Figure 2 is also comprehensive with the authors acknowledging the lower accuracy of the DPBoxplot estimates at small sample sizes.\n\nHowever, there are several gaps and unexplained notions used in the paper. Specifically,\n\n1.\tWhat notion of consistency is being used when stating that the inner quantile estimates are consistent? I presume it is the notion of convergence in expectation at large sample sizes but this is not apparent.\n2.\tWhat motivated the choice of privacy budget split between the various steps in Algorithm 1?\n3.\tWhy is the parameter $\\lambda_n$ required? A clearer justification or demonstration of its utility would be helpful.", "other_comments_or_suggestions": "1.\tIn Section 1, the references in the early part of the second paragraph do not appear to be relevant to the paper; the references should ideally be restricted to data visualization tools.\n2.\tIn the last line on the left side of page 2, ‘sough’ should be emended to ‘seek’.\n3.\tThe variable $q$ could be removed form Theorem 4.2, as $p = q$.\n4.\tUsing a mix of markers and colors in the figures could help distinguish the results for the various algorithms. As it stands, it is difficult to make out some of the lines because they overlap.\n5.\tTheorems 4.2 and 4.3 appear to be making very similar points. Is Theorem 4.2 simply a step towards arriving at Theorem 4.3, which shows that the inner quantile estimates are consistent.\n6.\t“Algorithm 3” is mentioned in Section 5 but I am unable to find it in the paper.", "questions_for_authors": "1.\tOn line 170, what does $\\nu$ refer to?\n2.\tOn line 245, what do $o_{\\ell,\\nu}$ and $o_{u,\\nu}$ refer to?\n3.\tTheorem 4.3 states a minimax bound on the minimax risk, but the infimum appears to be taken over all DP mechanisms. Doesn’t this mean that the result proves the existence of the a DP mechanism with optimal sample complexity, rather than the optimal sample complexity of the selected mechanism?\n4.\tIn Section 6, the authors state that each visualization is assigned the same privacy budget due to parallel composition. Is this because the selected attribute for each visualization is independent of the rest?\n    \n     a.\tThe paper states that “each visualization is assigned a privacy budget equal to the number of boxplots in the visualization, divided by the number of boxplots on all generated visualizations.” This is difficult to parse. What is the difference between the “visualizations” and “generated visualizations”?\n5.\tHow would DPBoxplots be used in practice? Wouldn’t the repeated visualization of the dataset lead to privacy leakage unless a much stricter privacy budget is used? This may limit its actual utility in practice as typical data exploration entails multiple data visualizations.", "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": "", "extra_scores": {}}, {"review_id": "opy4KIkMa6", "reviewer": "Reviewer_VKVL", "summary": "This paper constructs an algorithm for (pure) differentially private box plots by combining two somewhat recent works on private multiple quantiles (for the box), private extreme quantiles (whiskers), and Laplace noise (# outliers). Its theoretical contributions are a few further results about algorithms from these works: a simple lower bound for applying non-extreme private quantiles algorithms to extreme quantiles (Lemma 4.1), a sample complexity upper bound for private multiple quantiles algorithms (Theorem 4.2), a lower bound for a private quantiles (Theorem 4.3), and an asymptotic consistency guarantee for private extreme quantiles (Theorem 4.4) Finally, it shows experimentally that the resulting algorithm, DPBoxPlot, largely outperforms naive approaches based on one quantile algorithm.\n\n## update after rebuttal\nAfter reading the author responses, I'm keeping my score at weak reject. The presented work is a nicely packaged result for a plausible real-world use case, but the algorithmic novelty is IMO too low -- I'm just not that excited by finding a problem that has several pieces and then locating a tool in the literature for each piece. I think the bar for ICML should be higher than that. But I acknowledge that's subjective, so if other reviewers are excited about it, accepting the paper is not bad.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "Thank you for your careful review! We think most of your concern comes from a miscommunication on our part, see point 2 in the following theoretical claims.\n\n**Theoretical Claims:**\n\n1. The PrivateQuantile algorithm only generates one quantile. So, for PrivateQuantile, we would be applying it $m$ times to estimate $m$ quantiles. Given that all three algorithms are the same with $m=1$, Theorem 4.2 applies to PrivateQuantile with $m=1$. Applying Theorem 4.2 $m$ times with $t=t/m^{1/2}$ results in the same bound (actually a better one in terms of the dependence on m) than is given in Theorem 4.2.  For ApproxQuantile, if you inspect the ApproxQuantile algorithm, it comes from successive applications of PrivateQuantile at each level of the tree, with the input bounds depending on the previous levels of the tree. In that case, you can combine our bound for PrivateQuantile with $m=1$, $t=t/(log m+1)$ and $\\gamma=\\gamma/m$. Then you can apply Lemma 3.2 of https://arxiv.org/pdf/2110.05429 (Note their notation uses $\\beta$ for $\\gamma$ and $\\gamma$ for $t$) and it follows immediately. Here, you also get a slightly better bound in terms of the dependence on $m$, but here $m = 3$ and so this doesn’t matter too much, especially when we remember that these bounds are stated only up to universal constants which are unknown. We are happy to add a discussion in the appendix about this, so that it is clearer to the reader. We can also add corollaries of Theorem 4.2, if that is helpful. \n\n2. We have accidentally miscommunicated that a version of Theorem 4.2 exists in the literature for ApproxQuantile with a better dependence on $m$, which is not true. By the sentence “Lastly, we note that the upper bound given in Theorem 4.2 has suboptimal scaling in $m$, the ApproxQuantile algorithm of Kaplan et al. (2022) obtains logarithmic scaling in $m$.” we mean to say that combining our bound with ApproxQuantile results in an improved scaling in $m$. We are just trying to acknowledge that, by combining our bound with their results, we could improve the result in terms of the dependence on $m$, not that there is an identical result in the literature with a better dependence on $m$. We can clarify this in the text. Regarding choosing JoinExp over ApproxQuantile, we observed in simulation that the performance of ApproxQuantile and JointExp was virtually identical, see Figure 2, Figure 5, and Figure 6. This is also easy to see intuitively, where the tree-based solution of ApproxQuantile is not so beneficial if we only end up having a two-level tree. In the end, we went with JointExp because it is easier to understand and implement. The computational complexity is also the same for both algorithms $O(n log(n) + n)$.  We have also made both choices available in the released code, so the user can decide.\n\n**Relation To Broader Scientific Literature:**\n\nWe want to highlight that there is little literature on private visualization, as it is tough to quantify the performance of the algorithms in a meaningful way for a data analyst. For instance, no version of a private boxplot had existed, even though DP is not new, and we believe this is because evaluating the performance is challenging. Therefore, one of the main novelties of our work is studying a new direction. For example, the case study is not just a proof of concept, as it sometimes is in other papers. Here, it shows what exactly happens to a boxplot visually in a real data analysis, at different levels of privacy. We are also evaluating if private visualization is even feasible. Therefore, as a first investigation, it makes sense to consider the natural approach in a rigorous way. Furthermore, the most basic approach is the naïve boxplot, which we prove is not a good approach. \n\n**Other Strengths And Weaknesses:**\n\nWe agree the algorithmic novelty is low, but the main contribution of our work is providing a statistically valid boxplot that is also verified feasible in a practical setting. Having this tool is essential for many data analysts if they want to do a private data analysis in practice. We respectfully disagree with your comments about the theoretical results. \n-\tFirst, Theorem 4.2 is relevant - we have accidentally miscommunicated that a version of Theorem 4.2 exists in the literature for ApproxQuantile with a better dependence on $m$, which is not true. See the response in “Theoretical Considerations” point 2 above.\n-\tWe respectfully disagree with this statement: “weak consistency is to me kind of a \"valid, but not that helpful\" result for extreme quantiles.” This theorem, in combination with the inconsistency of the other algorithms, refutes the naïve boxplot and justifies the proposed boxplot theoretically. \n\n**Minor Comments:** 1 and 3 are typos, thank you. For 2, this is standard notation in probability theory. The 1 represents the space of probability measures and comes from the fact that taking the measure of the whole space gives you back 1.", "claims_and_evidence": "(See other boxes.)", "methods_and_evaluation_criteria": "Sure.", "theoretical_claims": "1) The text before Theorem 4.2 claims that an upper bound for JointExp implies upper bounds for PrivateQuantile and ApproxQuantile. Why is this? It is clear for the single-quantile case of Lemma 4.1, since the three algorithms become identical, but that isn't true for multiple quantiles. The proof of Theorem 4.2 uses a result, Lemma C.1, that assumes that the vector of estimated quantiles is \"a draw from the exponential mechanism\" (Appendix Line ~632), but that only holds for JointExp, while the other algorithms are compositions of the exponential mechanism.\n\n2) The text after Theorem 4.2 notes that ApproxQuantile has a utility guarantees with better dependence on $m$. Is that guarantee worse than Theorem 4.2 in another way? If not, why not just use ApproxQuantile instead of JointExp? My understanding from the ApproxQuantile paper is that it's never worse than JointExp, is significantly better for large $m$ (not the setting here, admittedly) and is faster.", "experimental_designs_or_analyses": "I don't see any obvious issues.", "relation_to_broader_scientific_literature": "The paper's key contributions are a bit unusual. Its core algorithm combines existing algorithms in a straightforward way -- if you're aware of those algorithms, this approach is probably one of the first things you'd try. That's a valid contribution, but the primary novelty comes from 1) actually doing the experiments to compare the various plausible methods, and 2) the new results about the existing methods.", "essential_references_not_discussed": "None come to mind.", "other_strengths_and_weaknesses": "Overall, I think the paper's primary strength is that it reasonably answers the question of how to do (pure) DP boxplots. To the best of my knowledge, that answer has not explicitly appeared in the literature. I appreciate that contribution, because boxplots are a basic statistical object, and it's easy to see a practitioner wanting a DP version. The algorithmic answer makes sense, and the experiments are good support.\n\nThe paper's primary weakness is that the answer is a straightforward combination of existing work. A boxplot consists of inner and extreme quantiles and outliers (or their counts), and the presented solution combines previous work for each of these. That makes the algorithmic novelty low. The theoretical results help a bit, but one might not really be relevant for DPBoxplot (see #2 in \"Theoretical Claims\"), Theorem 4.3's main contribution is combining the private Fano's inequality from ASZ21 with the Gaussian approach from TV21, and, subjectively, weak consistency is to me kind of a \"valid, but not that helpful\" result for extreme quantiles.\n\nThis leads me to recommend weak reject. I think the paper contributes something genuine, but I think it's too much a combination of existing work and minor improvements on results about them.", "other_comments_or_suggestions": "Some minor stuff:\n\n1)  The notation around the data distribution looks inconsistent. Sometimes it is denoted $\\mu$ (start of the exposition of JointExp ) and other times it is $\\upsilon$ (end of the exposition of JointExp and most other places). It seems like this should just be $\\upsilon$.\n\n2) What is the subscript $1$ in $\\mathcal{M}_1(\\mathbb{R})$ accomplishing?\n\n3) Line 369 in the experiments says that \"[Figure 2's] line style corresponds to the privacy budget $\\epsilon$\", but $\\epsilon$ appears to be fixed to 1 everywhere.", "questions_for_authors": "(See numbered questions above.)", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Although the algorithmic novelty of this paper is somewhat low, it nevertheless offers a thorough, clear, and and convincing argument for the authors' proposed method for generating differentially private boxplots. The method appears to behave nicely across a range of experiments, and the theoretical results, though not revolutionary, underline the algorithmic choices. The authors provide code, and any practitioners in need of private boxplots would likely benefit from the work.

The authors are encouraged to use the additional page allowed in the final version to address reviewer comments; for example, they can clarify the relationship to the literature on range estimation, more clearly explain the role of $\lambda_n$, and perhaps give more intuition around Theorems 4.2 and 4.3, which were confusing to several reviewers.
Decision: Accept (poster)