A persistent puzzle throughout the cognitive and social sciences is how people manage to learn social conventions from the sparse and noisy behavioral data of diverse actors, without explicit instruction. Here, we show that the dominant theories of social learning perform poorly at capturing how individuals learn conventions in coordination experiments that task them with matching their behaviors while interacting in social networks. Across experiments, participants’ choices systematically deviate from both imitation and optimization. Instead, they follow a categorical, two-stage learning process: they behave probabilistically until they acquire enough information about each other to trigger a mental threshold and then their choices stabilize. We effectively estimate this threshold using the Tolerance Principle (TP), a parameter-free equation first developed to model how children learn rules in language. We show that threshold-based agents produce social learning that is more accurate than imitating and optimizing agents, while also providing a better model of how a critical mass of dissenters can overturn conventions. The superior performance of our model holds when comparing against a variety of optimization approaches, including Bayesian inference. Furthermore, in a pre-registered dyadic experiment requiring people to infer non-linguistic behavioral patterns amid controlled levels of noise in observed signals, TP outperforms all other models at reproducing learning rates among human participants. These findings offer compelling evidence that a simple, mathematical threshold underlies individual and social learning, from grammatical rules to behavioral conventions.