Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

Differentially Private Sparse Linear Regression with Heavy-tailed Responses

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper establishes $(\varepsilon,\delta)$-DP sparse linear regression under heavy-tailed responses, achieving rates $\tilde{O}\big((s^*)^{1/2}(\log d/n)^{\zeta/(1+\zeta)} + (s^*)^{(1+2\zeta)/(2+2\zeta)}(\log^2…

desk verdict A serious attempt at a real gap, but the advertised ζ-independent DP-IHT-L rate rests on a false gradient-norm bound and should not be trusted as written. read the letter →

arxiv 2506.06861 v1 pith:PBOHSL6Y submitted 2025-06-07 cs.LG cs.CR

Xizhi Tian , Meng Ding , Touming Tao , Zihang Xiang , Di Wang This is my paper
classification cs.LGcs.CR MSC 62J0768P2762F35
keywords differentialprivacysparselinearregressionheavy-taileddataiterativehardthresholdingHuberlossl1Peelingmechanismfinitemoments
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether high-dimensional sparse linear regression can be made differentially private when the response variable has only a finite $(1+\zeta)$-th moment, so its distribution can be heavy-tailed. It claims yes, and proposes two iterative hard-thresholding algorithms: DP-IHT-H, which uses the Huber loss, and DP-IHT-L, which uses the $\ell^1$ loss. For general heavy-tailed responses, DP-IHT-H is shown to achieve error $O\big((s^*)^{1/2}(\log d/n)^{\zeta/(1+\zeta)} + (s^*)^{(1+2\zeta)/(2+2\zeta)}(\log^2 d\,\log(1/\delta)/(n\varepsilon))^{\zeta/(1+\zeta)}\big)$ under $(\varepsilon,\delta)$-DP. Under an additional mild condition on the noise density, DP-IHT-L achieves $O\big((s^*)^{3/2}\log d\,\sqrt{\log(1/\delta)}\log n/(n\varepsilon)\big)$, a rate independent of $\zeta$ and matching the best known rate for sub-Gaussian responses. If correct, these are the first such high-dimensional sparse DP regression bounds under only a finite $(1+\zeta)$-th moment.

What carries the argument

The load-bearing mechanism is the combination of feature clipping, a robust loss with bounded gradient, and the private Peeling procedure (Algorithm 2), a coordinate-selection routine that adds Laplace noise before and after choosing the $s$ largest-magnitude entries so that the support itself is protected. Clipping each feature coordinate to $O(\log d)$ keeps the gradient's $\ell_\infty$-sensitivity at $\tau K/m$, so the Peeling noise scale is $\lambda\sqrt{s\log(1/\delta)}/\varepsilon$ rather than something polynomial in $d$. Restricted strong convexity and smoothness of the robust losses drive the IHT contraction, and for DP-IHT-L the proof splits the sub-gradient into a large-deviation regime (fast geometric convergence) and a small-deviation regime (linear contraction dominated by the noise term). The resulting two-phase argument produces the final $\ell_2$-error bound.

What would settle it

Run DP-IHT-L for $T=O(\log n)$ rounds on a fixed heavy-tailed dataset with $\varepsilon=0.5$, $\delta=1/n^{1.1}$, and track the realized privacy loss of the $T$ adaptive Laplace mechanisms (e.g., via R\'{e}nyi composition). Standard composition predicts a total budget near $T\varepsilon$, so if the realized privacy parameter exceeds $(\varepsilon,\delta)$ as $T$ grows, the paper's claim that the algorithm is $(\varepsilon,\delta)$-DP, and hence the stated rate, is falsified.

Watch

Extended reading notes

Core claim

The paper's central claim is that differential privacy is compatible with heavy-tailed high-dimensional sparse linear regression, provided the estimation procedure is robustified by a bounded-gradient loss and a coordinate-selection step whose sensitivity does not scale with the dimension. The first theorem states that DP-IHT-H, using clipped features, a tuned Huber parameter, and the private Peeling selection, is $(\varepsilon,\delta)$-DP and yields $\|\beta_T-\beta^*\|_2 = O\big((s^*)^{1/2}(\log d/n)^{\zeta/(1+\zeta)} + (s^*)^{(1+2\zeta)/(2+2\zeta)}(\log^2 d\,\log(1/\delta)/(n\varepsilon))^{\zeta/(1+\zeta)}\big)$. The second central result states that under Assumption 3, which imposes a local Bernstein lower bound and a uniform upper bound on the noise density, DP-IHT-L achieves $\|\beta_T-\beta^*\|_2 = O\big((s^*)^{3/2}\log d\,(\log(1/\delta))^{1/2}\log n/(n\varepsilon)\big)$, independent of the tail parameter $\zeta$. The paper positions these as the first bounds of their kind for the case where the response only has a bounded $(1+\zeta)$-th moment with $\zeta\in(0,1]$, and supports the theory with experiments on synthetic and genomic data.

Load-bearing premise

The privacy guarantee depends on the premise that $T$ rounds of the full-budget $(\varepsilon,\delta)$ Peeling run on disjoint data chunks, with iterates shared across rounds, still compose to an overall $(\varepsilon,\delta)$-DP mechanism; standard composition would give roughly $(T\varepsilon,T\delta)$.

Editorial extensions

If this is right

  • Sparse DP regression becomes feasible in $d\gg n$ settings with heavy-tailed responses, because both error bounds scale as $\mathrm{poly}(s^*)\log d$ times a privacy term rather than polynomially in $d$.
  • With Assumption 3, DP-IHT-L's rate $\tilde{O}((s^*)^{3/2}\log d/(n\varepsilon))$ holds for every $\zeta\in(0,1]$, so practitioners do not need to know the tail parameter to deploy the $\ell^1$-loss version.
  • The Huber-based bound separates statistical and privacy costs: the first term is the optimal non-private rate, and when $\zeta=1$ the privacy term becomes $\tilde{O}((s^*)^{3/4}\log d/\sqrt{n\varepsilon})$, better in sparsity than the $\ell^1$-loss rate.
  • For finite $(1+\zeta)$-th moments with small $\zeta$, both algorithms should beat DP estimators built for sub-Gaussian or bounded data, matching the paper's synthetic and genomic experiments.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The $(\varepsilon,\delta)$ guarantee as stated rests on composing $T$ full-budget Peeling runs across adaptive rounds; standard adaptive composition would predict a total budget near $(T\varepsilon,T\delta)$, so the advertised rates depend on that composition premise holding.
  • A clean falsification experiment for the $\zeta$-independence claim: run DP-IHT-L on noise whose density violates Assumption 3 (e.g., vanishing near zero) but which still has a finite $(1+\zeta)$-th moment; the theory predicts a degraded, $\zeta$-dependent rate.
  • The feature-clipping-plus-Peeling recipe could plausibly extend to other sparse $M$-estimators (e.g., logistic or quantile regression) under heavy-tailed responses, a direction the paper does not explore.
  • On the real-data benchmark the unknown $\beta^*$ is approximated by the non-private adaHuber fit; a held-out prediction-error comparison would provide a more neutral evaluation of the DP estimators.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper studies differentially private sparse linear regression under heavy-tailed responses, assuming sub-Gaussian features and responses with only a finite (1+ζ)-th moment. It proposes two iterative hard-thresholding algorithms: DP-IHT-H, which uses a Huber loss and claims an estimation error of order Õ(√s* (log d/n)^{ζ/(1+ζ)} + (s*)^{(1+2ζ)/(2+2ζ)} (log^2 d/(nε))^{ζ/(1+ζ)}), and DP-IHT-L, which uses an ℓ1 loss with clipped features and claims a ζ-independent bound of order Õ((s*)^{3/2} log d/(nε)) under an additional local Bernstein condition on the noise density. The paper also reports synthetic and real-data experiments comparing the methods with DP-SLR and non-private adaHuber.

Significance. If the theorems were correct, the paper would be a meaningful step: it targets a realistic heavy-tailed regime in high-dimensional sparse linear regression, and the ζ-independent rate for DP-IHT-L would match the best known sub-Gaussian-rate dependence on n and ε. The algorithmic design (clipping, data splitting, Peeling-based sparse selection) is natural and the experiments are relevant. However, the paper's central proofs contain load-bearing gaps, including a false gradient-norm bound in the proof of Theorem 4 and an incorrect privacy composition argument in Appendix A, so the advertised guarantees are not established by the manuscript as written.

major comments (4)
  1. [Appendix D (proof of Theorem 4)] The proof asserts, by reference to 'Lemma 1 in [38]', that f(β_t)−f(β*) ≥ (n/4)c_l^{1/2}||β_t−β*||_2 and moreover ||G_t||_2 ≤ n c_u^{1/2}. The second bound is false for Algorithm 3. Because every feature coordinate is clipped to |\tilde x_{i,j}| ≤ K, the subgradient G_t (either the sum or the normalized average used in the update) satisfies a triangle-inequality bound of the form ||G_t||_2 ≤ |D_t| K √d (or K√d after normalization), which is dimension-dependent and can exceed n√c_u by a large factor when d≫n, e.g., d=n^2 and K=log d. The subsequent step-size choice η_t ∈ n^{−1}√(c_l/c_u)[D_t/8, 3D_t/8] is derived from the false bound, and the quadratic term η_t^2||G_t||_2^2 is not shown to be dominated by the negative linear term. Consequently the two-phase contraction in Theorem 4, and therefore the ζ-independent rate in Theorem 5, do not follow from the supplied analysis.
  2. [Appendix A (proofs of Theorems 1 and 3)] The privacy proof states that each iteration of the algorithm is (ε,δ)-DP because the Peeling step is (ε,δ)-DP and the per-iteration influence of one sample is bounded, and then concludes that the entire procedure is (ε,δ)-DP. This is not a valid composition argument: applying a mechanism with budget (ε,δ) in each of T adaptive iterations would only yield (Tε,Tδ)-DP under standard sequential composition. A parallel-composition argument could repair the claim because the T rounds use disjoint data chunks, and for a neighboring dataset differing in one record only one chunk changes; however, that argument is not supplied, and the fact that the iterate β_t carries information from earlier chunks through the adaptively chosen inputs to later Peeling steps must be handled explicitly.
  3. [Appendix B (Lemma 6 and proof of Theorem 2)] The proof of Lemma 6 invokes 'a lemma from Lemma A.4[?]' to assert ||g^t_{S_t∪S*}||_2^2 − (c_l^2/4)||\hat β − β^t||_2^2 ≥ (c_l/2)(L_n(β^t) − L_n(\hat β)). This referenced lemma is not stated or proved anywhere in the manuscript; the placeholder '[?]' explicitly marks it as missing. Since Lemma 6 is the contraction result underlying Theorem 2, the proof of Theorem 2 is incomplete. The same proof also uses undefined notation (e.g., 'I†' in the display after Eq. (3)) and refers to 'Lemma 8.3 and Theorem 4.4 in [41]' without stating the content needed for the argument.
  4. [Section 5 (display after Assumption 3)] The displayed identity G_t = Σ_{i∈D_t} sign(x_i^T β_t − y_i) \tilde x_i = Σ_{i∈D_t} sign(x_i^T(β_t−β*)) \tilde x_i − Σ_{i∈D_t} sign(x_i^T ε_i) \tilde x_i is incorrect in general, because sign(a−b) is not equal to sign(a)−sign(b). This decomposition is used to motivate the two-regime analysis for the ℓ1-loss algorithm, so it should either be replaced by a correct inequality or the proof should be rewritten not to rely on the displayed equality.
minor comments (5)
  1. [Appendix E (proof of Theorem 5)] The final displayed bound in the proof is O((s*)^{3/2} log d (log(1/δ))^{1/2} log(T/n) / ((T/n)ε)), whereas Theorem 5 states O((s*)^{3/2} log d (log(1/δ))^{1/2} log n / (nε)). For T=O(log n), log(T/n) is negative, so the expression in the proof is not even positive; the discrepancy needs to be resolved for the claimed rate to be transparent.
  2. [Appendix C (proof of Theorem 2)] The proof refers to an event E3 and a parameter σ that are not defined in the manuscript; the statement of Theorem 2 uses log(1/δ), while the proof uses log(1/σ). These symbols should be defined and used consistently.
  3. [Assumption 3 and its remark] The claim that Assumption 3 is 'quite relaxed' is overstated: the lower bound h_ε(x) ≥ 1/b_0 on an interval around zero excludes densities that vanish near zero, and the upper bound h_ε(x) ≤ 1/b_1 excludes densities with unbounded peaks at zero. The authors should state more precisely which heavy-tailed families are covered.
  4. [Theorem 2 and Theorem 4 constants] The sparsity settings are inconsistent across the paper: Theorem 2 uses s=O(s*), while the proof of Lemma 6 requires s=72(c_u/c_l)^2 s*, and Theorem 4 states s=Ω((c_u/c_l)^8(b_0/b_1)^8 s*). The constants should be reconciled.
  5. [Throughout] There are numerous typos, including 'adaHuher' instead of 'adaHuber' in Section 6.1, 'imcomparable' instead of 'incomparable' in Section 5, and 'as ϵ decrease' in the caption of Figure 2d.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the main rates are parameter-free and rest on external lemmas, with self-citations only in comparisons.

full rationale

The claimed derivation chain is not circular. Theorems 2 and 5 state parameter-free rates: no coefficient is fitted from the data or from the target error, and the DP noise scales are derived from the mechanism's sensitivity, not chosen to match the conclusion. The load-bearing technical inputs are external: RSC/RSS and adaptive-Huber lemmas from [41], the clipped l1 two-phase analysis from [38], and the Peeling utility/privacy lemmas from [10]. The paper's self-citations ([21], [44], [48], [53], [54], etc.) occur in related-work positioning and comparisons; none is used as the unverified premise of a main theorem, and none is invoked as a uniqueness or forcing result. No equation in the paper is defined in terms of the quantity it is supposed to predict, and no fitted parameter is renamed as a prediction. The main weaknesses are correctness risks, not circularity: the Appendix D assertion that ||G_t||_2 <= n c_u^{1/2} is inconsistent with K-clipped features when d >> n, and the privacy proof composes T full-budget rounds without an explicit composition argument. A false lemma or missing composition step is a proof gap; it does not make the derivation equivalent to its inputs by construction. I therefore find no circular step to report.

Assumptions & free parameters 4 free parameters · 7 assumptions · 0 invented entities

The central bounds rest on standard high-dimensional assumptions (sub-Gaussian features, RSC, finite moment) and two imported analysis frameworks ([41] for Huber, [38] for l1). The main unstated burden is the privacy-composition premise and the missing Lemma A.4 reference.

free parameters (4)
  • Huber loss parameter τ = τ=1 in experiments; theoretical tuning τ≍(t/n)^{1/(1+ζ)} (Theorem 2)
    Chosen by hand in experiments; the theory tunes it to balance bias and privacy noise, so the bound is not a fit.
  • Step size η = η=0.01 in experiments; theoretical η_t schedule in Theorem 4
    Fixed heuristically in experiments; the theory specifies a decaying then constant schedule, but the proof of Theorem 4 selects it using the target contraction bound.
  • Truncation parameter K = K=log d
    Set to log d in both theory and experiments to clip features to bounded l∞ norm.
  • Sparsity s = s=5 in experiments
    The theoretical guarantees require s=O(s*) or s=Ω((c_u/c_l)^8(b_0/b_1)^8 s*), while experiments set s=s*=5.
assumptions (7)
  • domain assumption Features x are zero-mean O(1)-sub-Gaussian with bounded eigenvalue covariance (Assumption 1)
    Standard high-dimensional sparse regression condition; bounds the gradient and enables RSC/RSS lemmas.
  • domain assumption Noise ε has zero mean and finite (1+ζ)-th moment (Assumption 2)
    Defines the heavy-tailed regime; the entire paper targets this weaker-than-variance condition.
  • ad hoc to paper Noise density h_ε is bounded below near zero and bounded above everywhere (Assumption 3)
    Needed only for DP-IHT-L to get the ζ-independent bound; excludes distributions with vanishing or unbounded density near the origin.
  • domain assumption Lemma 1 from [41] (restricted strong convexity of adaptive Huber)
    Imported without proof; requires n≳(τ/r)^2(d+t) and τ≥..., which is assumed to hold in the paper's regime.
  • domain assumption Lemma 1 from [38] (two-regime l1 loss analysis)
    Imported without proof for the Phase One/Phase Two convergence of l1 subgradient descent.
  • standard math Unstated Lemma A.4[?] used in Lemma 6
    The proof of Lemma 6 in Appendix B invokes 'Lemma A.4[?]' with a missing reference; the contraction inequality depends on it.
  • ad hoc to paper Implicit privacy composition: T adaptive iterations with per-step budget (ε,δ) on disjoint chunks yield (ε,δ)-DP overall
    Appendix A asserts this without proof; standard adaptive composition would multiply ε by T unless the per-step budget is scaled.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Differentially Private Sparse Linear Regression with Heavy-tailed Responses." pith.science (2026). https://pith.science/paper/PBOHSL6Y

@misc{pith2026250606861,
  author       = {Pith},
  title        = {Pith review of: Differentially Private Sparse Linear Regression with Heavy-tailed Responses},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PBOHSL6Y}},
  note         = {Machine review of arXiv:2506.06861}
}
abstract

As a fundamental problem in machine learning and differential privacy (DP), DP linear regression has been extensively studied. However, most existing methods focus primarily on either regular data distributions or low-dimensional cases with irregular data. To address these limitations, this paper provides a comprehensive study of DP sparse linear regression with heavy-tailed responses in high-dimensional settings. In the first part, we introduce the DP-IHT-H method, which leverages the Huber loss and private iterative hard thresholding to achieve an estimation error bound of \( \tilde{O}\biggl( s^{* \frac{1 }{2}} \cdot \biggl(\frac{\log d}{n}\biggr)^{\frac{\zeta}{1 + \zeta}} + s^{* \frac{1 + 2\zeta}{2 + 2\zeta}} \cdot \biggl(\frac{\log^2 d}{n \varepsilon}\biggr)^{\frac{\zeta}{1 + \zeta}} \biggr) \) under the $(\varepsilon, \delta)$-DP model, where $n$ is the sample size, $d$ is the dimensionality, $s^*$ is the sparsity of the parameter, and $\zeta \in (0, 1]$ characterizes the tail heaviness of the data. In the second part, we propose DP-IHT-L, which further improves the error bound under additional assumptions on the response and achieves \( \tilde{O}\Bigl(\frac{(s^*)^{3/2} \log d}{n \varepsilon}\Bigr). \) Compared to the first result, this bound is independent of the tail parameter $\zeta$. Finally, through experiments on synthetic and real-world datasets, we demonstrate that our methods outperform standard DP algorithms designed for ``regular'' data.

Figures

Figures reproduced from arXiv: 2506.06861 by the authors.

Figure 1
Figure 1. Comparison of DP-IHT-H, DP-SLR, and adaHuber methods. [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. Comparison of DP-IHT-L and DP-IHT-H across various metrics. [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition

    cs.LG 2025-09 reject novelty 6.0 of 10

    DP-SCO with Tsybakov noise and bounded gradient moments is claimed to achieve excess risk ((r(1/sqrt(n)+sqrt(d)/(n eps))^{(k-1)/k}))^{theta/(theta-1)} with high probability, but the lower bound proof violates the pape...

Reference graph

Works this paper leans on

62 extracted references · 58 canonical work pages · cited by 1 Pith paper

  1. [38]

    Shen, Y., Li, J., Cai, J.F., Xia, D.: Computationally efficient and statistically optimal robust high-dimensional linear regression (2023) Differentially Private Sparse Linear Regression with Heavy-tailed Responses 17

    work page 2023

  2. [41]

    Journal of the American Statistical Association115(529), 254–265 (2020)

    Sun, Q., Zhou, W., Fan, J.: Adaptive huber regression. Journal of the American Statistical Association115(529), 254–265 (2020)

    work page 2020

  3. [1]

    In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security

    Abadi, M., Chu, A., Goodfellow, I., McMahan, H.B., Mironov, I., Talwar, K., Zhang, L.: Deep learning with differential privacy. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. pp. 308–

    work page 2016

  4. [2]

    The Annals of Statistics 47(4), 2117–2144 (2019)

    Alquier, P., Cottet, V., Lecué, G.: Estimation bounds and sharp oracle inequalities of regularized procedures with lipschitz loss functions. The Annals of Statistics 47(4), 2117–2144 (2019)

    work page 2019

  5. [3]

    Barber, R.F., Duchi, J.C.: Privacy and statistical risk: Formalisms and minimax bounds (2014)

    work page 2014

  6. [4]

    Advances in Neural Information Processing Systems33(2020)

    Bassily, R., Feldman, V., Guzmán, C., Talwar, K.: Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems33(2020)

    work page 2020

  7. [5]

    In: Advances in Neural Information Processing Sys- tems (2019)

    Bassily, R., Feldman, V., Talwar, K., Thakurta, A.: Private stochastic convex op- timization with optimal rates. In: Advances in Neural Information Processing Sys- tems (2019)

    work page 2019

  8. [6]

    Biswas, A., Datta, S., Fine, J.P., Segal, M.R.: Statistical advances in the biomedical science (2007)

    work page 2007

Show all 62 references
  1. [7]

    The Annals of Statistics43(6), 2507–2536 (2015)

    Brownlees, C., Joly, E., Lugosi, G.: Empirical risk minimization for heavy-tailed losses. The Annals of Statistics43(6), 2507–2536 (2015)

    2015

  2. [8]

    Bun, M., Steinke, T.: Average-case averages: Private algorithms for smooth sensi- tivity and mean estimation (2019)

    2019

  3. [9]

    Cai, T.T., Wang, Y., Zhang, L.: The cost of privacy in generalized linear models: Algorithms and minimax lower bounds (2020)

    2020

  4. [10]

    The Annals of Statistics49(5), 2825–2850 (2021)

    Cai, T.T., Wang, Y., Zhang, L.: The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics49(5), 2825–2850 (2021)

    2021

  5. [11]

    In: Advances in Neural Information Processing Systems

    Chaudhuri, K., Monteleoni, C.: Privacy-preserving logistic regression. In: Advances in Neural Information Processing Systems. pp. 289–296 (2009)

    2009

  6. [12]

    Journal of Machine Learning Research12, 1069–1109 (2011)

    Chaudhuri, K., Monteleoni, C., Sarwate, A.D.: Differentially private empirical risk minimization. Journal of Machine Learning Research12, 1069–1109 (2011)

    2011

  7. [13]

    Nature486(7403), 346–352 (2012)

    Curtis, C., et al.: The genomic and transcriptomic architecture of 2,000 breast tumours reveals novel subgroups. Nature486(7403), 346–352 (2012)

    2012

  8. [14]

    In: Ad- vances in Neural Information Processing Systems

    Ding, B., Kulkarni, J., Yekhanin, S.: Collecting telemetry data privately. In: Ad- vances in Neural Information Processing Systems. pp. 3571–3580 (2017)

    2017

  9. [15]

    arXiv preprint arXiv:2503.06009 (2025)

    Ding, M., Lei, M., Wang, S., Zheng, T., Wang, D., Xu, J.: Nearly optimal differ- entially private relu regression. arXiv preprint arXiv:2503.06009 (2025)

    2025 arXiv

  10. [16]

    Advances in Neural Information Processing Systems37, 55470–55506 (2024)

    Ding, M., Lei, M., Zhu, L., Wang, S., Wang, D., Xu, J.: Revisiting differentially private relu regression. Advances in Neural Information Processing Systems37, 55470–55506 (2024)

    2024

  11. [17]

    Journal of the American Statistical Association113(521), 182–201 (2018)

    Duchi, J.C., Jordan, M.I., Wainwright, M.J.: Minimax optimal procedures for lo- cally private estimation. Journal of the American Statistical Association113(521), 182–201 (2018)

    2018

  12. [18]

    265–284 (2006)

    Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis pp. 265–284 (2006)

    2006

  13. [19]

    In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

    Feldman, V., Koren, T., Talwar, K.: Private stochastic convex optimization: Op- timal rates in linear time. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. pp. 439–449 (2020) 16 X.Tian et al

    2020

  14. [20]

    In: International Conference on Machine Learning

    Holland, M., Ikeda, K.: Better generalization with less data using robust gradient descent. In: International Conference on Machine Learning. pp. 2761–2770 (2019)

    2019

  15. [21]

    In: Proceedings of the 41st ACM SIGMOD- SIGACT-SIGAI Symposium on Principles of Database Systems (PODS ’22)

    Hu,L.,Ni,S.,Xiao,H.,Wang,D.:Highdimensionaldifferentiallyprivatestochastic optimization with heavy-tailed data. In: Proceedings of the 41st ACM SIGMOD- SIGACT-SIGAI Symposium on Principles of Database Systems (PODS ’22). pp. 227–236. Association for Computing Machinery, New Yo...

    2022

  16. [22]

    In: Proceedings of the AAAI Conference on Artificial Intelligence

    Huai, M., Wang, D., Miao, C., Xu, J., Zhang, A.: Pairwise learning with differ- ential privacy guarantees. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 34, pp. 694–701 (2020)

    2020

  17. [23]

    The Annals of Mathemat- ical Statistics35(1), 73–101 (1964)

    Huber, P.J.: Robust estimation of a location parameter. The Annals of Mathemat- ical Statistics35(1), 73–101 (1964)

    1964

  18. [24]

    Ibragimov, M., Ibragimov, R., Walden, J.: Heavy-Tailed Distributions and Robust- ness in Economics and Finance, vol. 214. Springer (2015)

    2015

  19. [25]

    In: 2019 IEEE Symposium on Security and Privacy (SP)

    Iyengar, R., Near, J.P., Song, D., Thakkar, O., Thakurta, A., Wang, L.: Towards practical differentially private convex optimization. In: 2019 IEEE Symposium on Security and Privacy (SP). pp. 299–316. IEEE (2019)

    2019

  20. [26]

    Kamath, G., Liu, X., Zhang, H.: Improved rates for differentially private stochastic convex optimization with heavy-tailed data (2021)

    2021

  21. [27]

    In: Conference on Learning Theory

    Kamath, G., Singhal, V., Ullman, J.: Private mean estimation of heavy-tailed dis- tributions. In: Conference on Learning Theory. pp. 2204–2235. PMLR (2020)

    2020

  22. [28]

    In: International Conference on Machine Learning

    Kasiviswanathan, S.P., Jin, H.: Efficient private empirical risk minimization for high-dimensional learning. In: International Conference on Machine Learning. pp. 488–497 (2016)

    2016

  23. [29]

    In: Conference on Learning Theory

    Kifer, D., Smith, A., Thakurta, A.: Private convex empirical risk minimization and high-dimensional regression. In: Conference on Learning Theory. pp. 25–1 (2012)

    2012

  24. [30]

    Lecue, G., Lerasle, M., Mathieu, T.: Robust classification via mom minimization (2018)

    2018

  25. [31]

    Liu, X., Kong, W., Kakade, S., Oh, S.: Robust and differentially private mean estimation (2021)

    2021

  26. [32]

    Journal of the European Mathematical Society (2019)

    Lugosi, G., Mendelson, S.: Risk minimization by median-of-means tournaments. Journal of the European Mathematical Society (2019)

    2019

  27. [33]

    British Journal of Cancer91(5), 873–878 (2004)

    Nakata, B., Takashima, T., Ogawa, Y., Ishikawa, T., Hirakawa, K.: Serum cyfra 21- 1 (cytokeratin-19 fragments) is a useful tumour marker for detecting disease relapse and assessing treatment efficacy in breast cancer. British Journal of Cancer91(5), 873–878 (2004)

    2004

  28. [34]

    In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing

    Nissim, K., Raskhodnikova, S., Smith, A.: Smooth sensitivity and sampling in pri- vate data analysis. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing. pp. 75–84. ACM (2007)

    2007

  29. [35]

    Nature Communications7, 11479 (2016)

    Pereira, B., et al.: The somatic mutation profiles of 2,433 breast cancers refines their genomic and transcriptomic landscapes. Nature Communications7, 11479 (2016)

    2016

  30. [36]

    Cancer Research72(14), 3499–3511 (2012)

    Reinhold, W., Varma, S., Sousa, F., et al.: Cellminer: A web-based suite of genomic and pharmacologic tools to explore transcript and drug patterns in the nci-60 cell line set. Cancer Research72(14), 3499–3511 (2012)

    2012

  31. [37]

    arXiv preprint arXiv:2310.08425 (2023)

    Shen, H., Wang, C.L., Xiang, Z., Ying, Y., Wang, D.: Differentially private non- convex learning for multi-layer neural networks. arXiv preprint arXiv:2310.08425 (2023)

    2023 arXiv

  32. [39]

    In: International Conference on Algorithmic Learning Theory

    Su, J., Hu, L., Wang, D.: Faster rates of private stochastic convex optimization. In: International Conference on Algorithmic Learning Theory. pp. 995–1002. PMLR (2022)

    2022

  33. [40]

    Journal of Machine Learning Research25(114), 1–41 (2024)

    Su, J., Hu, L., Wang, D.: Faster rates of differentially private stochastic convex optimization. Journal of Machine Learning Research25(114), 1–41 (2024)

    2024

  34. [42]

    In: Proceedings of the 28th International Conference on Neural Information Processing Systems

    Talwar, K., Thakurta, A., Zhang, L.: Nearly-optimal private lasso. In: Proceedings of the 28th International Conference on Neural Information Processing Systems. pp. 3025–3033 (2015)

    2015

  35. [43]

    CoRR (2017)

    Tang, J., Korolova, A., Bai, X., Wang, X., Wang, X.: Privacy loss in apple’s im- plementation of differential privacy on macos 10.12. CoRR (2017)

    2017

  36. [44]

    In: 31st International Joint Conference on Artificial Intelligence, IJCAI 2022

    Tao, Y., Wu, Y., Cheng, X., Wang, D.: Private stochastic convex optimization and sparse learning with heavy-tailed data revisited. In: 31st International Joint Conference on Artificial Intelligence, IJCAI 2022. pp. 3947–3953. International Joint Conferences on Artificial Intel...

    2022

  37. [45]

    Journal of Complexity74, 101696 (2023)

    Tong, H.: Functional linear regression with huber loss. Journal of Complexity74, 101696 (2023)

    2023

  38. [46]

    In: International Conference on Machine Learning

    Wang, D., Chen, C., Xu, J.: Differentially private empirical risk minimization with non-convex loss functions. In: International Conference on Machine Learning. pp. 6526–6535. PMLR (2019)

    2019

  39. [47]

    Journal of Machine Learning Research21(200), 1–39 (2020)

    Wang, D., Gaboardi, M., Smith, A., Xu, J.: Empirical risk minimization in the non-interactive local model of differential privacy. Journal of Machine Learning Research21(200), 1–39 (2020)

    2020

  40. [48]

    In: International Conference on Machine Learning

    Wang, D., Xiao, H., Devadas, S., Xu, J.: On differentially private stochastic con- vex optimization with heavy-tailed data. In: International Conference on Machine Learning. pp. 10081–10091. PMLR (2020)

    2020

  41. [49]

    In: Proceedings of the AAAI Conference on Artificial Intelligence

    Wang, D., Xu, J.: Differentially private empirical risk minimization with smooth non-convex loss functions: A non-stationary view. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 33, pp. 1182–1189 (2019)

    2019

  42. [50]

    In: International Conference on Machine Learning

    Wang, D., Xu, J.: On sparse linear regression in the local differential privacy model. In: International Conference on Machine Learning. pp. 6628–6637. PMLR (2019)

    2019

  43. [51]

    In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases

    Wang, D., Xu, J.: Escaping saddle points of empirical risk privately and scalably via dp-trust region method. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases. pp. 90–106. Springer (2020)

    2020

  44. [52]

    IEEE Transactions on Information Theory67(2), 1182–1200 (2020)

    Wang, D., Xu, J.: On sparse linear regression in the local differential privacy model. IEEE Transactions on Information Theory67(2), 1182–1200 (2020)

    2020

  45. [53]

    In: 2022 IEEE International Symposium on Information Theory (ISIT)

    Wang, D., Xu, J.: Differentially privateℓ1-norm linear regression with heavy-tailed data. In: 2022 IEEE International Symposium on Information Theory (ISIT). pp. 1856–1861. IEEE (2022)

    2022

  46. [54]

    Theo- retical Computer Science1030, 115071 (2025)

    Wang, D., Xu, J.: Private least absolute deviations with heavy-tailed data. Theo- retical Computer Science1030, 115071 (2025)

    2025

  47. [55]

    Advances in Neural Information Processing Systems 30(2017)

    Wang, D., Ye, M., Xu, J.: Differentially private empirical risk minimization revis- ited: Faster and more general. Advances in Neural Information Processing Systems 30(2017)

    2017

  48. [56]

    In: Proceedings of the AAAI Conference on Artificial Intelligence

    Wang, L., Gu, Q.: A knowledge transfer framework for differentially private sparse learning. In: Proceedings of the AAAI Conference on Artificial Intelligence. pp. 6235–6242 (2020)

    2020

  49. [57]

    Woolson, R.F., Clarke, W.R.: Statistical Methods for the Analysis of Biomedical Data, vol. 371. John Wiley & Sons (2011) 18 X.Tian et al

    2011

  50. [58]

    In: 30th International Joint Conference on Artificial Intelligence, IJCAI

    Xue, Z., Yang, S., Huai, M., Wang, D.: Differentially private pairwise learning re- visited. In: 30th International Joint Conference on Artificial Intelligence, IJCAI

  51. [59]

    In: Pro- ceedings of the AAAI Conference on Artificial Intelligence

    Zhang, R., Lei, M., Ding, M., Xiang, Z., Xu, J., Wang, D.: Improved rates of differentially private nonconvex-strongly-concave minimax optimization. In: Pro- ceedings of the AAAI Conference on Artificial Intelligence. vol. 39, pp. 22524–22532 (2025)

    2025

  52. [60]

    arXiv preprint arXiv:2310.07367 (2023)

    Zhu, L., Ding, M., Aggarwal, V., Xu, J., Wang, D.: Improved analysis of sparse lin- ear regression in local differential privacy model. arXiv preprint arXiv:2310.07367 (2023)

    2023 arXiv

  53. [61]

    Zhu, L., Manseur, A., Ding, M., Liu, J., Xu, J., Wang, D.: Truthful high dimen- sional sparse linear regression. arXiv preprint arXiv:2410.13046 (2024) Differentially Private Sparse Linear Regression with Heavy-tailed Responses 19 A Proof of Theorem 1 Proof.Consider two neighb...

    2024 arXiv

  54. [2021]

    3242–3248

    pp. 3242–3248. International Joint Conferences on Artificial Intelligence Or- ganization (2021)

    2021

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.