Hong Wang’s NeurIPS paper tightened low-rank approximation bounds with interpolation

量子位 · wechat · 2026-07-24

A retrospective on Hong Wang’s NeurIPS 2019 paper shows how a pure-math tool crossed into ML theory.

The paper studied low-rank matrix approximation via column subset selection (CSS).
It tightened the approximation ratio from a generic O(k+1) bound to (k+1)^(1/p) for 1 ≤ p ≤ 2 and (k+1)^(1-1/p) for p ≥ 2.
For p ≥ 2, the authors also proved a matching lower bound up to constant 1.
The key move was importing Riesz–Thorin interpolation, a classic harmonic-analysis theorem, to derive the full range of bounds from endpoint cases.
The piece argues this is exactly the kind of theory paper NeurIPS 2026 now wants to recognize: mathematically rigorous, methodologically original, and valuable even without large-scale experiments.

More from Models