Research map / Learning theory and algorithms / Sample complexity
Public-data Assisted Private Stochastic Optimization: Power and Limitations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows tight lower bounds for public-data-assisted DP stochastic convex optimization and mean estimation with labeled public data, and gives dimension-independent rates for GLMs and fat-shattering classes when public data is unlabeled.
Problem
Understanding when public data can improve differentially private stochastic convex optimization and supervised learning, both with labeled public data (fundamental limits) and unlabeled public data (possible rate improvements).
Approach
Fingerprinting-code lower bounds adapted to PA-DP show that labeled public data yields no fundamental rate gain over treating all data as private or discarding private data; with unlabeled public data, public features define a low-dimensional subspace (or a finite cover of the hypothesis class) on which a private learner operates, achieving dimension-independent rates.
Key results
- For labeled public data, any (epsilon,delta)-PA-DP algorithm has excess risk Omega(min{1/sqrt(n_pub), 1/sqrt(n)+sqrt(d log(1/delta))/(n epsilon)}), so treating all data as private or discarding private data is near-optimal.
- For GLMs with unlabeled public data, an efficient algorithm using ~O(n_priv*epsilon) unlabeled public samples achieves rate O~(1/sqrt(n_priv)+1/sqrt(n_priv*epsilon)), dimension-independent.
- A lower bound shows Omega(n_priv*epsilon/log(1/delta)) public samples are needed to achieve that rate, so the public sample complexity is near-optimal.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use unlabeled public features to project private features into a lower-dimensional subspace | PA-DP learning of Euclidean GLMs · Unlabeled-public Euclidean GLMs | excess risk: O\br{\frac{1}{\sqrt{\npriv}} + \frac{1}{\sqrt{\npriv\epsilon}}} versus O\br{\frac{1}{\sqrt{\npriv}} +\frac{\sqrt{d}}{\np | Helped |
| Provide more unlabeled public samples beyond the rate-achieving requirement | PA-DP learning of Euclidean GLMs · Unlabeled-public Euclidean GLMs | excess risk | No clear effect |
| Use fewer unlabeled public samples than the rate-achieving requirement | PA-DP learning of Euclidean GLMs · Unlabeled-public Euclidean GLMs | excess risk | Hurt |
| Use complete/labeled public data together with private data rather than either discarding private data or treating all data as private | PA-DP stochastic convex optimization · Complete/labeled-public SCO | excess risk | No clear effect |
| Use unlabeled public data to construct a cover of the hypothesis class | PA-DP supervised learning with finite fat-shattering dimension · Unlabeled-public fat-shattering classes | excess risk: O\br{\frak{R}_{\npriv}(\cH) + \frac{1}{(\npriv\epsilon)^{1/3}} + \frac{1}{\sqrt{\npriv}}} | Helped |
| Use the public-data method for bounded-weight feed-forward neural networks | PA-DP supervised learning · Unlabeled-public feed-forward neural networks | excess risk | Helped |
| Use the public-data method for non-Euclidean GLMs | PA-DP supervised learning · Unlabeled-public non-Euclidean GLMs | excess risk | Helped |
Surprising findings
- With labeled public data, a small amount of public data yields no rate improvement under pure PA-DP when d >= n*epsilon.
- Under the unlabeled public data setting, the non-private rate is attained for constant epsilon, i.e., no price of privacy in the leading term.
Limitations
- Gap remains for the regime d in (n*epsilon/n_pub, n*epsilon) left as open for labeled public data.
- Fat-shattering results use pure DP exponential mechanism and are not efficient in general; the efficient algorithm applies to convex GLMs only.
- Lower bounds for the sqrt(log(1/delta)) term hold only under restrictions on d and n_pub.
Experimental setup
Metrics: excess risk expected estimation error
Baselines: projected noisy SGD regularized exponential mechanism
Builds on: fingerprinting codes projected noisy SGD exponential mechanism fat-shattering dimension
Closest papers by meaning
- Faster Algorithms for User-Level Private Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.90)
- Differentially Private Optimization with Sparse Gradients (NeurIPS 2024 · similarity 0.90)
- Optimal Differentially Private Model Training with Public Data (ICML 2024 · similarity 0.89)
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.89)
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates (AAAI 2025 · similarity 0.89)
- Differentially Private Stochastic Gradient Descent with Fixed-Size Minibatches: Tighter RDP Guarantees with or without Replacement (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.