# Public-data Assisted Private Stochastic Optimization: Power and Limitations

arXiv: https://arxiv.org/abs/2403.03856 · HTML: https://mlsanity.com/paper/2403.03856/

## Key facts

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

## Builds on (most cited first, 29 of 29)

- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [FedMD: Heterogenous Federated Learning via Model Distillation](https://mlsanity.com/paper/1910.03581/) (2019)
- [Large Language Models Can Be Strong Differentially Private Learners](https://mlsanity.com/paper/2110.05679/) (2021)
- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (2021)
- [Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data](https://mlsanity.com/paper/1610.05755/) (2016)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Scalable Private Learning with PATE](https://mlsanity.com/paper/1802.08908/) (2018)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification](https://mlsanity.com/paper/2007.03813/) (2020)
- [Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning](https://mlsanity.com/paper/2102.12677/) (2021)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [Private Learning and Sanitization: Pure vs. Approximate Differential Privacy](https://mlsanity.com/paper/1407.2674/) (2014)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [Public Data-Assisted Mirror Descent for Private Model Training](https://mlsanity.com/paper/2112.00193/) (2021)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Differentially Private Bias-Term Fine-tuning of Foundation Models](https://mlsanity.com/paper/2210.00036/) (2022)
- [Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings](https://mlsanity.com/paper/2107.05585/) (2021)
- [Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization](https://mlsanity.com/paper/1512.09170/) (2015)
- [Limits of Private Learning with Access to Public Data](https://mlsanity.com/paper/1910.11519/) (2019)
- [Why Is Public Pretraining Necessary for Private Model Training?](https://mlsanity.com/paper/2302.09483/) (2023)
- [Private Estimation with Public Data](https://mlsanity.com/paper/2208.07984/) (2022)
- [A Primer on Private Statistics](https://mlsanity.com/paper/2005.00010/) (2020)
- [Private Query Release Assisted by Public Data](https://mlsanity.com/paper/2004.10941/) (2020)
- [Generalization for Adaptively-chosen Estimators via Stable Median](https://mlsanity.com/paper/1706.05069/) (2017)
- [Differentially Private Generalized Linear Models Revisited](https://mlsanity.com/paper/2205.03014/) (2022)
- [Private Distribution Learning with Public Data: The View from Sample Compression](https://mlsanity.com/paper/2308.06239/) (2023)
- [PILLAR: How to make semi-private learning more effective](https://mlsanity.com/paper/2306.03962/) (2023)
- [Optimal Differentially Private Model Training with Public Data](https://mlsanity.com/paper/2306.15056/) (2023)
- [On Size-Independent Sample Complexity of ReLU Networks](https://mlsanity.com/paper/2306.01992/) (2023)

## Built on by (most cited first, 6 of 6)

- [Synthetic Tabular Data: Methods, Attacks and Defenses](https://mlsanity.com/paper/2506.06108/) (2025)
- [Leveraging Vertical Public-Private Split for Improved Synthetic Data Generation](https://mlsanity.com/paper/2504.10987/) (2025)
- [On the Gradient Complexity of Private Optimization with Private Oracles](https://mlsanity.com/paper/2511.13999/) (2025)
- [Lower Bounds for Public-Private Learning under Distribution Shift](https://mlsanity.com/paper/2507.17895/) (2025)
- [Limits of Personalizing Differential Privacy Budgets](https://mlsanity.com/paper/2605.13503/) (2026)
- [High-Dimensional Asymptotics and Dataset Selection for Private Transfer Learning](https://mlsanity.com/paper/2610.02578/) (2026)

## 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.