Private Zeroth-Order Nonsmooth Nonconvex Optimization

• URL: http://arxiv.org/abs/2406.19579v1
• Date: Thu, 27 Jun 2024 23:57:01 GMT
• Title: Private Zeroth-Order Nonsmooth Nonconvex Optimization
• Authors: Qinzi Zhang, Hoang Tran, Ashok Cutkosky,
• Abstract summary: 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$.
• Score: 41.05664717242051
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a new zeroth-order algorithm for private stochastic optimization on nonconvex and nonsmooth objectives. Given a dataset of size $M$, our algorithm ensures $(\alpha,\alpha\rho^2/2)$-R\'enyi differential privacy and finds a $(\delta,\epsilon)$-stationary point so long as $M=\tilde\Omega\left(\frac{d}{\delta\epsilon^3} + \frac{d^{3/2}}{\rho\delta\epsilon^2}\right)$. This matches the optimal complexity of its non-private zeroth-order analog. Notably, although the objective is not smooth, we have privacy ``for free'' whenever $\rho \ge \sqrt{d}\epsilon$.

Related papers

• Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity [22.615156512223763]
  We propose variance- optimistic sliding (SVOGS) method, which takes the advantage of the finite-sum structure in the objective. We prove $mathcal O(delta D2/varepsilon)$, communication complexity of $mathcal O(n+sqrtndelta D2/varepsilon)$, and local calls of $tildemathcal O(n+sqrtndelta+L)D2/varepsilon)$.
  arXiv  Detail & Related papers  (2024-05-25T08:34:49Z)
• Differentially Private Stochastic Linear Bandits: (Almost) for Free [17.711701190680742]
  In the central model, we achieve almost the same regret as the optimal non-private algorithms, which means we get privacy for free. In the shuffled model, we also achieve regret of $tildeO(sqrtT+frac1epsilon)$ %for small $epsilon$ as in the central case, while the best previously known algorithm suffers a regret of $tildeO(frac1epsilonT3/5)$.
  arXiv  Detail & Related papers  (2022-07-07T17:20:57Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• 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)
• Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment [7.4288915613206505]
  We study differentially private online learning problems in a environment under both bandit and full information feedback. For differentially private bandits, we propose both UCB and Thompson Sampling-based algorithms that are anytime and achieve the optimal $O left(sum_j: Delta_j>0 fracln(T)min leftDelta_j, epsilon right right)$ minimax lower bound. For the same differentially private full information setting, we also present an $epsilon$-differentially
  arXiv  Detail & Related papers  (2021-02-16T02:48:16Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  We study online learning with bandit feedback (i.e. learner has access to only zeroth-order oracle) where cost/reward functions admit a "pseudo-1d" structure. We show a lower bound of $min(sqrtdT, T3/4)$ for the regret of any algorithm, where $T$ is the number of rounds. We propose a new algorithm sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively.
  arXiv  Detail & Related papers  (2021-02-15T08:16:51Z)
• A closed form scale bound for the $(\epsilon, \delta)$-differentially private Gaussian Mechanism valid for all privacy regimes [0.0]
  We present a similar closed form bound $sigma geq Delta (epsilonsqrt2)-1 left(sqrtaz+epsilon + ssqrtazright)$ for $epsilon in (0,1)$.
  arXiv  Detail & Related papers  (2020-12-18T21:35:26Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

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.