Leslie G. Valiant is a British-American computer scientist and the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics at Harvard University. His research spans computational learning theory, the theory of computation, computational neuroscience, and artificial intelligence. He received the ACM Turing Award in 2010 for transformative contributions to the theory of computation, including learning theory and the theory of parallel and distributed computing.
Valiant is best known for introducing PAC learning, short for “probably approximately correct,” in a 1984 paper. The idea gave machine learning its first rigorous foundation: it defines learning as finding, from a limited number of examples, a hypothesis that is probably (with high confidence) approximately (with small error) correct on new data it has not seen. PAC learning made it possible to ask precise questions, such as how many examples a learner needs, or whether a given problem is learnable at all, rather than treating learning as an art. It is one of the pillars of the field now called statistical learning theory.
The library’s reader meets Valiant’s work every time the question “but does it actually generalize?” comes up. PAC learning is the formal answer to why a model trained on a finite sample can be trusted on future data, and it underlies the guarantees, and the honest limits, behind modern machine learning. Valiant also pursued a deeper version of the same instinct, asking how learning could be the basic mechanism that biology and evolution use to cope with a complex world.