`

Timezone: »

Poster
Private Non-smooth ERM and SCO in Subquadratic Steps
Janardhan Kulkarni · Yin Tat Lee · Daogao Liu

Fri Dec 10 08:30 AM -- 10:00 AM (PST) @
We study the differentially private Empirical Risk Minimization (ERM) and Stochastic Convex Optimization (SCO) problems for non-smooth convex functions. We get a (nearly) optimal bound on the excess empirical risk for ERM with $O(\frac{N^{3/2}}{d^{1/8}}+ \frac{N^2}{d})$ gradient queries, which is achieved with the help of subsampling and smoothing the function via convolution. Combining this result with the iterative localization technique of Feldman et al. \cite{fkt20}, we achieve the optimal excess population loss for the SCO problem with $O(\min\{N^{5/4}d^{1/8},\frac{ N^{3/2}}{d^{1/8}}\})$ gradient queries.Our work makes progress towards resolving a question raised by Bassily et al. \cite{bfgt20}, giving first algorithms for private SCO with subquadratic steps. In a concurrent work, Asi et al. \cite{afkt21} gave other algorithms for private ERM and SCO with subquadratic steps.
{"ft_lang_label":"__label__en","ft_lang_prob":0.6322804,"math_prob":0.9851381,"size":3395,"snap":"2022-27-2022-33","text_gpt3_token_len":946,"char_repetition_ratio":0.12651135,"word_repetition_ratio":0.3813084,"special_character_ratio":0.24830633,"punctuation_ratio":0.06741573,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.97630197,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-08-16T13:48:05Z\",\"WARC-Record-ID\":\"<urn:uuid:ec8000fb-d5c4-45c9-bc29-4bba711f9cee>\",\"Content-Length\":\"44446\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:a30dfa99-cbd3-46fd-9470-68a05b4ac53e>\",\"WARC-Concurrent-To\":\"<urn:uuid:e0c62581-aa6b-4bde-bc21-6b299184d118>\",\"WARC-IP-Address\":\"198.202.70.65\",\"WARC-Target-URI\":\"https://nips.cc/Conferences/2021/ScheduleMultitrack?event=27141\",\"WARC-Payload-Digest\":\"sha1:SXAFTL6ON4KEWDD2EG6LDQXVEZJQS6GS\",\"WARC-Block-Digest\":\"sha1:DBWC36GXYTO445ZOYOD7FLT2RAWVEBPS\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-33/CC-MAIN-2022-33_segments_1659882572304.13_warc_CC-MAIN-20220816120802-20220816150802-00283.warc.gz\"}"}