Learning with User-Level Privacy

1 Introduction

• Across the considered tasks, privacy error decreases as O(1/√m) with samples per user, while increasing the number of users n reduces privacy cost at O(1/n).The analyses assume users draw samples i.i.d. from related distributions, a setting the paper calls limited heterogeneity.Source: §1 · p. 2

1.1 Our Contributions and Related Work

• The mean-estimation tool scales error with the concentration radius τ rather than the full range B, and works in arbitrary dimension for ℓ2-concentrated data.It also avoids a superfluous √d factor compared with coordinate-wise application of prior approaches.Source: §1.1 · pp. 2–3
• Under uniform concentration, the method answers adaptively chosen queries with privacy cost proportional to their concentration radius rather than their full range.The paper states guarantees for arbitrary ε, under the additional uniform-concentration assumption.Source: §1.1 · p. 3
• For ERM with users contributing i.i.d. sampled points, privacy cost decreases as O(1/√m) for convex and non-convex losses and O(1/m) for strongly convex losses.The analysis assumes regularity conditions.Source: §1.1 · p. 3
• Under pure DP, finite function classes of size K receive an estimator with excess risk ˜O((log K)/mn + (log K)^(3/2)/(n√mε)).The estimator combines the mean-estimation techniques with the private selection mechanism of [49].Source: §1.1 · p. 3
• With a fixed number of users, risk remains at least Ω(e^(−εn)) regardless of m, even when each user has infinitely many samples.This does not contradict the preceding results, which require n = Ω((log m)/ε).Source: §1.1 · p. 4

2 Preliminaries

• User-level DP treats datasets as neighboring when one user's entire contribution differs, rather than only one individual sample.The paper models each of n users as contributing m samples.Source: §2 · pp. 4–5
• Limited heterogeneity assumes each user's distribution is close in total variation to a shared reference distribution, with Δ measuring the discrepancy.The homogeneous setting is the special case Δ = 0, and the paper develops matching bounds there before extending guarantees to limited heterogeneity.Source: §2 · p. 5

2.1 ERM and stochastic convex optimization

• ERM and stochastic convex optimization use a closed, convex parameter set, G-Lipschitz losses, and assumptions including smoothness and sub-Gaussian gradients.The guarantees assume equal sample counts for simplicity; they extend to unequal counts using the median count, while optimal rates for arbitrary random counts are left open.Source: §2.1 · pp. 5–6

2.2 Uniform concentration of queries

• The query framework defines concentration radius τ and uniform concentration to describe when samples or a family of queries remain concentrated.The paper uses β-closeness to analyze estimators that are usually unbiased and small-noise but bounded otherwise.Source: §2.2 · pp. 6–7

3 High Dimensional Mean Estimation and Uniformly Concentrated Queries

• The private mean estimator scales its privacy cost with concentration radius τ rather than the full range.Its two-stage procedure privately locates an interval around the mean, then clips around it to reduce sensitivity before adding noise.Source: §3 · pp. 7–8
• Random rotation addresses the extra dimension dependence from applying the scalar estimator coordinate-wise to ℓ2-concentrated data.The rotation spreads coordinate ranges, avoiding the superfluous dimension factor described for previous approaches.Source: §3 · pp. 8–9
• Concentration-radius-based estimation yields user-level private mean estimates for ℓ2-bounded distributions with error bounds that are minimax optimal up to logarithmic factors.The stated result applies in the homogeneous setting, and the same bounds extend to estimating each user's mean when heterogeneity is polynomially small.Source: §3 · p. 9

3.1 Uniform concentration: answering many queries privately

• Under uniform concentration, the method answers adaptively chosen queries with privacy cost proportional to their concentration radius.The guarantee covers a sequence of K queries.Source: §3 · p. 7, §3.1 · p. 9

• The ERM method uses sequential gradient queries answered by the private query framework, followed by projected updates.The section presents this as Winsorized First-Order Optimization and provides its privacy and utility guarantees.Source: §4 · pp. 10–11
• Under smoothness and sub-Gaussian-gradient assumptions, the stochastic-gradient query class is uniformly concentrated.The section uses this concentration result to establish the ERM guarantees.Source: §4 · p. 10
• Projected SGD already attains the minimax optimal rate for SCO in the setting considered.The section notes that privacy guarantees also hold for improved first-order algorithms, but does not focus on their convergence-rate improvements.Source: §4 · p. 11
• For ε ≤ 1 and δ > 0, Algorithm 3, when instantiated with any first-order gradient algorithm, satisfies user-level (ε, δ)-differential privacy.Source: §4 · p. 12
• For strongly convex losses, localization places the optimal parameter within the privacy cost in approximately Õ(H/µ) steps.The section notes this is useful for the subsequent SCO analysis.Source: §4 · p. 12

5.1 Upper bound: minimizing a sequence of regularized ERM problems

• Algorithm 4 solves a sequence of regularized ERM problems, using fresh samples and increased regularization at each round.Each round starts from the previous round’s final iterate; the increasing regularization localizes the optimum while controlling the privacy budget.Source: §5 · p. 12, §5.1 · p. 13

5 Stochastic Convex Optimization with User-level Privacy

• The upper-bound result assumes a homogeneous setting and convex, smooth losses satisfying the paper’s stated assumptions.The section also reports an extension when the user distributions are sufficiently close, with risk measured against any user distribution.Source: §5 · p. 12
• The SCO upper bound matches the lower bound up to logarithmic factors under the stated conditions.The upper-bound guarantee is for Algorithm 4, which is user-level (ε, δ)-DP.Source: §5 · p. 12

5.2 Lower bound: SCO is harder than Gaussian mean estimation

• The lower-bound argument can be restricted to the homogeneous setting, since heterogeneity only makes the problem harder.It establishes a lower bound for (ε, δ)-user-level DP, a setting the authors identify as generally more challenging for lower bounds.Source: §5.2 · p. 13
• The lower-bound argument reduces SCO with linear losses to estimating the direction of a distribution’s mean, then invokes hardness for private mean estimation.The statistical rate is treated as optimal, so the proof focuses on the privacy rate.Source: §5.2 · pp. 13–14

6 Function Classes with Bounded Metric Entropy under Pure DP

• For bounded-loss classes with finite metric entropy, the paper presents a private estimator and an information-theoretic lower bound.The setting includes classes with a finite cover under a specified norm.Source: §6 · p. 14

6.1 Combining mean estimation and private selection

• The estimator combines the paper’s private mean estimator with private selection among candidate parameter values.Private selection releases noisy values for candidate losses and returns an approximate minimum.Source: §6 · p. 14
• The idealized estimator is not computationally efficient and can be intractable when the parameter set is exponential in dimension.Its running time roughly scales as |Θ|/α to obtain accuracy with probability greater than 1−α.Source: §6.1 · p. 15
• Algorithm 5 is ε-user-level DP and has a stated utility guarantee derived from the mean estimator and private selection.The theorem presents the guarantee with probability greater than 1−α; the supplied passage does not include its full bound.Source: §6.1 · p. 15

6.2 Information-theoretic lower bound

• The finite-hypothesis upper and lower bounds match only up to a √log K factor, and the bound is tight only for small hypothesis classes.The authors leave finding an optimal estimator for this setting to future work.Source: §6.2 · p. 16

Discussion

• The paper’s generalization guarantees rely on limited heterogeneity, and its algorithms are not runtime-optimized.The authors identify extending the results to more heterogeneous settings and developing faster algorithms as future directions.Source: Discussion · p. 17
• For SCO, the paper compares its algorithm’s runtime with the runtime needed to achieve the optimal item-level private rate.The supplied runtime expression for the user-level algorithm is incomplete, but the stated comparison motivates faster algorithms as future work.Source: Discussion · p. 17

A Limit of Learning with a Fixed Number of Users

• The fixed-user analysis considers two possible sample sets per user and uses the group property of DP to relate the algorithm’s outputs on the two datasets.The theorem concerns a binary testing problem under user-level (ε, δ)-DP.Source: A Limit of Learning with a Fixed… · pp. 23–24

B Extension to Limited Heterogeneity Setting

• Applying the algorithms designed for the i.i.d. setting in a black-box fashion works under limited heterogeneity with an additional bounded error.When ∆ is below the stated threshold, performance matches the homogeneous case up to constant factors.Source: B Extension to Limited Heterogeneity… · pp. 24–25

C.1 Private range estimation

• Private range estimation divides [−B, B] into bins of width 2τ and maps each observation to its nearest midpoint.The procedure then samples a midpoint according to a distribution described in the algorithm.Source: §C.1 · p. 26

C.2 Proof of Theorem 1

• Algorithm 1 is ε-DP and runs in time O~(n + log(B/τ)).Theorem 1 states a utility guarantee when the data is (τ, γ)-concentrated, but the supplied theorem passage truncates before giving its form.Source: §C.2 · p. 26

C.3 Proof of Theorem 2

• Random rotation converts ℓ2 concentration into ℓ∞ concentration up to logarithmic factors, supporting coordinate-wise estimation with Algorithm 2.Theorem 2 states an (ε, δ)-DP guarantee for Algorithm 2 on data concentrated in ℓ2 norm, but its estimator bound is truncated.Source: §C.3 · pp. 26–27

C.4 Proof of Corollary 1

• For Gaussian data, user-level mean estimation reduces to item-level estimation on each user’s sample average, with the same performance.The sample mean is sufficient for i.i.d. Gaussian samples; the proof also uses this reduction to establish the tightness of Corollary 1’s privacy term.Source: §C.4 · p. 29

C.5 Mean Estimation of Sub-Gaussian Distribution

• The sub-Gaussian mean-estimation bound is tight up to logarithmic factors.The cited lower bounds concern mean estimation for bounded random variables under (ε, δ)-DP.Source: §C.5 · p. 30

C.6 Proof of Theorem 3

• Theorem 3’s proof composes privacy across queries and uses per-query utility guarantees with a union bound over the K queries.Its privacy argument invokes the strong-composition theorem.Source: §C.6 · p. 30

D.1 Uniform Concentration

• The uniform-concentration proof uses a covering-number argument over the bounded parameter set Θ.The proof takes a finite Δ-net whose cardinality is bounded in terms of the dimension and radius.Source: §D.1 · p. 31

D.2 Stochastic gradient algorithms

• For an H-smooth function and stochastic first-order gradient oracle with variance bounded by ν², convergence guarantees are stated for convex [18, Theorem 6.3] and µ-strongly-convex [46, Corollary 32] cases.Source: §D.2 · p. 32

D.3 Proof of Theorem 4

• For ε ≤ 1 and δ > 0, Algorithm 3 with any first-order gradient algorithm is (ε, δ)-user-level DP.The supplied theorem statement also mentions guarantees under A1 when Δ meets a polynomial bound, but the bound is truncated.Source: §D.3 · p. 33
• The gradient-estimation steps are T adaptively chosen queries, so the privacy proof follows from Theorem 3.Source: §D.3 · p. 33
• The utility argument uses concentration of the gradients and the utility guarantee for answering the queries.The supplied passages do not provide the resulting utility bound.Source: §D.3 · p. 33

E.1 Proofs for Theorem 5

• Regularized ERM has generalization guarantees for convex, G-Lipschitz losses satisfying Assumption A4.The proof combines convex analysis with stability arguments.Source: §E.1 · pp. 33–34
• Algorithm 4 is user-level (ε, δ)-DP under the stated theorem setup.The utility expression following the theorem’s assumptions is truncated in the supplied passages.Source: §E.1 · p. 35
• Under A1, the results extend to heterogeneous settings when Δ satisfies the stated threshold, with risk measured against any user distribution Pu.The threshold itself is truncated in the supplied passages.Source: §E.1 · p. 35

E.2 Proofs of Theorem 6

• Theorem 6 gives a lower bound for some distribution and loss satisfying Assumptions A3 and A4.The lower-bound expression is truncated in the supplied passage.Source: §E.2 · p. 36
• The lower-bound construction uses ℓ∞-truncated Gaussians, obtained by projecting Gaussian mass outside the bounded hyperrectangle back coordinate-wise.Source: §E.2 · p. 36
• The SCO-to-Gaussian-mean-estimation reduction applies when G is sufficiently large relative to the mean norm, so clipping is rare.Under this condition, the truncated and untruncated Gaussian means are exponentially close in ℓ2 norm.Source: §E.2 · p. 37
• For Gaussian samples, user-level estimation with m samples per user reduces to item-level estimation on n user averages, with variance divided by m.The proof relies on the sample mean being sufficient when the Gaussian variance is known.Source: §E.2 · p. 39
• The adapted lower bound concerns estimating the direction of the mean, rather than only estimating the mean itself.The construction modifies the cited result because its original lower bound does not guarantee the required range for the mean norm; the excluded event has exponentially small probability in d.Source: §E.2 · p. 39

F.1 Proofs from Section 6.1

• Algorithm 5 is ε-user-level differentially private, as established by applying Theorem 3.2 in [49] to its ε/3-user-level private components.The proof states that each A_k is ε/3-user-level DP.Source: §F.1 · p. 40
• The utility proof combines uniform concentration, querying the best hypothesis, a bound on the number of queries, and a Laplace-noise bound to control the output's suboptimality.The excerpt gives a suboptimality bound beginning with 16τ, but its remainder is truncated.Source: §F.1 · pp. 40–41

F.2 Proofs from Section 6.2

• Theorem 8 sets up a finite-hypothesis lower-bound instance under conditions on K, m, n, ε, and B, with a sample space of size ⌈log2 K⌉.The theorem statement excerpt ends before specifying the bound itself.Source: §F.2 · p. 42
• The lower-bound proof computes separation between hypotheses, bounds private testing error, and adapts the argument to user-level privacy using m-fold product distributions.The proof describes a packing-based family of distributions and identifies the user-level adaptation as replacing P_v with P_v^m.Source: §F.2 · pp. 42–43