Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problems

• URL: http://arxiv.org/abs/2104.02988v1
• Date: Wed, 7 Apr 2021 08:37:07 GMT
• Title: Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problems
• Authors: Digvijay Boob and Crist\'obal Guzm\'an
• Abstract summary: We conduct the first systematic study of variational inequality (SVI) and saddle point inequality problems under the constraint of differential privacy-(DP) We propose two algorithms: Noisy Extragradient (NSEG) and Noisy Inexact Proximal Point (NISPP)
• Score: 5.051036968777244
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we conduct the first systematic study of stochastic variational inequality (SVI) and stochastic saddle point (SSP) problems under the constraint of differential privacy-(DP). We propose two algorithms: Noisy Stochastic Extragradient (NSEG) and Noisy Inexact Stochastic Proximal Point (NISPP). We show that sampling with replacement variants of these algorithms attain the optimal risk for DP-SVI and DP-SSP. Key to our analysis is the investigation of algorithmic stability bounds, both of which are new even in the nonprivate case, together with a novel "stability implies generalization" result for the gap functions for SVI and SSP problems. The dependence of the running time of these algorithms, with respect to the dataset size $n$, is $n^2$ for NSEG and $\widetilde{O}(n^{3/2})$ for NISPP.

Related papers

• SOREL: A Stochastic Algorithm for Spectral Risks Minimization [1.6574413179773761]
  spectral risk has wide applications in machine learning, especially in real-world decision-making. By assigning different weights to the losses of different sample points, it allows the model's performance to lie between the average performance and the worst-case performance. We propose SOREL, the first gradient-based algorithm with convergence guarantees for the spectral risk minimization.
  arXiv  Detail & Related papers  (2024-07-19T18:20:53Z)
• Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction [26.9632099249085]
  We propose two new variants of SPS and SLS, called AdaSPS and AdaSLS, which guarantee convergence in non-interpolation settings. We equip AdaSPS and AdaSLS with a novel variance reduction technique and obtain algorithms that require $smashwidetildemathcalO(n+1/epsilon)$ gradient evaluations.
  arXiv  Detail & Related papers  (2023-08-11T10:17:29Z)
• Accelerated stochastic approximation with state-dependent noise [7.4648480208501455]
  We consider a class of smooth convex optimization problems under general assumptions on the quadratic noise in the gradient observation. Such problems naturally arise in a variety of applications, in particular, in the well-known generalized linear regression problem in statistics. We show that both SAGD and SGE, under appropriate conditions, achieve the optimal convergence rate.
  arXiv  Detail & Related papers  (2023-07-04T06:06:10Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  We propose a sequential quadratic programming algorithm (TR-StoSQP) to solve nonlinear optimization problems with objectives and deterministic equality constraints. The algorithm adaptively selects the trust-region radius and, compared to the existing line-search StoSQP schemes, allows us to utilize indefinite Hessian matrices.
  arXiv  Detail & Related papers  (2022-11-29T05:52:17Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGD and DP-NSGD mitigate the risk of large models memorizing sensitive training data. We show that these two algorithms achieve similar best accuracy while DP-NSGD is comparatively easier to tune than DP-SGD.
  arXiv  Detail & Related papers  (2022-06-27T03:45:02Z)
• On Private Online Convex Optimization: Optimal Algorithms in $\ell_p$-Geometry and High Dimensional Contextual Bandits [9.798304879986604]
  We study the Differentially private (DP) convex optimization problem with streaming data sampled from a distribution and arrives sequentially. We also consider the continual release model where parameters related to private information are updated and released upon each new data, often known as the online algorithms. Our algorithm achieves in linear time the optimal excess risk when $1pleq 2$ and the state-of-the-art excess risk meeting the non-private lower ones when $2pleqinfty$.
  arXiv  Detail & Related papers  (2022-06-16T12:09:47Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  We study the citetgarber 2020online, where the loss functions may be chosen by an adversary, but are then presented online in a uniformly random order. We show that citetgarber 2020online algorithms achieve the optimal bounds and significantly improve their stability.
  arXiv  Detail & Related papers  (2021-06-29T09:48:46Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• 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)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  We provide sharp upper and lower bounds for several forms of gradient descent (SGD) on arbitrary Lipschitz nonsmooth convex losses. Our bounds allow us to derive a new algorithm for differentially private nonsmooth convex optimization with optimal excess population risk.
  arXiv  Detail & Related papers  (2020-06-12T02:45:21Z)

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.