## 3 Adacomp Method
### Ide 1: Search Optimal Learning Rate  
For problem (1) in which gradients are Lipschitz continuous, i.e., \(f(w_{t+1})-f(w_{t})\leq\langle\
abla f(w_{t}),w_{t+1}-w_{t}\rangle+\frac{k}{2}\|w _{t+1}-w_{t}\|^{2}\), by substituting Equation (2), we have  
\[f(w_{t+1})-f(w_{t})\leq-\gamma_{t}\langle\
abla f(w_{t}),\tilde{g}_{t}\rangle+ \frac{L\gamma_{t}^{2}}{2}\|\tilde{g}_{t}\|^{2}. \tag{4}\]  
To make progress at each iteration \(t\), let the r.h.s. of Equation (4) be less than zero, and we have \(\gamma_{t}\leq 2\langle\
abla f(w_{t}),\tilde{g}_{t}\rangle/L\|\tilde{g}_{t}\|^{2}\). To greedy search the optimal learning rate, we minimize Equation (4) to obtain  
\[\gamma_{t}=\langle\
abla f(w_{t}),\tilde{g}_{t}\rangle/(L\|\tilde{g}_{t}\|^{2 }). \tag{5}\]  
This presents an explicit relation between the learning rate and inner product of expected gradient \(\
abla f(w_{t})\) and observed gradients \(\tilde{g}_{t}\). When \(\langle\
abla f(w_{t}),\tilde{g}_{t}\rangle\geq 0\), Equation (5) is meaningful (\(\gamma_{t}\geq 0\)) and using this \(\gamma_{t}\) can make the largest progress at the current iteration. Elsewhere, we set \(\gamma_{t}=0\) when \(\langle\
abla f(w_{t}),\tilde{g}_{t}\rangle\leq 0\). This means that when \(\tilde{g}_{t}\) is far away from the correct direction \(\
abla f(w_{t})\), we will drop the incorrect direction and do not update the model parameters at the current iteration. By substituting Equation (5) into Equation (4) and through simple calculation, we obtain Theorem 1, which indicates that \(\|\
abla f(w_{t})\|\to 0\) as \(t\rightarrow\infty\), i.e., the convergence of nonconvex problem (1). Theorem 1: _If the learning rate \(\gamma_{t}\) is set as Equation (5), then_  
\[\sum_{t=1}^{T}\|\
abla f(w_{t})\|^{2}\leq 2L\sigma^{2}(f(w_{1})-f^{*})/b \tag{6}\]  
_where \(f^{*}=\inf_{w\in\mathbb{R}^{n}}f(w)\)._  
Proof: By substituting Equation (5) into Equation (4), we have  
\[f(w_{t+1})-f(w_{t})\leq-\frac{\langle\
abla f(w_{t}),\tilde{g}_{t}\rangle^{2} }{2L\|\tilde{g}_{t}\|^{2}}.\]  
Taking expectation with respect to \(\xi\) on the current condition \(w_{t}\), we have  
\[\mathbb{E}[f(w_{t+1})-f(w_{t})]\overset{(a)}{\leq}-\frac{\langle\
abla f(w_{ t}),\mathbb{E}\tilde{g}_{t}\rangle^{2}}{2L\mathbb{E}\|\tilde{g}_{t}\|^{2}} \overset{(b)}{\leq}-\frac{\|\
abla f(w_{t})\|^{4}}{2L(\|\
abla f(w_{t})\|^{2 }+\sigma^{2}/b)}\overset{(c)}{\leq}-\frac{\|\
abla f(w_{t})\|^{2}}{2L\sigma^{ 2}/b},\]  
where we use [PERSON]'s inequality \(\mathbb{E}\langle\
abla f(w_{t}),\tilde{g}_{t}\rangle^{2}\geq\langle\
abla f(w _{t}),\mathbb{E}\tilde{g}_{t}\rangle^{2}\) in (a) and assumption of bounded variance \(\mathbb{E}\|\tilde{g}_{t}\|^{2}\leq\|\
abla f(w_{t})\|^{2}+\frac{\sigma^{2}}{b}\) in (b), and the fact \(\frac{\|\
abla f(w_{t})\|^{2}}{\|\
abla f(w_{t})\|^{2}+\sigma^{2}}\geq\frac{1} {\sigma^{2}}\) in \begin{table}
\begin{tabular}{l l} \hline \hline
**Variables** & **Explanations** \\ \hline \(T_{r}t\) & Number of total iterations and index of the current iteration. \\ \(F(w,\xi),\
abla F(w,\xi)\) & Empirical loss function and gradient at model parameter \(w\) and sample \(\xi\). \\ \(f(w),\
abla f(w)\) & Expected function and gradient of \(F(w,\xi)\) and \(\
abla F(w,\xi)\) with respect to \\ \(L,\sigma^{2}\) & Smooth constant of \(f(w)\) and variance of \(\
abla F(w,\xi)\) with respect to \(\xi\). \\ \(\delta_{t},\delta_{t}\) & Abbreviations for \(\
abla F(w_{t},\xi)\) and \(\frac{1}{2}\sum_{\xi\in\mathbb{S}}\
abla F(w_{t},\xi)\), respectively. \\ \(\delta_{t},b\) & Mini-batch sampled at \(t\)-th iteration with size of \(b\). \\ \(\gamma_{t},\delta\) & Learning rate at \(t\)-th iteration, parameter of Adacomp used to adjust \(\gamma_{t}\). \\ \(\Delta_{t}\) & Difference in \(f(w)\) at two consecutive iterations, i.e., \(f(w_{t-1})-f(w_{t})\). \\ \hline \hline \end{tabular}
\end{table} 
Table 1: List of variables and explanations. (c). Taking summation on both sides of the above inequality from \(t=1\) to \(T-1\) and using the fact that \(f(w_{1})-f(w_{T})\leq f(w_{1})-f*\) derive the proved result.