# Stochastic Gradient Variance Reduction
by Solving a Filtering Problem

Xingyi Yang  School of Electrical and Computer Engineering
University of California, San Diego
9500 Gilman Dr, La Jolla, CA 92093
Email<EMAIL_ADDRESS>
###### Abstract

Deep neural networks (DNN) are typically optimized using stochastic gradient
descent (SGD). However, the estimation of the gradient using stochastic
samples tends to be noisy and unreliable, resulting in large gradient variance
and bad convergence. In this paper, we propose Filter Gradient Decent (FGD),
an efficient stochastic optimization algorithm that makes the consistent
estimation of the local gradient by solving an adaptive filtering problem with
different design of filters. Our method reduces variance in stochastic
gradient descent by incorporating the historical states to enhance the current
estimation. It is able to correct noisy gradient direction as well as to
accelerate the convergence of learning. We demonstrate the effectiveness of
the proposed Filter Gradient Descent on numerical optimization and training
neural networks, where it achieves superior and robust performance compared
with traditional momentum-based methods. To the best of our knowledge, we are
the first to provide a practical solution that integrates filtering into
gradient estimation by making the analogy between gradient estimation and
filtering problem in signal processing. 111The code is provided in
https://github.com/Adamdad/Filter-Gradient-Decent

##  I Introduction

Among common techniques to solve the optimization problem, stochastic gradient
descent (SGD) is one of the most common practice nowadays. It aims to minimize
the an objective function $J(\bm{\theta}_{t};\cdot)$ by taking the gradient
computed from the randomly sampled data iteratively. Consider training a
parametric model $f(\cdot;\bm{\theta})$ parameterized by
$\bm{\theta}\in\mathbb{R}^{d}$ over a finite set of training data
$\mathcal{D}=\\{(\mathbf{x}_{i},y_{i})\\}_{i=1}^{N}$. At iteration $t$, a
subset of the dataset $\mathcal{D}_{t}\subseteq\mathcal{D}$ is randomly
sampled. Denote
$\bm{g}_{t}=\nabla_{\bm{\theta}}J(\bm{\theta}_{t};\mathcal{D}_{t})$ as the
observed gradient, we minimize the objective by updating the weight
$\bm{\theta}$ in the down-hill direction

$\bm{\theta}_{t+1}=\bm{\theta}_{t}-\eta\bm{g}_{t}$ (1)

The learning rate $\eta$ determines the stepsize heading to the minimum.

A critical problem of SGD is that it is highly “greedy”. On the one hand, the
sampled data points $\mathcal{D}_{t}$ might not well represent the overall
data statistics, e.g. class-biased and noise-corrupted, which leads to
undesirable error for the gradient estimation. Meanwhile, the stochastic
gradient only considers local information for the error surface, therefore
might spend much time bouncing around ravines with poorly conditioned Hessian
matrix. Consequently, the estimated gradient has a large variance [1], leading
to slower convergence and worse performance. This phenomenon is most severe
for the non-smooth and non-convex optimization problems, like training deep
neural networks. Existing problems in stochastic gradient descent forces us to
think about how to alleviate the randomness in gradient calculation and solve
the problem of poor convergence.

In the theory of stochastic processes, the filtering problem is a model for
state estimation problems to establish a “best estimate” for the true value of
some system from an incomplete, potentially noisy set of observations on that
system. This is closely related to our problem: Given observations
$\\{\bm{g}_{i}\\}$ for $0\leq i\leq t$, what is the best estimate
$\hat{\bm{g}}_{t|t}$ of the true state $\hat{\bm{g}}_{t}$ of the system based
on those observations?

Figure 1: Illustration of Filter Gradient Decent (FGD) for a non-convex
optimization problem. Using common filtering techniques to “denoise” the
gradient observation, FGD is able to reduce the variance of the gradient as
well as to get rid of the local minimum in SGD.

Inspired by the successful application for filters in signal denoising and
reconstruction, we introduce a general framework called Filter Gradient Decent
(FGD), a remedy to the noisy gradient with the filters to reduce variance and
make consistent estimation of gradient in stochastic optimization. It takes
the stochastic gradient as a special signal and solving the filtering problem
or denoising problem to estimate the true gradient direction under the noisy
observations. As a simple illustration in Figure 1, FGD is able to reduce the
variance of the gradient as well as to get rid of the local minimum in SGD.
This general framework can be applied to any filtering techniques.

Our contributions are summarized as follows:

  * •

We propose Filter Gradient Decent (FGD), which incorporates signal filtering
into stochastic gradient descent to reduce the noise and randomness of
gradient estimation.

  * •

We show that our framework can be applied to any filters. In this paper, we
compare four kinds of filters including (1) Moving-average (MA) filter (2)
Autoregressive (AR) filter (3) Kalman filter (4) Wavelet filter.

  * •

Experiments verify that Filter Gradient Decent is effective in gradient
variance reduction and finding the global minimum for non-convex optimization
problem.

  * •

We train deep neural networks with Filter Gradient Decent under various
datasets, which demonstrates superior performance and fast convergence.

##  II Background

###  II-A Stochastic Gradient Descent

Stochastic gradient descent (SGD) is a way to minimize an objective function
by updating the parameters in the opposite direction of the gradient. Vanilla
SGD, however, does not guarantee good convergence, either suffering from the
large variance of the gradient or trapped in suboptimal local minima. Momentum
[2] helps accelerate SGD by adding a ratio of $\gamma$ of the update vector of
the past time step to the current update vector. It also reduces the gradient
variance by keeping a running average of past observations. Adagrad [3] uses a
different learning rate for every parameter $\theta_{i}$ at every time step
$t$. Adadelta [4] and RMSprop [5] are two extensions of Adagrad that seeks to
restrict its aggressive learning rate. Adaptive Moment Estimation (Adam)[6]
incorporates adaptive learning rates with a decaying average of past gradients
similar to momentum. Later variants like AdaMax[6] and Nadam‘[7] incrementally
extends the framework of Adam.

###  II-B Variance Reduction in Gradient Descent

SGD uses the noisy gradient estimated from random data samples. This method
introduces a large variance to gradient estimation, which is harmful to the
model in terms of convergence. Apparently, averaging is a simple yet off-the-
shelf solution. Averaged Stochastic Gradient Descent (ASGD) [8] is the
simplest method of variance reduction by keeping an average of some set of the
weight vectors. Stochastic Averaged Gradient (SAG) [9] builds on the ASGD
method by keeping a moving average of $n$ past gradients for updates. [1]
builds a variance reduction technique, which makes use of control variates to
augment the noisy gradient and thereby reduce its variance. [10] proposes to
control the variance of the reparameterization gradient estimator in Monte
Carlo variational inference (MCVI).

Averaging is equivalent to a simple lowpass filter in signal processing. It
removes the high frequency component as well as the noise in signals. Our FGD
is partially inspired by the averaging techniques: If an average lowpass
filter works for gradient variance reduction, sophisticated filters may work
better.

###  II-C Filters

In signal processing, a filter is a device or process that removes some
unwanted components or features from a signal. We introduce four types of
filters used in this paper and their basic concepts.
Moving-average Filter. In time series analysis, the moving-average (MA) model
specifies that the output variable depends linearly on the current and various
past values of a stochastic term. $MA(q)$ refers to the moving average model
of order q, where the output $\mathbf{y}_{t}$ is a weighted linear combination
of $\mathbf{x}_{t}$ and $q$ past input
$\\{\mathbf{x}_{t-1},\dots,\mathbf{x}_{t-p}\\}$

$\mathbf{y}_{t}=\mathbf{x}_{t}+\sum_{i=1}^{q}a_{i}\mathbf{x}_{t-i}$ (2)

Autoregressive Filter. An autoregressive (AR) model is a type of random
process that the output variable depends linearly on its own previous values
and on a stochastic term. $AR(p)$ indicates an autoregressive model of order
p, where the output $\mathbf{y}_{t}$ is a weighted linear combination of input
$\mathbf{x}_{t}$ and $p$ past output value
$\\{\mathbf{y}_{t-1},\dots,\mathbf{y}_{t-p}\\}$

$\mathbf{y}_{t}=\mathbf{x}_{t}+\sum_{i=1}^{p}b_{i}\mathbf{y}_{t-i}$ (3)

Kalman Filter. The Kalman filter [11] addresses the general problem of trying
to estimate the state $\mathbf{x}\in\mathbb{R}^{n}$ of a discrete-time
controlled process that is governed by the linear stochastic difference
equation with a measurement $\mathbf{y}\in\mathbb{R}^{m}$

$\mathbf{x}_{t}=\mathbf{F}_{t-1}\mathbf{x}_{t-1}+\mathbf{I}_{t-1}\mathbf{u}_{t}+\mathbf{w}_{t-1},\quad\mathbf{y}_{t}=\mathbf{C}_{t-1}\mathbf{x}_{t}+\mathbf{v}_{t}$
(4)

$\mathbf{F}_{t}\in\mathbb{R}^{n\times n}$ is the state transition matrix which
relates the state to the previous step, $\mathbf{I}_{t}\in\mathbb{R}^{n\times
k}$ is the control matrix that relates the optional control input
$\mathbf{u}\in\mathbb{R}^{k}$ to current state, and
$\mathbf{C}_{t}\in\mathbb{R}^{m\times n}$ is measurement matrix. The random
variables $\mathbf{w}_{t}\sim\mathcal{N}(0,Q)$ and
$\mathbf{v}_{t}\sim\mathcal{N}(0,R)$ represent the process and measurement
noise respectively. They are assumed to be independent of each other, white,
and with normal probability distributions.

The Kalman filter solves the problem in two steps: the prediction step, where
the next state of the system is predicted given the previous measurements, and
the update step, where the current state of the system is estimated given the
measurement at that time step. The steps translate to equations as follows

  * •

Prediction Step

$\displaystyle\hat{\mathbf{x}}_{t|t-1}=\mathbf{F}_{t-1}\mathbf{x}_{t-1}+\mathbf{I}_{t}\mathbf{u}_{t}$
(5)
$\displaystyle\hat{\mathbf{P}}_{t|t-1}=\mathbf{F}_{t-1}\mathbf{P}_{t-1|t-1}\mathbf{F}_{t-1}^{T}+Q$
(6)

  * •

Update Step

$\displaystyle\hat{\mathbf{y}}_{t}=\mathbf{y}_{t}-\mathbf{C}\hat{\mathbf{x}}_{t|t-1}$
(7)
$\displaystyle\mathbf{K}_{t}=\hat{\mathbf{P}}_{t|t-1}\mathbf{C}^{T}(\mathbf{C}\hat{\mathbf{P}}_{t|t-1}\mathbf{C}^{T}+R)^{-1}$
(8)
$\displaystyle\hat{\mathbf{x}}_{t|t}=\hat{\mathbf{x}}_{t|t-1}+\mathbf{K}_{t}\hat{\mathbf{y}}_{t}$
(9)
$\displaystyle\mathbf{P}_{t|t}=(\mathbf{I}-\mathbf{K}_{t}\mathbf{C})\hat{\mathbf{P}}_{t|t-1}$
(10)

Wavelet Filter. A wavelet is a mathematical function used to divide a given
function or continuous-time signal into different scale components. A wavelet
transform is the representation of a function by wavelets. By shifting and
scaling a mother wavelet function $\Psi(t)$, any function $f(t)$ can
decomposed into cofficents with multi-resolution wavelets

$\Psi_{a,b}(t)=\frac{1}{\sqrt{b}}\Psi(\frac{t-a}{b}),\gamma_{a,b}=\int
f(t)\Psi_{a,b}(t)dt$ (11)

where $a$ and $b$ are translation and scaling coefficients, $\gamma_{a,b}$ is
the wavelet coefficients correspond to wavelet $\Psi_{a,b}(t)$. A discrete
wavelet transform (DWT) is any wavelet transform for which the wavelets are
discretely sampled. There are three basic steps to filtering signals using
wavelets. (1) Decompose the signal using the DWT.

$\Psi_{j,k}(t)=\frac{1}{\sqrt{2^{j}}}\Psi(\frac{t-k2^{j}}{2^{j}}),\gamma_{j,k}=\sum_{t}f(t)\Psi_{j,k}(t)$
(12)

(2) Filter the signal in the wavelet space using thresholding operation $T$.

$\gamma^{\prime}_{j,k}=T(\gamma_{j,k})$ (13)

(3) Invert the filtered wavelet coefficients to reconstruct the filtered
signal using the inverse DWT.

$f^{\prime}(t)=\sum_{i}\sum_{k}\gamma^{\prime}_{j,k}\Psi_{j,k}(t)$ (14)

The filtering of signals using wavelets is based on the idea that as the DWT
decomposes the signal into details and approximation parts. At some scale the
details contain mostly the insignificant noise and can be removed or zeroed
out using thresholding without affecting the signal.

Figure 2: Pipeline for Wavelet Gradient Filtering for Gradient Decent. (1)
Forward DWT to get multi-resolution representation of the gradients (2)
Thresholding and amplification on wavelet domain (3) Inverse DWT to spatial
domain.

##  III Gradient Estimation with a Filtering Problem

In this paper, we make a bold analogy between gradient and high-dimensional
signal and reliably estimate gradient by solving a filtering problem. Given
the current and past noisy gradient observation $\\{\bm{g}_{i}\\}_{i=0}^{t}$,
we estimate the true state of the current gradient $\hat{\bm{g}}_{t|t}$ using
filter $F$

$\hat{\bm{g}}_{t|t}=F(\bm{g}_{t},\bm{g}_{t-1},\dots,\bm{g}_{0})$ (15)

The estimated gradient then is utilized to update the model weight
$\bm{\theta}$ via Equation 1. Algorithm 1 shows the overall framework of
Filter Gradient Decent.

Result: Network Parameter $\bm{\theta}$

Initialize the Network Parameter with $\bm{\theta}_{0}$ and Filter $F$ with
parameter $\Gamma$;

for  _$t=0,\dots,T-1$_ do

Compute Gradient:

$\bm{g}_{t}=\nabla_{\bm{\theta}}J(\bm{\theta}_{t};\mathcal{D}_{t})$;

Filtering Step:

$\hat{\bm{g}}_{t|t}=F(\bm{g}_{t},\bm{g}_{t-1},\dots,\bm{g}_{0})$;

Gradient Descent:

$\bm{\theta}_{t+1}=\bm{\theta}_{t}-\eta\hat{\bm{g}}_{t|t}$;

end for

Algorithm 1 Filter Gradient Decent

The different filter selection models the various parametric dependencies
between the true state and the gradient computed from randomly sampled data.
It works as a low-pass filter that removes the high-frequency components
(randomness and noise) in the gradient observations and enhances the low-
frequency components (consistent direction of the gradient). Gradient
estimation with filter gets rid of the drawbacks of local gradient and data
randomness by considering the historical states of the gradient, thus become
more consistent and robust. We select four well-known filters (1) MA filter
(2) AR filter (3) Kalman filter and (4) Wavelet filter as $F$ and would like
to study how different filters affect the gradient estimation.

###  III-A Solution 1: Moving-average for Gradient Decent

When assuming that the observed and true gradients follow a moving-average
model, we can approximate the true gradient $\hat{\bm{g}}_{t|t}$ using an
$MA(q)$ model

$\displaystyle\hat{\bm{g}}_{t|t}=\bm{g}_{t}+\sum_{i=1}^{q}a_{i}\bm{g}_{t-i}$

$\\{\bm{g}_{t-i}\\}_{i=1}^{q}$ is $q$ past stochastic gradients and $a_{i}$ is
the weight for historical gradient $\bm{g}_{t-i}$. We call this method Filter
Gradient Decent with Moving-average filter (FGD-MA). In the following paper,
we call the FGD-MA model with order $q$ as FGD-MA(q). It keep a weighted
averaging of $q$ past gradient observations.

###  III-B Solution 2: Autoregresive for Gradient Decent

When the autoregressive model best describes the relation between the observed
and true gradients, we may also estimate the true gradient
$\hat{\bm{g}}_{t|t}$ using an $AR(p)$ model

$\displaystyle\hat{\bm{g}}_{t|t}=\bm{g}_{t}+\sum_{i=1}^{p}b_{i}\hat{\bm{g}}_{t-i|t-i}$

The $b_{i}$ is the weight corresponds to historical gradient estimation
$\hat{\bm{g}}_{t-i|t-i}$. We call this model Filter Gradient Decent with
Autoregresive filter (FGD-AR). Interestingly, FGD-AR with order 1 turns out to
be the momentum method that is commonly used in stochastic gradient decent

$\displaystyle\bm{v}_{t}=\bm{g}_{t}+\gamma\bm{v}_{t-1}$

This shows that the momentum method is one special case for FGD-AR. FGD-AR
extends the current momentum term to allow longer time dependency for gradient
estimation. In the following paper, we call the FGD-AR model with order $p$ as
FGD-AR(p). We also call momentum method as FGD-AR(1).

###  III-C Solution 3: Kalman filter for Gradient Decent

To reduce the variance of the gradient, we adopt a Kalman filter to estimate
the true state of gradient upon a filtering problem. We assume the gradient
follows a linear scholastic model

$\begin{split}\hat{\bm{g}}_{t}=\mathbf{F}_{t-1}\hat{\bm{g}}_{t-1}+\mathbf{w}_{t-1},\quad\bm{g}_{t}=\mathbf{C}_{t-1}\hat{\bm{g}}_{t}+\mathbf{v}_{t-1}\end{split}$
(16)

where $\bm{g}_{t}$ is the observed gradient and $\hat{g}_{t}$ refers to real
gradient. We adopt the Kalman filter to give the minimum mean-square estimate
of real gradient $\hat{\bm{g}}_{t|t}$ given previous state
$\hat{\bm{g}}_{t-1|t-1}$ and observation $\bm{g}_{t}$ at time $t$.

$\hat{\bm{g}}_{t|t}=KF(\bm{g}_{t},\hat{\bm{g}}_{t-1|t-1})$ (17)

By assuming that the gradient for each parameter is independent, we need to
maintain a Kalman filter for each parameter. To reduce the computational
burden, we simplified our method to a scalar Kalmen filter:
$\mathbf{F}_{t}=\gamma I$, $\mathbf{C}_{t}=cI$, $Q=\sigma_{Q}^{2}I$,
$R=\sigma_{R}^{2}I$, $\mathbf{P}_{0}=p_{0}I$, where $I$ is the identity
matrix. This design cancels the time-consuming matrix multiplication, with
only a scalar Kalman filter per parameter. We call this model Filter Gradient
Descent with Kalman filter (FGD-K).

###  III-D Solution 4: Wavelet Gradient Decent

Wavelet Filtering is widely adopted in signal processing to remove certain
frequency components of the signal. In order to better eliminate gradient
noise, we consider the multi-resolution wavelet filter that soft-thresholds
highpass coefficients at each level. We also intend to boost the low-frequency
component of the gradient by amplifying the lowpass coefficient by a hyper-
parameter of $\alpha$. Figure 2 explains the overall pipeline for our proposed
Filter Gradient Descent with Wavelet filter (FGD-W). The procedure can be
summarized into three steps

  * •

Forward DWT We first apply K-level wavelet transformation for $L$ historical
gradients to get multi-resolution representation of the gradient

$(\bm{L}_{K},\bm{H}_{K},\dots,\bm{H}_{0})=DWT(\bm{g}_{t},\dots,\bm{g}_{t-L+1})$
(18)

$\bm{L}_{i}$ and $\bm{H}_{i}$ are the lowpass and highpass coefficient vectors
at level $i$. Particularly, we assume independence for different elements of
the gradient and maintain a 1D DWT for each parameter. In terms of
implementation, we keep a $L$-length queue for each parameter to store $L$
historical gradient observations. Every time a new gradient $\bm{g}_{t}$ is
computed, it is pushed in the queue while $\bm{g}_{t-L}$ is popped out.

  * •

Filter in wavelet domain Soft-thresholding is performed on all highpass
components $\bm{H}_{i}$ at each level with operation $T$ and amplify the
lowpass band by a coefficient of $\alpha\geq 1$

$\bm{H}^{\prime}_{i}=T(\bm{H}_{i}),\quad\bm{L}^{\prime}_{K}=\alpha\bm{L}_{K}$
(19)

where $\bm{H}^{\prime}_{i}$ and $\bm{L}^{\prime}_{K}$ is the filtered highpass
and low pass coefficients in wavelets domain. For simplicity, we adopt the
same threshold on all levels.

  * •

Inverse DWT The filtered coefficients in wavelet domain are converted back to
spatial domain using inverse DWT

$\displaystyle\bm{g}_{t|t},\dots,\bm{g}_{t-L+1|t}=IDWT(\bm{L}^{\prime}_{K},\bm{H}^{\prime}_{K},\dots,\bm{H}^{\prime}_{0})$

(a) Function Value surface with contour

(b) Learning rate 0.01

(c) Learning rate 0.03

(d) $f(x,y)$, learning rate 0.01

(e) $f(x,y)$, learning rate 0.03

(f) $|\nabla_{x}f(x,y)|^{2}$, learning rate 0.01

(g) $|\nabla_{x}f(x,y)|^{2}$, learning rate 0.03

(h) $|\nabla_{y}f(x,y)|^{2}$, learning rate 0.01

(i) $|\nabla_{y}f(x,y)|^{2}$, learning rate 0.03

Figure 3: Plot of Value surface of $f(x,y)$ with contour, the function value,
gradient variance for non-convex function minimization

(a) Batch-size 64, learning rate 0.001 (b) Batch-size 64, learning rate 0.01
(c) Batch-size 64, learning rate 0.1 (d) Batch-size 16, learning rate 0.001
(e) Batch-size 16, learning rate 0.01 (f) Batch-size 16, learning rate 0.1 (g)
Batch-size 4, learning rate 0.001 (h) Batch-size 4, learning rate 0.01 (i)
Batch-size 4, learning rate 0.1

Figure 4: Training loss on MNIST with MLP(x-axis: iteration; y-axis: loss)

##  IV Experiment

To empirically evaluate the proposed method, we first show a numerical problem
for non-convex optimization. We also investigated its performance in
optimizing different popular machine learning models, including multi-layer
fully connected neural networks and deep convolutional neural networks. Using
various models and datasets, we demonstrate FGD with various filter designs
can efficiently solve the numerical optimization and image classification
problems.

TABLE I: Test Accuracy on MNIST with MLP with different hyper-parameter setting Setting | Adam | FGD-K | FGD-W | SGD | FGD-AR(1) | FGD-AR(2) | FGD-MA(1) | FGD-MA(2)
---|---|---|---|---|---|---|---|---
Batch 4 lr 0.001 | 91.55 | 85.41 | 90.16 | 86.79 | 90.60 | 90.93 | 88.96 | 88.92
Batch 16 lr 0.001 | 89.95 | 80.59 | 87.58 | 77.90 | 88.85 | 88.87 | 84.38 | 84.38
Batch 64 lr 0.001 | 88.55 | 36.79 | 81.02 | 35.86 | 85.89 | 85.88 | 50.63 | 50.61
Batch 4 lr 0.01 | 85.55 | 91.41 | 91.48 | 90.41 | 91.18 | 90.42 | 91.34 | 90.73
Batch 16 lr 0.01 | 90.71 | 89.09 | 91.46 | 88.71 | 91.66 | 91.61 | 89.68 | 89.51
Batch 64 lr 0.01 | 87.86 | 86.22 | 89.26 | 85.96 | 90.22 | 90.16 | 89.41 | 89.41
Batch 4 lr 0.1 | 11.52 | 91.29 | 20.53 | 88.07 | 26.52 | 26.16 | 91.48 | 85.94
Batch 16 lr 0.1 | 12.03 | 90.64 | 89.54 | 91.77 | 71.81 | 79.36 | 92.13 | 92.07
Batch 64 lr 0.1 | 30.31 | 81.80 | 90.94 | 90.18 | 89.67 | 89.14 | 91.15 | 91.23
Mean | 65.34 | 81.47 | 81.33 | 81.74 | 80.71 | 81.39 | 85.46 | 84.76

###  IV-A Study 1: Non-convex optimization

We experiment with the scenario of optimizing a well designed non-convex
problem using (1) SGD (2) Adam [6] (3) FGD-MA with order 1 and 2 (4) FGD-AR
with order 1 (momentum) and 2 (5) FGD-K and (6) FGD-W. In this experiment, we
intend to minimize a non-convex function

$f(x,y)=(x^{2}+y^{2})+5\sin(x+y^{2})$ (20)

Experiment Setting. For each experiment, we select a learning rate from
$\eta=\\{0.01,0.03\\}$ to minimize this function. The initial point is fixed
to $(x,y)=(5,5)$. For Adam, we use the default setting that
$\beta_{1}=0.9,\beta_{2}=0.99$. For FGD-MA and FGD-AR, we select
$a_{1}=b_{1}=0.9$ for order 1 model and $a_{1}=b_{1}=0.8,a_{2}=b_{2}=0.1$ for
order 2. For FGD-K, we select $\gamma=2,c=1,\sigma_{Q}^{2}=0.01,\sigma_{R}=2$.
For FGD-W, we use Daubechies 4 (db4) wavelet and $K=3$ and $L=8$. We apply
soft-thresholding on each highpass band with threshold of $0.2$ and select
$\alpha=5$. Each Algorithm runs for $T=500$ iterations.
Result. Figure 3(a) visualizes the function value surface. We also show the
trajectory of the optimization process for different methods in Figure 3(b)
and 3(c). Figure 3(d) and 3(e) are the plots of the function value along with
the number of iterations. First, FGD resolves the local minimum problem by
boost the lowpass band of the gradient. Under both learning rates, SGD was
finally trapped in a local minimum. On the other hand, FGD-K and FGD-W is able
to find the global solution constantly with smoothed gradient. This shows
that, compared with vanilla SGD that only rely on local gradient, FGD-K and
FGD-W can robustly solve the non-convex optimization problem with filtered
gradients. Second, not all filters work the same good. In comparison to FGD-K
and FGD-W, the momentum method (FGD-AR(1)) and FGD-AR(2) succeeded in finding
the optimal solution when the learning rate is properly set (0.01 in this
experiment) but still fails when the learning rate increases to 0.03. FGD-MA
model fails under both settings. The filter selection is important for a good
convergence. Surprisingly, Adam, as the most popular method recently,
performed extremely poor on both setting, mainly because the non-smoothing
property of the optimization problem.

Figure 3(f), 3(h), 3(g) and 3(i) illustrate the variance of the gradient for
each parameter. SGD bounces around ravines, resulting in noisy gradients and
large variance on both $x$ and $y$. The moving-average model introduces large
variance to the gradient by blindly adding the past gradient to the current
update. FGD-AR(1) (momentum) and FGD-AR(2) relieve the variance problem when
the learning rate is small but fails when a large learning rate is used. Adam
succeeds in suppressing the gradient variance by keeping a running average of
second-order momentum, but nearly stops learning from the 200-th iteration. It
is clear that FGD-K and FGD-W are able to reduce the variance of the gradient
compared with the momentum-based methods and vanilla SGD. This experiment
shows promising results that FGD not only reduces the variance in gradient
descent, but also help to get rid of the local minimum in the non-convex
optimization problem. It encourages us to apply FGD to other optimization
problems, like training neural networks.

###  IV-B Study 2: Multi-layer perceptron

We train a multi-layer perceptron (MLP) on MNIST [12] dataset using (1) SGD
(2) Adam [6] (3) FGD-MA with order 1 and 2 (4) FGD-AR with order 1 (vanilla
momentum) and 2 (5) FGD-K and (6) FGD-W. We compare their (1) performance,
measured by test accuracy (2) convergence rate, measured by training loss.
Experiment setting. We establish a 3-layer neural network with 784 input
units, 10 hidden units, and 10 output units. All training images are augmented
with zero-padding of 2 pixels and random cropped to $28\times 28$. Each image
is flattened as a 1-dimension vector. We set the initial learning rate
$\eta=\\{0.1,0.01,0.001\\}$ and mini-batch size $batchsize=\\{4,16,64\\}$. The
learning rate is multiplied by 0.7 every epoch. For Adam, we use the default
setting that $\beta_{1}=0.9,\beta_{2}=0.99$. For FGD-MA and FGD-AR, we select
$a_{1}=b_{1}=0.9$ for order 1 model and $a_{1}=b_{1}=0.8,a_{2}=b_{2}=0.1$ for
order 2. For FGS-K, we select $\gamma=5,c=1,\sigma_{Q}^{2}=0.01,\sigma_{R}=2$.
For FGD-W, we use Daubechies 4 (db4) wavelet and $K=3$ and $L=16$. We apply
soft-thresholding on each highpass band with threshold of $0.2$ and select
$\alpha=5$. We train the network for 10 epoch. The network is trained with a
cross-entropy loss.
Result. Figure 4 compares the training loss under different learning rate and
batch size setting on MNIST classification task. First, convergence is slower
when the learning rate is small and batch size is large. In such
circumstances, filtering techniques accelerate the training by enhancing the
low-frequency part of the gradient. For example, when $lr=0.001$ and
$batchsize=64$, variants of FGD show faster convergence compared with vanilla
SGD. Second, a large learning rate and small batch size result in sharply
jittering curves, which demonstrates large randomness in training. For
example, Adam and FGD-AR(1) (momentum) fails under the case with $lr=0.1$ and
$batchsize=4$. It again shows that the momentum method is very sensitive to
the hyper-parameter setting. In such a case, FGD-K and FGD-MA successfully
produce smoother curves and reduce the noise and randomness in the training.
In comparison, FGD is more robust to learning rate changes compared to the
momentum-based method.

Table I shows the test accuracy given various parameter setup on MNIST. First,
FGD outperforms vanilla SGD when learning with small learning rate and large
batch size. For example, FGD-W, FGD-MA, FGD-AR(1)&(2) and FGD-MA(1)&(2)
ourperform SGD when $lr=0.01$ and $lr=0.001$ for all batch setting. FGD-W and
FGD-AR even improves SGD by over 130% for case where $lr=0.001$ and
$batchsize=64$. It reveals that FGD is able to accelerate learning and achieve
better convergence when the step-size is small. Another observation from the
table is that the momentum-based model (FGD-AR(1) and Adam) is very sensitive
to the hyper-parameter setting. Test accuracy with Adam dramatically drops to
around 20% for situations with a large learning rate (0.1). In comparison,
FGD-MA and FGD-K are robust to all kinds of hyper-parameter setting. This
result further provides pieces of evidence that blind acceleration with the
momentum method is not universally optimal. On the other hand, gradient
estimation with filters is able to adaptively find a robust estimation of the
true gradient regardless of parameter setup. In addition, FGD-MA with order 1
and order 2 makes the best performance on average. Compared with the
traditional momentum method, it provides a cheap solution to training the
neural network with great potential.

Figure 5: Test error curve On CIFAR-10 with ResNet-18, with two detail zoom in (x-axis: epoch; y-axis: test error) TABLE II: Test Accuracy on CIFAR-10 with ResNet-18 Method | Top1 test
---|---
Adam [6] | 92.50
FGD-AR(1) | 92.77
SGD | 93.33
FGD-K | 93.54
FGD-M | 93.42
FGD-AR(2) | 93.60
FGD-MA(1) | 93.23
FGD-MA(2) | 93.76

###  IV-C Study 3: Convolutional neural networks

We train a well-designed convolutional neural network (ResNet-18 [13]) on
CIFAR10 [14] dataset using (1) SGD (2) Adam [6] (3) FGD-MA with order 1 and 2
(4) FGD-AR with order 1 (vanilla momentum) and 2 (5) FGD-K and (6) FGD-W. We
compare their (1) convergence rate, measured by the test error curve, and (2)
performance, measured by best test accuracy.
Experiment setting. All training images are augmented with random horizontal
flip, zero-padding of 4 pixel and random cropped to $32\times 32$. We set the
initial learning rate of $\eta=0.1$, mini-batch size $batchsize=64$ and train
the network for 200 epoch. The learning rate is multiplied by 0.1 at the 80
and 160 epoch. For Adam, we use the default setting that
$\beta_{1}=0.9,\beta_{2}=0.99$. For FGD-MA and FGD-AR, we select
$a_{1}=b_{1}=0.9$ for order 1 model and $a_{1}=b_{1}=0.8,a_{2}=b_{2}=0.1$ for
order 2. For FGS-K, we select $\gamma=5,c=1,\sigma_{Q}^{2}=0.01,\sigma_{R}=2$.
For FGD-W, we use Daubechies 4 (db4) wavelet and $K=3$ and $L=16$. We apply
soft-thresholding on each highpass band with threshold of $0.2$ and select
$\alpha=5$. The network is trained with a cross-entropy loss.
Result. Table II list the test accuracy for different optimization methods on
the CIFAR-10 dataset. First, resembling with results in Study 2, momentum-
based method (Adam & FGD-AR(1)) may not be optimal even compared with vanilla
SGD. It again shows that blindly accelerating the gradient descent by using an
$AR(1)$ model does not capture the real dependency of the noisy gradient
observations and the true state. Second, FGD variants outperform SGD and
momentum method experiment. These results reemphasize the major merit of the
FGD method – it is able to help the network to get rid of the global minimum
while less sensitive to hyper-parameter selection. Third, we can make the
observation that FGD is not sensitive to the filter selection. FGD achieves
similar test accuracy regardless of which filter is applied. This result gives
supporting evidence that FGD is a generally efficient framework in
optimization. Impressively, among all variants, FGD-MA(2) achieves the best
test performance of 93.76% for ResNet-18 on the CIFAR-10 dataset. This result
reemphasizes the huge potential for the FGD-MA method in training the neural
network.

Figure 5 demonstrates the test error VS epoch through the training process.
The bottom-left and bottom-right plots provide two zoom-in views for the
training process. The bottom-left plot is in the middle of training and the
bottom-right plot visualizes the test error at the end of the training. First,
in the bottom-left plot, we may observe that the variance in the error curve
is successfully reduced by the different filters compared with vanilla SGD
(light blue solid). The curve SGD is highly non-smooth, with tremendous ups
and downs. Filtering in gradients, especially for FGD-AR(2) and FGD-K, succeed
in reducing the variance of the gradient, resulting in smoother curves.
Second, in the bottom-right plot, we see that FGD results in better
convergence in training neural networks. Compared with Adam (orange dotted)
and FGD-AR(1) (gray solid), FGDs generally achieve lower test error. For
example, FGD-MA(2) (purple dotted) and FGD-AR(2) (crimson dashed) achieve the
lowest test error. This observation illustrates that FGD is efficient in
training the neural network.

##  V Conclusion

In this paper, we propose Filter Gradient Decent, which reduces the variance
in gradient estimation by solving a filtering problem. It is a general
framework that applies filter techniques to stochastic gradient descent to
estimate the true state of the gradient from noisy observations. FGD not only
greatly reduces the noise in the gradient estimation, but also helps to get
rid of the local optima problem in the optimization. A series of comprehensive
experiments show that FGD is able to achieve superior performance in solving
non-convex optimization problems and training neural networks.

##  VI Team Member Contribution

Xingyi Yang: 100%

## Future work

Filtering in signal processing is a well-studied subjects. A large number of
researchers have provided mathematical proofs that different filtering
techniques can efficiently eliminate different noise models. In future works,
I would like to provide some theoretical provements that Filter Gradient
Decent is mathematically explainable in reduce the gradient variance.

## Acknowledgment

The authors would like to thank Professor Truong Nguyen for his quality
curriculum design and careful explanation for the course content .Thanks for
all the classmates in ECE251C. Hope everyone stay healthy.

## References

  * [1] Chong Wang, Xi Chen, Alexander J Smola, and Eric P Xing,  “Variance reduction for stochastic gradient optimization,”  in Advances in Neural Information Processing Systems, 2013, pp. 181–189.
  * [2] Ning Qian,  “On the momentum term in gradient descent learning algorithms,”  Neural networks, vol. 12, no. 1, pp. 145–151, 1999.
  * [3] John Duchi, Elad Hazan, and Yoram Singer,  “Adaptive subgradient methods for online learning and stochastic optimization,”  Journal of machine learning research, vol. 12, no. Jul, pp. 2121–2159, 2011.
  * [4] Matthew D Zeiler,  “Adadelta: an adaptive learning rate method,”  arXiv preprint arXiv:1212.5701, 2012.
  * [5] Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky,  “Neural networks for machine learning lecture 6a overview of mini-batch gradient descent,”  .
  * [6] Diederik P Kingma and Jimmy Ba,  “Adam: A method for stochastic optimization,”  arXiv preprint arXiv:1412.6980, 2014.
  * [7] Timothy Dozat,  “Incorporating nesterov momentum into adam,”  2016\.
  * [8] Léon Bottou,  “Stochastic gradient descent tricks,”  in Neural networks: Tricks of the trade, pp. 421–436. Springer, 2012.
  * [9] Mark Schmidt, Nicolas Le Roux, and Francis Bach,  “Minimizing finite sums with the stochastic average gradient,”  Mathematical Programming, vol. 162, no. 1-2, pp. 83–112, 2017.
  * [10] Andrew Miller, Nick Foti, Alexander D’Amour, and Ryan P Adams,  “Reducing reparameterization gradient variance,”  in Advances in Neural Information Processing Systems, 2017, pp. 3708–3718.
  * [11] Rudolph Emil Kalman,  “A new approach to linear filtering and prediction problems,”  1960\.
  * [12] Yann LeCun, Corinna Cortes, and CJ Burges,  “Mnist handwritten digit database,”  ATT Labs [Online]. Available: http://yann. lecun. com/exdb/mnist, vol. 2, 2010.
  * [13] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun,  “Deep residual learning for image recognition,”  arXiv preprint arXiv:1512.03385, 2015.
  * [14] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton,  “Cifar-10 (canadian institute for advanced research),”  .