Back to the Future: Going Beyond Worst Case Analysis
summary
Argues that worst-case NP-hardness misses real instances and shows concrete alternatives: assumes separable (anchor) words in topic models, uses convex programming to pick vertices of the simplex, implements a Python solver that empirically outperforms LDA heuristics on NYT data. Presents a generative log‑linear model explaining why the PMI matrix is low‑rank, derives predictions about word embeddings, and recommends making minimal realistic assumptions and exploiting input distributional structure rather than relying only on worst‑case tools.
AI-written summary · about
chapters (9)
- 0:00Start
- 0:43Berkeley, 1990-94
- 8:07Also in Machine Learning...
- 9:18Is NP-hardness an obstacle for understanding reality?
- 14:02"Bag of words" Assumption in Text Analysis
- 14:55Topic Models: Hidden Variable Explanation
- 16:53"Separable" Topic Matrices
- 17:47Separability changes problem geometry!
- 21:29PMI Matrix
related talks
52mLearning as a Tool for Algorithm Design and Beyond-Worst-Case Analysis
45mEvaluating Topic Models
51mHow to Predict When Estimation is Hard: Algorithms for Learning on Graphs
45mDecoding Topics: A Comparative Analysis of Python’s Leading Topic Modeling Libraries Using Climate C
56mTensor Decompositions for Learning Latent Variable Models I
01h 10mModern paradigms of generalization, the heliocentric model of Aristarchus,...
46mWhy data-driven methods will shape the future (...)
43mProbabilistic Programming in the Real World