Learning with User-Level Privacy
Authors: Daniel Asher Nathan Levy
Ziteng Sun
Kareem Amin
Satyen Kale
Alex Kulesza
Mehryar Mohri
Ananda Theertha Suresh
Venue: NeurIPS 2021 Poster (2021)
Keywords: privacy
user-level
optimization
sco
learning
minimax
lower bounds
differential privacy

Abstract: We propose and analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution ($m \ge 1$ samples), providing more stringent but more realistic protection against information leaks.  We show that for high-dimensional mean
estimation, empirical risk minimization with smooth losses, stochastic convex optimization, and learning hypothesis classes with finite metric entropy, the privacy cost decreases as $O(1/\sqrt{m})$ as users provide more samples. In contrast, when increasing the number of users $n$, the privacy cost decreases at a faster $O(1/n)$ rate.  We complement these results with lower bounds showing the minimax optimality of our algorithms for mean estimation and stochastic convex optimization. Our algorithms rely on novel techniques for private mean estimation in arbitrary dimension with error scaling as the concentration radius $\tau$ of the distribution rather than the entire range.

Learning with User-Level Privacy
Daniel Levy":!
Ziteng Sun 2
Kareem Amin
Satyen Kale Ananda Theertha Suresh
Alex Kulesza
Mehryar Mohri
Stanford University
Cornell University
GGooll Research
Courant Institute
zs335@cornel1. edu, Ikamin, satyenkale, kulesza, mohri, theertha| @ @google.
danilery@stanford. edu,
Abstract
We propose and analyze algorithms to solve range of learning tasks under user- level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects user's entire contribution (m 2 I samples), providing more stringent but more realistic protection against informa- tion leaks. We show that for high-dimensional mean estimation, empirical risk minimization with smooth losses, stochastic convex optimization, and learning hy- pothesis classes with finite metric entropy, the privacy cost decreases D11/vm) as users provide more samples. contrast, when increasing the number of users n, the privacy cost decreases faster ((1 /n) rate. We complement these results with lower bounds showing the minimax optimality of our algorithms for mean estimation and stochastic niques for private mean estimation in arbitrary dimension with error scaling as the concentration radius 7 of the distribution rather than the entire range.
optimization. Our algorithms rely novel tech-
Introduction
Releasing seemingly innocuous functions of data easily compromise the privacy of in- dividuals, whether the functions are simple counts [35] or complex machine learning models like deep neural networks [52, 30]. To protect against such leaks, Dwork al. proposed the notion of differential privacy (DP). Given some data from n participants in a study, we say that a statistic the data is differentially private if attacker who already knows the data of reliably determine from the statistic whether the n-th remaining participant is Alice or Bob. With the recent explosion of publicly available data, progress in machine learning, and widespread public release of machine learning models and other statistical inferences, differential privacy has become an important standard and is widely adopted by both industry and government [32, 5, 25J.
participants cannot
The standard setting of DP described in [22] assumes that each participant contributes a single data point to the dataset, and preserves privacy by "noising" the output in way that is commensurate with the maximum contribution of a single example. This is not the situation faced in many applications of machine learning models, where users often contribute multiple samples to the model for example, when language and image recognition models are trained on the users' own data, or in federated learning settings [37]. As result, current techniques either provide privacy guarantees that degrade with user's 's increased participation or naively add substantial amount of noise, relying on the group property of differential privacy, which significantly harms the performance of the deployed model.
To remedy this issue, we consider user-level DP, which instead of guaranteeing privacy for individual samples, protects user's entire contribution (m 2 samples). This is more stringent but more realistic privacy desideratum. To hold, it requires that the output of our algorithm does not significantly
Equual contribution. Work was done during an internship at Google Research.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

change when changing user's 's entire contribution possibly swapping up to m samples in total. We make this formal in Definition Very recently, for the reasons outlined above, there has been increasing interest in user-level DP for applications such as estimating discrete distributions under user-level privacy constraints [46], PAC learning with user-level privacy [31], and bounding user contributions in ML models [4, 26]. Differentillly private SQL with bounded user contributions was proposed in [59]. User-level privacy has been also studied in the context of learning models via federated learning [49, 48, 58, 6].
In this paper, we tackle the problem of learning with user-level privacy in the central model of DP. In particular, we provide algorithms and analyses for the tasks of mean estimation, empirical risk minimization (ERM). stochastic convex optimization (SCO), and learning hypothesis classes with finite metric entropy. Our utility analyses assume that all users draw their samples i..dd from related distributions, setting we refer to as limited heterogeneity. On these tasks, naively applying standard mechanisms, such as Laplace or Gaussian, or using the group property with item-level DP estimators, both yield a privacy error independent of m. We first develop novel private mean estimators in high dimension with statistical and privacy error scaling with the (arbitrary) concentration radius rather than the range, and apply these to the statistical query setting [SQ: 41]. Our algorithms then rely on (privately) answering a sequence of adaptively chosen queries using users' samples, e.g., gradient queries in stochastic gradient descent algorithms. We show that for these tasks, the additional error due to privacy constraints decreases as D(1/Vm)) contrasting with the naive rate- independent of m. Interestingly, increasing n, the number of users, decreases the privacy cost at a faster O(1/n) /nn) rate.
Importantly, our results imply concrete practical recommendations on sample collection, regardless of the level of heterogeneity. Indeed, increasing m will yield the most value in the i.i.d. setting and will yield no improvement when the users' distributions are arbitrary. As the real-world will lie somewhere in between, our results exhibit a regime where, for any heterogeneity, it is strictly better to collect more users (increasing n)) than more samples per user (increasing m.)
1.1 Our Contributions and Related Work
We provide thcoretical tool to construct estimators for tasks with user-level privacy constraints and apply it to a range of learning problems.
Optimal private mean estimation and uniformly concentrated queries (Section 3) We show that for a random variable in | B, B] concentrated in an unknown interval of radius T (made precise in Definition 2), can privately estimate its mean with error proportional to rather than B, as we would obtain using standard private mean estimation techniques such as Laplace mechanism [24]. When data is concentrated in -orm,, several papers show that one can achieve error scaling with r rather than B, either asymptotically [53], for Gaussian mean-estimation [40, 38), for sub-Gaussian symmetric distributions [18, 17] or for distributions with bounded p-th moment [39]. We propose a private mean estimator (Algorithm 2) with error scaling with 7 that works in arbitrary dimension when data is concentrated in é f2-norm (Theorem 2). In Corollary 1, we show it (optimally) solves mean estimation under user-level privacy constraints for random vectors bounded in 4n-nomm. In Appendix D.6, we show that for uniformly concentrated queries (see Definition 3), sequentially applying Algorithm 2 privately answers K adaptively chosen queries with privacy cost Ö(TV K /nE).
Our conclusions relate to the growing literature in adaptive data analysis. While a sequence of work [25, 9, 27, 28] use techniques from differential privacy and their answers are (c, 8)-DP with ε = +1), our work guarantees privacy for arbitrary & with the additional assumption of uniform concentration.
Empirical risk minimization (Section 4) An influential line of papers studies ERM under item- level privacy constraints [19, 42, 8). Importantly, these papers assume arbitrary data, i.e., not necessarily samples from users' distributions. The exact analog of ERM in the user-level setting is consequently less interesting as, for n data points {=1...., 2n ). in the worst case, each user u [n] contributes m copies of Zu and the problem reduces to the item-level setting. Instead, we consider the (related) problem of ERM when users contribute points sampled i.i.d. Assuming some regularity (A3 and A4), we develop and analyze algorithms for ERM under user-level DP constraints for convex, strongly-convex, and non-convex losses (Theorem 3).
Optimal stochastic convex optimization (Section 5) Under item-level DP (or equivalently, user- level DP with m 1). sequence of work [19, 8, 10, 11, 29] establishes the constrained minimax risk as 0(1/v/ /n= + vd)(n))). In this paper, with the additional assumptions that the losses are
2

---

individually smooth and the gradients are nuu-Gausiian random vectors, we prove matching upper (Theorem 4) and lower bounds (Theorem 5) of order ( + Vd/(n//mn in a regime we make precise. We leave closing the gap outside of this regime to future work.
Limit of learning with a fixed number of users (Appendix B) Finally, we resolve a conjecture of [4] and prove that with fixed number of users, even in the limit m - oc (i.e., each user has an infinite number of samples), we cannot reach zero error. In particular, we prove that for all the learning tasks consider, the risk under user-level privacy constraints is at least (() regardless of m. Note that this does not contradict the results above since they require n = 9 ([logm)/)) m)/E).
Finally, we provide results in Appendix A for learning under pure user-level DP for function classes with finite metric entropy. We apply these to SCO with &or constraints (Remark 1) and achieve (near)-optimal rates.
2 Preliminaries
Notation. Throughout this work, d denotes the dimension, n the number of users, and m the number of samples per user. Generically, will denote the sub- Gab-sia parameter, the concentration radius, V the variance a random vector and a data distribution. We denote the optimization variable with
O IRd use = (or Z when random) to denote the data sample supported space 2, and l: θ x Z - R for the loss function. Gradients (denoted V) are always taken with respect to the optimization variable A. For convex set C. Ie denotes the euclidean projection C, i.e.e. (I) == argminzec lyy - 21|2- We use A to refer to (possibly random) private mechanisms and X" as shorthand for the dataset (X Xn.) For two distributions P and Q, we denote by ||- TV their total variation distance and Dai (PIQ) their Kullback-Leibler divergence. For random vector X ~ P supported on Rd, we use Var(P) or Var(X) to denote E [[|X E[x]] which is equal to the trace of the covariance matrix of X.
Next, we consider differential privacy in the most general way, which only requires specifying a dataset space & and a distance d on S.
Definition 1 (Differential Privacy). Let E, 2 O. Let A: 8 + o be a (potentially randomized) mechanism. We say that A is (s, dDP with respect to d for any measurable subset O C O and all S,S' E satisfying d(S, S*) < 1,
P(A(S) E O) S EP((SS) E E0) 6
(1)
If 8 = 0, we refer to this guarantee pure differential privacy.
For data space Z, choosing S z" and d(S, S*) = dHam (S, = 2 recovers the canonical setting considered in most of the literature- we refer to this as item-level differential privacy. When we wish to guarantee privacy for users rather than individual samples, we instead assume structured dataset into which each of n users contributes m > 1 samples. This corresponds to S (z such that for S E S, we have
S= = (Si,..., Sn), where S,, ( (u)
2/1 and duser(( = Σ I(S S.
which means that, in this setting, two datasets are neighboring if at most one of the user's contributions differ. We henceforth refer to this setting as user-level differential privacy.
Distributional assumptions. In the case of user-level privacy with n users each providing m samples, assume existence of collection of distributions (Pu)ue(n) over Z. One then observes the following user-level d
S = (SI...,, Sw) where S, üd
~ Pa.
(2)
We note that the results only require -mmooth losses. For large n keeping all other problem parameters fixed-this is very weak assumption. More precisely, when poly(d, m, 1/e), our algorithm on a smoothed version i of é (e.g.. using the Moreau envelope [33]) yields optimal rates for mon-smooth losses. Whether the smoothness assumption 'For simplicity, we assume that |S.]| = m but our guarantees directly extend to the setting where users have different number of samples with replaced by median(ma.... m.) using techniques from [46]. We leave eliciting the optimal rates in settings when my is arbitrary random variable to future work.
be removed altogether is open question.
3

---

In this paper, we consider the limited heterogeneity setting, i.c. when the users have related distri- butions. This setting more reflective of practice, especially in light of growing interest towards federated learning applications [37, 60].
Assumption A1 (Limited heterogeneity setting). There exists a distribution Po over 2 such that all the user distributions close to Po in total variation distance, i.e.
max Pv - PPllTTV S A,
where A > 0 quantifies the level of heterogeneity, Note that A O corresponds assumption A2.
Note that our TV-based definition is natural in this setting as it is closely related to the notion of discrepancy (or d distance) which plays a key role in domain adaption scenarios [47, 12]. Lower bound results have been given in terms of the discrepancy measure (see [13]), which further justify the adoption of this definition in the presence of multiple distributions.
In the case that A = 0, Al reduces to the standard homogeneous setting. Many fundamental papers choose this setting when explicating minimax rates under constraints (e.g. in distributed optimization and federated learning [61] or under communication constraints [63, 15]).
Assumption A2 (Homogeneous setting). The distributions of individual users are equal, meaning there exists Po such that for all u E [nl]. Pa = Po.
In this paper, we develop techniques and provide matching upper and lower bounds for solving learning tasks in the homogeneous setting. In Appendix C, we prove that our techniques naturally apply to the heterogeneous setting in a black-box fashion, and for all considered problems provide meaningful guarantees under Assumption A1. Moreover, the algorithm achieves almost optimal rate whenever A is (polynomially) small. See the detailed statement in Theorem 9.
2.1 ERM and stochastic convex optimization
Assumptions on the loss. Throughout this work, we assume that the parameter space is closed,
convex, and satisfies ||0 0l12 R for all 0 & E O. We also assume that the loss E: θ 2 - R is
G-Lipschitz w.r.t. the fz-norm", meaning that for all 2 E 2, for all A E O, [[(;; 2) 2) S G. We further consider the following assumptions.
Assumption A3. The function f(:: is H-smooth. In other words, the gradient Ve(0;2) z) is H- Lipschitz in the variable A for all E Z.
Assumption A4. The random vector [e(0; Z) is o2 Gaussian for all 0 θ and Z ~ Po Equivalently, for all Rd, (v, Ve(0; Z)) is a ---sub-Gaussia random variable, i.e.
E [exp((u, VE(0; 2) - E 2))))| S exp((1u|202
In this work, our rates often depend on the sub-Gaussianity and Lipschitz parameters and G, and thus we define the shorthands G == a and G := min(G, G). Intuitively, the G-Lipschitzness assumption bounds the gradient in a ball around 0 (independently of 0), while sub-Gaussianity implies that, for each 6, Vē(0: Z) likely lies in ( Po), G). Generically, there is no ordering between G and G: for linear loss E(0: 2) (0, depending Po. it can hold that G < G (e.g., Po Unif(-v, v} for v E Rdd) G & G (e.g.. Py is N(H, o² Ia) truncated in ball around 14, with || > dvd) or G = G (e.g., Po = Unif (1,+())
We introduce the tasks we consider in this work, namely empirical risk minimization (ERM) and stochastic convex optimization (SCO). For a collection of samples from n users S = (Si,..,,,,,) S,). where each S,,
{z(w)
(w)
2m } E 2mh we define the empirical risk objectives
(u)
C(0; Sw) = m ((0:2,t) (")) and C(0:S)
m
1 Σ L(, = 17
1
m
2(0:2(
(3)
n
In the user-level setting we wish to minimize L(0; S) under user-level privacy constraints. Going beyond the empirical risk, we also solve SCO [51], i.e. minimizing a convex population objective
'It is straightforward to develop analogs of the results of Sections 3 and 4 for arbitrary norms, but we restrict attention to the &2 norm in this work for clarity.

---

when provided with samples from each users' distributions. In the user-level setting, for convex loss É and convex constraint we observe (Si..... ..)...))))..)..... @ue(m] (P.) and wish to
minimize lE
Σ 71
1
Σ
Ep. [0(; 2)).
(4)
72 [c(n)
mE(n)
In the homogeneous case (Assumption A2), this reduces to the classic SCO setting:
minimize L(0; Po) = E. [((0; 2)
(5)
BEB
2.2 Uniform concentration of queries
Let Ø: 2 + Re be d-dimensional query function. We define concentration of random variables and uniform concentration of multiple queries as follows.
Definition 2. (random) sample X" supported on [-B, B)d is (r, cooncetraat (and we call the "concentration radius") ") if there exists Tg [- B, BJd such that with probability at least %
max X; To 12 S.. sE(n]
[-B, be family of queries with bounded range. For Z IZ...... Zn,) iid P, we say that (Z", 22²) is (T, (nfoooanoolttycoooeeemeee if with probability at least we have
Definition 3 (Uniform concentration of vector queries). Let 2/ -
(((z) - -Ez ( ST. (E(n)
max sup
In this work, will often consider concentrated according to Definition 2. For example, if X is drawn i.i.d. from a -ussu--Gausi random vector supported on [-B, BJd, then it is (a (a (og(2n/7), 1)-concentrated around its mean (see, e.g., [56]). Finally, we define a distance between random variables (and estimators).
random variables (or vectors), which
Definition 4 (3-close Random Variables). For any two random variables X1 ~ P1 and X2 Ps. we say X, and X2 are 8-close, if P1 Pvll I B. We use the notation X1 rag X2 if X1 and X2 are 8-close.
9-closeness is useful as, in many of our results, the private estimator we propose returns a simple unbiased estimate with high probability and is bounded otherwise. Thus, it suffices do the analysis in the "nice" case and crudely bound the error otherwise.
3 High Dimensional Mean Estimation and Uniformly Concentrated Queries
In this section, we present private mean estimator with privacy cost proportional to the concentration radius. Using these techniques, show that, under uniform concentration, answer adaptively- chosen queries with privacy cost proportional to the concentration radius instead of the whole range. Our theorems guarantee that the estimator is f-close (with 3 exponentially small in n) simple unbiased estimator with small noise. We further show how to directly translate these results into bounds on the estimator error, which demonstrate by providing tight bounds on estimating the mean of bg-boudd random vectors under user-level DP constraints (Corollary 1).
Given i.i.d samples X" from distribution P supported on Rd with mean μ., the goal of mean estimation is to design private estimator that minimizes the E [|[A(X") - ==12]_ We focus on distributions with bounded supprot [-B, B, B)d, However, our algorithm also generalize to the case when the mean is guaranteed to be in [- B, Bld. In the user- setting (in the homogeneous case), one observes dataset S sampled as in (2) and wishes to minimize [[[[A(S)) EP under user-level privacy constraints. We first focus on the scalar case.
Mean estimation in one dimension. The algorithm uses two-stage procedure, similar in spirit to those of [53], [40], and [39]. In the first stage of this procedure, we use the approximate median estimation in [27]. detailed in Algorithm 6 in Appendix D.I, to privately estimate crude interval
5

---

Algorithm WinsorizedMeennDDGX ,,, B): Winsorized Mean Estimator (WME)
Require: X (2,, X2.... x,) E [- Bja, concentration radius, privacy parameter E 0. I: [a, bj = PrivateRange( s/ T, B)) with |b - al = 4T. {Algorithm 6 in Appendix D.I.
2: Sample Ç ~ (o, šr and return sm
IT [o.b)(X;) + +
where (z)) = max(a, min(2, b)}.
in which the means lie, with accuracy ((T). The second stage clips the mean around this interval, reducing the sensitivity from O (T), and adds the appropriate Laplace noise. With high probability, we can recover the guarantee the Laplace mechanism with smaller sensitivity since the samples are concentrated in a radius т. We present the formal guarantees of Algorithm I in Theorem and defer its proof to Appendix D.2.
Theorem 1. Let X be dataset supported on [-B, B). The output of Algorithm 1, denoted by )( is E-DP. Furthermore, if X is (T, cconeeeenttt,, it holds that
1 A(X*) ~B 71 Σ
88
X1
Lap
NE
where B = min {1,7 + exp (-"e)} Moreover, Algorithm 1 runs in time Ö(n + log( (B/T)).
Compared to [40, 38, 39], our algorithm runs in time Ö(n + log(B/r)) instead of Ö(n + B/T) owing the approximate median estimation algorithm in [27], which is faster when << B.
Mean estimation in arbitrary dimension. In the general d-dimensional case, if X is concentrated in -nrrm, one simply applies Algorithm each dimension. However, when X is concentrated in Ey-norm, naively upper bounding -nom by the fy-norm will incur superfluous /d factor: if ||ui|e S each |oy| is possibly as large as p. To remedy this issue, we use the random rotation trick in [3, 54J. This guarantees that all coordinates have roughly the same range: for E IRd, with high probability, ||Rv|ss loo < O(1vvlla/ v where is the random rotation. We present this procedure in Algorithm and its performance Theorem 2.
Algorithm 2 WinsorizedMMentHighDDXX ,,, T, B) WME High Dimension
Require: X == (X1, X2, X,,, X, E [. 7,7: concentration radius and probability, privacy parameter E, 0
1: Let D = Diag(w) where is sampled uniformly from 111]d.
2: Set U = HD, where H is a d-dimensional Hadamard matrix. For all i E [m]. compute
Y; U.
3: Let (8dlog(1/6) T' 10r
log(dn/ d
For j [d]. compute
Y(j) WinsorizedMean1D (Y:(i)) e', VaB).
4: return U-V-İV.
Theorem 2. Let A = WinsorizaMeenHHighDD.Z ,,, B, v be the output of Algorithm 2. A(X") (E, DD-.. Furthermore, X" is (T, (T..)) concentrattd in Ey-norm, there exists an estimator (x")) such that A(X") rg (X") and
dr Σ X₁ and (xx" s log(dn/oo log log(1/6)
n
[XA [X"]
(6)
n?g
d Bygllddn//))
where c = 102, 400 and min 1, 2y +
exp
ns
24 /dg/loo(1/8)
present the proof of Theorem Appendix D.3. We are able to transfer both Theorem 1 and Theorem into finite-sample estimation error bounds for various types of concentrated distributions

---

and obtain near optimal guarantees (see Appendix D.5 for an example in mean estimation of sub- Gaussian distributions). The next corollary characterizes the risk of mean estimation for distributions supported on an f2-bounded domain with user-level DP guarantees (see Appendix D.4 for the proof). [0, B) with mean p. Given S = (2, S2, S.). [Su| = m, consisting of m i.i.d. samples from Pu. There exists an (e, ---eer- level DP algorithm A(S) such that, if 2 (c1v (il//llog/////) (mg(m(d dn + n²²²)) ) for numerical constant C1, we have"
Corollary 1. Assume A2 holds with Po supported
Var(Po) δ
dB²
E [IA(S)) 2l
mn?g2
Trn
Note that Var(Po) B² for any Po supported on (0, B). Replacing Var (P) 6) by B², the bound is minimax optimal up to logarithmic factors. When only Al holds with A S poly dd, n m 2), the same error bounds holds (up constant) for estimating Ez~P, [T] [or any [n].
Note that algorithms in [38, 39], which focus on estimating the mean of d-dimensional subGaussian distributions, can also be used to estimate the mean of fy-bounded distributions since bounded random variables are also subGaussian. However, applying these algorithms directly will incur a superfluous d factor in the mean square error. We void this using the random rotation trick in Algorithm 2.
Answering multiple queries. We end this section by noting that, when family of queries Q is uni- formly concentrated (as made precise in Definition 3), we answer sequences of K d-dimensional, adap- tively chosen queries with error scaling as Ō( ((VKT// (nE)) by applying Algorithm 2 to he([) with the right (Eo, 6g). We make this formal in Theorem 10 in Appendix D.6.
Empirical Risk Minimization with User-Level Differential Privacy
In this section, we present an algorithm to solve the ERM objective of (3) under user-level DP constraints. We apply the results of Section 3 by noting that the SQ framework encompasses stochastic gradient methods. Informally, one can sequentially choose queries dv(2)) = Vl(0g; 2) and, for a stepsize 17, update 0k+1 = llle (0,- - 77&)). where U2 is the answer to the k-th query. For the results to hold, we require uniform concentration result over the appropriate class of queries.
Uniform concentration of stochastic gradients The class of queries for stochastic gradient meth- ods is Qern (V) 0 θ]. We prove that when assumptions A3 and A4 hold, ([V((-; JuE pej] 2erm) is (Ö(a /d/m)/ ---unfoomlly concentrated. The next proposition is a simplification of the result of [50] under the (stronger) assumption A3 that & is uniformly H-smooth. The proof, which we defer to Appendix 1. hinges on a covering number argument.
jid Proposition 1 (Concentration of random gradients). Let Sy ~ Pa. |Sul = for E [n]] and a 2 0. Under Assumptions A3 and A4, with probability greater than a it holds that
max sup (.) VL(00 P.)l22 = -V(0 (
d log
RHm do
log (4)
(E(m] BEe
Stochastic gradient methods We state classical convergence results for stochastic gradient methods for both convex and non-convex losses under smoothness. For a function F : e - R, we assume access to first-order stochastic oracle O Du,a, i..., random mapping such that for all 0 E θ,
O F (0) vF with E [ F())) and Var (Vi()) S
We abstract optimization algorithms in the following way: an algorithm consists of output set O a sub-routine Query O - θ that takes the last output and indicates the next point to query and sub-routine Update O x I2d + O that takes the previous output and stochastic gradient and returns the next output. After 7' steps, we call Aggregate O + O, which takes all the previous outputs and returns the final point. (See Algorithm 7 in Appendix E.2 for how to instantiate generic first-order optimization in this framework.) We detail in Proposition 4 in Appendix E.2 standard convergence results for variations of (projected) stochastic gradient descent (SGD). We introduce this abstraction to forego the details of each specific algorithm and instead focus on the privacy and utility guarantees.
Forr precise log factors, see Appendix D.4.
7

---

inf Algorithm We recall the ERM setting with user-level DP. We observe S = (Si...., S,) with S, E t for [n] and wish solve the constrained optimization problem with objective (3). We present our method in Algorithm 3 and provide utility and privacy guarantees in Theorem 3.
Algorithm 3 Winsorized First- Order Optimization
1: Input: Number of iterations T, optimization algorithm {O, Query, Update, Aggregate), privacy parameters (c, 6), data S (Si...., Sn), initial output oo, parameter set θ, concentration radius
т, probability
2: Set E'
2/ 2 17 and 8' 6 27
3: for O.....T ......TT-... do
4: 0₂ < Query(o.).
5: For each user E [n]. compute
VL(0,S.)) 1 Σ v((0);2)))) (u)
m je(mL, 6: Compute 9r WinsoriredMMannHHigDD ((gh JwE[m) &,,
014-1 (ppdate(o..g)).
8: end for
9: return 0 oggregate(oo.....or)
Theorem 3 (Privacy and utility guarantees for ERM), Assume A2 holds and recall that G o d, assume 12( (D(VdT/e, /e) and let 0 be the output of Algorithm 3. There exists variants of projected SGD (e.g. the ones we present in Proposition 4) such that, with probability greater than
(i) ffr all E Z, E(,((; 2) is convex, then
d'Ee E ((,,)) inf C(O'; = R2H + RG Vd
11 me
(ii) for all 2, 2,((:2) is p-strongly-conves then
= =O(cRoxp(- -O(GRexp(##1) HT) G2 2
E L(
d'Ee (()
(iii) Otherwise, defining the gradient mapping' (F = 1/0 -I - FV)()) we have
H2R T
Vd
= + HRG
ny/me)
For E O, Algorithm 3 instantiated with any first-order gradient algorithm is (e, uuserr-evee DP. In the case that only Al holds, the same guarantees hold whenever A poly(d, m 2
We present the proof in Appendix E.3. For the utility guarantees, the crux of the proof resides in Theorem 10: as well ensuring small excess loss in expectation, the SQ algorithm produces with high probability sample from the stochastic gradient oracle O O((-S),>> where D² ÓTT -= When this happens for all T steps, the analysis of stochastic gradient methods provide the desired regret. The privacy guarantees follow from the strong composition theorem of [23].
Importantly, when the function exhibits (some) strong-convent convexity (which will be the case for any regularized objective), we are able to localize the optimal parameter-uu up to the privacy cost in Ó(H/P) steps. This will be particularly important in Section 5.
Corollary 2 (Localization). Let θ be the output of Algorithum on the ERM problem of (3). Assume that ((;2) j-stronglyycoovve for all Z, that i D(/dH//p and T 22
H. log ( (n² p
ufte "RR" and 7 Tw For 03 E argiiingee L(O'; (('':S) S)) it holds
'For precise log factors, see Appendix E.3.
In the unconstrained case Rd this corresponds e-stationary point as GF, VF))). A logarithmic dependence on 7 is hiding in the result. Since T' = Ó(H/p). we implicitly assume H/u is polynomial in the stated parameters, which satisfied when later apply these results to regularized objectives.

---

o²d
5: end for B[110 031120 Ö
12222mm?
5 Stochastic Convex Optimization with User-level Privacy
In this section we address the SCO task of (5) under user-level DP constraints. Our approach (which we show in Algorithm solves sequence of carefully regularized ERM problems, drawing on the guarantees of the previous section. Recall that G = avd and = min(G, G), and that is H-smooth under assumption A3. In this section, we assume that l is convex. We first present our results and state an upper and lower bound for SCO with user-level privacy constraints.
Theorem (Phased ERM for SCO), Algorithm user-level (e, (e.B).DP. When A2 holds and n. Mminn { &m ne (GGG") (RRm/(ore)) or, equivalently, H = =ÖÓ all P and & satisfying Assumptions A3 and A4, we have
n2g20² R'm
GGn RR
for
RVGG Vmn
Vd nyme
E [[(APhasedERM Po)] min L(0'; Ö
RG
Furthermore, our results still hold in the heterogeneous setting (Assumption Al) whenever A S poly(d, 1 1 n m )); the risk guarantee being with respect to any user distribution Ps-
Theorem (Lower bound for SCO). There exists a distribution P and loss & satisfying Assump- lions A3 and A4 such that for any algorithm A satisfying (s, BDDP user-level, we have
RG Vmn
Vd
E [[C(A(S); P)]
min C(O'; = Ω d'Ee
+ RG ny/ms
When G ((ovd),, the upper bound matches the lower bound up to logarithmic factors. We present the algorithm and proof for Theorem 4 in Section 5.1. Theorem 5 is proved in Section 5.2.
5.1 Upper bound: minimizing sequence of regularized ERM problems
We now present Algorithm 4, which achieves the upper bound of Theorem 4. similar spirit to Phased FRM [29] and EpochGD [34], in that at each round we minimize regularized ERM problem with fresh samples and increased regularization, initializing each round from the final iterate of the previous round. This allows us localize the optimum with exponentially increasing accuracy without blowing up our privacy budget. We solve each round using Algorithm 3 to guarantee privacy and obtain approximate minimizer. We show the guarantee in Corollary 2 is enough to achieve optimal rates. We provide the proof Theorem 4 in Appendix F and present a sketch here.
Algorithm 4 APhasedERM: Phased ERM
Require: Private dataset: S = (Si..... Sn) E (Zm)² m i.idd samples from P, H-smooth, convex loss function f, convex set θ c Rdd, privacy parameters & S 1,8 S 1/n?, 2 sub-Gaussian parameter C
1: Set 7 logg( od
Gny/me
17,1
GG nm
me?
2: for = 1 to T do
3: Set n. ,, 4
4: Sample St, n4 users that have not participated previous rounds. Using Algorithm 3, compute an approximate minimizer o,, to the accuracy of Corollary 2, for the objective
Cx. (0:
Σ
E(O,
(w)
||0 0.
(7)
mn, WES,J=
2
6: return BT-
Proof sketch of Theorem The privacy guarantee comes directly from the privacy guarantee of Algorithm 3 and the fact that S, are non-overlapping. The proof for utility is similar to the proof

---

of Theorem 4.8 in [29]. In round of Algorithm 4, we consider the true minimizer of and the approximate minimizer d,. By stability [14],
bound the generalization error of f (see Proposition in Appendix F) and, by Corollary 2, we can bound E| - 0j 1|2. We finally choose {(A,, mg) such that the assumptions of Corollary 2 hold and to minimize the final error.
D
5.2 Lower bound: SCO is harder than Gaussian mean estimation
First of all, note that it suffices prove the lower bounds in the homogeneous setting as any level of heterogeneity only makes the problem harder. Theorem 5 holds for (e, 5) -useer-lev DP-importantly this is setting for which lower bounds are generally more challenging (we provide a related lower bound for E-user-level DP in Appendix A.2). We present the proof in Appendix F.2 and a sketch here.
Proof sketch of Theorem 5. The (constrained) minimax lower bound decomposes into statistical rate and a privacy rate. The statistical rate is optimal (see. e.g.. [44, 2)), thus we focus on the privacy rate. We consider linear losses of the form [(0; 2) - z). We show that optimizing L(0; P) Ep ((; 2 over 0 E ④ is harder than the mean estimation task for P. Intuitively, [(0; P) = (0, I.Z) attains its minimum 0* / | and finding 0* provides good estimate of (the direction of) Z[Z]. We make this formal in Proposition 6. Next, for Gaussian mean estimation, we reduce, in Proposition 3, user-level DP to item-level DP with lower variance by having each user contribute their sample average (which is a sufficient statistic). We conclude with the results of [38] (see Proposition 7) by proving in Corollary 6 that estimating the direction of the mean with item-level privacy is hard.
Acknowledgments
The authors would like to thank Hilal Asi and Karan Chadha for comments on an earlier draft as well as Yair Carmon, Peter Kairouz, Gautam Kamath, Sai Praneeth Karimireddy, Thomas Steinke and Sebastian Stich, for useful discussions and pointers to very relevant references.
References
[1] Acharya, Z. Sun, and H. Zhang. Differentially private Assouad, Fano, and Le Cam. In V. Feldman, K. Ligett, and S. Sabato, editors, Proceedings of the 32nd International Conference on Algorithmic Learning Theory, pages 48-78. PMLR, 16-19 Mar 2021. URL https:// proceedings mlr, 1atps////1//acaaa2211111 htmm.
[2] A. Agarwal, P. L. Bartlett, P. Ravikumar, and M. J. Wainwright. citematiionthhoreet lower bounds on the oracle complexity of convex optimization. IEEE Transactions on Information Theory, 58(5)3223--3444 2012.
[3] N. Ailon and B. Chazelle. Approximate nearest neighbors and the fast eechnson-lnndnsteeee transform. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 557-563, 2006.
[4] K. Amin, A. Kulesza, A. Munoz, and S. Vassilvtiskii. Bounding user contributions: bias- variance trade-off in differential privacy. In International Conference on Machine Learning, pages 263-271, 2019.
[5] Apple Privacy Team. Learning with privacy at scale, 2017. Available at https:
/ /machinelearning wtw.arannnnnnaaenaaneeeeeapppeee wwwp:/pppppp.........poaae.e html.
[6] S. Augenstein, H. B. McMahan, D. Ramage, S. Ramaswamy, Kairouz, M. Chen, R. Mathews, and B. A. y Arcas. Generative models for effective ml on private, decentralized datasets. In International Conference on Learning Representations, 2019.
[7] R. Barber and J. C. Duchi. Privacy and statistical risk: Formalisms and minimax bounds. arXiv: 1412 1412.445/ [math.ST]] 2014.
[8] R. Bassily, A. Smith, and A. Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEFE 55th Annual Symposium on Foundations of Computer Science, pages 464-473. IEEE, 2014.
10

---

[9] R. Bassily, K. Nissim, A. Smith, T. Steinke, U. Stemmer, and J. Ullman. Algorithmic stability for adaptive data analysis. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 1046-1059, 2016.
[10] R. Bassily, V. Feldman, K. Talwar, and A. G. Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, pages 11279- 12288 2019.
[11] R. Bassily, V. Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 4381 -4911. Curran Associates, Inc., 2020. URL https: / https://proceedingg http://roednnn..nuurrrraeee (et.2cdffecca44412222222eeeeeee Pape .df.
wwtpcccpppppcccccccccccceee.eeet ptppppppppr/2000//// 2020/
[12] S. Ben-David, J. Blitzer, K. Crammer, and F. Pereira. Analysis of representations for domain adaptation. Advances in Neural Information Processing Systems 20, 2007.
[13] S. Ben--avvd, T. Lu, T. Luu, and D. Pál. Impossibility theorems for domain adaptation. In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, pages 2010.
[14] O. Bousquet and A. Elisseeff. Stability and generalization. Journal of machine learning research, 29Mar):449-55 -2699 2002.
[15] M. Braverman, A. Garg, T. Ma, H. L. Nguyen, and D. Woodruff. Communication lower bounds for statistical estimation problems via distributed data processing inequality. In Proceedings of the Forty-Eig Annual ACM Symposium on the Theory of Computing, 2016. URL https:t/t///iiii URI. haarg/abs//11 17211
[16] S. Bubeck. Convex optimization: Algorithms and complexity. arXiv preprint arXiv: 1405.4980, 2014.
[17] M. Bun and T. Steinke. Average-cas averages: Private algorithms for smooth sensitivity and mean estimation. Advances Neural Information Processing Systems, pages 181-191, 2019.
[18] T. T. Cai, Y. Wang, and L. Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. arXiv preprint arXiv: 2019.
[19] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Differentially private empirical risk mini- mization. Journal of Machine Learning Research, 126M9r) 2011.
[20] D. Davis and D. Drusvyatskiy. Stochastic mosel- minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):007-239, 2019.
[21] B. Ding, J. Kulkarni, and S. Yekhanin. Collecting telemetry data privately. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. pages 3571-3580, 2017.
[22] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Theory of Cryplography Conference, pages 265-284, 2006.
[23] C. Dwork, G. N. Rothblum, and S. Vadhan. Boosting and differential privacy. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 51-60. IEEE, 2010.
[24] C. Dwork, A. Roth, et al. The algorithmic foundations of differential privacy. 2014.
[25] C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. I.. Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 117-126, 2015.
[26] A. Epasto, M. Mahdian, J. Mao, V. Mirrokni, and L. Ren. Smoothly bounding user contributions in differential privacy. H. Larochelle, M. Ranzato, Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 13999-14010. Curran Associates, Inc., 2020. URL hwwpt:ttps:/tttt httpps://pooeeeddnggg wwwpoeeeediinnne.unni..........e neurips. cctps/p/s/c//ppp///200///////// file/ htt.a///occccd9eeaaaaeaaaaaaadda Paper pdf.
11

---

[27] V. Feldman and T. Steinke. Generalization for adaptively-chosee estimators via stable median. In S. Kale and O. Shamir, editors, ICML, volume 65 of Proceedings of Machine Learning Research, pages 728-757, Amsterdam, Netherlands, 07-10 Jul 2017. PMLR.
[28] V. Feldman and T. Steinke. Calibrating noise to variance in adaptive data analysis. In Conference On Learning Theory, pages 535-544, PMLR, 2018.
[29] V. Feldman, Koren, and K. Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages
2020.
[30] M. Fredrikson, S. Jha, and T. Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In Proceedings the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 1322-1333, New York, NY, USA, 2015. ACM. URL http://doi acm. camm.rrg//00 10. 1 44/110002 2813677.
doi: 10.1 111114///11000.22111
[31] B. Ghazi, R. Kumar, and P. Manurangsi. User-level private learning via correlated sampling. arXiv preprint 17Xiv:2100.11200 2021.
[32] Google. vacy, 2019.
Enabling developers and organizations to use differential pri- Available at https:/ddeveloperss www.opperrggoolllloooooooooooooo http://lllo..om//g//o//oo com/2019/9/ html.
[33] C. Guzmán and A. Nemirovski. On lower complexity bounds for large-scale smooth convex optimization. Journal of Complexity, 31(1):1-14, 2015.
[34] E. Hazan and S. Kale. Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-oovvex optimization. In Proceedings of the 24th Annual Conference Learning Theory, pages 421-436, 2011.
[35] N. Homer, S. Szelinger, M. Redman, D. Duggan, W. Tembe, J. Muehling, J. V. Pearson, D. A. Stephan, S. F. Nelson, and D. W. Craig. Resolving individuals contributing trace amounts of DNA to highly complex mixtures using high-density SNP genotyping microarrays. PLoS Genetics, 4(8)=e1000167, 2008
[36] C. Jin, P. Netrapalli, Ge. S. M. Kakade, and M. I. Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. 19X20:9902003766 [math. PRJ. 2019.
[37] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, et al. Advances and open problems federated learning. Foundations and Trends in Machine Learning, 14(1-2): 1-0000 2021. ISSN 1935-8237. doi: 10.1 00.161/2200000083, URLhttp: / http://xxxxxiiooooooooooooo org/ 10. 1561 1501/2200000883.
[38] G. Kamath, J. Li, V. Singhal, and J. Ullman. Privately learning high-dimensional distributions.
In Conference on Learning Theory, pages 1853-1902. PMLR, 2019.
[39] G. Kamath, V. Singhal, and J. Ullman. Private mean estimation of heavy-tailed distributions. In J. Abernethy and S. Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 2204-2233 PMLR, 09-12 Jul 2020.
[40] V. Karwa and S. Vadhan. Finite sample differentially private confidence intervals. 9th Innova- lions in Theoretical Computer Science Conference (ITCS 2018), 2018
[41] M. Kearns, Efficient noise-tolerant learning from statistical queries. Journal of the Association for Computing Machinery, 45(6):983-1006, 1998.
[42] D. Kifer, A. Smith, and A. Thakurta. Private convex empirical risk minimization and high- dimensional regression. In Conference on Learning Theory, pages 25-1. JMLR Workshop and Conference Proceedings, 2012.
[43] A. Kulunchakov and J. Mairal. Estimate sequences for stochastic composite optimization: Vari- ance reduction, acceleration, and robustness to noise. Journal of Machine Learning Research, 21(155):1-5,, 2020.
12

---

[44] D. Levy and J. C. Duchi. Necessary and sufficient geometries for gradient methods. In Advances in Neural Information Processing Systems 32, 2019. URL https::/aaxxv..rg////a../ 10455.
[45] J. Liu and K. Talwar. Private selection from private candidates. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. pages 298-309, 2019.
[46] Y. Liu, A. Theertha Suresh, F. Yu, S. Kumar, and M. Riley. Learning discrete distributions: user vs item-level privacy. In Advances in Neural Information Processing Systems, 2020.
[47] Y. Mansour, M. Mohri, and A. Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In Proceedings of the Twenty Second Annual Conference on Computational Learning Theooy, 2009.
[48] H. B. McMahan, G. Andrew, U. Erlingsson, S. Chien, I. Mironov, N. Papernot, and P. Kairouz. general approach to adding differential privacy to iterative training procedures. arXiv preprint arXiv: arXiv:1812.066 1812.06210 10, 2018.
[49] H. B. McMahan, D. Ramage, K. Talwar, and L. Zhang. Learning differentially private recurrent language models. International Conference on Learning Representations, 2018.
[50] Mei, Y. Bai, A. Montanari, et al. The landscape of empirical risk for nonconvex losses. The Annals of Statistics, 46(6A):2747-2774, 2018.
[51] S. Shalev-Shwart O. Shamir, N. Srebro, and K. Sridharan. Stochastic convex optimization. In Conference on Learning Theory, 2009.
[52] R. Shokri and V. Shmatikov.
deep learning. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 1310-1321, 2015.
[53] A. Smith. ceedings of the forty-third annual ACM symposium on Theory of computing, pages 813-822, 2011.
statistical estimation with optimal convergence rates. In Pro-
[54] A. T. Suresh, F. X. Yu, S. Kumar, and H. B. McMahan. Distributed mean estimation with limited communication. D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3329-3337, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
[55] United States Census Bureau. Statistical safeguards, 2018. Available at https: census. httpaa///pp.ccceeeeeeaa////eee/e saafattssssstlssssauuuraasee html.
[56] R. Vershynin. High Dimensional Probubility; An Introduction with Applications in Data Science. Cambridge University Press, 2019.
[57] M. J. Wainwright. High-Diiensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019.
[58] 7.. Wang, M. Song, 7. Zhang, Y. Song, Q Wang, and H. Qi. Beyond inferring class represen- tatives: User-level privacy leakage from federated learning. In JEEE INFOCOM 2019-IFFE Conference Computer Communications, pages 2512 2520. IEEF, 2019.
[59] R. J. Wilson, C. Y. Zhang, W. Lam, D. Desfontaines, D. Simmons- and B. Gipson. Differentially private SQL with bounded user contribution. Proceedings on Privacy Enhancing Technologies, 2:230-250, 2020.
[60] B. Woodworth, K. K. Patel, and N. Srebro. Minibatch vs local SGD for heterogeneous distributed learning. In Proceedings of the 37th International Conference on Machine Learning, 2020.
[61] B. F. Woodworth, Wang, A. Smith, B. McMahan, and N. Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. In Advances in Neural Information Processing Systems 31, 2018
[62] B. Yu. Assouad, Fano, and Le Cam. In Festschrift for Lucien Le Cam, pages 423-435. Springer- Springer-Verlag, 1997.
13

---

[63] Y. Zhang, J. Duchi, M. I. Jordan, and M. J. Wainwright. Coormation-theoretii lower bounds for distributed statistical estimation with communication constraints. In C. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013, URL https: pto.//eirc........ Paper. .ap.r.pdf....
14


Reviews:
[{"review_id": "nX58SapHjTz", "reviewer": "Reviewer_7Pkz", "summary": "The paper proposes a new private mean estimation mechanism with estimation error proportional to the concentration radius of queries. The mechanism is applied to stochastic optimization algorithms to solve user-level private empirical risk minimization (ERM) and user-level private stochastic convex optimization (SCO) with improved performance for concentrated queries. \nContributions:\n1. A new private mean estimation mechanism with error scaling with query concentration radius.\n2. New algorithms for user-level private ERM and user-level private SCO with error scaling with concentration radius of gradients.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The core of the paper is a private mean estimation algorithm with error scaling with concentration radius instead of problem dimension. By applying the mean estimation mechanism in SGD based optimization algorithms, one can solve user-level private ERM and user-level \n private SCO with error scaling with gradient concentration radius. Overall the contribution of all the results combined seems enough for a publication.\n\nStrengths:\n1. A new private mean estimation is proposed with good utility guarantees.\n2. New private optimization algorithms with good utility guarantees for concentrated gradients.\n\nWeaknesses:\n1. For the limited heterogeneity setting, the maximum degree of allowed heterogeneity is not very clear. More specifically, it might be better to explicitly write down the maximum possible rate of \\Delta in Corollary 1, Theorem 3, etc. Or the authors could put \\Delta in the bounds to make it more clear. More discussion should be put on heterogeneous settings in these bounds since for user-level DP, it is too optimistic to assume homogeneous distributions.\n2. It seems user-level DP in the homogeneous setting does not have much difference from sample-level DP.\n\n-----------------after rebuttal---------------------\n\nThanks for the response, my concerns are addressed.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "e4CWLPMVXaW", "reviewer": "Reviewer_GqWK", "summary": "This paper provides algorithms for various learning tasks under the constraint of user-level differential privacy. Specifically, they provide solutions for problems like mean estimation, empirical risk minimisation, stochastic convex optimisation, and learning hypothesis classes with finite metric entropy. They also provide lower bounds showing optimality of their algorithms for mean estimation and stochastic convex optimisation for different settings.\n\nFor mean estimation, they consider 1D distributions (and extend to higher dimensions, too) that are bounded within an interval, but are concentrated in some smaller sub-interval. Using this, they show that for uniformly concentrated queries, they can adaptively answer $K$ queries with a small privacy cost depending polynomially in the concentration parameter ($\\tau$) and $K$.\n\nFor empirical risk minimisation and stochastic convex optimisation, they assume that each user's data is drawn i.i.d. from different distribution, such that all the distributions are close in TV distance.\n\nThey also show that even when each user contributes infinite samples, there would still be some error.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Update: On the authors' response, I have decided to update my final evaluation.\n\nStrengths:\n1. The paper studies these problems under a more stringent notion of user-level differential privacy. This is not just building up on prior work incrementally.\n2. The math involved is fairly rigorous, and the paper is technical enough for this conference.\n3. The methods and frameworks provided in Theorems 2 and 3 are fairly simple, hence practical.\n4. The paper feels fairly well-written to me, with all the preliminaries provided properly.\n5. Algorithm 4 looks quite neat. It is simple and efficient, and uses their own algorithm for empirical risk minimisation.\n6. Their results are optimal, at least for two types of problems under distributional assumptions.\n7. The algorithms run in polynomial time as well.\n8. They claim to have addressed the comments that they received in their previous submission.\n\nWeaknesses:\n1. The methods are simple, which is a good thing, as I said. They seem fairly standard though, so in those terms, the algorithms don't seem super novel.\n2. Assumption 3 looks very strong to me. How realistic is that?\n\nOther comments/questions:\n1. In lines 66-68, they say that the mean estimation papers of Kamath et al. use $\\ell_\\infty$ concentration assumptions. Is that really true? The concentration happens in $\\ell_2$ norm for both papers, I think. Like think of a standard, high-dimensional Gaussian. The decay is the same in all directions, so the distribution can be visualised as an $\\ell_2$ ball. Maybe, I'm missing something?\n2. In equation (2), $S_u \\sim P_u^m$ instead of $P_u$?\n3. It will be better to say what the randomness is over in Assumption 4.\n4. Line 198 should end with \"minimize\".\n5. Line 295 should read as \"Furthermore, our results still hold...\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, they have. But they don't seem too negative in the sense that there are limits of differential privacy in terms of practice right now. They may be overcome in future.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "6kcndb0i-Ab", "reviewer": "Reviewer_Vtrv", "summary": "This paper deals with DP in a setting where all users contribute m datapoints to the given dataset, and the curator wishes to maintain DP on a user-level. The main result of the paper is a SGD algorithm (or an iterative aggregator) in which for each user the m datapoints are averaged then an update step takes place w.r.t the avg. Utility bounds for the approach are given in Thm 3 and 4. In addition the authors give a (close) lower bound in Thm 5.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "On the one hand, I really like the idea of DP for user-level privacy. Moreover, the \"crux\" of the paper is the clever observation that averaging the m datapoints of the user reduces the variance in the mean to about 1/\\sqrt m, so less noise is needed under assumption A2 (and presumably also under A1). So, there's true novel observation in the paper.\n\nOn the other hand, I am uncertain whether the assumption that each user contributes *exactly* m points sampled i.i.d (or close to i.i.d) isn't too restrictive in some sense. I guess one can always average the m_i datapoints contributed by the user and check whether those are (roughly) within distance of 1/\\sqrt{m_i} of one another (and if not - replace the avg with zero) and add noise proportional to 1/\\epsilon\\sqrt{m_i} --- it's just that the utility analysis gets hairier (presumably). \n\nBut all in all, this is a solid contribution on an interesting problem, so I vote for acceptance.\n\nSome wording comments:\n*Line 41: you mean - in the central model of DP?\n* Lines 54-8: I'd be very careful in arguing anything about how the \"real world\" behaves. Some rewording is in order, especially since the idea here doesn't really come across clearly. \n* Alg2: Each x_i \\in [-B,B]^d (not ^n)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Irrelevant.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "Refuse to time myself."}, "extra_text": {}}, {"review_id": "18St6NK557v", "reviewer": "Reviewer_QMQQ", "summary": "The paper studies learning problems under so-called user-level differential privacy: in this setting, each one of n users holds m data points of the training set. This type of privacy then requires that under a change of *any number of data points belonging to a single user*, the distributions over the outputs of the algorithm are close in the sense of (epsilon, delta)-DP. A trivial way this could be achieved is group-privacy, where the privacy parameters would degrade linearly with the number of samples m. \n\nThe paper first gives a private mean estimation algorithm for the 1-dimensional case, which, given an input dataset that is both bounded in [-B,B] and (tau, gamma)-concentrated (that is, with probability gamma all points are within tau of a center point), returns an estimate that is close to the empirical mean plus a Laplace noise term of order tau/epsilon*n. This is then extended to the d-dimensional setting, using a random rotation of the data to ensure that each dimension is bounded appropriately in ell-2 norm rather than the ell-infty norm, and using the 1-dimensional solution on each dimension. Both these algorithms are *not* user-level DP but are used in the rest of the paper as building blocks of user-level DP algorithms.\n\nThe first application of these is a user-level DP d-dimensional mean estimation algorithm which, given samples from a distribution P supported on the euclidean ball with radius B, has squared ell-2 error in the order of sqrt{Var(P)/(m*n)}+\\sqrt{d}*B/(\\sqrt{m}*n*epsilon). The error due to privacy in this result degrades with 1/\\sqrt{m} rather than being independent of m which is what the trivial approach would give us.\n\nUsing these tools, the authors then present user-level DP algorithms for empirical risk minimization with smooth convex, strongly convex, and non-convex losses as well as for stochastic convex optimization (SCO) with subgaussian gradients, demonstrating this improvement of 1/sqrt{m} in the error bounds.\n\nThey finally prove lower bounds that show that both the latter result on SCO (although not in all generality) as well as the d-dimensional user-level DP mean estimation bound are tight.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- I think that the paper is very well motivated by practical applications and studying the effect of multiple user entries is meaningful.\n- The paper includes a variety of results for learning problems under user-level DP (even slightly more than described above) which makes it a useful extensive study of this notion.\n- It is generally well written.\n\nWeaknesses:\n- It appears that the techniques used in the paper are not particularly surprising, as the mean estimation algorithms which are used as building blocks for the rest of the results are mostly based on the known approach of Karwa-Vadhan, and the way this is extended to the user-level DP algorithm is by taking the average of the contributions of each user and applying the algorithm above. The random projection trick in the d-dimensional mean estimation case is nice. That said, this collection of results requires detailed work and I find that the results themselves are valuable enough.\n\n*Detailed comments/typos:*\n- How necessary is the bound B in the mean estimation result? The Gaussian mean estimation of Karwa-Vadhan (and in general the stable-histogram algorithm) works even for infinite number of bins using (epsilon,delta)-DP. Would it be possible to state your results more generally?\n- I understand that the TV-closeness statements help in the results about in the limited heterogeneity setting, but I would have found a statement of the form “w.p. 1-beta, the error is…” easier to parse. Perhaps adding these after the theorem statements might help.\n- line 35: I actually found the phrase “does not significantly change if any single element of a user’s data changes” in the intro confusing. If we know that only one data point changes then neighboring datasets satisfy the classic definition of adjacency that we have in DP. It is made clear by the previous and later more formal definitions but perhaps you might want to revise this particular phrase.\n- line 198: wishes to minimizes -> wishes to minimize\n- Algorithm+Theorem 2: Shouldn’t both alpha (the desired failure probability) and gamma (the concentration failure probability) be inputs to the algorithm? The algorithm takes only gamma and the theorem only alpha.\n- line 234: Z in the expectation is not defined close to the theorem.\n- Minor: The use of mu for mean and strongly convexity and the use of H for the Hadamard matrix and smoothness parameter could maybe be avoided.\n- Algorithm 3+Corollary 2: Again alpha is set but is not used in the algorithm as an input.\n-line 322: lossesof -> losses of\n-line 754: In Lemma 2, the maximum on the LHS is over i but the RHS does not have a quantifier (which i is it for?). I think it should be replaced by a “for all i: ||Uz_i||_infty<=…||z_i||_2…”\n-line 763: delta->alpha\n\n===================\n\nThank you for the response --  I still recommend acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Sufficiently discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper deals with DP in a setting where all users contribute m datapoints to the given dataset, and the curator wishes to maintain DP on a user-level. The main result of the paper is a SGD algorithm (or an iterative aggregator) in which for each user the m datapoints are averaged before an update step takes place w.r.t the avg. The reviewers agree that this is an interesting paper with solid contribution.
Decision: Accept (Poster)