In this section, we introduce the underlying ideas behind the convergence rate improvement for achieving first-order stationary points (FSPs) in non-convex optimization.
We introduce the concept of Reducible Gradient Perturbation Sequence (RGPS) which is defined as
\begin{equation}
    \label{eq:consturcted_auxiliary_sequence}
    \begin{split}
        \vs_t = \frac{1}{m}\sum\limits_{i=1}^m \grad f_{\sB_i^t}(\vx_i^t),\quad t\in \sI_T.
    \end{split}
\end{equation}
In random shuffling setting, RGPS can establish strong connections with both the update paradigm of adaptive gradient methods and full gradients, which provides the sufficient descent a $\Theta(\|\grad f(\vx_1^{\tau})\|)$ lower bound rather than the common result $\Theta(\|\grad f(\vx_1^{\tau})\|^2)$.
Besides, the upper bound $U(T)$ of sufficient descents in our analysis is similar to previous work, which means the sufficient conditions for convergence only request $U(T) \le \epsilon$ rather than $U(T) \le \epsilon^2$.
Hence, a better provable convergence rate can be obtained by introducing RGPS.
Specifically, we take AdaGrad\_F~\cite{duchi2011adaptive} and \radagrad as examples to explain how RGPS works in the convergence analysis, and organize the details guided by answering the following two questions
\begin{enumerate}
    \item How \radagrad obtains a tighter sufficient descent lower bound with RGPS?
    \item How the tighter sufficient descent lower bound benefits the convergence in \radagrad?
\end{enumerate}

\subsection{RGPS is a Coupling of Gradients and Sufficient Descents}
\label{sec:RGPS_sufficient_descent}
In this section, we answer the first question proposed in section~\ref{sec:rgps_ci}. 
We note that RGPS can establish strong connection with both the full gradient, i.e., $\grad f(\vx_1^t)$, and the sufficient descent about $\vs_t$.
Scaling the sufficient descent about $\vs_t$ through RPGS can utilize the properties of $\mG_{m,t}$ to the full potential, and obtain a tighter lower bound compared with investigating the sufficient descent about $\grad f(\vx_1^t)$ directly.

In particular, we provide two lemmas to explain that RGPS is a coupling of the full gradient sequence and the sufficient descent about $\vs_t$. 
\begin{lemma}
    \label{lem:auxiliary_sequence_closeness}
    Suppose Assumption~\ref{ass:comm_ass_pre} and Assumption~\ref{ass:H_full_column_rank_ass_pre} hold, we have
    \begin{equation}
        \label{ineq:auxiliary_sequence_closeness}
        \begin{split}
            \left\|\grad f(\vx_1^t) - \vs_t\right\| \le O(\eta /\sqrt{t}),
        \end{split}
    \end{equation}
    if the step size is fixed at each iteration.
\end{lemma}
This lemma illustrates that $\vs_t$ is close to $\grad f(\vx_1^t)$ when the fixed step size $\eta$ is small enough.
With triangle inequality, it also denotes that the full gradient norm $\|\grad f(\vx_1^t)\|$ can be bounded by $\|\vs_t\|$.
\begin{lemma}
    \label{lem:G_denominator_effect}
    Suppose Assumption~\ref{ass:comm_ass_pre} and Assumption~\ref{ass:H_full_column_rank_ass_pre} hold, in \radagrad, if $\delta_{m,t}\le t mG^2$, $0\le \delta_{m,t}-\delta_{m,t-1}\le m\lambda_{\mathrm{max}}\left(\mH_{m,t}\mH^\top_{m,t}\right)$ and $\Gamma \ge m$, we have
    \begin{equation}
        \label{eq:G_denominator_effect}
        \begin{split}
            \sqrt{\frac{\delta_{m,t}-\delta_{m,t-1}}{t}}\left\|\vs_t\right\| \le O\left(\vs_t^\top\mG^{-\frac{1}{2}}_{m,t}\vs_t\right).
        \end{split}
    \end{equation}
\end{lemma}
This lemma reveals the connection between $\|\vs_t\|$ and the sufficient descent about $\vs_\tau$.
According to the special structure of $\mG_{m,t}$, we are able to provide $\left\|\vs_t\right\|$ as the lower bound of the quadratic form $\vs_t^\top\mG_{m,t}^{-\frac{1}{2}}\vs_t$.
Combining Lemma~\ref{lem:auxiliary_sequence_closeness} with Lemma~\ref{lem:G_denominator_effect}, $\vs_t^\top\mG_{m,t}^{-\frac{1}{2}}\vs_t$ can be even lower bounded:
\begin{equation}
    \label{ineq:s_sufficient_descent_lb}
    \begin{aligned}[b]
        \sqrt{\frac{\delta_{m,t}- \delta_{m,t-1}}{t}}\left\|\grad f(\vx_1^t)\right\|= O\left(\vs_t^\top\mG_{m,t}^{-\frac{1}{2}}\vs_t\right) + O\left(\frac{\eta}{t}\right)
    \end{aligned}
\end{equation}
by using RPGS as a bridge.

On the other hand, if we investigate the sufficient descent about $\grad f(\vx_1^t)$ directly, we obtain a lower bound of the sufficient descent as
\begin{equation}
    \label{ineq:grad_sufficient_descent_lb}
    \begin{aligned}[b]
         \frac{1}{\sqrt{t}}\left\|\grad f(\vx_1^t)\right\|^2 \le O(\grad f^T(\vx_1^t)\mG_{m,t}^{-\frac{1}{2}}\grad f(\vx_1^t)),
    \end{aligned}
\end{equation}
due to the definition of $\mG_{m,t}$ and Gradient Bounded Assumption in Assumption~\ref{ass:comm_ass_pre}.
When the parameter $\vx_1^t$ is close to an FSP, $\|\grad f(\vx_1^t)\|$ is close to $0$ due to L-Smooth Assumption in Assumption~\ref{ass:comm_ass_pre}.
With a lower order of $\|\grad f(\vx_1^t)\|$, LHS of eq.~\ref{ineq:s_sufficient_descent_lb} is a undoubtedly better lower bound compared with that in eq.~\ref{ineq:grad_sufficient_descent_lb}, when $\delta_{m,t}-\delta_{m-1,t}$ has a constant lower bound, and the upper bound of RHS in eq.~\ref{ineq:s_sufficient_descent_lb} is almost the same as that in eq.~\ref{ineq:grad_sufficient_descent_lb}.

\subsection{Tight Lower Bounds Weaken Sufficient Conditions for the Convergence}
In this section, we answer the second question proposed in section~\ref{sec:rgps_ci}. 
First, we introduce the relation between the sufficient descent lower bound and the convergence rate.
Then, combining with section~\ref{sec:RGPS_sufficient_descent}, we provide a explanation about the convergence rate improvement in \radagrad.

\textbf{The relation between the sufficient descent lower bound and the convergence rate.} 
If we analyze the convergence through investigating the lower bound of the sufficient descent about $\grad f(\vx_1^t)$ in \radagrad, we have following inequalities:
\begin{equation}
    \label{ineq:convergence_bottleneck_3}
    \begin{split}
        m\eta\sum_{t=1}^T\frac{C}{\sqrt{t}}\left\|\grad f(\vx_1^t)\right\|^2 \mathop{\le}^{\circled{1}} m\eta\sum\limits_{t=1}^T\grad f^\top(\vx_1^t)\mG^{-\frac{1}{2}}_{m,t}\grad f(\vx_1^t) \mathop{\le}^{\circled{2}} f(\vx_1^1) - f^* + \Theta(T\eta^a),
    \end{split}
\end{equation}
where $\circled{1}$ follows from eq.~\ref{ineq:grad_sufficient_descent_lb} and $\circled{2}$ can be obtained through providing the telescoping sum of eq.~\ref{ineq:convergence_bottleneck_1} and scaling the terms with positive upper bounds to $\Theta(\eta^a)$ ($a\ge 0$).
If a random variable $\tau$ follows $\mathbb{P}[\tau = i] = \frac{i^{-0.5}}{\sum_{i=1}^T i^{-0.5}}$, we obtain 
\begin{small}
\begin{equation}
    \label{ineq:convergence_bottleneck_4}
    \begin{split}
        \mathbb{E}_{\tau} \left[\left\|\grad f(\vx_1^\tau)\right\|^2\right] \le \frac{f(\vx_1^1)-f^*}{\eta m \sqrt{T}}+\frac{\Theta(\sqrt{T}\eta^{a-1})}{m}
        \xRightarrow{\frac{1}{\eta\sqrt{T}}=\sqrt{T}\eta^{a-1}}
        \mathbb{E}_{\tau} \left[\left\|\grad f(\vx_1^\tau)\right\|^2\right] \le \Theta\left(T^{\frac{1}{a}-\frac{1}{2}}\right).
    \end{split}
\end{equation}
\end{small}
As a result, the sufficient condition for achieving \emph{FSP}, $\mathbb{E}_{\tau} [\|\grad f(\vx_1^\tau)\|^2] \le \epsilon^2$, is $RHS \le \epsilon^2$ for eq.~\ref{ineq:convergence_bottleneck_4}. 
The convergence rate of \radagrad is at least $O(T^{-1/4})$ if we lower bound the sufficient descent about $\grad f(\vx_1^\tau)$ like previous work.
As a result, we can conclude that the order of $\|\grad f(\vx_1^\tau)\|$ in the lower bound of sufficient descent directly decide the order of $\epsilon$ in RHS of the sufficient condition for convergence.
The order of $\|\grad f(\vx_1^\tau)\|$ higher, the convergence rate worse.

\textbf{The convergence rate improvement in \radagrad.} eq.~\ref{ineq:s_sufficient_descent_lb} in section~\ref{sec:RGPS_sufficient_descent} shows that the order of  $\|\grad f(\vx_1^t)\|$ in the lower bound of the sufficient descent about $\vs_t$ is significantly smaller than that in eq.~\ref{ineq:grad_sufficient_descent_lb}.
Hence, similar to eq.~\ref{ineq:convergence_bottleneck_3}, we can approximately provide
\begin{small}
\begin{equation}
    \label{ineq:convergence_bottleneck_5}
    \begin{aligned}[b]
         &\sum_{t=1}^T\frac{\eta}{\sqrt{t}}\left\|\grad f(\vx_1^t)\right\| \mathop{\le}^{\circled{1}} \eta \sum_{t=1}^T\vs_t^\top\mG_{m,t}^{-\frac{1}{2}}\vs_t + \Theta\left(\eta^2 \ln T\right) \mathop{\le}^{\circled{2}} f(\vx_1^1)-f^*+ \underbrace{\Theta\left(\eta^\alpha \sum_{t=1}^T t^{-\beta}\right)}_{T_1}  + \underbrace{\Theta\left(\eta^2 \ln T\right)}_{T_2},
    \end{aligned}
\end{equation}
\end{small}
where $\circled{1}$ follows from eq.~\ref{ineq:s_sufficient_descent_lb}, $\circled{2}$ can be obtained by techniques similar to the inequality $\circled{2}$ in eq.~\ref{ineq:convergence_bottleneck_3}.
The constants satisfy $\alpha\ge 0$, $\beta \ge 1$.
Notice that $T_1$ in eq.~\ref{ineq:convergence_bottleneck_5} is corresponding to $\Theta\left(T\eta^\alpha\right)$ in eq.~\ref{ineq:convergence_bottleneck_3}, and $T_2$ in eq.~\ref{ineq:convergence_bottleneck_5} is from the gap between $\vs_t$ and $\grad f(\vx_1^t)$. Similar to eq.~\ref{ineq:convergence_bottleneck_4}, we obtain
\begin{equation}
    \label{ineq:convergence_bottleneck_6}
    \begin{split}
        \mathbb{E}_{\tau}\left[\left\|\grad f(\vx_1^\tau)\right\|\right] \le \frac{f(\vx_1^1)-f^*}{\eta\sqrt{T}}+ \frac{\Theta(\eta^\alpha)}{\sqrt{T}} + \Theta\left(\frac{\eta\ln T}{\sqrt{T}}\right).
    \end{split}
\end{equation}
As a result, the sufficient condition for the parameters achieving \emph{FSP}, $\mathbb{E}_{\tau}\left[\left\|\grad f(\vx_1^\tau)\right\|\right]\le \epsilon$, is $RHS \le \epsilon$ for eq.~\ref{ineq:convergence_bottleneck_6}. 
That is to say, the convergence rate of \radagrad is near $\tilde{O}(T^{-1/2})$ which is better than previous best-known results.
{"config": "arxiv", "file": "2006.07037/040core.tex"}