Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings

Simple item page
dc.catalogadorfcr
dc.contributor.authorRaef Bassily
dc.contributor.authorGuzman Paredes, Cristobal Andres
dc.contributor.authorMichael Menart
dc.date.accessioned2024-03-05T15:15:02Z
dc.date.available2024-03-05T15:15:02Z
dc.date.issued2021
dc.description.abstractWe study differentially private stochastic optimization in convex and non-convex settings. For the convex case, we focus on the family of non-smooth generalized linear losses (GLLs). Our algorithm for the $\ell_2$ setting achieves optimal excess population risk in near-linear time, while the best known differentially private algorithms for general convex losses run in super-linear time. Our algorithm for the $\ell_1$ setting has nearly-optimal excess population risk $\tilde{O}\big(\sqrt{\frac{\log{d}}{n\varepsilon}}\big)$, and circumvents the dimension dependent lower bound of \cite{Asi:2021} for general non-smooth convex losses. In the differentially private non-convex setting, we provide several new algorithms for approximating stationary points of the population risk. For the $\ell_1$-case with smooth losses and polyhedral constraint, we provide the first nearly dimension independent rate, $\tilde O\big(\frac{\log^{2/3}{d}}{{(n\varepsilon)^{1/3}}}\big)$ in linear time. For the constrained $\ell_2$-case with smooth losses, we obtain a linear-time algorithm with rate $\tilde O\big(\frac{1}{n^{1/3}}+\frac{d^{1/5}}{(n\varepsilon)^{2/5}}\big)$. Finally, for the $\ell_2$-case we provide the first method for {\em non-smooth weakly convex} stochastic optimization with rate $\tilde O\big(\frac{1}{n^{1/4}}+\frac{d^{1/6}}{(n\varepsilon)^{1/3}}\big)$ which matches the best existing non-private algorithm when $d= O(\sqrt{n})$. We also extend all our results above for the non-convex $\ell_2$ setting to the $\ell_p$ setting, where $1 < p \leq 2$, with only polylogarithmic (in the dimension) overhead in the rates.
dc.fechaingreso.objetodigital2024-12-09
dc.fuente.origenORCID
dc.identifier.doi10.48550/arXiv.2107.05585
dc.identifier.urihttps://research.utwente.nl/en/publications/differentially-private-stochastic-optimization-new-results-in-convex-and-nonconvex-settings(6d027229-4495-4b7d-ad23-e75da3c052f5).html
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/84092
dc.information.autorucInstituto de Ingeniería Matemática y Computacional; Guzman Paredes, Cristobal Andres; 0000-0002-1498-2055; 1041986
dc.language.isoen
dc.nota.accesoContenido completo
dc.rightsacceso abierto
dc.titleDifferentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings
dc.typecomunicación de congreso
sipa.codpersvinculados1041986
sipa.trazabilidadORCID;2024-01-22
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Differentially Private Stochastic Optimization New Results in Convex and Non-Convex Settings.pdf
Size:
524.16 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de conferencia