  Deep learning is computationally intensive, with significant efforts focused
on reducing arithmetic complexity, particularly regarding energy consumption
dominated by data movement. While existing literature emphasizes inference,
training is considerably more resource-intensive. This paper proposes a novel
mathematical principle by introducing the notion of Boolean variation such that
neurons made of Boolean weights and inputs can be trained -- for the first time
-- efficiently in Boolean domain using Boolean logic instead of gradient
descent and real arithmetic. We explore its convergence, conduct extensively
experimental benchmarking, and provide consistent complexity evaluation by
considering chip architecture, memory hierarchy, dataflow, and arithmetic
precision. Our approach achieves baseline full-precision accuracy in ImageNet
classification and surpasses state-of-the-art results in semantic segmentation,
with notable performance in image super-resolution, and natural language
understanding with transformer-based models. Moreover, it significantly reduces
energy consumption during both training and inference.
