Private Zeroth-Order Optimization with Public Data

AI summary

Overview

Research area: Differentially private machine learning, specifically private optimization algorithms (zeroth-order versus first-order methods) and privacy/utility tradeoffs.

Technical level: Advanced. The paper includes formal DP definitions, convergence theorems with explicit error rates, and gradient-estimator derivations, alongside an empirical study.

Scope in one sentence: The paper introduces PAZO, a family of three public-data-assisted zeroth-order optimizers that use a small amount of public data to guide private gradient approximation, and it evaluates them across vision and text pre-training and fine-tuning tasks against private first-order baselines.

What This Paper Is About

First-order differentially private training methods such as DP-SGD rely on per-sample gradient clipping, which is computationally and memory expensive at scale. Zeroth-order methods avoid this by privatizing scalar function queries instead of gradients, but they produce high-variance estimates and have generally lagged behind DP-SGD in utility, with prior work mostly tested on narrow settings like prompt tuning of language models. The goal of this paper is to close that utility gap by using non-sensitive public data—and its first-order gradients—to steer and constrain the private zeroth-order search.

Key Contributions

1. Algorithm design: The paper proposes the first set of private zeroth-order optimizers augmented with public gradients, denoted PAZO-{M, P, S}: PAZO-M mixes private zeroth-order estimates with public first-order gradients; PAZO-P samples random directions inside the subspace spanned by public gradients; and PAZO-S selects the best public gradient using function queries on private data. Privatization is applied only on top of function evaluations to preserve zeroth-order efficiency.

2. Theoretical analysis: The paper provides privacy and utility guarantees for each method under a γ-similarity assumption between public and private full gradients. PAZO-M improves the vanilla zeroth-order method by a factor of log d with a rate of O((1−α)/α · √d), while PAZO-{P, S} obtain d-independent rates.

3. Empirical validation across domains and settings: Evaluation covers both image and text domains and both pre-training and fine-tuning, spanning CIFAR-10 with NFResNet18 trained from scratch, Tiny-ImageNet with a Places365 pre-trained ViT-S, IMDB with an LSTM trained from scratch, and MNLI with prompt-tuned RoBERTa-base.

4. Efficiency demonstration: PAZO is reported to be 2 to 16 times faster per training iteration than private first-order methods with or without public data, while being comparable or better in utility.

Main Findings

• PAZO beats vanilla private zeroth-order across all settings: All three PAZO variants outperform DPZero on the four datasets evaluated, though no single PAZO variant dominates the others in every setting.

• Zeroth-order methods are more robust to strict privacy: Across privacy budgets ε = {0.1, 0.5, 1, 2, 3}, first-order methods (DP-SGD, DPMD, DOPE-SGD, GEP), with or without public data, were much more sensitive to smaller ε than zeroth-order methods. Under small ε, PAZO was superior to first-order baselines by a large margin.

• Public data expands the regime where zeroth-order wins: The performance gap between zeroth-order and first-order methods decreases as ε decreases both with and without public data, and adding public data expands the range of ε values where zeroth-order methods outperform first-order ones. PAZO (ZO+PUB) achieves a better privacy/utility tradeoff than the best public-data-augmented first-order method (FO+PUB) when ε is small.

• Faster convergence: Public information significantly accelerates convergence of private zeroth-order methods relative to DPZero, which matters because fewer iterations means less accumulated privacy noise. The paper notes that MeZO and DPZero had been run 100 times and 10 times more steps than first-order methods in prior work.

• Runtime per iteration: PAZO is comparable to or more performant than baselines while being 2 ~ 16 times faster per training iteration, and the abstract reports up to 16× runtime speedup. Experiments were run on a single 48GB L40S GPU.

• Theoretical rates: PAZO-M converges at a rate with an O((1−α)/α · √d) term, saving a log d factor versus DPZero plus a constant improvement if α > 1/2, and it carries an additional bias term from public gradients. PAZO-P has a d-independent error rate O(k) plus error from biased public stochastic gradients and private stochastic gradients, with k ≪ log d in practice. PAZO-S reaches a d-independent bound O(γ² + σ₂²/b′) as T → ∞, where the remaining σ₂²/b′ term comes from stochastic public sampling.

• Sharper bounds under bounded loss: If the loss is additionally assumed bounded (|f(x_t)| ≤ S), the paper reports improved bounds of O((1−α)/α · d^{1/4}) for PAZO-M and O(√k log k) for PAZO-P.

• Hyperparameter robustness: PAZO performance is robust to public batch size b′, mixing coefficient α, number of public candidates k, and perturbation scale ε. PAZO also has reduced dependence on the number of random direction queries q compared with DPZero, which benefits from larger q. The study used q ∈ {1, 5} and selected q = 1 where the gap was negligible.

• Public/private distribution shift is studied: The authors introduce distribution shifts between private and public data, including class imbalance and semantic context shifts of various extents, with details in the appendix.

Methodology in Plain English

Zeroth-order methods estimate a gradient by querying the loss value at two nearby points in a random direction and using the difference to form a direction vector. This is easy to privatize—you clip the scalar query results and add Gaussian noise—but the estimate is noisy, especially in high dimensions.

The paper's idea is to use a small set of public data, assumed to be drawn from a distribution similar to the private data, to make that search smarter. Three approaches are developed. PAZO-M takes a convex combination of the public batch gradient and the private zeroth-order estimate, with the random directions sampled from a sphere of radius d^{1/4} so that the norms of the two components are aligned and the mixing coefficient is easy to tune. PAZO-P restricts random directions to the subspace spanned by k public gradients, turning a d-dimensional search into a k-dimensional one, which is where the d-independent rates come from. PAZO-S queries the private loss at the points produced by each of k public gradients (plus a noisy additional candidate), picks the best one by the private function values, and moves in that direction.

Privacy is handled by bounding the L2 sensitivity of the sum of function queries with a clipping threshold C and adding Gaussian noise with variance qC²σ², where q is the number of queries per iteration; the privacy bound per iteration is the same for any q. Composition across T rounds uses the moments accountant with sampling ratio b/n, yielding a σ requirement of c₂ · b√(T log(1/δ)) / (nε). For utility analysis, the authors define γ-similarity as the norm of the gap between full public and private gradients being at most γ at every step, which is weaker than prior coordinate-wise similarity conditions combined with bounded-gradient assumptions, and they add Lipschitz, smoothness, and bounded-variance assumptions on private and public stochastic gradients.

Why This Matters

The paper argues that zeroth-order private training can be a practical alternative to DP-SGD when public data of similar distribution is available, which is common in many real deployments where a public dataset accompanies a sensitive one. It shows the advantage is largest exactly where DP-SGD hurts most—tight privacy budgets—and that the approach also saves wall-clock time.

Real-world applications:

• Fine-tuning pre-trained language or vision models on sensitive user data when a public corpus of similar content is available.
• Training on sensitive image data (e.g., medical or personal imagery) with public proxy datasets.
• Private natural language tasks such as sentiment classification on user reviews or prompt-based tuning for private text datasets.
• Large-batch private training pipelines where per-sample gradient clipping is memory-infeasible, since PAZO avoids per-sample gradient clipping.

Industry relevance: DP-SGD's per-sample clipping creates memory and computation overheads—vanilla DP-SGD consumes O(bd) memory for per-sample clipped gradients, and ghost-clipping/bookkeeping reduces layer-wise storage to min{2bp, bd}. Methods that avoid per-sample gradients while retaining DP guarantees have direct cost implications for large-scale private training. The paper also releases code at github.com/xuchengong/pazo.

Future Directions

• Sharpening the convergence bounds by considering other similarity metrics beyond γ-similarity.
• Exploring a broader set of public and private dataset pairs in practical DP training applications.
• Extending the analysis to incorporate more advanced clipping analysis, which the paper notes as a natural extension of its conservative clipping-threshold bound.
• Combining PAZO with prior zeroth-order improvements such as using previous estimated gradient directions or sparsifying gradients, which the paper states its techniques can be combined with.

Target Audience

Researchers and practitioners working on differentially private machine learning, private optimization, and privacy-preserving model training—particularly those interested in alternatives to DP-SGD, in zeroth-order optimization, or in combining public and private data. Readers benefit from familiarity with differential privacy definitions, gradient estimators, and convergence analysis, though the empirical results and the plain-language description of the three algorithms are accessible to a broader machine learning audience.

Authors’ abstract

One of the major bottlenecks for deploying popular first-order differentially private (DP) machine learning algorithms (e.g., DP-SGD) lies in their high computation and memory cost, despite the existence of optimized implementations. Zeroth-order methods have promise in mitigating the overhead, as they leverage function evaluations to approximate the gradients, hence significantly easier to privatize. While recent works have explored zeroth-order approaches in both private and non-private settings, they still suffer from relatively low utilities compared with DP-SGD, and have only been evaluated in limited application domains. In this work, we propose to leverage public information to guide and improve gradient approximation of private zeroth-order algorithms. We explore a suite of public-data-assisted zeroth-order optimizers (PAZO) with minimal overhead. We provide theoretical analyses of the PAZO framework under an assumption of the similarity between public and private data. Empirically, we demonstrate that PAZO achieves superior privacy/utility tradeoffs across vision and text tasks in both pre-training and fine-tuning settings, outperforming the best first-order baselines (with public data) especially in highly private regimes, while offering up to $16\times$ runtime speedup.