Binarized neural network

I am currently looking at a paper by Hubara et al on binarized neural network.

I am stuck in understanding algorithm 2 of the paper. The algorithm uses shift-based (bit-shifting) AdaMax, where AdaMax is an extension of the Adam optimizer. In particular, they are using

$$m_{t} = \beta_{1}.m_{t-1} + (1 - \beta_{1}).g_{t}$$

$$v_{t} = \max(\beta_{2}.v_{t-1}, |g_{t}|)$$

$$\theta_{t} = \theta_{t−1} − (\alpha\oslash(1−β_{1}^t)).(m_{t} \oslash v_{t}^{-1} )$$

where $g_{t}$ is the gradient, $\theta_{t-1}$ is the previous parameter, $\alpha$, $\beta_{1}$, $\beta_{2}$ are learning rate, and the betas of Adam optimizer. They stated that $\oslash$ stands for both left and right bit shift. I know the left shift and the right shift on its own, but I am not sure how do we have both at the same time? Help will be much appreciated. Thank you.

I take a look at their github.

Here are the relevant parts:

local stepSize = lr/biasCorrection1 --math.sqrt(biasCorrection2)/biasCorrection1

stepSize=math.pow(2,torch.round(math.log(stepSize)/(math.log(2))))

and also

state.v:copy(torch.pow(2,torch.round(torch.log(state.v):div(math.log(2)))))

It seems that for $\alpha \oslash (1-\beta_1^t)$, what is being done is $$2^{\lfloor \log_2 \frac{\alpha}{1-\beta_1^t} \rfloor}$$

which is a left shift if $\lfloor \log_2 \frac{\alpha}{1-\beta_1^t} \rfloor > 0$ and a right shift if $\lfloor \log_2 \frac{\alpha}{1-\beta_1^t} \rfloor < 0$.

On the other hand, for $m_t \oslash v_t^{-1}$, what is being done is

$$\frac{m_t}{2^{\lfloor \log_2 v_t\rfloor}}$$

which is a right shift if $\lfloor \log_2 v_t\rfloor> 0$ and a left shift if $\lfloor \log_2 v_t\rfloor < 0$.

• Thanks for your answer, would you mind explaining the last line a bit more? Apr 28 '18 at 12:24
• division by $2$ corresponds to right shift by $1$ position and multiplication corresponds to left shift by $1$. Apr 28 '18 at 15:34
• Thanks for the answer Siong Thye; it seems that the ⊘ operation is not quite consistent... Apr 29 '18 at 0:26