Private Zeroth-Order Optimization with Public Data

• URL: http://arxiv.org/abs/2511.10859v1
• Date: Thu, 13 Nov 2025 23:51:24 GMT
• Title: Private Zeroth-Order Optimization with Public Data
• Authors: Xuchen Gong, Tian Li,
• Abstract summary: One of the major bottlenecks for deploying first-order differentially private machine learning algorithms is their high computation and memory cost.<n>We propose to leverage public information to guide and improve approximation of private zeroth-order algorithms.<n>We show that PAZO achieves superior privacy/utility tradeoffs across vision and text tasks in both pre-training and fine-tuning settings.
• Score: 5.409688800035885
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Private Hyperparameter Tuning with Ex-Post Guarantee [98.43027866582979]
  " Utility-first" privacy mechanisms prioritize a desired level of utility and then determine the corresponding privacy cost.<n>We extend the work of Wu et al. [ 2019] and Liu and Talwar [ 2019] to support any sequence of private estimators.<n>We demonstrate that hyper parameter tuning for these estimators, including the selection of an optimal privacy budget, can be performed without additional privacy cost.
  arXiv  Detail & Related papers  (2025-08-21T02:42:23Z)
• Privacy Amplification in Differentially Private Zeroth-Order Optimization with Hidden States [23.033229440303355]
  We show that convergent privacy bounds can be established for zeroth-order optimization.<n>Our analysis generalizes the celebrated privacy amplification-by-iteration framework to the setting of smooth loss functions.<n>It induces better DP zeroth-order algorithmic designs previously unknown to the literature.
  arXiv  Detail & Related papers  (2025-05-30T18:55:32Z)
• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  User-level differentially private convex optimization (DP-SCO) has garnered significant attention due to the importance of safeguarding user privacy in machine learning applications.<n>Current methods, such as those based on differentially private gradient descent (DP-SGD), often struggle with high noise accumulation and suboptimal utility.<n>We introduce a novel linear-time algorithm that leverages robust statistics, specifically the median and trimmed mean, to overcome these challenges.
  arXiv  Detail & Related papers  (2025-02-13T02:05:45Z)
• Optimized Tradeoffs for Private Prediction with Majority Ensembling [59.99331405291337]
  We introduce the Data-dependent Randomized Response Majority (DaRRM) algorithm.<n>DaRRM is parameterized by a data-dependent noise function $gamma$, and enables efficient utility optimization over the class of all private algorithms.<n>We show that DaRRM provably enjoys a privacy gain of a factor of 2 over common baselines, with fixed utility.
  arXiv  Detail & Related papers  (2024-11-27T00:48:48Z)
• Provable Privacy with Non-Private Pre-Processing [56.770023668379615]
  We propose a general framework to evaluate the additional privacy cost incurred by non-private data-dependent pre-processing algorithms. Our framework establishes upper bounds on the overall privacy guarantees by utilising two new technical notions.
  arXiv  Detail & Related papers  (2024-03-19T17:54:49Z)
• Private Fine-tuning of Large Language Models with Zeroth-order Optimization [51.19403058739522]
  Differentially private gradient descent (DP-SGD) allows models to be trained in a privacy-preserving manner.<n>We introduce DP-ZO, a private fine-tuning framework for large language models by privatizing zeroth order optimization methods.
  arXiv  Detail & Related papers  (2024-01-09T03:53:59Z)
• TAN Without a Burn: Scaling Laws of DP-SGD [70.7364032297978]
  Differentially Private methods for training Deep Neural Networks (DNNs) have progressed recently. We decouple privacy analysis and experimental behavior of noisy training to explore the trade-off with minimal computational requirements. We apply the proposed method on CIFAR-10 and ImageNet and, in particular, strongly improve the state-of-the-art on ImageNet with a +9 points gain in top-1 accuracy.
  arXiv  Detail & Related papers  (2022-10-07T08:44:35Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  We characterize privacy guarantees for individual examples when releasing models trained by DP-SGD. We find that most examples enjoy stronger privacy guarantees than the worst-case bound. This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees.
  arXiv  Detail & Related papers  (2022-06-06T13:49:37Z)
• Pre-trained Perceptual Features Improve Differentially Private Image Generation [8.659595986100738]
  Training even moderately-sized generative models with differentially-private descent gradient (DP-SGD) is difficult. We advocate building off a good, relevant representation on an informative public dataset, then learning to model the private data with that representation. Our work introduces simple yet powerful foundations for reducing the gap between private and non-private deep generative models.
  arXiv  Detail & Related papers  (2022-05-25T16:46:01Z)
• Output Perturbation for Differentially Private Convex Optimization with Improved Population Loss Bounds, Runtimes and Applications to Private Adversarial Training [12.386462516398469]
  Finding efficient, easily implementable differentially private (DP) algorithms that offer strong excess risk bounds is an important problem in modern machine learning. We provide the tightest known $(epsilon, 0)$-DP population loss bounds and fastest runtimes under the presence of smoothness and strong convexity. We apply our theory to two learning frameworks: tilted ERM and adversarial learning frameworks.
  arXiv  Detail & Related papers  (2021-02-09T08:47:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.