English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study differentially private stochastic optimization in convex andnon-convex settings. For the convex case, we focus on the family of non-smoothgeneralized linear losses (GLLs). Our algorithm for the $\ell_2$ settingachieves optimal excess population risk in near-linear time, while the bestknown differentially private algorithms for general convex losses run insuper-linear time. Our algorithm for the $\ell_1$ setting has nearly-optimalexcess population risk$\tilde{O}\big(\sqrt{\frac{\log{d}}{n\varepsilon}}\big)$, and circumvents thedimension dependent lower bound of \cite{Asi:2021} for general non-smoothconvex losses. In the differentially private non-convex setting, we provideseveral new algorithms for approximating stationary points of the populationrisk. For the $\ell_1$-case with smooth losses and polyhedral constraint, weprovide the first nearly dimension independent rate, $\tildeO\big(\frac{\log^{2/3}{d}}{{(n\varepsilon)^{1/3}}}\big)$ in linear time. Forthe constrained $\ell_2$-case with smooth losses, we obtain a linear-timealgorithm with rate $\tildeO\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 weaklyconvex} stochastic optimization with rate $\tildeO\big(\frac{1}{n^{1/4}}+\frac{d^{1/6}}{(n\varepsilon)^{1/3}}\big)$ whichmatches the best existing non-private algorithm when $d= O(\sqrt{n})$. We alsoextend 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 thedimension) overhead in the rates.

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