Leslie Valiant

Leslie Valiant is the mathematician who asked the question that made machine learning a science rather than a craft: when can a machine learn? His 1984 paper A Theory of the Learnable introduced Probably Approximately Correct (PAC) learning—a framework that defines what it means for an algorithm to learn a concept from examples, specifying precisely how many examples are needed, how much computation may be expended, and with what probability of success. PAC learning gave machine learning the vocabulary of the theoretical computer scientist: complexity bounds, sample bounds, impossibility results. It proved that learning is not magic but a precisely analyzable computational process, with definite limits on what can be learned efficiently from a given amount of data. Valiant was born in Hungary in 1949 and received his doctorate from Warwick in 1974; he has been at Harvard since 1982. He received the 2010 ACM Turing Award for his foundational contributions to learning theory and