The concept of an output-driven map formally characterizes an intuitive notion about phonology: that disparities between the input and the output are introduced only to the extent necessary to satisfy restrictions on outputs. When all of the grammars definable in a phonological system are output-driven, the implied structure provides significant computational benefits to language learners. An output-driven map imposes significant structure on the space of possible inputs for words, which can allow a learner to efficiently learn a lexicon of phonological underlying forms despite the vast number of possible lexica, as well as contend with the challenges of map/lexicon interactions inherent in phonological learning. This article presents a learning algorithm that exploits the structure of output-driven maps, illustrated with a system of grammars based in Optimality Theory. The algorithm highlights the roles played by contrast and paradigmatic information in phonological learning.