The Ridgeless minimum $\ell_2$-norm interpolator in overparametrized linear regression has attracted considerable attention in recent years in both machine learning and statistics communities. While it seems to defy conventional wisdom that overfitting leads to poor prediction, recent theoretical research on its $\ell_2$-type risks reveals that its norm minimizing property induces an `implicit regularization' that helps prediction in spite of interpolation. This paper takes a further step that aims at understanding its precise stochastic behavior as a statistical estimator. Specifically, we characterize the distribution of the Ridgeless interpolator in high dimensions, in terms of a Ridge estimator in an associated Gaussian sequence model with positive regularization, which provides a precise quantification of the prescribed implicit regularization in the most general distributional sense. Our distributional characterizations hold for general non-Gaussian random designs and extend uniformly to positively regularized Ridge estimators. As a direct application, we obtain a complete characterization for a general class of weighted $\ell_q$ risks of the Ridge(less) estimators that are previously only known for $q=2$ by random matrix methods. These weighted $\ell_q$ risks not only include the standard prediction and estimation errors, but also include the non-standard covariate shift settings. Our uniform characterizations further reveal a surprising feature of the commonly used generalized and $k$-fold cross-validation schemes: tuning the estimated $\ell_2$ prediction risk by these methods alone lead to simultaneous optimal $\ell_2$ in-sample, prediction and estimation risks, as well as the optimal length of debiased confidence intervals.

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.

The Stochastic Block Model (SBM) is a widely used random graph model for networks with communities. Despite the recent burst of interest in community detection under the SBM from statistical and computational points of view, there are still gaps in understanding the fundamental limits of recovery. In this paper, we consider the SBM in its full generality, where there is no restriction on the number and sizes of communities or how they grow with the number of nodes, as well as on the connectivity probabilities inside or across communities. For such stochastic block models, we provide guarantees for exact recovery via a semidefinite program as well as upper and lower bounds on SBM parameters for exact recoverability. Our results exploit the tradeoffs among the various parameters of heterogenous SBM and provide recovery guarantees for many new interesting SBM configurations.