Robust Gradient Descent: Agnostically Estimating an Unknown Affine Transformation...

on YouTube ↗51m

" summary

Claims a polynomial-time algorithm that, from an ε‑corrupted sample of an unknown affine transform of the d‑cube, outputs ĤA, Ĥb with total variation O(ε) using poly(d) time and samples. It replaces moment methods (which provably fail here) with Robust Gradient Descent plus a geometric certificate and pairwise‑slab filtering: iteratively estimate slab means robustly, remove high‑density intersections, and converge to the parallelepiped up to optimal information‑theoretic error.

AI-written summary · about

" chapters (12)

1. 0:00Problem introduction
2. 2:25Geometric transformation
3. 5:13Robust statistics context
4. 7:49Algorithmic robust statistics
5. 9:42Role of moments
6. 11:59Challenge of TV distance
7. 16:19Iterative learning algorithm
8. 20:53Theoretical lemma proof
9. 24:56Handling rotation
10. 32:56Unified algorithm
11. 35:49Open problems and Q&A
12. 44:46Technical derivation