Sign-rank vs Margin

on YouTube ↗58m

" summary

Two strong negative answers: small sign-rank does not force small margin because an explicit inner‑product construction (rows/columns are integer vectors) achieves sign-rank 3 with gamma2_infty = poly(N); the lower bound uses careful Fourier‑analysis to pick a distribution that balances every rectangle. The other direction also fails: low margin need not imply low sign‑rank — a continuous sphere/partial‑matrix version has full dimension by a Borsuk–Ulam obstruction, showing the Johnson–Lindenstrauss log factor is necessary. A related separation uses a modular‑prime randomized protocol to keep approximate gamma2 small while exact gamma2 is large.

AI-written summary · about

" chapters (5)

1. 0:00Start
2. 7:39Example
3. 12:54Applications of Rank
4. 30:39Main Lemma
5. 47:57Open problems

" related talks

• 36mThe Rank of Sparse Random MatricesJane Gao · Computational Phase Transitions (Simons Institute, 2020)
• 45mTractability And Overparametrization In Some Simple ModelsAndrea Montanari · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 35mSmoothed Analysis of Low Rank Solutions to Semidefinite Programs via Burer Monteiro FactorizationPraneeth Netrapalli · Randomized Numerical Linear Algebra and Applications 2018
• 01h 23mGeneralization IIPeter Bartlett, Sasha Rakhlin · Deep Learning Boot Camp 2019
• 01h 23mImplicit Regularization IINati Srebro · Deep Learning Boot Camp 2019
• 23mHow Large is the Norm of a Random Matrix?Ramon van Handel · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 23mLow-Rank Matrix Recovery Through Rank-One ProjectionsTony Cai · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 10mOptimization IIBen Recht · Big Data Boot Camp 2013