Private Isotonic Regression
Authors: Badih Ghazi
Pritish Kamath
Ravi Kumar
Pasin Manurangsi
Venue: NeurIPS 2022 Accept (2022)
Keywords: isotonic regression
differential privacy
posets

Abstract: In this paper, we consider the problem of differentially private (DP) algorithms for isotonic regression.  For the most general problem of isotonic regression over a partially ordered set (poset)  $\mathcal{X}$ and for any Lipschitz loss function, we obtain a pure-DP algorithm that, given $n$ input points, has an expected excess empirical risk of roughly $\mathrm{width}(\mathcal{X}) \cdot \log|\mathcal{X}| / n$, where $\mathrm{width}(\mathcal{X})$ is the width of the poset.  In contrast, we also obtain a near-matching lower bound of roughly $(\mathrm{width}(\mathcal{X}) + \log |\mathcal{X}|) / n$, that holds even for approximate-DP algorithms. Moreover, we show that the above bounds are essentially the best that can be obtained without utilizing any further structure of the poset.
In the special case of a totally ordered set and for $\ell_1$ and $\ell_2^2$ losses, our algorithm can be implemented in near-linear running time; we also provide extensions of this algorithm to the problem of private isotonic regression with additional structural constraints on the output function.

Private Isotonic Regression
Badih Ghazi
Pritish Kamath
Ravi Kumar
Pasin Manurangsi
Google Research Mountain View, CA, US
badihghazi com, pritish@alum.. mit edu, ravi www.kk530lmm..mmmmm com, pasinogoogle. com
Abstract
In this paper, consider the problem of differentially private (DP) algorithms for isotonic regression. For the most general problem of isotonic regression over partially ordered set (poset) X' and for any Lipschitz loss function, we obtain a pure-DP algorithm that, given n input points. has an expected excess empirical risk of roughly width(Xt)) log | where (idth(X')) is the width of the poset. In contrast, we also obtain a near- hear-matching lower bound of roughly (Wid + log (x())/n, /n, that holds even for approximate-DD algorithms. Moreover, we show that the above bounds are essentially the best that can be obtained without utilizing any further structure of the poset. In the special case of totally ordered set and for & and f losses, our algorithm can be implemented in near-linear running time; we also provide extensions of this algorithm to the problem of private isotonic regression with additional structural constraints on the output function.
Introduction
Isotonic regression is a basic primitive in statistics and machine learning, which has been studied at least since the 1950s [4, 9]: see also the textbooks on the topic [5, 38]. It has seen applications in numerous fields including medicine [31, 39] where the expression of antigen is modeled monotone function of the DNA index and WBC count, and education [19], where isotonic regression was used predict college GPA using high school GPA and standardized test scores. Isotonic gression is also arguably the most common non-parametric method for calibrating machine learning models [51], including modern neural networks [23].
In this paper, we study isotonic regression with a differential privacy (DP) constraint on the output model. DP [17, 16] is highly popular notion of privacy for algorithms and machine learning primitives, and has seen increased adoption due to its powerful guarantees and properties [37, 43]. Despite the plethora of work DP statistics and machine learning (see Section 5 for related work), ours is, to the best of our knowledge, the first to study DP isotonic regression.
In fact, we consider the most general version of the isotonic regression problem. We first set up some notation to describe our results. Let (X' $) be any partially ordered set (poset). function f: X + [0, 1] is monotone if and only if [(x) S [(x') (cc')) for all S x'. For brevity, we use F(X,)) to denote the set of all monotone functions from X' to Y) throughout, we consider C [0, 1].
Let [n]] denote {l....,n) nn. Given an input dataset D (121,))..... (In, vn)} } E (X' x [0, 1))", let the empirical risk of function f X 1] be L)f:D) - Eie( ((f(z;), v.)., where
: [0,1] x [0, 1] + a loss function.
We study private isotonic regression in the basic machine learning framework of empirical risk minimization. Specifically, the goal of the isotonic regression problem, given dataset D (I.. E (X' x [0. 1))", is to find a monotone function f X - [0, that
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

minimizes D). The excess empirical risk of a function f is defined as L(f:D) - D) where f == argmm ((g:
1.1 Our Results
General Posets. Our first contribution is give nearly tight upper and lower bounds for any poset, based on its width, as stated below (see Section 4 for a formal definition.)
Theorem (Upper Bound for General Poset). Let X be any finite poset and let E be an L-Lipschitz loss function. For any E (0, 11, there is an E-DP algorithm for isotonic regression for & with expected excess empirical risk most O (L-iddth(X)) -log [X (X1-((1)gg((e)) 5m
Theorem 2 (Lower Bound for General Poset; Informal). For any E (0. and any å < 0.01 (x), any (c, DDDP algorithm for isotonic regression for a "nice" loss function i must have expected excess empirical risk S2 width(
While our upper and lower bounds do not exactly match because of the multiplication-v--adiiii of log X we show in Section 4.3 that there are posets for which each bound in tight. In other words, this gap cannot be closed for generic posets.
Totally Ordered Sets. The above upper and lower bounds immediately translate to the case of totally ordered sets, by plugging in (idth(X') 1. More importantly, give efficient algorithms in this case, which runs in time (n log XI) for general loss function f, and in nearly linear Ö(n log (x time for the widely-studies lz- and fi-losses'.
Theorem 3. For all finite totally ordered sets X, T--Lipschitz loss functions f, and e E (0, 1), there 6-DP algorithm for isotonic regression for &. with expected excess empirical risk O L-(log (x)))((+oog((mm)) (en)) The running time of this algorithm is Ó(n² + (1) in general and can be improved Ö(n for & and Eg losses.
We are not aware of any prior work on private isotonic regression. A simple baseline algorithm for this problem would be to use the exponential mechanism over the set of all monotone functions taking values a discretized set, to choose one with small loss. We show in Appendix A that this achieves an excess empirical risk of O(L / widdtt((X) log (/l/En), which is quadratically worse than the bound in Theorem 1. Moreover, even in the case of totally ordered set, it is unclear how to implement such a mechanism efficiently.
We demonstrate the flexibility of our techniques by showing that it can be extended to variants of isotonic regression where, in addition to monotonicity, we also require f to satisfy additional prop- erties. For example, we may want f to be Ly-Lipchitz for some specified Ly > O. Other constraints we can handle include k-piecewise constant, l- k-piecewise linear, convexity, and concavity. For each of these constraints, we devise algorithm that yields essentially the same error compared to the unconstrained case and still runs in polynomial time.
Theorem 4. For all finite totally ordered sets X, T.-Lipschitz loss functions l, and E (0, 1), there an e-DP algorithm for k-piecewise constant, k-piecewise linear, Lipchitz, convex, or concave isotonic regression for with expected excess empirical risk Ô ( [Lo(log x1) The running time of this algorithm (n) (1)(1).
ER
Organization. We next provide necessary background on DP. In Section we prove our results for totally ordered sets (including Theorem 3). We then move on to discuss general posets in Sec- tion 4. Section 5 contains additional related work. Finally, we conclude with some discussion in Section 6. Due to space constraints, we omit some proofs from the main body; these can be found the Appendix.
Recall that the lo-ss is Es v') (y- 2 and the fossoss is 41 v') ly ='1-

---

2 Background on Differential Privacy
Two datasets D = {((11, v1)..... ..... (Ins Bo)} and neighboring, denoted D ~ D', if there is an index i E [n] such that (zz, M3) w/) for all j E [n]] \ {i}. We recall the formal definition of differential privacy [18, 16]:
{(11) .f..... (4) are said to be
Definition 5 (Differential Privacy (DP) [18, 16]) Let >> and 6 E [0, 11. A randomized algorithm M : X + y is (e, diffferrrettlll private ((E, 6)-D) if, for all D D' and all (measurable)
outcomes S _ V. we have that Pr[M(D) S S e Pr(M(D') E S] +
We denote (e, D)-DP as s-DP (aka pure-DP), The case when å > 0 is referred to as approximate-Di We will use the following composition theorems throughout our proofs.
Lemma 6. (s, DD satisfies the following:
mechanisms Mi...., Mr are such that M; satisfies (Et, 6,) DD) then the composed mechanism
Basic Composition:
(D)......M.(())) satisfies (E, Ei. 5, 5:)-DP. This holds even under adaptive composition, where each M, can depend on the outputs of MM.....M;-I
Parallel Composition [33]: If mechanism M satisfies (E, D)- then for any partition of Dj U...U. Dr, the composed mechanism given as (..Di),..,,MIDD satisfies (c, 8)- DP.
Exponential Mechanism. The exponential mechanism solves the basic task of selection in data analysis: given dataset D Z and set A of options, it outputs the (approximately) best option, where "best" is defined by scoring function A x z" + R. The e-DP exponential mecha- nism [34] the randomized mechanism M z - A given by
VDEZ", A Pr(M(D) = al & exp (-2.. D)).
where A, == SUP maXxEA [s D) D')l is the sensitivity of the scoring function.
Lemma' 7 ([34)), For M being the D-DP exponential mechanism, it holds for all D E Z" that
Lls(M(D), D)J < minae s(a, D) + 24 log (A).
Lower Bound for Privatizing Vectors. Lower bounds for DP algorithms that can output binary vector that is close (say, in the Hamming distance) the input are well-known.
Lemma 8 (c.g., [32]). Let E, 0.m E N, let the imput domain be {0, 13"h and let two vectors
z,z' E {0, 1 t be neighbors if and only if | z' llo < Then, for any (e, 8)DP algorithm M 10, + {0, 13"", we have (0,1) M(z) z 2|o 2 - m 0.5 (1 (1-
It is also simple to extend the lower bound for the case where the vector is not binary, stated below. We defer the full proof to Appendix B.
Lemma 9. Let D, m be any positive integer such that D 2 2, let the input domain be [D]m and let two vectors z, z' E [D]m be neighbors if and only [|z z llo < 1. Then, for any (In(D/2), 0.25)- DP algorithm M D + [D]m we have that Ez_[p!'' [[] z z|lu 2 2(m).
Group Differential Privacy. For any neighboring relation ~e, we write ~ as neighboring rela- tion where D D' iff there is a sequence D = Do.... D D' for some k' < k such that D;-1 D, for all E [K'].
Fact 10 (e.g.. [41]). Let > 0,5 2 and N. Suppose that M an (D algorithm for the -DP for the neighboring relation ~ik-
neighhoring relation Then M is (ke, ="11 5) --DDP
3 DP Isotonic Regression over Total Orders
We first focus on the "'oeeddmenniioal"" case where X' is totally ordered; for convenience, we assume that = [m]] where the order the natural order on integers. We first present an efficient algorithm for the this case and then a matching lower bound.

---

3.1 An Efficient Algorithm
To describe our algorithm, it will be more convenient to use the unnormalized version of the empir- ical risk, which we define as (J; == ((..))D (()())
We now provide high-level overview of our algorithm. Any monotone function f [m] - [0, 1] contains a (not necessarily unique) threshold a E {0] [m] such that f(a) 2 1/2 for all a > a and f(a) < 1/2 for all S a. Our algorithm works by first choosing this threshold in private manner using the exponential mechanism. The choice a partitions [m]] into [m] := {a E [mm] and [m] Sa = {a E im] a S a). The algorithm recurses these two parts to find functions f> [m]>a + [1/2, 1] and fs [m]Sn + [0, 1/2), which are then glued to obtain the final function.
a}
In particular, the algorithm proceeds in stages, where in stage i, the algorithm starts with par- tition of (m] into 2' intervals (Pu, i (O....,2 2¹ 1},. and the algorithm eventually outputs a 1)/2"] for all x E P... This partition further refined for stage t + by choosing a threshold as, in Pst and partitioning P.t into p and PS In the final stage, the function ʃ is chosen to be the constant i/2 over P.,--1- Note that the algorithm may stop at T = O₂ (log because the Lipschitzness of ensures that assigning each partition the constant i/2 cannot increase the error by more than L/2" S (L(n/)).
monotone function f such that f(z) E [i/2",
i,t
We already have mentioned above that each a;, has to be chosen in private manner. However, let the scoring function directly be the unnormalized empirical risk, then its sensitivity remains as large as L. even at a large stage L. This is undesirable because the error from each run of the exponential mechanism can be large as O log m) but there as many 2 runs in stage Adding these error terms up would result a far larger total error than desired.
To circumvent this, we observe that while the sensitivity can still be large, they are mostly "ineffec- tive" because the function range is now restricted to only an interval length 1/2'. Indeed, we may use the following "clipped" version of the loss function which has low sensitivity of L/2 instead.
Definition 11 (Clipped Loss Function). For range [T, 0] C [0, 1]. let f(r.0] [T. 0] x [0, 1] -
R be given as (1r.0) (0. y) == E(D. y) m (ly', 9). Similar to above, we also define 1 D): E(DN)D (f( y:).
Observe that range(e(r.0) C [0, L (0 - +) since l is L-Lipschitz. In other words, the sensitivity of Cabo (f: is only L- (0 T). Algorithm contains a full description.
Proof of Theorem 3. Before proceeding to prove the algorithm's privacy and utility guarantees, we note that the output f is indeed monotone since for every x' < that gets separated when we partition Pt. into
we must have x' E Pa and x E P24+10+1-
Privacy Analysis. Since the exponential mechanism is e'DP and the dataset is partitioned with the exponential mechanism being applied only to each partition once, the parallel composition prop- erty (Lemma 6) implies that the entire subroutine for each is eDDP Thus, by basic composition (Lemma 6), it follows that Algorithm 1 is e-D (since
e'T).
for all t E (O....,T-- 1} and i f0, (0.,,...,,2), Utility Analysis. Since the sensitivity of score;,(()) is at most L/2', we have from Lemma 7, that
< so <0(4 2 < O
L L. log m
E scorer.(aa.)) min scores
(1)
aEP...
El 2
Let h4. denote argminne.UPP...// (1+)))))))))))))))))))) Laba Di.e) (with ties broken arbitrarily). Then, let Gz,t denote the largest element in Pa,, such that h (ūs,) I (i+1/22) 1/2 namely, ãs is the optimal threshold when restricted to D Under this notation, we have that
(a min s(ore
aeP..
z scores,((a..)) - ((,,,))

---

Algorithm DP Isotonic Regression for Totally Ordered Sets.
Input: X' = [m]] dataset D = {(11, vi)..... :.... (Ins Un)), DP parameter e.
Output: Monotone function f [m]] - [0, 1].
T - [log(en)]
e' s/T Po.0 - [m]
for t = -....., - do
for = O,....
Di, t- (5z 1 |] P.,) {Set of all input points whose æ belongs to P.t.)
(Notation: Define 5 = {(r,)) E Dug x S a and D similarly
[Notation: Define P {ar E Pa x a) and P, similarly
>> Choose threshold aie E {0} U Pst. using D'DDP exponential mechanism with scoring function
score;,((a) ==
min fEF ba (
Cake 2t 1u (f:
min GE I (64.5) (DD
Cabs (?2) D2??)
(S2;
(Note: score;,)(a) has sensitivity at most L/2..
b Pri,11 6- P,t Sa.. and P2441,411 f- P,, p>ai.
Let f [m] [0, 1] be given f(x) = i/22--1 for all x P,r-1 and all i E [27).
return f
(6//2 (b24444 D24441) + Cabs (6/22, (122) (h2541 (atpb/ass-.i::::::..... D2st1,41))
Cabs
2//2 11/2//244)/2 (ha, Dia))
Cabs
(h2. + Ca Ch (12141,141 D2411.41) Cave (hi,3 Dz,e).
(2)
Finally, notice that
= Ca (f: Cab - (
(3)
With all the ingredients ready, we may now bound the expected (unnormalized) excess risk:
Cabs (f:D)
Eosiezr-1 Labs (ab
< Engiegt-1 (0 L.1 + 11
= O(L/E) + Ca (h
Labs
O(L/e) Caba Do.o)
Σ 1e[T-1]
(Cabe D21,) + (h244 D2042,) (ha, D Dr. 051e2t-1
Taking the expectation on both sides and using (1) and (2) yields
El (f: < O(L/E) + Cabe Cabe Do.o) + Σ cetr il
O
L-log e.22
osieat-1
O(L/e) Cabe + O 0 Cabe(f (f;)(())))) D) + O
Lologm
[olog [.log (1+ (ong))
Dividing both sides by yields the desired claim.

---

Running Time. To obtain a bound on the running time for general loss functions, we need to make a slight modification to the algorithm: we will additionally only restrict the range of fi, f2 to multiples of 1 1/2"-1, We remark that this does not affect the utility since anyway we always take the final output whose values are multiples of 1/2"-1.
Given any dataset D (111,,1)......... y1)...., (In, vn)} where σ1 < ... < In. the prefix isotonic re- gression algorithm to compute, for each i [n]] the optimal loss in isotonic regression on (I1, 31).... (Ti, wi). Straightforward dynamic programming solves this in O(n v) time, where denote the number of possible values allowed in the function.
Now, for each i, t. we may run the above algorithm with D = Di,e and the allowed values are all multiples of 1/27-1 in (2t ++0.3]; this gives us min hEF(P, * Cabs (+) ( (
for all a E Pie in time O(DD,,r 2 + |Ptel). Analogously, we can also compute Cabs
//:11/1/1: D2()) for all a E P.t in similar time. Thus, we can compute (()or, in time O(IDs,1 -
min HEF(P I (1P " " - (S2:
and then sample accordingly.
We can further speed up the algorithm by observing that the score remains constant for all [ci, 13).). Hence, we may first sample an interval among 2)) [2), [In= and then sample Oug uniformly from that interval. This entire process can be done in O (DDed 2T + m) time. In total, the running time of the algorithm is thus
), [Tn, m)
T-12'-1 ΣΣ
T-1 O(n2 + llogmm S OOn2log + n m)..).
O(DDaal 2T + +og m) S
Σ
t=
Near-Linear Time Algorithms for L1,, l2 Losses. We now describe faster algorithms for the 4 and lo-lsss functions, thereby proving the last part of Theorem 3. The key observation is that for convex loss functions, the restricted optimal is simple: we just have to "clip" the optimal function to be in the range [T, 0). Below clip denotes the function y min max(r, y}
Observation 12. Let be any convex loss function, D any dataset, f E argmin C(f: and T S. any real numbers such that T, 0 y. Define f Sehpped (1) == clip|n (f (x)). Then, we must have S'hipped( (x) E argunin D).
Proof. Consider any f E F(X,) F( Let X² (resp. X'5) denote the set of all x E X such that (x) > 8 (resp. (z) T). Consider the following operations:
For each x E x², change f(x) to O.
For each x E x change f(x) T.
Let f(x) (x) for all x E X (X> UX
At the end, we end up with f(x) fcipped(()) (x). Each of the first two changes does not in-
crease the loss L(f: otherwise, due to convexity, changing f*)) to f(z) would have de-
crease the objective function. Finally, the last operation does not decrease the loss; otherwise,
may replace this section of f with the values in f instead. Thus, can conclude that (c) E argmin
D).
Li
We will now show how to compute the scores in Algorithm I simultancously for all a (for fixed t, in nearly linear time. To do this, recall the prefix isotonic regression problem from earlier. For this problem, Stout [42] gave an O(n)-time algorithm for f2-loss and an O(n log n)-timme al- gorithm for llss (both the unrestricted value case). Furthermore, after the ith iteration, the al- gorithm also keeps a succinct representation sope of the optimal solution in the form of an array (11, U1. ( (4k, Uk, 4.). which denotes fzz uy for all æ E [Ia,, Tiz41). )) and é, indicates the loss Cabs up until Zi,.1. not including.
We can extend the above algorithm to prefix clipped isotonic regression problem, which we define in the same manner as above except that we restrict the function range to be [T. f] for some given T 0. Using Observation 12, is not hard to extend the above algorithm to work in this case.
Lemma 13. There is an (n log n) -tiee algorithm for 22-and prerffi clipped isotonic regression.

---

Proof. We first precompute (+ (())=E {TT and = ((0,z,) for all i E [n]. We then run the aforementioned algorithm from [42]. At each iteration i, use binary search to find the largest index j. such that v/-- that the optimal solution of the clipped version is simply the same as the unrestricted version except that we need change the function values before 2,, to and after 35 to The loss of this clipped optimal can be written as Eg. - L, (j- + (c) co (jo)), which can be computed in ((1) time given that we have already precomputed c,, cp. The running time of the entire algorithm is thus the same as that of [42] together with the binary search time; the latter totals to On log n).
and the largest index je such that Vj < 0. Observation 12 implies
Our fast algorithm for computing (scorcL,(a))DEP, first runs the above algorithm with T
Caba 1+1 (f1: (f1; ( 2+0.5 and D = Da,i this gives us min AEFFP, " T at for all a E Pat in time O( log Di,el + P..l). Analogously, we can also compute min hET(PP (0to,, sDpD gabs الي (f2: (()) for all a E Pi. in a similar time. Thus, we can compute (score,,(a))aEP, in time O(D log Da.ll + (Pr,)), and sample accordingly. Using the same observation as the general loss function case, this can be sped up further to O((Dr, Da.el + log m) time. In total, the running time of the algorithm is thus
2e, A = 2
T-12-1
O( Da,el + log m) S
O(n log + 2' log I O(n(log² n + m)). 7
t=
3.2 A Nearly Matching Lower Bound
We show that the excess empirical risk guarantee in Theorem tight, even for approximate-DD algorithms with sufficiently small 5, under mild assumption about the loss function stated below.
Definition 14 (Distance- Based Loss Function). For R 2 0, loss function is said to be R-distance- based if there exist g : [0. 1] - R., such that Ely. 3/) = g( y - y'l) where g is a non-decreasing function with g(0) = 0 and g (1/2) R.
We remark that standard loss functions, including f or E losso, are all ((1) ((()--istannce-asse
Our lower bound is stated below. It is proved via packing argument [25] in similar manner as lower bound for properly PAC learning threshold functions [10]. This not a coincidence: indeed, when restrict the range of our function to {0, 1}, the problem becomes exactly (the empirical version of) properly learning threshold functions. As a result, the same technique can be used to prove lower bound in our setting as well.
Theorem 15. For all 0 < 5 < 0.1 -e - 1)/m, any (e, 8)DD algorithm for isotonic regres- sion over [m] for any R-distance-bass loss function must have expected excess empirical risk logm
Ω R min En
Proof. Suppose for the sake of contradiction that there exists an (E, 6)-D algorithm M for iso- tonic regression with an R-distance-bar loss function l with expected excess empirical risk 0.01- (R- [R-min/ {1, log(0.lm) }). Let k := [0.1 log (0.
We may assume that n 2 2k: as the ((R) lower bound for the case n = 2k can easily be adapted for an 2 R) lower bound for the case < 2k as well.
We will use the standard packing argument [25]. For each j [m 1]. create dataset D, that contains is copies of (j, 0). k copies of (j + 1, 1) and n - 2k copies of (1, 0). Finally, let Dm. denote the dataset that contains copies of (m, 0) and
k copies of (1, 0). Let V, denote the set of all f E F(mm), [0, 1]) such that D): < Rk/n. The utility guarantee of M implies that
Pr(M(D;) E V3J 2 0.5.
Furthermore, it is not hard to see that Vi...., ., Vm are disjoint. In particular, for any function f F(mm), [0, 1]), let xy be the largest element x E [m] for which f(x) 1/2; if no such æ exists (i.e., f(0)= > 1/2), let xy = O. For any 2,, we have L,f:D,) 2 ke(f + 1), > &or g(11)) >
7

---

Rk/n. Similarly, for any j >> 2/. we have Lf) (((() 0) 901/2)(12))))) 2 Rk/n This implies that f can only belong v. claimed.
Therefore, we have that
1 2 Ejelm Pr(M(Dm) VV}]
Ejelml 200 (Pr(M E eVj]
5 g(anter1))
(Fact 10)
c--1
Eje(m
20 (0.5 0.1)
>
1,
contradiction.
3.3 Extensions
We now discuss several variants of the isotonic regression problem that places certain additional constraints on the function that we seek, as listed below.
X-Piecewise Constant: must be step function that consists of most k pieces.
k-Piecewise Linear: f must be a piecewise linear function with at most & pieces.
Lipschitz Regression: f must be L.y-Lipschitz for some specified T.g O. Convex/Concave: f must be convex/concave.
We devise general meta algorithm that, with small tweak in each case, works for all of these constraints to yield Theorem 4. At a high-level, our algorithm similar to Algorithm I, except that, in addition to using exponential mechanism pick the threshold ai also pick certain auxiliary information that is then passed onto the next stage, For example, in the k-piecewise constant setting, the algorithm in fact picks also the number of pieces the left of ag and that to the right of it. These are then passed on to the next stage. The algorithm stops when the number pieces become one, and then simply use the exponential mechanism find the constant value on this subdomain.
The full description of the algorithm and the corresponding proof are deferred to Appendix C.
DP Isotonic Regression over General Posets
We now provide an algorithm and lower bounds for the case of general discrete posets. We first recall basic quantities about posets. An anti-chain of poset (X, S) is set of elements such that no two distinct elements are comparable, whereas a chain is set of elements such that every pair of elements comparable. The width of a poset (X, Σ), denoted by width(X''). is defined as the maximum size among all anti-chains in the poset. The height of (X, S), denoted by height (X), defined as the maximum size among all chains in the poset. Dilworth's 's theorem and Mirsky's theorem give the following relation between chains anti-chains:
Lemma 16 (Dilworth's 's and Mirsky's 's theorems [12, 36)). A poset with width w can be partitioned into chains. poset with height h can be partitioned into h anti-chains.
4.1 An Algorithm
Our algorithm for general posets similar to that of totally ordered set presented in the previ- ous section. The only difference is that, instead of attempting to pick single maximal point such that (a) S T as the previous case, there could now be many such maximal a's. In- deed, we need to use the exponential mechanism to pick all such a's. Since these are all maxi- mal, they must be incomparable; therefore, they form an anti-chain. Since there can be as many as width((() anti-chains in total, this means that the enror from the exponential mechanism O (log widdthh)()) /e") Owwitth(X)) log |X//s), leading to the multiplicative increase of width(X') in the total error. This completes our proof sketch for Theorem
4.2 Lower Bounds
To prove lower bound of 9 (w) we observe that the values of the function in any anti- chain can be arbitrary. Therefore, we may use each element in a maximum anti-chain to encode X
8

---

as binary vector. The lower bound from Lemma 8 then gives an ((wiith(AX)/n) lower bound for = 1, as formalized below.
Lemma 17. For any ó > O, any (1,8)-DP algorithm for isotonic regression for any R-distance- based loss function l must have expected excess empirical risk Q (R(1 - -8) miin width(X)
n
Proof. Consider any (1, DDDP isotonic regression algorithm M' for loss &. Let A be any maximum anti-chain (of size width(A) A)) in X. We use this algorithm build a (1, 8DDP algorithm M for privatizing a binary vector m = min(n, | 1} dimensions as follows:
Let 2o, ....... Im be distinct elements of A. On imput z E {0, create a dataset D {(I1, (um: 2m), (ro, 0), .)....... (Io, 0)} times.
where (Zo; 0) is repeated
Run M on the instance to get f. and output a vector z' where 2 = 1ff(z;) 2 1/2].
It is obvious that this algorithm is (1, L)- Observe also that (f D) = 0 and thus MM expected excess empirical risk is IE (D> D)) 2 R. (xzz(((() ||| z [lo]// /n, which, from Lemma 8, must be at least O [m((1 - 8)/n) Ω R(1 - 8) minnn width(x))
By using group privacy (Fact 10) and repeating each element ((1EE) times, we arrive at lower bound of ? R min width(.X) Furthermore, since X' contains height(A') elements that form a totally ordered set, Theorem 15 gives a lower bound of Q(R log (heightt((())) as long as 5 < 0.01 e/ height((Xt) Finally, due Lemma 16, we have height(XX) / wi)th(2"), which means that max (oitth(, log(
2 2(log (2)). Thus, we arrive at:
Theorem 18, For any E (0, 1] and any 5 < 0.01 E/(2), any (e,8)-DP algorithm for iso- tonic regression for R-distance-based loss function & must have expected excess empirical risk Ω R min {1, width(XX) [X]
4.3 Tight Examples for Upper and Lower Bounds
while our lower bound is Ω wl) Recall that our upper bound is Ô ())
en
on
One might wonder whether this gap can be closed. Below we show that, unfortunately, this is impossible in general: there are posets for which each bound tight.
Tight Lower Bound Example. Let Kaij((w,h) denote the poset that consists of w disjoint chains, CI...., Cn where [C1 and [C2l = ... = ICu, = 1. (Every pair of elements on different chains incomparable.) In this case, and piece the solutions together into the final output f. Note that (Xaisj(w
solve the isotonic regression problem directly each chain
w + - and width(X') = w, height(X() = h. According to Theorem I, the unnormalized excess empirical risk in C2 is Ô (lo)((C)))/E). Therefore, the total (normalized) empirical risk for the entire domain X' is This is at most Ô wi En
log (w--)
as long as (xp(O(w)) (w)); this matches the lower bound.
832
Tight Upper Bound Example. Consider the grid poset Xgrid(w,h) == [w] x [h] where (I,,) S (x', ('',")) if and only if x < x and S y'. We assume throughout that < h. Observe that width( (xrr = w and height (Xgid(w)))))) w + h.
We will show the following lower bound, which matches the δ (widch(()) [x]) upper bound the on
case where h 2 w. (0()), up to (log²(en)) factor. We prove it by a reduction from Lemma 9. Note that this reduction is in some sense a "combination" of the proofs of Theorem 15 and Lemma 17, as the coordinate-wise encoding aspect of Lemma 17 is still present (across the rows) whereas the packing-style lower bound is present in how we embed elements of [D] (in blocks of columns).
Lemma 19. For any E (0, and 8 (1/h/), any (e, 6)-D algorithu for isotonic regression for any R-distance-based loss function é must have expected excess empirical risk R min {1, wolog(b/1))

---

Proof. Let D 1h/w m = w and r := mmn[
Consider any
(e, 6) algorithm M' for isotonic regression for on (grid(m,h) where S L.01e/D. We use this algorithm to build a (In(D/2), 0.25)-DP algorithm M for privatizing a vector z E [D] follows:
Create a dataset D that contains:
For all E [m=]. r copies of ((i, (wc -w- (D 1)) ()) and r copies of ((i, - () 1)
24 + 1).
n 2rm copies of ((1,1),0)
Run M' on instance D to get f.
Output vector z' where z max {j [D] plicity, when such j does not exist let 2/ = 0.)
+)) - 1/2]. (For sim-
By group privacy, is (.25))), Furthermore, [(f": D) = 0 and the expected empirical excess risk M'
E B)~MI() [[]; D)]
Eie(m] (e(f(i, (w ()) (((())))))(((((( 1)) +), 1).
:. [m 9(1/2)- 1[2 * 2:] Rr. -||z z z'1lo=
which must be at least Q ((rmm/)) = R min {I, (o }} by Lemma 9.
5 Additional Related Work
(Non-private) isotonic regression is well-studied in statistics and machine learning. The one- dimensional (aka univariate) case has long history [9, 46, 5, 44, 45, 13, 8, 35, 14, 15, 49]: for general introduction, see [22]. Moreover, isotonic regression has been studied in higher dimensions [24, 27, 26], including the sparse setting [21], as well as in online learning [29]. A related line of work studies learning neural networks under (partial) monotonicity constraints [3, 50, 30, 40].
There has been rich body of work on DP machine learning, including DP empirical risk minimiza- tion (ERM), e.g., [11, 6, 48, 47], and DP linear regression, e.g., [1]; however, to the best of our knowledge none of these be applied to isotonic regression obtain non-trivial guarantees.
Another line of work related to our setting is around privately learning threshold functions [7, 20, 10, 2, 28]. We leveraged this relation to prove our lower bound for totally ordered case (Section 3.2).
6 Conclusions
In this paper we obtained new private algorithms for isotonic regression on posets and proved nearly matching lower bounds in terms of the expected empirical excess risk. Although algorithms for totally ordered sets are efficient, our algorithm for general posets is not. Specifically, a trivial implementation of the algorithm would run in time exp(O(withh(X))) open question whether this can be sped up. To the best of knowledge, this question does not seem to be well understood even for the non-private setting, as previous algorithmic works have focused primarily on the totally ordered case. Similarly, while our algorithm efficient for the totally ordered sets, it remains interesting to understand whether nearly linear time algorithms for f1- and Lz losses can be extended larger class of loss functions.
It remains an interesting
10

---

References
[1] D. Alabi, A. McMillan, J. Sarathy, A. D. Smith, and P. Vadhan. Differentially private simple linear regression. Proc. Priv. Enhancing Technol., 2022(2):184-204 2022.
[2] N. Alon, R. Livni, M. Malliaris, and S. Moran. Private PAC learning implies finite littlestone dimension. In STOC, pages 852-860, 2019.
[3] N. P. Archer and S. Wang. Application the back propagation neural network algorithm with monotonicity constraints for two-group classification problems. Dec. Sci., 24(1):60-75, 1993.
[4] M. Ayer, H. D. Brunk, G. M. Ewing, W. T. Reid, and E. Silverman. An empirical distribution function for sampling with incomplete information. Ann. Math. Stat., pages 641-647, 1955.
[5] R. E. Barlow, D. Bartholomew, J. M. Bremner, and H. D. Brunk. Statistical Inference Under Order Restrictions. John Wiley & Sons, 1973.
[6] R. Bassily, A. Smith, and A. Thakurta. Private empirical risk minimization: Efficient algo- rithms and tight error bounds. In FOCS, pages 464-473, 2014.
[7] A. Beimel, K. Nissim, and U. Stemmer, Private learning and sanitization: Pure vs. approximate differential privacy. Theory Comput., 12(1):1-61, 2016.
[8] L. Birgé and P. Massart. Rates of convergence for minimum contrast estimators. Prob. Theory Rel. Fields, 97(1):113-150 1993.
[9] H. D. Brunk. Maximum likelihood estimates of monotone parameters. Ann. Math. Stat., pages 607-616, 1955.
[10] M. Bun, K. Nissim, U. Stemmer, and P. Vadhan. Differentially private release and learning of threshold functions. In FOCS, pages 634-649, 2015.
[11] K. Chaudhuri, C. Montelconi, and A. D. Sarwate. Differentially private empirical risk mini- mization. JMLR, 12(3), 2011.
[12] R. P. Dilworth. A decomposition theorem for partially ordered sets. Ann. Math., 51(1):161- 166, 1950.
[13] D. L. Donoho. Gelfand widtts and the method of least squares. Technical Rephort, University of California, 1991.
[14] C. Durot. On the error of monotonicity constrained estimators. Ann. Stat., 35(3): 104, 2007.
[15] C. Durot. Monotone nonparametric regression with random design. Math. Methods Stat., 17(4):327-341, 2008
[16] C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, pages 486-503, 2006.
[17] C. Dwork, F. McSherry, K. Nissim, and A. D. Smith. Calibrating noise sensitivity in private data analysis. In TCC, pages 265-284, 2006.
[18] C. Dwork, F. McSherry, K. Nissim, and A. D. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265-284, 2006.
[19] R. L. Dykstra and T. Robertson. An algorithm for isotonic regression for two or more indepen- dent variables. Ann. Stat., 10(3):708-716, 1982.
[20] V. Feldman and D. Xiao. Sample complexity bounds on differentially private learning via communication complexity. In COLT, volume 35, pages 1000-1019, 2014.
[21] D. Gamarnik and Gaudio. Sparse high-dimensional isotonic regression. NeurlPS, 2019.
[22] Groeneboom and G. Jongbloed. Nonparametric Estimation under Shape Constraints. Cam- bridge University Press, 2014.

---

[23] C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger. On calibration of modern neural networks. In ICML, pages 1321-1330, 2017.
[24] Q. Han, T. Wang. Chatterjee, and R. J. Samworth. Isotonic regression in general dimensions. Ann. Stat., 47(5):2440223 2470, 2019.
[25] M. Hardt and K. Talwar. On the geometry of differential privacy. In STOC, pages 705-714, 2010.
[26] M. Kakade, V. Kanade, O. Shamir, and A. Kalai. Efficient learning of generalized linear and single index models with isotonic regression. In NeurlPS, 2011.
[27] A. T. Kalai and R. Sastry. The isotron algorithm: High-dimensional isotonic regression. In COLT, 2009.
[28] H. Kaplan, K. Ligett, Y. Mansour, M. Naor, and U. Stemmer. Privately learning thresholds: Closing the exponential gap. In COLT, pages 2263-2285, 2020.
[29] W. Kotlowski, W. M. Koolen, and A. Malek. Online isotonic regression. In COLT, pages 1165-1189, 2016.
[30] X. Liu, X. Han, N. Zhang, and Q. Liu. Certified monotonic neural networks. NeurlPS, pages 15427-15438, 2020.
[31] R. Luss, S. Rosset, and M. Shahar. Efficient regularized isotonic regression with application to cone-gene interaction search. Ann. Appl. Stat., 6(1):253-28)) 2012.
[32] Manurangsi. Tight bounds for differentially private anonymized histograms. In SOSA, pages 203-213, 2022.
[33] McSherry. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. Commun. ACM, 53(9):89-97) 2010.
[34] McSherry and K. Talwar. Mechanism design via differential privacy. In FOCS, pages 94- 103, 2007.
[35] M. Meyer and M. Woodroofe. On the degrees of freedom in shape-restricted regression. Ann Stat., 108331108-11104 2000.
[36] L. Mirsky. A dual of Dilworth's decomposition theorem. AMS, 78(8):876-877, 1971.
[37] C. Radebaugh and U. Erlingsson. Introducing TensorFlow Privacy: Learning with Differential Privacy for Training Data, March 2019. blog. tensorflow.or org.
[38] Robertson, T. Wright, and R. L. Dykstra. Order restricted statistical inference. John Wiley & Sons, 1988.
[39] M. J. Schell and B. Singh. The reduced monotonic regression method. JASA, 12443) 1997.
[40] A. Sivaraman, G. Farnadi, T. Millstein, and G. Van den Broeck. Counterexample-guiee learn ing of monotonic neural networks. In NeurIPS, pages (1936-1194 2020.
[41] T. Steinke and J. R. Ullman. Between pure and approximate differential privacy. J. Priv. Confidentiality, 7(2), 2016.
[42] Q. F. Stout. Unimodal regression via prefix isotonic regression. Comput. Stat. Data Anal., 53(2):289-29) 297, 2008
[43] D. Testuggine and I. Mironov. PyTorch Differential Privacy Series Part 1: DP-SGD Algorithm Explained, August 2020. medium. com.
[44] Van de Geer. Estimating a regression function. Ann. Stat., pages 907-924, 1990.
[45] Van de Geer. Hellinger-comsistenay of certain nonparametric maximum likelihood estima- tors. Ann. Stat. 21(1):14 1993.
12

---

[46] C. van Eeden. Testing and Estimating Ordered Parameters of Probability Distribution. CWI, Amsterdam, 1958.
[47] D. Wang, Chen, and Xu. Differentially private empirical risk minimization with non- convex loss functions. In ICML, pages 6526-6535, 2019.
[48] D. Wang, M. Ye, and J. Xu. Differentially private empirical risk minimization revisited: Faster and more general. In NIPS, 2017.
[49] Yang and R. F. Barber. Contraction and uniform convergence of isotonic regression. Flec.
J. Stat., 13(4)66466677, 2019.
[50] You, D. Ding, K. Canini, Pfeifer, and M. Gupta. Deep lattice networks and partial mono- tonic functions. NIPS, 2017.
[51] B. Zadrozny and C. Elkan. Transforming classifier scores into accurate multiclass probability estimates, KDD, pages 694-699, 2002.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes) See Section 6.
(c) Did you discuss any potential negative societal impacts of your work? [NIA] Since this a purely theoretical paper regarding private algorithms for well studied ML task of isotonic regression, we do not foresee any immediale potential negalive impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Including some proofs in the supplementury material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report enror bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l re using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "v2CZOFT35Ec", "reviewer": "Reviewer_YkU9", "summary": "This paper is the first to deal with DP isotonic regression: where the domain is some *partially* ordered set X and the goal is to find a *monotonic* f:X\\to[0,1] that minimizes a certain empirical loss. The paper first discusses the totally-ordered set X case and then the partially ordered set case by implementing a generalization of the totally-ordered algorithm.\n\nThis is a the first paper to tackle this problem.", "questions": "Many typos throughout (like \"the the\" on P.1). Please go over the paper carefully and remove them.", "limitations": "First paper to tackle a new problem, and as such the painting isn't \"complete\" yet.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* first to deal with this problem\n* poses upper- and lower-bounds that depend on both log(|X|) and width(X) (the max-length of an anti-chain in X).\n\nWeakness:\n* upper and lower bounds don't match yet fully\nThat is of course, expected from a first paper.\n\nI think this is an interesting paper that is likely to instigate follow-up works on this version of ERM and many other variants of \"constrained\" ERMs. A clear accept.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "pCROERZUusG", "reviewer": "Reviewer_4CVD", "summary": "The paper studies the problem of diferentially private isotonic regression. It first introduces an algorithm and its excess risk. It then studies a lower bound for solving this problem privately, and shows that the gap between the two bounds is tight, in the sense that for each bound there exist posets for which each bound is tight,  and thus the gap cannot be closed. The algorithm runs in near linear time for totally ordered sets with $\\ell_1$ and $\\ell^2_2$ losses. \n\nPrivacy is guaranteed by relying on the exponential mechanism to iteratively select threshold functions on smaller partitions of the domain. Then it applies standard composition to allocate the privacy budget across iterations. \n", "questions": "- Do these complexity bounds allow for running the algorithm in practice? or what scale of problems, settings would this algorithm fit and be meaningful? \n- Is it useful to consider algorithms similar to the one in Kaplan 2020 [27] that could reduce the dependency on the domain size?\n", "limitations": "- Width(X) can be an extremely large quantity and make this algorithm impractical. \n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n*Strengths*\n- The specific problem of isotonic regression has not been studied before in the privacy literature. \n- The paper provides a clear characterization of the problem introducing upper and lower bounds, and assumptions that allow for improvement or tightness of the results. \n- The paper is clearly written and well organized. \n\n*Weaknesses*:\n- The paper could provide more tangible intuition on the results, for example in what settings this would be a meaningful practical algorithm, and in what settings it is still a first attempt that needs improvements to be applied. Either a discussion or small synthetic experiments could help understand these results, especially given that there is no previous work on the area.  This would give an intuition on the price of privacy, the easiness to tune clipping, etc. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "i6nQ1AK2ZMw", "reviewer": "Reviewer_DQZ5", "summary": "This paper considers the problem of DP isotonic regression. For general loss functions, an inefficient algorithm is proposed to achieve a utility with a logarithmic dependency on the alphabet size for pure dp, An efficient algorithm is provided for $\\ell_1$ and $\\ell_2$ loss functions.", "questions": "NA", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper considers the problem of DP isotonic regression. For general loss functions, an inefficient algorithm is proposed to achieve a utility with a logarithmic dependency on the alphabet size for pure dp, The result is tight if the paper considers the minimax setting. I think this is a very good result for an initial work in this area.\n2. An efficient algorithm is provided for $\\ell_1$ and $\\ell_2$ loss functions.\n\nWeakness:\n1. My most complaints are on the presentation. First, the paper does not distinguish between the minimax setting and the instance based setting. Specifically, I was quite confused when I first looked at the discussion about the tightness. If the paper explicitly defined the two concepts, it could easily say the algorithm is minimax optimal but not instance optimal. Furthermore, it would be much better if the authors could define the isotonic regression and the width in the introduction, making it easier for the readers to evaluate the results.\n1. it remains interesting to see the effects of different loss functions, both to the sample complexity and computation complexity.\n\nMinor:\n1. No hyperlinks for theorems.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "5RzvWbJLmtU", "reviewer": "Reviewer_heQ2", "summary": "This paper considers the problem of private isotonic regression in which given a dataset D consisting of n samples, the goal is to output a monotone function f that minimizes the empirical risk $L(f;D)=(1/n)\\sum_i \\ell(f(x_i,y_i)$. The authors give a pure DP algorithm for the most general version of the problem which considers a poset X and a Lipschitz loss function $\\ell$ and they obtain an expected excess empirical risk of $width(X)*log(X)/n$.  For a fully ordered set, this algorithm is efficient and the idea is to privately choose a maximal point \\alpha via the exponential mechanism and then recursively obtain the final function f by gluing together the functions obtained from recursing on the two partitions of [m] created via \\alpha. The authors note that a simple implementation of assigning the (unnormalized) empirical risk as the score function results in a large error loss, so instead, they use a clipped version of the loss function as the score function resulting in reasonably low sensitivity. The more general DP algorithm has a similar flavor, except now one has to privately choose multiple maximal points \\alpha, which leads to a less efficient algorithm (due to multiple calls to the exponential mechanism). \nThe authors also obtain a near-matching lower bound of $(width(X)+log(X))/n$. They achieve this by reducing to a known DP lower bound for DP algorithms that output a binary vector that is close to the input. They also show that while there is a gap between the demonstrated upper and lower bounds, there are posets that tightly realize each bound. \n", "questions": "See in comments above.", "limitations": "See in comments above. No potential for negative societal impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: \nThe contributions are original and would be of much interest to the overall machine learning community. It would be good to discuss existing DP algorithms on the closely related topic of simple linear regression in the Related Work section (see Daniel Alabi, Audra McMillan, Jayshree Sarathy, Adam D. Smith, Salil P. Vadhan: Differentially Private Simple Linear Regression. Proc. Priv. Enhancing Technol. 2022(2): 184-204 (2022))\n\n\nQuality: The methods used are standard techniques in DP such as exponential mechanism, composition for the upper bounds, and reductions from known DP problems for the lower bounds. I am fairly confident that the work is sound, although I have not checked every single detail.   \n\n\nClarity: The paper is mostly well-written, just for completeness, it would be good to explicitly state the running time of the DP algorithm for the general posets.  \n\n\nSignificance: Isotonic regression is an important primitive in the machine learning toolbox. This work advances the state of the art on DP machine learning algorithms by adding this problem to the DP machine learning toolbox. The algorithms and proofs presented are relatively straightforward and easy to follow, and the authors also leave a set of intriguing open questions which may lead to further understanding of the complexity of machine learning tasks under DP constraints. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept