acceptodds
Under review as a conference paper at ICLR 2027

On the Limits of Sparse Linear Model with Shuffled Differential Privacy

Abstract

Sparse linear regression is a fundamental problem in high-dimensional statistics, and its private counterparts leave a large gap between the central and the local model of differential privacy. Shuffled differential privacy (SDP) sits between the two, offering accuracy closer to the central model without the trust requirement of a central curator. This paper studies sparse linear regression under both non-interactive and interactive SDP protocols. In the non-interactive setting, any non-interactive -SDP protocol is shown to incur an -norm estimation error of with dimension , sparsity , and users, revealing an inherent dimensionality barrier. In addition, a non-interactive algorithm is proposed that achieves an -norm upper bound of . To overcome this barrier, we turn to the interactive user-level setting, where each user holds samples. A two-round interactive algorithm is developed that first recovers the support through a heavy hitter step and then estimates the parameter, achieving an error of with no polynomial dependence on . Furthermore, by extending the score attack framework to user-level data, a new lower bound is established for any user-level -DP, showing that the proposed algorithm is near-optimal with only a gap of the factor .

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
shuffled differential privacy, sparse linear regression, interactive protocols, user-level privacy, heavy hitter, score attack

Reviews

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

The paper studies the private counterpart of sparse linear regression by conisdering the shuffled differential privacy (SDP), under both non-interactive and interactive SDP protocols.

Critical strengths

The paper is well presented and the structure and the contribution are easy to follow. The technical contents look correct and I beleive the contributions are sufficient.

Critical weaknesses

Please refer to the next section.

Questions for authors

I do not use AI-tools to review, so it is likely I miss some of the details and have grammar mistakes since I am not a native speaker. If so, please just indicate what I miss or where I am wrong. Thank you.

Things that i'd prefer to be clarified:

  • Why introducing Assumption 3 at the beginning of Section 4? If it is only used for upper bound for the closed-form solution, it can be deferred.
  • Is introducing Pan-Privacy the kep step/solution to the lower bound part?
  • Is this "Hard Distribution" in Definition 6 entirely novel here, or it has been used in literatur elsewhere?
1 comment

Thank you for your clarifications. You have answered my questions clearly. I have carefully checked your responses to me and the other reviewers. The paper is clear to me, and I only have a minor concern regarding the overall contributions. In any case, I intend to keep my positive score. Thank you.

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

The authors consider the problem of private sparse linear regression. There is already a pretty wide literature on ordinary and sparse linear regression in the standard "central" DP and the very stringent "local" DP which forces the privatization to be done in a federated way. In this paper, the authors consider an intermediate level of privacy called "shuffled" DP, where we assume some trusted party is in charge of shuffling the individual privatized records before the learner aggregates them into a single model. In some learning problems, the leading shuffled DP approach is only as good as the leading LDP approach (shuffling does not improve privacy) and in others shuffled DP approaches yield better utility privacy tradeoffs than LDP (shuffling does improve privacy), sometimes matching CDP, leading to the high-level question: does shuffling improve privacy for sparse linear regression?

The authors prove asymptotic lower bound and upper bounds on the accuracy that can be achieved for private sparse regression in this shuffled DP setting. If I understood them correctly, these bounds place SDP sparse regression somewhere in the middle with asymptotic separation from both CDP and LDP.

Overall, the paper looks very rigorous and seems to prove new results. I think the writing can be improved (e.g., to better explain / advocate for the non-standard shuffled notion of privacy being considered), but to my reading the biggest limitation is that it is not clear (to me) what the significance of the results are / what useful applications they unlock.

Critical strengths

The paper provides a rigorous theory that seems correct to me.

Critical weaknesses

It is not clear to me if SDP is that useful of a notion. To some extent, SDP seems theoretically interesting as a natural middle point between DP and LDP and can help us understand the fundamental limits of those more commonly used notions of privacy, but it is not clear to me if there are any realistic scenarios where we expect to trust an intermediate party enough to have it shuffle the data, but we do not trust this party enough to have it actually run the full private training pipeline.

Also, the paper focuses only on k-sparse regressions. If the goal is to gain an understanding of SDP regressions, what is the added value of focusing on the more complex sparse regression problem?

The algorithms presented in this paper seem to require very strong assumptions on the data to ensure privacy.

Finally, Table 1 presents private linear regression in the standard setting as essentially solved, but there have been significant advances in this problem after that paper (see e.g., Table 2 of https://arxiv.org/abs/2503.24321). Are these the rates for potentially inefficient algorithms / do they require a similar set of assumptions about the subgaussian nature of the samples and the structure of the covariance of the underlying population?

Questions for authors

See above.

1 comment

I thank the authors for answering my questions and for providing better motivation for SDP in their rebuttal. However, I agree with the assessment of reviewer fMp2 that the problem is a bit too specialized / theoretical for ICLR (I agree that on their own, SDP as an exploration of notions of privacy and private linear regression are sufficiently fundamental and applicable problems for ICLR-like settings, but the crossover adds another layer of specialization, requiring a higher bar for the strength of the results / writing).

Therefore, as of right now, I stand by my original score.

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

High-dimensional sparse linear regression (i.e., estimating a linear model where only a small subset of features have non-zero weights among a very large number of total features) exhibits a significant utility gap between the central and local models of differential privacy. While central differential privacy achieves near-optimal estimation accuracy with error growing only logarithmically with the total number of features, it requires users to trust a central server with their raw data. On the other hand, local differential privacy removes the trusted server by perturbing data on each user's device, but incurs an unavoidable estimation error that grows polynomially with the total number of features in both single-round (non-interactive) and multi-round (interactive) sample-level settings, making it impractical when the number of features is significantly larger than the number of samples. This paper studies whether the shuffled differential privacy model, which puts an anonymizing shuffler between users and the server to strip sender identities, can bridge this gap and avoid polynomial dimensionality barriers without relying on a trusted curator. To answer this question, the paper establishes both theoretical lower bounds and algorithmic upper bounds across non-interactive and interactive shuffled settings. First, in the non-interactive sample-level regime (where each user holds a single sample and communicates in one round), the paper reduces robust shuffled protocols to pan-privacy to prove that estimation error still grows with the square root of the total feature dimension, demonstrating an inherent dimensionality barrier akin to local privacy alongside a complementary non-interactive algorithm. Second, to overcome this barrier, the work moves to an interactive user-level setting (where each user holds multiple samples) and designs a 2-round algorithm: the first round identifies the active features using a shuffled heavy-hitter protocol, and the second round estimates the model weights restricted to those selected features, completely eliminating polynomial dependence on the ambient feature dimension. Finally, by extending the score attack framework to user-level datasets, the paper proves a matching information-theoretic lower bound for any user-level DP mechanism, establishing that the proposed two-round shuffled protocol is near-optimal up to logarithmic factors and reduces the privacy error of user-level local differential privacy by a factor of the square root of the number of users.

Critical strengths

The paper provides a clear answer to where shuffled privacy sits between local and central privacy for high-dimensional sparse estimation, establishing a clean separation between single-round sample-level protocols (which suffer from a local-privacy-like polynomial dimension barrier) and multi-round user-level protocols (which achieve central-privacy-like logarithmic dimension scaling). In the user-level setting, the estimation error of the proposed 2-round shuffled algorithm matches the newly derived user-level DP lower bound up to logarithmic factors. This shows that interactive shuffled privacy achieves the same asymptotic accuracy as trusted-curator central privacy while improving upon prior user-level local privacy bounds by a factor of the square root of the number of users.

Critical weaknesses

First, the way the paper overcomes the polynomial dimensionality barrier in the interactive user-level regime relies on overly restrictive per-user sample size and signal-strength assumptions, leaving the sample-level (m=1) and small-sample (m << k) interactive regimes unresolved. Second, the theoretical characterization in the non-interactive sample-level regime remains incomplete, and the paper's narrow statistical scope makes it a borderline fit for ICLR. Specifically, a polynomial gap proportional to the square root of the feature dimension remains between the privacy error of the proposed non-interactive algorithm and the proved lower bound, leaving the exact minimax rate open. There is also an exposition discrepancy between Theorem 1, Theorem 5, and the Introduction (which require "robust" shuffled DP protocols) and the Abstract and Conclusion (which state the lower bound unconditionally for any non-interactive shuffled DP protocol). More broadly, as a purely minimax parameter-estimation study on linear models, the paper's contribution is somewhat specialized and would find a more natural audience at a statistical learning theory such as ALT or COLT.

Questions for authors

Can the authors clarify the discrepancy between Theorem 1 (and Theorem 5), which restricts the non-interactive lower bound to robust shuffled DP protocols, and the Abstract/Conclusion, which state the lower bound unconditionally for any non-interactive approximate shuffled DP protocol? Does the lower bound hold without the robustness assumption?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.