The availability of large scale datasets requires the development of ever more efficient machine learning solutions. A key feature towards scalability is to tailor computational requirements to the generalization properties in the data, rather than their raw amount. This project aims at blending statistical and algorithmic principles to design new, sound and scalable learning machines.