  The classical low rank approximation problem is to find a rank $k$ matrix
$UV$ (where $U$ has $k$ columns and $V$ has $k$ rows) that minimizes the
Frobenius norm of $A - UV$. Although this problem can be solved efficiently, we
study an NP-hard variant of this problem that involves weights and
regularization. A previous paper of [Razenshteyn et al. '16] derived a
polynomial time algorithm for weighted low rank approximation with constant
rank. We derive provably sharper guarantees for the regularized version by
obtaining parameterized complexity bounds in terms of the statistical dimension
rather than the rank, allowing for a rank-independent runtime that can be
significantly faster. Our improvement comes from applying sharper matrix
concentration bounds, using a novel conditioning technique, and proving
structural theorems for regularized low rank problems.
