, The next Proposition states some important properties of c( ) = (c k ( )) k2N when satisfies (?). In what follows, we write for brevity c k = c k (
Community detection and stochastic block models, 2017. ,
, Exact recovery in the stochastic block model, 2014.
Entrywise eigenvector analysis of random matrices with low expected rank, 2017. ,
Thresholding of wavelet coefficients as multiple hypotheses testing procedure, Wavelets and statistics, pp.5-14, 1995. ,
Adapting to unknown sparsity by controlling the false discovery rate, The Annals of Statistics, vol.34, issue.2, pp.584-653, 2006. ,
Handbook of mathematical functions: with formulas, graphs, and mathematical tables, Courier Corporation, vol.55, 1964. ,
Information theoretic bounds for compressed sensing, IEEE Transactions on Information Theory, vol.56, issue.10, pp.5111-5130, 2010. ,
Sparse signal processing with linear and nonlinear observations: A unified Shannon-theoretic approach, IEEE Transactions on Information Theory, vol.63, issue.2, pp.749-776, 2017. ,
The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, vol.58, issue.1, pp.137-147, 1999. ,
Distribution-free multiple testing, Electronic Journal of Statistics, vol.11, issue.1, pp.1983-2001, 2017. ,
Improved spectral-norm bounds for clustering, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp.37-49, 2012. ,
Rate optimality of wavelet series approximations of fractional brownian motion, Journal of Fourier Analysis and Applications, vol.9, issue.5, pp.451-471, 2003. ,
Informationtheoretic bounds and phase transitions in clustering, sparse pca, and submatrix localization, IEEE Transactions on Information Theory, 2018. ,
, The noise barrier and the large signal bias of the lasso and other convex estimators, 2018.
Slope meets lasso: improved oracle bounds and optimality, The Annals of Statistics, vol.46, issue.6B, pp.3603-3642, 2018. ,
Pivotal estimation via square-root lasso in nonparametric regression, The Annals of Statistics, vol.42, issue.2, pp.757-788, 2014. ,
, Sparse covariance matrix estimation in high-dimensional deconvolution, 2017.
The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices, Advances in Mathematics, vol.227, issue.1, pp.494-521, 2011. ,
URL : https://hal.archives-ouvertes.fr/hal-00423593
The singular values and vectors of low rank perturbations of large rectangular random matrices, Journal of Multivariate Analysis, vol.111, pp.120-135, 2012. ,
URL : https://hal.archives-ouvertes.fr/hal-00575203
Computational lower bounds for sparse pca, 2013. ,
Selection of variables and dimension reduction in highdimensional non-parametric regression, Electronic Journal of Statistics, vol.2, pp.1224-1241, 2008. ,
Slopeadaptive variable selection via convex optimization, The annals of applied statistics, vol.9, issue.3, p.1103, 2015. ,
Percolation processes: I. crystals and mazes, Mathematical Proceedings of the Cambridge Philosophical Society, vol.53, pp.629-641, 1957. ,
Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix, ESAIM: Probability and Statistics, vol.19, pp.115-134, 2015. ,
Minimax estimation of the noise level and of the deconvolution density in a semiparametric convolution model, Bernoulli, vol.11, issue.2, pp.309-340, 2005. ,
URL : https://hal.archives-ouvertes.fr/hal-00101845
Variable selection with hamming loss, The Annals of Statistics, vol.46, issue.5, pp.1837-1875, 2018. ,
Adaptive variable selection in nonparametric sparse additive models, Electronic Journal of Statistics, vol.11, issue.1, pp.2321-2357, 2017. ,
Optimal rates of convergence for estimating the null density and proportion of nonnull effects in large-scale multiple testing, The Annals of Statistics, vol.38, issue.1, pp.100-145, 2010. ,
Orthogonal matching pursuit for sparse signal recovery with noise, IEEE Transactions on Information Theory, vol.57, issue.7, pp.4680-4688, 2011. ,
The dantzig selector: Statistical estimation when p is much larger than n. The annals of Statistics, vol.35, pp.2313-2351, 2007. ,
, , 2018.
, Minimax rate of testing in sparse linear regression
Adaptive estimation of the sparsity in the gaussian vector model, The Annals of Statistics, vol.47, issue.1, pp.93-126, 2019. ,
Challenging the empirical mean and empirical variance: a deviation study, Annales de l'IHP Probabilités et statistiques, vol.48, pp.1148-1185, 2012. ,
URL : https://hal.archives-ouvertes.fr/hal-00517206
Oracle inequalities for inverse problems, Annals of Statistics, vol.30, issue.3, pp.843-874, 2002. ,
Robust covariance and scatter matrix estimation under huber's contamination model, The Annals of Statistics, vol.46, issue.5, pp.1932-1960, 2018. ,
, Fast mean estimation with sub-gaussian rates, 2019.
Minimax estimation of linear and quadratic functionals on sparsity classes, The Annals of Statistics, vol.45, issue.3, pp.923-958, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01215833
Optimal adaptive estimation of linear functionals under sparsity, The Annals of Statistics, vol.46, issue.6A, pp.3130-3150, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-01425801
Minimax estimation of a p-dimensional linear functional in sparse gaussian models and robust estimation of the mean, 2017. ,
Adaptive robust estimation in sparse vector model, 2018. ,
Tight conditions for consistency of variable selection in the context of high dimensionality, The Annals of Statistics, vol.40, issue.5, pp.2667-2696, 2012. ,
URL : https://hal.archives-ouvertes.fr/hal-00602211
Functional quantization-based stratified sampling methods, 2010. ,
URL : https://hal.archives-ouvertes.fr/hal-01172309
A probabilistic analysis of em for mixtures of separated, spherical gaussians, Journal of Machine Learning Research, vol.8, pp.203-226, 2007. ,
A direct formulation for sparse pca using semidefinite programming, Advances in neural information processing systems, pp.41-48, 2005. ,
A karhunen-loève expansion for a mean-centered brownian bridge, Statistics & probability letters, vol.77, issue.12, pp.1190-1200, 2007. ,
Improved bounds for square-root lasso and square-root slope, Electronic Journal of Statistics, vol.12, issue.1, pp.741-766, 2018. ,
Sub-gaussian mean estimators, The Annals of Statistics, vol.44, issue.6, pp.2695-2725, 2016. ,
URL : https://hal.archives-ouvertes.fr/hal-01204519
Robust estimators in high dimensions without the computational intractability, 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp.655-664, 2016. ,
Being robust (in high dimensions) can be practical, Proceedings of the 34th International Conference on Machine Learning, vol.70, pp.999-1008, 2017. ,
Fast and exact simulation of stationary gaussian processes through circulant embedding of the covariance matrix, SIAM Journal on Scientific Computing, vol.18, issue.4, pp.1088-1107, 1997. ,
An optimalstorage approach to semidefinite programming using approximate complementarity, 2019. ,
Maximum entropy and the nearly black object, Journal of the Royal Statistical Society: Series B (Methodological), vol.54, issue.1, pp.41-67, 1992. ,
A series expansion of fractional brownian motion, Probability theory and related fields, vol.130, pp.39-55, 2004. ,
On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci, vol.5, pp.17-61, 1960. ,
Sure independence screening for ultrahigh dimensional feature space, Journal of the Royal Statistical Society: Series B (Statistical Methodology), vol.70, issue.5, pp.849-911, 2008. ,
Hidden integrality of sdp relaxation for sub-gaussian mixture models, 2018. ,
Subsampled power iteration: a unified algorithm for block models and planted csp's, Advances in Neural Information Processing Systems, pp.2836-2844, 2015. ,
Sorted concave penalized regression, 2017. ,
The largest eigenvalue of rank one deformation of large wigner matrices, Communications in mathematical physics, vol.272, issue.1, pp.185-228, 2007. ,
Necessary and sufficient conditions for sparsity pattern recovery, IEEE Transactions on Information Theory, vol.55, issue.12, pp.5758-5772, 2009. ,
, Spectral thresholds in the bipartite stochastic block model. In Conference on Learning Theory, pp.943-959, 2016.
An iht algorithm for sparse recovery from subexponential measurements, IEEE Signal Processing Letters, vol.24, issue.9, pp.1280-1283, 2017. ,
Sparse high-dimensional linear regression. Algorithmic barriers and a local search algorithm, 2017. ,
Exact exponent in optimal rates for crowdsourcing, International Conference on Machine Learning, pp.603-611, 2016. ,
Community detection in degree-corrected block models, The Annals of Statistics, vol.46, issue.5, pp.2153-2185, 2018. ,
Fundamental limits of exact support recovery in high dimensions, 2018. ,
Pivotal estimation in high-dimensional regression via linear programming, Empirical inference, pp.195-204, 2013. ,
URL : https://hal.archives-ouvertes.fr/hal-00805556
A comparison of the lasso and marginal regression, Journal of Machine Learning Research, vol.13, pp.2107-2143, 2012. ,
Introduction to high-dimensional statistics, 2014. ,
, Partial recovery bounds for clustering with the relaxed k means, 2018.
On estimation of the noise variance in highdimensional linear models, 2017. ,
Optimal estimation of genetic relatedness in high-dimensional linear models, Journal of the American Statistical Association, pp.1-12, 2018. ,
Innovated higher criticism for detecting sparse signals in correlated noise, The Annals of Statistics, vol.38, issue.3, pp.1686-1732, 2010. ,
A lower bound for the critical probability in a certain percolation process, Mathematical Proceedings of the Cambridge Philosophical Society, vol.56, pp.13-20, 1960. ,
A sharper bonferroni procedure for multiple tests of significance, Biometrika, vol.75, issue.4, pp.800-802, 1988. ,
Stochastic blockmodels: First steps, Social networks, vol.5, issue.2, pp.109-137, 1983. ,
A simple sequentially rejective multiple test procedure, Scandinavian journal of statistics, pp.65-70, 1979. ,
Sub-gaussian mean estimation in polynomial time, 2018. ,
A tail inequality for quadratic forms of subgaussian random vectors. Electronic Communications in Probability, p.17, 2012. ,
Robust estimation of a location parameter, Breakthroughs in statistics, pp.492-518, 1992. ,
, Robust statistics, 2011.
Statistical estimation: asymptotic theory, vol.16, 2013. ,
A rate-optimal trigonometric series expansion of the fractional brownian motion, Electron. J. Probab, vol.10, pp.1381-1397, 2005. ,
Inequalities for quantiles of the chi-square distribution, Probability and Mathematical Statistics, vol.30, issue.2, pp.339-351, 2010. ,
Adaptive variable selection in nonparametric sparse regression, Journal of Mathematical Sciences, vol.199, issue.2, pp.184-201, 2014. ,
On the convergence of sums of independent banach space valued random variables, Osaka Journal of Mathematics, vol.5, issue.1, pp.35-48, 1968. ,
Eigenprism: inference for high dimensional signal-to-noise ratios, Journal of the Royal Statistical Society: Series B (Statistical Methodology), vol.79, issue.4, pp.1037-1065, 2017. ,
Debiasing the lasso: Optimal sample size for gaussian designs, The Annals of Statistics, vol.46, issue.6A, pp.2593-2622, 2018. ,
Random generation of combinatorial structures from a uniform distribution, Theoretical Computer Science, vol.43, pp.169-188, 1986. ,
Ups delivers optimal phase diagram in high-dimensional variable selection, The Annals of Statistics, vol.40, issue.1, pp.73-103, 2012. ,
Optimality of graphlet screening in high dimensional variable selection, Journal of Machine Learning Research, vol.15, issue.1, pp.2723-2772, 2014. ,
Variable selection in high-dimension with random designs and orthogonal matching pursuit, Journal of Machine Learning Research, vol.14, issue.1, pp.1771-1800, 2013. ,
A constructive sharp approach to functional quantization of stochastic processes, Journal of Applied Mathematics, 2010. ,
Reducibility among combinatorial problems, Complexity of computer computations, pp.85-103, 1972. ,
Covariance assisted screening and estimation, Annals of statistics, vol.42, issue.6, p.2202, 2014. ,
The critical probability of bond percolation on the square lattice equals 1/2. Communications in mathematical physics, vol.74, pp.41-59, 1980. ,
Statistical guarantees for estimating the centers of a two-component gaussian mixture by em, 2016. ,
Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion, The Annals of Statistics, vol.39, issue.5, pp.2302-2329, 2011. ,
URL : https://hal.archives-ouvertes.fr/hal-00676868
Optimal series representation of fractional brownian sheets, Bernoulli, pp.669-696, 2002. ,
Clustering with spectral norm and the k-means algorithm, 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp.299-308, 2010. ,
Rodeo: sparse, greedy nonparametric regression, The Annals of Statistics, vol.36, issue.1, pp.28-63, 2008. ,
Robust machine learning by median-of-means: theory and practice, 2017. ,
Theory of point estimation, 2006. ,
Testing statistical hypotheses, 2006. ,
, Between hard and soft thresholding: optimal iterative thresholding algorithms, 2018.
Least squares quantization in pcm, IEEE transactions on information theory, vol.28, pp.129-137, 1982. ,
Sup-norm convergence rate and sign concentration property of lasso and dantzig estimators, Electronic Journal of statistics, vol.2, pp.90-102, 2008. ,
URL : https://hal.archives-ouvertes.fr/hal-00222251
Oracle inequalities and optimal inference under group sparsity, Annals of Statistics, vol.39, issue.5, pp.2164-2204, 2011. ,
URL : https://hal.archives-ouvertes.fr/hal-00501509
Statistical and computational guarantees of lloyd's algorithm and its variants, 2016. ,
Functional quantization of gaussian processes, Journal of Functional Analysis, vol.196, issue.2, pp.486-531, 2002. ,
URL : https://hal.archives-ouvertes.fr/hal-00102159
High-resolution product quantization for gaussian processes under sup-norm distortion, Bernoulli, vol.13, issue.3, pp.653-671, 2007. ,
URL : https://hal.archives-ouvertes.fr/hal-00171801
Expansions for gaussian processes and parseval frames, Electron. J. Probab, vol.14, issue.42, pp.1198-1221, 2009. ,
URL : https://hal.archives-ouvertes.fr/hal-00437672
High-dimensional graphs and variable selection with the lasso. The annals of statistics, pp.1436-1462, 2006. ,
Stability selection, Journal of the Royal Statistical Society: Series B (Statistical Methodology), vol.72, issue.4, pp.417-473, 2010. ,
Clustering subgaussian mixtures by semidefinite programming, 2016. ,
Settling the polynomial learnability of mixtures of gaussians, 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp.93-102, 2010. ,
Consistency thresholds for the planted bisection model, Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp.69-75, 2015. ,
Harmonic analysis meets stationarity: A general framework for series expansions of special gaussian processes, 2018. ,
, Sharp optimal recovery in the two component gaussian mixture model, 2018.
Interplay of minimax estimation and minimax support recovery under sparsity, 2019. ,
Optimal variable selection and adaptive noisy compressed sensing, 2018. ,
Problem Complexity and Method Efficiency in Optimization, 1983. ,
On false discovery rate thresholding for classification under sparsity, The Annals of Statistics, vol.40, issue.5, pp.2572-2600, 2012. ,
URL : https://hal.archives-ouvertes.fr/hal-00604427
Optimality and sub-optimality of pca i: Spiked random matrix models, The Annals of Statistics, vol.46, issue.5, pp.2416-2451, 2018. ,
Functional quantization for numerics with an application to option pricing, Monte Carlo Methods and Applications mcma, vol.11, issue.4, pp.407-446, 1995. ,
Nearly sharp sufficient conditions on exact sparsity pattern recovery, IEEE Transactions on Information Theory, vol.57, issue.7, pp.4672-4679, 2011. ,
Adaptive clustering through semidefinite programming, Advances in Neural Information Processing Systems, pp.1795-1803, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01524677
Thresholded basis pursuit: LP algorithm for orderwise optimal support recovery for sparse and approximately sparse signals from noisy random measurements, IEEE Transactions on Information Theory, vol.57, issue.3, pp.1567-1586, 2011. ,
Learning mixtures of arbitrary gaussians, Proceedings of the thirty-third annual ACM symposium on Theory of computing, pp.247-257, 2001. ,
A tight bound of hard thresholding, The Journal of Machine Learning Research, vol.18, issue.1, pp.7650-7691, 2017. ,
Empirical processes with applications to statistics, vol.59, 2009. ,
Rectangular confidence regions for the means of multivariate normal distributions, Journal of the American Statistical Association, vol.62, issue.318, pp.626-633, 1967. ,
Slope is adaptive to unknown sparsity and asymptotically minimax, The Annals of Statistics, vol.44, issue.3, pp.1038-1068, 2016. ,
Scaled sparse linear regression, Biometrika, vol.99, issue.4, pp.879-898, 2012. ,
An asymptotic analysis of distributed nonparametric methods, 2017. ,
Signal recovery from random measurements via orthogonal matching pursuit, IEEE Transactions on information theory, vol.53, issue.12, pp.4655-4666, 2007. ,
Introduction to Nonparametric Estimation, 2008. ,
Mathematics and the picturing of data, Proceedings of the International Congress of Mathematician, vol.2, pp.523-531, 1975. ,
A spectral algorithm for learning mixture models, Journal of Computer and System Sciences, vol.68, issue.4, pp.841-860, 2004. ,
Introduction to the non-asymptotic analysis of random matrices, pp.210-268, 2012. ,
High-dimensional probability: An introduction with applications in data science, vol.47, 2018. ,
Minimax risks for sparse regressions: Ultra-high dimensional phenomenons, Electronic Journal of Statistics, vol.6, pp.38-90, 2012. ,
URL : https://hal.archives-ouvertes.fr/hal-00508339
Adaptive estimation of high-dimensional signal-tonoise ratios, Bernoulli, vol.24, issue.4B, pp.3683-3710, 2018. ,
Inequalities for the r th absolute moment of a sum of random variables, 1 ? r ? 2, The Annals of Mathematical Statistics, vol.36, issue.1, pp.299-303, 1965. ,
Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting, IEEE Transactions on Information Theory, vol.55, issue.12, pp.5728-5741, 2009. ,
Sharp thresholds for high-dimensional and noisy sparsity recovery using`1-constrained quadratic programming (lasso), IEEE transactions on information theory, vol.55, pp.2183-2202, 2009. ,
Which bridge estimator is optimal for variable selection?, 2017. ,
Information-theoretic limits on sparse signal recovery: Dense versus sparse measurement matrices, IEEE Transactions on Information Theory, vol.56, issue.6, pp.2967-2979, 2010. ,
All of statistics: a concise course in statistical inference, 2013. ,
High dimensional variable selection, Annals of statistics, vol.37, issue.5A, p.2178, 2009. ,
Model selection in nonparametric regression, Annals of Statistics, vol.31, issue.1, pp.252-273, 2003. ,
Estimation of the covariance structure of heavy-tailed distributions, Advances in Neural Information Processing Systems, pp.2859-2868, 2017. ,
On the distribution of the roots of certain symmetric matrices, The Annals of Mathematics, vol.67, pp.325-328, 1958. ,
Model selection and sharp asymptotic minimaxity. Probability Theory and Related Fields, vol.156, pp.165-191, 2013. ,
The sup-norm perturbation of hosvd and low rank tensor denoising, 2017. ,
, Heteroskedastic pca: Algorithm, optimality, and applications, 2018.
Minimax rates of community detection in stochastic block models, The Annals of Statistics, vol.44, issue.5, pp.2252-2280, 2016. ,
Nearly unbiased variable selection under minimax concave penalty. The Annals of statistics, vol.38, pp.894-942, 2010. ,
The sparsity and bias of the lasso selection in high-dimensional linear regression, The Annals of Statistics, vol.36, issue.4, pp.1567-1594, 2008. ,
Some sharp performance bounds for least squares regression with l1 regularization, The Annals of Statistics, vol.37, issue.5A, pp.2109-2144, 2009. ,
Adaptive forward-backward greedy algorithm for learning sparse representations, IEEE transactions on information theory, vol.57, issue.7, pp.4689-4708, 2011. ,
Sparse recovery with orthogonal matching pursuit under rip, IEEE Transactions on Information Theory, vol.57, issue.9, pp.6215-6221, 2011. ,
On model selection consistency of lasso, The Journal of Machine Learning Research, vol.7, pp.2541-2563, 2006. ,
The adaptive lasso and its oracle properties, Journal of the American statistical association, vol.101, issue.476, pp.1418-1429, 2006. ,
, List of Figures 1.1 Illustration of percolation on a square lattice of size 500 ? 500. Bonds are red if open, white if blocked and percolation paths are in green
, The empirical spectral distribution of a matrix drawn from the 1500?1500 GOE
, 10 1.4 A two-dimensional projection of a two component Gaussian mixture with n = 100 and p = 1000
, Product quantization of a centered Ornstein-Uhlenbeck process, starting from Y 0 = 0 (left), and a fBm (right)
19 2.2 Rates of convergence of the minimax risks, List of Tables 2.1 Phase transitions in Gaussian setting ,