6.883 Advanced Machine Learning  —  Learning with Combinatorial Structure

Real-world machine learning tasks frequently involve combinatorial structure. How model, infer or predict with graphs, matchings, hierarchies, informative subsets or other discrete structure underlying the data? This graduate course explores mathematical models, overarching concepts and algorithmic techniques for solving such problems efficiently. A focus will lie on understanding connections between machine learning, suitable representations, and convex and combinatorial optimization.


  • Time: MW 11-12:30

  • Location: 2-105

  • Instructor: Prof. Stefanie Jegelka
    Room 32-G472
    Office hours: Wed 1.30-2.30pm

  • TA: Zi Wang

Tentative List of Topics


  • structured prediction

  • combinatorial norms, (structured) sparse and low-rank representations

  • modeling diversity, informativeness and influence

  • selected graph and network problems

Overarching concepts and representations

  • polyhedral representations: convex hulls and combinatorial polyhedra

  • submodular functions and matroids

  • determinantal representations: diversity, repulsion and random trees


  • submodular optimization: relaxations, convexity, greedy methods

  • non-smooth convex optimization

  • conditional gradients everywhere

  • scaling to larger problems, splitting methods, online and stochastic methods

  • statistical and computational tradeoffs


Disclaimer: these lecture notes have been checked only loosely, and may contain typos or errors. If you find any, please let me know. If you find those notes useful, I'd be happy to hear about that too. Not all lectures were scribed, so the below only covers parts of the course.