We study the classification problem under the two-component anisotropic sub-Gaussian mixture model in high dimensions and in the non-asymptotic setting. First, we derive lower bounds and matching upper bounds for the minimax risk of classification in this framework. We also show that in the high-dimensional regime, the linear discriminant analysis classifier turns out to be sub-optimal in the minimax sense. Next, we give precise characterization of the risk of classifiers based on solutions of $\ell_2$-regularized least squares problem. We deduce that the interpolating solutions may outperform the regularized classifiers under mild assumptions on the covariance structure of the noise, and present concrete examples of this phenomenon. Our analysis also demonstrates robustness of interpolation to certain models of corruption. To the best of our knowledge, this peculiar fact has not yet been investigated in the rapidly growing literature related to interpolation. We conclude that interpolation is not only benign but can also be optimal, and in some cases robust.

We establish sufficient conditions of exact and almost full recovery of the node partition in Bipartite Stochastic Block Model (BSBM) using polynomial time algorithms. First, we improve upon the known conditions of almost full recovery by spectral clustering algorithms in BSBM. Next, we propose a new computationally simple and fast procedure achieving exact recovery under milder conditions than the state of the art. Namely, if the vertex sets$V_{1}$and$V_{2}$in BSBM have sizes$n_{1}$and$n_{2}$, we show that the condition$ p = \Omega \left ({\max \left ({\sqrt {\frac {\log {n_{1}}}{n_{1}n_{2}}},\frac {\log {n_{1}}}{n_{2}}}\right )}\right )$on the edge intensity$p$is sufficient for exact recovery within$V_{1}$. This condition exhibits an elbow at$n_{2} \asymp n_{1}\log {n_{1}}$between the low-dimensional and high-dimensional regimes. The suggested procedure is a variant of Lloyd’s iterations initialized with a well-chosen spectral estimator leading to what we expect to be the optimal condition for exact recovery in BSBM. The optimality conjecture is supported by showing that, for a supervised oracle procedure, such a condition is necessary to achieve exact recovery. The key elements of the proof techniques are different from classical community detection tools on random graphs. Numerical studies confirm our theory, and show that the suggested algorithm is both very fast and achieves almost the same performance as the supervised oracle. Finally, using the connection between planted satisfiability problems and the BSBM, we improve upon the sufficient number of clauses to completely recover the planted assignment.

In the context of high-dimensional linear regression models, we propose an algorithm of exact support recovery in the setting of noisy compressed sensing where all entries of the design matrix are independent and identically distributed standard Gaussian. This algorithm achieves the same conditions of exact recovery as the exhaustive search (maximal likelihood) decoder, and has an advantage over the latter of being adaptive to all parameters of the problem and computable in polynomial time. The core of our analysis consists in the study of the non-asymptotic minimax Hamming risk of variable selection. This allows us to derive a procedure, which is nearly optimal in a non-asymptotic minimax sense. Then, we develop its adaptive version, and propose a robust variant of the method to handle datasets with outliers and heavy-tailed distributions of observations. The resulting polynomial time procedure is near optimal, adaptive to all parameters of the problem and also robust.

In this paper, we study a new notion of scaled minimaxity for sparse estimation in high-dimensional linear regression model. We present more optimistic lower bounds than the one given by the classical minimax theory and hence improve on existing results. We recover sharp results for the global minimaxity as a consequence of our study. Fixing the scale of the signal-to-noise ratio, we prove that the estimation error can be much smaller than the global minimax error. We construct a new optimal estimator for the scaled minimax sparse estimation. An optimal adaptive procedure is also described.