Research map / Federated learning and privacy / Differential privacy
Private Zeroth-Order Optimization with Public Data
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.
Proposes PAZO, three public-data-assisted private zeroth-order optimizers (mixing, subspace sampling, selection) that improve privacy/utility tradeoffs over DPZero and match or beat public-data first-order DP methods at small epsilon, with up to 16x speedup.
Problem
Private training with first-order DP methods (DP-SGD) is computationally and memory expensive, while existing private zeroth-order methods have low utility compared with DP-SGD and have only been tested on prompt-based LM fine-tuning.
Approach
Use a small public dataset's first-order gradients to guide private zeroth-order gradient estimation: mix public gradients with private two-point estimates (PAZO-M), restrict random perturbations to the span of public gradients (PAZO-P), or select the best public gradient via private function queries (PAZO-S), keeping privatization limited to function evaluations.
Key results
- PAZO variants outperform DPZero across all four datasets and, under small epsilon, outperform first-order public-data baselines by a large margin.
- PAZO is up to 16x faster per training iteration than first-order FO and FO+PUB methods while remaining comparably performant at epsilon=1.
- Theory gives d-independent error O(k) for PAZO-P and O(gamma^2 + sigma_2^2/b') for PAZO-S under gamma-similarity between public and private gradients.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add public-data guidance to private zeroth-order optimization | DPZero · CIFAR-10, Tiny-ImageNet, IMDB, and MNLI | accuracy | Helped |
| Use public-data-assisted zeroth-order optimization instead of public-data-assisted first-order optimization | PAZO versus FO+PUB · Vision and text tasks at small privacy budgets | accuracy | Helped |
| Use PAZO rather than first-order methods | DP training · Training iteration | runtime speedup: 2∼ 16× faster | Helped |
| Add public data to guide zeroth-order updates | Private zeroth-order methods · Vision and language tasks | convergence speed | Helped |
| Use PAZO-M rather than DPZero | Private zeroth-order optimization · Model dimension d | convergence error rate: $O(\sqrt{d}\log{d})$ -> $O(\frac{1-\alpha}{\alpha}\sqrt{d})$ | Helped |
| Use public-gradient-subspace sampling rather than full-dimensional sampling | PAZO-P · Model dimension d | convergence error rate: DPZero: $O(\sqrt{d}\log{d})$; PAZO-P: $O(k)$ | Helped |
| Use PAZO-S | Private zeroth-order optimization · Model dimension d | convergence error rate: DPZero: $O(\sqrt{d}\log{d})$; PAZO-S: $O(c)$ | Helped |
| Increase the number of random directions q (ablation) | DPZero · Tasks in the hyperparameter study | accuracy | Helped |
| Increase the number of random directions q (ablation) | PAZO · Tasks in the hyperparameter study | accuracy | No clear effect |
| Use PAZO-P without orthonormalizing public gradients (ablation) | PAZO-P · Empirical tasks | performance | No clear effect |
| Remove the noisy candidate from PAZO-S (ablation) | PAZO-S · Hyperparameter sensitivity study | accuracy | Mixed |
Surprising findings
- First-order DP methods are more sensitive to small epsilon than zeroth-order ones, so the zeroth-order gap narrows or reverses under strict privacy.
- PAZO's extra hyperparameters (alpha, b', k, epsilon) are robust, with PAZO-M's error improving over DPZero by a log d factor.
Limitations
- Convergence guarantees rely on an assumed gamma-similarity between public and private full gradients, which may not hold in practice.
- PAZO-S is motivated by a convexity argument but applied to non-convex models without guarantees.
- Requires extra hyperparameters for public batch size, mixing coefficient, number of public candidates and perturbation scale, plus extra privacy noise from q queries.
Experimental setup
Datasets: CIFAR-10 Tiny-ImageNet IMDB MNLI
Benchmarks: CIFAR-10 Tiny-ImageNet IMDB MNLI
Metrics: accuracy wall-clock time per iteration
Baselines: DP-SGD DPZero DPMD GEP DOPE-SGD
Builds on: DPZero DP-SGD DPMD DOPE-SGD GEP
Closest papers by meaning
- Differentially private optimization for non-decomposable objective functions (ICLR 2025 · similarity 0.88)
- Public-data Assisted Private Stochastic Optimization: Power and Limitations (NeurIPS 2024 · similarity 0.88)
- Differentially Private Stochastic Gradient Descent with Fixed-Size Minibatches: Tighter RDP Guarantees with or without Replacement (NeurIPS 2024 · similarity 0.88)
- The importance of feature preprocessing for differentially private linear optimization (ICLR 2024 · similarity 0.88)
- Optimal Differentially Private Model Training with Public Data (ICML 2024 · similarity 0.88)
- Towards hyperparameter-free optimization with differential privacy (ICLR 2025 · similarity 0.87)
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.