Oral
Lower Bounds for Smooth Nonconvex Finite-Sum Optimization
Dongruo Zhou · Quanquan Gu

Tue Jun 11th 11:30 -- 11:35 AM @ Room 104

Smooth finite-sum optimization has been widely studied in both convex and nonconvex settings. However, existing lower bounds for finite-sum optimization are mostly limited to the setting where each component function is (strongly) convex, while the lower bounds for nonconvex finite-sum optimization remain largely unsolved. In this paper, we study the lower bounds for smooth nonconvex finite-sum optimization, where the objective function is the average of $n$ nonconvex component functions. We prove tight lower bounds for the complexity of finding $\epsilon$-suboptimal point and $\epsilon$-approximate stationary point in different settings, for a wide regime of the smallest eigenvalue of the Hessian of the objective function (or each component function). Given our lower bounds, we can show that existing algorithms including {KatyushaX} \citep{allen2018katyushax}, {Natasha} \citep{allen2017natasha} and {StagewiseKatyusha} \citep{yang2018does} have achieved optimal {Incremental First-order Oracle} (IFO) complexity (i.e., number of IFO calls) up to logarithm factors for nonconvex finite-sum optimization. We also point out potential ways to further improve these complexity results, in terms of making stronger assumptions or by a different convergence analysis.
{"ft_lang_label":"__label__en","ft_lang_prob":0.65805954,"math_prob":0.9466442,"size":4652,"snap":"2019-43-2019-47","text_gpt3_token_len":1203,"char_repetition_ratio":0.15856282,"word_repetition_ratio":0.5807365,"special_character_ratio":0.22441961,"punctuation_ratio":0.06512301,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9941837,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-11-18T19:41:28Z\",\"WARC-Record-ID\":\"<urn:uuid:9c4644b3-8e96-4867-881c-719aee89db5d>\",\"Content-Length\":\"47067\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:a7c7bd43-c829-4cb9-aa6e-f7c29e892d97>\",\"WARC-Concurrent-To\":\"<urn:uuid:92b099d6-5932-457a-b79f-3ab9426d5531>\",\"WARC-IP-Address\":\"198.202.70.65\",\"WARC-Target-URI\":\"https://icml.cc/Conferences/2019/ScheduleMultitrack?event=4755\",\"WARC-Payload-Digest\":\"sha1:AUVSHZ5YFLBQLILMZTRNPG56RVMVJN63\",\"WARC-Block-Digest\":\"sha1:2UN53DKUZYFGRS52HOBISX4IEEPUFVG7\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-47/CC-MAIN-2019-47_segments_1573496669813.71_warc_CC-MAIN-20191118182116-20191118210116-00517.warc.gz\"}"}