Solvable Model of Unsupervised Feature Learning

on YouTube ↗46m

" summary

Defines a planted sparse dictionary matrix factorization (Gaussian noise, iid dictionary, sparse X) and computes the information‑theoretic MMSE via the replica-derived MMSE formula; derives an AMP algorithm with matching state-evolution and shows its predictions; finds a sharp sample‑complexity phase transition separating an easy region from an information‑theoretic-but‑algorithmically‑hard region; implements AMP variants and shows they converge only up to a strictly larger sample threshold than the optimal, leaving a sizable algorithmic gap to close.

AI-written summary · about

" chapters (25)

1. 0:00Intro
2. 1:15FEATURE LEARNING
3. 2:10MULTILAYER PERCEPTRON (SUPERVISED)
4. 4:34AUTO-ENCODER (UNSUPERVISED) (Rumelhart, Hinton, Williams 86)
5. 9:26SIMPLEST CASE TO STUDY
6. 13:17SOME KNOWN RESULTS
7. 15:04"PLANTED" MATRIX FACTORIZATION
8. 15:27BAYES-OPTIMAL STUDENT
9. 16:30SOLVABLE WITH REPLICAS
10. 18:34THE REPLICA METHOD
11. 21:46STATIONARITY CONDITIONS
12. 22:41AND ALGORITHMS?
13. 22:58GRAPHICAL MODEL
14. 23:51BELIEF PROPAGATION
15. 24:38Approximate message passing
16. 27:28AMP FOR MATRIX FACTORIZATION
17. 29:14GENERALITY OF AMP
18. 29:39STATE EVOLUTION
19. 30:14BOTTOM LINE
20. 31:11EXAMPLE: DICTIONARY LEARNING
21. 32:11The phase diagram of dictionary learning
22. 33:35Lower bound for the noiseless case and continuous variables
23. 34:17Sample complexity of dictionary learning
24. 39:33CONCLUSIONS
25. 40:36TO DO LIST

" related talks

• 29mAre Generative Models The New Sparsity?Bruno Loureiro · Rigorous Evidence for Information-Computation Trade-offs
• 35mPhase Retrieval In High Dimensions: Statistical And Computational Phase TransitionsAntoine Maillard · Rigorous Evidence for Information-Computation Trade-offs
• 01h 08mTutorial: Methods from Statistical Physics IIIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022
• 58mUniversality of Approximate Message Passing on Semi-random MatricesSubhabrata Sen · Deep Learning Theory Workshop and Summer School 2022
• 38mAll-or-Nothing Statistical and Computational Phase Transitions in Sparse Spiked Matrix EstimationCynthia Rush · Rigorous Evidence for Information-Computation Trade-offs
• 01h 06mTutorial: Methods from Statistical Physics IIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022
• 01h 04mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 19mGeneralSparse: Bridging the Gap in SpMM for Pruned Large Language Model Inference..Yaoyu Wang, Xiao Guo, Junmin Xiao, De Chen, Guangming Tan · USENIX ATC '25