Machine learning enjoys a deep and powerful theory that has led to a wide variety of highly successful practical tools. However, most of this theory is developed under some simplifying assumptions that clearly fail in the real world. In particular, a fundamental assumption of the theory is that the data available for training and the data of the target application come from the same source. When this assumption fails, the learner is faced with a “domain adaptation” challenge. In the past few years, the range of machine learning applications have been expanded to include various tasks requiring domain adaptation. Such application have been addressed by several heuristic paradigms. However, the common theoretical models fall short of providing useful analysis of these techniques. The key to domain adaptation is the similarity between the training and target domains. In this talk I will discuss several parameters along which task similarity can be defined and measured and discuss to what extent can they be utilized to direct learning algorithms and guarantee their success. Recent work can provide theoretical justification to some existing practical heuristics, as well as guide the development of novel algorithms for handling some types of data discrepancies. However, our current understanding leaves much to be desired. I shall devote the last part of the talk to describing some of the challenges and open questions that will have to be addressed before one can claim satisfactory understanding of learning in the presence of training-test discrepancies. The talk is based on joint works with John Blitzer, Koby Crammer and Fernando Pereira and with my students, David Pal, Teresa Luu and Tyler Lu.