2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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)))))
state.v:add(epsilon)
tmp:addcdiv(1, state.m, state.v)

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.