  In neural networks with binary activations and or binary weights the training
by gradient descent is complicated as the model has piecewise constant
response. We consider stochastic binary networks, obtained by adding noises in
front of activations. The expected model response becomes a smooth function of
parameters, its gradient is well defined but it is challenging to estimate it
accurately. We propose a new method for this estimation problem combining
sampling and analytic approximation steps. The method has a significantly
reduced variance at the price of a small bias which gives a very practical
tradeoff in comparison with existing unbiased and biased estimators. We further
show that one extra linearization step leads to a deep straight-through
estimator previously known only as an ad-hoc heuristic. We experimentally show
higher accuracy in gradient estimation and demonstrate a more stable and better
performing training in deep convolutional models with both proposed methods.
