Nearest Neighbors II

on YouTube ↗01h 05m

" summary

One nearest neighbor has robustness radius → 0 at points where mu is continuous and eta(x)∈(0,1) so accuracy can remain high while robustness vanishes as n→∞. Letting K grow fast (K ≳ √(d n log n)/δ) makes K‑NN converge to the Bayes robust region. A practical defense keeps confident points (KN = 3 log(2N/δ)/δ²), then returns a maximal R‑separated subset and applies one‑NN — called adversarial pruning — and region‑based convex attacks (exact or approximate) make pruning competitive with prior defenses on trees, forests and NN.

AI-written summary · about

" chapters (43)

1. 0:00Intro
2. 2:44Many Classifiers are Vulnerable to Adversarial Examples
3. 2:55State of the Art
4. 3:52Statistical Learning Framework
5. 6:16Robustness wrt Distribution
6. 7:39Robustness Definitions
7. 8:27Astuteness: Combining Robustness and Accuracy
8. 10:22Prior Work - Parametric Methods
9. 14:32Constant k
10. 15:06Reminder: k-NN Accuracy
11. 17:01Some Notation
12. 19:10Robust Interiors
13. 21:42Where is Bayes Optimal Robust?
14. 25:44Proof Intuition
15. 27:58When is Nearest Neighbors Robust?
16. 29:43Getting Confident Labels
17. 30:43Full Algorithm
18. 31:52When is this algorithm robust?
19. 36:44Experiments: Details
20. 37:00White-box Attacks
21. 37:41White-Box Attack Results
22. 38:27Black-box Attacks
23. 39:11Black-Box Attack Results
24. 40:13Tutorial Outline
25. 42:32Beyond Nearest Neighbors...
26. 43:12Adversarial Examples for Parametric Methods
27. 44:11What about non-parametrics?
28. 44:53Talk Outline
29. 45:08Generic Attacks
30. 45:46Region-Based Attack
31. 46:27Approx Region Based Attack
32. 48:33Beyond the Bayes Optimal...
33. 49:03Maximizing Astuteness
34. 50:07suggests the classifier
35. 51:01A finite sample approximation...
36. 51:55How to solve this?
37. 52:33Algorithm: Adversarial Pruning
38. 52:54Evaluation
39. 53:13Attack Metric
40. 53:50Baselines
41. 55:51Defense Metric
42. 58:46Conclusion
43. 59:15Acknowledgements

" related talks

• 40mFast NN Prediction with No Statistical TradeoffSamory Kpotufe · Sublinear Algorithms and Nearest-Neighbor Search
• 01h 01mNearest Neighbor Methods IIIlya Razenshteyn · Foundations of Data Science Boot Camp 2018
• 43mSpectral Approaches to Nearest Neighbor SearchRobert Krauthgamer · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 42mDistribution-Specific Analysis of Nearest Neighbor Search and ClassificationSanjoy Dasgupta · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 48mSmooth Sensitivity for k-Nearest NeighborChristopher Clifton · Data Privacy: From Foundations to Applications (Simons Institute workshop, 2019)
• 46mSpectral Partitioning for Metrics (And NNs Too)Alex Andoni · Sublinear Algorithms and Nearest-Neighbor Search
• 01h 05mNearest Neighbor Methods IIlya Razenshteyn · Foundations of Data Science Boot Camp 2018
• 48mHolder Homeomorphisms and Approximate Nearest NeighborsIlya Razenshteyn · Sublinear Algorithms and Nearest-Neighbor Search