
\section{Method}

We propose an \textbf{a}daptive \textbf{g}radi\textbf{en}t correc\textbf{t}ion (AGENT) method and integrate it with recent sparse training pipelines to achieve accelerations and improve training stability. 
Specifically, to accomplish the goal, our AGENT filters out less relevant information and obtains a well-controlled and time-varying amount of knowledge from the old gradients. Our method overcomes the limitations of previous acceleration methods such as SVRG~\citep{allen2016variance, dubey2016variance, elibol2020variance}, and successfully accelerates and stabilizes sparse training.
We will illustrate each part of our method in the following sections. Our AGENT method is outlined in Algorithm~\ref{alg:avr-sgld}.













\subsection{Adaptive Control over Old Gradients}\label{subsec: weight}


In AGENT, we designed an adaptive addition of old gradients to new gradients to filter less relevant information and achieve a balance between new and old gradients.
Specifically, we add an adaptive weight $c_t \in [0, 1]$ to the old gradient as shown in Eq.~(\ref{equ: est g}), where we use ${\bm{g}}_{\text{new}}=\frac{1}{n}\sum_{i\in \textbf{B}_t}{\bm{g}}_i({\bm{\theta}}_t)$ and ${\bm{g}}_{\text{old}}=\frac{1}{n}\sum_{i\in \textbf{B}_t}{\bm{g}}_i(\widetilde{{\bm{\theta}}})$ to denote the gradient on current parameters $\bm{\theta}_t$ and previous parameters $\widetilde{\bm{\theta}}$ for a random subset $\textbf{B}_t$, respectively.
When the old and new gradients are highly correlated,  we need a large $c$ to get more useful information from the old gradient. Conversely, when the relevance is low, we need a smaller $c$ so that we do not let irrelevant information corrupt the new gradient.
\begin{equation}
\begin{split}
\label{equ: est g}
    \hat{{\bm{g}}}({\bm{\theta}}_t)
    &= \frac{1}{n}\sum_{i\in \textbf{B}_t}\bigg{(}{\bm{g}}_i({\bm{\theta}}_t)- c_t\cdot {\bm{g}}_i(\widetilde{{\bm{\theta}}})\bigg{)} + c_t\cdot \widetilde{{\bm{g}}}= {\bm{g}}_{\text{new}} - c_t \cdot {\bm{g}}_{\text{old}} + c_t \cdot \widetilde{{\bm{g}}}. 
   
\end{split}
\end{equation}

\begin{wrapfigure}{R}[0pt]{9cm
\vspace{-0.9cm}
\begin{minipage}{9cm}
\begin{algorithm}[H]
\small
   \caption{Adaptive Gradient Correction}
   \label{alg:avr-sgld}
\begin{algorithmic}
   \STATE {\textbf{Input:}} $\widetilde{\bm{\theta}}=\bm{\theta}_0$, epoch length $m$, step size $\eta_t$, $c_0=0$, scaling parameter $\gamma$, smoothing factor $\alpha$
   \FOR{$t=0$ \textbf{to} $T-1$}
   \IF{$t\mod m = 0$}
   \STATE $\widetilde{\bm{\theta}}=\bm{\theta}_t$
   \STATE $\widetilde{{\bm{g}}} = (\sum_{i=1}^N \nabla G(\textbf{x}_i\vert\widetilde{\bm{\theta}}))/N$
   \IF{$t > 0$}
   \STATE Calculate $\hat{c_t^*}$ via Eq. (\ref{equ: c loss})
   \STATE $c_t = (1-\alpha)c_{t-1} + \alpha \hat{c_t^*}$
   \ENDIF
   \ELSE
   \STATE $c_t = c_{t-1}$
   \ENDIF
   \STATE Sample a mini-batch data $\textbf{B}_t$ with size $n$
  
   \STATE $\bm{\theta}_{t+1} = \bm{\theta}_t - \eta_t \cdot \bigg{(}\frac{1}{n}\sum_{i\in \textbf{B}_t} \big{(}{\bm{g}}_i(\bm{\theta}_t)- \gamma c_t \cdot {\bm{g}}_i(\widetilde{\bm{\theta}})\big{)} + \gamma c_t \cdot\widetilde{{\bm{g}}} \bigg{)}$
   \ENDFOR
  
\end{algorithmic}
\end{algorithm}
\end{minipage}
\vspace{-0.9cm}
\end{wrapfigure}


A suitable $c_t$ should effectively reduce the variance of $\hat{{\bm{g}}}({\bm{\theta}}_t)$. To understand how $c_t$ influence the variance of updated gradient, we decompose the variance of $\hat{{\bm{g}}}({\bm{\theta}}_t)$ in Eq.~(\ref{equ: quad-var}) with some abuse of notation, where the variance of updated gradient is a quadratic function of $c_t$. For simplicity, considering the case where $\hat{{\bm{g}}}({\bm{\theta}}_t)$ is a scalar, the optimal $c_t^*$ will be in the form of Eq.~(\ref{equ: quad-var}). As we can see, $c_t^*$ is not closed to 1 when the new gradient is not highly correlated with the old gradient.  
Since low correlation between ${\bm{g}}_{\text{new}}$ and ${\bm{g}}_{\text{old}}$ is more common in sparse training, directly setting $c_t=1$ in previous methods is not appropriate and we need to estimate adaptive weights $c_t^*$. In support of this claim, we include a discussion and empirical analysis in the Appendix \ref{sub-sec:grad-speed} to demonstrate that as sparsity increases, the gradient changes faster, leading to lower correlations between ${\bm{g}}_{\text{new}}$ and ${\bm{g}}_{\text{old}}$.
\begin{equation}
\begin{split}
\label{equ: quad-var}
    \mathrm{Var}(\hat{{\bm{g}}}({\bm{\theta}}_t)) = \mathrm{Var}({\bm{g}}_{\text{new}}) + c_t^2\cdot \mathrm{Var}({\bm{g}}_{\text{old}})-2c_t\cdot \mathrm{Cov}({\bm{g}}_{\text{new}}, {\bm{g}}_{\text{old}}), \quad c_t^* = \frac{\mathrm{Cov}({\bm{g}}_{\text{new}}, {\bm{g}}_{\text{old}})}{\mathrm{Var}({\bm{g}}_{\text{old}})}.
\end{split}
\end{equation}
We find it impractical to compute the exact $c_t^*$ and thus propose an approximation algorithm for it to obtain a balance between the new and old gradient. There are two challenges to calculate the exact $c_t^*$.
On the one hand, to approach the exact value, we need to calculate the gradients on every batch data, which is too expensive to do it in each iteration. On the other hand, the gradients are often high-dimensional and the exact optimal $c_t^*$ will be different for different gradients. 
Thus, inspired by~\citet{deng2020accelerating}, we design an approximation algorithm that makes good use of the loss information and leads to only a small increase in computational effort. More specifically, we estimate $c_t^*$ according to the changes of loss as shown in Eq. (\ref{equ: c loss}) and update $\widehat{c}_t^*$ adaptively before each epoch using momentum.
Loss is a scalar, which makes it possible to estimate the shared correlation for all current and previous gradients. In addition, the loss is intuitively related to gradients and the correlation between losses can give us some insights into that of the gradients (some empirical analyses are included in the Appendix \ref{sub-sec:corr-approx}). 
\begin{equation}
\label{equ: c loss}
\widehat{c}_t^* = \frac{\mathrm{Cov}(G(\textbf{B}|{\bm{\theta}}_t),G(\textbf{B}|\widetilde{{\bm{\theta}}}))}{\mathrm{Var}(G(\textbf{B}|\widetilde{{\bm{\theta}}}))},
\end{equation}
where $\textbf{B}$ denotes a subset of samples used to estimate the gradients. 

We empirically justify the loss-based approximation in Eq. (\ref{equ: c loss}). Experimental details are included in Section \ref{sub-sec:corr-approx}). We compare the approximation $\widehat{c}_t^*$ and the correlation between the gradient of current weights and the gradient of previous epoch weights. We find that $\widehat{c}_t^*$ and the correlation have similar up-and-down patterns, indicating that our approximation captures the dynamic patterns of the correlation. For differences in magnitude, they can be matched by the scaling strategy we will describe in the next Section \ref{subsec: scaling}.


\subsection{Additional Scaling Parameter is Important}
\label{subsec: scaling}



To guarantee successful acceleration in sparse and adversarial training, we further propose a scaling strategy that multiplies the estimated $c_t^*$ by a small scaling parameter $\gamma$. There are two main benefits of using a scaling parameter. First, the scaling parameter $\gamma$ can reduce the bias of the gradient estimates in adversarial training~\citep{li2020implicit}. In standard training,
the batch gradient estimator is an unbiased estimator of the full gradient.
However, in adversarial training, we perturb the mini-batch of samples $\textbf{B}_t$ into $\Bar{\textbf{B}}_t$. The old gradients ${\bm{g}}_{\text{old}}$ are calculated on batch data $\Bar{\textbf{B}}_t$, but the stored old gradients $\widetilde{{\bm{g}}}$ are obtained from the original data including $\textbf{B}_t$, which makes $\mathbb{E} [ {\bm{g}}_{\text{old}}-\widetilde{{\bm{g}}}]$ unequal to zero. 
Consequently, as shown in Eq.~(\ref{equ: bias}), the corrected estimator for full gradients will no longer be unbiased. It may have a small variance but a large bias, resulting in poor performance.
Therefore, we propose a scaling parameter $\gamma$ between 0 and 1 to reduce the bias from $c_t({\bm{g}}_{\text{old}}-\widetilde{{\bm{g}}})$ to $\gamma c_t({\bm{g}}_{\text{old}}-\widetilde{{\bm{g}}})$
\begin{equation}
\begin{split}
\label{equ: bias}
    \mathbb{E}[\hat{{\bm{g}}}({\bm{\theta}}_t)]
    &= \mathbb{E} [ {\bm{g}}_{\text{new}} - c_t ( {\bm{g}}_{\text{old}} -\widetilde{{\bm{g}}} ) ] \neq  \mathbb{E} [{\bm{g}}_{\text{old}}] = \frac{1}{N}\sum_{i=1}^N {\bm{g}}_i({\bm{\theta}}_t).
\end{split}
\end{equation}



Second, the scaling parameter $\gamma$ guarantees that the variance can still be reduced in the face of worst-case estimates of $c_t^*$ to accelerate the training. The key idea is illustrated in Figure \ref{fig: quad}, where x and y axis correspond to the weight $c_t$ and the gradient variance, respectively. The blue curve is a quadratic function that represents the relationship between $c_t$ and the variance.
Suppose the true optimal is $c^*$, and we make an approximation to it. In the worst case, this approximation may be as bad as $\hat{c}_1$, making the variance even larger than $a_3$ (variance in SGD) and slowing down the training. Then, if we replace $\hat{c}_1$ with $\gamma\hat{c}_1$, we can reduce the variance and accelerate the training.



\subsection{Connection to Momentum-based Method}

To some extent, our AGENT is designed with a similar idea to the momentum-based method~\citep{qian1999momentum, ruder2016overview}, where old gradients are used to improve the current batch gradient.
However, the momentum-based method
still suffers from optimization difficulties due to sparsity constraints. 
The reason is that it does not take into account sparse and adversarial training characteristics such as the reduced correlation between current and previous gradients and potential bias of gradient estimator, and fails to provide an adaptive balance between old and new information. When the correlation is low, the momentum-based method can still incorporate too much of the old information and increase the gradient variance or bias.
In contrast, our AGENT is designed for sparse and adversarial training and can establish finer adaptive control over how much information we should take from the old to help the new. 



\subsection{Connection to Adaptive Gradient Method}

\begin{wrapfigure}{r}[0pt]{8 cm}
\setlength{\abovecaptionskip}{0.0 cm}
\vspace{-1.2 cm}
\begin{center}
\centerline{\includegraphics[width=5.6cm,height=4cm]{./figs/scale.pdf}
\caption{Illustration of how the scaling parameter $\gamma=0.1$ ensures the acceleration in the face of worst-case estimate of $c_t^*$. The blue curve is a quadratic function, representing the relationship between $c_t$ and the variance. $c^*$ is the optimal value. $\hat{c}_1$ is a poor estimate making the variance larger than $a_3$ (variance in SGD). $\gamma\hat{c}_1$ can reduce the variance.}
\label{fig: quad}
\end{center}
\vspace{-0.4 cm}
\end{wrapfigure}

Our AGENT can be viewed as a new type of adaptive gradient method that adaptively adjusts the amount of gradient information used to update parameters, such as Adam~\citep{kingma2014adam}. However, previous adaptive gradient methods are not designed for sparse training. Although they also provide adaptive gradients, their adaptivity is different and does not take the reduced correlation into account. On the contrary, our AGENT is designed for sparse training and is tailored to the characteristics of sparse training. When old information is used to correct the gradients, the main problem is the reduced correlation between the old and new gradients. Therefore, our AGENT approximates the correlation and adds an adaptive weight to the old gradient to establish a balance between the old and new gradients.





\section{Introduction}


With the development of deep neural networks (DNNs), there is a trend towards larger and more intensive computational models to enhance task performance. Despite of the good performance, such large models are not applicable when memory or computational resources are limited~\citep{bellec2017deep, evci2020rigging, liu2022comprehensive}.
In addition, these large models consume a considerable amount of energy and produce a large amount of carbon footprint~\citep{thompson2021deep, patterson2021carbon, matus2022certification}. As a result, it attracts more efforts in research to find resource-efficient ways (e.g., less memory \& less compute) to train DNNs while maintaining results comparable to the state of the art~\citep{yu2021toward, rock2021resource, leite2021optimal}.




Sparse training~\citep{mocanu2018scalable, evci2020rigging, liu2022comprehensive}
is one of the most popular classes of methods to improve efficiency in terms of space (e.g. memory storage) and is receiving increasing attention. 
During sparse training, a certain percentage of connections are removed to save memory~\citep{bellec2017deep, evci2020rigging}. 
Sparse patterns, which describe where connections are retained or removed, are iteratively updated with various criteria~\citep{dettmers2019sparse, evci2020rigging, liu2021we, ozdenizci2021training}.
The goal is to find a resource-efficient sparse neural network (i.e., removing some connections) with comparable or even higher performance compared to the original dense model (i.e., keeping all connections).



However, sparse training can bring some side effects to the training process, especially in the case of high sparsity (e.g., 99\% weights are zero). First, sparsity can increase the variance of stochastic gradients, leading the model to move in a sub-optimal direction and hence slow convergence~\citep{hoefler2021sparsity, graesser2022state}. As shown in Figure \ref{fig: intro} (a), we empirically see that the gradient variance grows with increasing sparsity~(more details in Section~\ref{subsec: intro}). Second, it can result in training instability (i.e., a noisy trajectory of test accuracy w.r.t. iterations)~\citep{sehwag2020hydra, bartoldson2020generalization}, which 
requires additional time to compensate for the accuracy drop, resulting in slow convergence~\citep{xiao2019autoprune}. 
Additionally, the need to consider the robustness of the model during sparse training is highlighted in order to apply sparse training to a wide range of real-world scenarios where there are often challenges with dataset shifts~\citep{ye2019adversarial, hoefler2021sparsity, kundu2021dnr, ozdenizci2021training}.
To address these issues, we raise the following questions:

\textbf{\textit{Question 1.}} \textit{How to simultaneously improve convergence speed and training stability of sparse training?}

Prior gradient correction methods, such as variance reduction~\citep{zou2018subsampled,chen2019convergence, gorbunov2020unified}, are used to accelerate and stabilize dense training, while we find that it fails in sparse training. They usually assume that current and previous gradients are highly correlated, and therefore they add a large constant amount of previous gradients to correct the gradient~\citep{dubey2016variance, chatterji2018theory, chen2019convergence}. However, this assumption does not hold in sparse training. Figure \ref{fig: intro} (b) shows the gradient correlation at different sparsities, implying that the gradient correlation decreases with increasing sparsity (more details in Section~\ref{subsec: intro}), which breaks the balance between current and previous gradients.
Therefore, we propose to adaptively change the weights of previous and current gradients based on their correlation to add an appropriate amount of previous gradients.

\textbf{\textit{Question 2.}} \textit{How to design an accelerated and stabilized sparse training method that is effective in real-world scenarios with dataset shifts?}

Moreover, real-world applications are under-studied in sparse training.
Prior methods use adversarial training to improve model robustness and address the challenge of data shifts, which usually introduces additional bias beyond the variance in the gradient estimation~\citep{li2020implicit}, increasing the difficulty of gradient correction (more details in Section~\ref{subsec: scaling}). Thus, to more accurately approximate the full gradient, especially during the adversarial setup,
we design a scaling strategy to control the weights of the two gradients, determining the amount of previous gradient information to be added to the current gradient, which helps the balance and further accelerates the convergence.






 


\begin{figure}[!t
\vspace{0cm}
\begin{center}
\subfigure[Gradient Variance]{\includegraphics[width=0.47\textwidth,height=0.30\textwidth]{./figs/gra_var.pdf}}
\subfigure[Gradient Correlation]{\includegraphics[width=0.47\textwidth,height=0.30\textwidth]{./figs/gra_corr.pdf}}
\caption{Gradient variance (a) and gradient correlation (b) of models obtained by RigL and SET at different sparsities including 0\%~(dense), 50\%, 80\%, 90\%, 95\%. Gradient variance grows with increasing sparsity. Gradient correlation drops with increasing sparsity. The sparse models have larger gradient variance and smaller gradient correlation compared to dense models.}
\label{fig: intro}
\end{center}
\vspace{0cm}
\end{figure}

In this work, we propose an \textbf{a}daptive \textbf{g}radi\textbf{en}t correc\textbf{t}ion (AGENT) method to accelerate and stabilize sparse training for both standard and adversarial setups.
Theoretically, we prove that our method can accelerate the convergence rate of sparse training.
Empirically, we perform extensive experiments on multiple benchmark datasets, model architectures, and sparsities. In both standard and adversarial setups, our method improves the accuracy by up to \textbf{5.0\%} given the same number of epochs and reduces the number of epochs up to \textbf{52.1\%} to achieve the same performance compared to the leading sparse training methods.
In contrast to previous efforts of sparse training acceleration which mainly focus on structured sparse patterns, our method is compatible with both unstructured ans structured sparse training pipelines~\citep{hubara2021accelerated, chen2021pixelated}.








   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   











\label{sec:intro}




\section{Additional Experimental Results}

We summarize additional experimental results for the BSR-Net-based~\cite{ozdenizci2021training}, RigL-based~\cite{evci2020rigging}, and ITOP-based~\cite{liu2021we} models.

\subsection{Accuracy Comparisons in Different Epochs}

Aligned with the main manuscript, we compare the accuracy for a given number of epochs to compare both the speed of convergence and training stability. We first show BSR-Net-based results in this section. Since our approach has faster convergence and does not require a long warm-up period, the dividing points for the decay scheduler are set to the 50th and 100th epochs. In the manuscript, we also use this schedule for BSR-Net for an accurate comparison. In the Appendix, we include the results using its original schedule. BSR-Net and BSR-Net (ori) represent the results learned using our learning rate schedule and original schedule in \cite{ozdenizci2021training}, respectively.
As shown in Figures \ref{subfig: new1}, \ref{subfig: new2}, \ref{subfig: new3}, \ref{subfig: new4}, \ref{subfig: new5}, \ref{subfig: new6}, \ref{fig: c100-stable}, the blue curves (A-BSR-Net) are always higher than the yellow curves and also much smoother than yellow curves (BSR-Net and BSR-Net (ori)), indicating faster and more stable training when using our proposed A-BSR-Net.


\begin{figure}[ht]
\vspace{-0.2cm}
\begin{center}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_vgg16_na_10_ep.png}}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_vgg16_na_10_ori_ep.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_vgg16_na_1_ep.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_vgg16_na_1_ori_ep.png}}
\caption{Comparisons (accuracy given the number of epochs) with BSR-Net \cite{ozdenizci2021training}. We evaluate sparse networks (99\% or 90\%) learned with natural training on CIFAR-10 using VGG-16.}
\label{subfig: new1}
\end{center}
\vskip -0.2in
\end{figure}


\begin{figure}[ht]
\vspace{-0.2cm}
\begin{center}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_vgg16_at_10_ep.png}}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_vgg16_at_10_ori_ep.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_vgg16_at_1_ep.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_vgg16_at_1_ori_ep.png}}
\caption{Comparisons (accuracy given the number of epochs) with BSR-Net \cite{ozdenizci2021training}. We evaluate sparse networks (99\% or 90\%) learned with adversarial training (objective: AT) on CIFAR-10 using VGG-16.}
\label{subfig: new2}
\end{center}
\vskip -0.2in
\end{figure}


\begin{figure}[!t]
\vspace{-0.2cm}
\begin{center}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_wrn28_4_na_10_ep.png}}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_wrn28_4_na_10_ori_ep.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_wrn28_4_na_1_ep.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_wrn28_4_na_1_ori_ep.png}}
\caption{Comparisons (accuracy given the number of epochs) with BSR-Net \cite{ozdenizci2021training}. We evaluate sparse networks (99\% or 90\%) learned with natural training on CIFAR-10 using Wide-ResNet-28-4.}
\label{subfig: new3}
\end{center}
\vskip -0.2in
\end{figure}


\begin{figure}[!t]
\vspace{-0.2cm}
\begin{center}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_wrn28_4_at_10_ep.png}}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_wrn28_4_at_10_ori_ep.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_wrn28_4_at_1_ep.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_wrn28_4_at_1_ori_ep.png}}
\caption{Comparisons (accuracy given the number of epochs) with BSR-Net \cite{ozdenizci2021training}. We evaluate sparse networks (99\% or 90\%) learned with adversarial training (objective: AT) on CIFAR-10 using Wide-ResNet-28-4.}
\label{subfig: new4}
\end{center}
\vskip -0.2in
\end{figure}


\begin{figure}[!t]
\vspace{-0.2cm}
\begin{center}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/svhn_vgg16_na_10_ep.png}}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/svhn_vgg16_na_10_ori_ep.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/svhn_vgg16_na_1_ep.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/svhn_vgg16_na_1_ori_ep.png}}
\caption{Comparisons (accuracy given the number of epochs) with BSR-Net \cite{ozdenizci2021training}. We evaluate sparse networks (99\% or 90\%) learned with natural training on SVHN using VGG-16.}
\label{subfig: new5}
\end{center}
\vskip -0.2in
\end{figure}


\begin{figure}[!t]
\vspace{-0.2cm}
\begin{center}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/svhn_vgg16_trades_10_ep.png}}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/svhn_vgg16_trades_10_ori_ep.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/svhn_vgg16_trades_1_ep.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/svhn_vgg16_trades_1_ori_ep.png}}
\caption{Comparisons (accuracy given the number of epochs) with BSR-Net \cite{ozdenizci2021training}. We evaluate sparse networks (99\% or 90\%) learned with adversarial training (objective: TRADES) on SVHN using VGG-16.}
\label{subfig: new6}
\end{center}
\vskip -0.2in
\end{figure}

\begin{figure*}[!t]
\vspace{-0.4cm}
\begin{center}
\subfigure[CIFAR-100,VGG-16]{\includegraphics[scale=0.5]{./figs/vgg16_cifar100.png}}
\subfigure[SVHN,VGG-16]{\includegraphics[scale=0.5]{./figs/vgg16_svhn.png}}
\subfigure[CIFAR-100,WRN-28-4]{\includegraphics[scale=0.5]{./figs/wrn_cifar100.png}}
\subfigure[SVHN,WRN-28-4]{\includegraphics[scale=0.5]{./figs/wrn_svhn.png}}
\caption{Training curve (accuracy given number of epochs) of BSR-Net-based models~\citep{ozdenizci2021training}. Sparse networks (99\%) are learned in standard setups on (a) CIFAR-100 using VGG-16, (b) SVHN using VGG-16, (c) CIFAR-100 using WRN-28-4, (d) SVHN using WRN-28-4.}
\label{fig: c100-stable}
\end{center}
\vspace{-0.6cm}
\end{figure*}



\begin{figure}[!t]
\vspace{-0.2cm}
\begin{center}
\subfigure[Standard]{\includegraphics[width=0.45\textwidth,height=0.32\textwidth]{./figs/full_cifar10_vgg16_na_099.png}}
\subfigure[Adversarial (AT)]{\includegraphics[width=0.45\textwidth,height=0.32\textwidth]{./figs/full_cifar10_vgg16_at_099.png}}
    \caption{Training curve (required epochs to reach given accuracy) of BSR-Net-based models~\citep{ozdenizci2021training}. Dense networks are learned in standard and adversarial setups on CIFAR-10 using VGG-16.}
\label{fig: acc and epoch dense}
\end{center}
\vskip -0.2in
\end{figure}

\clearpage

In Figure \ref{fig: acc and epoch dense}, we also compare the convergence speed without sparsity. We show a BSR-Net-based result, where dense network is learned by adversarial training (AT) and standard training on CIFAR-10 using VGG-16. The blue curve of our A-BSR-Net tends to be above the yellow curve of BSR-Net, indicating successful acceleration. This demonstrates the broad applicability of our method.




Then, we also show ITOP-based results on ImageNet-2012. As shown in Figure~\ref{fig: acc and epoch img12}, the red and blue curve represent AGENT + RigL-ITOP and RigL-ITOP on 80\% and 90\% sparse ResNet-50, respectively. 
For 80\% sparsity, we can see that the red curve is above the blue curve, demonstrating the acceleration effect of our AGENT, especially in the early stages. For 90\% sparity, we can see that the red curve is more stable than the blue curve, which shows the stable effect of our AGENT on large data sets and is a slightly different manifestation of the strengths of our AGENT. If we use SVRG in this case, we will not only fail to train stably, but also slow down the training speed. In contrast, our AGENT can solve the limitation of SVRG.

For other sparsity levels, we can expect advantages of our AGENT, in terms of acceleration or stability. Moreover, we can expect more significant speedups at different sparsity levels with more hyperparameter tuning, as the speedups are guaranteed by theoretical proofs. 

\begin{figure}[!t]
\vspace{-0.2cm}
\begin{center}
\subfigure[80\% Sparsity]{\includegraphics[width=0.48\textwidth,height=0.35\textwidth]{./sub_figs/imagenet_sparsity_0_8_itop.pdf}}
\subfigure[90\% Sparsity]{\includegraphics[width=0.48\textwidth,height=0.35\textwidth]{./figs/img12_sp09_itop_rigl.pdf}}
    \caption{Training curve (required epochs to reach given accuracy) of ITOP-based models~\citep{liu2021we}. Sparse networks are learned in standard setup on ImageNet-2012 using ResNet-50.}
\label{fig: acc and epoch img12}
\end{center}
\vskip -0.2in
\end{figure}











\subsection{Number of Training Epoch Comparisons}

We also compare the number of training epochs required to reach the same accuracy in BSR-Net-based results. 
In Figures \ref{fig: acc and time}, \ref{subfig: acc and time1}, \ref{subfig: acc and time2}, \ref{subfig: acc and time3}, \ref{subfig: acc and time4}, \ref{subfig: acc and time5}, \ref{subfig: acc and time6},
the blue curves (A-BSR-Net) are always lower than yellow curves (BSR-Net and BSR-Net (ori)), indicating faster convergence of A-BSR-Net.







\begin{figure*}[!t]
\vspace{-0.2cm}
\begin{center}
\subfigure[Wide-ResNet-28-4]{\includegraphics[width=0.45\textwidth,height=0.33\textwidth]{./figs/cifar100_wrn28_4.png}}
\subfigure[ResNet-18]{\includegraphics[width=0.45\textwidth,height=0.337\textwidth]{./figs/cifar100_resnet18.png}}
\caption{Comparisons (required hours to reach given accuracy. We evaluate sparse networks (99\%) learned with natural training on CIFAR-100 using (a) Wide-ResNet-28-4, and (b) ResNet-18.}
\label{fig: acc and time}
\end{center}
\vspace{-0.4cm}
\end{figure*}



\begin{figure}[ht]
\vspace{-0.2cm}
\begin{center}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_vgg16_na_10.png}}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_vgg16_na_10_ori.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_vgg16_na_1.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_vgg16_na_1_ori.png}}
\caption{Comparisons (required hours to reach given accuracy. We evaluate sparse networks (99\% or 90\%) learned with natural training on CIFAR-10 using VGG-16.}
\label{subfig: acc and time1}
\end{center}
\vskip -0.2in
\end{figure}


\begin{figure}[ht]
\vspace{-0.2cm}
\begin{center}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_vgg16_na_10.png}}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_vgg16_na_10_ori.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_vgg16_at_1.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_vgg16_at_1_ori.png}}
\caption{Comparisons (required hours to reach given accuracy). We evaluate sparse networks (99\% or 90\%) learned with adversarial training (objective: AT) on CIFAR-10 using VGG-16.}
\label{subfig: acc and time2}
\end{center}
\vskip -0.2in
\end{figure}



\begin{figure}[!t]
\vspace{-0.2cm}
\begin{center}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_wrn28_4_na_10.png}}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_wrn28_4_na_10_ori.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_wrn28_4_na_1.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_wrn28_4_na_1_ori.png}}
\caption{Comparisons (required hours to reach given accuracy). We evaluate sparse networks (99\% or 90\%) learned with natural training on CIFAR-10 using Wide-ResNet-28-4.}
\label{subfig: acc and time3}
\end{center}
\vskip -0.2in
\end{figure}


\begin{figure}[!t]
\vspace{-0.2cm}
\begin{center}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_wrn28_4_at_10.png}}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_wrn28_4_at_10_ori.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_wrn28_4_at_1.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/cifar10_wrn28_4_at_1_ori.png}}
\caption{Comparisons (required hours to reach given accuracy). We evaluate sparse networks (99\% or 90\%) learned with adversarial training (objective: AT) on CIFAR-10 using Wide-ResNet-28-4.}
\label{subfig: acc and time4}
\end{center}
\vskip -0.2in
\end{figure}


\begin{figure}[!t]
\vspace{-0.2cm}
\begin{center}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/svhn_vgg16_na_10.png}}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/svhn_vgg16_na_10_ori.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/svhn_vgg16_na_1.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/svhn_vgg16_na_1_ori.png}}
\caption{Comparisons (required hours to reach given accuracy). We evaluate sparse networks (99\% or 90\%) learned with natural training on SVHN using VGG-16.}
\label{subfig: acc and time5}
\end{center}
\vskip -0.2in
\end{figure}


\begin{figure}[!t]
\vspace{-0.2cm}
\begin{center}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/svhn_vgg16_trades_10.png}}
\subfigure[90\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/svhn_vgg16_trades_10_ori.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/svhn_vgg16_trades_1.png}}
\subfigure[99\% Sparsity]{\includegraphics[scale=0.5]{sub_figs/svhn_vgg16_trades_1_ori.png}}
\caption{Comparisons (required hours to reach given accuracy). We evaluate sparse networks (99\% or 90\%) learned with adversarial training (objective: TRADES) on SVHN using VGG-16.}
\label{subfig: acc and time6}
\end{center}
\vskip -0.2in
\end{figure}


\clearpage

\subsection{Scaling Parameter Setting}\label{sub-sec scale}

The choice of the scaling parameter $\gamma$ is important to the acceleration and can be seen as a hyper-parameter tuning process. We experiment with different values of $\gamma$ and find that setting $\gamma=0.1$ is a good choice for effective acceleration of training. The presented results are based on sparse networks (99\%) learned with adversarial training (objective: AT) on CIFAR-10 using VGG-16.



As shown in Figure \ref{fig: scaling} (a), we compare the training curves (testing accuracy at different epochs) A-BSR-Net ($\gamma=0.1$), A-BSR-Net ($\gamma=0.5$), and BSR-Net. The yellow curve for A-BSR-Net ($\gamma=0.5$) collapses after around 40 epochs training, indicating a model divergence. The reason is that if setting $\gamma$ close to 1, e.g., like 0.5, we will not be able to completely avoid the increase in variance. The increase in variance will lead to a decrease in performance, which is similar to "No $\gamma$" in section 5.4 of the manuscript. 


As shown in Figure \ref{fig: scaling} (b), we compare the training curves (testing accuracy at different epochs) A-BSR-Net ($\gamma=0.1$), A-BSR-Net ($\gamma=0.01$), and BSR-Net. The yellow curve for A-BSR-Net ($\gamma=0.01$) is below the blue curve for A-BSR-Net ($\gamma=0.1$), indicating a slower convergence speed. The reason is that if $\gamma$ is set small, such as 0.01, the weight of the old gradients will be small. Thus, the old gradients will have limited influence on the updated direction of the model, which tends to slow down the convergence and sometimes can lead to more training instability.


\begin{figure}[ht]
\vspace{-0.2cm}
\begin{center}
\subfigure[Scaling parameter = 0.1 or 0.5]{\includegraphics[scale=0.45]{sub_figs/cifar_at_vgg_05.pdf}}
\subfigure[Scaling parameter = 0.1 or 0.01]{\includegraphics[scale=0.45]{sub_figs/cifar_at_vgg_001.pdf}}
\caption{Comparisons (testing accuracy given the number of epochs) with different scaling parameters in BSR-Net-based models \cite{ozdenizci2021training}. We evaluate sparse networks (99\%) learned with adversarial training (objective: AT) on CIFAR-10 using VGG-16. (a) scaling parameter = 0.1 or 0.5, (b) scaling parameter = 0.1 or 0.01.}
\label{fig: scaling}
\end{center}
\vskip -0.2in
\end{figure}





\subsection{Other Variance Reduction Method Comparisons}

We also include more results about comparison between our ADSVRG and stochastic variance reduced gradient (SVRG) \cite{baker2019control, chen2019convergence, zou2018subsampled}, a popular variance reduction method in non-sparse case, to show the limitations of previous methods. 



\subsubsection{BSR-Net-based Results}

The presented results are based on sparse networks (99\%) learned with adversarial training (objective: AT) on CIFAR-10 using VGG-16. As presented in Figure \ref{fig: svrg}, we show the training curves (testing accuracy at different epochs)of A-BSR-Net, BSR-Net, and BSR-Net using SVRG. The yellow curve for BSR-Net using SVRG rises to around 0.4 and then rapidly decreases to a small value around 0.1, indicating a model divergence. This demonstrates that SVRG does not work for sparse training. As for the blue curve for our A-BSR-Net, it is always above the green curve for BSR-Net, indicating a successful acceleration.


\begin{figure}[ht]
\vspace{-0.2cm}
\begin{center}
\includegraphics[scale=0.75]{sub_figs/cifar_at_vgg_svrg.pdf}
\caption{Comparisons (testing accuracy given the number of epochs) with different variance reduction methods in BSR-Net-based models \cite{ozdenizci2021training}. We evaluate sparse networks (99\%) learned with adversarial training (objective: AT) on CIFAR-10 using VGG-16.}
\label{fig: svrg}
\end{center}
\vskip -0.2in
\end{figure}


\subsubsection{RigL-based Results}

The presented results are based on sparse networks (90\%) learned with standard training on CIFAR-100 using ResNet-50. As presented in Figure \ref{fig: svrg rigl}, we show the training curves (testing accuracy at different epochs) of A-RigL, RigL, and RigL using SVRG. The yellow curve for RigL using SVRG is always below the other two curves, indicating a slower model convergence. This demonstrate that SVRG does not work for sparse training. As for the blue curve for our A-RigL, it is always on the top of the green curve for RigL, indicating that the speedup is successful.

\begin{figure}[ht]
\vspace{-0.2cm}
\begin{center}
\includegraphics[scale=0.75]{sub_figs/svrg_rigl_resnet_cifar100_01.pdf}
\caption{Comparisons (testing accuracy given the number of epochs) with different variance reduction methods in RigL-based models \cite{evci2020rigging}. We evaluate sparse networks (90\%) learned with standard training on CIFAR-100 using ResNet-50.}
\label{fig: svrg rigl}
\end{center}
\vskip -0.2in
\end{figure}



\subsection{Final Accuracy Comparisons}

We also provide additional BSR-Net-based results for the final accuracy comparison. In addition to the BSR-Net and A-BSR-Net in the manuscript, we also include HYDRA in the appendix, which is also a SOTA sparse and adversarial training pipeline. The results are trained on SVHN using VGG-16 and WideResNet-28-4 (WRN-28-4). The final results for BSR-Net and HYDRA are obtained from \cite{ozdenizci2021training} using their original learning rate schedules. As shown in Table \ref{tb: end mul}, it is encouraging to note that our method tends to be the best in all cases when given clean test samples. In terms of the robustness, our A-BSR-Net beats HYDRA in most cases, while experience a performance degradation compared to BSR-Net.



\linespread{1.1}
\begin{table}[!t]
\caption{Comparisons the BSR-Net \cite{ozdenizci2021training} and HYDRA \cite{sehwag2020hydra}. Evaluations of sparse networks learned with robust training objectives (TRADES) on SVHN using VGG-16 and WideResNet-28-4. Evaluations are after full training (200 epochs) and presented as clean/robust accuracy (\%). Robust accuracy is evaluated via $\text{PGD}^{50}$ with 10 restarts $\epsilon= 8/255$.}
\label{tb: end mul}
\begin{center}
\addtolength{\tabcolsep}{-2.5pt}
\renewcommand{\arraystretch}{1}
\begin{sc}
\begin{tabular}{lcccc}
\toprule
& & BSR-Net & HYDRA & Ours \\
\midrule
\multirow{2}{*}{90\% Sparsity} & VGG-16 & 89.4/\textbf{53.7} & 89.2/52.8& \textbf{94.4}/51.9 \\
~ & WRN-28-4 & 92.8/\textbf{55.6} & 94.4/43.9& \textbf{95.5}/46.2\\
\midrule
\multirow{2}{*}{99\% Sparsity} & VGG-16 & 86.4/\textbf{48.7} & 84.4/47.8 & \textbf{90.9}/47.9\\
~ & WRN-28-4 & 89.5/\textbf{52.7} & 88.9/39.1 & \textbf{92.2}/51.1  \\
\bottomrule
\end{tabular}
\end{sc}
\end{center}
\vskip -0.1in
\end{table}

\subsection{Gradient Change Speed \& Sparsity Level}\label{sub-sec:grad-speed}

In sparse training, when there is a small change in the weights, the gradient changes faster than in dense training, and this phenomenon can be expressed as a low correlation between the current and previous gradients, making the existing variance reduction methods ineffective.

We first demonstrate this lower correlation from an intuitive point of view.
Considering the weights on which the current and previous gradients were calculated, there are three cases to be discussed in sparse training when the masks of current and previous gradients are different.
First, if current weights are pruned, we do not need to consider their correlation because we do not need to update the current weights using the corresponding previous weights. Second, if current weights are not pruned but previous weights are pruned, the previous weights are zero and the difference between two weights is relatively large, leading to a lower relevance.
Third, if neither the current nor the previous weights are pruned, which weights are pruned can still change significantly, leading to large changes in the current and previous models. Thus, the correlation between the current and previous gradients of the weights will be relatively small.
Thus, it is not a good idea to set $c=1$ directly in sparse training which can even increase the variance and slow down the convergence.


When the masks of the current and previous gradients are the same, the correlation still tends to be weaker. As we know, $c_t^* = \frac{\mathrm{Cov}(g_{\text{new}}, g_{\text{old}})}{\mathrm{Var}(g_{\text{old}})}$. Even if $\mathrm{Cov}(g_{\text{new}}, g_{\text{old}})$ does not decrease, the variance $\mathrm{Var}(g_{\text{old}})$ increases in sparse training, leading to a decrease in $c_t^*$.


Apart from the analysis above, we also do some experiments to demonstrate that the gradient changes faster as the sparsity increases. 
To measure the rate of change, our experiments are described below.
We begin with fully-trained checkpoints from ResNet-50 on CIFAR-100 with RigL and SET at 0\%, 50\%, 80\%, 90\%, and 95\% sparsity.
We calculate and store the gradient of each weight on all training data.
Then, we add Gaussian perturbations (std = 0.015) to all the weights and calculate the gradients again.
Lastly, we calculate the correlation between the gradient of the new perturbed weights and the old original weights.

As we know, there is always a difference between the old and new weights. 
If the gradients become very different after adding some small noise to the weights, the new and old gradients will tend to have smaller correlations. If the gradients do not change a lot after adding some small noise, the old and new gradients will have a higher correlation.
Thus, we add Gaussian noise to the weights to simulate the difference between the new and old gradients.
As shown in Table~\ref{subtb: corr}, the correlation decreases with increasing sparsity, which indicates a weaker correlation in sparse training and supports our claim.

\linespread{1.2}
\begin{table}[h]
\vspace{-0.2cm}
\small
\addtolength{\tabcolsep}{0.5pt}
\renewcommand{\arraystretch}{0.8}
\caption{Correlation between the gradient of the new perturbed weights and the old original weights from ResNet-50 on CIFAR-100 produced by RigL and SET at different sparsity including 0\%, 50\%, 80\%, 90\%, 95\%, 99\%.
\label{subtb: corr}
\begin{center}
\begin{small}
\renewcommand{\arraystretch}{1}
\begin{sc}
\begin{tabular}{cccccc}
\toprule \toprule
Sparsity & 0\% & 50\% &80\% & 90\% &95\% \\
\midrule
ResNet-50, CIFAR-100 (RigL) & 0.6005 & 0.4564 & 0.3217 & 0.1886 & 0.1590 \\
ResNet-50, CIFAR-100 (SET) & 0.6005 & 0.4535 & 0.2528 & 0.1763 & 0.1195 \\
\bottomrule\bottomrule
\end{tabular}
\end{sc}
\end{small}
\end{center}
\vspace{-0.4cm}
\end{table}



\subsection{Comparison between True Correlation \& Our Approximation}\label{sub-sec:corr-approx}

In this section, to test how well our approximation estimates the true optimum c, we empirically compare the approximation $c^*$ in Eq. (\ref{equ: c loss}) (in the main manuscript) and the correlation between gradient of current weights and gradient of previous epoch weights. As shown in Figure \ref{fig: rigl corr}, the yellow and blue curves represent the approximation $c^*$ and the correlation, respectively. The two curves tend to have similar up-and-down patterns, and the yellow curves usually have a larger magnitude. This suggests that our c approximation captures the dynamic patterns of the correlation. For the larger magnitude, it can be matched by our scaling parameter.


\begin{figure}[ht]
\vspace{-0.2cm}
\begin{center}
\subfigure[90\%]{\includegraphics[scale=0.45]{sub_figs/cifar10_res_90_corr.pdf}}
\subfigure[99\%]{\includegraphics[scale=0.45]{sub_figs/cifar10_res_99_corr.pdf}}
\caption{Comparisons between the approximation $c^*$ and correlation between gradient of current weights and gradient of previous epoch weights. We evaluate sparse networks learned with RigL-based standard training on CIFAR-10 using ResNet-50 with (a) 90\% sparsity and (b) 99\% sparsity.}
\label{fig: rigl corr}
\end{center}
\vskip -0.2in
\end{figure}


\subsection{Variants of RigL}

RigL is one of the most popular dynamic sparse training pipeline which uses weight magnitude for pruning and gradient magnitude for growing. Our method adaptively updates the new batch gradient using the old storage gradient which usually has less noise. As a result, the variance of the new batch gradient is reduced, leading to fast convergence. Currently, we only use gradients with corrected variance in weight updates. A natural question is how does it perform if we also use this variance-corrected gradient for weight growth in RigL.

We do some experiments in RigL-based models trained on CIFAR-10. As shown in Figure \ref{fig: rigl itop grad}, the blue curves (RigL-ITOP-G) and yellow curves (RigL-ITOP) correspond to the weight growth with and without the variance-corrected gradient, respectively. We can see that in the initial stage, the blue curves are higher than the yellow curves. But after the first learning rate decay, they tend to be lower than the yellow curves. This suggests that weight growth using a variance-corrected gradient at the beginning of training can help the model improve accuracy faster. However, this may lead to a slight decrease in accuracy in the later training stages. This may be due to the fact that some variance in the gradient can help the model explore local regions better and find better masks as the model approaches its optimal point.


\begin{figure}[ht]
\vspace{-0.2cm}
\begin{center}
\subfigure[VGG-C]{\includegraphics[scale=0.45]{sub_figs/cifar10_vgg_99_grad.pdf}}
\subfigure[ResNet-34]{\includegraphics[scale=0.45]{sub_figs/cifar10_res50_99_grad.pdf}}
\caption{Comparisons (testing accuracy given the number of epochs) between weight growth with (RigL-ITOP-G) and without (RigL-ITOP) variance-corrected gradient  \cite{liu2021we}. We evaluate sparse networks (99\%) learned with standard training on CIFAR-10 using (a) VGG-C and (b) ResNet-34.}
\label{fig: rigl itop grad}
\end{center}
\vskip -0.2in
\end{figure}






\subsection{Comparison with Reducing Learning Rate}

To demonstrate the design of the scaling parameter $\gamma$, we compare our AGENT with "Reduce LR", where we remove the scaling parameter $\gamma$ from AGENT and set the learning rate to 0.1 times the original one. As shown in Table~\ref{subtb: reduce lr}, reducing the learning rate can lead to a comparable convergence rate in the early stage. However, it slows down the later stages of training and leads to sub-optimal final accuracy. The reason is that it reduces both signal and noise, and therefore does not improve the signal-to-noise ratio or speed up the sparse training.

The motivation of $\gamma$ is to avoid introducing large variance due to error in approximating $c_t$ and bias due to the adversarial training. The true correlation depends on many factors such as the dataset, architecture, and sparsity. In some cases, it can be greater or smaller than 10\%. For the value of $\gamma$, it is a hyperparameter and we can choose different values for different settings. In our case, for simplicity, we choose $\gamma=0.1$ for all the settings, and find that it works well and accelerates the convergence. If we tune the value of $\gamma$ for different settings according to their corresponding correlations, it is possible to obtain faster convergence rates.


\linespread{1.2}
\begin{table}[ht]
\vspace{-0.2cm}
\small
\addtolength{\tabcolsep}{0.5pt}
\renewcommand{\arraystretch}{0.8}
\caption{Testing accuracy (\%) of SET-ITOP-based models for AGENT (ours) and "Reduce LR". Sparse VGG-C and ResNet-34 are learned in standard setups.
\label{subtb: reduce lr}
\begin{center}
\begin{small}
\renewcommand{\arraystretch}{1}
\begin{sc}
\begin{tabular}{cccccc}
\toprule \toprule
Epoch & 20& 80& 130& 180& 240 \\
\midrule 
Reduce LR (VGG-C, SET-ITOP)&\textbf{76.5}& 81.3& 84.6& 85.5& 85.5 \\
AGENT (VGG-C, SET-ITOP) & 76.1& \textbf{81.5}&\textbf{87.6}&\textbf{87.1}&\textbf{88.6}\\
Reduce LR (ResNet-34, SET-ITOP)& 81.4&\textbf{85.9}& 89.3& 89.5& 89.8 \\
AGENT (ResNet-34, SET-ITOP) &\textbf{83.0}&  85.6& \textbf{92.0}&\textbf{92.3}&\textbf{92.5} \\
\bottomrule\bottomrule
\end{tabular}
\end{sc}
\end{small}
\end{center}
\vspace{-0.4cm}
\end{table}


\subsection{Comparison with Momentum-based Methods}

The momentum-based approach works well in general, but it still suffers from optimization difficulties due to sparsity constraints. 
For example, in our baseline SGD, following the original code base, we have also added momentum to the optimizer. However, as shown in the pink curves in Figure 2, it still has training instability and convergence problems. 
The reason is that they do not take into account the sparse and adversarial training characteristics and cannot provide an adaptive balance between old and new information.

Our method AGENT is designed for sparse and adversarial training and can establish a finer control over how much information we should get from the old to help the new. 
To demonstrate the importance of this fine-grained adaptive balance, we do ablation studies in Section 6.4. In "Fixed $c_t$", we set $c_t=0.1$ and test the convergence rate without the adaptive control. 
We find that the adaptive balance (ours) outperforms "Fixed $c_t$" in almost all cases, especially in adversarial training. For standard training, "Fix $c_t$" provides similar convergence rates to our method, while ours tends to have better final scores.

\section{Additional Details about Experiment Settings}\label{sub-sec:add-detail}

\subsection{Gradient Variance and Correlation Calculation}\label{subsec: intro}

We calculate the gradient variance and correlation of the ResNet-50 on CIFAR-100 from RigL~\citep{evci2020rigging} and SET~\citep{mocanu2018scalable} at different sparsities including 0\%, 50\%, 80\%, 90\%, and 95\%. The calculation is based on the checkpoints from~\citet{sundar2021reproducibility}.


\textbf{Gradient variance}: We first load fully trained checkpoints for the 0\%, 50\%, 80\%, 90\%, and 95\% sparse models. Then, to see the gradient variance around the converged optimum, we add small perturbations to the weights and compute the mean of the gradient variance. For each checkpoint, we do three replicates.

\textbf{Gradient correlation}: We begin with fully-trained checkpoints at 0\%, 50\%, 80\%, 90\%, and 95\% sparsity.
We calculate and store the gradient of each weight on all training data. Then, we add Gaussian perturbations to all the weights and calculate the gradients again.
Lastly, we calculate the correlation between the gradient of the new perturbed weights and the old original weights. For each checkpoint, we do three replicates.


\subsection{Implementations}
\textbf{In BSR-Net-based results}, aligned with the choice of~\citet{ozdenizci2021training},
the gradients for all models are calculated by SGD with momentum and decoupled weight decay~\citep{loshchilov2019decoupled}. All models are trained for 200 epochs with a batch size of 128. 

\textbf{In RigL-based results}, we follow the settings in~\citet{evci2020rigging, sundar2021reproducibility}. We train all the models for 250 epochs with a batch size of 128, and parameters are optimized by SGD with momentum. 

\textbf{In ITOP-based results}, we follow the settings in~\citet{liu2021we}. For CIFAR-10 and CIFAR-100, we train all the models for 250 epochs with a batch size of 128. For ImageNet-2012, we train all the models for 100 epochs with a batch size of 64. Parameters are optimized by SGD with momentum. 

\subsection{Learning Rate}

Aligned with popular sparse training methods~\citep{evci2020rigging, ozdenizci2021training, liu2021we}, we choose piecewise constant decay schedulers for learning rate and weight decay. 
In our A-BSR-Net, we use the 50th and 100th epochs as the dividing points of our learning rate decay scheduler. The reason is that our approach has faster convergence and doesn't require a long warm-up period. In the evaluation shown in the manuscript, we also use this scheduler for BSR-Net for a more accurate and fair comparison. 


\subsection{Initialization (BSR-Net-based results)}

Consistent with \cite{ozdenizci2021training}, we also choose Kaiming initialization to initialize the network weights \cite{he2015delving}



\subsection{Benchmark Datasets (BSR-Net-based results)}

For a fair comparison, we choose the same benchmark datasets as \cite{ozdenizci2021training}. Specifically, we use CIFAR-10 and CIFAR-100 \cite{krizhevsky2009learning} and SVHN \cite{netzer2011reading} in our experiments. Both CIFAR-10 and CIFAR-100 datasets include 50, 000 training and 10, 000 test images. SVHN dataset includes 73, 257 training and 26, 032 test samples.

\subsection{Data Augmentation}

We follow a popular data augmentation method used in \cite{ozdenizci2021training, he2016deep}. In particular, we randomly shift the images to the left or right, crop them back to their original size, and flip them in the horizontal direction. In addition, all the pixel values are normalized in the range of [0, 1].

\section{Appendix: Theoretical Proof of Convergence Rate}\label{appendix:proof}

In this section, we provide a detailed proof for the convergence rate of our AGENT method. We start with some assumptions on which we will give some useful lemmas. Then, we will establish the convergence rate of our AGENT method based on these lemmas.

\subsection{Algorithm Reformulation}

We reformulate our Adaptive Gradient Correction (AGENT) into a math-friendly version that is shown in Algorithm \ref{sub-alg:avr-sgld}. 

\begin{algorithm}[H]
\small
   \caption{Adaptive Gradient Correction}
   \label{sub-alg:avr-sgld}
\begin{algorithmic}
   \STATE \textbf{Input:} Initialize $\bm{\theta}_{0}^0$ and $c_{-1}=0$, set the number of epochs $S$, epoch length $m$, step sizes $h_t$, scaling parameter $\gamma$, and smoothing factor $\alpha$
   \FOR{$s=0$ {\bfseries to} $S-1$}
   \STATE $\widetilde{\bm{\theta}}=\bm{\theta}_{0}^s$
   \STATE $\widetilde{g} = (\sum_{i=1}^N \nabla G(\textbf{x}_i;\widetilde{\bm{\theta}}))/N$
   \STATE Calculate $\widehat{c}_s^*$ via Eq. (\ref{equ: c loss})
   \STATE $\widetilde{c}_{s} = (1-\alpha)\widetilde{c}_{s-1} + \alpha \widehat{c}_s^*$   
   \STATE $c_{s} = \gamma \widetilde{c}_s$
   \FOR{$t=0$ {\bfseries to} $m-1$}
   \STATE Sample a mini-batch data $\textbf{B}_t$ with size $n$
  
   \STATE $\bm{\theta}_{t+1}^s = \bm{\theta}_{t}^s - \eta_t  \bigg{(}  \frac{1}{n}\sum_{i\in \textbf{B}_t}\big{(}g_i(\bm{\theta}_{t}^s) - c_s \cdot  g_i(\widetilde{\bm{\theta}})\big{)} + c_s \cdot\widetilde{g} \bigg{)}$
   \ENDFOR
   \STATE $\bm{\theta}_{0}^{s+1} = \bm{\theta}_{m}^s$
   \ENDFOR
   \STATE {\bfseries Output:} Iterates $\bm{\theta}_{\pi}$ chosen uniformly random from $\{\{\bm{\theta}_{t}^s\}_{t=0}^{m-1}\}_{s=0}^{S-1}$
\end{algorithmic}
\end{algorithm}



\subsection{Assumptions}

\textbf{L-smooth}: A differentiable function $ G: \mathbb{R}^n \rightarrow \mathbb{R}$ is said to be L-smooth if for all ${\bm{x}},{\bm{y}} \in \mathbb{R}^n$ is satisfies $|| \nabla G({\bm{x}}) - \nabla G({\bm{y}}) || \leq L||{\bm{x}} - {\bm{y}}||$. And an equivalent definition is for. all ${\bm{x}}, {\bm{y}} \in \mathbb{R}^n$:
\begin{equation}
\begin{split}
    -\frac{L}{2}||{\bm{x}}-{\bm{y}}||^2 \leq G(x) - G(y) - \langle \nabla G({\bm{x}}), {\bm{x}} - {\bm{y}}
    \rangle  \leq \frac{L}{2}||{\bm{x}}-{\bm{y}}||^2 \nonumber
\end{split}
\end{equation}

$\bm{\sigma}$\textbf{-bounded}: We say function G has a $\sigma$-bounded gradient if $|| \nabla G_{i}({\bm{x}})|| \leq \sigma $ for all $i \in \left[ N \right]$ and ${\bm{x}} \in \mathbb{R}^n$

\subsection{Analysis framework }

Under the above assumptions, we are ready to analyze the convergence rate of AGENT in \textbf{Algorithm~\ref{sub-alg:avr-sgld}}. To introduce the convergence analysis more clearly, we provide a brief analytical framework for our proof.

\begin{itemize}
    \item[$\bullet$] First, we need to show that the variance of our gradient estimator is smaller than that of minibatch SVRG under proper choice of $c_s$. Since the gradient estimator of both AGENT and minibatch SVRG are unbiased estimators in standard training, we only need to show that our bound $E[||\textbf{u}_t||^2]$ is smaller than minibatch SVRG. (See in Lemma 1)
    
    \item[$\bullet$] Based on above fact, we next apply the Lyapunov function to prove the convergence rate of AGENT in one arbitrary epoch. (See in Lemma 3)
    
    \item[$\bullet$] Then, we extend our previous results to the entire epoch (from 0 to $S$-th epoch) and derive the convergence rate of the output $\theta_{\pi}$ of \textbf{Algorithm~\ref{sub-alg:avr-sgld}}. (See in Lemma 4)
     
    \item[$\bullet$] Finally, we compare the convergence rate of our AGENT with that of minibatch SVRG. Setting the parameters in Lemma 4 according to the actual situation of sparse learning, we obtain a bound that is more stringent than minibatch SVRG.
    
   
\end{itemize}

\subsection{lemma}

We first denote step length $\eta_{t} = N \cdot h_{t}$. Since we mainly focus on a single epoch, we drop the superscript $s$ and denote $\textbf{u}_{t} = \frac{1}{n}\sum_{i\in \textbf{B}_t}\bigg{(}g_i(\bm{\theta}_t)-  c \cdot g_i(\widetilde{\bm{\theta}})\bigg{)} + c \cdot\widetilde{g}$ which is the gradient estimator in our algorithm and $\bm{\tau}_{t} = \frac{1}{n}\sum_{i\in \textbf{B}_t}\bigg{(}g_i(\bm{\theta}_t)-  c \cdot g_i(\widetilde{\bm{\theta}})\bigg{)}$, then lines the update procedure in \textbf{Algorithm 2} can be replaced with $\bm{\theta}_{t+1} = \bm{\theta}_t - \eta_{t}  \cdot \textbf{u}_{t}$

\subsubsection{lemma 1}
For the $\textbf{u}_{t}$ defined above and function G is a L-smooth, $\lambda$ - strongly convex function with $\sigma$-bounded gradient, then we have the following results:

\begin{equation}
\begin{split}
     \mathbb{E} \left[ ||\textbf{u}_{t} ||^2 \right] \leq 2\mathbb{E} \left[ || g(\bm{\theta}_{t})||^2 \right] + \frac{4c^2 L^2}{n}\mathbb{E}
    \left[ ||\bm{\theta}_{t} - \tilde{\bm{\theta}} ||^2\right] +
    \frac{4(1-c)^2}{n}\sigma^2
\end{split}
\end{equation}

\textit{Proof}:

\begin{equation}
\begin{split}
    \mathbb{E} \left[ ||\textbf{u}_{t} ||^2 \right]  &= \mathbb{E} \left[ ||\bm{\tau}_{t} + c \cdot\widetilde{g} ||^2\right] \nonumber
    = \mathbb{E} \left[ || \bm{\tau}_{t} + c \cdot\widetilde{g}   - g(\bm{\theta}_{t}) + g(\bm{\theta}_{t})||^2\right] \\
    &\leq 2\mathbb{E} \left[ ||g(\bm{\theta}_{t})||^2\right] + 2\mathbb{E}\left[||\bm{\tau}_{t}-\mathbb{E}(\bm{\tau}_t)||^2\right] 
    \leq 2\mathbb{E} \left[ ||g(\bm{\theta}_{t})||^2\right] + \frac{2}{n}\mathbb{E}\left[\bm{\tau}_t^2\right] \\ &= 2\mathbb{E}\left[||g(\bm{\theta})||^2\right] + \frac{2}{n}\mathbb{E}\left[||c(g_{i}(\bm{\theta}_t)-g_{i}(\tilde{\bm{\theta}})) + (1-c)g_{i}(\bm{\theta}_{t})||^2\right] \\ & \leq 2\mathbb{E}\left[||g(\bm{\theta})||^2\right] + \frac{4}{n}\mathbb{E}\left[||c(g_{i}(\bm{\theta}_t)-g_{i}(\tilde{\bm{\theta}}))||^2\right] + \frac{4 (1-c)^2}{n}\mathbb{E}\left[||g_{i}(\bm{\theta}_{t})||^2\right]
    \\&\leq 2\mathbb{E}\left[||g(\bm{\theta})||^2\right] + \frac{4 c^2 L^2}{n}\mathbb{E}\left[ ||\bm{\theta}_{t}-\tilde{\bm{\theta}}||^2 \right] + \frac{4(1-c)^2}{n} \sigma^2
\end{split}
\end{equation}

The first and third inequality are because $||a + b||^2 \leq 2||a||^2 + 2||b||^2$ , the second inequality follows the $\mathbb{E}\left[||\bm{\tau} - E\left[ \bm{\tau}\right]||^2\right] \leq \mathbb{E} \left[||\bm{\tau}||^2 \right] $ and the last inequality follows the L-smoothness and $\sigma$-bounded of function $G_{i}$.

\begin{remark}
Compared with the gradient estimator of minibatch SVRG, the bound of $\mathbb{E}[||\textbf{u}_{t}||^2]$ is smaller when L is large, $\sigma$ is relative small and $c$ is properly chosen.
\end{remark}


\subsubsection{Lemma 2}

\begin{equation}
\begin{split}
     \mathbb{E} \left[G(\bm{\theta}_{t+1})\right] \leq \mathbb{E}\left[G(\bm{\theta}_{t}) + \eta_t ||g(\bm{\theta}_{t})||^2
     + \frac{L \eta^2}{2}||\textbf{u}_{t}||^2\right] 
\end{split}
\end{equation}

\textit{Proof}:

By the L-smoothness of function G, we have

\begin{equation}
\begin{split}
     \mathbb{E} \left[G(\bm{\theta}_{t+1})\right] &\leq \mathbb{E}\left[G(\bm{\theta}_t) + \langle g(\bm{\theta}_{t}), \bm{\theta}_{t+1} - \bm{\theta}_{t} \rangle + \frac{L}{2} ||\bm{\theta}_{t+1} -  \bm{\theta}_{t}||^2 \right] \nonumber
\end{split}
\end{equation}

By the update procedure in algorithm 2 and unbiasedness, the right hand side can further upper bounded by 
\begin{equation}
\begin{split}
 \mathbb{E}\left[G(\bm{\theta}_t) + \eta_t ||g(\bm{\theta}_{t})||^2 +
 \frac{ L \eta_t^{2}}{2}||\textbf{u}_{t}||^2 \right] \nonumber
\end{split}
\end{equation}

\subsubsection{Lemma 3}
For $b_{t},b_{t+1}, \zeta_{t} > 0$ and $b_{t}$ and $b_{t+1}$ have the following relationship 
\begin{equation}
\begin{split}
 b_{t} = b_{t+1}(1+\eta_{t}\zeta_{t} + \frac{4 c^2 \eta_{t}^2 L^2}{n}) + 2\frac{c^2 \eta_{t}^2 L^3}{n} \nonumber
\end{split}
\end{equation}

and define 

\begin{equation}
\begin{split}
\Phi_{t} \coloneqq  \eta_{t} - \frac{b_{t+1} \eta_{t}}{\zeta_{t}} - \eta_{t}^2 L - 2b_{t+1}\eta_{t}^2 \nonumber
\end{split}
\end{equation}

\begin{equation}
\begin{split}
 \Psi_{t} \coloneqq \mathbb{E}\left[G(\bm{\theta}_{t}) + b_{t}||\bm{\theta}_{t}-\tilde{\bm{\theta}}||^2\right]  
\end{split}
\end{equation}

$\eta_{t}$, $\zeta_{t}$ and $b_{t+1}$ can be chosen such that $\Phi_{t} > 0$.Then the $x_{t}$ in Algorithm 1 have the bound: 
\begin{equation}
\begin{split}
 \mathbb{E} [||g(\bm{\theta}_{t})||^2] \leq \frac{\Psi_{t} - \Psi_{t+1} + \frac{2(L \eta_{t}^2+ 2 b_{t+1} \eta_{t}^2)(1-c)^2}{n}\sigma^2}{\Phi_{t}}  \nonumber
\end{split}
\end{equation}


\textit{Proof}:\\
We apply Lyapunov function  
\begin{equation}
\begin{split}
 \Psi_{t} = \mathbb{E}\left[G(\bm{\theta}_{t}) + b_{t}||\bm{\theta}_{t}-\tilde{\bm{\theta}}||^2\right] \nonumber
\end{split}
\end{equation}

Then we need to bound $||\bm{\theta}_{t}-\tilde{\bm{\theta}}||$

\begin{equation}
\begin{split}
 \mathbb{E}\left[||\bm{\theta}_{t+1}-\tilde{\bm{\theta}}||^2\right] &= 
 \mathbb{E}\left[||\bm{\theta}_{t+1}-\bm{\theta}_{t}+\bm{\theta}_{t} - \tilde{\bm{\theta}}||^2\right] \\& = \mathbb{E}\left[||\bm{\theta}_{t+1}-\bm{\theta}_{t}||^2 +||\bm{\theta}_{t} - \tilde{\bm{\theta}}||^2 + 2 \langle \bm{\theta}_{t+1}-\bm{\theta}_{t}, \bm{\theta}_{t} - \tilde{\bm{\theta}} \rangle \right] \\ &= 
 \mathbb{E}\left[ \bm{\eta_{t}}^2||\textbf{u}_{t}||^2 + ||\bm{\theta}_{t}-\tilde{\bm{\theta}}||^2\right] - 2\eta_t \mathbb{E}\left[\langle g(\bm{\theta}_{t}), \bm{\theta}_{t} - \tilde{\bm{\theta}} \rangle \right] \\ &\leq
 \mathbb{E} [\eta_{t}^2 ||\textbf{u}_{t}^{s+1}||^2 + ||\bm{\theta}_{t} - \tilde{\bm{\theta}}||^2 ]
 + 2 \eta_{t} \mathbb{E}\left[\frac{1}{2 \zeta_{t}} ||g(\bm{\theta}_t)|| + \frac{\zeta_t}{2}||\bm{\theta}_{t} - \tilde{\bm{\theta}}||^2\right]
\end{split}
\end{equation}

The third equality due to the unbiasedness of the update and the last inequality follows Cauchy-Schwarz and Young's inequality. Plugging Equation (6), Equation (7) and Equation (9) into Equation (8), we can get the following bound:

\begin{equation}
\begin{split}
 \Psi_{t+1} &\leq \mathbb{E} \left[ G(\bm{\theta}_{t}) \right] + \bigg{(} b_{t+1}(1 + \eta_{t}\zeta_{t} + \frac{4 c^2 \eta_{t}^2 L^2}{n}) + \frac{2 c^2 \eta_{t}^2 L^3}{n} \bigg{)} \mathbb{E} [|| \bm{\theta}_{t} - \tilde{\bm{\theta}} ||^2]  \\& - (\eta_{t} - \frac{b_{t+1} \eta_{t}}{\zeta_{t}}-L\eta_{t}^2 -  2 b_{t+1} \eta_{t}^2) \mathbb{E}\left[ ||g(\bm{\theta}_{t})||^2\right] + 4(\frac{L \eta_{t}^2}{2} + b_{t+1} \eta_{t}^2) \frac{(1-c)^2}{n} \sigma^2 \\ &= \Psi_{t} - (\eta_{t} - \frac{b_{t+1} \eta_{t}}{\zeta_{t}}-L\eta_{t}^2 -  2 b_{t+1} \eta_{t}^2) \mathbb{E}\left[ ||g(\bm{\theta}_{t})||^2\right] + 4(\frac{L \eta_{t}^2}{2} + b_{t+1} \eta_{t}^2)\frac{(1-c)^2}{n} \sigma^2 \nonumber
\end{split}
\end{equation}

\subsubsection{Lemma 4}

Now we consider the effect of epoch and use $s$ to denote the epoch number. Let $b_{m}^s = 0$, $\eta_{t}^s = \eta$, $\zeta_{t}^s  = \zeta$ and $b_{t}^s = b_{t+1}^s(1+\eta \zeta + \frac{4 c_{s}^2 \eta L^2}{n}) + 2\frac{c_{s}^2 \eta^2 L^2}{n}$, $\Phi_t^s = \eta - \frac{b_{t+1}^s \eta}{\zeta_{t}} - \eta^2 L - 2b_{t+1}^s\eta^2$ Define $\phi \coloneqq \min_{t,s} \Phi_{t}^s$. Then we can conclude that: 

\begin{equation}
\begin{split}
 \mathbb{E} [|| g(\bm{\theta_{\pi}})||^2]  & \leq \frac{G(\theta_{0}) - G(\theta_{*})}{T \phi} + \sum_{s = 0}^{S - 1} \sum_{t = 0}^{m-1} \frac{2 (L + 2 b_{t+1}^s  ) (1 - c_{s})^2 \eta^2 \sigma^2}{T n \phi} \nonumber
\end{split}
\end{equation}

\textit{Proof}:\\

Under the condition of $\eta_t^s = \eta$, we apply telescoping sum on \textbf{Lemma 3}, then we will get:

\begin{equation}
\begin{split}
 \sum_{t = 1}^{m - 1} \mathbb{E}[||g(\bm{\theta}_{t}^s)||^2] \leq \frac{\Psi_{0}^s - \Psi_{m}^s}{\phi}  
 + \sum_{t=0}^{m-1} \frac{2(L + 2b_{t+1}^{s}) (1 - c_{s})^2 \eta^2 \sigma^2}{n \phi}
 \nonumber
\end{split}
\end{equation}

From previous definition, we know $\Psi_{0}^s = G(\tilde{\bm{\theta}}^s)$, $\Psi_{m}^s =  G(\tilde{\bm{\theta}}^{s+1})$ and plugging into previous equation, we obtain:


\begin{equation}
\begin{split}
 \sum_{t = 1}^{m-1} \mathbb{E}[||g(\bm{\theta}_{t}^s)||^2] \leq \frac{G(\tilde{\bm{\theta}}^s)- G(\tilde{\bm{\theta}}^{s+1})}{\phi}  
 + \sum_{t=0}^{m-1} \frac{2(L + 2b_{t+1}^{s}) (1 - c_{s})^2 \eta^2 \sigma^2}{n \phi}
 \nonumber
\end{split}
\end{equation}

Take summation over all the epochs and using the fact that $\tilde{\bm{\theta}}^{0} = \theta_{0}$, $G(\tilde{\bm{\theta}}^{S}) \leq G(\bm{\theta}_{*}) $ we immediately obtain:

\begin{equation}
\begin{split}
 \frac{1}{T}\sum_{s = 0}^{S-1} \sum_{t = 1}^{m-1} \mathbb{E}[||g(\bm{\theta}_{t}^s)||^2] \leq \frac{G(\bm{\theta}_0)- G(\bm{\theta}_{*})}{\phi}  
 + \sum_{s = 0}^{S-1}\sum_{t=0}^{m-1} \frac{2(L + 2b_{t+1}^{s}) (1 - c_{s})^2 \eta^2 \sigma^2}{T n \phi}
\end{split}
\end{equation}

\subsection{Theorem}

\subsubsection{Theorem 1}

Define $\xi_{s} = \sum_{t = 0}^{m-1} (L + 2 b_{t+1}^{s} )$ and $\xi \coloneqq \min_{s} \xi_{s}$. Let $\eta = \frac{\mu n }{L N^{\alpha}} \quad (0 < \mu < 1) \quad and \quad (0 < \alpha \leq 1)$, $\zeta = \frac{L}{N^{\alpha/2}}$ and $ m = \frac{N^{\frac{3\alpha}{2}}}{\mu n} $. Then there exists constant $\nu, \mu, \alpha,  \kappa > 0$ such that $\phi \geq \frac{n \nu}{L N^{\alpha}}$ and $\xi \leq \kappa L$. Then $\mathbb{E} [|| g(\bm{\theta_{\pi}})||^2]$ can be future bounded by:

\begin{equation}
\begin{split}
 \mathbb{E} [|| g(\bm{\theta_{\pi}})||^2] \leq \frac{(G(\bm{\theta}_0)- G(\bm{\theta}_{*})) L N^\alpha}{T n \nu } + \frac{2 \kappa \mu^2 \sigma^2}{ N^\alpha \nu m} \nonumber
\end{split}
\end{equation}

\textit{Proof}:\\

By applying summation formula of geometric progression on the relation $b_{t}^s = b_{t+1}^s(1+\eta_{t}\zeta_{t} + \frac{4 c_{s}^2 \eta_{t}^2 L^2}{n}) + 2\frac{c_{s}^2 \eta_{t}^2 L^3}{n}$, we have $b_{t}^s = \frac{2 c_{s}^2 \eta^2  L^3}{n} \frac{(1+\omega_{s})^{m-t} - 1}{\omega_{s}} $ where:

\begin{equation}
\begin{split}
  \omega_{s} = \eta \zeta + \frac{4 c_{s}^2 \eta^2 L}{n} = \frac{\mu n}{N^{\frac{3 \alpha}{2}}} + \frac{4c_{s}^2 \mu^2 n }{N^{2\alpha}} \leq \frac{(4c_{s}^2 + 1) \mu n}{N^{\frac{3 \alpha}{2}}} \nonumber
\end{split}
\end{equation}

This bound holds because $\mu \leq 1$ and $N \geq 1$ and thus $\frac{4c_{s}^2 \mu^2 n }{N^{2\alpha}} = \frac{4c_{s}^2 \mu n }{N^{\frac{3 \alpha}{2}}} \times \frac{\mu}{N^\frac{\alpha}{2}} \leq \frac{4c_{s}^2 \mu n }{N^{\frac{3 \alpha}{2}}}$. And using this bound, we obtain: 

\begin{equation}
\begin{split}
    b_{0}^s &= \frac{2 \eta^2 c_{s}^2 L^3}{n} \frac{(1+\omega_s)^m - 1}{\omega_s}  = \frac{2 \mu^2 n c_{s}^2 L}{N^{2 \alpha}} \frac{(1+\omega_s)^m - 1}{\omega_s} \\ &\leq \frac{2 \mu n c_s^2 L((1 + \omega_s)^m - 1)}{N^{\frac{\alpha}{2}} (4 c_s + 1)} \leq \frac{2 \mu n c_{s}^2 L((1 + \frac{(4c_{s}^2 + 1) \mu n}{N^{\frac{3 \alpha}{2}}})^{\frac{N^{{\frac{3\alpha}{2}}}}{\mu n}} - 1)}{N^{\frac{\alpha}{2}} (4 c_{s}^2 + 1)} \\ &\leq 
    \frac{2 \mu n c_{s}^2 L (e^{\frac{1}{4c_s^2 + 1}} - 1)}{N^{\frac{\alpha}{2}} (4 c_{s}^2 + 1)} \nonumber
\end{split}
\end{equation}


The last inequality holds because $(1 + \frac{1}{x})^x$ is a monotone increasing function of $x$ when $x > 0$. Thus $(1 + \frac{(4c_{s}^2 + 1) \mu n}{N^{\frac{3 \alpha}{2}}})^{\frac{N^{{\frac{3\alpha}{2}}}}{\mu n}} \leq e^{\frac{1}{4c_s^2 + 1}}$ in the third inequality. And we can obtain the lower bound for $\phi$

\begin{equation}
\begin{split}
\phi = \min_{t,s} \Phi_{t}^s \geq \min_{s} (\eta - \frac{b_{0}^s \eta}{\zeta} - \eta^2 L - 2b_{0}^s\eta^2) \geq \frac{n \nu}{L N^{\alpha}} \nonumber
\end{split}
\end{equation}

The first inequality holds since $b_{s}^{t}$ is a decrease function of $t$. Meanwhile, the second inequality holds because there exist uniform constant $\nu$ such that  $\nu \geq \mu (1-\frac{b_{0}^{s} \eta}{\zeta} - L \eta  - b_{0}^s \eta)$.

\begin{remark}\label{sub-remark: mu small}
 In practice, $b_{0}^s \approx 0$ because both $\gamma$ and $c_s$ is both smaller than 0.1 which leads to $\mu(1-\frac{b_{0}^{s}}{\zeta} - L \eta  - b_{0}^s \eta) \approx \mu(1 - L \eta)$ and this value is usually much bigger than the $\nu^{*}$ in the bound of minibatch SVRG.
\end{remark}

We need to find the upper bound for $\xi$

\begin{equation}
\begin{split}
\xi_{s} & = \sum_{t = 0}^{m-1} (L + 2 b_{t+1}^{s} ) = m L + 2 \sum_{t = 0}^{m -1} b_{t + 1}^{s}  \\ & = m L + 2 \sum_{t = 0}^{m -1} \frac{2 c_{s}^2 \eta^2  L^3}{n} \frac{(1+\omega_{s})^{m - t}-1}{\omega_{s}}  \\ &= m L + \frac{2 c_{s}^2 \eta^2  L^3}{n \omega_{s}}[\frac{(1+\omega_s)^{m+1}- (1+\omega_s)}{\omega_s} - m]
\\ & \leq m L  +  \frac{2 c_{s}^2 \eta^2  L^3}{n} [\frac{1+ \omega_{s}}{\omega_{s}^2}(e^{\frac{1}{4c_s^2 + 1}} - 1) - m ]
\\ & \leq m L + \frac{2c_{s}^2 L N^{\alpha}}{n}(1 + \frac{\mu n }{N^{3\alpha/2}})(e^{\frac{1}{4c_s^2 + 1}} - 1) - \frac{2c_{s}^2 \mu^2 n m L}{N^{2\alpha}} \\&= L [(1-\frac{2c_{s}^2 \mu^2 n L}{N^{2\alpha}}) m + \frac{2c_{s}^2 N^{\alpha}}{n}(1 + \frac{\mu n }{N^{3\alpha/2}})(e^{\frac{1}{4c_s^2 + 1}} - 1)] \nonumber
\end{split}
\end{equation}

The reason why the first inequality holds is explained before and the second inequality holds because $\frac{1+x}{x^2}$ is a monotone decreasing function of $x$ when $x > 0$, $\omega_{s} = \frac{\mu n}{N^{\frac{3 \alpha}{2}}} + \frac{4c_{s}^2 \mu^2 n }{N^{2\alpha}} \leq \frac{\mu n}{N^{\frac{3 \alpha}{2}}}$ and $\eta = \frac{\mu n }{L N^{\alpha}}$. Then $\xi  = \max_{s} \xi_{s} \leq \kappa L$ where $\kappa \geq \max_{s} ((1-\frac{2c_{s}^2 \mu^2 n L}{N^{2\alpha}}) m + \frac{2c_{s}^2 N^{\alpha}}{n}(1 + \frac{\mu n }{N^{3\alpha/2}})(e^{\frac{1}{4c_s^2 + 1}} - 1))$. When $c_{s} \approx 0$, $(1-\frac{2c_{s}^2 \mu^2 n L}{N^{2\alpha}}) m + \frac{2c_{s}^2 N^{\alpha}}{n}(1 + \frac{\mu n }{N^{3\alpha/2}})(e^{\frac{1}{4c_s^2 + 1}} - 1) \approx m$. 

Now we obtain the lower bound for $\phi$ and upper bound for $\xi$, plugging them into equation (10), we will have:

\begin{equation}
\begin{split}
 \mathbb{E} [|| g(\bm{\theta_{\pi}})||^2] & \leq \frac{G(\bm{\theta}_0)- G(\bm{\theta}_{*})}{\phi}  
 + \sum_{s = 0}^{S-1}\sum_{t=0}^{m-1} \frac{2(L + 2b_{t+1}^{s}) (1 - c_{s})^2 \eta^2 \sigma^2}{T n \phi} \\ & \leq \frac{(G(\bm{\theta}_0)- G(\bm{\theta}_{*})) L N^\alpha}{T n \nu } + \sum_{s = 0}^{S-1}\sum_{t=0}^{m-1} \frac{2(L + 2b_{t+1}^{s}) \eta^2 \sigma^2}{T n \phi} \\ & \leq \frac{(G(\bm{\theta}_0)- G(\bm{\theta}_{*})) L N^\alpha}{T n \nu } + \sum_{s = 0}^{S-1} (\frac{2 \eta^2 \sigma^2}{T n \phi})\sum_{t=0}^{m-1}(L + 2b_{t+1}^{s}) \\ &\leq \frac{(G(\bm{\theta}_0)- G(\bm{\theta}_{*})) L N^\alpha}{T n \nu } + \frac{2 \kappa \mu^2 \sigma^2}{ N^\alpha \nu m} \nonumber
\end{split}
\end{equation}

\begin{remark}
In our theoretical analysis above, we consider $c$ as a constant in each epoch, which is still consistent with our practical algorithm for the following reasons.
\end{remark}

(i) In our Algorithm 1, $\widehat{c}_t^*$ is actually a fixed constant within each epoch, which can be different in different epochs. Since it is too expensive to compute the exact $\widehat{c}_t^*$ in each iteration, we compute it at the beginning of each epoch and use it as an approximation in the following epoch.

(ii) As for our proof, we first show the convergence rate of one arbitrary training epoch. In this step, treating $c$ as a constant is aligned with our practical algorithm.

(iii) Then, when we extend the results of one epoch to the whole epoch, we establish an upper bound for different $c$ in each epoch. Thus, the bound can be applied when $c$ differs across epochs, which enables our theoretical analysis consistent with our practical algorithm.


\subsection{Real Case Analysis for Sparse Training}

\subsubsection{CIFAR-10/100 dataset}
In our experiments, we apply both SVRG and AGENT on  CIFAR-10 and CIFAR-100 dataset with $\eta = 0.1$, $\gamma = 0.1$, batch size $m = 128$ and in total 50000 training sample. Under this parameter setting, $\nu$ and $\nu^{*}$in \textbf{Theorem 1} and \textbf{Remark 4} are about 0.1 and 0.06, respectively. While $\frac{2 \kappa \mu^2 \sigma^2}{ N^\alpha \nu m}$ is around $10^{-5}$ which is negligible so we know AGENT should have a tighter bound than SVRG in this situation which matches with the experimental results show in $Figure~ 6$. 


\subsubsection{svhn dataset}
Meanwhile, in SVHN dataset, we train our model with parameters:  $\eta = 0.1$, $\gamma = 0.1$, batch size $m = 573$ and sample size $N = 73257 $. $\nu$, $\nu^{*}$ equal 0.4 and 0.06 respectively and $\frac{2 \kappa \mu^2 \sigma^2}{ N^\alpha \nu m}$ is around $10^{-4}$. Although the second term in \textbf{Theorem 1} is bigger. Since $\nu$ here is a lot bigger than $\nu^*$ which lead to the first term in \textbf{Theorem 1} much smaller than that of \textbf{Remark 4}. So we still obtain a more stringent bound compared with SVRG which also meets with the outcome presented in $Figure~ $9.




 


\section{Experiments}

We add our AGENT to three recent sparse training pipelines, namely SET~\citep{mocanu2018scalable}, RigL~\citep{evci2020rigging}, BSR-Net~\citep{ozdenizci2021training} and ITOP~\citep{liu2021we}.
SET is a broadly-used sparse training method that prunes and regrows connections by examining the magnitude of the weights.
RigL is another popular dynamic sparse training method which uses weight and gradient magnitudes to learn the connections. BSR-Net is a recent sparse training method that updates connections by Bayesian sampling and also includes adversarial setups for model robustness. ITOP is another recent pipeline for dynamic sparse training, which uses sufficient and reliable parameter exploration to achieve in-time over-parameterization and find well-performing sparse models. Detailed information about the dataset, model architectures, and other training and evaluation setups is provided below.








\textbf{Datasets \& Model Architectures:} The datasets we use include CIFAR-10, CIFAR-100~\citep{krizhevsky2009learning}, SVHN~\citep{netzer2011reading}, and ImageNet-2012 (see Appendix) \citep{russakovsky2015imagenet}. For model architectures, we use VGG-16~\citep{simonyan2015very}, ResNet-18, ResNet-50~\citep{he2016deep}, and Wide-ResNet-28-4~\citep{zagoruyko2016wide}.



\textbf{Training Settings:} For sparse training, we choose two sparsity levels, namely 90\% and 99\%. For BSR-Net, we consider both standard and adversarial setups. In RigL and ITOP, we focus on standard training. In standard training, we only use the original data to update the parameters instead of using perturbed samples. For adversarial part, we use the perturbed data with two popular objective (AT and TRADES)~\citep{madry2018towards, zhang2019theoretically}. Following~\citet{ozdenizci2021training}, we evaluate robust accuracy against PGD attacks with random starts using 50 iterations ($\text{PGD}^{50}$)~\citep{madry2018towards, brendel2019accurate}.

\textbf{Implementations: } 
Aligned with the choice of~\citet{evci2020rigging, sundar2021reproducibility, ozdenizci2021training}, the parameters of the model are optimized by SGD with momentum. Thus, the comparison between the popular sparse training pipelines can be viewed as a comparison between AGENT and momentum-based SGD.

\subsection{Convergence Speed \& Stability Comparisons}

\linespread{1.2}
\begin{table}[!t]
\vspace{0.0cm}
\small
\addtolength{\tabcolsep}{0.5pt}
\renewcommand{\arraystretch}{0.85}
\caption{Testing accuracy (\%) of BSR-Net-based models. Sparse VGG-16 are learned in standard and adversarial setups. Results are presented as clean/robust accuracy (\%). For the same number of training epochs, our method has higher accuracy compared to BSR-Net in almost all cases.}
\label{tb: each epc}
\begin{center}
\begin{small}
\renewcommand{\arraystretch}{1}
\begin{sc}
\begin{tabular}{llccccc}
\toprule
& & \multicolumn{2}{c}{90\% Sparsity} & & \multicolumn{2}{c}{99\% Sparsity} \\
 \cline{3-4}   \cline{6-7} 
& & BSR-Net & Ours & & BSR-Net & Ours \\
\midrule
\multirow{6}{*}{\rotatebox{90}{AT}} & 20-th & 55.0 (1.59)/\textbf{38.2} & \textbf{63.6 (1.31)}/37.3 & & 49.8 (1.46)/31.0 & \textbf{56.4 (1.39)}/\textbf{31.4} \\
~ & 40-th & 62.2 (1.88)/\textbf{39.2} & \textbf{64.9 (0.81)}/37.9 & & 54.1 (1.72)/33.9 & \textbf{57.7 (0.39)}/\textbf{34.5} \\
~ & 70-th & 73.1 (0.39)/37.8 & \textbf{75.1 (0.27)}/\textbf{45.2} & & 64.7 (0.30)/34.9 & \textbf{66.0 (0.23)}/\textbf{39.4} \\
~ & 90-th & 73.2 (0.29)/33.6 & \textbf{74.1 (0.25)}/\textbf{44.8} & & 63.7 (0.25)/35.8 & \textbf{65.8 (0.24)}/\textbf{39.8} \\
~ & 140-th & 76.7 (0.27)/\textbf{46.5} & \textbf{77.4 (0.26)}/43.8 & & 68.4 (0.20)/40.8 & \textbf{69.8 (0.14)}/\textbf{41.2} \\
~ & 200-th & 76.6 (0.25)/43.3 & \textbf{78.1 (0.24)}/\textbf{44.6} & & 69.0 (0.15)/\textbf{42.2} &  \textbf{70.7 (0.06)}/42.0 \\
\hline
\multirow{6}{*}{\rotatebox{90}{TRADES}} & 20-th & 62.0 (0.82)/33.3 & \textbf{65.0 (0.61)}/\textbf{37.6} & & 55.7 (0.76)/25.5 & \textbf{57.6 (0.45)}/\textbf{31.6}\\
~ & 40-th & 65.4 (0.97)/35.3 & \textbf{66.0 (0.34)}/\textbf{37.2} & &  \textbf{60.6 (0.69)}/28.9 & 58.4 (0.34)/\textbf{33.4} \\
~ & 70-th & 73.4 (0.52)/34.8 & \textbf{73.5 (0.33)}/\textbf{45.4} & & 66.3 (0.35)/33.5 &  \textbf{67.3 (0.30)}/\textbf{39.0} \\
~ & 90-th & 73.0 (0.36)/36.8 & \textbf{73.6 (0.28)}/\textbf{44.8} & &  66.2 (0.33)/31.7 & \textbf{67.5 (0.24)}/\textbf{39.1} \\
~ & 140-th & 76.4 (0.25)/45.1 & \textbf{76.8 (0.25)}/\textbf{46.3} & &  \textbf{70.0 (0.29)}/38.2 & 69.9 (0.21)/\textbf{41.5} \\
~ & 200-th & 75.6 (0.23)/\textbf{47.2} & \textbf{77.0 (0.24)}/46.2 & &  70.8 (0.19)/39.3 & \textbf{70.9 (0.25)}/\textbf{41.2} \\
\hline
\multirow{6}{*}{\rotatebox{90}{Standard}} & 20-th  & 70.4  (2.50)/0.0 & \textbf{81.8 (0.62)}/0.0 & & 60.6 (1.26)/0.0 & \textbf{69.8 (1.45)}/0.0 \\
~ & 40-th & 77.6 (1.39)/0.0 & \textbf{82.4 (0.47)}/0.0 & & 62.6 (2.47)/0.0 & \textbf{73.7 (0.36)}/0.0 \\
~ & 70-th & 86.8 (0.78)/0.0 & \textbf{89.7 (0.38)}/0.0 & & 79.7 (0.72)/0.0 & \textbf{83.7 (0.24)}/0.0 \\
~ & 90-th & 87.6 (0.63)/0.0 & \textbf{89.3 (0.22)}/0.0 & & 80.5 (0.55)/0.0 & \textbf{83.9 (0.42)}/0.0 \\
~ & 140-th & 91.7 (0.44)/0.0 & \textbf{92.5 (0.06)}/0.0 & & 85.7 (0.42)/0.0 & \textbf{86.9 (0.07)}/0.0 \\
~ & 200-th & 91.8 (0.23)/0.0 & \textbf{92.6 (0.12)}/0.0 & & 85.8 (0.12)/0.0 & \textbf{87.1 (0.25)}/0.0 \\
\bottomrule
\end{tabular}
\end{sc}
\end{small}
\end{center}
\vspace{-0.7cm}
\end{table}


We compare the convergence speed by two criteria, including (a) \textbf{the test accuracy} at the same number of pass data (epoch) and (b) \textbf{the number of pass data (epoch)} required to achieve the same test accuracy,
which is widely used to compare the speed of optimization algorithms~\citep{allen2016variance, chatterji2018theory, zou2018subsampled, cutkosky2019momentum}.





\textbf{For BSR-Net-based results using criterion (a)}, 
Table~\ref{tb: each epc} lists the accuracies on both clean and adversarial samples after 20, 40, 70, 90, 140, and 200 epochs of training, where the higher accuracies are bolded. Sparse VGG-16 are learned on CIFAR-10 in both standard and adversarial sutups. For the standard setup, we only present the clean accuracy. As we can see, our method maintains higher clean and robust accuracies for almost all training epochs and setups which demonstrates the successful acceleration from our method. In particular, for limited time periods like 20 epochs, our A-BSR-Net usually shows dramatic improvements with clean accuracy as high as \textbf{11.4\%}, indicating a significant reduction in early search time. In addition, considering the average accuracy improvement over the 6 time budgets, our method outperforms BSR-Net in accuracy by upto \textbf{5.0\%}. 





\linespread{1.1}
\begin{wraptable}{r}[0pt]{10cm
\vspace{-0.9cm}
\small
\addtolength{\tabcolsep}{0pt}
\renewcommand{\arraystretch}{-4}
\caption{Final accuracy (\%) of RigL-based models at 0\% (dense), 90\% and 99\% sparsity. AGENT + RigL (A-RigL) maintains or even improves the accuracy compared to that of RigL.}
\label{tb: end mul rigl}
\begin{center}
\addtolength{\tabcolsep}{-3.5pt}
\renewcommand{\arraystretch}{1}
\begin{small}
\begin{sc}
\begin{tabular}{lcccc}
\toprule
& & Dense & 90\% & 99\% \\
\midrule
\multirow{2}{*}{CIFAR-10} & A-RigL & \textbf{95.2 (0.24)} & \textbf{95.0 (0.21)} & \textbf{93.1 (0.25)} \\
~ & RigL & 95.0 (0.26)& 94.2 (0.22) & 92.5 (0.33)\\
\midrule
\multirow{2}{*}{CIFAR-100} & A-RigL & 72.9 (0.19) & \textbf{72.1 (0.20)} & \textbf{66.4 (0.14)}\\
~ & RigL & \textbf{73.1 (0.17)} & 71.6 (0.26) & 66.0 (0.19) \\
\bottomrule
\end{tabular}
\end{sc}
\end{small}
\end{center}
\vspace{-0.7cm}
\end{wraptable}




\textbf{For ITOP-based results using criterion (a)}, as shown in Figure \ref{fig: itop conv}, the blue curves (A-RigL-ITOP and A-SET-ITOP) are always higher than the pink curves (RigL-ITOP and SET-ITOP), indicating faster training when using our AGENT. In addition, we can see that the pink curves experience severe up and down fluctuations, especially in the early stages of training. In contrast, the blue curves are more stable all the settings, which indicates AGENT is effective in stabilizing the sparse training.


\begin{figure}[!t]
\setlength{\abovecaptionskip}{-0.1cm}
\vspace{0.2cm}
\begin{center}
\subfigure[VGG-C(RigL)]{\includegraphics[width=0.24\textwidth,height=0.2\textwidth]{figs/acc_epo_cifar10_vgg-c_0_99__gradient_magnitude.pdf}}
\subfigure[ResNet-34(RigL)]{\includegraphics[width=0.24\textwidth,height=0.2\textwidth]{figs/acc_epo_cifar10_ResNet34_0_99__gradient_magnitude.pdf}}
\subfigure[VGG-C(SET)]{\includegraphics[width=0.24\textwidth,height=0.2\textwidth]{figs/acc_epo_cifar10_vgg-c_0_99__random_magnitude.pdf}}
\subfigure[ResNet-34(SET)]{\includegraphics[width=0.24\textwidth,height=0.2\textwidth]{figs/acc_epo_cifar10_ResNet34_0_99__random_magnitude.pdf}}
\caption{Testing accuracy for ITOP-based models at 99\% sparsity on CIFAR-10. A-RigL-ITOP and A-SET-ITOP (blue curves) converge faster than RigL-ITOP and SET-ITOP (pink curves).}
\label{fig: itop conv}
\end{center}
\vspace{-0.6cm}
\end{figure}



\textbf{For BSR-Net-based results using criterion (b)}, Figure \ref{fig: epo-acc-bsn} depicts the number of training epochs required to achieve certain accuracy. We can see that the blue curves (A-BSR-Net) are always lower than the pink curves (BSR-Net), and on average our method reduces the number of training epochs by up to \textbf{52.1\%}, indicating faster training when using our proposed A-BSR-Net.

\begin{figure}[!t]
\setlength{\abovecaptionskip}{-0.2cm}
\vspace{-0.2cm}
\begin{center}
\subfigure[VGG-16, Standard]{\includegraphics[width=0.24\textwidth,height=0.2\textwidth]{figs/epo_acc_1_natural_cifar10_vgg16.pdf}}
\subfigure[WRN-28-4, Standard]{\includegraphics[width=0.24\textwidth,height=0.2\textwidth]{figs/epo_acc_1_natural_cifar10_wrn28_4.pdf}}
\subfigure[VGG-16, AT]{\includegraphics[width=0.24\textwidth,height=0.2\textwidth]{figs/epo_acc_1_at_cifar10_vgg16.pdf}}
\subfigure[WRN-28-4, AT]{\includegraphics[width=0.24\textwidth,height=0.2\textwidth]{figs/epo_acc_1_at_cifar10_wrn28_4.pdf}}
\caption{Number of training epochs required to achieve the accuracy at 99\% sparsity. Our A-BSR-Net (blue curves) need less time to achieve the accuracy compared to BSR-Net (pink curves).}
\label{fig: epo-acc-bsn}
\end{center}
\vspace{-0.8cm}
\end{figure}





\subsection{Final Accuracy Comparisons}



In addition, we compare the final accuracy after sufficient training. 
RigL-based results on CIFAR-10/100 are shown in Table \ref{tb: end mul rigl}. Our method A-RigL tends to be the best in almost all the scenarios.  For BSR-Net-based results in Table \ref{tb: end mul bsr}, we compare our A-BSR-Net with BSR-Net on SVHN using VGG-16 and WideResNet-28-4 (WRN-28-4), and our method is often the best again.
This shows that our AGENT can accelerate sparse training while maintaining or even improving the accuracy.


\subsection{Comparison with Other Gradient Correction Methods}


\linespread{1.1}
\begin{wraptable}{r}[0pt]{0.52\textwidth}
\vspace{-0.5cm}
\small
\addtolength{\tabcolsep}{0pt}
\renewcommand{\arraystretch}{-4}
\caption{Final accuracy (\%) of BSR-Net-based models at 90\% and 99\% sparsity on SVHN with adversarial training objectives (TRADES). Our AGENT maintains or even improves the accuracy.}
\label{tb: end mul bsr}
\begin{center}
\addtolength{\tabcolsep}{-3.5pt}
\renewcommand{\arraystretch}{1}
\begin{small}
\begin{sc}
\begin{tabular}{lccc}
\toprule
& & BSR-Net & Ours \\
\midrule
\multirow{2}{*}{90\%} & VGG-16 & 89.4 (0.29) & \textbf{94.4 (0.25)} \\
~ & WRN-28-4 & 92.8 (0.24) & \textbf{95.5 (0.23)}\\
\midrule
\multirow{2}{*}{99\%} & VGG-16 & 86.4 (0.25) & \textbf{90.9 (0.26)}\\
~ & WRN-28-4 & 89.5 (0.22) & \textbf{92.2 (0.19)}  \\
\bottomrule
\end{tabular}
\end{sc}
\end{small}
\end{center}
\vspace{-0.3cm}
\end{wraptable}


We also compare our AGENT with SVRG~\citep{baker2019control}, a popular gradient correction method in the non-sparse case. 
The presented ITOP-based results are based on sparse (99\%) VGG-C and ResNet-34 on CIFAR-10. Figure \ref{fig: svrg itop} (a)-(b) show the testing accuracy of A-RigL-ITOP (blue), RigL-ITOP (pink), and RigL-ITOP+SVRG (green) at different epochs. We can see that the green curve for RigL-ITOP+SVRG is often lower than the other two curves for A-RigL-ITOP and RigL-ITOP, indicating that model convergence is slowed down by SVRG. As for the blue curve for our A-RigL-ITOP, it is always on the top of the pink curve for RigL-ITOP and also smoother than the green curve for RigL-ITOP+SVRG, indicating a successful acceleration and stabilization. 
The SET-ITOP-based results depicted in Figure \ref{fig: svrg itop} (c)-(d) show a similar pattern. The green curve (SET-ITOP+SVRG) is often lower than the blue (A-SET-ITOP) and pink (SET-ITOP) curves.
This demonstrates that SVRG does not work for sparse training, while our AGENT overcomes its limitations, leading to accelerated and stabilized sparse training.

\begin{figure}[!t]
\setlength{\abovecaptionskip}{-0.1cm}
\vspace{0.2cm}
\begin{center}
\subfigure[VGG-C]{\includegraphics[width=0.24\textwidth,height=0.2\textwidth]{figs/svrg_cifar10_vgg-c_0_99__gradient_magnitude.pdf}}
\subfigure[ResNet-34]{\includegraphics[width=0.24\textwidth,height=0.2\textwidth]{figs/svrg_cifar10_ResNet34_0_99__gradient_magnitude.pdf}}
\subfigure[VGG-C]{\includegraphics[width=0.24\textwidth,height=0.2\textwidth]{figs/svrg_cifar10_vgg-c_0_99__random_magnitude.pdf}}
\subfigure[ResNet-34]{\includegraphics[width=0.24\textwidth,height=0.2\textwidth]{figs/svrg_cifar10_ResNet34_0_99__random_magnitude.pdf}}
\caption{Testing accuracy for ITOP-based models at 99\% sparsity on CIFAR-10. SVRG (green curves) slows down the training compared to SGD (pink curves). Our AGENT (blue curves) accelerates the training.}
\label{fig: svrg itop}
\end{center}
\vspace{-0.4cm}
\end{figure}


\subsection{Comparison with Other Adaptive Gradient Methods}



We also compare our AGENT with other adaptive gradient methods, where we take Adam~\citep{kingma2014adam} as an example. As shown in Figure \ref{fig: adam}, AGENT-RigL-ITOP and AGENT-SET-ITOP (blue curves) are usually above Adam-RigL-ITOP and Adam-SET-ITOP (pink curves), indicating that our AGENT converges faster compared to Adam. This demonstrates the importance of using correlation in sparse training to balance old and new information.

\begin{figure}[!t]
\vspace{-0.2cm}
\begin{center}
\subfigure[VGG-C(RigL)]{\includegraphics[width=0.24\textwidth,height=0.2\textwidth]{figs/acc_adam_cifar10_vgg-c_0_99__gradient_magnitude.pdf}}
\subfigure[ResNet-34(RigL)]{\includegraphics[width=0.24\textwidth,height=0.2\textwidth]{figs/acc_adam_cifar10_ResNet34_0_99__gradient_magnitude.pdf}}
\subfigure[VGG-C(SET)]{\includegraphics[width=0.24\textwidth,height=0.2\textwidth]{figs/acc_adam_cifar10_vgg-c_0_99__random_magnitude.pdf}}
\subfigure[ResNet-34(SET)]{\includegraphics[width=0.24\textwidth,height=0.2\textwidth]{figs/acc_adam_cifar10_ResNet34_0_99__random_magnitude.pdf}}
\caption{Testing accuracy for ITOP-based models at 99\% sparsity on CIFAR-10. AGENT-based training (blue curves) converge faster than Adam-based training (pink curves).}
\label{fig: adam}
\end{center}
\vspace{-0.4cm}
\end{figure}


\subsection{Combination with Other Gradient Correction Methods}



In addition to working with SVRG, our AGENT can be combined with other gradient correction methods to achieve sparse training acceleration, such as the momentum-based variance reduction method (MVR)~\citep{cutkosky2019momentum}. We train 99\% SET-ITOP-based sparse VGG-C using MVR and MVR+AGENT, respectively. As shown in Table~\ref{tb: mvr}, MVR+AGENT usually achieves higher test accuracy than MVR for different number of training epochs (20, 40, 70, 90, 140, and 200), which demonstrates the acceleration effect of AGENT and the generality of our AGENT.










\subsection{Ablation Studies}






\linespread{1.1}
\begin{wraptable}{r}[0pt]{0.60\textwidth}
\vspace{-0.8cm}
\small
\addtolength{\tabcolsep}{0pt}
\renewcommand{\arraystretch}{-4}
\caption{Testing accuracy (\%) comparisons between MVR and AGENT+MVR. AGENT can accelerate MVR in sparse training.}
\label{tb: mvr}
\begin{center}
\addtolength{\tabcolsep}{-3.5pt}
\renewcommand{\arraystretch}{1}
\begin{small}
\begin{sc}
\begin{tabular}{ccccccc}
\toprule
 & 20-th	& 40-th	& 70-th	& 90-th	& 140-th & 200-th \\
\midrule
 MVR & 62.6 & 66.8 & 69.8 & 71.2 & 73.5 & 74.4 \\
 AGENT+MVR & \textbf{71.6} & \textbf{75.7} & \textbf{77.9} & \textbf{79.1} &	\textbf{82.3} & \textbf{82.3}
\\
\bottomrule
\end{tabular}
\end{sc}
\end{small}
\end{center}
\vspace{-0.6cm}
\end{wraptable}



We demonstrate the importance of each component in our method AGENT by removing them one by one and comparing the results.  
Specifically, we consider examining the contribution of the time-varying weight $c_t$ of the old gradients and the scaling parameter $\gamma$. The term "Fixed $c_t$" corresponds to fixing weight $c_t=0.1$ during training, and "No $\gamma$" represents a direct use of $\hat{c_t^*}$ in Eq.~(\ref{equ: c loss}) and the momentum scheme without adding the scaling parameter $\gamma$.


Table \ref{tb: vr-variants} shows the clean and robust accuracies of standard and adversarial (AT or TRADES) training at 90\% and 99\% sparsity on CIFAR-10 using VGG-16 under different number of training epoch budgets. In the adversarial training (AT and TRADES), we can see that "No $\gamma$" is poorly learned and has the worst results. While our method outperforms "Fix $c_t$" and "No $\gamma$" in almost all cases, especially in highly sparse tasks (i.e., 99\% sparsity). For standard training, "No $\gamma$" can learn some information, but still performs worse than the other two methods. For "Fix $c_t$", it provides similar convergence speed as our method, while ours tends to have a better final score.



From the above discussion, both the adaptive update of $c_t$ and the multiplication of the scaling parameter $\gamma$ are important for the acceleration. On the one hand, the traditional way of setting $c_t=1$ is not desirable in sparse training and can cause model divergence under sparsity constraints. Fixing it as a smaller value, such as 0.1, sometimes can work in standard training. But updating $c_t$ adaptively with loss-dependent information usually provides some benefits, such as a better final score. These benefits become more significant in sparse and adversarial training which are more challenging and of great value. On the other hand, we recommend adding a scaling parameter $\gamma$ (e.g., $\gamma=0.1$) to $c_t$ to avoid increasing the variance and reduce the potential bias in adversarial training, which helps the balance and further accelerates the convergence.







\linespread{1.2}
\begin{table*}[!t]
\vspace{-0.4cm}
\small
\addtolength{\tabcolsep}{0.5pt}
\renewcommand{\arraystretch}{0.85}
\caption{Ablation Studies: testing accuracy (\%) comparisons with Fixed $c$ and No $\gamma$ on sparse VGG-16. Results are presented as clean/robust accuracy (\%). For the same number of training epochs, our method has higher accuracy compared to Fixed $c$ and No $\gamma$ in almost all cases.}
\label{tb: vr-variants}
\begin{center}
\begin{small}
\begin{sc}
\begin{tabular}{llccccccc}
\toprule
& & \multicolumn{3}{c}{90\% Sparsity} & & \multicolumn{3}{c}{99\% Sparsity} \\
 \cline{3-5}   \cline{7-9} 
& & Fixed $c_t$ & No $\gamma$ & Ours & & Fixed $c_t$ & No $\gamma$ & Ours \\
\midrule
\multirow{6}{*}{\rotatebox{90}{AT}} & 20-th & 54.1/36.2 & 28.6/20.1 & \textbf{63.6}/\textbf{37.3} & & 10.0/10.0 & 10.0/10.0 & \textbf{56.4}/\textbf{31.4} \\
~ & 40-th & 58.9/37.1 & 20.4/13.0 & \textbf{64.9}/\textbf{37.9} & & 10.0/10.0 & 10.0/10.0 & \textbf{57.7}/\textbf{34.5} \\
~ & 70-th & 66.8/41.6 & 19.9/14.7 & \textbf{75.1}/\textbf{45.2} & & 10.0/10.0 & 10.0/10.0 & \textbf{66.0}/\textbf{39.4} \\
~ & 90-th & 67.7/43.3 & 21.8/15.6 & \textbf{74.1}/\textbf{44.8} & & 10.0/10.0 & 10.0/10.0 & \textbf{65.8}/\textbf{39.8} \\
~ & 140-th & 71.4/43.4 & 20.0/12.1 & \textbf{77.4}/\textbf{43.8} & & 10.0/10.0 & 10.0/10.0 & \textbf{69.8}/\textbf{41.2} \\
~ & 200-th & 71.7/43.0 & 20.5/9.5  & \textbf{78.1}/\textbf{44.6} & & 10.0/10.0 & 10.0/10.0 & \textbf{70.7}/\textbf{42.0} \\
\hline
\multirow{6}{*}{\rotatebox{90}{TRADES}} & 20-th & 62.6/35.2 & 38.5/21.8 & \textbf{65.0}/\textbf{37.6} & & 54.5/31.2 & 35.2/21.6 & \textbf{57.6}/\textbf{31.6} \\
~ & 40-th & 65.0/\textbf{38.0} & 34.7/20.2 & \textbf{66.0}/37.2 & & 56.0/30.5 & 21.5/10.0 & \textbf{58.4}/\textbf{33.4} \\
~ & 70-th & \textbf{73.9}/44.5 & 28.8/18.4 & 73.5/\textbf{45.4} & & 62.5/36.8 & 18.8/16.2 & \textbf{67.3}/\textbf{39.0} \\
~ & 90-th & \textbf{75.1}/44.4 & 25.8/15.9 & 73.6/\textbf{44.8} & & 63.9/37.4 & 16.9/15.9 & \textbf{67.5}/\textbf{39.1} \\
~ & 140-th & 76.7/\textbf{46.5} & 28.6/14.1 &  \textbf{76.8}/46.3 & & 65.5/39.0 & 19.7/14.4 & \textbf{69.9}/\textbf{41.5} \\
~ & 200-th & 76.8/46.1 & 30.7/12.7 & \textbf{77.0}/\textbf{46.2} & & 70.3/38.5 & 20.1/13.2 & \textbf{70.9}/\textbf{41.2} \\
\hline
\multirow{6}{*}{\rotatebox{90}{Standard}} & 20-th  & 80.9/0.0 & 70.6/0.0 & \textbf{81.8}/0.0 & & \textbf{73.7}/0.0 & 51.8/0.0 & 69.8/0.0 \\
~ & 40-th  & \textbf{83.3}/0.0 & 68.0/0.0 & 82.4/0.0 & & \textbf{74.9}/0.0 & 55.2/0.0 & 73.7/0.0 \\
~ & 70-th  & \textbf{90.2}/0.0 & 77.3/0.0 & 89.7/0.0 & & \textbf{84.1}/0.0 & 65.9/0.0 & 83.7/0.0 \\
~ & 90-th & \textbf{89.8}/0.0 & 77.8/0.0 & 89.3/0.0 & & 80.5/0.0 & 67.8/0.0 & \textbf{83.9}/0.0 \\
~ & 140-th & 92.4/0.0 & 80.7/0.0 & \textbf{92.5}/0.0 & & \textbf{87.2}/0.0 & 71.9/0.0 & 86.9/0.0 \\
~ & 200-th & 92.1/0.0 & 78.6/0.0 & \textbf{92.6}/0.0 & & 86.4/0.0 & 70.0/0.0 & \textbf{87.1}/0.0 \\
\bottomrule
\end{tabular}
\end{sc}
\end{small}
\end{center}
\vspace{-0.4cm}
\end{table*}

\subsection{Scaling Parameter Setting}

The scaling parameter $\gamma$ is to avoid introducing large variance due to error in approximating $c_t^*$ and bias due to the adversarial training. The choice of $\gamma$ is important and can be seen as a hyper-parameter tuning process. Our results are based on $\gamma=0.1$ and the best value for $\gamma$ depends on many factors such as the dataset, architecture, and sparsity. Therefore, if we tune the value of $\gamma$ according to the gradient correlation of different settings, it is possible to obtain a faster convergence rate than the reported results.

We check different values from 0 to 1 and find that it is generally better not to set $\gamma$ to close to 1 or 0. If setting $\gamma$ close to 1, we will not be able to completely avoid the increase in variance, which leads to performance drop, similar to "No $\gamma$" in Table~\ref{tb: vr-variants}. 
If $\gamma$ is set too small, such as 0.01, the weight of the old gradients will be too small and the old gradients will have limited influence on the model update, which will return to SGD's slowdown and training instability.
More detailed experimental results using different scaling parameters $\gamma$ are included in the Appendix~\ref{sub-sec scale}. 

\section{Limitations of Our Adaptive Gradient Correction Method}

\subsection{Extra FLOPs}

Similar to SVRG, our ADSVRG increases the training FLOPs in each iteration due to the extra forward and backward used to compute the old gradients.



However, the true computation difference can be smaller and the GPU-based runining time of SVRG will not be affected that much. For example, in the adversarial setting, we need additional computations to generate the adversarial samples, which is time-consuming and only needs to be done once in each iteration of our AVR and SGD. For BSR-Net, we empirically find that the ratio of time required for each iteration of our AVR and SGD is about 1.2.


There are also several methods to reduce the extra computation caused by SVRG. The first approach is to use the sparse gradients proposed by M Elibol (2020) \cite{elibol2020variance}. It can effectively reduce the computational cost of SVRG and can be easily applied to our method. The second approach is suggested by Allen-Zhu and Hazan (2016) \cite{allen2016variance}.  The extra cost on computing batch gradient on old model parameters is totally parallelizable. Thus, we can view SVRG as doubling the mini-batch size. Third, we can follow the idea of SAGA \cite{defazio2014saga} and store gradients for individual samples. By this way, we do not need the extra forward and backward step and save the computation. But it requires extra memory to store the gradients.


In the main manuscript, we choose to compare the convergence speed of our ADSVRG and SGD for the same number of pass data (epoch), which is widely used as a criterion to compare SVRG-based optimization and SGD~\citep{allen2016variance, chatterji2018theory, zou2018subsampled, cutkosky2019momentum}. A comparison in this way in this way can  demonstrate the accelerating effect of the optimization method and provide inspiration for future work.


\subsection{Scaling parameter tuning}

In our adaptive variance reduction method (AVR), we add an additional scaling parameter $\gamma$ which need to be adjusted. We find that setting $\gamma=0.1$ is a good choice for BSR-Net, RigL, and ITOP. However, it can be different for other different sparse training pipelines.





\subsection{Robust Accuracy Degradation}

For the final accuracy results of BSR-Net-based models, there is a small decrease in the robustness accuracy after using our AVR. It is still an open question how to further improve the robust accuracy when using adaptive variance reduction in sparse and adversarial training.
\section{Sparse Training Method Description}
\subsection{Bayesian Sparse Robust Training}

Bayesian Sparse Robust Training (BSR-Net) \cite{ozdenizci2021training} is a Bayesian Sparse and Robust training pipeline. Based on a Bayesian posterior sampling principle, a network rewiring process simultaneously learns the sparse connectivity structure and the robustness-accuracy trade-off based on the adversarial learning objective. More specifically, regarding its mask update, it prunes all negative weights and grows new weights randomly.
\section{Discussion and Conclusion}
We develop an adaptive gradient correction (AGENT) method for sparse training to achieve the time efficiency and reduce training instability from an optimization perspective, which can be incorporated into any SGD-based sparse training pipeline and work in both standard and adversarial setups. 
To achieve a fine-grained control over the balance of current and previous gradients, we use loss information to analyze gradient changes, and add an adaptive weight to the old gradients.
In addition, we design a scaling parameter to reduce the bias of the gradient estimator introduced by the adversarial samples and improve the worst case of the adaptive weight estimate. 
In theory, we show that our AGENT can accelerate the convergence rate of sparse training.
Experiment results on multiple datasets, model architectures, and sparsities demonstrate that our method outperforms state-of-the-art sparse training methods in terms of accuracy by up to \textbf{5.0\%} and reduces the number of training epochs by up to \textbf{52.1\%} for the same accuracy achieved.


A number of methods can be employed to reduce the FLOPs in our AGENT. Similar to SVRG, our AGENT increases the training FLOPs in each iteration due to the extra forward and backward used to compute the old gradients.
To reduce the FLOPs, the first method is to use sparse gradients~\citep{elibol2020variance}, which effectively reduces the cost of backward in sparse training and can be easily applied to our method. The second method is parallel computing~\citet{allen2016variance}. Since the additional forward and backward over the old model parameters are fully parallelizable, we can view it as doubling the mini-batch size. Third, we can follow the idea of SAGA~\citep{defazio2014saga} by storing gradients for each single sample. By this way, we do not need extra forward and backward steps, saving the computation. However, it requires extra memory to store the gradients.
\section{Preliminaries: Stochastic Variance Reduced Gradient}



Stochastic variance reduced gradient (SVRG)~\citep{johnson2013accelerating, allen2016variance, dubey2016variance} is a widely-used gradient correction method designed to obtain more accurate gradient estimates, which has been followed by many studies~\citep{zou2018subsampled, baker2019control, chen2019convergence}. Specifically, after each epoch of training, we evaluate the full gradients $\widetilde{{\bm{g}}}$
based on $\widetilde{\bm{\theta}}$ at that time and store them for later use. In the next epoch, the batch gradient estimate on $\textbf{B}_t$ is updated using the stored old gradients via Eq.~(\ref{equ: svrg-ld})
\begin{equation}
\label{equ: svrg-ld}
    \hat{{\bm{g}}}(\bm{\theta}_t)
        = \frac{1}{n}\sum_{i\in \textbf{B}_t}\bigg{(}{\bm{g}}_i(\bm{\theta}_t)-  {\bm{g}}_i(\widetilde{\bm{\theta}})\bigg{)} + \widetilde{{\bm{g}}}
\end{equation}
where ${\bm{g}}_i(\bm{\theta}_t)=\nabla G(\textbf{x}_i|\bm{\theta}_t)$, $G(\bm{\theta}_t) = (\sum_{i = 1}^N G(\textbf{x}_i|\bm{\theta}_t))/N$ is the loss function, $\widetilde{{\bm{g}}}=\nabla G(\widetilde{\bm{\theta}})$, $\bm{\theta}_t$ is the current parameters, $n$ is the number of samples in each mini-batch data, and $N$ is the total number of samples.
SVRG successfully accelerates many training tasks in the non-sparse case, but does not work well in sparse training, which is similar to many other gradient correction methods.





\section{Related Work}

\subsection{Sparse Training}

Interest in sparse DNNs has been on the rise recently, especially when dealing with resource constraints. The goal is to achieve comparable performance with sparse weights to satisfy the constraints. 
Different sparse training methods have emerged, where sparse weights are maintained in the training process.
Various pruning and growth criteria  are proposed, such as weight/gradient magnitude, random selection, and weight sign~\citep{mocanu2018scalable, bellec2018deep, frankle2019lottery, mostafa2019parameter, dettmers2019sparse, evci2020rigging, jayakumar2020top, liu2021we, ozdenizci2021training, zhou2021effective, schwarz2021powerpropagation, huang2022dynamic, liu2022comprehensive}.





However, the aforementioned studies focus on improving the performance of sparse training, while neglecting the side effect of sparse training. Sparsity not only increases gradient variance, thus delaying convergence~\citep{hoefler2021sparsity, graesser2022state}, but also leads to training instability~\citep{bartoldson2020generalization}. It is a challenge to achieve both space and time efficiency. 
Additionally, sparse training can also exacerbate models' vulnerability to adversarial samples, which is one of the weaknesses of DNNs~\citep{ozdenizci2021training}. When the model encounters intentionally manipulated data, its performances may deteriorate rapidly, leading to increasing security concerns~\cite{rakin2019robust, akhtar2018threat}. 
In this paper, we focus on sparse training. In general, our method can be applied to any SGD-based sparse training pipelines.

\subsection{Accelerating Training}

Studies have been conducted in recent years on how to achieve time efficiency in DNNs, and one popular direction is to obtain a more accurate gradient estimate to update the model~\citep{gorbunov2020unified}, such as variance reduction. SGD is the most common training method, where one uses small batches of data to approach the full gradient. In standard training, the batch estimator is unbiased, but can have a large variance and misguide the model, leading to studies on variance reduction~\citep{johnson2013accelerating, xiao2014proximal, shang2018vr, zou2018subsampled,chen2019convergence, gorbunov2020unified}. While adversarial training brings bias in the gradient estimation~\citep{li2020implicit}, and we need to face the bias-variance tradeoff when doing gradient correction.
A shared idea is to balance the gradient noise with a less-noisy old gradient~\citep{nguyen2017sarah, fang2018spider, chen2019convergence}. Some other momentum-based methods have a similar strategy of using old information~\citep{ cutkosky2019momentum, chayti2022optimization} However, all the above work considers only the acceleration in non-sparse case.


Acceleration is more challenging in sparse training, and previous research on it has focused on structured sparse training~\citep{hubara2021accelerated, chen2021pixelated, zhou2021efficient}. First, sparse training will induce larger variance~\citep{hoefler2021sparsity}. In addition, some key assumptions associated with gradient correction methods do not hold under sparsity constraint. In the non-sparse case, the old and new gradients are assumed to be highly correlated, so we can collect a large amount of knowledge from the old gradients~\citep{chen2019convergence, chatterji2018theory, dubey2016variance}. 
However, sparsity tends to lead to lower correlations, and this irrelevant information can be harmful, making previous methods no longer applicable to sparse training and requiring a finer balance between new and old gradients.
Furthermore, the structured sparsity pattern is not flexible enough, which can lead to lower model accuracy.
In contrast, our method accelerates sparse training from an optimization perspective and is compatible with both unstructured and structured sparse training pipelines.








\section{Theoretical Justification}


Theoretically, we provide a convergence analysis for our AGENT and compare it to SVRG~\citep{reddi2016stochastic}. We use $G(.)$ to denote the loss function and ${\bm{g}}$ to denote the gradient. Our proof is based on Assumptions~\ref{assup:lsmooth}-\ref{assup:sigma-b}, and detailed derivation is included in Appendix~\ref{appendix:proof}.

\begin{assumption}
(L-smooth): The differentiable loss function $ G: \mathbb{R}^n \rightarrow \mathbb{R}$ is L-smooth, i.e., for all ${\bm{x}},{\bm{y}} \in \mathbb{R}^n$ is satisfies $|| \nabla G({\bm{x}}) - \nabla G({\bm{y}}) || \leq L||{\bm{x}} - {\bm{y}}||$. And an equivalent definition is for. all ${\bm{x}}, {\bm{y}} \in \mathbb{R}^n$:
\begin{equation}
\begin{split}
\label{equ:acc-l}
    -\frac{L}{2}||{\bm{x}}-{\bm{y}}||^2 \leq G(x) - G(y) - \langle \nabla G({\bm{x}}), {\bm{x}} - {\bm{y}}
    \rangle  \leq \frac{L}{2}||{\bm{x}}-{\bm{y}}||^2 \nonumber
\end{split}
\end{equation}
\label{assup:lsmooth}
\end{assumption}

\begin{assumption}
\label{assup:sigma-b}($\sigma$-bounded): 
The loss function $G$ has a $\sigma$-bounded gradient, i.e., $|| \nabla G_{i}({\bm{x}})|| \leq \sigma $ for all $i \in \left[ N \right]$ and ${\bm{x}} \in \mathbb{R}^n$.
\end{assumption}

\textbf{Our convergence analysis framework} outlines four steps:
\begin{itemize}[leftmargin=*]
    \item We first show that an appropriate choice of $c_t$ will result in smaller variance in our gradient estimates compared to SVRG
    \item Next, we show the convergence rate of one arbitrary training epoch.
   
    \item We then extend the one-epoch results and analyze the convergence rate for the whole epoch.
    \item After obtaining the convergence rate, we bring it to the real case of sparse learning and find that our method indeed yields a tighter bound.   
\end{itemize}


Given Assumptions~\ref{assup:lsmooth}-\ref{assup:sigma-b}, we follow the analysis framework above and establish Theorem~\ref{theo1} to show the convergence rate of our AGENT:
\begin{theorem}
\label{theo1}
Under Assumptions~\ref{assup:lsmooth}-\ref{assup:sigma-b}, with proper choice of step size $\eta_t$ and $c_t$,
the gradient $\mathbb{E} [|| g(\bm{\theta_{\pi}})||^2]$ using AGENT after $T$ training epochs can be bounded by:
\begin{align}
\begin{split}
 \mathbb{E} [|| g(\bm{\theta_{\pi}})||^2] \leq \frac{(G(\bm{\theta}_0)- G(\bm{\theta}_{*})) L N^\alpha}{T n \nu } + \frac{2 \kappa \mu^2 \sigma^2}{ N^\alpha m \nu } \nonumber
\end{split}    
\end{align}
where $\bm{\theta}_{\pi}$ is sampled uniformly from $\{\{\bm{\theta}_{t}^s\}_{t=0}^{m-1}\}_{s=0}^{T-1}$, 
$N$ denotes the data size, $n$ denotes the mini-batch size, $m$ denotes the epoch length, $\bm{\theta}_ 0$ is the initial point and $\bm{\theta}_{*}$ is the optimal solution, $\nu, \mu, \kappa, \alpha > 0$ are constants depending on $\eta_t$ and $c_t$, $N$ and $n$.
\end{theorem}
In regard to Theorem~\ref{theo1}, we make the following remarks to justify the acceleration from our AGENT:

\begin{remark}(Faster Gradient Change Speed)
An influential difference between sparse and dense training is the gradient change speed, which is reflected in Assumption~\ref{assup:lsmooth} (L-smooth).  Typically, $L$ in sparse training will be larger than $L$ in dense training. 
\end{remark}

\begin{remark}(First Term Analysis)
In Theorem~\ref{theo1}, the first term in the bound of our AGENT measures the error introduced by deviations from the optimal parameters, which goes to zero when the number of epochs $T$ reaches infinity. However, in real sparse training applications, $T$ is finite and this term is expanded due to the increase of $L$ in sparse training, which implies that the optimization under sparse constraints is more challenging.


\end{remark}

\begin{remark}(Second Term Analysis)
In Theorem~\ref{theo1}, the second term measures the error introduced by the noisy gradient and the finite data during the optimization.
Since $\sigma^2$ is relatively small and $N$ is usually large in our DNNs training, the second term is negligible or much smaller compared to the first term when $T$ is assumed to be finite.
\end{remark}


From the above analysis, we can compare the bounds of AGENT and SVRG and find that in the case of sparse training, an appropriate choice of $c_t$ can make the bound for our AGENT tighter than the bound for SVRG by well-corrected gradients.

\begin{remark}
(Comparison with SVRG) Under Assumptions~\ref{assup:lsmooth}-\ref{assup:sigma-b}, the gradient $\mathbb{E} [|| g(\bm{\theta_{\pi}})||^2]$ using SVRG after $T$ training epochs can be bounded by~\citep{reddi2016stochastic}:
\begin{align*}
    \mathbb{E} [|| g(\bm{\theta_{\pi}})||^2] \leq \frac{(G(\bm{\theta}_0)- G(\bm{\theta}_{*})) L N^\alpha}{T n \nu^* }.
\end{align*}
This bound is of a similar form to the first term in Theorem~\ref{theo1}. Since the second term of Theorem~\ref{theo1} is negligible or much smaller than the first one, we only need to compare the first term.
With a proper choice of $c_t$, the variance of $\hat{{\bm{g}}}({\bm{\theta}}_t)$ will decrease, which leads to a smaller $\nu$ for AGENT than $\nu^*$ for SVRG (detailed proof is included in Appendix A Remark~\ref{sub-remark: mu small}).
Thus, AGENT can bring a smaller first term compared to SVRG, which indicates that AGENT effectively reduces the error due to the deviations and has a tighter bound compared to SVRG.
\end{remark}






