Semi-Random Models and Robustness in Unsupervised Learning

on YouTube ↗45m

" summary

A semi-random model mixes a tiny fraction beta of truly random sparse supports with adversarially chosen supports and shows polynomial-time recovery of the dictionary A and sparse codes X up to any accuracy when incoherence holds and sparsity up to sqrt(n) (purely random analysis extends to about n^{2/3}). Recovery uses a testing procedure that reads inner-product histograms (bimodal if a candidate equals a column) plus weighted-sum candidate generation, proven via coupling/CLT and concentration bounds; identifiability follows from a mild triples condition.

AI-written summary · about

" chapters (16)

1. 0:00Semi-random Models and Robustness in Unsupervised Learning
2. 0:31Probabilistic Modeling in ML
3. 1:33Semirandom models
4. 4:19Monotone Adversaries Feige-Kilian
5. 5:22Monotone Adversaries - 1" type **Improving" planted solution
6. 8:06Monotone Adversaries - 2nd type Additional information about signal
7. 15:57Guarantees for Dictionary Learning
8. 20:56Goal
9. 26:58Main Results
10. 29:40o(n2/3) Sparsity in the Random Model (B = 1)
11. 32:09Identifiability Under Minimal Assumptions
12. 33:23Techniques
13. 34:52Testing Procedure
14. 38:30Key Lemma (Soundness for NO case)
15. 40:59Candidate Generation
16. 44:25Conclusion

" related talks

• 45mHigh Dimensional Robust Sparse RegressionConstantine Caramanis · Sublinear Algorithms and Nearest-Neighbor Search
• 12mDistribution-Free RobustnessSitan Chen · Meet the Fellows Welcome Event
• 01h 05mRecovering Hidden Sparsity via Sum of SquaresJonathan Kelner · Semidefinite Optimization, Approximation and Applications 2014
• 40mThe Trimmed Lasso: Sparse Recovery Guarantees And Practical OptimizationBoaz Nadler · Statistics in the Big Data Era 2022
• 01h 01mRobustness, Stochastics, Uncertainty 1Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 53mDesigning Robust LearnersJacob Steinhardt · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 19mSupport Recovery in Universal One-bit Compressed SensingSoumyabrata Pal, Arya Mazumdar · ITCS 2022
• 01h 24mAdversarial ExamplesSebastien Bubeck · Deep Learning Boot Camp 2019