Spectral Methods for Machine Learning and Network Analysis

CMSC 35410 · University of Chicago · Autumn 2026

Spectral methods study complex systems through the eigenvalues and eigenvectors of associated linear operators. Because the theory extends from finite-dimensional linear algebra to infinite-dimensional operators, it gives one framework for problems ranging from graph partitioning and random walks to manifold learning and the numerical solution of differential equations. This graduate course develops that theory and its algorithmic uses, with a focus on spectral graph theory and spectral methods in machine learning.

Logistics

Instructor Lorenzo Orecchia
Lectures T and Th 9.30-10.50am in JCL 011
Office hours TBD and Th 11am-12pm 315
Communication Slack
Prerequisites Linear algebra, probability, and algorithms at the advanced undergraduate level.

Tentative topics

Finite dimensions

  • Spectral graph theory
  • Random walks on graphs and their convergence
  • Spectral clustering
  • Cheeger’s inequality
  • Spectral algorithms via semidefinite programming
  • Spectral sparsification
  • Expander graphs
  • Markov chain mixing times and log-Sobolev inequalities
  • Method of moments for latent-variable models

Infinite dimensions

  • Sturm–Liouville theory and spectral decomposition
  • Markov processes in continuous space and their generators
  • Brownian motion and the Laplacian
  • Langevin dynamics and the Fokker–Planck equation
  • Bakry–Émery theory
  • Manifold learning and diffusion maps
  • Spectral collocation methods

Getting started

Grading

Component Weight
Project 30%
In-class final 30%
Oral final exam 30%
Participation 10%