Maybe it's a cliche--I think I've used it myself--to say that scientists' and philosophers' explanations for how the brain works tend to metaphorically track the most advanced technology of their time. Greek writers thought brains worked like hydraulic water clocks. European writers in the Middle Ages suggested that thoughts operated through gear-like mechanisms. In the 19th century the brain was like a telegraph; a few decades later, it was more like a telephone network. Shortly after that, no surprise, people thought the brain worked like a digital computer, and that maybe they could build computers that work like the brain, or talk to it.

This paper presents a family of backpropagation-free neural architectures, Gated Linear Networks (GLNs),that are well suited to online learning applications where sample efficiency is of paramount importance. The impressive empirical performance of these architectures has long been known within the data compression community, but a theoretically satisfying explanation as to how and why they perform so well has proven difficult. What distinguishes these architectures from other neural systems is the distributed and local nature of their credit assignment mechanism; each neuron directly predicts the target and has its own set of hard-gated weights that are locally adapted via online convex optimization. By providing an interpretation, generalization and subsequent theoretical analysis, we show that sufficiently large GLNs are universal in a strong sense: not only can they model any compactly supported, continuous density function to arbitrary accuracy, but that any choice of no-regret online convex optimization technique will provably converge to the correct solution with enough data. Empirically we show a collection of single-pass learning results on established machine learning benchmarks that are competitive with results obtained with general purpose batch learning techniques.