Modern computing applications involve data measured from complex, real-world phenomena, whose complexity stems from massive networks of dynamic, multifaceted relationships among typed entities. For example, human social interaction, electronic communication, and municipal operations all exhibit this form of complexity. Effective data-driven analysis of these phenomena requires computational tools expressive enough to model their complex structure. However, such models overextend the theoretical foundation that supports core machine learning methods. In this talk, I will describe new algorithmic tools for efficient machine learning of complex structured models, applications of these tools, and theoretical analysis to support them. Specifically, I will cover probabilistic soft logic (PSL), a modeling language for relational domains, highlighting PSL’s underlying mathematical foundation, its associated algorithms, and its applications to computational social science and computer vision problems. I will also discuss new theoretical guarantees that formally characterize our ability to learn complex structured models. Finally, I will share my vision of the immediate and long-term future for complex structured machine learning.