Finding Differentially Private Second Order Stationary Points in Stochastic Minimax Optimization

• URL: http://arxiv.org/abs/2602.01339v1
• Date: Sun, 01 Feb 2026 17:06:48 GMT
• Title: Finding Differentially Private Second Order Stationary Points in Stochastic Minimax Optimization
• Authors: Difei Xu, Youming Tao, Meng Ding, Chenglin Fan, Di Wang,
• Abstract summary: We provide the first of the problem of finding differentially private (DP) second-order stationary points (SOSP) inilon (non-d) minimax problems.<n>We propose a first-order method that combines a nested descent-proascent scheme with SP-style variance reduction and Gaussian perturbations to ensure privacy.
• Score: 10.291697009273124
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We provide the first study of the problem of finding differentially private (DP) second-order stationary points (SOSP) in stochastic (non-convex) minimax optimization. Existing literature either focuses only on first-order stationary points for minimax problems or on SOSP for classical stochastic minimization problems. This work provides, for the first time, a unified and detailed treatment of both empirical and population risks. Specifically, we propose a purely first-order method that combines a nested gradient descent--ascent scheme with SPIDER-style variance reduction and Gaussian perturbations to ensure privacy. A key technical device is a block-wise ($q$-period) analysis that controls the accumulation of stochastic variance and privacy noise without summing over the full iteration horizon, yielding a unified treatment of both empirical-risk and population formulations. Under standard smoothness, Hessian-Lipschitzness, and strong concavity assumptions, we establish high-probability guarantees for reaching an $(α,\sqrt{ρ_Φα})$-approximate second-order stationary point with $α= \mathcal{O}( (\frac{\sqrt{d}}{n\varepsilon})^{2/3})$ for empirical risk objectives and $\mathcal{O}(\frac{1}{n^{1/3}} + (\frac{\sqrt{d}}{n\varepsilon})^{1/2})$ for population objectives, matching the best known rates for private first-order stationarity.

Related papers

• Differential Privacy in Kernelized Contextual Bandits via Random Projections [8.658538065693206]
  We consider the problem of contextual kernel bandits with contexts.<n>The underlying reward function belongs to a known Reproducing Kernel Hilbert Space.<n>We propose a novel algorithm that achieves the state-of-the-art cumulative regret of $widetildemathcalO(sqrtgamma_TT+fracgamma_Tvarepsilon_mathrmDP)$
  arXiv  Detail & Related papers  (2025-07-18T03:54:49Z)
• Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees [2.5871382203332907]
  Existing methods typically aim to find an $epsilon$-stochastic stationary point, where the expected violations of both constraints and first-order stationarity are within a prescribed accuracy.<n>In many practical applications, it is crucial that the constraints be nearly satisfied with certainty, making such an $epsilon$-stochastic stationary point potentially undesirable.
  arXiv  Detail & Related papers  (2024-09-16T00:26:42Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  We show that policies under study avoid strict saddle points / submanifolds with probability 1. This result provides an important sanity check as it shows that, almost always, the limit state of an algorithm can only be a local minimizer.
  arXiv  Detail & Related papers  (2023-11-04T11:12:24Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  We show a non-asymptotic bound of the order $t_mathrmmix tfracdn$ on the squared error of the last iterate of a standard scheme. We derive corollaries of these results for policy evaluation with Markov noise.
  arXiv  Detail & Related papers  (2021-12-23T18:47:50Z)
• Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps [23.38496232877376]
  We study the differentially private Empirical Risk Minimization (ERM) and Convex Optimization (SCO) problems for non-smooth convex functions. We get a (nearly) optimal bound on the excess empirical risk and excess population loss with subquadratic gradient complexity.
  arXiv  Detail & Related papers  (2021-03-29T05:58:56Z)
• Non-Euclidean Differentially Private Stochastic Convex Optimization [15.302167005107135]
  We show that noisy gradient descent (SGD) algorithms attain the optimal excess risk in low-dimensional regimes. Our work draws upon concepts from the geometry of normed spaces, such as the notions of regularity, uniform convexity, and uniform smoothness.
  arXiv  Detail & Related papers  (2021-03-01T19:48:44Z)
• Learning with User-Level Privacy [61.62978104304273]
  We analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution. We derive an algorithm that privately answers a sequence of $K$ adaptively chosen queries with privacy cost proportional to $tau$, and apply it to solve the learning tasks we consider.
  arXiv  Detail & Related papers  (2021-02-23T18:25:13Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  We propose a new algorithm -- the Momentum- Single-timescale Approximation (MSTSA) -- for tackling problems. MSTSA allows us to control the error in iterations due to inaccurate solution to the lower level subproblem.
  arXiv  Detail & Related papers  (2021-02-15T07:10:33Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  adversary-resilient distributed optimization, in which. machines can independently compute gradients, and cooperate. Our algorithm is based on a new concentration technique, and its sample complexity. It is very practical: it improves upon the performance of all prior methods when no. setting machines are present.
  arXiv  Detail & Related papers  (2020-12-28T17:19:32Z)
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification [54.22421582955454]
  We provide the first result of the optimal minimax guarantees for the excess risk for adversarially robust classification. Results are stated in terms of the Adversarial Signal-to-Noise Ratio (AdvSNR), which generalizes a similar notion for standard linear classification to the adversarial setting.
  arXiv  Detail & Related papers  (2020-06-29T21:06:52Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  We propose differentially private (DP) algorithms for bound non-dimensional optimization. We demonstrate two popular deep learning methods on the empirical advantages over standard gradient methods.
  arXiv  Detail & Related papers  (2020-06-24T06:01:24Z)

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.