Rong Ge asks the class how one usually handles NP-hard problems; a student answers "some sort of approximation" 22:21, 23:07. That opens a survey of four options.

1. Approximation algorithms

  • Sometimes genuinely fine: for well-separated k-means data, even a 2- or 3-approximation gives a reasonable clustering 23:29.
  • But it fails for maximum likelihood, because the objective is a sum of log probabilities (a negative number) 23:29, 24:06.
  • The killer detail: a constant factor in log-probability space is not a constant factor in probability space — if two logs are within a constant factor, their exponentials need not be, so the recovered θ can assign vastly lower probability than the optimum 24:06, 24:29.

2. Average-case analysis

  • Solving the worst case would be ideal, but that only happens for very special problems 24:53.
  • Being able to solve the average case — data actually drawn from D(θ) — is already a satisfying result, and potentially much easier 24:53, 25:21.
  • Realistically one may want something in between: data roughly generated by D(θ) 25:21.
  • Average case can also cover randomness in the parameters themselves — e.g. assuming Gaussian means are random vectors, which further simplifies the problem 25:47, 26:08.

3. Natural assumptions — the lecture's chosen route

  • Abstract models like mixtures of Gaussians apply in many settings, but in a specific real system the parameters carry meaning, and that meaning yields extra restrictions enabling faster algorithms 26:08, 26:41.
  • This is the route the rest of the lecture takes for topic models 26:08.

4. Heuristics

  • If nothing else works, use a heuristic and hope it does well in practice 26:41.

The synthesis

  • These options are not mutually exclusive. Using a heuristic should not stop you from analyzing it under average-case or natural-assumption models 27:25.
  • The stated research goal: a heuristic algorithm that works in practice, which we can also analyze under approximation, average case, or natural assumptions 27:25, 28:24.
  • Status of the field: achieved for only a small set of problems; a relatively new area with many open problems 28:24, 29:20.
  • What today delivers instead: an algorithm different from the existing heuristics, analyzable under natural assumptions, for learning topic models 29:20.