mlsanityData to 13 Oct 2026

Public-data Assisted Private Stochastic Optimization: Power and Limitations

arXiv 2403.03856 ↗First posted 6 Mar 2024cs.LG cs.CR math.OCcited by 6

Not on the map. Why?

Abstract (arXiv)

We study the limits and capability of public-data assisted differentially private (PA-DP) algorithms. Specifically, we focus on the problem of stochastic convex optimization (SCO) with either labeled or unlabeled public data. For complete/labeled public data, we show that any (ε,δ)-PA-DP has excess risk tildeOmegabig(minbigfrac1√npub,frac1√n+frac√dnε big big), where d is the dimension, npub is the number of public samples, npriv is the number of private samples, and n=npub+npriv. These lower bounds are established via our new lower bounds for PA-DP mean estimation, which are of a similar form. Up to constant factors, these lower bounds show that the simple strategy of either treating all data as private or discarding the private data, is optimal. We also study PA-DP supervised learning with textitunlabeled public samples. In contrast to our previous result, we here show novel methods for leveraging public data in private supervised learning. For generalized linear models (GLM) with unlabeled public data, we show an efficient algorithm which, given tildeO(nprivε) unlabeled public samples, achieves the dimension independent rate tildeObig(frac1√npriv + frac1√nprivεbig). We develop new lower bounds for this setting which shows that this rate cannot be improved with more public samples, and any fewer public samples leads to a worse rate. Finally, we provide extensions of this result to general hypothesis classes with finite fat-shattering dimension with applications to neural networks and non-Euclidean geometries.

Key facts. Cited by 6 papers in the map (data through 13 Oct 2026). Builds on 29 of its 55 references that are in the map. First posted on arXiv 6 Mar 2024.

Builds on

29 of 55 references.

References · 29

  1. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  2. 2019FedMD: Heterogenous Federated Learning via Model Distillationcited by 459
  3. 2021Large Language Models Can Be Strong Differentially Private Learnerscited by 412
  4. 2021Differentially Private Fine-tuning of Language Modelscited by 398
  5. 2016Semi-supervised Knowledge Transfer for Deep Learning from Private Training Datacited by 347
  6. 2017Size-Independent Sample Complexity of Neural Networkscited by 289
  7. 2018Scalable Private Learning with PATEcited by 268
  8. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  9. 2020Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identificationcited by 89
  10. 2021Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learningcited by 86
  11. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 82
  12. 2014Private Learning and Sanitization: Pure vs. Approximate Differential Privacycited by 63
17 more
  1. 2015Between Pure and Approximate Differential Privacycited by 56
  2. 2021Public Data-Assisted Mirror Descent for Private Model Trainingcited by 49
  3. 2022Private Convex Optimization via Exponential Mechanismcited by 47
  4. 2022Differentially Private Bias-Term Fine-tuning of Foundation Modelscited by 47
  5. 2021Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settingscited by 45
  6. 2015Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimizationcited by 41
  7. 2019Limits of Private Learning with Access to Public Datacited by 39
  8. 2023Why Is Public Pretraining Necessary for Private Model Training?cited by 37
  9. 2022Private Estimation with Public Datacited by 32
  10. 2020A Primer on Private Statisticscited by 30
  11. 2020Private Query Release Assisted by Public Datacited by 27
  12. 2017Generalization for Adaptively-chosen Estimators via Stable Mediancited by 26
  13. 2022Differentially Private Generalized Linear Models Revisitedcited by 17
  14. 2023Private Distribution Learning with Public Data: The View from Sample Compressioncited by 14
  15. 2023PILLAR: How to make semi-private learning more effectivecited by 10
  16. 2023Optimal Differentially Private Model Training with Public Datacited by 9
  17. 2023On Size-Independent Sample Complexity of ReLU Networkscited by 6

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2025: 4; 2026: 2.

6 papers.

  1. 2025Synthetic Tabular Data: Methods, Attacks and Defensescited by 9
  2. 2025Leveraging Vertical Public-Private Split for Improved Synthetic Data Generationcited by 2
  3. 2025On the Gradient Complexity of Private Optimization with Private Oraclescited by 2
  4. 2025Lower Bounds for Public-Private Learning under Distribution Shiftcited by 0
  5. 2026Limits of Personalizing Differential Privacy Budgetscited by 0
  6. 2026High-Dimensional Asymptotics and Dataset Selection for Private Transfer Learningcited by 0