summaries: This study presents a deep reinforcement learning method, Advantage-Weighted Regression (AWR). The policy update of AWR is constrained as in a similar manner as REPS (Peters et al., 2010). Although the benefit of AWR is not clear in the reinforcement learning tasks, AWR exhibits its advantages in the context of imitation learning and off-policy learning with static datasets.

summaries: This paper focuses on developing an RL learning algorithm that is simple and can significantly improve performance over existing algorithms. The paper presents the algorithm AWR, which is an extension of the algorithm reward weighted regression. The primary extensions of RWR are using the advantage function instead of the q function and the ability to use experience replay. Experiments on common environments are conducted to evaluate the performance of AWR and compare it to other algorithms. There are ablation experiments to justify the choice of some of the extensions.

summaries: This paper presents a reinforcement learning algorithm that applies advantage-weighted regression. In each iteration, it samples trajectories from a mixture of previous policies, estimates the value function and then computes the advantage value to estimate the policy. The idea is very similar to the work published in “Neumann, Gerhard and Peters, Jan R, Fitted Q-iteration by advantage weighted regression, Advances in neural information processing systems, 2009”, starting from reward-weighted regression and further developing to advantage weighted regression.  The difference in this paper is to add a constraint on the policy search, requiring the policy to be similar to the sampling policy. However, this constraint has also been studied in the paper "Christian Wirth and Johannes Furnkranz and Gerhard Neumann, Model-Free Preference-based Reinforcement Learning, AAAI 2017" (It seems not in reference). Overall, it may enhance this paper if it has more technical novelty when developing a new algorithm.

abstractText: In this work, we aim to develop a simple and scalable reinforcement learning algorithm that uses standard supervised learning methods as subroutines, while also being able to leverage off-policy data. Our proposed approach, which we refer to as advantage-weighted regression (AWR), consists of two standard supervised learning steps: one to regress onto target values for a value function, and another to regress onto weighted target actions for the policy. The method is simple and general, can accommodate continuous and discrete actions, and can be implemented in just a few lines of code on top of standard supervised learning methods. We provide a theoretical motivation for AWR and analyze its properties when incorporating off-policy data from experience replay. We evaluate AWR on a suite of standard OpenAI Gym benchmark tasks, and show that it achieves competitive performance compared to a number of well-established state-of-the-art RL algorithms. AWR is also able to acquire more effective policies than most off-policy algorithms when learning from purely static datasets with no additional environmental interactions. Furthermore, we demonstrate our algorithm on challenging continuous control tasks with highly complex simulated characters. (Video1)

authors:
Abbas Abdolmaleki
Jost Tobias Springenberg
Jonas Degrave
Steven Bohez
Yuval Tassa
Dan Belov
Nicolas Manfred Otto Heess
Martin A. Riedmiller

title: Relative entropy regularized policy

venue: iteration. ArXiv,

authors:
Abbas Abdolmaleki
Jost Tobias Springenberg
Yuval Tassa
Remi Munos
Nicolas Heess
Martin Riedmiller

title: Maximum a posteriori policy optimisation

venue: In International Conference on Learning Representations,

authors:
Yan Duan
Xi Chen
Rein Houthooft
John Schulman
Pieter Abbeel

title: Benchmarking deep reinforcement learning for continuous control

venue: In ICML,

authors:
Justin Fu
Aviral Kumar
Matthew Soh
Sergey Levine

title: Diagnosing bottlenecks in deep qlearning algorithms

venue: In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning,

authors:
Scott Fujimoto
Herke van Hoof
David Meger

title: Addressing function approximation error in actor-critic methods

venue: Proceedings of the 35th International Conference on Machine Learning,

authors:
Scott Fujimoto
David Meger
Doina Precup

title: Off-policy deep reinforcement learning without exploration

authors:
Shixiang Gu
Timothy Lillicrap
Ilya Sutskever
Sergey Levine

title: Continuous deep q-learning with model-based acceleration

venue: Proceedings of The 33rd International Conference on Machine Learning,

authors:
Tuomas Haarnoja
Aurick Zhou
Pieter Abbeel
Sergey Levine

title: Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor

authors:
Hirotaka Hachiya
Takayuki Akiyama
Masashi Sugiayma
Jan Peters

title: Adaptive importance sampling for value function approximation in off-policy reinforcement learning

venue: Neural Netw.,

authors:
Danijar Hafner
James Davidson
Vincent Vanhoucke

title: Tensorflow agents: Efficient batched reinforcement learning in tensorflow

authors:
Hado van Hasselt
Arthur Guez
David Silver

title: Deep reinforcement learning with double q-learning

venue: In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence,

authors:
Nicolas Heess
Dhruva TB
Srinivasan Sriram
Jay Lemmon
Josh Merel
Greg Wayne
Yuval Tassa
Tom Erez
Ziyu Wang
S.M. Ali Eslami
Martin A. Riedmiller
David Silver

title: Emergence of locomotion behaviours in rich environments

authors:
Matteo Hessel
Joseph Modayil
Hado van Hasselt
Tom Schaul
Georg Ostrovski
Will Dabney
Daniel Horgan
Bilal Piot
Mohammad Gheshlaghi Azar
David Silver

title: Rainbow: Combining improvements in deep reinforcement learning

authors:
Sham Kakade
John Langford

title: Approximately optimal approximate reinforcement learning

venue: In Proceedings of the Nineteenth International Conference on Machine Learning,

authors:
Jens Kober
Jan R. Peters

title: Policy search for motor primitives in robotics

venue: Advances in Neural Information Processing Systems

authors:
Aviral Kumar
Justin Fu
George Tucker
Sergey Levine

title: Stabilizing off-policy q-learning via bootstrapping error reduction

authors:
Timothy P. Lillicrap
Jonathan J. Hunt
Alexander Pritzel
Nicolas Manfred Otto Heess
Tom Erez
Yuval Tassa
David Silver
Daan Wierstra

title: Continuous control with deep reinforcement learning

authors:
Nicolas Meuleau
Leonid Peshkin
Leslie P. Kaelbling
Kee eung Kim

title: Off-policy policy search

venue: Technical report,

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei A. Rusu
Joel Veness
Marc G. Bellemare
Alex Graves
Martin Riedmiller
Andreas K. Fidjeland
Georg Ostrovski
Stig Petersen
Charles Beattie
Amir Sadik
Ioannis Antonoglou
Helen King
Dharshan Kumaran
Daan Wierstra
Shane Legg
Demis Hassabis

title: Human-level control through deep reinforcement learning

authors:
Rémi Munos
Thomas Stepleton
Anna Harutyunyan
Marc G. Bellemare

title: Safe and efficient off-policy reinforcement learning

venue: In Proceedings of the 30th International Conference on Neural Information Processing Systems,

authors:
Vinod Nair
Geoffrey E. Hinton

title: Rectified linear units improve restricted boltzmann machines

venue: In Proceedings of the 27th International Conference on International Conference on Machine Learning,

title: Variational inference for policy search in changing situations

venue: In Proceedings of the 28th International Conference on International Conference on Machine Learning,

authors:
Gerhard Neumann
Jan R. Peters

title: Fitted q-iteration by advantage weighted regression

authors:
Junhyuk Oh
Yijie Guo
Satinder Singh
Honglak Lee

title: Self-imitation learning

authors:
Deepak Pathak
Pulkit Agrawal
Alexei A. Efros
Trevor Darrell

title: Curiosity-driven exploration by self-supervised prediction

venue: In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops,

authors:
Xue Bin Peng
Pieter Abbeel
Sergey Levine
Michiel van de Panne

title: Deepmimic: Exampleguided deep reinforcement learning of physics-based character skills

venue: ACM Trans. Graph.,

authors:
Jan Peters
Stefan Schaal

title: Reinforcement learning by reward-weighted regression for operational space control

venue: In Proceedings of the 24th International Conference on Machine Learning,

authors:
Jan Peters
Katharina Mülling
Yasemin Altün

title: Relative entropy policy search

venue: In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence,

authors:
Doina Precup
Richard S. Sutton
Sanjoy Dasgupta

title: Off-policy temporal difference learning with function approximation

venue: In Proceedings of the Eighteenth International Conference on Machine Learning,

authors:
Aravind Rajeswaran
Vikash Kumar
Abhishek Gupta
Giulia Vezzani
John Schulman
Emanuel Todorov
Sergey Levine

title: Learning Complex Dexterous Manipulation with Deep Reinforcement Learning and Demonstrations

venue: In Proceedings of Robotics: Science and Systems (RSS),

authors:
John Schulman
Sergey Levine
Pieter Abbeel
Michael Jordan
Philipp Moritz

title: Trust region policy optimization

venue: Proceedings of the 32nd International Conference on Machine Learning,

authors:
John Schulman
Filip Wolski
Prafulla Dhariwal
Alec Radford
Oleg Klimov

title: Proximal policy optimization algorithms. CoRR, abs/1707.06347, 2017

authors:
Richard S. Sutton
Andrew G. Barto

title: Introduction to Reinforcement Learning

authors:
Richard S Sutton
David A. McAllester
Satinder P. Singh
Yishay Mansour

title: Policy gradient methods for reinforcement learning with function approximation

authors:
Qing Wang
Jiechao Xiong
Lei Han
peng sun
Han Liu
Tong Zhang

title: Exponentially weighted imitation learning for batched historical data

authors:
Ziyu Wang
Victor Bapst
Nicolas Heess
Volodymyr Mnih
Rémi Munos
Koray Kavukcuoglu
Nando de Freitas

title: Sample efficient actor-critic with experience

venue: replay. CoRR,

title: Simple statistical gradient-following algorithms for connectionist reinforcement learning

venue: Mach. Learn.,

heading: 1 INTRODUCTION

text:
Model-free reinforcement learning can be a general and effective methodology for training agents to acquire sophisticated behaviors with minimal assumptions on the underlying task. However, RL algorithms can be substantially more complex to implement and tune than standard supervised learning methods. Arguably the simplest reinforcement learning methods are policy gradient algorithms (Sutton et al., 2000), which directly differentiate the expected return and perform gradient ascent. Unfortunately, these methods can be notoriously unstable and are typically on-policy, often requiring a substantial number of samples to learn effective behaviors. Our goal is to develop an RL algorithm that is simple, easy to implement, and can readily incorporate off-policy data.
In this work, we propose advantage-weighted regression (AWR), a simple off-policy algorithm for model-free RL. Each iteration of the AWR algorithm simply consists of two supervised regression steps: one for training a value function baseline via regression onto cumulative rewards, and another for training the policy via weighted regression. The complete algorithm is shown in Algorithm 1. AWR can accommodate continuous and discrete actions, and can be implemented in just a few lines of code on top of standard supervised learning methods. Despite its simplicity, we find that AWR achieves competitive results when compared to commonly used on-policy and off-policy RL algorithms, and can effectively incorporate fully off-policy data, which has been a challenge for other RL algorithms. Our derivation presents an interpretation of AWR as a constrained policy optimization procedure, and provides a theoretical analysis of the use of off-policy data with experience replay.
We first revisit the original formulation of reward-weighted regression (RWR) (Peters & Schaal, 2007), an on-policy RL method that utilizes supervised learning to perform policy updates, and then propose a number of new design decisions that significantly improve performance on a suite of standard control benchmark tasks. We then provide a theoretical analysis of AWR, including the capability to incorporate off-policy data with experience replay. Although the design of AWR involves only a few simple design decisions, we show experimentally that these additions provide for a large improvement over previous methods for regression-based policy search, such as RWR,
1Supplementary video: sites.google.com/view/awr-supp/
while also being substantially simpler than more modern methods, such as MPO (Abdolmaleki et al., 2018b). We show that AWR achieves competitive performance when compared to several well-established state-of-the-art on-policy and off-policy algorithms.

heading: 2 PRELIMINARIES

text:
In reinforcement learning, the objective is to learn a policy that maximizes an agent’s expected return. At each time step t, the agent observes the state of the environment st, and samples an action from a policy at ∼ π(at|st). The agent then applies that action, which results in a new state st+1 and a scalar reward rt = r(st,at). The goal is to learn a policy that maximizes the expected return J(π),
J(π) = Eτ∼pπ(τ) [ ∞∑ t=0 γtrt ] = Es∼dπ(s),a∼π(a|s) [r(s,a)] , (1)
where pπ(τ) represents the likelihood of a trajectory τ = {(s0,a0, r0) , (s1,a1, r1) , ...} under a policy π, and γ ∈ [0, 1) is the discount factor. dπ(s) = ∑∞ t=0 γ
tp(st = s|π) represents the unnormalized discounted state distribution induced by the policy π (Sutton & Barto, 1998), and p(st = s|π) is the likelihood of the agent being in state s after following π for t timesteps. Our proposed AWR algorithm builds on ideas from reward-weighted regression (RWR) (Peters & Schaal, 2007), a policy search algorithm based on an expectation-maximization framework. At each iteration, the E-step constructs an estimate of the optimal policy according to π∗(a|s) ∝ πk(a|s)exp (Rs,a/β), where πk represents the policy at the kth iteration, Rs,a = ∑∞ t=0 γ
trt is the return, and β > 0 is a temperature parameter. Then the M-step projects π∗ onto the space of parameterized policies by solving a supervised regression problem:
πk+1 = arg max π
Es∼dπk (s)Ea∼πk(a|s) [ log π(a|s) exp ( 1 β Rs,a )] . (2)
The RWR update can be interpreted as fitting a new policy πk+1 to samples from the current policy πk, where the likelihood of each action is weighted by the exponentiated return for that action.

heading: 3 ADVANTAGE-WEIGHTED REGRESSION

text:
In this work, we present advantage-weighted regression (AWR), a simple off-policy RL algorithm based on reward-weighted regression. We first provide an overview of the AWR algorithm, and then describe its theoretical motivation and analyze its properties. The AWR algorithm is summarized in Algorithm 1. Each iteration k of AWR consists of the following simple steps. First, the current policy πk(a|s) is used to sample a batch of trajectories {τi} that are then stored in the replay buffer D, which is structured as a first-in first-out (FIFO) queue (Mnih et al., 2015). Then, a value function V Dk (s) is fitted to all trajectories in the replay buffer D, which can be done with simple Monte Carlo return estimatesRDs,a = ∑T t=0 γ
trt. Finally, the same buffer is used to fit a new policy using advantage-weighted regression, where each state-action pair in the buffer is weighted according to the exponentiated advantage exp( 1βA
D(s,a)), with the advantage given by AD(s,a) = RDs,a − V D(s) and β is a hyperparameter. In the following subsections, we first motivate AWR as a constrained policy search problem, and then extend our analysis to incorporate experience replay.

heading: 3.1 DERIVATION

text:
In this section, we derive the AWR algorithm as an approximate optimization of a constrained policy search problem. Our goal is to find a policy that maximizes the expected improvement η(π) = J(π)− J(µ) over a sampling policy µ(a|s). We first derive AWR for the setting where the sampling policy is a single Markovian policy. Then, in the next section, we extend our result to data from multiple policies, as in the case of experience replay. The expected improvement η(π) can be expressed in terms of the advantage Aµ(s,a) = Rµs,a − V µ(s) with respect to µ (Kakade & Langford, 2002; Schulman et al., 2015):
η(π) = Es∼dπ(s)Ea∼π(a|s) [ Rµs,a − V µ(s) ] , (3)
where Rµs,a denotes the return obtained by performing action a in state s and following µ for the following timesteps, and V µ(s) = ∫ a µ(a|s)Ras da corresponds to the value function of µ. This objective differs from the ones used in the derivations of related algorithms, such as RWR and
Algorithm 1 Advantage-Weighted Regression 1: π1 ← random policy 2: D ← ∅ 3: for iteration k = 1, ..., kmax do 4: add trajectories {τi} sampled via πk to D 5: V Dk ← arg minV Es,a∼D
[∣∣∣∣RDs,a − V (s)∣∣∣∣2] 6: πk+1 ← arg maxπ Es,a∼D [ log π(a|s)exp ( 1 β ( RDs,a − V Dk (s)
))] 7: end for
REPS (Peters & Schaal, 2007; Peters et al., 2010; Abdolmaleki et al., 2018b), which maximize the expected return J(π) instead of the expected improvement. The expected improvement directly gives rise to an objective that involves the advantage. We will see later that this yields a policy update that differ in a subtle but important way from standard RWR. As we show in our experiments, this difference results in a large empirical improvement.
The objective in Equation 3 can be difficult to optimize due to the dependency between dπ(s) and π, as well as the need to collect samples from π. Following Schulman et al. (2015), we can instead optimize an approximation η̂(π) of η(π) using the state distribution of µ:
η̂(π) = Es∼dµ(s)Ea∼π(a|s) [ Rµs,a − V µ(s) ] . (4)
Here, η̂(π) matches η(π) to first order (Kakade & Langford, 2002), and provides a good estimate of η if π and µ are close in terms of the KL-divergence (Schulman et al., 2015). Using this objective, we can formulate the following constrained policy search problem:
arg max π ∫ s dµ(s) ∫ a π(a|s) [ Rµs,a − V µ(s) ] da ds (5)
s.t. ∫ s dµ(s)DKL (π(·|s)||µ(·|s)) ds ≤ . (6)
The constraint in Equation 6 ensures that the new policy π is close to the data distribution of µ, and therefore the surrogate objective η̂(π) remains a reasonable approximation to η(π). We refer the reader to Schulman et al. (2015) for a detailed derivation and an error bound.
We can derive AWR as an approximate solution to this constrained optimization. This derivation follows a similar procedure as Peters et al. (2010), and begins by forming the Lagrangian of the optimization problem presented above,
L(π,β) = ∫ s dµ(s) ∫ a π(a|s) [ Rµs,a − V µ(s) ] da ds + β ( − ∫ s dµ(s)DKL (π(·|s)||µ(·|s)) ds ) , (7) where β is a Lagrange multiplier. Differentiating L(π, β) with respect to π(a|s) and solving for the optimal policy π∗ results in the following expression for the optimal policy
π∗(a|s) = 1 Z(s)
µ(a|s) exp ( 1
β
( Rµs,a − V µ(s) )) , (8)
with Z(s) being the partition function. A detailed derivation is available in Appendix A. If π is represented by a function approximator (e.g., a neural network), a new policy can be obtained by projecting π∗ onto the manifold of parameterized policies,
arg min π
Es∼D [DKL (π∗(·|s)||π(·|s))] (9)
= arg max π
Es∼dµ(s)Ea∼µ(a|s) [ log π(a|s)exp ( 1
β
( Rµs,a − V µ(s) ))] . (10)
While this derivation for AWR largely follows the derivations used in prior work (Peters et al., 2010; Abdolmaleki et al., 2018b), our expected improvement objective introduces a baseline V µ(s) to the policy update, which as we show in our experiments, is a crucial component for an effective algorithm. A similar advantage-weighting scheme has been previously used for fitted Q-iteration (Neumann & Peters, 2009), where the policy is given by π(a|s) = 1Z(s)exp (( Rµs,a − V µ(s) ) /β ) . In this definition, the likelihood of an action does not depend on the sampling distribution, and therefore does not enforce a trust region with respect to µ.

heading: 3.2 EXPERIENCE REPLAY AND OFF-POLICY LEARNING

text:
A crucial design decision of AWR is the choice of sampling policy µ(a|s). Standard implementations of RWR are typically on-policy, where the sampling policy is selected to be the current policy µ(a|s) = πk(a|s) at iteration k. This can be sample inefficient, as data collected at each iteration are discarded after a single update iteration. Importance sampling can be incorporated into RWR to reuse data from previous iterations, but at the cost of larger variance (Kober & Peters, 2009). Instead, we can improve sample efficiency of AWR by incorporating experience replay and explicitly accounting for training data from a mixture of multiple past policies. As described in Algorithm 1, at each iteration, AWR collects a batch of data using the latest policy πk, and then stores this data in a replay buffer D, which also contains data collected from previous policies {π1, · · · , πk}. The value function and policy are then updated using samples drawn from D. This replay strategy is analogous to modeling the sampling policy as a mixture of policies from previous iterations µk(τ) = ∑k i=1 wiπi(τ), where πi(τ) = p(τ |πi) represents the likelihood of a trajectory τ under a policy πi from the ith iteration, and the weight wi specify the probability of selecting πi.
We now extend the derivation from the previous section to the off-policy setting with experience replay, and show that Algorithm 1 indeed optimizes the expected improvement over a sampling policy modeled by the replay buffer. Given a replay buffer consisting of trajectories from past policies, the joint state-action distribution of µ is given by µ(s,a) = ∑k i=1 widπi(s)πi(a|s), and similarly
for the marginal state distribution dµ(s) = ∑k i=1 widπi(s). The expected improvement can now be expressed with respect to the set of sampling policies in the replay buffer,
η(π) = J(π)− ∑ i wiJ(πi) = Es∼dπ(s)Ea∼π(a|s) [∑ i wiA πi(s,a) ] , (11)
where Aπi(s,a) = Rπis,a − V πi(s) is the advantage with respect to each sampling policy. In Appendix B, we show that the update procedure in Algorithm 1 optimizes the following objective:
arg max π k∑ i=1 wi ( Es∼dπi (s)Ea∼π(a|s) [A πi(s,a)] )
(12)
s.t. Es∼dµ(s) [DKL (π(·|s)||µ(·|s))] ≤ , (13)
where µ(a|s) = µ(s,a)dµ(s) = ∑ i widπi (s)πi(a|s)∑ j wjdπj (s) represents the conditional action distribution defined by the replay buffer. This objective can be solved via the Lagrangian to yield the following update:
arg max π k∑ i=1 wi Es∼dπi (s)Ea∼πi(a|s)
[ log π(a|s)exp ( 1
β
( Rπis,a − ∑ j wjdπj (s)V
πj (s)∑ j wjdπj (s)
))] ,
(14)
where the expectations can be approximated by simply sampling from D following Line 6 of Algorithm 1. A detailed derivation is available in Appendix B. Note, the baseline in the exponent now consists of an average of the value functions of the different policies. This mean value function V̄ (s) can be fitted by simply sampling from the replay buffer following Line 5 of Algorithm 1,
V̄ = arg min V ∑ i wiEs,∼dπi (s),a∼πi(a|s) [ ||Rπis,a − V (s)||2 ] . (15)
The optimal solution V̄ (s) = ∑ i widπi (s)V
πi (s)∑ j wjdπj (s) is exactly the baseline in Equation 14.

heading: 3.3 IMPLEMENTATION DETAILS

text:
Finally, we discuss several important design decisions for a practical implementation of AWR. Monte Carlo estimates can be used to approximate the expected return RDs,a, but this can result in a highvariance estimate. Instead, we approximate RDs,a using TD(λ) to obtain a lower-variance estimate (Sutton & Barto, 1998). TD(λ) is applied by bootstrapping with the value function V Dk−1(s) from the previous iteration. To set the value of the Lagrange multiplier β, we found that a simple adaptive heuristic of setting β to the standard deviation of all advantage values σA in the replay buffer works well in practice. This is akin to the advantage normalization technique commonly used in implementations of algorithms such as PPO (Dhariwal et al., 2017). Details are available in Appendix C.
The weights ωDs,a = exp
(
1 β
(
RDs,a − V D(s)
))
used to update the policy can occasionally assume excessively large values, which causes gradients to explode. Therefore, we apply weight clipping ω̂Ds,a = min ( ωDs,a, ωmax ) with a threshold ωmax to prevent exploding weights.

heading: 4 RELATED WORK

text:
Existing RL methods can be broadly categorized into on-policy and off-policy algorithms (Sutton & Barto, 1998). On-policy algorithms generally update the policy using data collected from the same policy. A popular class of on-policy algorithms is policy gradient methods (Williams, 1992; Sutton et al., 2000), which can be effective for a diverse array of complex tasks (Heess et al., 2017; Pathak et al., 2017; Peng et al., 2018; Rajeswaran et al., 2018). However, on-policy algorithms are typically data inefficient. Off-policy algorithms improve sample efficiency by enabling training using data from other sources, such as data from different agents or data from previous iterations of the algorithm. Importance sampling is a simple strategy for off-policy learning (Sutton & Barto, 1998; Meuleau et al., 2000; Hachiya et al., 2009), but can introduce optimization instabilities due to the large variance of the importance sampling estimator. Dynamic programming methods based on Q-function learning can also leverage off-policy data (Precup et al., 2001; Mnih et al., 2015; Lillicrap et al., 2016; Gu et al., 2016; Haarnoja et al., 2018b). But these methods can be notoriously unstable, and in practice, require a variety of stabilization techniques (Hasselt et al., 2016; Wang et al., 2016; Munos et al., 2016; Hessel et al., 2017; Fujimoto et al., 2018; Fu et al., 2019). Furthermore, it can be difficult to apply these methods to fully off-policy data, where an agent is unable to collect additional environmental interactions (Fujimoto et al., 2019; Kumar et al., 2019).
Policy search can also be formulated under an expectation-maximization framework (Peters et al., 2010; Neumann, 2011; Abdolmaleki et al., 2018b), an early example of which is reward-weighted regression (RWR) (Peters & Schaal, 2007). RWR presents a simple on-policy RL algorithm that casts policy search as a supervised regression problem. A similar algorithm, relative entropy policy search (REPS) (Peters et al., 2010), can also be derived from the dual formulation of a constrained policy search problem. RWR has a number appealing properties: it has a very simple update rule, and since each iteration corresponds to supervised learning, it can be more stable and easier to implement than many of the previously mentioned RL methods. Despite these advantages, RWR has not been shown to be an effective when combined with neural networks (Schulman et al., 2015; Duan et al., 2016). In this work, we propose a number of modifications to the formulation of RWR to produce an effective off-policy deep RL algorithm, while still retaining much of the simplicity of RWR.
The optimization problem being solved in AWR is similar to REPS (Peters et al., 2010), but REPS optimizes the expected return instead of the expected improvement. The weights in REPS also contains a Bellman error term that resembles advantages, but are computed using a linear value function derived from a feature matching constraint. Learning the REPS value function involves minimization of a dual function, which is a complex function of the Bellman error, while the value function in AWR can be learned with simple supervised regression. More recently, Abdolmaleki et al. (2018b) proposed MPO, a deep RL variant of REPS, which applies a partial EM algorithm for policy optimization. The method first fits a Q-function of the current policy via bootstrapping, and then performs a policy improvement step with respect to this Q-function. MPO uses off-policy data for training a Q-function and employs Retrace(λ) for off-policy correction (Munos et al., 2016). In
contrast, AWR is simpler, as it can simply fit a value function to the observed returns in a replay buffer, and performs weighted supervised regression on the actions to fit the policy. Oh et al. (2018) proposed self-imitation learning (SIL), which augments policy gradient algorithms with an auxiliary behaviour cloning loss to reuse samples from past experiences. Unlike SIL, AWR is a standalone algorithm, and does not need to be combined with an auxiliary RL algorithm. Neumann & Peters (2009) proposed LAWER, a kernel-based fitted Q-iteration algorithm where the Bellman error is weighted by the normalized advantage of each state-action pair. This was then followed by a soft-policy improvement step. Similar to Neumann & Peters (2009), AWR also uses exponentiated advantages, but LAWER’s definition of the policy is different from the one in AWR and does not enforce a trust region constraint. Furthermore, AWR does not perform fitted Q-iteration, and instead utilizes off-policy data in a simple constrained policy search procedure. Wang et al. (2018) applied a similar advantage-weighting scheme for imitation learning, but the method was not demonstrated for the RL setting. In this work, we propose several design decisions that are vital for an effective RL algorithm. We also provide a theoretical analysis of AWR when combined with experience replay, and show that the algorithm optimizes the expected improvement with respect to a mixture of policies modeled by a replay buffer.

heading: 5 EXPERIMENTS

text: Our experiments aim to comparatively evaluate the performance of AWR with commonly used on-policy and off-policy deep RL algorithms. We evaluate our method on the OpenAI Gym benchmarks (Brockman et al., 2016), consisting of discrete and continuous control tasks. We also evaluate our method on complex motion imitation tasks with high-dimensional simulated characters. We then demonstrate the effectiveness of AWR on fully off-policy learning, by training on static datasets of demonstrations from demo policies. Behaviors learned by the policies are best seen in the supplementary video1. Code for our implementation of AWR is available at sites.google.com/view/awr-supp/. Detailed hyperparameter settings are provided in Appendix C.

heading: 5.1 BENCHMARKS

text:
We compare AWR to a number of state-of-the-art RL algorithms, including on-policy algorithms, such as TRPO (Schulman et al., 2015) and PPO (Schulman et al., 2017), off-policy algorithms, such as DDPG (Lillicrap et al., 2016), TD3 (Fujimoto et al., 2018), and SAC (Haarnoja et al., 2018a), as well as RWR (Peters & Schaal, 2007) and LAWER (Neumann & Peters, 2009).2 TRPO, PPO, and DDPG use the implementations from OpenAI baselines (Dhariwal et al., 2017). TD3 and SAC use the implementations from Fujimoto et al. (2018) and Haarnoja et al. (2018a). RWR and LAWER are implemented following the descriptions in Peters & Schaal (2007) and Neumann & Peters (2009), but neural networks are used instead of kernel-based approximators.
2While we attempted to compare to MPO (Abdolmaleki et al., 2018b), we were unable to find or implement a version of the algorithm that reproduces the results comparable to those reported by Abdolmaleki et al. (2018b).
Snapshots of the AWR policies are shown in Figure 1. Figure 2 shows learning curves comparing the different algorithms, and Table 1 summarizes the average returns of the final policies across 10 training runs initialized with different random seeds. Due to the slow wall-clock times of TD3 and SAC, some training runs did not have sufficient time to collect as many samples as other algorithms. Overall, AWR shows competitive performance with the state-of-the-art deep RL algorithms. It is competitive with on-policy methods, such as TRPO and PPO, in both sample efficiency and asymptotic performance. While it is not yet as sample efficient as current state-of-the-art off-policy methods, such SAC and TD3, it is able to achieve a comparable asymptotic performance on most tasks. RWR tends to perform poorly on these tasks, which suggests that, the particular modifications from AWR are critical. AWR also significantly outperforms LAWER across the various tasks. Though both methods use a similar advantaged-weighting scheme, our design decisions for AWR produce a simpler and more effective algorithm.

heading: 5.2 ABLATION EXPERIMENTS

text:
To determine the effects of various design decisions, we evaluate the performance of AWR when key components have been removed. The experiments include: an on-policy version of AWR (On-Policy), where updates use only data from the latest policy, a version of AWR without the baseline V (s) (No Baseline), and a version that uses Monte Carlo return estimates instead of TD(λ) (No TD(λ)). The effects of these components are illustrated in Figure 3. Overall, these design decisions appear to be vital for an effective algorithm, with the most crucial components being the use of experience replay and a baseline. Updates using only on-policy data can lead to instabilities and noticeable degradation in performance, which may be due to overfitting on a smaller dataset. Removing the baseline also noticeably hampers performance. Using simple Monte Carlo return estimates instead of TD(λ) seems to be a viable alternative, and the algorithm still achieves competitive performance on some tasks. When combined, these different components yield substantial performance gains over standard RWR.
To further evaluate the effect of experience replay, we compare policies trained using replay buffer with different capacities. Figure 3 illustrates the learning curves for buffers of size 5k, 20k, 50k, 100k, and 500k, with 50k being the default buffer size in our experiments. The size of the replay buffer appears to have a significant impact on overall performance. Smaller buffer sizes can result in instabilities during training, which again may be an effect of overfitting to a smaller dataset. As the buffer size increases, AWR remains stable even when the dataset is dominated by off-policy data from previous iterations. In fact, AWR appears more stable with larger replay buffers, but progress can also become slower. Since the sampling policy µ(a|s) is modeled by the replay buffer, a larger buffer can limit the rate at which µ changes by maintaining older data for more iterations.

heading: 5.3 MOTION IMITATION

text: In this section, we show that AWR can also solve high-dimensional tasks with complex simulated characters, including a 34 DoF humanoid and 64 DoF dog. The objective of the tasks is to imitate reference motion clips recorded using mocap. The experimental setup follows the framework proposed by Peng et al. (2018). The motions include walking and running (e.g. canter), as well as acrobatic skills, such as cartwheels and spinkicks. Figure 1 shows snapshots of the behaviors learned by the AWR. Table 2 and Figure 4 compare the performance of AWR to RWR and PPO. AWR performs well across the set of challenging skills, consistently achieving comparable or better performance than PPO. RWR struggles with controlling the humanoid, but exhibits stronger performance on the dog. This difference may be due to the more dynamic and acrobatic skills of the humanoid.

heading: 5.4 OFF-POLICY LEARNING WITH STATIC DATASETS

text:
Next, we evaluate AWR in a fully off-policy setting, where the algorithm is provided with a static dataset of experiences, and then tasked with learning the best possible policy without collecting any additional data. To evaluate our method, we use the off-policy tasks proposed by Kumar et al. (2019). The dataset consists of trajectories τ = {(s0,a0, r0) , (s1,a1, r1) , ...} from rollouts of a demo policy. Unlike standard imitation learning tasks, which only observes the states and actions from the demo policy, the dataset also records the reward at each step. The demo policies are trained using SAC on various OpenAI Gym tasks. A dataset of 1 million timesteps is collected for each task.
For AWR, we simply treat the dataset as the replay buffer D and directly apply the algorithm without any modifications. Figure 5 compares AWR to the original demo policy (Demo) and a behavioral cloning policy (BC). We also include comparisons to recent off-policy methods: batch-constrained Q-learning (BCQ) (Fujimoto et al., 2019) and bootstrapping error accumulation reduction (BEAR) (Kumar et al., 2019), which have shown strong performance on off-policy learning with static datasets. Note that both of these prior methods are modifications to existing off-policy RL methods, such as TD3 and SAC, which are already quite complex. In contrast, AWR is simple and requires no modifications for the fully off-policy setting. Despite not collecting any additional data, AWR is able to learn effective policies from these fully off-policy datasets, achieving comparable or better performance than the original demo policies. On-policy methods, such as PPO performs poorly in this off-policy setting. Q-function based methods, such as TD3 and SAC, can in principle handle off-policy data but tend to struggle in practice (Fujimoto et al., 2019; Kumar et al., 2019). Unlike Q-function based methods, AWR is less susceptible to issues from out-of-distribution actions as the policy is always trained on observed actions from the behaviour data (Kumar et al., 2019). AWR also shows comparable performance to BEAR and BCQ, which are specifically designed for this off-policy setting and introduce considerable algorithmic overhead.

heading: 6 DISCUSSION AND FUTURE WORK

text: We presented advantage-weighted regression, a simple off-policy reinforcement learning algorithm, where policy updates are performed using standard supervised learning methods. Despite its simplicity, our algorithm is able to solve challenging control tasks with complex simulated agents, and achieve competitive performance on standard benchmarks compared to a number of well-established RL algorithms. Our derivation introduces several new design decisions, and our experiments verify the importance of these components. AWR is also able to learn from fully off-policy datasets, demonstrating comparable performance to state-of-the-art off-policy methods. While AWR is effective for a diverse suite of tasks, it is not yet as sample efficient as the most efficient off-policy algorithms. We believe that exploring techniques for improving sample efficiency and performance on fully off-policy learning can open opportunities to deploy these methods in real world domains. A better theoretical understanding of the convergence properties of these algorithms, especially when combined with experience replay, could also be valuable for the development of future algorithms.


summaries: The paper proposes using a sinusoidal regularizer for neural network quantization. The regularizer “WaveQ” (sin^2) pushes floating-point parameters towards quantized values. Because the period of the function is highly related to the required bit-width, it can be used to determine the bit-width while keeping good characteristics - continuous and trainable. The authors provide experiments on both CNN and Transformers. The proposed method is widely adaptable and easy-to-use with quite promising results.

summaries: This paper proposed a regularization term to control the bit-width and encourage the DNN weights moving to the quantization intervals. The key in such regularization is the Sinusoidal function, where the penalty is maximized in the middle of quantization levels and minimized at the quantization points. The sinusoidal period is regarded as the continuous representation of the bit-width.

summaries: When training quantized neural networks, one typically first fixes the desired bitwidth $b$ (of weights and activations). While training, one maintains and updates full-bitwidth weights during backprop and "cheats" by using $b$-quantized versions of these full-precision weights during forward propagation. The quantization scheme used may vary.

abstractText: Deep quantization of neural networks below eight bits can lead to superlinear benefits in storage and compute efficiency. However, homogeneously quantizing all the layers to the same level does not account for the distinction of the layers and their individual properties. Heterogeneous assignment of bitwidths to the layers is attractive but opens an exponentially large non-contiguous hyperparameter space (Available Bitwidths ). Thus, finding the bitwidth while also quantizing the network to those levels becomes a major challenge. This paper addresses this challenge through a sinusoidal regularization mechanism, dubbed WaveQ. Adding our parametrized sinusoidal regularizer enables WaveQ to not only find the quantized weights, but also learn the bitwidth of the layers by making the period of the sinusoidal regularizer a trainable parameter. In addition, the sinusoidal regularizer itself is designed to align its minima on the quantization levels. With these two innovations, during training, stochastic gradient descent uses the form of the sinusoidal regularizer and its minima to push the weights to the quantization levels while it is also learning the period which will determine the bitwidth of each layer separately. As such WaveQ is a gradient-based mechanism that jointly learns the quantized weights as well as the heterogeneous bitwidths. We show that WaveQ balances compute efficiency and accuracy, and provides a heterogeneous bitwidth assignment for quantization of a large variety of deep networks (AlexNet, CIFAR10, MobileNet, ResNet-18, ResNet-20, SVHN, and VGG-11) that virtually preserves the accuracy. WaveQ is versatile and can also be used with predetermined bitwidths by fixing the period of the sinusoidal regularizer. In this case, WaveQ, on average, improves the accuracy of quantized training algorithms (DoReFa and WRPN) by∼ 4.8%, and outperforms multiple state-of-the-art techniques. Finally, WaveQ is applicable to quantizing transformers and yields significant benefits.

authors:
Jan M. Köhler
Anke Schmeink
Tim Genewein

title: Variational network quantization

venue: In 6th ICLR,

authors:
Dan Alistarh
Demjan Grubic
Jungshian Li
Ryota Tomioka
Milan Vojnovic

title: Qsgd: Communication-optimal stochastic gradient descent, with applications to training neural networks. 2016

authors:
Yu Bai
Yu-Xiang Wang
Edo Liberty

title: Proxquant: Quantized neural networks via proximal operators

venue: In 7th International Conference on Learning Representations,

authors:
Yoshua Bengio
Nicholas Léonard
Aaron C. Courville

title: Estimating or propagating gradients through stochastic neurons for conditional computation

authors:
Jungwook Choi
Zhuo Wang
Swagath Venkataramani
Pierce I-Jen Chuang
Vijayalakshmi Srinivasan
Kailash Gopalakrishnan

title: Pact: Parameterized clipping activation for quantized neural networks

authors:
Yoojin Choi
Mostafa El-Khamy
Jungwon Lee

title: Learning low precision deep neural networks through regularization

authors:
Anna Choromanska
Mikael Henaff
Michael Mathieu
Gérard Ben Arous
Yann LeCun

title: The Loss Surfaces of Multilayer Networks

venue: In Artificial Intelligence and Statistics,

authors:
Ahmed T. Elthakeb
Prannoy Pilligundla
Fatemehsadat Mireshghallah
Amir Yazdanbakhsh
Hadi Esmaeilzadeh

title: ReLeQ: A reinforcement learning approach for deep quantization of neural networks

venue: Advances in Neural Information Processing Systems (NeurIPS) Workshop on Machine Learning for Systems,

authors:
Steven K. Esser
Jeffrey L. McKinstry
Deepika Bablani
Rathinakumar Appuswamy
Dharmendra S. Modha

title: Learned step size quantization

venue: 8th ICLR,

authors:
Ruihao Gong
Xianglong Liu
Shenghu Jiang
Tianxiang Li
Peng Hu
Jiazhen Lin
Fengwei Yu
Junjie Yan

title: Differentiable soft quantization: Bridging full-precision and low-bit neural networks

venue: URL http://arxiv.org/abs/1908.05033

authors:
Lu Hou
James T. Kwok

title: Loss-aware weight quantization of deep networks

authors:
Lu Hou
Quanming Yao
James T. Kwok

title: Loss-aware binarization of deep networks

venue: In 5th ICLR,

authors:
Itay Hubara
Matthieu Courbariaux
Daniel Soudry
Ran El-Yaniv
Yoshua Bengio

title: Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations

venue: J. Mach. Learn. Res.,

authors:
Patrick Judd
Jorge Albericio
Tayler H. Hetherington
Tor M. Aamodt
Andreas Moshovos

title: Stripes: Bit-serial deep neural network computing

venue: Annual IEEE/ACM International Symposium on Microarchitecture, MICRO 2016,

venue: 49th MICRO,

title: Quantizing deep convolutional networks for efficient inference: A whitepaper, 2018

authors:
Anders Krogh
John A. Hertz

title: A simple weight decay can improve generalization

venue: In Proceedings of the 4th International Conference on Neural Information Processing Systems,

authors:
Hao Li
Zheng Xu
Gavin Taylor
Christoph Studer
Tom Goldstein

title: Visualizing the Loss Landscape of Neural Nets

venue: In NIPS,

authors:
Asit K. Mishra
Eriko Nurvitadhi
Jeffrey J. Cook
Debbie Marr

title: WRPN: Wide ReducedPrecision Networks

venue: In ICLR,

authors:
Abdelrahman Mohamed
Dmytro Okhonko
Luke Zettlemoyer

title: Transformers with convolutional context for asr, 2019

authors:
Maxim Naumov
Utku Diril
Jongsoo Park
Benjamin Ray
Jedrzej Jablonski
Andrew Tulloch

title: On periodic functions as regularizers for quantization of neural networks

authors:
Hieu Duy Nguyen
Anastasios Alexandridis
Athanasios Mouchtaris

title: Quantization aware training with absolute-cosine regularization for automatic speech recognition

venue: 21st Annual Conference of the International Speech Communication Association, Virtual Event, Shanghai,

authors:
Myle Ott
Sergey Edunov
David Grangier
Michael Auli

title: Scaling neural machine translation

venue: Proceedings of the Third Conference on Machine Translation: Research Papers,

authors:
Myle Ott
Sergey Edunov
Alexei Baevski
Angela Fan
Sam Gross
Nathan Ng
David Grangier
Michael Auli

title: fairseq: A fast, extensible toolkit for sequence modeling

venue: In Proceedings of NAACL-HLT 2019: Demonstrations,

authors:
Gabriele Prato
Ella Charlaix
Mehdi Rezagholizadeh

title: Fully quantized transformer for improved

venue: translation. ArXiv,

authors:
David E. Rumelhart
Geoffrey E. Hinton
Ronald J. Williams

title: Learning internal representations by error propagation

authors:
Hardik Sharma
Jongse Park
Naveen Suda
Liangzhen Lai
Benson Chau
Vikas Chandra
Hadi Esmaeilzadeh

title: Bit fusion: Bit-level dynamically composable architecture for accelerating deep neural network

authors:
Peter Shaw
Jakob Uszkoreit
Ashish Vaswani

title: Self-attention with relative position representations

venue: In NAACL-HLT,

authors:
Frederick Tung
Greg Mori

title: CLIP-Q: deep network compression learning by in-parallel pruningquantization

venue: IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Stefan Uhlich
Lukas Mauch
Kazuki Yoshiyama
Fabien Cardinaux
Javier Alonso Garcı́a
Stephen Tiedemann
Thomas Kemp
Akira Nakamura

title: Mixed precision dnns: All you need is a good parametrization

venue: URL http://arxiv.org/abs/1905.11452

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N. Gomez
Lukasz Kaiser
Illia Polosukhin

title: Attention is all you need, 2017

authors:
Kuan Wang
Zhijian Liu
Yujun Lin
Ji Lin
Song Han

title: HAQ: Hardware-Aware Automated Quantization

venue: arXiv preprint arXiv:1811.08886,

authors:
Haichuan Yang
Shupeng Gui
Yuhao Zhu
Ji Liu

title: Automatic neural network compression by sparsity-quantization joint learning: A constrained optimization-based approach

venue: IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Shaokai Ye
Tianyun Zhang
Kaiqi Zhang
Jiayu Li
Jiaming Xie
Yun Liang
Sijia Liu
Xue Lin
Yuankai Wang

title: A unified framework of dnn weight pruning and weight clustering/quantization using admm

authors:
Dongqing Zhang
Jiaolong Yang
Dongqiangzi Ye
Gang Hua

title: Lq-nets: Learned quantization for highly accurate and compact deep neural networks

venue: In ECCV,

authors:
Shuchang Zhou
Zekun Ni
Xinyu Zhou
He Wen
Yuxin Wu
Yuheng Zou

title: DoReFa-Net: Training Low Bitwidth Convolutional Neural Networks with Low Bitwidth Gradients

authors:
Chenzhuo Zhu
Song Han
Huizi Mao
William J. Dally

title: Trained Ternary Quantization

authors:
Neta Zmora
Guy Jacob
Gal Novik

title: Neural network distiller

heading: 1 INTRODUCTION

text:
Quantization, in general, and deep quantization (below eight bits) (Krishnamoorthi, 2018), in particular, aims to not only reduce the compute requirements of DNNs but also reduce their memory footprint (Zhou et al., 2016; Judd et al., 2016b; Hubara et al., 2017; Mishra et al., 2018; Sharma et al., 2018). Nevertheless, without specialized training algorithms, quantization can diminish the accuracy. As such, the practical utility of quantization hinges upon addressing two fundamental challenges: (1) discovering the appropriate bitwidth of quantization for each layer while considering the accuracy; and (2) learning weights in the quantized domain for a given set of bitwidths.
This paper formulates both of these challenges as a gradient-based joint optimization problem by introducing an additional novel sinusoidal regularization term in the training loss, called WaveQ. The following two main insights drive this work. (1) Sinusoidal functions (sin2) have inherent periodic minima and by adjusting the period, the minima can be positioned on quantization levels corresponding to a bitwidth at per-layer granularity. (2) As such, sinusoidal period becomes a direct and continuous representation of the bitwidth. Therefore, WaveQ incorporates this continuous variable (i.e., period) as a differentiable part of the training loss in the form of a regularizer. Hence, WaveQ is a differentiable regularization mechanism, it piggy backs on the stochastic gradient descent that trains the neural network to also learn the bitwidth (the period). Simultaneously this parametric sinusoidal regularizer pushes the weights to the quantization levels (sin2 minima).
By adding our parametric sinusoidal regularizer to the original training objective function, our method automatically yields the bitwidths for each layer along with nearly quantized weights for
those bitwidths. In fact, the original optimization procedure itself is harnessed for this purpose, which is enabled by the differentiability of the sinusoidal regularization term. As such, quantized training algorithms (Zhou et al., 2016; Mishra et al., 2018) that still use some form of backpropagation (Rumelhart et al., 1986) can effectively utilize the proposed mechanism by modifying their loss. Moreover, the proposed technique is flexible as it enables heterogeneous quantization across the layers. The WaveQ regularization can also be applied for training a model from scratch, or for fine-tuning a pretrained model. In contrast to the prior inspiring works (Uhlich et al., 2019; Esser et al., 2019), WaveQ is the only technique that casts finding the bitwidths and the corresponding quantized weights as a simultaneous gradient-based optimization through sinusoidal regularization during the training process. We also prove a theoretical result to provide an insight on why the proposed approach leads to solutions preserving the original accuracy during quantization. We evaluate WaveQ using different bitwidth assignments across different DNNs (AlexNet, CIFAR-10, MobileNet, ResNet-18, ResNet20, SVHN, and VGG-11). To show the versatility of WaveQ, it is used with two different quantized training algorithms, DoReFa (Zhou et al., 2016) and WRPN (Mishra et al., 2018). Over all the bitwidth assignments, the proposed regularization, on average, improves the top-1 accuracy of DoReFa by 4.8%. The reduction in the bitwidth, on average, leads to 77.5% reduction in the energy consumed during the execution of these networks. Finally, we apply WaveQ to Transformer DNNs citeppby augmenting their loss with WaveQ parametric sinusiodal regularization. In this case, the conventional stochastic gradient descent plus WaveQ regularization is used to quantize the big Transformer model from (Ott et al., 2018) for machine translation on the IWSLT14 German-English dataset (IWS). For 5, 6, and 7-bit quantization, training with WaveQ yields 0.46, 0.14, 0.04 improved BiLingual Evaluation Understudy (BLEU) score, respectively. As a point of reference, the original big Transformer model from (Ott et al., 2018) improves the BLEU by only 0.1 over the state-of-the-art. Code available at https://github.com/waveq-reg/waveq

heading: 2 JOINT LEARNING OF LAYER BITWIDTHS AND QUANTIZED PARAMETERS

text: Our proposed method WaveQ exploits weight regularization in order to automatically quantize a neural network while training. To that end, Section 2.1 describes the role of regularization in neural networks and then Section 2.2 explains WaveQ in more details.

heading: 2.1 PRELIMINARIES

text:
Quantizer. We discuss how quantization of weight works. Consider a floating-point variable wf to be mapped into a quantized domain using (b + 1) bits. Let Q be a set of (2k + 1) quantized values, where k = 2b − 1. Considering linear quantization, Q can be represented as{ −1,−k−1k , ...,− 1 k , 0, 1 k , ..., k−1 k , 1 } , where 1k is the size of the quantization bin. Now, wf can be mapped to the b-bit quantization Zhou et al. (2016) space as follows.
wqo = 2× quantizeb (
tanh(wf )
2max(|tanh(Wf )|) +
1
2
) − 1 (2.1)
In Equation 2.1, quantizeb(x) = 1 2b−1 round((2 b−1)x), wf is a scalar, Wf is a vector, and wqo is a scalar in the range [−1, 1]. Then, a scaling factor c is determined per layer to map the final quantized weight wq into the range [−c,+c]. As such, wq takes the form cwqo, where c > 0, and wqo ∈ Q.
Soft constraints through regularization and the loss landscape of neural networks. Neural networks’ loss landscapes are known to be highly non-convex and it has been empirically verified that loss surfaces for large networks have many local minima that essentially provide equivalent test errors Choromanska et al. (2015); Li et al. (2018). This opens up the possibility of adding soft constrains as extra custom objectives during the training process, in addition to the original objective (i.e., to minimize the accuracy loss). The added constraint could be with the purpose of increasing gener-
alization or imposing some preference on the weights values.
Regularization in action. Regularization effectively constrains weight parameters by adding a corresponding term (regularizer) to the objective loss function. A classical example is Weight Decay Krogh & Hertz (1991) that aims to reduce the network complexity by limiting the growth of the weights. This soft constraint is realized by adding a term, proportional to the L2 norm of the weights to the objective function as the regularizer that penalizes large weight values. WaveQ, on the other hand, uses regularization to push the weights to the quantization levels. For the sake of simplicity and clarity, Figure 1(a) and (b) illustrate a geometrical sketch for a hypothetical loss surface (original objective function to be minimized) and an extra regularization term in 2-D weight space, respectively. For weight decay regularization (Figure 1 (a)), the faded circle shows that as we get closer to the origin, the regularization loss is minimized. The point wopt is the optimum just for the loss function alone and the overall optimum solution is achieved by striking a balance between the original loss term and the regularization loss term. Similarly, Figure 1(b) shows a representation of the proposed periodic regularization for a fixed bitwidth β. A periodic pattern of minima pockets are seen surrounding the original optimum point. The objective of the optimization problem is to find the best solution that is the closest to one of those minima pockets where weight values are nearly matching the desired quantization levels, hence the name quantization-friendly. 2.2 WAVEQ REGULARIZATION The proposed regularizer is formulated in Equation (2.2) where the first term pushes the weights to the quantization levels and the second correlated term aims to reduce the bitwidth of each individual layer heterogeneously.
R(w;β) = λw ∑ i ∑ j
sin2 ( πwij(2 βi − 1) )
2βi︸ ︷︷ ︸ Weights quantization regularization
+ λβ ∑ i
βi︸ ︷︷ ︸ Bitwidth regularization
(2.2)
In Equation (2.2), λw is the weights quantization regularization strength which governs how strongly weight quantization errors are penalized, and λβ is the bitwidth regularization strength. The parameter βi is proportional to the quantization bitwidth which is elaborated later in this section. Figure 2 (a) shows a 3-D visualization of our regularizer, R. Figure 2 (b), (c) show a 2-D profile w.r.t weights (w), while (d) shows a 2-D profile w.r.t the bitwidth (β). Periodic sinusoidal regularization. As shown in Equation equation 2.2, the first regularization term is based on a periodic function (sinusoidal) that adds a smooth and differentiable term to the original objective, Figure 2(b). The periodic regularizer induces a periodic pattern of minima that correspond to the desired quantization levels. Such correspondence is achieved by matching the period to the quantization step (1/(2βi − 1)) based on a particular number of bits (βi) for a given layer i. Learning the sinusoidal period. The parameter βi in (Equation 2.2) controls the period of the sinusoidal regularizer. Thereby βi is directly proportional to the actual quantization bitwidth (bi) of layer i as follows: bi = dβie, and αi = 2bi/2βi (2.3) In Equation (B.2) where αi ∈ R+ is a scaling factor. Note that bi ∈ Z is the only discrete parameter, while βi ∈ R+ is a continuous real valued variable, and d∗e. is the ceiling operator. While the first term in Equation equation 2.2 is only responsible for promoting quantized weights, the second term (λβ ∑ i βi) aims to reduce the number of bits for each layer i individually while the
overall loss is aiming to maximize accuracy. As such, this term is a soft constraint that yields heterogeneous bitwidths for different layers. The main insight here is that βi, which also controls the period of the sinusoidal term, is a continuous valued parameter by definition. As such, βi acts as an ideal optimization objective constraint and a proxy to minimize the actual quantization bitwidth bi. Therefore, WaveQ avoids the issues of gradient-based optimization for discrete valued parameters. Furthermore, the benefit of learning the sinusoidal period is two-fold. First, it provides a smooth differentiable objective for finding minimal bitwidths. Second, simultaneously learning the scaling factor (αi) associated with the found bitwidth.
Leveraging the sinusoidal properties, WaveQ learns the following two quantization parameters simultaneously: (1) a per-layer quantization bitwidth (bi) along with (2) a scaling factor (αi) through learning the period of the sinusoidal function. Additionally, by exploiting the periodicity, differentiability, and the local convexity profile in sinusoidal functions, WaveQ automatically propels network weights towards values that are inherently closer to quantization levels according to the jointly learned quantizer’s parameters bi, αi as follows.
Mapping this to the quantizer’s design, for (b+ 1) bits quantization, k = 2b − 1, and c = α. These learned parameters (b, α), as explained above, can be mapped to the quantizer parameters explained in Equation equation 2.1. For (b+1) bits quantization (the extra bit is the sign bit):
k = 2b − 1, and c = α = 2b/2β (2.4)
Bounding the gradients. The denominator in the first term of Equation equation 2.2
( ∑ i ∑ j sin2(πwij(2βi−1)) 2βi
) is used to control the range derivatives of the proposed regularization term with respect to β. This denominator is chosen to limit vanishing and exploding gradients during training. To this end, we compared three variants of equation equation 2.2 with different normalization defined, for k = 0, 1, and 2, as:
Rk(w; β) = λw ∑ i ∑ j
sin2 ( πwij(2 βi − 1) )
2kβi + λβ ∑ i βi
(2.5)
Figure 3 (a), (b), (c) provide a visualization on how each of the proposed scaled variants affect the first and second derivatives. For Rk=0 and Rk=2, there are regions of vanishing or exploding gradients. Only the regularization Rk=1 (the proposed one) is free of such issues.
Setting the regularization strengths. The convergence behavior depends on the setting of the regularization strengths λw and λβ . Our proposed objective seeks to learn multiple quantization parameterization in conjunction. As such, the learning process can be portrayed as three phases (Figure 2(e)). In Phase ( 1 ), the learning process optimizes for the original task loss E0. Initially, the small λw and λβ values allow the gradient descent to explore the optimization surface freely. As the training process moves forward, we transition to phase ( 2 ) where the larger λw and λβ gradually engage both the weights quantization regularization and the bitwidth regularization, respectively. Note that, for this to work, the strength of the weights quantization regularization λw should be higher than the strength of the bitwidth regularization λβ such that a bitwidth per layer could be properly evaluated and eventually learned during this phase. After the bitwidth regularizer converges to a bitwidth for each layer, we transition to phase ( 3 ), where we fix the learned bitwidths and gradually decay λβ while we keep λw high. The criterion for choosing λw and λβ is to balance the magnitude of regularization loss to be smaller than the magnitude of accuracy loss. The mathematical formula used to generate λw and λβ profiles can be found in the supplementary material. (Figure 8).

heading: 3 THEORETICAL ANALYSIS

text:
The results of this section are motivated as follows. Intuitively, we would like to show that the global minima of E = E0 + R are very close to the minima of E0 that minimizes R. In other words, we expect to extract among the original solutions, the ones that are most prone to be quantized. To establish such result, we will not consider the minima of E = E0 + R, but the sequence Sn of minima of En = E0+ δnR defined for any sequence δn of real positive numbers. The next theorem shows that our intuition holds true, at least asymptotically with n provided δn → 0. Theorem 1. Let E0, R : Rn → [0,∞) be continuous and assume that the set SE0 of the global minima of E0 is non-empty and compact. As SE0 is compact, we can also define SE0,R ⊆ SE0 as the set of minima of E0 which minimizes R. Let δn be a sequence of real positive numbers, define En = E0+δnR and the sequence Sn = SEn of the global minima of En. Then, the following holds true:
1. If δn → 0 and Sn → S∗, then S∗ ⊆ SE0,R,
2. If δn → 0 then there is a subsequence δnk → 0 and a non-empty set S∗ ⊆ SE0,R so that Snk → S∗,
where the convergence of sets, denoted by Sn → S∗, is defined as the convergence to 0 of their Haussdorff distance, i.e., lim
n→∞ dH(Sn, S∗) = 0.
Proof. For the first statement, assume that Sn → S∗. We wish to show that S∗ ⊆ SE0,R. Assume that xn is a sequence of global minima of F + δnG converging to x∗. It suffices to show that x∗ ∈ SE0,R. First let us observe that x∗ ∈ SE0 . Indeed, let
λ = inf x∈Rn E0(x)
and assume that x ∈ SE0 . Then, λ ≤ E0(xn) ≤ (E0 + δnR)(xn) ≤ (E0 + δnR)(x) = λ+ δnR(x)︸ ︷︷ ︸
→λ
.
Thus, since E0 is continuous and xn → x∗ we have that E0(x∗) = λ which implies x∗ ∈ SE0 . Next, define
µ = inf x∈SE0 R(x).
Let x̂ ∈ SE0,R so that R(x̂) = µ. Now observe that, by the minimality of xn we have that λ+ δnµ = (E0 + δnR)(x̂) ≥ (E0 + δnR)(xn) ≥ λ+ δnR(xn)
Thus, R(xn) ≤ µ for all n. Since R is continuous and xn → x∗ we have that R(x∗) ≤ µ which implies that R(x∗) = µ since x∗ ∈ SE0 . Thus, x∗ ∈ SE0,R. The second statement follows from the standard theory of Hausdorff distance on compact metric spaces and the first statement. Theorem 1 implies that by decreasing the strength of R, one recovers the subset of the original solutions that achives the smallest quantization loss. In practice, we are not interested in global minima, and we should not decrease much the strength of R. In our context, Theorem 1 should then be understood as a proof of concept on why the proposed approach leads the expected result. Experiments carried out in the next section will support this claim. Additionally, note that while the theorem is stated in terms of a limit as the regularization parameter vanishes, the proof in fact gives a corresponding stability result. Namely, if the regularization parameter is sufficiently small relative to the main loss then the minimizers will be “almost” quantized. For the interested reader, we provide a more detailed version of the above analysis in the supplementary material.

heading: 4 EXPERIMENTAL RESULTS

text:
To demonstrate the effectiveness of WaveQ, we evaluated it on several deep neural networks with different Image Classification datasets (CIFAR10, SVHN, and ImageNet), and one Transformerbased network, which is the big Transformer model from(Ott et al., 2018) on the IWSLT14 GermanEnglish dataset (IWS). We provide results for two different types of quantization. First, we show quantization results for learned heterogeneous bitwidths using WaveQ and we provide different analyses to asses the quality of these learned bitwidth assignments. Second, we further provide results assuming a preset homogeneous bitwidth assignment as a special setting of WaveQ. This is, in some cases, a practical assumption that might stem from particular hardware requirements or constraints. Table 1 provides a summary of the evaluated networks and datasets for both learned heterogeneous bitwidths, and the special case of training preset homogeneous bitwidth assignments. We compare our proposed WaveQ method with PACT (Choi et al., 2018a), LQ-Nets (Zhang et al., 2018),
W32/A32 Full Precision Homogenous 57.1 80.2 70.1 89.5 71.8 90.3
DSQ (Gong et al., 2019), and DoReFa, which are current state-of-the-art methods that show results with homogeneous 3-, and 4-bit weight/activation quantization for various networks (AlexNet, ResNet-18, and MobileNet).
Experimental setup. We implemented WaveQ on top of DoReFa inside Distiller (Zmora et al., 2018), an open source framework for quantization by Intel that implements various quantization techniques. The reported accuracies for DoReFa and WRPN are with the built-in implementations in Distiller, which may not exactly match the accuracies reported in their respective papers. However, an independent implementation from a major company provides an unbiased foundation for comparison. We quantize all convolution and fully connected layers, except for the first and last layers which use 8-bits. This assumption is commensurate with the previous techniques.

heading: 4.1 LEARNED HETEROGENEOUS BITWIDTHS

text:
As for quantizing both weights and activations, Table 1 shows that incorporating WaveQ into the quantized training process yields best accuracy results outperforming PACT, LQ-Net, DSQ, and DoReFa with significant margins. Furthermore, it can be seen that the learned heterogeneous bitwidths yield better accuracy as compared to the preset 4-bit homogeneous assignments, with
lower, on average, bitwidth (3.85, 3.57, and 3.95 bits for AlexNet, ResNet-18, and MobileNet, respectively). Figure 4(a),(b) (bottom bar graphs) show the learned heterogeneous weight bitwidths over layers for AlexNet and ResNet-18, respectively. As seen, WaveQ parametric regularization yields a spectrum of varying bitwidth assignments to the layers which vary from 2 bits to 8 bits with an irregular pattern. These results demonstrate that the proposed regularization, WaveQ, automatically distinguishes different layers and their varying importance with respect to accuracy while learning their respective bitwidths. To assess the quality of these bitwidths assignments, we conduct a sensitivity analysis on the relatively big networks (see next subsection). Benefits of heterogeneous quantization. Figure 4(a),(b) (top graphs) show various comparisons and sensitivity results for learned heterogeneous bitwidth assignments for bigger networks (AlexNet and ResNet-18). It is infeasible to enumerate these networks’ respective quantization spaces. Compared to 4-bit homogeneous quantization, learned heterogeneous assignments achieve better accuracy with lower, on average, bitwidth 3.85 bits for AlexNet and 3.57 bits for ResNet-18. This demonstrates that a homogeneous (uniform) assignment of the bits is not always the desired choice to minimize accuracy loss. Furthermore, Figure 4 also shows that decrementing the learned bitwidth for any single layer at a time results in 0.44% and 0.24% average reduction in accuracy for AlexNet and ResNet-18, respectively. The dotted blue line with markers shows how differently decrementing the bitwidth of various individual layers affect the accuracy. This trend further demonstrates the effectiveness of learning with WaveQ to find the lowest bitwidth that maximizes the accuracy. Energy savings. To demonstrate the energy savings of the solutions found by WaveQ, we evaluate it on Stripes (Judd et al., 2016a), a custom accelerator designed for DNNs, which exploits bit-serial computation to support flexible bitwidths for DNN operations. As shown in Table 1, the reduction in the bitwidth, on average, leads to 77.5% reduction in the energy consumed during the execution of these networks.

heading: 4.2 PRESET HOMOGENOUS BITWIDTH QUANTIZATION

text:
We also consider a preset homogeneous bitwidth quantization which can also be supported by WaveQ under special settings where we fix β (to a preset bitwidth). Hence, only the first regularization term is engaged for propelling the weights to the quantization levels.
Table 2 shows accuracies of different networks (SimpleNet-5, ResNet-20, VGG-11, and SVHN-8) using plain WRPN, plain DoReFa and DoReFa + WaveQ for 3, 4, and 5 bitwdiths. As depicted, the results concretely show the effect of incorporating WaveQ into existing quantized training techniques and how it outperforms the previously reported accuracies. Weight distributions during training. Figure 5 shows the evolution of weights distributions over fine-tuning epochs for different layers of CIFAR10, SVHN, AlexNet, and ResNet18 networks. The high-precision weights form clusters and gradually converge around the quantization centroids as regularization loss is minimized along with the main accuracy loss. 4.3 WAVEQ FOR TRANSFORMER
QUANTIZATION Table 3: Performance of WaveQ
for quantizing Transformers.
Bitwidth
BLEU score
Unregularized Training
(without WaveQ)
Regularized Training
(with WaveQ)
Full precision 34.93
7-bit 34.79 34.83 (0.04 )
6-bit 34.39 34.53 (0.14 )
5-bit 32.74 33.20 (0.46 ) Transformers (encoder-decoder architectures) have been shown to achieve best results for NLP tasks including machine translation (Vaswani et al., 2017) and automatic speech recognition (Mohamed et al., 2019). A Transformer layer relies on a key-value self-attention mechanism for learning relationships between distant concepts, rather than relying on recurrent connections and memory cells. Herein, we extend the application of WaveQ regularization to improve the accuracy of deeply
quantized (below 8 bits) Transformer models. We run our experiments on IWSLT 2014 GermanEnglish (DE-EN) dataset. We use the Transformer model implemented in the fairseq-py toolkit (Ott et al., 2019). All experiments are based on the big transformer model with 6 blocks in the encoder and decoder networks. Table 3 shows the effect of applying WaveQ regularization into the training process for 5, 6, and 7-bit quantization on the final accuracy (BLEU score). WaveQ consistently improves the BLEU score of quantized models at various quantization bitwidths (7-5 bits). Moreover, higher improvements are obtained at lower bitwidths.
5 DISCUSSION
We conduct an experiment that uses WaveQ for training from scratch. For the sake of clarity, we are considering in this experiment the case of preset bitwidth assignments (i.e., λβ = 0). Figure 6-Row(I)-Col(I) shows weight trajectories without WaveQ as a point of reference. Row(II)-Col(I) shows the weight trajectories when WaveQ is used with a constant λw.
As the Figure illustrates, using a constant λw results in the weights being stuck in a region close to their initialization, (i.e., quantization objective dominates the accuracy objective). However, if we dynamically change the λw following the exponential curve in Figure 6- Row(III)-Col(I)) during the from-scratch training, the weights no longer get stuck. Instead,
the weights traverse the space (i.e., jump from wave to wave) as illustrated in Figure 6-Cols(II) and (III) for CIFAR and SVHN, respectively. In these two columns, Rows (I), (II), (III), correspond to quantization with 3, 4, 5 bits, respectively. citepInitially, the smaller λw values allow the gradient descent to explore the optimization surface freely, as the training process moves forward, the larger λw gradually engages the sinusoidal regularizer, and eventually pushes the weights close to the quantization levels. Further convergence analysis is provided in the supplementary material.
Next, we provide results comparing two profiles of the regularization strength (λw). Profile 1: λw gradually increases as training proceeds then gradually decays towards the end of training. (Figure 7(a)). Profile 2: λw gradually increases as training proceeds and remains high (Figure 7(c)). Figure 7(a,c) depicts different loss components and Figure 7(b,d) visualizes weights trajectories. Both profiles show that accuracy loss is unimpededly minimized along with WaveQ loss. Our theoretical results align with Profile 1 (Figure 7(b))–what reviewer insightfully pointed out. Although λw decays back towards end of training, the weights mostly remain tied to their
quantization levels except for a few deflections that cause slight increase of the regularization loss towards end of training. In terms of test accuracy, both profiles yield similar results (Profile 1, 74.95%) vs (Profile 2, 74.45%). Note that while the theorem is stated in terms of a limit as the regularization parameter vanishes, the proof in fact gives a corresponding stability result. Namely, if the regularization parameter is sufficiently small relative to the main loss then the minimizers will be “almost” quantized.

heading: 6 RELATED WORK

text:
This research lies at the intersection of (1) quantized training algorithms and (2) techniques that discover bitwidth for quantization. The following discusses the most related works in both directions. Most related methods define a new optimization problem and use a special method for solving it. For example, (Bai et al., 2019) uses a proximal gradient method (adds a prox step after each stochastic gradient step), (Yang et al., 2020) uses ADMM, and (Tung & Mori, 2018) takes a Bayesian approach. This only makes the training more difficult, slower and increases the computational com-
plexity. In contrast, WaveQ exploits the conventional stochastic gradient descent method while jointly optimizing for the original training loss while softly constraining it to simultaneously learn the quantized parameters, and more importantly bitwidths. The differentiability of the adaptive sinusoidal regularizer enables simultaneously learning both the bitwidths and pushing the weight values to the quantization levels. As such, WaveQ can be used as a complementary method to some of these efforts, which is demonstrated by experiments with both DoReFa-Net (Zhou et al., 2016) and WRPN (Mishra et al., 2018). Our preliminary efforts (Anonymous) and another concurrent work (Naumov et al., 2018) use a sinusoidal regularization to push the weights closer to the quantization levels. However, neither of these two works make the period a differentiable parameter nor find bitwidths during training. Quantized training algorithms There have been several techniques (Zhou et al., 2016; Zhu et al., 2017; Mishra et al., 2018) that train a neural network in a quantized domain after the bitwidth of the layers is determined manually. DoReFa-Net (Zhou et al., 2016) uses straight through estimator (Bengio et al., 2013) for quantization and extends it for any arbitrary k bit quantization in weights, activations, and gradients. WRPN (Mishra et al., 2018) is training algorithm that compensates for the reduced precision by increasing the number of filter maps in a layer (doubling or tripling). TTQ (Zhu et al., 2017) quantizes the weights to ternary values by using per layer scaling coefficients learnt during training. These scaling coefficients are used to scale the weights during inference. PACT (Choi et al., 2018a) proposes a technique for quantizing activations by introducing an activation clipping parameter α. This parameter (α) is used to represent the clipping level in the activation function and is learned via back-propagation during training. More recently, VNQ (Achterhold et al., 2018) uses a variational Bayesian approach for quantizing neural network weights during training. VNQ requires a careful choice prior distribution of the weights, which is not straightforward, and the model is often intractable. In contrast, WaveQ is directly applicable without introducing extra hyperparameters to optimize. Additionally, VNQ takes on a probabilistic approach, while WaveQ is a deterministic approach towards soft quantization. Loss-aware weight quantization. Recent works pursued loss-aware minimization approaches for quantization. (Hou et al., 2017) and (Hou & Kwok, 2018) developed approximate solutions using proximal Newton algorithm to minimize the loss function directly under the constraints of low bitwidth weights. One effort (Choi et al., 2018b) proposed to learn the quantization of DNNs through a regularization term of the mean-squared-quantization error. LQ-Net (Zhang et al., 2018) proposes to jointly train the network and its quantizers. DSQ (Gong et al., 2019) employs a series of tanh functions to gradually approximate the staircase function for low-bit quantization (e.g., sign for 1- bit case), and meanwhile keeps the smoothness for easy gradient calculation. Although some of these techniques use regularization to guide the process of quantized training, none explores the use of adaptive sinusoidal regularizers for quantization. Most recently, (Nguyen et al., 2020) suggests using |cos| function as a regularizer. Moreover, unlike WaveQ, these techniques do not find the bitwidth for quantizing the layers. Techniques for discovering quantization bitwidths. A recent line of research focused on methods which can also find the optimal quantization parameters, e.g., the bitwidth, the stepsize, in parallel to the network weights. Recent work (Ye et al., 2018) based on ADMM (adm) runs a binary search to minimize the total square quantization error in order to decide the quantization levels for the layers. Most recently, (Uhlich et al., 2019) proposed to indirectly learn quantizer’s parameters via Straight Through Estimator (STE) (Bengio et al., 2013) based approach. In a similar vein, (Esser et al., 2019) has proposed to learn the quantization mapping for each layer in a deep network by approximating the gradient to the quantizer step size that is sensitive to quantized state transitions. On another side, recent works (Elthakeb et al., 2018; Wang et al., November 21, 2018) proposed a reinforcement learning based approach to find an optimal bitwidth assignment policy. Quantizing Transformers. FullyQT (Prato et al., 2019) uses a bucketing based uniform quantization proposed by QSGD (Alistarh et al., 2016) and extends it to Tranformers. Q8BERT (Zafrir et al., 2019) quantizes all the GEMM (General Matrix Multiply) operations to 8 bit by adding an additional term for quantization loss during training, which is calculated based on the rounding effect of floating point values (Shaw et al., 2018). WaveQ, however, uses a sinusoidal regularizer to automatically push the weights towards the quantization levels.

heading: 7 CONCLUSION

text: This paper devised WaveQ that casts the two problems of finding layer bitwidth and quantized weights as a gradient-based optimization through parametric sinusoidal regularization. WaveQ provides significant improvements over the state-of-the-art and is even applicable to the Transformers.

heading: A DETAILED THEORETICAL ANALYSIS

text:
A.1 MOTIVATION
The results of this section are motivated by the following question. Question A.1. Suppose that a function F : Rn → [0,∞) has many global minima and thatQ ⊂ Rn is closed. How do we isolate the global minima of F that are closest toQwithout actually computing the full set of global minima of F?
Intuitively, we would like to show that if > 0 is very small, then the global minima of the function
F (x) + d(x,Q)
are very close to the global minima of F closest to Q. To achieve this we will have to introduce first the concept of convergence of sets and then we will show that our intuition is correct by proving that the set of global minima to the above relaxed function converges to a subset of global minima of F closest to Q.
A.2 RELEVANT DEFINITIONS
Definition A.2. If F : Rn → [0,∞) satisfies lim|x|→∞ F (x) = +∞, we will say that F is coercive. Definition A.3. For a coercive function F : Rn → [0,∞) we let SF = {x ∈ Rn : F (x) = miny∈Rn F (y)} be coercive. Lemma A.4. Assume that F : Rn → [0,∞) is continuous and coercive. Then F has at least one global minimum. That is, SF is non-empty. Furthermore, SF is a compact set. Definition A.5. Let F,G : Rn → [0,∞) are continuous and assume that F is coercive. Define
SF,G = {x ∈ SF : G(x) = inf y∈SF G(y)},
the minima of F which minimize G among the minima of F . Definition A.6. Let Q ⊂ Rn be a closed set and assume that x ∈ Rn. Define the distance from x to the set Q to be
d(x,Q) = inf y∈Q ‖x− y‖.
Observe that since Q is a closed set we have that x ∈ Q if and only if d(x,Q) = 0 and otherwise d(x,Q) > 0. Definition A.7. Let A,B ⊂ Rn be compact sets. We define the Hausdorff distance between A and B by
dH(A,B) = max{sup x∈B d(x,A), sup y∈A d(y,B)}.
Observe that dH(A,B) = 0 if and only if A = B. Definition A.8. Let {Sδ}δ>0 be a family of compact subsets of Rn. We say that limδ→0 Sδ = S∗ if
lim δ→0 dH(Sδ, S∗) = 0.
Lemma A.9. Let Sδ be a family of compact subsets of Rn, then limδ→0 Sδ = S∗ if and only if the following two conditions hold.
1. If xδ ∈ Sδ converges to x, then x ∈ S∗
2. For every x ∈ S∗, there exists a family xδ ∈ Sδ with xδ → x.
The lemma is just an exercise in the definition.
A.3 STATEMENT OF THE THEOREM
Theorem 2. Let F,G : Rn → [0,∞) are continuous and assume that F is coercive. Consider the sets SF+δG, the set of points at which F + δG is globally minimum. The following are true:
1. If δn → 0 and SF+δnG → S∗, then
S∗ ⊂ SF,G
2. If δn → 0 then there is a subsequence δnk → 0 and a non-empty set S∗ ⊂ SF,G so that SF+δnkG → S∗.
Proof. The second statement follows from the standard theory of Hausdorff distance on compact metric spaces and the first statement. For the first statement, assume that SF+δnG → S∗. We wish to show that S∗ ⊂ SF,G. Assume that xn is a sequence of global minima of F + δnG converging to x∗. It suffices to show that x∗ ∈ SF,G. First let us observe that x∗ ∈ SF . Indeed, let
λ = inf x∈Rn F (x)
and assume that x ∈ SF . Then,
λ ≤ F (xn) ≤ (F + δnG)(xn) ≤ (F + δnG)(x) = λ+ δnG(x)→ λ.
Thus, since F is continuous and xn → x∗ we have that F (x∗) = λ which implies x∗ ∈ SF . Next, define
µ = inf x∈SF G(x).
Let x̂ ∈ SF,G so that G(x̂) = µ. Now observe that, by the minimality of xn we have that
λ+ δnµ = (F + δnG)(x̂) ≥ (F + δnG)(xn) ≥ λ+ δnG(xn)
Thus, G(xn) ≤ µ
for all n. Since G is continuous and xn → x∗ we have that G(x∗) ≤ µ which implies that G(x∗) = µ since x∗ ∈ SF . Thus, x∗ ∈ SF,G.

heading: B QUANTIZER

text:
Here, we give an overview about the used quantization method. Consider a floating-point variable wf to be mapped into a quantized domain using (b + 1) bits. Let Q be a set of (2k + 1) quantized values, where k = 2b − 1. Considering linear quantization, Q can be represented as{ −1,−k−1k , ...,− 1 k , 0, 1 k , ..., k−1 k , 1 } , where 1k is the size of the quantization bin. Now, wf can be mapped to the b-bit quantization (Zhou et al., 2016) space as follows:
(B.1)wqo = 2× quantizeb ( tanh(wf )
2max(|tanh(Wf )|) +
1
2
) − 1
where quantizeb(x) = 1 2b−1 round((2 b−1)x), wf is a scalar,Wf is a vector, andwqo is a scalar and tanh is used to limit its range to [−1, 1]. Then, a scaling factor c is determined per layer to map the final quantized weight wq into the range [−c,+c]. As such, wq takes the form cwqo, where c > 0, and wqo ∈ Q. These learned parameters (b, α), as explained in Section 2.2, can be mapped to the quantizer parameters explained in Equation equation B.1. For (b + 1) bits quantization (the extra bit is the sign bit):
k = 2b − 1, and c = α = 2b/2β (B.2)

heading: C CONVERGENCE ANALYSIS

text:
Figure 8 (a), (b) show the convergence behavior of WaveQ by visualizing both accuracy and regularization loss over finetuning epochs for two networks: CIFAR10 and SVHN. As can be seen, the regularization loss (WaveQ Loss) is minimized across the finetuning epochs while the accuracy is maximized. This demonstrates a validity for the proposed regularization being able to optimize the two objectives simultaneously. Figure 8 (c), (d) contrasts the convergence behavior with and without WaveQ for the case of training from scratch for VGG-11. As can be seen, at the onset of training, the accuracy in the presence of WaveQ is behind that without WaveQ. This can be explained as a result of optimizing for an extra objective in case of with WaveQ as compared to without. Shortly thereafter, the regularization effect kicks in and eventually achieves ∼ 6% accuracy improvement. The convergence behavior, however, is primarily controlled by the regularization strengths (λw, λβ). As briefly mentioned in Section 2.2, (λw, λβ) ∈ [0,∞) is a hyperparameter that weights the relative contribution of the proposed regularization objective to the standard accuracy objective.
We reckon that careful setting of λw, λβ across the layers and during the training epochs is essential for optimum results (Choi et al., 2018b).
D WAVEQ PERFORMANCE ON BERT
Additionally, Table 5 provides layer-wise quantization with a heterogeneous mix of 4 and 5 bits for the BERT model. In all cases, WaveQ improves UPOS and LAS metrics for two French treebanks (SPOKEN, PARTUT).

heading: E TRAINING FROM SCRATCH

text: Table 6 shows a comparison between training from scratch with WaveQ vs without. It can be seen that incorporating WaveQ into the training process achieves strictly better accuracy than the baseline training without WaveQ across all cases. Moreover, higher improvements are obtained at lower bitwidths reaching to 35%

heading: F REGULARIZATION STRENGTHS

text:
Having a regularization strength is a normal setting associated with any regularization method. The criterion for choosing λw and λβ is to balance the magnitude of regularization loss to be smaller than the magnitude of accuracy loss. We then perform a grid search over a few points and chose the ones with the best convergence.
From the theoretical perspective, while the theorem is stated in terms of a limit as the regularization parameter vanishes, the proof in fact gives a corresponding stability result. Namely, if the regularization parameter is sufficiently small relative to the main loss then the minimizers will be “almost” quantized.

heading: G HETEROGENEOUS COMPARISON

text: For Mobilenet-V2, WaveQ quantizes the network to an average bitwidth of 3.95(20.66 GBOPS) compared to 5.90(29.16 GBOPs) reported by Uhlich et al. (2019). Similarly, for Resnet-18, WaveQ achieves an average bitwidth of 3.57(62.56 GBOPs) compared to 5.47(65.90 GBOPs) by Uhlich et al. (2019). Table 7 shows this comparison. However this is not a fair comparison since WaveQ is a regularization method and not a full-blown quantization technique.

title: WAVEQ: GRADIENT-BASED DEEP QUANTIZATION