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 the problem of approximating stationary points of Lipschitz andsmooth functions under $(\varepsilon,\delta)$-differential privacy (DP) in boththe finite-sum and stochastic settings. A point $\widehat{w}$ is called an$\alpha$-stationary point of a function $F:\mathbb{R}^d\rightarrow\mathbb{R}$if $\|\nabla F(\widehat{w})\|\leq \alpha$. We provide a new efficient algorithmthat finds an$\tilde{O}\big(\big[\frac{\sqrt{d}}{n\varepsilon}\big]^{2/3}\big)$-stationarypoint in the finite-sum setting, where $n$ is the number of samples. Thisimproves on the previous best rate of$\tilde{O}\big(\big[\frac{\sqrt{d}}{n\varepsilon}\big]^{1/2}\big)$. We alsogive a new construction that improves over the existing rates in the stochasticoptimization setting, where the goal is to find approximate stationary pointsof the population risk. Our construction finds a$\tilde{O}\big(\frac{1}{n^{1/3}} +\big[\frac{\sqrt{d}}{n\varepsilon}\big]^{1/2}\big)$-stationary point of thepopulation risk in time linear in $n$. Furthermore, under the additionalassumption of convexity, we completely characterize the sample complexity offinding stationary points of the population risk (up to polylog factors) andshow that the optimal rate on population stationarity is $\tilde\Theta\big(\frac{1}{\sqrt{n}}+\frac{\sqrt{d}}{n\varepsilon}\big)$. Finally, weshow that our methods can be used to provide dimension-independent rates of$O\big(\frac{1}{\sqrt{n}}+\min\big(\big[\frac{\sqrt{rank}}{n\varepsilon}\big]^{2/3},\frac{1}{(n\varepsilon)^{2/5}}\big)\big)$on population stationarity for Generalized Linear Models (GLM), where $rank$ isthe rank of the design matrix, which improves upon the previous best knownrate.

Faster Rates of Convergence to Stationary Points in Differentially Private Optimization