Learning to produce complex outputs encompasses many fundamental and application problems. A research direction has been Extreme Classification, a new challenge consisting in classifying with millions of classes. MLIA has organized 4 international challenges and workshops on this topic and participated to a EU project. We are also investigating classification in graphs for social networks and image segmentation. In a Franco-Canadian project, we are combining deep learning and structured prediction.