acceptodds
Under review as a conference paper at ICLR 2027

Learning with User-Level Local Differential Privacy

Abstract

User-level privacy is important in distributed systems. Previous research primarily focuses on the central model, while the local models have received much less attention. Under the central model, user-level DP is strictly stronger than the item-level one. However, under the local model, the relationship between user-level and item-level LDP becomes more complex, thus the analysis is crucially different. In this paper, we first analyze the mean estimation problem and then apply it to stochastic optimization, classification, and regression. In particular, we propose adaptive strategies to achieve optimal performance at all privacy levels. Moreover, we also obtain information-theoretic lower bounds, which show that the proposed methods are minimax optimal up to logarithmic factors. Unlike the central DP model, where user-level DP always leads to slower convergence, our result shows that under the local model, the convergence rates are nearly the same between user-level and item-level cases for distributions with bounded support. For heavy-tailed distributions, the user-level rate is even faster than the item-level one.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
user-level LDP, minimax optimax algorithm, heavy-tailed distribution, statistical analysis

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_nJL1OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies learning under user-level LDP, where each of n users holds m samples and releases only a privatized message based on their entire local dataset. The authors first develop nearly minimax-optimal methods for one- and high-dimensional mean estimation across different privacy regimes, and then extend these ideas to stochastic optimization, nonparametric classification, and regression.

Critical strengths

S1. The paper studies an important and relatively underexplored privacy model.
User-level local differential privacy is highly relevant when each user contributes multiple observations, yet it has received much less attention than either item-level LDP or user-level central DP.

S2. The main statistical message is interesting.
The paper shows that, under the authors' i.i.d. user-sampling model, user-level and item-level LDP can have nearly the same convergence rates for bounded distributions. For heavy-tailed mean estimation, the user-level rate can even be faster.

S3. The paper covers a broad range of statistical problems.
Starting from mean estimation, the authors consider high-dimensional mean estimation under different support geometries, stochastic optimization, nonparametric classification, and regression.

Critical weaknesses

W1. The statistical model is much more restrictive than the motivating user-level/federated-learning setting.
The paper assumes that all data are i.i.d. from a common distribution. In realistic user-level or federated settings, observations from the same user are often dependent, and different users can have heterogeneous distributions. It is unclear whether the main conclusions survive under even mild within-user dependence or user heterogeneity.

W2. Beyond the mean-estimation primitive, several extensions appear largely reduction-based.
The paper is broad, but I am less convinced that all of these applications provide substantial new methodological ideas beyond the core mean estimation result.

W3. There is no empirical evaluation.
The paper is entirely theoretical. Even for a theory-focused ICLR submission, numerical experiments would be valuable for illustrating the claimed phase transitions, the finite-sample effect of mm, the transition between privacy regimes, and the practical gap between the upper bounds and actual performance.

W4. Several results rely on strong assumptions or knowledge of problem parameters.
The bounded-mean results assume a known support radius DD, the heavy-tailed results rely on moment conditions, stochastic optimization assumes strong convexity and almost surely bounded gradients, and the nonparametric results impose Holder smoothness. It is not clear which tuning parameters require these quantities to be known, or whether adaptive versions are possible.

W5. The presentation is not sufficiently polished.
The paper would benefit from a substantial language and technical-editing pass.

Questions for authors

See weaknesses

Reviewer_La2eOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies statistical learning under user-level LDP, where each user holds multiple observations and privacy protection applies to the entire dataset of each user. Unlike in the central DP model, the relationship between user-level and item-level privacy under LDP is more complicated, as users can process their observations jointly before privatization. The authors consider several statistical problems, including mean estimation, stochastic optimization, nonparametric classification and regression, and develop privacy mechanisms tailored to different privacy budgets. They derive upper bounds on estimation errors and corresponding information-theoretic minimax lower bounds, showing that the proposed methods achieve optimal convergence rates up to logarithmic factors under certain assumptions. It is claimed that user-level LDP can achieve nearly the same convergence rates as item-level LDP for bounded-support distributions, given the same total number of observations. In addition, user-level LDP can achieve faster rates for mean estimation under heavy-tailed distributions.

Critical strengths
  • Covers several important statistical learning problems under user-level LDP, including mean estimation, stochastic optimization, nonparametric classification and regression, offering a unified approach to these problems.
  • Provides upper bounds on estimation errors and corresponding information-theoretic minimax lower bounds, showing that the proposed methods achieve nearly optimal convergence rates up to logarithmic factors.
  • User-level LDP can achieve nearly the same convergence rates as item-level LDP for bounded-support distributions, and even faster rates for heavy-tailed mean estimation.
Critical weaknesses
  • Does not include numerical experiments or simulations to evaluate the practical performance of the proposed methods. Comparisons with existing approaches would help demonstrate their effectiveness and robustness.
  • Assumes that each of the users holds iid observations. In practice, users may have different sample sizes and data distributions. It is unclear how well the proposed methods would work in such settings.
  • Does not discuss the computational or communication complexity of the proposed methods.
  • The literature review misses some relevant recent work, such as

Kent, A., Berrett, T. B., & Yu, Y. (2026). Rate Optimality and Phase Transition for User-Level Local Differential Privacy. Journal of the American Statistical Association, 1–15,

which studies mean and density estimation under user-level LDP. The authors should discuss this work and explain how their contributions differ from the existing results.

  • Does not explicitly discuss the limitations of the proposed methods.
Questions for authors
  • How sensitive are the proposed algorithms to the choice of the support bound DD, especially when the underlying distribution is unknown?
  • Regarding the faster convergence rates than item-level LDP for heavy-tailed distributions: Is the item-level rate used for comparison in Theorem 3 minimax optimal under the same assumption? Is it possible to provide a matching minimax lower bound for user-level LDP or explain more clearly when this improvement holds?
  • The citation commands appear to be used incorrectly in several places, where \citep should be replaced with \citet. For example, "(Acharya et al., 2023) analyzes the discrete distribution…” on page 1. There are also some typos and grammatical errors, such as “it is inevitable in many cases to user larger (\epsilon)” on page 1.
  • Please see the weaknesses for the remaining questions.
Reviewer_mhAKOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This work studies mean estimation and similar problems under user-level local differential privacy. In this setting, a user may contribute multiple datapoints to an algorithm without allowing the algorithm or any outsiders to identify the user. The authors study mean estimation in one and dd-dimensions, stochastic convex optimization (SCO), classification, and regression. They propose a mean estimation algorithm that operates slightly differently depending on the privacy parameter ϵ\epsilon. They claim that differentiating between different privacy regimes is necessary, because the optimal randomization scheme in each is different. They initially provide bounds for this problem when samples from the distributions have bounded ℓ∞\ell_\infty norm, then use Kashin's representation to extend this to ℓ1\ell_1 and ℓ2\ell_2. In addition to these upper bounds, the authors establish nearly-matching lower bounds for mean estimation, proving that they are optimal up to log factors.

The authors then employ their algorithm as a subroutine for SCO, classification and regression. They derive the upper bounds given by these algorithms, and compare them to lower bounds.

Critical strengths
  • The given upper and lower bounds for mean estimation match up to logarithmic factors. This contributes to the significance of the result.
  • The authors prove their algorithm's worth by using them as building blocks to solve other problems. This contributes to the significance of the result.
Critical weaknesses
  • The mean estimation algorithms are quite similar to those of (Bassily and Sun, 2023). They seem to have the same structure, but the proposed algorithms include different cases, to account for different ϵ\epsilon. This may weaken the novelty of the paper.
Questions for authors
  • Can the high privacy results of (Bassily and Smith, 2023) be translated to any constant ϵ\epsilon, rather than only $\epsilon \leq 1, at a cost of a constant factor of accuracy?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.