Abstract: Many problems in Machine Learning and Data Science require solving large-scale discrete optimization problems under uncertainty. In the recent years, a fundamental problem structure has emerged as extremely useful for addressing such problems: Submodularity is an intuitive diminishing returns property. Submodularity naturally occurs in numerous applications such as data summarization, information retrieval, network analysis, active learning and experimental design, sparse modelling and inference in probabilistic models. Exploiting submodularity allows to devise efficient algorithms with strong theoretical guarantees. In this talk, I will give an introduction to the concept of submodularity and discuss basic algorithms and applications of submodular optimization.