We consider the problem of estimating an unknown matrix $\boldsymbol{X}\in {\mathbb R}^{m\times n}$, from observations $\boldsymbol{Y} = \boldsymbol{X}+\boldsymbol{W}$ where $\boldsymbol{W}$ is a noise matrix with independent and identically distributed entries, as to minimize estimation error measured in operator norm. Assuming that the underlying signal $\boldsymbol{X}$ is low-rank and incoherent with respect to the canonical basis, we prove that minimax risk is equivalent to $(\sqrt{m}\vee\sqrt{n})/\sqrt{I_W}$ in the high-dimensional limit $m,n\to\infty$, where $I_W$ is the Fisher information of the noise. Crucially, we develop an efficient procedure that achieves this risk, adaptively over the noise distribution (under certain regularity assumptions). Letting $\boldsymbol{X} = \boldsymbol{U}{\boldsymbolΣ}\boldsymbol{V}^{\sf T}$ --where $\boldsymbol{U}\in {\mathbb R}^{m\times r}$, $\boldsymbol{V}\in{\mathbb R}^{n\times r}$ are orthogonal, and $r$ is kept fixed as $m,n\to\infty$-- we use our method to estimate $\boldsymbol{U}$, $\boldsymbol{V}$. Standard spectral methods provide non-trivial estimates of the factors $\boldsymbol{U},\boldsymbol{V}$ (weak recovery) only if the singular values of $\boldsymbol{X}$ are larger than $(mn)^{1/4}{\rm Var}(W_{11})^{1/2}$. We prove that the new approach achieves weak recovery down to the the information-theoretically optimal threshold $(mn)^{1/4}I_W^{1/2}$.