Back

Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data

Gautam KamathXingtu LiuHuanyu Zhang

article2022ICML66 citations

Establishes improved excess population risk upper bounds and nearly matching lower bounds for differentially private stochastic convex optimization with heavy-tailed gradients under concentrated differential privacy.

Listen

Modern machine learning systems frequently train models on sensitive real-world datasets that contain extreme outliers or heavy-tailed distributions. Standard differential privacy techniques protect individual data records by bounding the sensitivity of model updates, but they almost universally rely on the unrealistic assumption that model loss functions are uniformly bounded (Lipschitz). In real-world applications where this assumption fails, standard practice relies on arbitrary gradient clipping heuristics that degrade accuracy. The article evaluates differentially private stochastic convex optimization under relaxed conditions, where data gradients are not strictly bounded but satisfy general bounded moment conditions across data dimensions.

To establish rigorous performance guarantees in this setting, the article develops a gradient-descent optimization framework powered by private heavy-tailed mean estimation routines. Instead of treating mean estimation as a rigid sub-procedure, the approach customizes the truncation thresholds across optimization steps to balance estimation bias against added noise variance. The analysis evaluates convex and strongly convex loss functions under concentrated differential privacy—a standard formulation that tracks privacy loss tightly across repeated iterations—as well as pure differential privacy. The article also establishes theoretical performance limits using an adapted version of Fano's inequality tailored to concentrated privacy.

The findings demonstrate substantial, provable performance improvements over previous benchmarks. For convex loss functions with bounded second moments, the proposed methods improve convergence error from prior rates of order n to the -1/3 to the standard non-private rate scaling with n to the -1/2 in sample size. For strongly convex losses, the algorithms achieve an excess risk bound that scales tightly with sample size and privacy parameters, accommodating moment conditions of any order k. Furthermore, the newly proved lower bounds match the algorithmic upper bounds for strongly convex objectives, establishing the fundamental statistical limits of private optimization with heavy-tailed data. The article also identifies an inherent performance gap between pure and concentrated privacy when moments are bounded coordinate-wise.

These results provide a solid mathematical foundation for deploying privacy-preserving optimization in environments with noisy, volatile, or outlier-heavy data. By replacing heuristic clipping methods with theoretically optimal truncation and noise calibration, organizations can achieve both formal privacy guarantees and superior model accuracy. For decision-makers, this translates to reduced risk of data exposure during model training while avoiding the performance penalties previously associated with non-Lipschitz, heavy-tailed data.

Organizations implementing private machine learning pipelines should adopt these adaptive truncation and mean estimation frameworks, choosing between parameter configurations based on their specific tolerance for privacy-accuracy trade-offs. Practitioners are advised to evaluate their data's empirical moment profile to tune truncation thresholds effectively. Future research should extend these guarantees to non-convex architectures, such as deep neural networks, and investigate whether the observed performance gaps between privacy definitions persist under alternative multidimensional moment constraints.

University of California, San Diegodifferential privaciesindividual privacyneural networksdifferentially private stochastic convex optimizationheavy-tailed gradientsprivate empirical risk minimization
Kamath et al (2022).pdf
  • Paper: Differentially Private Empirical Risk Minimization, Kamalika Chaudhuri et al. (2009). Its private empirical-risk-minimization framework introduces the convex optimization and privacy guarantees that this work sharpens for stochastic gradients with unbounded data.
  • Paper: What Can We Learn Privately?, Shiva Prasad Kasiviswanathan et al. (2008). Its foundational account of what differential privacy permits in learning clarifies the privacy framework underlying the source’s sharper optimization guarantees.
  • Paper: Deep Learning with Differential Privacy, Martín Abadi et al. (2016). Its clipped, noise-perturbed SGD and moments accountant provide useful grounding for the private iterative optimization methods whose bounded-gradient assumptions the source relaxes.
  • Paper: Linear-Time User-Level DP SCO via Robust Statistics, Pasin Manurangsi et al. (2025). It carries robust-statistics techniques into user-level private stochastic convex optimization, extending the source’s treatment of heavy-tailed gradients to a setting where each user contributes multiple samples.
Cover for Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data

Abstract

We study differentially private stochastic convex optimization (DP-SCO) under heavy-tailed gradient noise, a setting where the gradients have bounded variance but may have unbounded higher moments. We provide improved rates for DP-SCO in this setting, both in the population and empirical risk minimization problems. Our rates are based on a new clipping strategy that adapts to the gradient variance, and a new analysis of the stability of the clipped gradient descent. Our results improve upon the state-of-the-art rates in several regimes, and are optimal in some cases.

Topics

differential privaciesindividual privacyneural networksoptimizationperformance guaranteesstochastictradeoptimization problemsestimation method

Keywords

differentially private stochastic convex optimizationheavy-tailed gradientsprivate empirical risk minimizationprivate mean estimationdifferential privacyexcess risk boundsGaussian mechanism

Table of Contents

  • 1. Introduction
  • 1.1. Results
  • 1.2. Techniques
  • 2. Preliminaries
  • 2.1. Privacy Preliminaries
  • 2.2. Optimization Preliminaries
  • 2.3. Problem Setup
  • 3. A Framework for Stochastic Convex Optimization
  • 4. Mean Estimation Oracle
  • 5. Algorithms for SCO with Heavy-Tailed Data
  • 5.1. Convex Setting
  • 5.2. Strongly Convex Setting
  • 6. Lower Bounds for DP SCO with Heavy-Tailed Data
  • 6.1. Strongly-Convex Loss Functions
  • 6.2. Convex Loss Functions
  • 7. Acknowledgements
  • References
  • A. Useful Inequalities
  • B. Omitted Proofs
  • B.1. Proof of Theorem 3.1
  • B.2. Proof of Theorem 3.2
  • B.3. Proof of Theorem 4.1
  • B.4. Proof of Theorem 5.2
  • B.5. Proof of Theorem 5.4
  • B.6. Proof of Theorem 5.6
  • B.7. Proof of Lemma 6.2
  • B.8. Proof of Lemma 6.3
  • B.9. Proof of Theorem 6.4
  • B.10. Proof of Theorem 1.4
  • B.11. Theorem 5.2 with High-probability Guarantees

Knowls

  1. Knowl 1 — Convex SCO rates under concentrated differential privacy

    theoretical result

    For stochastic convex optimization in dimension dd, let nn samples be drawn i.i.d. from a distribution, and let the loss be nonnegative, convex, differentiable, and LL-smooth over a constraint set of diameter MM. Assume the population-risk gradient at an optimum is zero, the expected gradient has norm at most RR, and every coordinate of the centered per-sample gradient has bounded kk-th moment, for k≥2k\ge 2. When R,L≤10R,L\le 10, the paper gives two ρ\rho-concentrated differentially private (CDP) algorithms with the following expected excess population-risk bounds:

    O ⁣(Mdn+Md2nρ(ρ nMd3/2)1/k)O\!\left(\frac{Md}{\sqrt n}+\frac{Md^2}{n\sqrt{\rho}}\left(\frac{\sqrt{\rho}\,n}{Md^{3/2}}\right)^{1/k}\right)

    and, for any q∈[0.5,2]q\in[0.5,2],

    O ⁣(M d(3−q)/2n+M d(1+q)/2ρ1/4n).O\!\left(\frac{\sqrt M\,d^{(3-q)/2}}{\sqrt n}+\frac{\sqrt M\,d^{(1+q)/2}}{\rho^{1/4}\sqrt n}\right).

    The first rate uses a coordinatewise clipped median-of-means gradient estimator; the second uses a smoothed mean estimator. The parameter qq tunes the balance between the nonprivate and privacy-dependent terms. Both methods use projected gradient descent and run in time O(ndT)O(ndT) for TT iterations. These guarantees apply when the stated assumptions and parameter choices of the respective algorithms hold.

  2. Knowl 2 — Strongly convex SCO upper bound

    theoretical result

    Under the same bounded-coordinate-kk-th-moment, bounded-mean-gradient, and smoothness conditions for stochastic convex optimization, suppose additionally that the loss is λ\lambda-strongly convex. A ρ\rho-CDP projected-gradient algorithm using a private heavy-tailed mean estimator on disjoint data blocks across iterations achieves expected excess population risk

    O~ ⁣((M+1)2(λ+L)2λ2L[dn+d(dρ n)2(k−1)/k]),\widetilde O\!\left(\frac{(M+1)^2(\lambda+L)^2}{\lambda^2L}\left[\frac dn+d\left(\frac{\sqrt d}{\sqrt{\rho}\,n}\right)^{2(k-1)/k}\right]\right),

    where MM is the diameter of the constraint set. The number of gradient steps is polylogarithmic in nn and dd, and the running time is O(ndT)O(ndT). The result is nearly matched by the paper's strongly convex lower bound.

  3. Knowl 3 — Strongly convex SCO lower bound

    theoretical result

    For every sample size nn, dimension dd, moment order k≥2k\ge2, and privacy parameter ρ>0\rho>0, there are a smooth, strongly convex loss and a data distribution for which every ρ\rho-CDP algorithm has expected excess population risk at least

    Ω ⁣(dn+dmin⁡ ⁣{1,(dρ n)2(k−1)/k}).\Omega\!\left(\frac dn+d\min\!\left\{1,\left(\frac{\sqrt d}{\sqrt{\rho}\,n}\right)^{2(k-1)/k}\right\}\right).

    The construction satisfies the coordinatewise moment condition: at every parameter, each coordinate of the centered per-sample gradient has bounded kk-th moment at most 11. Thus the lower bound includes both a nonprivate sampling term and a privacy-dependent term, and matches the paper's strongly convex upper bound up to logarithmic factors in the regime where the minimum is not saturated.

  4. Knowl 4 — Convex SCO privacy lower bounds

    theoretical result

    For every n,dn,d, and k≥2k\ge2, there is a smooth convex stochastic optimization problem with centered coordinatewise gradient kk-th moments at most 11 for which any ρ\rho-CDP algorithm has expected excess population risk at least

    Ω ⁣(dn+dmin⁡ ⁣{1,(dρ n)(k−1)/k}).\Omega\!\left(\sqrt{\frac dn}+\sqrt d\min\!\left\{1,\left(\frac{\sqrt d}{\sqrt{\rho}\,n}\right)^{(k-1)/k}\right\}\right).

    For pure ε\varepsilon-differential privacy, a corresponding lower bound is

    Ω ⁣(dn+dmin⁡ ⁣{1,(dεn)(k−1)/k}).\Omega\!\left(\sqrt{\frac dn}+\sqrt d\min\!\left\{1,\left(\frac{d}{\varepsilon n}\right)^{(k-1)/k}\right\}\right).

    The distributions and losses may be chosen adversarially for the algorithm. The bounds exhibit different dimension dependence for pure and concentrated privacy under this coordinatewise moment assumption.

  5. Knowl 5 — Heavy-tailed mean estimation rates and privacy separation

    theoretical result

    Let X∈RdX\in\mathbb R^d have mean μ\mu, with each coordinate of X−μX-\mu having kk-th moment at most 11, where k≥2k\ge2. For a mean bounded in norm by a constant, the paper gives polynomial-time estimators from nn i.i.d. samples with probability at least 0.90.9 and error

    O~ ⁣(dn+d(dρ n)(k−1)/k)\widetilde O\!\left(\sqrt{\frac dn}+\sqrt d\left(\frac{\sqrt d}{\sqrt{\rho}\,n}\right)^{(k-1)/k}\right)

    under ρ\rho-CDP, and

    O~ ⁣(dn+d(dεn)(k−1)/k)\widetilde O\!\left(\sqrt{\frac dn}+\sqrt d\left(\frac{d}{\varepsilon n}\right)^{(k-1)/k}\right)

    under pure ε\varepsilon-DP. Matching expected-error lower bounds hold up to polylogarithmic factors, with the privacy-dependent terms capped by the corresponding d\sqrt d scale when written in full as dmin⁡{1,⋅}\sqrt d\min\{1,\cdot\}. Consequently, under this coordinatewise moment model, pure and concentrated privacy have different dimension dependence in their mean-estimation sample complexity.

  6. Knowl 6 — Coordinatewise clipped median-of-means private estimator

    algorithm

    The paper constructs a heavy-tailed mean estimator by clipping each coordinate, taking batch means, and aggregating them by a median. Given nn vectors Yi∈RdY_i\in\mathbb R^d with mean μ\mu, assume ∥μ∥2≤R≤10\|\mu\|_2\le R\le10 and that every centered coordinate has kk-th moment at most 11, for k≥2k\ge2. Let τ≥10\tau\ge10, confidence parameter 0<β<10<\beta<1, and m=4log⁡(2d/β)m=4\log(2d/\beta) (with the equal-batch convention of the estimator).

    Input: Samples Y_1,...,Y_n in R^d; truncation level τ\tau; confidence parameter β\beta
    Set m=4log⁡(2d/β)m = 4\log(2d/\beta) and split the samples into mm equal batches
    For each coordinate j=1,...,dj=1,...,d:
        For each batch r=1,...,mr=1,...,m:
            Clip every Yi[j]Y_i[j] in batch rr to [−3τ,3τ][-3\tau,3\tau]
            Compute the clipped batch mean ar,ja_{r,j}
        Set μ^j\widehat\mu_j to the median of a1,j,...,am,ja_{1,j},...,a_{m,j}
    Return μ^=(μ^1,...,μ^d)\widehat\mu=(\widehat\mu_1,...,\widehat\mu_d)

    With probability at least 1−β1-\beta, the nonprivate estimator has error

    ∥μ^−μ∥2=O ⁣(d[log⁡(d/β)n+(Cτ)k−1]),\|\widehat\mu-\mu\|_2=O\!\left(\sqrt d\left[\sqrt{\frac{\log(d/\beta)}n}+\left(\frac C\tau\right)^{k-1}\right]\right),

    where C≥14C\ge14 is a universal constant. A ρ\rho-CDP version adds independent Gaussian noise with covariance 1152τ2dlog⁡2(2d/β)ρn2Id\frac{1152\tau^2d\log^2(2d/\beta)}{\rho n^2}I_d; its error bound adds

    O ⁣(τlog⁡(d/β)dρ n(d+log⁡(1/β))).O\!\left(\frac{\tau\log(d/\beta)\sqrt d}{\sqrt\rho\,n}\left(\sqrt d+\sqrt{\log(1/\beta)}\right)\right).

    A pure ε\varepsilon-DP version adds independent Laplace noise of scale 48τdlog⁡(2d/β)εn\frac{48\tau d\log(2d/\beta)}{\varepsilon n} to each coordinate; its error bound adds O ⁣(τd3/2log⁡2(d/β)εn)O\!\left(\frac{\tau d^{3/2}\log^2(d/\beta)}{\varepsilon n}\right). The truncation level can be tuned to balance clipping bias against sampling and privacy noise.

  7. Knowl 7 — Concentrated-DP Fano inequality

    theoretical result

    Let p1,…,pMp_1,\ldots,p_M be probability distributions on a sample space, let θ(pi)∈Rd\theta(p_i)\in\mathbb R^d be the parameter associated with pip_i, and let ℓ\ell be a loss satisfying ℓ(θ(pi),θ(pj))≥r\ell(\theta(p_i),\theta(p_j))\ge r for every distinct pair. Suppose also that every pair obeys dTV(pi,pj)≤αd_{\mathrm{TV}}(p_i,p_j)\le\alpha and dKL(pi,pj)≤κd_{\mathrm{KL}}(p_i,p_j)\le\kappa. For any estimator θ^\widehat\theta that is ρ\rho-CDP on datasets of nn i.i.d. samples, the average expected loss satisfies

    1M∑i=1MEX∼pin ⁣[ℓ(θ^(X),θ(pi))]≥r2max⁡ ⁣{1−κ+log⁡2log⁡M,  1−ρ(n2α2+nα(1−α))+log⁡2log⁡M}.\frac1M\sum_{i=1}^M\mathbb E_{X\sim p_i^n}\!\left[\ell\bigl(\widehat\theta(X),\theta(p_i)\bigr)\right] \ge\frac r2\max\!\left\{1-\frac{\kappa+\log 2}{\log M},\;1-\frac{\rho\left(n^2\alpha^2+n\alpha(1-\alpha)\right)+\log 2}{\log M}\right\}.

    The first term in the maximum is the ordinary information-theoretic obstruction, while the second incorporates the privacy constraint. This inequality supplies a lower-bound tool for distinguishing among separated distributions under concentrated privacy.

  8. Knowl 8 — Gradient-oracle framework for private stochastic optimization

    model/method

    The paper reduces private stochastic convex optimization to repeated private estimation of the population-risk gradient. At each iteration, form sample gradients at the current parameter, pass them to a differentially private mean oracle, take a projected gradient step on the constraint set, and return the average iterates for a convex loss or the final iterate for a strongly convex loss. For convex losses, the framework reuses the full dataset at each step and requires uniform control of the gradient-estimation error; for strongly convex losses, it uses disjoint data blocks to retain independence across steps.

    If the oracle output g~(w)\widetilde g(w) satisfies, for every parameter ww, ∥E[g~(w)]−∇LD(w)∥2≤B\|\mathbb E[\widetilde g(w)]-\nabla L_D(w)\|_2\le B and E∥g~(w)−∇LD(w)∥22≤G2\mathbb E\|\widetilde g(w)-\nabla L_D(w)\|_2^2\le G^2, then projected gradient descent with constant step size η>0\eta>0 and TT iterations has expected excess risk for the averaged output bounded by

    M22ηT+η(R2+G2)+MB,\frac{M^2}{2\eta T}+\eta(R^2+G^2)+MB,

    where MM is the constraint-set diameter and ∥∇LD(w)∥2≤R\|\nabla L_D(w)\|_2\le R. Thus oracle bias, oracle variance, optimization error, and privacy can be analyzed separately before selecting the mean estimator.

  9. Knowl 9 — Coordinatewise heavy-tail model and SCO conditions

    assumption

    The paper studies losses ℓ(w,x)\ell(w,x) over a bounded convex set W⊆RdW\subseteq\mathbb R^d of diameter MM. The loss is nonnegative, differentiable, convex, and LL-smooth, and the population risk LD(w)=Ex∼D[ℓ(w,x)]L_D(w)=\mathbb E_{x\sim D}[\ell(w,x)] has zero gradient at an optimum. For each w∈Ww\in W, the gradient distribution has bounded coordinatewise centered moments: for every coordinate jj and some k≥2k\ge2,

    E[∣∂jℓ(w,X)−E[∂jℓ(w,X)]∣k]≤1.\mathbb E\left[\left|\partial_j\ell(w,X)-\mathbb E[\partial_j\ell(w,X)]\right|^k\right]\le1.

    The mean gradient is also assumed bounded, ∥E[∇ℓ(w,X)]∥2≤R\|\mathbb E[\nabla\ell(w,X)]\|_2\le R for a constant RR. This coordinatewise moment condition allows individual sample gradients to be unbounded; it is weaker than a uniform Lipschitz bound on each sample loss's gradient and is the heavy-tailed model underlying the paper's algorithms and lower bounds.

Coverage note — The appendix's high-probability refinement of the convex upper bound is omitted because it is a technical variant of the expected-risk guarantee; standard privacy preliminaries and proof-only intermediate steps are also omitted.

References

  1. 1.Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learning with differential privacy. In Proceedings of the 2016 ACM Conference on Computer and Communications Security, CCS ’16, pp. 308–318, New York, NY, USA, 2016. ACM.
  2. 2.Acharya, J., Sun, Z., and Zhang, H. Differentially private assouad, fano, and le cam. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, ALT ’21, pp. 48–78. JMLR, Inc., 2021.
  3. 3.Agarwal, N., Suresh, A. T., Yu, F. X. X., Kumar, S., and McMahan, B. cpSGD: Communication-efficient and differentially-private distributed SGD. In Advances in Neural Information Processing Systems 31, NeurIPS ’18, pp. 7575–7586. Curran Associates, Inc., 2018.
  4. 4.Asi, H., Feldman, V., Koren, T., and Talwar, K. Private stochastic convex optimization: Optimal rates in `1 geometry. In International Conference on Machine Learning, pp. 393–403. PMLR, 2021.
  5. 5.Barber, R. F. and Duchi, J. C. Privacy and statistical risk: Formalisms and minimax bounds. arXiv preprint arXiv:1412.4451, 2014.
  6. 6.Bassily, R., Smith, A., and Thakurta, A. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’14, pp. 464–473, Washington, DC, USA, 2014. IEEE Computer Society.
  7. 7.Bassily, R., Feldman, V., Talwar, K., and Thakurta, A. G. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems 32, NeurIPS ’19, pp. 11282–11291. Curran Associates, Inc., 2019.
  8. 8.Bassily, R., Guzman, C., and Nandi, A. Non-euclidean differentially private stochastic convex optimization. In Conference on Learning Theory, pp. 474–499. PMLR, 2021.
  9. 9.Bubeck, S. Convex optimization: Algorithms and complexity. Foundations and Trends® in Machine Learning, 8 (2–3):231–357, 2015.
  10. 10.Bun, M. and Steinke, T. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Proceedings of the 14th Conference on Theory of Cryptography, TCC ’16-B, pp. 635–658, Berlin, Heidelberg, 2016. Springer.
  11. 11.Bun, M., Ullman, J., and Vadhan, S. Fingerprinting codes and the price of approximate differential privacy. In Proceedings of the 46th Annual ACM Symposium on the Theory of Computing, STOC ’14, pp. 1–10, New York, NY, USA, 2014. ACM.
  12. 12.Chaudhuri, K. and Monteleoni, C. Privacy-preserving logistic regression. In Advances in Neural Information Processing Systems 21, NIPS ’08, pp. 289–296. Curran Associates, Inc., 2008.
  13. 13.Chaudhuri, K., Monteleoni, C., and Sarwate, A. D. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(29):1069–1109, 2011.
  14. 14.Dwork, C. and Rothblum, G. N. Concentrated differential privacy. arXiv preprint arXiv:1603.01887, 2016.
  15. 15.Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, TCC ’06, pp. 265–284, Berlin, Heidelberg, 2006. Springer.
  16. 16.Dwork, C., Rothblum, G. N., and Vadhan, S. Boosting and differential privacy. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS ’10, pp. 51–60, Washington, DC, USA, 2010. IEEE Computer Society.
  17. 17.Dwork, C., Smith, A., Steinke, T., Ullman, J., and Vadhan, S. Robust traceability from trace amounts. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’15, pp. 650–669, Washington, DC, USA, 2015. IEEE Computer Society.
  18. 18.Feldman, V., Koren, T., and Talwar, K. Private stochastic convex optimization: Optimal rates in linear time. In Proceedings of the 52nd Annual ACM Symposium on the Theory of Computing, STOC ’20, New York, NY, USA, 2020. ACM.
  19. 19.Holland, M. J. Robust descent using smoothed multiplicative noise. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 703–711. PMLR, 2019.
  20. 20.Hu, L., Ni, S., Xiao, H., and Wang, D. High dimensional differentially private stochastic optimization with heavy-tailed data. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, SIGMOD/PODS ’22, pp. 227–236, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450392600. doi: 10.1145/3517804.3524144.
  21. 21.Iyengar, R., Near, J. P., Song, D., Thakkar, O., Thakurta, A., and Wang, L. Towards practical differentially private convex optimization. In Proceedings of the 40th IEEE Symposium on Security and Privacy, SP ’19, pp. 299–316, Washington, DC, USA, 2019. IEEE Computer Society.
  22. 22.Jain, P. and Thakurta, A. G. (near) dimension independent risk bounds for differentially private learning. In Proceedings of the 31st International Conference on Machine Learning, ICML ’14, pp. 476–484. JMLR, Inc., 2014.
  23. 23.Kamath, G., Singhal, V., and Ullman, J. Private mean estimation of heavy-tailed distributions. In Proceedings of the 33rd Annual Conference on Learning Theory, COLT ’20, pp. 2204–2235, 2020.
  24. 24.Karwa, V. and Vadhan, S. Finite sample differentially private confidence intervals. In Proceedings of the 9th Conference on Innovations in Theoretical Computer Science, ITCS ’18, pp. 44:1–44:9, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  25. 25.Kasiviswanathan, S. P. and Jin, H. Efficient private empirical risk minimization for high-dimensional learning. In Proceedings of the 33rd International Conference on Machine Learning, ICML ’16, pp. 488–497. JMLR, Inc., 2016.
  26. 26.Kifer, D., Smith, A., and Thakurta, A. Private convex empirical risk minimization and high-dimensional regression. In Proceedings of the 25th Annual Conference on Learning Theory, COLT ’12, pp. 25.1–25.40, 2012.
  27. 27.Kulkarni, J., Lee, Y. T., and Liu, D. Private non-smooth erm and sco in subquadratic steps. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 4053–4064. Curran Associates, Inc., 2021.
  28. 28.Laurent, B. and Massart, P. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, pp. 1302–1338, 2000.
  29. 29.Rubinstein, B., Bartlett, P., Huang, L., and Taft, N. Learning in a large function space: Privacy-preserving mechanisms for SVM learning. The Journal of Privacy and Confidentiality, 4(1):65–100, 2012.
  30. 30.Shalev-Shwartz, S. and Ben-David, S. Understanding Machine Learning - From Theory to Algorithms. Cambridge University Press, 2014.
  31. 31.Shamir, O. A variant of azuma’s inequality for martingales with subgaussian tails. CoRR, abs/1110.2392, 2011.
  32. 32.Song, S., Chaudhuri, K., and Sarwate, A. D. Stochastic gradient descent with differentially private updates. In Proceedings of the 2013 IEEE Global Conference on Signal and Information Processing, GlobalSIP ’13, pp. 245–248, Washington, DC, USA, 2013. IEEE Computer Society.
  33. 33.Steinke, T. and Ullman, J. Interactive fingerprinting codes and the hardness of preventing false discovery. In Proceedings of the 28th Annual Conference on Learning Theory, COLT ’15, pp. 1588–1628, 2015.
  34. 34.Talwar, K., Thakurta, A., and Zhang, L. Nearly-optimal private LASSO. In Advances in Neural Information Processing Systems 28, NIPS ’15, pp. 3025–3033. Curran Associates, Inc., 2015.
  35. 35.Thakurta, A. G. and Smith, A. Differentially private feature selection via stability arguments, and the robustness of the lasso. In Proceedings of the 26th Annual Conference on Learning Theory, COLT ’13, pp. 819–850, 2013.
  36. 36.Wang, D., Ye, M., and Xu, J. Differentially private empirical risk minimization revisited: Faster and more general. In Advances in Neural Information Processing Systems 30, NIPS ’17, pp. 2722–2731. Curran Associates, Inc., 2017.
  37. 37.Wang, D., Xiao, H., Devadas, S., and Xu, J. On differentially private stochastic convex optimization with heavy-tailed data. In Proceedings of the 37th International Conference on Machine Learning, ICML ’20, pp. 10081–10091. JMLR, Inc., 2020.
  38. 38.Wang, D., Zhang, H., Gaboardi, M., and Xu, J. Estimating smooth glm in non-interactive local differential privacy model with public unlabeled data. In Algorithmic Learning Theory, pp. 1207–1213. PMLR, 2021.
  39. 39.Wang, L., Jayaraman, B., Evans, D., and Gu, Q. Efficient privacy-preserving stochastic nonconvex optimization. arXiv preprint arXiv:1910.13659, 2019.
  40. 40.Wu, X., Li, F., Kumar, A., Chaudhuri, K., Jha, S., and Naughton, J. Bolt-on differential privacy for scalable stochastic gradient descent-based analytics. In Proceedings of the 2017 ACM SIGMOD International Conference on Management of Data, SIGMOD ’17, pp. 1307–1322, New York, NY, USA, 2017. ACM.
  41. 41.Zhang, H., Mironov, I., and Hejazinia, M. Wide network learning with differential privacy. arXiv preprint arXiv:2103.01294, 2021.

Citation

MLA
Kamath, G., et al. “Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data”. International Conference on Machine Learning, vol. 162, 2022, pp. 10633–60, https://proceedings.mlr.press/v162/kamath22a.html.
APA
Kamath, G., Liu, X., & Zhang, H. (2022). Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data. International Conference on Machine Learning, 162, 10633–10660. https://proceedings.mlr.press/v162/kamath22a.html
Chicago
Kamath, G., X. Liu, and H. Zhang. 2022. “Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data”. International Conference on Machine Learning 162: 10633–60. https://proceedings.mlr.press/v162/kamath22a.html.
Harvard
Kamath, G., Liu, X. and Zhang, H. (2022) “Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data”, International Conference on Machine Learning. PMLR, pp. 10633–10660. Available at: https://proceedings.mlr.press/v162/kamath22a.html.
Vancouver
1. Kamath G, Liu X, Zhang H (2022) Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data. In: International Conference on Machine Learning. PMLR, pp 10633–10660

BibTeX

@InProceedings{pmlr-v162-kamath22a,
  title = 	 {Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data},
  author =       {Kamath, Gautam and Liu, Xingtu and Zhang, Huanyu},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {10633--10660},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/kamath22a/kamath22a.pdf},
  url = 	 {https://proceedings.mlr.press/v162/kamath22a.html},
  abstract = 	 {We study stochastic convex optimization with heavy-tailed data under the constraint of differential privacy (DP). Most prior work on this problem is restricted to the case where the loss function is Lipschitz. Instead, as introduced by Wang, Xiao, Devadas, and Xu \cite{WangXDX20}, we study general convex loss functions with the assumption that the distribution of gradients has bounded $k$-th moments. We provide improved upper bounds on the excess population risk under concentrated DP for convex and strongly convex loss functions. Along the way, we derive new algorithms for private mean estimation of heavy-tailed distributions, under both pure and concentrated DP. Finally, we prove nearly-matching lower bounds for private stochastic convex optimization with strongly convex losses and mean estimation, showing new separations between pure and concentrated DP.}
}
Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: https://creativecommons.org/licenses/by/4.0/