Theoretical analysis has played a major role in some of the most prominent practical successes of statistical machine learning. However, mainstream machine learning theory assumes some strong simplifying assumptions which are often unrealistic. In the past decade, the practice of machine learning has led to the development of various heuristic paradigms that answer the needs of a vastly growing range of applications. Many useful such paradigms fall beyond the scope of the currently available analysis. Will theory play a similar pivotal role in the newly emerging sub areas of machine learning? In this talk, I will survey some such application-motivated theoretical challenges. In particular, I will discuss recent developments in the theoretical analysis of semi-supervised learning, multi-task learning, “learning to learn”, privacy-preserving learning and more.