We propose $\textsf{ScaledGD($\lambda$)}$, a preconditioned gradient descent method to tackle the low-rank matrix sensing problem when the true rank is unknown, and when the matrix is possibly ill-conditioned. Using overparametrized factor representations, $\textsf{ScaledGD($\lambda$)}$ starts from a small random initialization, and proceeds by gradient descent with a specific form of preconditioning with a fixed damping term to combat overparameterization. At the expense of light computational overhead incurred by preconditioners, $\textsf{ScaledGD($\lambda$)}$ is remarkably robust to ill-conditioning compared to vanilla gradient descent ($\mathsf{GD}$). Specifically, we show that, under the Gaussian design, $\textsf{ScaledGD($\lambda$)}$ converges to the true low-rank matrix at a constant linear rate that is independent of the condition number (apart from a short nearly dimension-free burdening period), with near-optimal sample complexity. This significantly improves upon the convergence rate of vanilla $\mathsf{GD}$ which suffers from a polynomial dependency with the condition number. Our work provides evidence on the power of preconditioning in accelerating the convergence without hurting generalization in overparameterized learning.

The Gaussian-smoothed optimal transport (GOT) framework, pioneered by Goldfeld et al. and followed up by a series of subsequent papers, has quickly caught attention among researchers in statistics, machine learning, information theory, and related fields. One key observation made therein is that, by adapting to the GOT framework instead of its unsmoothed counterpart, the curse of dimensionality for using the empirical measure to approximate the true data generating distribution can be lifted. The current paper shows that a related observation applies to the estimation of nonparametric mixing distributions in discrete exponential family models, where under the GOT cost the estimation accuracy of the nonparametric MLE can be accelerated to a polynomial rate. This is in sharp contrast to the classical sub-polynomial rates based on unsmoothed metrics, which cannot be improved from an information-theoretical perspective. A key step in our analysis is the establishment of a new Jackson-type approximation bound of Gaussian-smoothed Lipschitz functions. This insight bridges existing techniques of analyzing the nonparametric MLEs and the new GOT framework.

In the Gaussian sequence model$Y= \theta _{0} + \varepsilon $in$\mathbb {R}^{n}$, we study the fundamental limit of statistical estimation when the signal$\theta _{0}$belongs to a class$\Theta _{n}(d,d_{0},k)$of (generalized) splines with free knots located at equally spaced design points. Here$d$is the degree of the spline,$d_{0}$is the order of differentiability at each inner knot, and$k$is the maximal number of pieces. We show that, given any integer$d\geq 0$and$d_{0}\in \{-1,0,\ldots,d-1\}$, the minimax rate of estimation over$\Theta _{n}(d,d_{0},k)$exhibits the following phase transition:$\begin{aligned} \inf _{ \widetilde {\theta }}\sup _{\theta \in \Theta _{n}(d,d_{0}, k)} \mathbb {E}_\theta \lVert \widetilde {\theta } - \theta \rVert _{}^{2} \asymp _{d} \begin{cases} k\log \log (16n/k), & 2\leq k\leq k_{0},\\ k\log (en/k), & k \geq k_{0}+1. \end{cases} \end{aligned}$The transition boundary$k_{0}$, which takes the form$\left \lfloor{ (d+1)/(d-d_{0}) }\right \rfloor + 1$, demonstrates the critical role of the regularity parameter$d_{0}$in the separation between a faster$\log \log (16n)$and a slower$\log (en)$rate. We further show that, once encouraging an additional ‘$d$-monotonicity’ shape constraint (including monotonicity for$d = 0$and convexity for$d=1$), the above phase transition is removed and the faster$k\log \log (16n/k)$rate can be achieved for all$k$. These results provide theoretical support for developing$\ell _{0}$-penalized (shape-constrained) spline regression procedures as useful alternatives to$\ell _{1}$- and$\ell _{2}$-penalized ones.