Momentum Aggregation for Private Non-convex ERM

• URL: http://arxiv.org/abs/2210.06328v1
• Date: Wed, 12 Oct 2022 15:48:26 GMT
• Title: Momentum Aggregation for Private Non-convex ERM
• Abstract summary: We introduce new algorithms and guarantees for privacy-preserving nondimensional non Empirical Minimization on smooth $ddimensional objectives. We develop gradient descent objectives that exploits the recurrence of smooth examples.
• Score: 45.17205354923149
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce new algorithms and convergence guarantees for privacy-preserving non-convex Empirical Risk Minimization (ERM) on smooth $d$-dimensional objectives. We develop an improved sensitivity analysis of stochastic gradient descent on smooth objectives that exploits the recurrence of examples in different epochs. By combining this new approach with recent analysis of momentum with private aggregation techniques, we provide an $(\epsilon,\delta)$-differential private algorithm that finds a gradient of norm $\tilde O\left(\frac{d^{1/3}}{(\epsilon N)^{2/3}}\right)$ in $O\left(\frac{N^{7/3}\epsilon^{4/3}}{d^{2/3}}\right)$ gradient evaluations, improving the previous best gradient bound of $\tilde O\left(\frac{d^{1/4}}{\sqrt{\epsilon N}}\right)$.

Related papers

• Underdamped Langevin MCMC with third order convergence [1.8374319565577153]
  We present a new numerical method for the underdamped Langevin diffusion (ULD)<n>Under the assumptions that the gradient and Hessian of $f$ are Lipschitz continuous, our algorithm achieves a 2-Wasserstein error of $varepsilon$ in $mathcalO(sqrtd/varepsilon)$ steps.<n>This is the first gradient-only method for ULD with third order convergence.
  arXiv  Detail & Related papers  (2025-08-22T16:00:01Z)
• Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization [10.913566070767596]
  We study the problem of (fin sum) minimax optimization in the Differential Privacy (DP) model. We show that it is possible to get an estimator whose Descent $l$-norm of the empirical risk function is upper bounded by $tO(n)(n)$, whered is the sample size.
  arXiv  Detail & Related papers  (2025-03-24T03:51:27Z)
• Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates [15.27596975662702]
  We explore algorithms achieving optimal rates of DP optimization with heavy-tailed gradients. Our results match the minimax lower bound in citekamath2022, indicating that the theoretical limit of convex optimization under DP is achievable.
  arXiv  Detail & Related papers  (2024-08-19T11:07:05Z)
• Private Zeroth-Order Nonsmooth Nonconvex Optimization [41.05664717242051]
  We introduce a new zeroth-order algorithm for private optimization on non and nonsmooth objectives. Given a dataset size $M$, our algorithm finds a privacy differential. Although the objective is not smooth, we have privacy. for free whenever $tdepsilon$.
  arXiv  Detail & Related papers  (2024-06-27T23:57:01Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  We introduce a new tool for BFG convex optimization (SCO): a Reweighted Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probability density. We develop algorithms achieving state-of-the-art complexities for SCO in parallel and private settings.
  arXiv  Detail & Related papers  (2023-01-01T18:51:29Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Faster Perturbed Stochastic Gradient Methods for Finding Local Minima [92.99933928528797]
  We propose tttPullback, a faster perturbed gradient framework for finding local minima. We show that Pullback with gradient estimators such as SARAH/SP and STORM can find $(epsilon, epsilon_H)$approximate local minima within $tilde O(epsilon-3 + H-6)$. The core idea of our framework is a step-size pullback'' scheme to control the average movement of the gradient evaluations.
  arXiv  Detail & Related papers  (2021-10-25T07:20:05Z)
• Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings [15.122617358656539]
  We present differentially private algorithms for convex and non-smooth general losses (GLLs) For the convex case, we focus on the family of non-smooth generalized losses (GLLs)
  arXiv  Detail & Related papers  (2021-07-12T17:06:08Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$ We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
  arXiv  Detail & Related papers  (2021-03-02T06:53:44Z)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  We provide a new convergence analysis of gradient Langevin dynamics (SGLD) for sampling from a class of distributions that can be non-log-concave. At the core of our approach is a novel conductance analysis of SGLD using an auxiliary time-reversible Markov Chain.
  arXiv  Detail & Related papers  (2020-10-19T15:23:18Z)
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization [133.53164856723782]
  We propose a new accelerated zeroth-order momentum (AccZOM) method for black-box mini-optimization where only function values can be obtained. Meanwhile, we propose an accelerated zeroth-order momentum descent (Acc-MDA) method for black-box minimax optimization, where only function values can be obtained. In particular, our Acc-MDA can obtain a lower gradient complexity of $tildeO(kappa_y2.5epsilon-3)$ with a batch size $O(kappa_y4)$.
  arXiv  Detail & Related papers  (2020-08-18T22:19:29Z)
• Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces [24.52697154861819]
  We show that noisy AdaGrad achieves a regret comparable to traditional AdaGrad plus a well-controlled term due to noise. We operate with general convex functions in both constrained and unconstrained minimization.
  arXiv  Detail & Related papers  (2020-08-14T20:46:38Z)

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.