high_prob_ls_nonconvex_final

Next, we will show that e ( x, S) is sub-exponential. Proposition 3. Let g = g ( x, U), and fix In Section 2.3 of [ BCCS21 ], it is shown that kr F ( x) r ( x) k p nL + p n We use these facts to show that Gaussian smoothed gradients gives a valid first order oracle. First, by the triangle inequality, we have k g ( x, U) r ( x) k k g ( x, U) r F ( x) k + kr F ( x) r ( x) k . To prove Lemma 2, we will first prove two additional lemmas. The first lemma shows that the number of large and successful iterations is bounded below by the number of large and unsuccessful ones up to a constant.