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 differentially private Empirical Risk Minimization (ERM) andStochastic Convex Optimization (SCO) problems for non-smooth convex functions.We get a (nearly) optimal bound on the excess empirical risk and excesspopulation loss with subquadratic gradient complexity. More precisely, ourdifferentially private algorithm requires $O(\frac{N^{3/2}}{d^{1/8}}+\frac{N^2}{d})$ gradient queries for optimal excess empirical risk, which isachieved with the help of subsampling and smoothing the function viaconvolution. This is the first subquadratic algorithm for the non-smooth casewhen $d$ is super constant. As a direct application, using the iterativelocalization approach of Feldman et al. \cite{fkt20}, we achieve the optimalexcess population loss for stochastic convex optimization problem, with$O(\min\{N^{5/4}d^{1/8},\frac{ N^{3/2}}{d^{1/8}}\})$ gradient queries. Our workmakes progress towards resolving a question raised by Bassily et al.\cite{bfgt20}, giving first algorithms for private ERM and SCO withsubquadratic steps.  We note that independently Asi et al. \cite{afkt21} gave other algorithms forprivate ERM and SCO with subquadratic steps.

Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps