Quadratic Objective Perturbation: Curvature-Based Differential Privacy

• URL: http://arxiv.org/abs/2605.05905v1
• Date: Thu, 07 May 2026 09:16:53 GMT
• Title: Quadratic Objective Perturbation: Curvature-Based Differential Privacy
• Abstract summary: We introduce Quadratic Objective Perturbation (QOP), which perturbs the objective with a random quadratic form.<n>This perturbation induces strong convexity and enforces stability of the problem through curvature.<n>We extend the analysis to account for approximate solutions, showing that privacy guarantees are preserved under inexact solves.
• Score: 0.14323566945483496
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Objective perturbation is a standard mechanism in differentially private empirical risk minimization. In particular, Linear Objective Perturbation (LOP) enforces privacy by adding a random linear term, while strong convexity and stability are ensured by an additional deterministic quadratic term. However, this approach requires the strong assumption of bounded gradients of the loss function, which excludes many modern machine learning models. In this work, we introduce Quadratic Objective Perturbation (QOP), which perturbs the objective with a random quadratic form. This perturbation induces strong convexity and enforces stability of the problem through curvature, thereby enabling privacy and allowing sensitivity to be controlled through spectral properties of the perturbation rather than assumptions on the gradients. As a result, we obtain $(\varepsilon, δ)$-differential privacy under weaker assumptions, in the interpolation regime. Furthermore, we extend the analysis to account for approximate solutions, showing that privacy guarantees are preserved under inexact solves. Additionally, we derive utility guarantees in terms of empirical excess risk, and provide a theoretical and numerical comparison to LOP, highlighting the advantages of curvature-based perturbations. Finally, we discuss algorithmic aspects and show that the resulting problems can be solved efficiently using modern splitting schemes.

Related papers

• Kernel Methods for Refined Prophet Inequalities [27.407082709350707]
  Single-selection prophet inequality is a canonical online selection problem in which independent nonnegative values arrive sequentially.<n>We develop a general kernel method for single-threshold prophet inequalities.
  arXiv  Detail & Related papers  (2026-08-09T12:08:57Z)
• Derivative-Free Sequential Quadratic Programming for Equality-Constrained Stochastic Optimization [3.2489082010225485]
  We consider solving nonlinear optimization problems with an objective and deterministic equality constraints.<n>We propose a Derivative-Free Sequential Quadratic Programming (DF-SSQP) method.<n>Under standard assumptions, we establish the global almost-sure convergence of the proposed DF-SSQP method.
  arXiv  Detail & Related papers  (2025-10-25T23:51:20Z)
• Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations [57.179679246370114]
  We identify the distribution of random perturbations that minimizes the estimator's variance as the perturbation stepsize tends to zero.<n>Our findings reveal that such desired perturbations can align directionally with the true gradient, instead of maintaining a fixed length.
  arXiv  Detail & Related papers  (2025-10-22T19:06:39Z)
• Spectral Graph Clustering under Differential Privacy: Balancing Privacy, Accuracy, and Efficiency [53.98433419539793]
  We study the problem of spectral graph clustering under edge differential privacy (DP)<n>Specifically, we develop three mechanisms: (i) graph perturbation via randomized edge flipping combined with adjacency matrix shuffling, which enforces edge privacy; (ii) private graph projection with additive Gaussian noise in a lower-dimensional space to reduce dimensionality and computational complexity; and (iii) a noisy power iteration method that distributes Gaussian noise across iterations to ensure edge DP while maintaining convergence.
  arXiv  Detail & Related papers  (2025-10-08T15:30:27Z)
• 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)
• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  We propose a Trust Sequential Quadratic Programming method to find both first and second-order stationary points. To converge to first-order stationary points, our method computes a gradient step in each iteration defined by minimizing a approximation of the objective subject. To converge to second-order stationary points, our method additionally computes an eigen step to explore the negative curvature the reduced Hessian matrix.
  arXiv  Detail & Related papers  (2024-09-24T04:39:47Z)
• Randomized algorithms and PAC bounds for inverse reinforcement learning in continuous spaces [47.907236421762626]
  This work studies discrete-time discounted Markov decision processes with continuous state and action spaces. We first consider the case in which we have access to the entire expert policy and characterize the set of solutions to the inverse problem.
  arXiv  Detail & Related papers  (2024-05-24T12:53:07Z)
• Privacy Risk for anisotropic Langevin dynamics using relative entropy bounds [1.911678487931003]
  We show how anisotropic noise can lead to better privacy-accuracy trade-offs. We show how anisotropic noise can lead to better privacy-accuracy trade-offs.
  arXiv  Detail & Related papers  (2023-02-01T21:32:22Z)
• Distributed Stochastic Optimization under a General Variance Condition [13.911633636387059]
  Distributed optimization has drawn great attention recently due to its effectiveness in solving largescale machine learning problems. We revisit the classical Federated Averaging (Avg) and establish the convergence results under only a mild variance for smooth non objective functions. Almost a stationary convergence point is also established under the gradients condition.
  arXiv  Detail & Related papers  (2023-01-30T05:48:09Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  Modern machine learning algorithms aim to extract fine-grained information from data to provide accurate predictions, which often conflicts with the goal of privacy protection. This paper addresses the practical and theoretical importance of developing privacy-preserving machine learning algorithms that ensure good performance while preserving privacy.
  arXiv  Detail & Related papers  (2022-09-09T08:54:13Z)
• Inference on Strongly Identified Functionals of Weakly Identified Functions [71.42652863687117]
  We study a novel condition for the functional to be strongly identified even when the nuisance function is not. We propose penalized minimax estimators for both the primary and debiasing nuisance functions.
  arXiv  Detail & Related papers  (2022-08-17T13:38:31Z)
• Improving Generalization via Uncertainty Driven Perturbations [107.45752065285821]
  We consider uncertainty-driven perturbations of the training data points. Unlike loss-driven perturbations, uncertainty-guided perturbations do not cross the decision boundary. We show that UDP is guaranteed to achieve the robustness margin decision on linear models.
  arXiv  Detail & Related papers  (2022-02-11T16:22:08Z)

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.