PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Limits of Sparse Linear Model with Shuffled Differential Privacy

Yan Zhang, Jiong Tuo, Meng Ding, Yuheng Ma, Di Wang

arXiv:2610.32822v2cs.LG

TL;DR

Sparse linear regression under privacy lies between central and local differential privacy, but the shuffled model's dimensional behavior is unresolved. The paper analyzes non-interactive SDP and develops a two-round interactive user-level algorithm; its interactive upper and lower bounds differ by a log(d/k) factor.

  • Problem

    The paper asks whether shuffled privacy makes sparse linear regression behave more like central DP or retains the dimension-dependent barriers of local DP.

    Source: §1 · p. 2

  • Method

    It studies non-interactive SDP and develops U2R, a two-round interactive algorithm for the user-level setting.

    Source: §1 · p. 3

  • Results

    Non-interactive SDP has a dimension-dependent lower bound, while the interactive user-level upper and lower rates differ by a factor of log(d/k).

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    With interaction and user-level data, the problem is more closely related to central DP, and U2R is near-optimal within the stated logarithmic factor.

    Source: §1 · p. 3

    The non-interactive setting retains polynomial dependence on d, and closing the gap between its bounds is left to future work.

    Source: §4.2 · p. 6

Abstract

from arXiv · show

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 $(\epsilon,\delta)$-SDP protocol is shown to incur an $\ell_2$-norm estimation error of $\Omega( \frac{\sqrt{dk}}{n\epsilon} )$ with dimension $d$, sparsity $k$, and $n$ users, revealing an inherent dimensionality barrier. In addition, a non-interactive algorithm is proposed that achieves an $\ell_2$-norm upper bound of $\tilde{\mathcal{O}}( \sqrt{\frac{k}{n}} + \frac{d\sqrt{k}}{n\epsilon})$. To overcome this barrier, we turn to the interactive user-level setting, where each user holds $m$ 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 $\tilde{\mathcal{O}}( \sqrt{\frac{k}{nm}} + \frac{k}{n\sqrt{m}\epsilon} )$ with no polynomial dependence on $d$. Furthermore, by extending the score attack framework to user-level data, a new lower bound $\Omega( \sqrt{\frac{k\log(d/k)}{nm}} + \frac{k\log(d/k)}{n\sqrt{m}\epsilon} )$ is established for any user-level $(\epsilon,\delta)$-DP, showing that the proposed algorithm is near-optimal with only a gap of the factor $\log(d/k)$.

1 INTRODUCTION

Shuffled differential privacy (SDP) offers a middle ground between central and local privacy for sparse linear regression, where the central question is whether it avoids the dimension dependence associated with local privacy. The paper characterizes non-interactive limits and develops an interactive user-level approach whose bounds are near-optimal up to a log(d/k) factor.

1 INTRODUCTION

  • SDP uses a shuffler to de-identify and permute local messages, aiming for accuracy closer to central DP without a trusted curator.The paper frames SDP as a middle ground between central and local privacy.Source: §1 · pp. 1–2
  • The paper focuses on estimating a k-sparse linear-model parameter in high dimensions, where avoiding error that scales polynomially with d is a central challenge.The setting allows d to far exceed the sample size n.Source: §1 · p. 2
  • Non-interactive SDP has an estimation-error lower bound with an inherent dimensionality barrier, and the proposed algorithm provides an upper bound that characterizes those limits.The lower bound is established for any non-interactive protocol; the passage does not provide the complete rate expression.Source: §1 · pp. 2–3
  • The interactive user-level algorithm uses two rounds and achieves an upper bound, while the corresponding lower bound differs by only a factor of log(d/k).Each user holds m samples; the upper bound is reported as near-optimal.Source: §1 · p. 3
  • Across privacy budgets, dimensions, and user counts, U2R has the lowest coefficient error and mean squared error among the private methods evaluated.The evaluation uses synthetic and real data.Source: §1 · p. 3

2 RELATED WORK

The related-work review positions shuffled DP between central and local privacy, whose sparse-regression guarantees differ in their dependence on dimension. It identifies sparse linear regression in the shuffled model as an open application area addressed by this paper.

2 RELATED WORK

  • Central sparse estimation typically has logarithmic dependence on d, whereas local estimators exhibit polynomial dependence on d.The review also notes that user-level multi-sample regimes can alleviate local-model costs.Source: §2 · p. 3
  • Shuffled DP combines privacy amplification and multi-message summation, but its theory resembles central DP for some problems and local DP for others.The review cites histogram estimation and parity learning as contrasting examples.Source: §2 · p. 3
  • Prior shuffled-DP work covers primitives such as heavy hitters, while its application to sparse linear regression remains largely open.The paper identifies this gap as the focus of its study.Source: §2 · p. 3

3 PRELIMINARIES

The preliminaries establish the notation and assumptions for sparse linear regression, then distinguish privacy definitions and protocol settings. They define sample-level and user-level records and specify the sparse-model and covariance conditions used in the analysis.

3 PRELIMINARIES

  • The paper defines vector and matrix notation, including support as the indices of nonzero coordinates, and uses O and Ω in their standard sense.The notation also defines norms, the minimum eigenvalue, sub-Gaussian variables, and Õ as suppressing logarithmic factors.Source: §3 · p. 3

3.1 DIFFERENTIAL PRIVACY

  • In the user-level regime, neighboring datasets differ in one user's entire local dataset of m samples.In the sample-level regime, one record is a single (x_i, y_i) pair.Source: §3.1 · pp. 3–4
  • A shuffled-DP protocol comprises a local randomizer, a shuffler that uniformly permutes messages, and an analyzer that maps the shuffled view to an output.Protocols may be non-interactive, with one round, or interactive, with later randomizers depending on earlier aggregated outputs.Source: §3.1 · p. 4

3.2 PROBLEM SETUP

  • The regression setting assumes i.i.d. samples from a mean-zero-covariate linear model with conditionally mean-zero sub-Gaussian noise and a k-sparse, bounded-norm parameter.The covariance assumption bounds the sub-Gaussian norm of the whitened covariates.Source: §3.2 · p. 4

4 UNDERSTANDING THE LIMITATIONS IN NON-INTERACTIVE SDP

The section establishes a minimax error lower bound for non-interactive shuffled DP and presents an algorithm, while showing that polynomial dependence on dimension remains. Its lower-bound strategy uses pan-privacy, and its upper-bound approach relaxes sparse least squares to control local noise.

4.1 LOWER BOUND

  • Theorem 1 establishes a minimax ℓ2-error lower bound for robust non-interactive shuffled-DP protocols, under δ=o(1/n).The proof route converts robust shuffled DP to pan-privacy; pan-privacy protects against observing the output together with an internal state at one point in the stream.Source: §4 · p. 4, §4.1 · p. 5
  • Shuffling makes the stated lower bound smaller than the local-DP bound by a factor √n log d, but the dimension dependence remains.The section attributes this remaining dependence to per-coordinate noise that shuffling rescales but does not remove.Source: §4.1 · p. 6
  • Non-interactive shuffled-DP estimation retains polynomial dependence on d, the main bottleneck when d is much larger than n.The section contrasts this with central DP, where dimension enters logarithmically through support identification.Source: §4.1 · p. 6

4.2 UPPER BOUND

  • The non-interactive algorithm relaxes ℓ0-constrained least squares to an ℓ1-regularized problem, then solves aggregated statistics with a normal equation and soft-thresholding.This closed-form relaxation relies on the section's curvature and boundedness assumptions; the upper-bound theorem states shuffled-DP privacy and a high-probability output guarantee.Source: §4 · p. 4, §4.2 · p. 6
  • The upper-bound gap comes from clipping the second-moment statistic, whose Θ(d) scale enters the privacy noise; closing the gap is left for future work.The polynomial dependence on d therefore remains in the proposed non-interactive bound.Source: §4.2 · p. 6

5 OVERCOMING THE THEORETICAL BARRIER

The paper overcomes the non-interactive dimensionality barrier with a two-round user-level protocol, then proves its rate is near-optimal up to a factor of log(d/k). Its support-recovery stage reduces estimation to the active coordinates, while a user-level score attack establishes the lower bound.

5 OVERCOMING THE THEORETICAL BARRIER

  • The two-round user-level algorithm has an error bound with no polynomial dependence on d once m is large enough, under the restricted eigenvalue condition.The second stage operates on the recovered k-coordinate support; the conditions on m and n1 still depend on d.Source: §5 · p. 6, §5.1 · p. 8

5.1 UPPER BOUND

  • Stage 1 replaces the local-model prefix tree with one round of randomized response over [d], and the heavy hitter step returns the true support under Proposition 1’s conditions.Each user reduces m samples to one index, and the aggregator debiases shuffled counts before thresholding coordinates.Source: §5.1 · pp. 7–8
  • The support-recovery guarantee requires a beta-min signal-strength condition, and the first two terms of equation 10 ensure a user’s local selection is correct with probability at least 1 − 1/(32k).The third term supports the local least-squares estimate on the selected support.Source: §5.1 · p. 8

5.2 LOWER BOUND

  • Theorem 4 lower-bounds user-level (ε, δ)-DP estimators for an exponential-family class that includes the sparse linear model, so it also applies to user-level SDP.The proof compares upper and lower bounds on the expected sum of user-level score-attack terms.Source: §5.2 · pp. 8–9
  • The upper and lower rates agree in n, m, k, and ε and differ only by a factor of log(d/k), making the algorithm near-optimal within that gap.The paper concludes that interactive shuffled sparse regression is closer to central DP when interaction and enough user-level data are available.Source: §5.2 · p. 9
  • The lower-bound analysis extends the score attack framework to user-level data, where each record is a user’s full dataset of m i.i.d. samples.The paper presents this user-level score attack as its main technical tool for the lower bound.Source: §5.2 · p. 9

6 CONCLUSION

The paper characterizes non-interactive and interactive user-level shuffled privacy for sparse linear regression. Its two-round algorithm avoids polynomial dependence on d, and a user-level lower bound shows it is near-optimal; synthetic and real-world experiments support these results.

6 CONCLUSION

  • The paper gives a non-interactive lower bound and algorithm whose bounds both carry polynomial dependence on d, then presents a two-round user-level algorithm whose error does not.Extending the score attack to user-level data yields a lower bound showing the interactive algorithm is near-optimal; experiments on synthetic and real-world datasets support the results.Source: §6 · p. 9
  • The Kelmarsh experiments use wind-turbine operational measurements and involve neither human participants nor personally identifiable information.The dataset is publicly available under the CC BY 4.0 license.Source: ETHICS STATEMENT · p. 10
  • The paper does not release source code, while stating that its paper and appendix descriptions are sufficient to reimplement the algorithms and reproduce the reported results.The appendix includes algorithm pseudocode, theorem parameters, experimental settings, and the real-data preprocessing pipeline.Source: REPRODUCIBILITY STATEMENT · p. 10

A DETAILED COMPARISON AND RELATED WORK

This material situates the work among central, local, and shuffled privacy methods, then details algorithm parameters and experimental scope. The shuffled protocols use aggregate summation, while the interactive method combines support recovery with constrained estimation.

A DETAILED COMPARISON AND RELATED WORK

  • Sparse shuffled regression had remained largely open despite work on shuffle primitives and local or user-level baselines; this paper analyzes both non-interactive sample-level and interactive user-level regimes.The related-work discussion also contrasts central sparse estimation, local methods’ polynomial dependence on d, and multi-sample user-level approaches.Source: A DETAILED COMPARISON AND RELATED WORK · pp. 13, 15

B DETAILED ALGORITHMS AND PARAMETER SETTINGS

  • Both protocols privatize sums of rounded integer vectors with centered-binomial noise and additive shares, calibrating noise to ℓ2 sensitivity rather than ℓ1 sensitivity.The user groups in U2R are disjoint, allowing each group to run at the full privacy budget by parallel composition.Source: B DETAILED ALGORITHMS AND PARAMETER… · p. 16

B.1 NON-INTERACTIVE ALGORITHM

  • Algorithm 2 clips and rounds local sufficient statistics, adds binomial noise, shuffles additive shares, then reconstructs and thresholds an estimate of θ.The rounding error is chosen to match the binomial-noise scale; clipping can be inactive under bounded-data assumptions and handles unbounded data otherwise.Source: §B.1 · p. 16

B.3 STAGE 2: CONSTRAINED ESTIMATION

  • Stage 2 estimates on the recovered support: one user group forms a coarse estimate, and another clips around it to produce the refined estimate.Its summation step uses s parallel shufflers rather than D, and the privacy term involves s rather than d.Source: §B.3 · pp. 17–18

B.2 STAGE 1: SUPPORT RECOVERY

  • Stage 1 fits a local Lasso, thresholds coefficients at ρ/2 to form a candidate set (using [d] if empty), samples uniformly, and sends randomized-response bits through independently shuffled streams.Source: §B.3 · p. 18

C EXPERIMENTAL SETUP AND RESULTS

  • The experiments evaluate U2R on synthetic sparse regression and nacelle-temperature prediction using the Kelmarsh wind-farm dataset.The cited passage identifies the evaluation settings but does not report comparative outcomes.Source: C EXPERIMENTAL SETUP AND RESULTS · p. 18

C.1 EXPERIMENTAL SETUP

The experimental setup compares user-level and sample-level privacy methods on synthetic and Kelmarsh data. It specifies shared evaluation metrics, repeated runs, and the real-data split and preprocessing.

C.1 EXPERIMENTAL SETUP

  • U2R and 2-SLR protect users, while LDP-IHT and Sample-SDP protect individual observations; the comparison uses the same numerical privacy budget while retaining privacy-unit and trust-model differences.U2R and Sample-SDP use shuffled (ε, δ)-DP with δ = 10^-5, whereas 2-SLR and LDP-IHT use pure ε-LDP.Source: §C.1 · p. 18
  • Synthetic data use n = 15000, m = 50, d = 256, k = 8, σ = 0.25, and ε = 4 by default, with each sweep varying one quantity.The realized support is used only for evaluation.Source: §C.1 · p. 18
  • The synthetic experiments report relative coefficient error, test MSE, support recall, and exact recovery, using 30 repetitions in Exp1 and Exp2 and ten in Exp3 and Exp4.Methods share training data and 4000 independent test observations; matching settings reuse data and randomization.Source: §C.1 · p. 19
  • Kelmarsh predicts nacelle temperature from 90 predictors, using whole UTC dates for public, training, and test splits and public-data medians and scaling statistics for preprocessing.The training and test sets contain 1,295,987 and 185,416 rows, respectively, after rows with missing responses are removed.Source: §C.1 · p. 19
  • The real-data runs assign sampled training rows to 10,000 simulated users, testing m ∈ {10, 50, 100} and ε ∈ {1, 4} with a fixed test set.Public validation across the six settings and three seeds selects k = 12 from {8, 10, 12}.Source: §C.1 · p. 19

C.2 MAIN RESULTS

Across the privacy-budget, user-count, and dimension sweeps, U2R maintains low relative coefficient error; on Kelmarsh, it has the lowest mean test-MSE ratio among private methods in all six settings.

C.2 MAIN RESULTS

  • U2R’s mean relative coefficient error decreases from 0.04260 at ϵ = 0.5 to 0.00544 at ϵ = 32, and is 0.00631 at ϵ = 4, comparable to non-private Lasso.U2R has the lowest mean error among private methods at every tested budget.Source: §C.2 · p. 20, Figure 1 · p. 20
  • Increasing n from 8000 to 20000 at m = 50 reduces U2R’s mean error from 0.01022 to 0.00496; it recovers the exact support in every repetition.With exact support recovered, its remaining coefficient error lies on the active coordinates.Source: §C.2 · p. 20
  • With k = 8 and m = 50, U2R’s mean error ranges from 0.00553 to 0.00659 as d increases from 64 to 512, while Sample-SDP rises from 0.01849 to 0.14111.U2R remains close to non-private Lasso across these dimensions.Source: §C.2 · p. 20
  • On Kelmarsh, U2R has the lowest mean test-MSE ratio among private methods in all six settings; as m increases from 10 to 100, its ratio falls at both tested privacy budgets.At ϵ = 1, the ratio decreases from 1.48261 to 1.12978; at ϵ = 4, it decreases from 1.43505 to 1.13213.Source: §C.2 · p. 20

C.3 ADDITIONAL RESULTS

Additional results examine support recovery, synthetic-data prediction error, and Kelmarsh prediction in original units. The section also identifies the omitted proofs for the Section 4 theories.

C.3 ADDITIONAL RESULTS

  • At n = 15000, U2R’s mean support recall rises from 3.75% at m = 25 to 100% at m = 50, and it recovers the exact support in all ten repetitions at m = 50, 75, and 100.Table 8 reports Stage 1 support recall and exact recovery.Source: §C.3 · p. 20, Table 8 · p. 21
  • At m = 50, U2R recovers the exact support in every repetition for all tested user counts from 8000 to 20000; 2-SLR recall ranges from 35.00% to 63.75%.Across the m sweep, 2-SLR recall increases from 26.25% to 76.25%.Source: §C.3 · p. 22
  • At the default setting, U2R and Lasso have mean test MSEs of 0.0625570 and 0.0625521, respectively, close to the residual variance σ^2 = 0.0625.At ϵ = 32, U2R’s MSE is 0.0625546, and its lower coefficient error has little effect on prediction MSE over this budget range.Source: §C.3 · p. 22
  • At ϵ = 1, increasing m from 10 to 100 reduces U2R’s mean Kelmarsh MSE from 3.55270 to 2.70655 and mean RMSE from 1.88464 to 1.64505 °C.Mean R^2 rises from 0.87900 to 0.90782; at m = 100 and ϵ = 4, U2R, Lasso, and Sample-SDP mean MSEs are 2.71218, 2.39565, and 3.28753, respectively.Source: §C.3 · p. 22, Table 9 · p. 22

D OMITTED PROOFS IN SECTION 4

D.1 PROOF OF THEOREM 1

This section provides proofs for results on robust shuffled differential privacy and the algorithms in Theorem 2 and Section 5. It analyzes privacy and accuracy guarantees, including support recovery by the heavy-hitter step.

D.1 PROOF OF THEOREM 1

  • Theorem 1’s proof reduces robust shuffled DP to pan-privacy, then uses a stream hybrid argument and Assouad’s method over coordinates to establish the lower bound.The proof controls coordinate-wise testing errors and completes the pan-private bound for sufficiently small ε.Source: §D.1 · pp. 22–24

D.2 PROOF OF THEOREM 2

  • Algorithm 2 satisfies (ε, δ)-shuffled DP, and the proof establishes Theorem 2’s estimation rate with probability at least 1 − O(d^-2).The privacy argument first shows the aggregate vector is (ε, δ/2)-DP, then relates the aggregator’s view to that vector.Source: §D.2 · pp. 26–27

E OMITTED PROOFS IN SECTION 5

E.1 PROOF OF PROPOSITION 1

  • Stage 1’s local Lasso selects the true support with probability at least 1 − 1/(32k), while its debiased counts separate the support from its complement.The proof also establishes Stage 1’s (ε, δ)-shuffled DP guarantee; the privacy argument is used in Theorem 3’s proof.Source: §E.1 · pp. 27–28
  • The shuffled view consists of independent per-coordinate counts, and changing one user’s index affects only two counts, each bounded using randomized bits and composition.For each affected count, other users’ bits are independently replaced by uniform bits with probability 2γ; the privacy bound follows when γn1 = Cγ log(1/δ)/ϵ^2.Source: §E.1 · pp. 28–29
  • With probability at least 1 − O(n^-2), the heavy-hitter step’s threshold separates support and nonsupport counts, yielding ˆS = S* and s = k.The threshold is τHH = n1/(4k); the proof uses n1 = Ω(k log(dn)) and a concentration bound for the noisy counts.Source: §E.1 · p. 29

E.2 PROOF OF THEOREM 3

The proof establishes privacy by conditioning on earlier releases and composing disjoint user groups, then bounds estimation error under support recovery and design conditions. It also proves soundness and completeness for a sparse user-level score attack.

E.2 PROOF OF THEOREM 3

  • Disjoint user groups let the privacy proof condition on earlier released quantities and use parallel composition, provided each group’s conditional protocol satisfies (ϵ, δ)-shuffled DP.Stage 2b is analyzed explicitly; Stage 2a uses the corresponding parameters and argument.Source: §E.2 · p. 30
  • For Stage 2b, rounding and summation yield a private aggregate, and coupling the coordinates bounds the distance to a simulated view, establishing (ϵ, δ)-privacy for Algorithm 1.The proof first obtains (ϵ, δ/2)-privacy for the aggregate and then bounds the full view’s privacy loss.Source: §E.2 · p. 30
  • The error analysis works on the high-probability event that support recovery is exact, with local design conditioning controlled once m is at least on the order of k.The proof bounds estimation errors and verifies that clipping does not change the local statistics under its stated conditions.Source: §E.2 · pp. 30–31

E.3 PROOF OF PROPOSITION 2

  • The Proposition 2 proof restricts the user-level score to the support of θ and establishes soundness and completeness for that sparse score attack.Source: §E.3 · pp. 32–33

E.4 PROOF OF THEOREM 4

The proof of Theorem 4 combines a privacy-based upper bound on users’ scores with a sparse-prior lower bound. It also accounts for the non-private minimax risk and controls the user-level tail under stated sample-size and model assumptions.

E.4 PROOF OF THEOREM 4

  • The privacy-based score bound assumes user-level (ϵ, δ)-DP, 0 < ϵ < 1, and L = log(2k/δ) ≤ m.Its tail term reflects that each user's score sums m terms and depends on that user's empirical design-vector second moments.Source: §E.4 · p. 33
  • The proof combines a privacy-based upper bound on the summed user scores with a sparse-prior lower bound to establish Theorem 4.The score bound uses a tail estimate for each user's sum of m sample-level terms; the prior supplies a lower bound on the same sum.Source: §E.4 · pp. 33–35
  • The sparse-prior argument assumes k ≤ d and k ≥ C0 log2(d/k), with the risk bounded over parameters in Θ.The proof uses a prior supported on sparse vectors and applies Stein’s lemma within fixed support sets.Source: §E.4 · pp. 34–35
  • The proof also invokes the non-private minimax risk over Θ, which lower-bounds the risk of any estimator, private or not.For the linear model, the cited comparison is to the rate of Raskutti et al. (2011).Source: §E.4 · pp. 35–36

F.1 NON-INTERACTIVE USER-LEVEL SHUFFLED DP

The section shows that user-level data alone does not remove dimension dependence for non-interactive shuffled protocols, and contrasts that with the role of interaction. It also extends the user-level score-attack analysis to dense regression, replacing the sparsity-dependent quantity with d.

F.1 NON-INTERACTIVE USER-LEVEL SHUFFLED DP

  • Non-interactive user-level shuffled protocols retain a dimension-dependent privacy term, whereas the interactive protocol’s corresponding term carries k in place of d.The section states that the non-interactive dependence persists regardless of the local sample size m.Source: §F.1 · p. 36
  • The proof of the non-interactive lower bound converts the protocol to a pan-private algorithm and compares output distributions across neighboring constructions.The argument uses a hybrid over records and then applies Assouad’s method.Source: §F.1 · pp. 36–37

F.2 USER-LEVEL DP IN DENSE REGRESSION

  • For dense regression, the user-level score-attack rate is the Theorem 4 rate with k log(d/k) replaced by d.The dense parameter lies in the box Θbox = {θ ∈ Rd : ∥θ∥∞ ≤ 1}.Source: §F.2 · p. 38
  • The dense-case privacy score bound uses a union bound over all d coordinates and the constraint ∥A(Z) − θ∥1 ≤ 2d.This is the dense analogue of the sparse score-bound argument.Source: §F.2 · pp. 38–39

Related papers

Loading 2610.32822v2…