11footnotetext: Hao Zhu and Jia-Yao Yang contributed equivalently to this
work.22footnotetext<EMAIL_ADDRESS>Corresponding
author33footnotetext<EMAIL_ADDRESS>Corresponding author

# Why Existing Machine Learning Methods Fails At Extracting the Information of
Future Returns Out of Historical Sctock Prices : the Curve-Shape-Feature and
Non-Curve-Shape-Feature Modes

Jia-Yao Yang  Hao Zhu  Yue-Jie Hou  Ping Zhang  and Chi-Chun Zhou

###### Abstract

The financial time series analysis is important access to touch the complex
laws of financial markets. Among many goals of the financial time series
analysis, one is to construct a model that can extract the information of the
future return out of the known historical stock data, such as stock price,
financial news, and e.t.c. To design such a model, prior knowledge on how the
future return is correlated with the historical stock prices is needed. In
this work, we focus on the issue: in what mode the future return is correlated
with the historical stock prices. We manually design several financial time
series where the future return is correlated with the historical stock prices
in pre-designed modes, namely the curve-shape-feature (CSF) and the non-curve-
shape-feature (NCSF) modes. In the CSF mode, the future return can be
extracted from the curve shapes of the historical stock prices. By applying
various kinds of existing algorithms on those pre-designed time series and
real financial time series, we show that: (1) the major information of the
future return is not contained in the curve-shape features of historical stock
prices. That is, the future return is not mainly correlated with the
historical stock prices in the CSF mode. (2) Various kinds of existing machine
learning algorithms are good at extracting the curve-shape features in the
historical stock prices and thus are inappropriate for financial time series
analysis although they are successful in the image recognition and natural
language processing. That is, existing machine learning methods that are good
at handling the CSF series will fail at extracting the information of future
returns out of historical stock prices. New models handling the NCSF series
are needed in the financial time series analysis.

##  1 Introduction

The financial market is indeed a complex and giant system [1, 2, 3]. The
financial time series analysis is important access to touch the complex laws
of financial markets [1, 2, 3]. Among many goals of the financial time series
analysis, one is to construct a model that can extract the information of the
future return out of the already known historical data, such as stock prices,
financial news, economic events, and political events [4, 5, 6, 7, 8].

Before constructing a model that can extract the information of the future
return out of the historical data, researchers need the prior-knowledge of the
markets and investigate issues such as whether the information of the future
return contained in the already known historical data? Or, is there a
correlation between the future return and the historical stock prices?
According to the effective market hypothesis (EMH) [9, 10, 11], stocks always
trade at their fair value on exchanges, thus, no investors can outperform the
overall market through stock selection or market timing, the higher returns
can only be obtained by purchasing riskier investments. Therefore, according
to EMH, there is no correlation between the current price and the future price
of the stock market, I.e., any change in the stock price is completely
independent of the past price. However, there are different opinions on the
issue of EMH [9, 11, 12, 13] and higher returns can be obtained by technical
analysis such as expert stock selection and market timing in real investments
[14, 15, 16, 17, 18]. In this regard, we cannot deny that the historical data
of financial markets contains information of the future return. Therefore, it
is of great significance to analyze the hidden features and laws of historical
financial data, including stock prices, financial news, economic events, and
political events.

Stock prices are typical data that are accessible and intuitive. There are
research studying how to extract future return from the known historical stock
prices. Before the popularity of machine learning methods, researchers
investigate the financial time series from the perspective of analytical and
statistical methods. For example, the fractional market shows that the
financial market has the characteristics of fractional and non-linearity [19,
20, 21, 22]. Spectrum analysis methods [23], such as the Fourier transform
[24, 25] and the wavelet transform [24, 26, 27] are applied to the financial
time series analysis. The auto regressive model (AR), the moving average model
(MA), the auto regressive and moving average model (AR-MA), and e.t.c., are
proposed to modeling the market [1, 2, 3]. Besides is directly forecasting the
future return, the generalized autoregressive conditional heteroskedasticity
model (GARCH) is proposed to model and forecast conditional mean and
volatility [28]. Other hybrid models such as ARMA-GARCH [29, 30] and its
improved ARMA-GARCH-M [31] model are proposed . However, the statistical
method is not suitable for actively discovering various potential rules from
numerous data [32]

With the popularity of machine learning methods, researchers use the machine
learning methods to investigate the financial time series. For example, the
support vector machines (SVM) [4, 33] , the recurrent neural network (RNN)
[34] and it’s generalization long-short term memory (LSTM) [35, 36] network,
and the convolutional neural network (CNN) [37, 38] are applied in financial
time series forecasting. A multi-scale recurrent convolutional neural network
(MSTD-RCNN) [39] is proposed and proved to improve the accuracy of data
prediction. The hybrid models which is the combination of the statistical
method and the machine learning method such as multi forecast model of ARIMA
and artificial neural network (ANN) [40], the FEPA model (FTS-EMD-PCA-ANN)
[41], nonlinear autoregressive neural network model [42] are used in modeling
the financial time series. Beyond the model structure designing, other
researchers focus on the data. For example, Ref. [43] evaluates several
augmentation methods applied to stocks datasets using two state-of-the-art
deep learning models and show that several augmentation methods significantly
improve financial performance when used in combination with a trading
strategy.

The majority of the research focused on how to improve the model’s behavior in
forecasting the future return and most of the proposed models report a
improving in the forecasting accuracy. However, there are research report a
failure of the deep learning approach on financial time series analysis [44].
In our opinions, the prior-knowledge on how the future stock price or return
is correlated with the historical stock price should be obtained before
designing an effect algorithm or model. Unfortunately, to our knowledge, not
many research concern the question about in what mode the future return is
correlated with the historical stock price. Or, how is the information of the
future return contained in the already known stock price. With the absence of
the prior-knowledge, one might become blind in choosing models.

In this paper, under the assumption that the market is not completely
effective, we focus on the issue: in what mode the future return is correlated
with the historical stock prices. We manually design several financial time
series where the future return is correlated with the historical stock prices
in pre-designed modes, namely the curve-shape-feature (CSF) and the non-curve-
shape-feature (NCSF) modes. In the CSF mode, the future return can be
extracted from the curve shapes of the historical stock prices. In the NCSF
mode, the information of future return is not contained in the curve shape of
historical stock prices. By applying various kinds of existing algorithms on
those pre-designed time series, we find that various kinds of existing models
only perform well on the CSF mode series and fail on the NCSF mode series. By
comparing the behavior of the same algorithm on the CSF mode series, NCSF mode
series, and real financial time series, we conclude that: (1) the major
information of the future return is not contained in the curve-shape features
of historical stock prices. That is, the future return is not mainly
correlated with the historical stock prices in the CSF mode. (2) Various kinds
of existing machine learning algorithms are good at extracting the curve-shape
features in the historical stock prices and thus are inappropriate for
financial time series analysis although they are successful in the image
recognition, nature language processing, and e.t.c. It points out that beyond
the existing models, new models that can extract non-curve-shape features are
needed in the financial time series analysis.

This paper is organized as follows: In Sec. 2, the pre-designed time series,
including the CSF mode series and NCSF mode series, are introduced. In Sec. 3,
we firstly give a brief review on various existing algorithms and secondly
apply them on the CSF mode series, NCSF mode series, and the real series. In
Sec. 4, we analyze the results. Conclusions and discussions are given in Sec.
5.

##  2 Pre-designed series: the CSF mode series and NCSF mode series

The prior-knowledge that in what mode the future return is correlated with the
historical stock prices is important in financial time series analysis. In
this section, we manually design several financial time series where the
future return is correlated with the historical stock prices in pre-designed
modes, namely the curve-shape-feature (CSF) and the non-curve-shape-feature
(NCSF) modes.

###  2.1 The CSF mode series

In this section, we introduce the CSF mode series. In the CSF mode series the
future return can be extracted from the curve shapes of the historical stock
price.

The curve-shape features and simplified curve-shape features. In the
historical stock price, the curve-shape features are morphological shapes
occurring in a window with given size. There is a large amount of the curve-
shape features. In this work, we simplify the curve-shape features by ignoring
the magnitude of the stock prices and only considering the trend of increase
and decrease, as shown in Fig. 1. In the following discussion, we consider the
simplified curve-shape features only and make no distinguish between the
curve-shape features and simplified curve-shape features.

The effective curve-shape features We can capture numerous different curve-
shape features from historical financial data. For example, curve-shape
features intercepted within different-size windows, as shown in Fig. 2. The
curve-shape features that are strongly correlated with the future return is
the effective curve-shape features. For example, the curve-shape feature A
occurs at a higher frequency in a positive return history series, then, A is
an effective curve-shape feature. The curve-shape feature B occurs evenly in a
positive and negative return history series respectively, then, B is not an
effective curve-shape feature. A combination of effective curve-shape features
can predict the future return.

The CSF mode series. In the CSF mode series the future return can be extracted
from the curve shapes of the historical stock price. We manually assign a
weight on the curve-shape features. The summation of the weight of the
features occur in a given historical stock prices decide the future return. In
the CSF mode series, those features with larger weight are effective curve-
shape features, as show in Fig. 3.

Figure 1: Examples of the curve-shape features and simplified curve-shape
features. In the simplified curve-shape features only the trend of increase
and decrease is considered. Figure 2: Examples of effective curve-shape
features. Effective curve-shape features occur unevenly in the time series
with positive and negative returns and decide the future returns. Figure 3:
Examples of effective curve-shape features with weights and CSF mode series.
The effective curve-shape features with higher degree of uneven occurrences
have larger weights. The summation of the weight of the effective curve-shape
features in a time series, namely the score of the time series, decide the
future return. For example, if the score beyond a threshold, the future return
will be positive with a high probability.

###  2.2 The NCSF mode series: the momentum-featured series

In this section, we manually design a NCSF mode series, where the future
return can not be extracted from the curve shape of the historical stock
prices. In this series, the future return is determined by the number of rises
and falls in the historical data, For the sake of convenient, we name it the
momentum-featured series. For example, for a historical data with in a fixed-
size window, the ratio of the amount of rising data to the total amount of
data is calculated. When the ratio exceeds a given value, say $0.7$, the
future return will be positive with a high probability, as shown in Fig. 4.
The momentum-featured series is just one of the NCSF mode series.

Figure 4: An example of the momentum-featured series

###  2.3 The selected four kinds of series

In this section, we introduce the four kinds of series that are used in the
following experiment, and they are: (1) the CSF mode series, (2) the momentum-
featured series which is a typical NCSF mode series, (3) the real stock
series, and (4) the random generated series. As shown in Fig. 5.

In the series, the maximum size of the time window is $20$, that is, the next
days return is decided by the prices in previous $20$ days.

Figure 5: A diagram of the prices and autocorrelation function of the four
kinds of series including the CSF mode, NCSF mode, random generated, and real
series.

##  3 The methods and the experiment settings

In this section, various of existing algorithms are applied on the four kinds
of series, including a new proposed statistical method, the existing machine
learning methods, and the existing deep learning methods. The result shows
that, the existing algorithms are good at extracting the curve-shape features
in the historical stock price. That is, the existing algorithms are effective
for the CSF mode series and are inappropriate for the NCSF mode series.

###  3.1 The proposed statistical method for curve-shape features (the SM-CSF
model)

In this section, we propose a statistical method that is designed to extract
the effective curve-shape features in the series. For the sake of convenient,
we name this method statistical method for curve-shape features (the SM-CSF
model). In this section, we give an introduction of the SM-CSF model.

In the SM-CSF model, we firstly collect all possible simplified curve-shape
features in given window sizes, say window sizes 4, 5, 6, and 7. Secondly, we
count the occurrence times of each curve-shape features in the positive and
negative samples. And the effective curve-shape features are selected
according to their unevenly occurrence times. For example, if the feature A
occurs $100$ times in the positive samples and $1000$ times in the negative
samples, we consider A as an effective curve-shape feature. Finally, the
linear regression method is applied to find the weight that evaluates the
importance of the each effective curve-shape feature to the future return.
That is, a weight is assigned to each effective features and the weight is
evaluated by linear regression method [45].

###  3.2 The existing algorithms: a brief review

In this section, we give a brief review of the existing algorithms, including
the statistical methods, machine learning methods, and deep learning methods

Machine learning methods: support vector machine (SVM) The SVM is a supervised
learning model and related learning algorithm for data analysis in
classification and regression analysis. Given a group of training instances,
each training instance is marked as belonging to one or the other of the two
categories. SVM training algorithm creates a model to assign the new instance
to one of the two categories, making it a non probabilistic binary linear
classifier [46].

Machine learning methods: random forest (RF) It can be regarded as a basic
classification method of decision tree. The decision tree is composed of nodes
and directed edges. The internal nodes represent feature attributes, and the
external nodes (leaf nodes) represent categories. RF is a bagging combination
of different decision trees, which is based on decision tree. The decision
tree selects an optimal feature (maximum information gain ID3, maximum
information gain ratio C4.5, minimum Gini index) from the feature set to
branch, while the random forest selects the optimal feature from the randomly
selected feature subset to branch.

Machine learning methods: multilayer perceptron (MLP) The MLP is a kind of
forward structure artificial neural network, which maps a group of input
vectors to a group of output vectors. MLP can be regarded as a directed graph,
which is composed of multiple node layers, and each layer is fully connected
to the next layer. Except for the input nodes, each node is a neuron with a
nonlinear activation function.

Machine learning methods: bayesian classifier Based on Naive Bayes formula,
the maximum value of a posteriori probability is compared to classify. The
calculation of a posteriori probability is obtained by the product of a priori
probability and class conditional probability. A priori probability and class
conditional probability are obtained by training data set.

Deep learning methods: the embedded convolution neural network (CNN) The
convolutional neural network contains a feature extractor composed of
convolution layer and subsampling layer. In convolution layer of convolution
neural network, one neuron is only connected with some neighboring neurons. In
a convolution layer of CNN, there are usually several feature maps. Each
feature plane is composed of some neurons arranged in a rectangle. The neurons
in the same feature plane share weights, and the weights shared here are
convolution kernels. Convolution kernel is usually initialized in the form of
random decimal matrix. In the process of network training, convolution kernel
learn to get reasonable weights. Subsampling, also known as pooling, usually
has two forms: mean pooling and Max pooling [47]. Convolution and subsampling
greatly simplify the model complexity and reduce the model parameters.

We design an embedded convolution neural network [48]. In this network,
firstly, embedding the input series, sparsely representing the original data,
converting each value in the series into vectors, learning into vector space.
After that we convolute the embedded series by using 32 filters of size 5x7x9,
then pooling them to extract the effective features. Finally, the output
prediction value is calculated at the full connection layer.

Deep learning methods: the embedded long short-term memory neural network
(LSTM) LSTM is an improved RNN. LSTM networks consist of LSTM units. LSTM unit
is composed of cells having input, output and forget gates. These three gates
regulate the information flow. With these features, each cell remembers the
desired values over arbitrary time intervals. LSTM cells combine to form
layers of neural networks [49].

Based on the biLSTM, we structure an embedded biLSTM, where we embed the input
series firstly, which converts each value in the series into a vector, this
process can represent the series sparsely in vector space. Next,the embedded
series is input from forward LSTM and backward LSTM in one time step. Forward
LSTM and backward LSTM are calculated to get two sets of hidden vectors with
valid features. Then two sets of hidden vectors are stitched together to get
the final hidden state [50]. The model’s output layer calculates the predicted
value based on parameters such as hidden state and weight, and the Loss
function use the cross-entropy.

###  3.3 The ground truth of the CSF and the NCSF mode series

In this work, the CSF and NCSF series are generated manually. According to the
generation rules of the CSF and the NCSF series, we can easily design a model
that can extract the information of future return from such series. With this
regard, we consider the model as the model of ground truth, because it
extracts the maximum degree of information from the CSF and the NCSF series.
For the sake of convenient, we name them the ground truth model for the CSF
series (GT-CSF) and ground truth model for the NCSF model (GT-NCSF).

The GT-CSF model. In the GT-CSF model, the pre-designed rule is used to design
the model. For example, we know the weight for each curve-shape features and
the threshold of the score. By directly calculating the score of the series
and comparing it with the threshold, we can give the trend of future return.

The GT-NCSF model. In the GT-NCSF model, the pre-designed rule is also used to
design the model. For example, we know the ratio between ups and downs that
decide the future return. By directly calculating the ratio of ups and downs
and comparing it with the threshold, we can give the trend of future return.

An overview of the methods is given in Fig. 6.

Figure 6: An overview of the methods

##  4 The results and analysis

In this section, we show the results of different algorithms on the four
series.

###  4.1 The criteria

We give a criterion to judge the behavior of the algorithms as follows: in a
given test data set, we calculate the precision of the positive return cases
in selected samples by each algorithm and compare it with that of the random
selected samples. The precision given by the ground truth gives the upper
bound over all the algorithms. For example, in the randomly selected samples,
the precision of the positive return cases is $0.52$. The ground truth is
$0.75$ evaluates the maximum amount of the information of future return that
is contained in the historical prices. If the precision of selected samples by
algorithm A is obviously larger than $0.52$, then algorithm A is concluded to
be effective. That is, algorithm A can extract the mode where the future
return is correlated with the historical price. Otherwise, algorithm A is
ineffective on the series.

###  4.2 The result of the CSF mode series

Figure 7: The result of the CSF mode series

###  4.3 The result of the NCSF mode series

Figure 8: The result of the NCSF mode series Figure 9: The result of several
models(deep learning models,statistical model)for CSF mode series

From these different models, we put forward the first four with the best
effect and put them in Figure 8. Through comparison, it can be observed that
the deep learning model is more suitable for extracting the CSF, while the
extraction effect for the NCSF is poor.

###  4.4 The result of the real series

Figure 10: The result of the real stock series

###  4.5 The result of the $random_{g}enerated$ series

Figure 11: The result of the $random_{g}enerated$ series

###  4.6 The analysis

We conclude that in the real financial time series, less information of future
return is contained in the curve-shape manner and more information is
contained in the non-curve-shape manner. It points out that beyond the
existing models, new models that can extract non-curve-shape features are
needed in the financial time series analysis. We show that various kinds of
existing machine learning models which are successful in the image recognition
and natural language processing are inappropriate in financial time series
analysis. We also point out the reason: various kinds of existing machine
learning models are good at extracting the curve shape features and the
information of the future return is not all contained in the curve shape
features of historical data.

##  5 Conclusions and outlook

Through the above research results, we can see that statistical models,
machine learning models, and deep learning models can give effective
classification and prediction results for the curve-shape-featured data,
however, for the non-curve-shape-featured data which does not contain the
significant laws, these multi domain models cannot effectively classify them,
that is also completely consistent with our speculation.

This is also sufficient to explain that in the financial data, due to a large
number of combined curve-shape-features and non-curve-shape-features, the
current forecasting methods cannot provide effective answers to the trend of
future income. At the same time, we also pay attention to that in the
financial market, different participants and researchers have their own
subjective combination of characteristics, because according to the different
time scales, a lot of combined curve-shape-features can be observed from the
historical data, so everyone form their own judgment methods, such as those
experienced investors. Therefore, the complex and diversified combination of
curve-shape-features also affects the above model to judge the future income
results differently.

Our breakthrough in this research is to prove the existence of effective
curve-shape-features from complex financial data. These features of different
curve-shape patterns contain effective information that affects future income
results. According to the different combination methods and orders of various
data-shape forms, the formed laws and speculative results also be different.
In addition, the data are mixed with a large number of non-curve-shape-
featured data (disorderly and random data). In the test of A-shares and Hong
Kong stocks data, the test results of the three domain models are invalid,
which indicates that the market is not effective under the premise of this
theory, if we want to predict the future trend by analyzing the historical
data, we can either analyze more historical data to extract enough effective
features, so as to improve the more accurate basis for the future trend. Or we
can only design more complicated and more powerful models (more intelligent
models), more accurate parameters, more complicated data processing and model
optimization.

In this experiment, we use supervised models and discrimination models. These
models can be understood as completely relying on data volume, just like use
memory. Therefore, the data classification and prediction effect of curve-
shape-features is better. For complex data that cannot identify the laws, they
cannot make effective classification and prediction. So, we turn to the use of
generative models in the next step: AE, GAN, etc.

##  6 Acknowledgments

We are very indebted to Prof. Wu-Sheng Dai, Guan-Wen Fang, and Yong-Xie for
their encouragement. This work is supported by Yunnan Youth Basic Research
Projects (202001AU070020) and Doctoral Programs of Dali University
(KYBS201910).

## References

  * [1] R. S. Tsay, Analysis of financial time series, vol. 543.  John wiley & sons, 2005.
  * [2] T. C. Mills and R. N. Markellos, The econometric modelling of financial time series.  Cambridge University Press, 2008.
  * [3] T. G. Andersen, R. A. Davis, J.-P. Kreiß, and T. V. Mikosch, Handbook of financial time series.  Springer Science & Business Media, 2009.
  * [4] F. E. Tay and L. Cao, Application of support vector machines in financial time series forecasting, omega 29 (2001), no. 4 309–317.
  * [5] B. Krollner, B. J. Vanstone, and G. R. Finnie, Financial time series forecasting with machine learning techniques: a survey., in ESANN, 2010\.
  * [6] Q. A. Al-Radaideh, A. A. Assaf, and E. Alnagi, Predicting stock prices using data mining techniques, in The International Arab Conference on Information Technology (ACIT’2013), 2013.
  * [7] R. Adhikari and R. Agrawal, A combination of artificial neural network and random walk models for financial time series forecasting, Neural Computing and Applications 24 (2014), no. 6 1441–1449.
  * [8] O. B. Sezer, M. U. Gudelek, and A. M. Ozbayoglu, Financial time series forecasting with deep learning: A systematic literature review: 2005–2019, Applied Soft Computing 90 (2020) 106181.
  * [9] S. Basu, Investment performance of common stocks in relation to their price-earnings ratios: A test of the efficient market hypothesis, The journal of Finance 32 (1977), no. 3 663–682.
  * [10] B. G. Malkiel, Efficient market hypothesis, in Finance, pp. 127–134.  Springer, 1989.
  * [11] B. G. Malkiel, The efficient market hypothesis and its critics, Journal of economic perspectives 17 (2003), no. 1 59–82.
  * [12] A. Degutis and L. Novickytė, The efficient market hypothesis: A critical review of literature and methodology, Ekonomika 93 (2014) 7–23.
  * [13] K. Hamid, M. T. Suleman, S. Z. Ali Shah, and R. S. Imdad Akash, Testing the weak form of efficient market hypothesis: Empirical evidence from asia-pacific markets, Available at SSRN 2912908 (2017).
  * [14] L. Blume, D. Easley, and M. O’hara, Market statistics and technical analysis: The role of volume, The journal of finance 49 (1994), no. 1 153–181.
  * [15] J. J. Murphy, Technical analysis of the financial markets: A comprehensive guide to trading methods and applications.  Penguin, 1999.
  * [16] W.-K. Wong, M. Manzur, and B.-K. Chew, How rewarding is technical analysis? evidence from singapore stock market, Applied Financial Economics 13 (2003), no. 7 543–551.
  * [17] C.-H. Park and S. H. Irwin, What do we know about the profitability of technical analysis?, Journal of Economic surveys 21 (2007), no. 4 786–826.
  * [18] C. D. Kirkpatrick II and J. A. Dahlquist, Technical analysis: the complete resource for financial market technicians.  FT press, 2010.
  * [19] J. A. Scheinkman and B. LeBaron, Nonlinear dynamics and stock returns, Journal of business (1989) 311–337.
  * [20] E. E. Peters, Fractal market analysis: applying chaos theory to investment and economics, vol. 24.  John Wiley & Sons, 1994.
  * [21] E. E. Peters, Chaos and order in the capital markets: a new view of cycles, prices, and market volatility.  John Wiley & Sons, 1996.
  * [22] N. Laskin, Fractional market dynamics, Physica A: Statistical Mechanics and its Applications 287 (2000), no. 3-4 482–492.
  * [23] P. Rostan and A. Rostan, The versatility of spectrum analysis for forecasting financial time series, Journal of Forecasting 37 (2018), no. 3 327–339.
  * [24] K. Kawagoe and T. Ueda, A similarity search method of time series data with combination of fourier and wavelet transforms, in Proceedings Ninth International Symposium on Temporal Representation and Reasoning, pp. 86–92, IEEE, 2002.
  * [25] U. Cherubini, G. Della Lunga, S. Mulinacci, and P. Rossi, Fourier transform methods in finance, vol. 524.  John Wiley & Sons, 2010.
  * [26] H. Zhang, T. B. Ho, Y. Zhang, and M.-S. Lin, Unsupervised feature extraction for time series clustering using orthogonal wavelet transform, Informatica 30 (2006), no. 3.
  * [27] P. S. Addison, The illustrated wavelet transform handbook: introductory theory and applications in science, engineering, medicine and finance.  CRC press, 2017.
  * [28] L. Bauwens, S. Laurent, and J. V. Rombouts, Multivariate garch models: a survey, Journal of applied econometrics 21 (2006), no. 1 79–109.
  * [29] S. Ling and M. McAleer, Asymptotic theory for a vector arma-garch model, Econometric theory (2003) 280–310.
  * [30] C. Francq, J.-M. Zakoian, et al., Maximum likelihood estimation of pure garch and arma-garch processes, Bernoulli 10 (2004), no. 4 605–637.
  * [31] H. Liu, E. Erdem, and J. Shi, Comprehensive evaluation of arma–garch (-m) approaches for modeling the mean and volatility of wind speed, Applied Energy 88 (2011), no. 3 724–732.
  * [32] D. J. Hand, Principles of data mining, Drug safety 30 (2007), no. 7 621–622.
  * [33] K.-j. Kim, Financial time series forecasting using support vector machines, Neurocomputing 55 (2003), no. 1-2 307–319.
  * [34] R. Madan and P. S. Mangipudi, Predicting computer network traffic: a time series forecasting approach using dwt, arima and rnn, in 2018 Eleventh International Conference on Contemporary Computing (IC3), pp. 1–5, IEEE, 2018\.
  * [35] Y. Wu and J. Gao, Adaboost-based long short-term memory ensemble learning approach for financial time series forecasting., Current Science (00113891) 115 (2018), no. 1.
  * [36] J. Cao, Z. Li, and J. Li, Financial time series forecasting model based on ceemdan and lstm, Physica A: Statistical Mechanics and its Applications 519 (2019) 127–139.
  * [37] I. E. Livieris, E. Pintelas, and P. Pintelas, A cnn–lstm model for gold price time-series forecasting, Neural computing and applications 32 (2020), no. 23 17351–17360.
  * [38] S. Mehtab, J. Sen, and S. Dasgupta, Analysis and forecasting of financial time series using cnn and lstm-based deep learning models, arXiv preprint arXiv:2011.08011 (2020).
  * [39] L. Guang, W. Xiaojie, and L. Ruifan, Multi-scale rcnn model for financial time-series classification, arXiv (2019).
  * [40] C. N. Babu and B. E. Reddy, A moving-average filter based hybrid arima–ann model for forecasting time series data, Applied Soft Computing 23 (2014), no. Complete 27–38.
  * [41] Z. Chengzhao, A Deep Learning Model for Financial Market Forecasting: FEPA Model.  PhD thesis, Chengdu: School of Management and Economics of UESTC, 2016\.
  * [42] G. Benrhmach, K. Namir, A. Namir, and J. Bouyaghroumni, Nonlinear autoregressive neural network and extended kalman filters for prediction of financial time series, Journal of Applied Mathematics 2020 (2020).
  * [43] E. Fons, P. Dawson, X. J. Zeng, J. Keane, and A. Iosifidis, Evaluating data augmentation for financial time series classification, Papers (2020).
  * [44] A. Dingli and K. S. Fournier, Financial time series forecasting–a deep learning approach, International Journal of Machine Learning and Computing 7 (2017), no. 5 118–122.
  * [45] M. Q. Islam and M. L. Tiku, Multiple linear regression model under nonnormality, Communications in Statistics-Theory and Methods 33 (2005), no. 10 2443–2467.
  * [46] F. Osisanwo, J. Akinsola, O. Awodele, J. Hinmikaiye, O. Olakanmi, and J. Akinjobi, Supervised machine learning algorithms: classification and comparison, International Journal of Computer Trends and Technology (IJCTT) 48 (2017), no. 3 128–138.
  * [47] D. Palaz, R. Collobert, et al., Analysis of cnn-based speech recognition system using raw speech as input, tech. rep., Idiap, 2015.
  * [48] M. Cho, J. Ha, C. Park, and S. Park, Combinatorial feature embedding based on cnn and lstm for biomedical named entity recognition, Journal of Biomedical Informatics 103 (2020) 103381.
  * [49] T.-Y. Kim and S.-B. Cho, Predicting residential energy consumption using cnn-lstm neural networks, Energy 182 (2019) 72–81.
  * [50] S. Siami-Namini, N. Tavakoli, and A. S. Namin, The performance of lstm and bilstm in forecasting time series, in 2019 IEEE International Conference on Big Data (Big Data), pp. 3285–3292, IEEE Computer Society, 2019\.


#  GradFreeBits: Gradient Free Bit Allocation for Dynamic Low Precision Neural
Networks

Benjamin Bodner  Gil Ben Shalom  Eran Treister

###### Abstract

Quantized neural networks (QNNs) are among the main approaches for deploying
deep neural networks on low resource edge devices. Training QNNs using
different levels of precision throughout the network (dynamic quantization)
typically achieves superior trade-offs between performance and computational
load. However, optimizing the different precision levels of QNNs can be
complicated, as the values of the bit allocations are discrete and difficult
to differentiate for. Also, adequately accounting for the dependencies between
the bit allocation of different layers is not straight-forward. To meet these
challenges, in this work we propose GradFreeBits: a novel joint optimization
scheme for training dynamic QNNs, which alternates between gradient-based
optimization for the weights, and gradient-free optimization for the bit
allocation. Our method achieves better or on par performance with current
state of the art low precision neural networks on CIFAR10/100 and ImageNet
classification. Furthermore, our approach can be extended to a variety of
other applications involving neural networks used in conjunction with
parameters which are difficult to optimize for.

Machine Learning, ICML, Quantization, Gradient Free Optimization, Low
Precision Neural Networks, Compression

##  1 Introduction

In recent years, deep neural networks have been shown to be highly effective
in solving many real world problems, creating an increased demand for their
deployment in a variety of applications. However, such deep neural networks
often require a large amount of computational resources for both training and
inference purposes, which limits the adoption and spread of this technology in
scenarios where large computational resources are not available. This issue is
likely to persist in the near future, since recent trends have demonstrated
that increased model size is often correlated with improved performance (Brown
et al., 2020; Tan & Le, 2019; Kolesnikov et al., 2020). To mitigate this
issue, recent efforts have been focused on developing specialized hardware to
support the computational demands (Chen et al., 2020) as well as model
compression methods in order to reduce them (Cheng et al., 2018). These
include broad families of techniques such as pruning (Blalock et al., 2020),
knowledge distillation (Gou et al., 2020), neural architecture search
(NAS)(Ren et al., 2020) and as is the focus of this paper, quantization
(Hubara et al., 2017).

Quantization methods enable the computations performed by neural networks to
be carried out with fixed point operations, rather than floating point
arithmetic. This improves the computational efficiency of neural networks and
reduces their memory requirements. However, as with other compression methods,
this typically comes at the cost of reduced performance (Cheng et al., 2018).
Recent efforts in the field have focused on improving the trade-offs between
model compression and performance, by proposing a plethora of quantization
schemes tailored for different scenarios.

###  1.1 Quantization Methods

Quantization schemes can first be divided into post training and quantization
aware training schemes. Post training schemes decouple the tasks of model
training and the quantization of its weights and/or activations. These methods
are most suitable when the training data is no longer available when
compressing the network, and only the trained network is available (Banner et
al., 2019; Zhao et al., 2019). On the other hand, quantization aware training
schemes perform both optimization tasks together, and do require training
data, which tends to provide better performance.

In addition, quantization schemes can be further divided into methods which
perform uniform or non-uniform quantization. Uniform quantization divides the
real-valued domain into equally sized bins, whereas non-uniform methods do so
with bins of varying sizes. The former method tends to be more resource
efficient and compatible with modern hardware accelerators, while the latter
tends to provide better model performance (Li et al., 2019; Jung et al.,
2019).

Quantization schemes can be further subdivided into per-channel methods, which
utilize different quantization parameters for different channels within each
layer, as opposed to per-layer methods, which use the same parameters for all
channels in each layer, but different parameters for different layers.
However, as with non-uniform quantization, per-channel methods can be
difficult to implement efficiently on standard hardware components, making
per-layer methods more feasible for deployment on edge devices.

For the reasons stated above, in this work we focus on per-layer, uniform
quantization aware training with a different number of bits allocated per
layer, referred to as dynamic quantization.

###  1.2 Dynamic Quantization

Figure 1: Our proposed training scheme, which uses iterative optimization of
the model weights and bit allocation. Given a fixed allocation of bits for
each layer, the weights are optimised using a quantization aware training
procedure. Then, the bit allocation is optimized for those fixed weights and
the process is repeated.

Dynamic quantization aims to further improve the trade-offs between
performance and computational requirements of QNNs for deployment on
specialized edge devices. However, the proper allocation of bits between
layers is combinatorial in nature and is hard to optimize. Recent efforts to
tackle this problem include the use of reinforcement learning (Elthakeb et
al., 2018; Wang et al., 2019), Hessian analysis (Dong et al., 2019, 2020),
quantizer parametrization (Uhlich et al., 2020), and differentiable NAS
approaches (Wu et al., 2018; Li et al., 2020; Cai & Vasconcelos, 2020). Among
these methods, only the NAS approaches account for dependencies between bit
allocations in different layers, by forming a super network that includes
multiple branches for each precision at each layer. NAS approaches, however,
are more expensive to train due to the multiple network branches. Here we
offer an alternative approach to achieve the same goal.

###  1.3 Our Contributions

In this work we wish to optimize for the bit allocation of the network as a
whole, and address the full interactions between different components of QNNs.
To this end, we propose to utilize gradient-free optimization algorithms for
the bit allocation. Such algorithms are known to perform well in difficult
scenarios with complex dependencies between variables, while maintaining
excellent sample efficiency during optimization (Conn et al., 2009; Rios &
Sahinidis, 2013). In particular, we use the algorithm Covariance Matrix
Adaptation Evolution Strategy (CMA-ES) (Hansen et al., 2003), which aims to
achieve the mentioned goals, though other alternatives may also be suitable
for the task.

We propose a novel quantization aware training procedure for dynamic QNNs. In
this procedure, CMA-ES is used for computing the optimal (per-layer) dynamic
bit allocation for the weights and activations of the network. This method is
interchangeably applied with gradient-based methods. That is, the network
weights are updated by a gradient-based method, while the bit allocation is
updated using the gradient-free method CMA-ES—see Fig. 1.

The advantages of our approach are as follows:

  * •

Our training scheme for the dynamic bit allocation optimizes for the network
as a whole. That is, it takes into account dependencies between layers of the
neural network, as well as dependencies between weights and their bit
allocation.

  * •

Our method for bit allocation is gradient-free, hence it can handle multiple
(possibly non-differentiable) hardware constraints. This enables the QNN to be
tailored to the resources of the specific edge devices it is to be deployed
on.

  * •

The systematic combination of gradient-based and gradient-free optimization
algorithms can be utilized in other applications and scenarios, e.g.
systematic search of the network’s other hyper-parameters.

##  2 Preliminaries

###  2.1 Quantization Aware Training

The quantization schemes of weights or activations in neural networks that we
consider here can typically be broken into three steps: clip, scale and round.
In the first step, the real values of the weights or activations are clipped
to be within a range of values: i.e., $[-\alpha,\alpha]$ for symmetric signed
quantization (typically weights) and $[0,\alpha]$ for unsigned quantization
(typically activations, outputs of ReLU operations). Then, the range is mapped
to the target integer range $[-2^{b-1}+1,2^{b-1}-1]$ and $[0,2^{b}-1]$, for
signed and unsigned quantization respectively, where $b$ is the number of
bits. The values $\alpha$ are referred to as “scales” or clipping parameters
and take on different values for different layers. The clipping parameters are
optimized throughout the training procedure (along with the weights), so that
they yield the lowest possible generalization error when quantization applied
to the models’ weights and/or activations.

Several approaches have been proposed in recent years, in order to optimize
for the scales. In (Zhang et al., 2018a) the scales are chosen based on
quantization error minimization. (Choi et al., 2018) proposes differentiable
clipping parameters which are learned through backpropagation together with
the model’s weights. This approach is further improved in (Li et al., 2019),
which also supports a computationally efficient _non-uniform_ quantization
scheme. In this work we base our uniform quantization aware training scheme
(for the weights and activations) on (Li et al., 2019), while interchangeably
utilizing CMA-ES for the dynamic bit allocation.

Figure 2: Example of a signed 4-bit quantized weights tensor and $\alpha=0.16$
(original-left, quantized-right). Values which are lesser or greater than the
clipping parameters $\pm\alpha$ are clipped to $-\alpha$ or $+\alpha$
respectively, then scaled and rounded to the signed integer range. The value
of 0 is preserved in this process.

To formally introduce the point-wise quantization operations we first define
the quantization operator:

$Q_{b}(x)=\frac{\mbox{round}((2^{b}-1)\cdot x)}{2^{b}-1},$ (1)

where $x$ is a real-valued tensor in [-1, 1] or [0, 1] for signed or unsigned
quantization, respectively. $b$ is the number of bits that are used to
represent $x$. Given this operator, we use the reparameterized clipping
function (Li et al., 2019) to define the quantized weights and activations.

$\displaystyle W_{b}$ $\displaystyle=$
$\displaystyle\alpha_{W}Q_{b-1}(\mbox{clip}(\frac{W}{\alpha_{W}},-1,1))$ (2)
$\displaystyle X_{b}$ $\displaystyle=$
$\displaystyle\alpha_{X}Q_{b}(\mbox{clip}(\frac{X}{\alpha_{X}},0,1)).$ (3)

Here, $W,W_{b}$ are the real-valued and quantized weight tensors, $X,X_{b}$
are the real-valued and quantized input tensors, and $\alpha_{W},\alpha_{X}$
are their associated scale (or clipping) parameters, respectively. An example
of Eq. (2) being applied to a weights tensor, using 4-bit signed quantization
(without multiplying by $\alpha_{W}$), can be seen in Figure 2.

We note that equations (1)-(3) are used for training only. During inference,
weights and activations are dynamically quantized, and all operations are
performed using integers in mixed precision, while taking the scales into
account.

In this quantization aware training scheme, both weights and activations are
quantized during the forward pass, and during the backward pass, the Straight
Through Estimator (STE) (Bengio et al., 2013) is used to optimize the weights.
That is, we ignore the derivative of $Q_{b}$ in the backward pass, and iterate
on the floating point values of $W$ using the derivatives w.r.t $W_{b}$ in the
SGD optimization. Given Eq. (2)-(3) the STE can also be used to calculate the
gradients with respect to $\alpha_{W},\alpha_{X}$ (Li et al., 2019). This
enables the quantized network to be trained in an end-to-end manner using
backpropogation. To improve stability, (Li et al., 2019) also use weight
normalization before quantization:

$\hat{W}=\frac{W-\mu}{\sigma+\epsilon}.$ (4)

Here, $\mu$ and $\sigma$ are the mean and standard deviation of the weight
tensor, respectively, and $\epsilon=10^{-6}$.

###  2.2 CMA-ES

Covariance Matrix Adaptation Evolution Strategies (CMA-ES) (Hansen et al.,
2003), is a population based gradient-free optimization algorithm. It is known
to be highly versatile and has been applied to a large variety of settings,
such as RL (Heidrich-Meisner & Igel, 2008), placement of wave energy
converters (Neshat et al., 2020), hyper-parameter optimization (Loshchilov &
Hutter, 2016), evolving game levels in Mario (Volz et al., 2018), adversarial
attacks (Kuang et al., 2019) and more. It is designed to work in
$d$-dimensional continuous spaces and optimize discontinuous, ill-conditioned
and non-separable objective functions, in a black box optimization setting
(Hansen, 2009).

At a high level, the optimization process of CMA-ES is as follows. At the
$g$-th generation, a set of $\lambda$ $d$-dimensional samples are drawn from a
multivariate normal distribution $\mathcal{N}(m^{(g)},\mathcal{C}^{(g)})$:

$x_{k}^{(g+1)}\sim m^{(g)}+\sigma^{(g)}\mathcal{N}(0,\mathcal{C}^{(g)}),\mbox{
for }k=1,...,\lambda$ (5)

Where $m^{(g)}$, $\mathcal{C}^{(g)}$ are the mean and covariance matrrix of
the population at the previous generation, respectively. $\lambda$ is the
population size and $\sigma^{(g)}$ is the step-size.

Once the samples are drawn from this distribution, they are evaluated and
ranked based on the objective function. Then, keeping only the top $\mu$
samples with the best objective values, $m^{(g+1)}$, $\mathcal{C}^{(g+1)}$ and
$\sigma^{(g+1)}$ are calculated using a set of update rules. Please refer to
(Hansen, 2016) for more details. These are then used to draw samples for the
next generation using Eq. (14). This process is repeated until one of several
convergence criteria are full-filled, or until the algorithm exceeds its
predefined budget of allowed samples.

Though CMA-ES is an effective gradient-free optimization algorithm, it has
several downsides. First, its computational complexity is $O(d^{2})$ in space
and time (Hansen et al., 2003), where $d$ is the dimension of the parameter
vector to be optimized. Second, its convergence rate is often also $O(d^{2})$
(Hansen, 2009), making it inefficient for solving high dimensional problems
where $d$ is larger than a few thousands.

##  3 The GradFreeBits Method

In this section we describe the components of our optimization procedure for
dynamic QNNs.

###  3.1 Motivation: CMA-ES for Dynamic Precision.

We argue that CMA-ES is highly compatible with the problem of bit-allocation
in QNNs. Here we assume the objective function is the differentiable loss
function used during training, with additional possibly non-differentiable
constraints related to computational requirements (exact details are provided
below).

As recent evidence suggests (Wang et al., 2019; Dong et al., 2019), the
optimization landscape of the bit-allocation problem is likely to be
discontinuous, ill-conditioned and amenable for optimization using gradient-
free optimizers. Since the constraints may be non-differentiable, they can be
sampled in a black-box setting, as is done in gradient-free optimization (CMA-
ES) and reinforcement learning (Wang et al., 2019). Additionally, as shown in
(Dong et al., 2019, 2020), the Hessian eigenvalues show large variations for
different layers in QNNs, meaning that certain layers are typically more
sensitive to changes in bit-allocation than others. This is in part what
motivated us to choose CMA-ES for this work, as it is capable of adapting to
high variations in the Hessian eigenvalues, and is therefore considered to be
one of the best and widely used gradient-free methods. Lastly, since neural
networks typically have an order of tens to hundreds of layers, the problem of
bit optimization falls well within the range of dimensionallity where CMA-ES
is known to perform well, as discussed in the previous section.

###  3.2 Setting the Stage for CMA-ES

To enable the gradient-free optimization algorithm to efficiently optimize the
bit-allocation of a QNN, two items must be defined: its search space and the
objective function.

#### Search Space

We define the search space as a vector containing the bit allocation of the
weights and activations in all the layers of the network, asides the first and
the last layer, as these are quantized using a fixed allocation of 8 bits. We
found it beneficial to optimize the logarithm (base 2) of this vector, rather
than the vector itself. Thus, the vector to be optimized by CMA-ES is the log-
precision vector:

$\mathbf{v}=[\mathbf{v_{W}},\mathbf{v_{X}}]=\log_{2}([\mathbf{r_{W}},\mathbf{r_{X}}]),$
(6)

where $\mathbf{r_{W}},\mathbf{r_{X}}$ are the bit allocations of the network’s
weights and activations respectively, and $[\cdot,\cdot]$ is the concatenation
operation.

#### Objective Function

As mentioned in Section 7, the objective function to minimize is a combination
of the network’s performance measure, the differentiable loss function,
subject to a number of non-differrentiable computational constraints. More
formally:

$\min_{\mathbf{v}}\textit{ }\mathcal{L}(\mathbf{v};\mathbf{\theta}),\\\ \hskip
4.0pt\mbox{ s.t. }h_{j}(\mathbf{v})\leq C_{j}\hskip 4.0pt\mbox{ for
}j=1,...,M$ (7)

Where $\mathcal{L}(\mathbf{v};\mathbf{\theta})$ is the loss function over the
training set, parameterized by network parameters $\mathbf{\theta}$, which are
assumed to be fixed during the bit-allocation optimization stage. Furthermore,
$h_{j}(\mathbf{v})$ are the computational requirements for a given precision
vector $\mathbf{v}$ (e.g., model size, inference time etc.), $C_{j}$’s are the
target requirements that we wish to achieve, and $M$ is the number of
constraints. In our framework, we combine the constraints into the objective
function using the penalty method (Bertsekas, 2014):

$\min_{\mathbf{v}}\textit{
}\mathcal{L}(\mathbf{v};\mathbf{\theta})+\sum_{j=1}^{M}\rho_{j}\max(0,h_{j}(\mathbf{v})-C_{j})^{2},$
(8)

Where $\rho_{j}$ are balancing constraint parameters. This is similar to the
approach taken in (Uhlich et al., 2020), but here it is applied to gradient-
free optimization.

We define the computational constraints by comparing the requirements between
the dynamic and static precision networks. For example, we wish that the model
size will be equal to that of a static 4 bits allocation. Specifically, we use
constraints on the model size for the weights entries $\mathbf{v_{W}}$ and the
mean bit allocation for the activation entries $\mathbf{v_{X}}$:

$h_{1}({\mathbf{v}})=MB({\mathbf{v_{W}}}),\hskip
4.0ptC_{1}=\beta_{1}MB({\mathbf{v}^{S}_{\textbf{W}}})$ (9)
$h_{2}({\mathbf{v}})=\frac{1}{L}\sum_{i=1}^{L}v_{X_{i}},\hskip
4.0ptC_{2}=\frac{\beta_{2}}{L}\sum_{i=1}^{L}v^{S}_{X_{i}}$ (10)

Where $MB(\cdot)$ calculates the model size given weight entries
$\mathbf{v_{W}}$, $\mathbf{v}^{S}$ is the log-precision vector of the target
static precision we wish to achieve, $L$ is the number of relevant layers, and
$\beta_{1},\beta_{2}>0$ control the target compression rates of the weights
and activations, respectively.

These constraints are designed to limit the computational requirements, while
allowing the gradient-free optimization algorithm to explore non-trivial
solutions which satisfy them. It is important to note that though these
constraints are only related to memory requirements, other constraints can
easily be incorporated into our framework - such as power usage or inference
time measurements, chip area, etc.

###  3.3 Variance Reduction

Variance reduction has been shown to improve the convergence rate of
optimization algorithms (Johnson & Zhang, 2013). The main source of variance
in our objective function (Eq. (8)) is in the first term, related to the
performance of the model for different bit-allocations. There are two main
causes of variance in this term: sub-sampling noise, caused by using small
mini-batches of randomly selected samples, and sensitivity to quantization
errors, which networks are typically not robust to. To mitigate these issues
and improve the convergence rate of CMA-ES we adopt two strategies for
reducing the variance in the objective function, utilizing moving super-
batches and quantization aware pretraining, which will be described promptly.

Figure 3: Batch replacement scheme used in moving super-batches, as compared
to standard mini-batch replacement. At each iteration a single mini-batch is
replaced, in a queue-like manner, creating a high overlap of samples between
consecutive super-batches.

#### Moving Super-batches

We define a moving super-batch as a set of mini-batches which are replaced in
a queue-like manner. That is, in each iteration of the super-batch we replace
part of the mini-batches within it. During each objective evaluation of CMA-
ES, the entire super-batch is run through the model in order to calculate the
first term of (8). The queue-like replacement scheme enables CMA-ES to
encounter new data samples in each objective evaluation, but with a larger
overlap of data samples as compared to standard SGD, where the entire mini-
batch is re-sampled at each iteration. The process is illustrated in Figure 3.
Several strategies for the frequency of replacement can be considered, such as
replacing one or more mini-batches after each objective evaluation, or doing
so every fixed number of evaluations. These different settings are explored in
the ablation study in Section 4.3.

#### Pretraining

Another way to reduce variability in performance, is by reducing sensitivity
to quantization errors. This can be done by pretraining the network, using the
quantization aware training scheme, as described in section 2.1. The bit
allocation for this stage is static, meaning the weights and activations in
all conv layers are quantized to the same target precision, except the first
conv and last full-connected layers, which are always quantized to 8-bit
precision.

###  3.4 Gradient-free Steps

We define gradient-free steps, as steps in which the CMA-ES algorithm
optimizes the bit allocation (given the network’s weights) according to the
objective function in Eq. (8). In each step, multiple generations of samples
of the log-precision vector $\mathbf{v}$ are evaluated on (8). At each
objective evaluation, the sample of $\mathbf{v}$ is used to quantize the
weights and activations of the model. Since CMA-ES typically operates in
continuous spaces, the bit allocations of the weights and activations (which
are positive integers) are extracted from $\mathbf{v}$ using the following
formula:

$\mathbf{r_{W}}=\lceil 2^{\mathbf{v_{W}}}\rceil,\mathbf{r_{X}}=\lceil
2^{\mathbf{v_{X}}}\rceil$ (11)

Where $\lceil x\rceil$ is the ”ceil” operator, which rounds its argument
upwards to the nearest integer. Once the bit allocations have been inserted
into the model, the loss (8) is calculated over all the mini-batches in the
super-batch, yielding the value of the objective for each of the sampled bit-
allocations. This process gradually minimizes the value of the objective
function and enables non-trivial bit-allocations to be found. We define each
gradient-free step to include a predefined number of objective evaluations.
(this a hyper-parater, typically set to 512 evaluations). It is important to
note that gradient-free steps require significantly less computational
resources than traditional epochs, even if the number of mini-batches are
matched. This is because they do not require backpropogation and the gradient-
free optimizer computations are negligible compared to those performed by the
model.

###  3.5 Iterative Alternating Retraining

The primary innovation in this work is the combination of gradient-based
training sessions of the model weights and gradient-free training sessions of
the bit-allocation, which we refer to as iterative alternating retraining.

After the pretraining stage, the model is passed to the gradient-free
optimizer CMA-ES to optimize its bit allocation for a session of a predefined
number of steps $N_{GF}$. This adapts the bit allocation to the model weights,
which are fixed at this stage in their floating point values. This maximizes
the performance of quantized networks, subject to the computational
constraints (Eq. (8)), using the optimization process as described in section
7.

Once the gradient-free session is completed, the best bit allocation found by
CMA-ES is passed to the gradient-based optimizer, for a session of a
predefined number of epochs $N_{GB}$. This adapts the model weights to the bit
allocation, which is kept fixed, using the quantization aware training scheme
described in Section 2.1. Once this session is completed, the model is
returned to the gradient-free optimizer to further improve the bit allocation,
given the new model weights. This cycle is then repeated a number of times, or
until the performance and computational requirements are satisfactory. The
process is illustrated in Fig. 1.

To increase stability in the handover process between the optimization
algorithms, we found it beneficial to restart CMA-ES after each gradient-based
session and handover only the best model weights and bit allocation (with
lowest loss/objective values) found across all sessions, as opposed to handing
over the best versions found in each session.

##  4 Experiments

Figure 4: (a) Convergence plot for a 3 and 4-bit dynamically quantized
ResNet56 on CIFAR10, during the retraining process. Grey regions correspond to
gradient-free steps, while white regions correspond to gradient-based epochs.
(b) The bit allocations for the weights (blue, left) and activations (green,
right) of the 4-bit ResNet56.

To quantitatively compare our dynamic quantization scheme (GradFreeBits) to
other related works, we apply it to several neural network architectures for
image classification tasks. Throughout all the experiments, we consider
similar numbers of bits (on average, in the dynamic case) for the weights and
activations. Since we use the ReLU activation in all the settings, the
activations are quantized using unsigned integers. The weights are quantized
symmetrically using signed integers, so for example, 2-bit quantization will
result in ternary weights in $\\{-1,0,1\\}$.

Furthermore, in this section we also perform an ablation study, to identify
the effects that different settings of the proposed system have on the
performance metrics of the resulting dynamically quantized models.

We compare our approach to the following related works that use uniform
quantization, with either static (S) or dynamic (D) bit-allocation schemes:
LQ-Nets(S) (Zhang et al., 2018a), PACT(S) (Choi et al., 2018), APoT(S) (Li et
al., 2019), DSQ(S) (Gong et al., 2019), BSGD(S) (Yin et al., 2019), TQT(D)
(Jain et al., 2020), MPD(D) (Uhlich et al., 2020), EBS(D)(Li et al., 2020),
EDMIPS(D) (Cai & Vasconcelos, 2020), HAQ(D) (Wang et al., 2019), HAWQ-V1(D)
(Dong et al., 2019), HAWQ-V2(D) (Dong et al., 2020), WNQ(S) (Cai & Li, 2019),
RES(S) (Guo et al., 2017), DoReFa-Net(S) (Zhou et al., 2016). Lastly, we
denote our our proposed method GradFreeBits as GFB(D).

###  4.1 CIFAR 10/100

The CIFAR10 and CIFAR100 image classification benchmarks (Krizhevsky & Hinton,
2009) have 10 and 100 classes respectively, both containing 50k train and 10k
test 32x32 RGB images. For these datasets, pretraining from scratch was
conducted for 400 epochs, using a mini-batch size of 128, SGD optimizer with
momentum of 0.9, cosine learning rate decay, with a maximum learning rate of
0.1 and warm-up of 10 epochs. Data augmentation used during the pretraining
and iterative retraining stages included: random horizontal flips and crops,
and mixup (Zhang et al., 2018b). To approximately satisfy the constraints of
(8), we chose $\beta_{1}=\beta_{2}=0.7$ and $\rho_{1}=\rho_{2}=0.5$. This
allows the penalty constraints to be slightly violated, while keeping model
size and mean precision below their actual targets. We also limit the search
space, such that all values of v are in $[0,3]$.

Given the pretrained model, we applied 5/3 rounds of the iterative alternating
retraining algorithm for CIFAR10/100 respectively. In each round, we applied 4
steps in the gradient-free session and 4/16 epochs in the gradient-based
session for CIFAR10/100 respectively. At each gradient-free step of CMA-ES we
applied 512 objective evaluations on super-batches, each containing 32 mini-
batches of 128 data samples. After each of the 512 objective evaluations we
swap only one mini-batch in the super-batch as illustrated in Fig. 3.3.

Table 1: Top1 accuracy of quantized network on CIFAR10/100. (S) and (D) denote
static and dynamic quantization, while * denotes experiments which use 2-bit
weights and 4-bit activations.
Model | Method | 3/3 | 4/4
---|---|---|---
Res.20 | PACT(S) | 91.1 | 91.7
CIFAR10 | LQ-Nets(S) | 91.6 | -
FP 93.3 | BCGD(S) | 91.2 * | 92.0
| TQT(D) | 90.4 * | -
| MPD(D) | 91.4 * | -
| EBS(D) | 92.7 | 92.9
| GFB(D) (ours) | 93.3 | 93.6
| GFB(D) (ours) |  93.4* | -
Res.56 CIFAR10 | EBS(D) | 94.1 | 94.3
FP 95.1 | GFB(D) (ours) | 94.8 | 94.9
Res.20 | DoReFa-Net(S) | 68.4 | 68.9
CIFAR100 | Res(S) | 68.3 | 68.7
FP 70.35 | LQ-Nets(S) | 68.4 | 69.0
| WNQ(S) | 68.8 | 69.0
| GFB(D) (ours) | 69.6 | 70.6

The results for the CIFAR10 dataset are presented in Table 1. Our method out-
performs the previous state of the art EBS(D) for both ResNet20 and ResNet56
models, at both dynamic precision settings: e.g. +0.7% for 4-bit ResNet20 and
+0.6% for 4-bit ResNet56. Table 1 also includes the results for the CIFAR100
dataset. For this benchmark, our method also outperforms all other related
works: by 1.6 for 4-bit ResNet20 and 0.8 for fore 3-bit ResNet20.

###  4.2 ImageNet

The ImageNet (Russakovsky et al., 2015) image classification benchmark has 1K
classes, 1.2M train and 150K test RGB images. For all models, we used
pretrained weights from TorchVision (Marcel & Rodriguez, 2010). Additional
quantization aware pretraining was then conducted for 30 epochs, using mini-
batches of size 128, SGD optimizer with momentum of 0.9, and a cosine learning
rate decay with a maximum of 0.001 and a warm-up of 3 epochs.

Data augmentations are identical to those used in the CIFAR10/100 experiments
(above), with the addition of image resize to $256\times 256$ and random crops
to $224\times 224$. These are used for both pretraining and iterative
alternating retraining stages. Furthermore, $\beta_{1}=\beta_{2}=0.7$,
$\rho_{1}=\rho_{2}=0.5$ are used to satisfy the constraints and the search
space for v is limited to $[0,3]$. Three rounds of iterative alternating
retraining were applied. In each round, we applied 4 steps in the gradient-
free session and 4 epochs in the gradient-based session. In each gradient-free
step of CMA-ES we applied 512 objective evaluations on super-batches, each
containing 8 mini-batches of 128 data samples, swapping one-minibatch in the
super-batch after each objective evaluation. The entire procedure requires
objective evaluations that are comparable to 47 epochs (30 gradient-based
pretraining epochs, 12 gradient-free steps, and 12 gradient-based epochs).

Table 2: Top1 accuracy of quantized networks on ImageNet. (S) and (D) denote
static and dynamic quantization, ($\cdot$) denotes model size, measured in MB.
$\approx$ is used when only graphical results were available for comparison. *
denotes experiments which use 2-bit weights and 4-bit activations.

Model | Method | 3/3 | 4/4
---|---|---|---
Res.18 | BCGD(S) | - | 67.4(-)
FP 70.7 | LQ-Nets(S) | 68.2(6.1) | 69.3(7.4)
(46.8) | DSQ(S) | 68.7(6.1) | 69.6(7.4)
| PACT(S) | 68.1(6.1) | 69.2(7.4)
| APoT(S) | 69.4(4.6) | -
| EBS(D) | 69.5(-) | 70.2(-)
| EDMIPS(D) |  $\approx$67(-) |  $\approx$68(-)
| TQT(D) | - | 69.5(5.6)
| MPD(D) | - |  70.1(5.4)
| GFB(D) (ours) | 69.2(3.6) |  70.3(5.4)
Res.50 | DoReFa-Net(S) | 69.9(16.6) | 71.4(19.4)
FP 76.4 | LQ-Nets(S) | 74.2(16.6) | 75.1(19.4)
(97.5) | PACT(S) | 75.3(16.6) |  76.5(19.4)
| EDMIPS(D) |  $\approx$72.5(-) |  $\approx$74.0(-)
| HAQ(D) | 75.4(9.2) |  76.1(12.1)
| HAWQ-V1(D) |  75.5(8.0) * | -
| HAWQ-V2(D) |  75.8(8.0) * | -
| GFB(D) (ours) | 75.7(9.6) | 76.1(12.8)

The results for the ImageNet dataset are presented in Table 2. For the Renet18
model, our method slightly outperforms the previous state of the art EBW(D)(Li
et al., 2020) for 4-bits dynamic precision $+0.1\%$, though slightly under-
performs for 3-bits $-0.3\%$. However, both dynamically quantized models
achieve the smallest model size in their category.

For the 3-bit weights and 3-bit ResNet50, our method achieves similar Top1
accuracy to that of HAWQ2(D) (Dong et al., 2020) with 2-bit weights and 4-bit
activations, though with a larger model size $+1.6MB$. However, our 4-bit
ResNet50 falls behind PACT(S) (Choi et al., 2018) in performance $-0.4\%$,
though with a significantly smaller model size $-6.6MB$. This is on par with
the previous state of the art method HAQ(D) (Wang et al., 2019), even though
it uses _non-uniform_ , quantization which can achieve a higher accuracy than
uniform.

For these experiments we can observe the advantage of the dynamically
quantized models compared to the statically quantized ones. Even though the
dynamically quantized models require less memory, they tend to obtain higher
or comparable Top1 accuracy scores.

###  4.3 Ablation Study

In this section we examine the effects that different system settings have on
the performance of our dynamically quantized models. More specifically, we
examine the effects of pretraining, iterative alternating retraining, the
different settings of moving super-batches and the number of mini-batches they
contain. To enable efficient comparison, all experiments are conducted with
4-bit dynamically quantized ResNet20 models on CIFAR100 with the same
hyperparameters used in 4.1. (learning rate, number of gradient-based/free
epochs, etc.).

We consider the following settings for replacing mini-batches in the super-
batch with new batches of randomly selected training samples: NR \- no mini-
batches are replaced in the super-batch, EB \- single mini-batch replacement
after each gradient-free step, EF \- replacement of all mini-batches after
each gradient-free step, SB \- single mini-batch replacement after each
objective evaluation, SF \- replacement of all mini-batches after each
objective evaluation. The test without iterative alternating retraining runs
all gradient-free steps first, followed by all the gradient-based epochs. The
test without pretraining, uses the full-precision model as the initial
weights.

Table 3: Ablation study of a 4-bit dynamically quantized ResNet20 on CIFAR100,
for various system settings. We use the shorthand: ”SS.” for super-batch
setting, ”NMB.” for number of mini-batches in the super-batch, ”IT.-RET.” for
iterative alternating retraining, ”PRET.” for pretraining and ”ACC.” for
accuracy.
variable | ss. | nmb. | it.-ret. | pret. | Acc.
---|---|---|---|---|---
Baseline | SB | 32 | $\surd$ | $\surd$ | 70.61
Components | SB | 32 | $\surd$ | $\times$ | 66.99
| SB | 32 | $\times$ | $\surd$ | 70.43
Super-batch | NR | 32 | $\surd$ | $\surd$ | 70.21
Setting | EB | 32 | $\surd$ | $\surd$ | 70.36
| EF | 32 | $\surd$ | $\surd$ | 70.26
| SF | 32 | $\surd$ | $\surd$ | 70.39
Super-batch | SB | 4 | $\surd$ | $\surd$ | 69.68
Size | SB | 8 | $\surd$ | $\surd$ | 70.25
| SB | 16 | $\surd$ | $\surd$ | 70.18
| SB | 64 | $\surd$ | $\surd$ | 70.26

The results of the ablations study are presented in Table 3. The $-3.6\%$
accuracy degradation demonstrates that pretraining plays a crucial role in
reducing performance degradation due to changes in bit-allocation. It also
seems that iterative alternating retraining, as opposed to separating the bit-
optimization and weight-optimization stages, leads to a small $+0.2\%$
increase in performance, demonstrating the added value of this approach.
Regarding the super-batch settings, it seems that the optimal setting is to
use 32 mini-batches and replace a single batch after each objective evaluation
(SB), also leading to a performance increase of $+0.2\%$. For these reasons,
we used these settings used in the rest of the experiments.

##  5 Discussion

Though the proposed method achieves favorable trade-offs between performance
and model size, several items need be taken into account when applying it to
new problems.

First, since CMA-ES is designed to operate in continuous search spaces and the
search space considered here is discrete, rounding operations are required to
ensure compatibility (Eq. (11)). This creates plateaus of constant values in
the objective function, which may harm the convergence rate. To tackle this,
we may use other gradient-free algorithms, which are more suitable for
discrete optimization, and may lead to even better results using our
framework.

Secondly, though this work shows that the CMA-ES optimizer is highly effective
in a variety of QNNs, applying it to larger networks (such as EfficientNet B7
(Tan & Le, 2019)) may require more generations and objective evaluations in
order to achieve the comparable improvements in the performance and
compression rate. This is because the convergence rate of CMA-ES is typically
$O(L^{2})$ (see section (7)), where $L$ is the number of layers. That said, if
these consideration are taken into account, the combination of gradient-based
and gradient-free optimization methods can be applied to achieve highly
competitive results.

##  6 Conclusion

We proposed GradFreeBits, a novel framework for optimizing the bit-allocation
in dynamically quantized neural networks, which enables neural networks to be
customized to meet multiple hardware constraints. The framework is based on
the combination of a gradient-based quantization aware training scheme for the
weights and gradient-free optimization of the bit-allocation, based on CMA-ES.
By benchmarking our method on multiple image classification tasks, we find
that our method often outperforms several related dynamic and static
quantization methods, in both accuracy and model size. We believe our method
will help accelerate the deployment of low-precision neural network on
resource constrained edge-devices, by enabling the network compression to be
tailored to the specific hardware requirements. Additionally, the proposed
framework for combining gradient-free and gradient-based optimization in an
iterative alternating retraining scheme is quite general, making it likely
easy to apply to other applications.

Future work in this direction includes utilizing additional constraints, such
as FLOPS count and measurements from hardware simulators (such as BISMO
(Umuroglu et al., 2018)) - including inference time, power consumption and
chip area. Furthermore, it is important to evaluate this method on new tasks
such as object detection and semantic segmentation, as these tasks are more
difficult than image classification, perhaps making the models more sensitive
to changes in bit allocation. We hope this framework will provide a foundation
for future works related to the combination of gradient-free and gradient-
based neural network training, and are looking forward to more contributions
in this direction.

## References

  * Banner et al. (2019) Banner, R., Nahshan, Y., and Soudry, D.  Post training 4-bit quantization of convolutional networks for rapid-deployment.  _In Advances in Neural Information Processing Systems (pp. 7950-7958)_ , 2019.
  * Bengio et al. (2013) Bengio, Y., Léonard, N., and Courville, A.  Estimating or propagating gradients through stochastic neurons for conditional computation.  _CoRR_ , abs/1308.3432, 2013.  URL http://arxiv.org/abs/1308.3432.
  * Bertsekas (2014) Bertsekas, D.  Constrained optimization and lagrange multiplier methods.  _Academic press_ , 2014.
  * Blalock et al. (2020) Blalock, D., Ortiz, J., Frankle, J., and Guttag, J.  What is the state of neural network pruning?  _Machine Learning and Systems (MLSys)_ , 2020.
  * Brown et al. (2020) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., and Agarwal, S.  Language models are few-shot learners.  _Advances in Neural Information Processing Systems (NeurIPS), 33_ , 2020.
  * Cai & Li (2019) Cai, W. and Li, W.  Weight normalization based quantization for deep neural network compression.  _CoRR_ , abs/1907.00593, 2019.  URL http://arxiv.org/abs/1907.00593.
  * Cai & Vasconcelos (2020) Cai, Z. and Vasconcelos, N.  Rethinking differentiable search for mixed-precision neural networks.  _In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 2349-2358)_ , 2020.
  * Chen et al. (2020) Chen, Y., Xie, Y., Song, L., Chen, F., and Tang, T.  A survey of accelerator architectures for deep neural networks.  _Engineering_ , 6(3):264—274, 2020.  ISSN 2095-8099.  doi: https://doi.org/10.1016/j.eng.2020.01.007.
  * Cheng et al. (2018) Cheng, Y., Wang, D., Zhou, P., and Zhang, T.  Model compression and acceleration for deep neural networks: The principles, progress, and challenges.  _IEEE Signal Processing Magazine_ , 35(1):126–136, 2018.
  * Choi et al. (2018) Choi, J., Wang, Z., Venkataramani, S., Chuang, P. I.-J., Srinivasan, V., and Gopalakrishnan, K.  Pact: Parameterized clipping activation for quantized neural networks.  _CoRR_ , abs/1805.06085, 2018.  URL http://arxiv.org/abs/1805.06085.
  * Conn et al. (2009) Conn, A. R., Scheinberg, K., and Vicente, L. N.  _Introduction to derivative-free optimization_.  SIAM, 2009.
  * Dong et al. (2019) Dong, Z., Yao, Z., Gholami, A., Mahoney, M. W., and Keutzer, K.  Hawq: Hessian aware quantization of neural networks with mixed-precision.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pp. 293–302, 2019.
  * Dong et al. (2020) Dong, Z., Yao, Z., Cai, Y., Arfeen, D., Gholami, A., Mahoney, M. W., and Keutzer, K.  Hawq-v2: Hessian aware trace-weighted quantization of neural networks.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 2020\.
  * Elthakeb et al. (2018) Elthakeb, A. T., Pilligundla, P., Mireshghallah, F., Yazdanbakhsh, A., Gao, S., and Esmaeilzadeh, H.  Releq: an automatic reinforcement learning approach for deep quantization of neural networks.  _NeurIPS Workshop on ML for Systems_ , 2018.
  * Gong et al. (2019) Gong, R., Liu, X., Jiang, S., Li, T., Hu, P., Lin, J., Yu, F., and Yan, J.  Differentiable soft quantization: Bridging full-precision and low-bit neural networks.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pp. 4852–4861, 2019.
  * Gou et al. (2020) Gou, J., Yu, B., Maybank, S., and Tao, D.  Knowledge distillation: A survey.  _CoRR_ , abs/2006.05525, 2020.  URL https://arxiv.org/abs/2006.05525.
  * Guo et al. (2017) Guo, Y., Yao, A.and Zhao, H., and Chen, Y.  Network sketching: Exploiting binary structure in deep cnns.  _In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (pp. 5955-5963)_ , 2017.
  * Hansen (2009) Hansen, N.  Benchmarking a bi-population cma-es on the bbob-2009 function testbed.  _Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers (pp. 2389-2396)_ , 2009.
  * Hansen (2016) Hansen, N.  The cma evolution strategy: A tutorial.  _arXiv preprint arXiv:1604.00772_ , 2016.
  * Hansen et al. (2003) Hansen, N., Müller, S. D., and Koumoutsakos, P.  Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (cma-es).  _Evolutionary computation_ , 11(1):1–18, 2003\.
  * Heidrich-Meisner & Igel (2008) Heidrich-Meisner, V. and Igel, C.  Evolution strategies for direct policy search.  In _International Conference on Parallel Problem Solving from Nature_ , pp. 428–437. Springer, 2008.
  * Hubara et al. (2017) Hubara, I., Courbariaux, M., Soudry, D., El-Yaniv, R., and Bengio, Y.  Quantized neural networks: Training neural networks with low precision weights and activations.  _The Journal of Machine Learning Research_ , 18(1):6869–6898, 2017.
  * Jain et al. (2020) Jain, S. R., Gural, A., Wu, M., and Dick, C. H.  Trained quantization thresholds for accurate and efficient fixed-point inference of deep neural networks.  _Machine Learning and Systems (MLSys)_ , 2020.
  * Johnson & Zhang (2013) Johnson, R. and Zhang, T.  Accelerating stochastic gradient descent using predictive variance reduction.  _Advances in neural information processing systems, 26, pp.315-323._ , 2013.
  * Jung et al. (2019) Jung, S., Son, C., Lee, S., Son, J., Han, J.-J., Kwak, Y., Hwang, S. J., and Choi, C.  Learning to quantize deep networks by optimizing quantization intervals with task loss.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 4350–4359, 2019.
  * Kolesnikov et al. (2020) Kolesnikov, A., Beyer, L., Zhai, X., Puigcerver, J., Yung, J., Gelly, S., and Houlsby, N.  Big transfer (bit): General visual representation learning.  12350:491–507, 2020.
  * Krizhevsky & Hinton (2009) Krizhevsky, A. and Hinton, G.  Learning multiple layers of features from tiny images.  _Advances in neural information processing systems, 26, pp.315-323._ , 2009.
  * Kuang et al. (2019) Kuang, X., Liu, H., Wang, Y., Zhang, Q., Zhang, Q., and Zheng, J.  A cma-es-based adversarial attack on black-box deep neural networks.  _IEEE Access_ , 7:172938–172947, 2019.
  * Li et al. (2019) Li, Y., Dong, X., and Wang, W.  Additive powers-of-two quantization: An efficient non-uniform discretization for neural networks.  _International Conference on Learning Representations (ICLR)_ , 2019\.
  * Li et al. (2020) Li, Y., Wang, W., Bai, H., Gong, R., Dong, X., and Yu, F.  Efficient bitwidth search for practical mixed precision neural network.  _CoRR_ , abs/2003.07577, 2020.  URL https://arxiv.org/abs/2003.07577.
  * Loshchilov & Hutter (2016) Loshchilov, I. and Hutter, F.  Cma-es for hyperparameter optimization of deep neural networks.  _arXiv preprint arXiv:1604.07269_ , 2016.
  * Marcel & Rodriguez (2010) Marcel, S. and Rodriguez, Y.  Torchvision the machine-vision package of torch.  _In Proceedings of the 18th ACM international conference on Multimedia (pp. 1485-1488)._ , 2010.
  * Neshat et al. (2020) Neshat, M., Alexander, B., and Wagner, M.  A hybrid cooperative co-evolution algorithm framework for optimising power take off and placements of wave energy converters.  _Information Sciences_ , 534:218–244, 2020.
  * Ren et al. (2020) Ren, P., Xiao, Y., Chang, X., Huang, P., Li, Z., Chen, X., and Wang, X.  A comprehensive survey of neural architecture search: Challenges and solutions.  _CoRR_ , abs/2006.02903, 2020.  URL https://arxiv.org/abs/2006.02903.
  * Rios & Sahinidis (2013) Rios, L. M. and Sahinidis, N. V.  Derivative-free optimization: a review of algorithms and comparison of software implementations.  _Journal of Global Optimization_ , 56(3):1247–1293, 2013.
  * Russakovsky et al. (2015) Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., and Berg, A.  ImageNet large scale visual recognition challenge.  _International journal of computer vision, 115(3), pp.211-252_ , 2015\.
  * Tan & Le (2019) Tan, M. and Le, Q. V.  EfficientNet: Rethinking model scaling for convolutional neural networks.  97:6105–6114, 2019.
  * Uhlich et al. (2020) Uhlich, S., Mauch, L., Cardinaux, F., Yoshiyama, K., Garcia, J., Tiedemann, S., Kemp, T., and Nakamura, A.  Mixed precision DNNs: All you need is a good parametrization.  _8th International Conference on Learning Representations, (ICLR)_ , 2020.
  * Umuroglu et al. (2018) Umuroglu, Y., Rasnayake, L., and Själander, M.  Bismo: A scalable bit-serial matrix multiplication overlay for reconfigurable computing.  _28th IEEE International Conference on Field Programmable Logic and Applications (FPL) (pp. 307-3077)._ , 2018.
  * Volz et al. (2018) Volz, V., Schrum, J., Liu, J., Lucas, S. M., Smith, A., and Risi, S.  Evolving mario levels in the latent space of a deep convolutional generative adversarial network.  In _Proceedings of the Genetic and Evolutionary Computation Conference_ , pp. 221–228, 2018.
  * Wang et al. (2019) Wang, K., Liu, Z., Lin, Y., Lin, J., and Han, S.  HAQ: Hardware-aware automated quantization with mixed precision.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 8612–8620, 2019.
  * Wu et al. (2018) Wu, B., Wang, Y., Zhang, P., Tian, Y., Vajda, P., and Keutzer, K.  Mixed precision quantization of convnets via differentiable neural architecture search.  _CoRR_ , abs/1812.00090, 2018.  URL http://arxiv.org/abs/1812.00090.
  * Yin et al. (2019) Yin, P., Zhang, S., Lyu, J., Osher, S., Qi, Y., and Xin, J.  Blended coarse gradient descent for full quantization of deep neural networks.  _Research in the Mathematical Sciences, 6(1), p.14._ , 2019.
  * Zhang et al. (2018a) Zhang, D., Yang, J., Ye, D., and Hua, G.  Lq-nets: Learned quantization for highly accurate and compact deep neural networks.  In _Proceedings of the European conference on computer vision (ECCV)_ , pp. 365–382, 2018a.
  * Zhang et al. (2018b) Zhang, H., Cisse, M., Dauphin, Y., and Lopez-Paz, D.  Mixup: Beyond empirical risk minimization.  2018b.
  * Zhao et al. (2019) Zhao, R., Hu, Y., Dotzel, J., De Sa, C., and Zhang, Z.  Improving neural network quantization without retraining using outlier channel splitting.  97:7543–7552, 2019.
  * Zhou et al. (2016) Zhou, S., Wu, Y., Ni, Z., Zhou, X., Wen, H., and Zou, Y.  Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients.  _CoRR_ , abs/1606.06160, 2016.  URL http://arxiv.org/abs/1606.06160.

##  7 Appendix: CMA-ES

In this section we provide a very brief overview of the main derivations that
are used in CMA-ES, without including any theoretical background for the
structure of these update rules, or the choices of hyperparameters. For more
details regarding these topics, we refer the curious reader to (Hansen,
2016)—we follows the same notation as this paper here.

Covariance Matrix Adaptation Evolution Strategies (CMA-ES) (Hansen et al.,
2003), is a population based gradient-free optimization algorithm. At a high
level, the optimization process of CMA-ES is as follows. At the $g$-th
generation, a set of $\lambda$ $d$-dimensional samples
$\boldsymbol{x}_{k}\in\mathbb{R}^{d}$ are drawn from a multivariate normal
distribution $\mathcal{N}(m^{(g)},\mathcal{C}^{(g)})$:

$\boldsymbol{x}_{k}^{(g+1)}\sim\boldsymbol{m}^{(g)}+\sigma^{(g)}\mathcal{N}\left(\mathbf{0},\boldsymbol{C}^{(g)}\right),\mbox{
for }k=1,...,\lambda$ (12)

Where $\boldsymbol{m}^{(g)}$, $\boldsymbol{C}^{(g)}$ are the mean and
covariance matrix of the population at the previous generation, respectively.
$\lambda$ is the population size and $\sigma^{(g)}$ is the step-size.

Once the samples are drawn from this distribution, they are evaluated and
ranked based on their objective function values. These ranked samples
$\boldsymbol{x}_{i:\lambda}^{(g+1)}$ are used to calculate $m^{(g+1)}$,
$\mathcal{C}^{(g+1)}$ and $\sigma^{(g+1)}$ of the next generation, using a set
of update rules which are provided below.

###  7.1 Hyperparameters

CMA-ES uses several hyperparameters in order to perform optimization (Hansen,
2016). These include a dampling parameter $d_{\sigma}$ and
$c_{1},c_{\mu},c_{\mathrm{c}},c_{\mathrm{m}},c_{\sigma}$ which are
”momentum”-like parameters, which control the amount of information retained
from previous generations. Furthremore, $w_{i}$ are known as the
”recombination weights”, which are used in most update rules. They are
typically chosen such that

$\sum_{j=1}^{\lambda}w_{j}\approx 0,\quad\sum_{i=1}^{\mu}w_{i}=1,\quad
w_{1}\geq\cdots\geq w_{\mu}>0.$ (13)

These are also used to calculate the effective population size for
recombination:
$\mu_{\mathrm{eff}}=\left(\sum_{i=1}^{\mu}w_{i}^{2}\right)^{-1}$. For more
details regarding the specific choices of these hyparamerameters, please refer
to (Hansen, 2016).

###  7.2 Mean Update Rule

As mentioned above, several update rules are employed in CMA-ES. The first of
those is the update of the mean $\boldsymbol{m}^{(g+1)}$:

$\boldsymbol{m}^{(g+1)}=\boldsymbol{m}^{(g)}+c_{\mathrm{m}}\sum_{i=1}^{\mu}w_{i}\left(\boldsymbol{x}_{i:\lambda}^{(g+1)}-\boldsymbol{m}^{(g)}\right).$
(14)

###  7.3 Covariance Matrix Update Rule

The covariance matrix requires auxiliary vectors in order to construct its
update rule, these are calculated using:

$\displaystyle\boldsymbol{p}_{\mathrm{c}}^{(g+1)}$ $\displaystyle=$
$\displaystyle\left(1-c_{\mathrm{c}}\right)\boldsymbol{p}_{\mathrm{c}}^{(g)}+\tilde{c}_{\mathrm{c}}\frac{\boldsymbol{m}^{(g+1)}-\boldsymbol{m}^{(g)}}{\sigma^{(g)}}$
(15) $\displaystyle\boldsymbol{y}_{i:\lambda}^{(g+1)}$ $\displaystyle=$
$\displaystyle\left(\boldsymbol{x}_{i:\lambda}^{(g+1)}-\boldsymbol{m}^{(g)}\right)/\sigma^{(g)},$
(16)

where
$\tilde{c}_{\mathrm{c}}=\sqrt{c_{\mathrm{c}}\left(2-c_{\mathrm{c}}\right)\mu_{\mathrm{eff}}}$.
These auxiliary vectors are then used to construct the rank-$\mu$ and rank-$1$
update matrices:

$\displaystyle\boldsymbol{C}_{\mu}^{(g+1)}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{\lambda}w_{i}\boldsymbol{y}_{i:\lambda}^{(g+1)}\left(\boldsymbol{y}_{i:\lambda}^{(g+1)}\right)^{\boldsymbol{\top}}$
(17) $\displaystyle\boldsymbol{C}_{1}^{(g+1)}$ $\displaystyle=$
$\displaystyle\boldsymbol{p}_{\mathrm{c}}^{(g+1)}\boldsymbol{p}_{\mathrm{c}}^{(g+1)^{\top}}.$
(18)

Finally, by defining
$c_{old}=\left(1-c_{1}-c_{\mu}\sum_{i=1}^{\lambda}w_{i}\right)$, we get the
update rule for the covariance matrix:

$\boldsymbol{C}^{(g+1)}=c_{old}\boldsymbol{C}^{(g)}+c_{1}\boldsymbol{C}_{1}^{(g)}+c_{\mu}\boldsymbol{C}_{\mu}^{(g+1)}.$
(19)

###  7.4 Step Size Update Rule

The last update rule is for the step size, which also requires use of an
auxiliary vector:

$\boldsymbol{p}_{\sigma}^{(g+1)}=\left(1-c_{\sigma}\right)\boldsymbol{p}_{\sigma}^{(g)}+\tilde{c}_{\sigma}\boldsymbol{C}^{(g)^{-\frac{1}{2}}}\frac{\boldsymbol{m}^{(g+1)}-\boldsymbol{m}^{(g)}}{\sigma^{(g)}},$
(20)

Where
$\tilde{c}_{\sigma}=\sqrt{c_{\sigma}\left(2-c_{\sigma}\right)\mu_{\mathrm{eff}}}$.
This is then used to construct the last update rule, which is for the step
size:

$\sigma^{(g+1)}=\sigma^{(g)}\exp\left(\frac{c_{\sigma}}{d_{\sigma}}\left(\frac{\left\|\boldsymbol{p}_{\sigma}^{(g+1)}\right\|}{E\|\mathcal{N}(\mathbf{0},\mathbf{I})\|}-1\right)\right),$
(21)

where
${E\|\mathcal{N}(\mathbf{0},\mathbf{I})\|}\approx\sqrt{n}+\mathcal{O}(1/n)$ is
the expectation of the $l_{2}$ norm of samples drawn from
$\mathcal{N}(\mathbf{0},\mathbf{I})$.

###  7.5 Next Generation

Once $\boldsymbol{m}^{(g+1)}$, $\boldsymbol{C}^{(g+1)}$ and $\sigma^{(g+1)}$
have been calculated, they are inserted into (12), so that the next generation
of samples can be drawn and the process repeated, until the convergence
criteria are full-filled.