Consider the standard Gaussian linear regression model @math , where @math is a response vector and @math is a design matrix. Numerous work have been devoted to building efficient estimators of @math when @math is much larger than @math . In such a situation, a classical approach amounts to assume that @math is approximately sparse. This paper studies the minimax risks of estimation and testing over classes of @math -sparse vectors @math . These bounds shed light on the limitations due to high-dimensionality. The results encompass the problem of prediction (estimation of @math ), the inverse problem (estimation of @math ) and linear testing (testing @math ). Interestingly, an elbow effect occurs when the number of variables @math becomes large compared to @math . Indeed, the minimax risks and hypothesis separation distances blow up in this ultra-high dimensional setting. We also prove that even dimension reduction techniques cannot provide satisfying results in an ultra-high dimensional setting. Moreover, we compute the minimax risks when the variance of the noise is unknown. The knowledge of this variance is shown to play a significant role in the optimal rates of estimation and testing. All these minimax bounds provide a characterization of statistical problems that are so difficult so that no procedure can provide satisfying results.
Recently, some high-dimensional problems have been studied from a minimax point of view. Wainwright @cite_48 @cite_30 provides minimax lower bounds for the problem of support estimation ( @math ). @cite_17 and Rigollet and Tsybakov @cite_34 have provided minimax upper bounds and lower bounds for @math and @math over @math balls for general fixed designs @math when the variance @math is known (see also Ye and Zhang @cite_1 and Abramovich and Grinshtein @cite_31 ). Arias- @cite_41 and @cite_42 have computed the asymptotic minimax detection boundaries for the testing problem @math for some specific designs. However, their study only encompasses reasonable dimensional problems ( @math grows polynomially with @math ). Some minimax lower bounds have also been stated for testing ( @math ) and prediction ( @math ) problems with Gaussian design @cite_15 @cite_18 . All the aforementioned results do not cover the ultra-high dimensional case and do not tackle the problem of adaptation to both @math and @math .
@cite_30 @cite_18 @cite_15 @cite_41 @cite_48 @cite_42 @cite_1 @cite_31 @cite_34 @cite_17
191129667 2014100575 2047838040 2508647357 1989151402 1993855803 2567351292 1526184959 2536849891 1538452572
Much recent effort has sought asymptotically minimax methods for recovering infinite dimensional objects-curves, densities, spectral densities, images-from noisy data. A now rich and complex body of work develops nearly or exactly minimax estimators for an array of interesting problems. Unfortunately, the results have rarely moved into practice, for a variety of reasons-among them being similarity to known methods, computational intractability and lack of spatial adaptivity. We discuss a method for curve estimation based on n noisy data: translate the empirical wavelet coefficients towards the origin by an amount √(2 log n) √n. The proposal differs from those in current use, is computationally practical and is spatially adaptive; it thus avoids several of the previous objections. Further, the method is nearly minimax both for a wide variety of loss functions-pointwise error, global error measured in L p -norms, pointwise and global error in estimation of derivatives-and for a wide range of smoothness classes, including standard Holder and Sobolev classes, and bounded variation. This is a much broader near optimality than anything previously proposed: we draw loose parallels with near optimality in robustness and also with the broad near eigenfunction properties of wavelets themselves. Finally, the theory underlying the method is interesting, as it exploits a correspondence between statistical questions and questions of optimal recovery and information-based complexity In this paper, we study the detection boundary for minimax hypothesis testing in the context of high-dimensional, sparse binary regression models. Motivated by genetic sequencing association studies for rare variant effects, we investigate the complexity of the hypothesis testing problem when the design matrix is sparse. We observe a new phenomenon in the behavior of detection boundary which does not occur in the case of Gaussian linear regression. We derive the detection boundary as a function of two components: a design matrix sparsity index and signal strength, each of which is a function of the sparsity of the alternative. For any alternative, if the design matrix sparsity index is too high, any test is asymptotically powerless irrespective of the magnitude of signal strength. For binary design matrices with the sparsity index that is not too high, our results are parallel to those in the Gaussian case. In this context, we derive detection boundaries for both dense and sparse regimes. For the dense regime, we show that the generalized likelihood ratio is rate optimal; for the sparse regime, we propose an extended Higher Criticism Test and show it is rate optimal and sharp. We illustrate the finite sample properties of the theoretical results using simulation studies. In this article we study function estimation via wavelet shrinkage for data with long-range dependence. We propose a fractional Gaussian noise model to approximate nonparametric regression with long-range dependence and establish asymptotics for minimax risks. Because of long-range dependence, the minimax risk and the minimax linear risk converge to 0 at rates that differ from those for data with independence or short-range dependence. Wavelet estimates with best selection of resolution leveldependent threshold achieve minimax rates over a wide range of spaces. Cross-validation for dependent data is proposed to select the optimal threshold. The wavelet estimates significantly outperform linear estimates. The key to proving the asymptotic results is a wavelet]vaguelette decomposition which decorrelates fractional Gaussian noise. Such wavelet]vaguelette decomposition is also very useful in fractal signal processing. Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say O(n1+Δ) bits. There is an inherent tradeoff between the sparsity parameter Δ and the stretch function f of the compression scheme, but the qualitative nature of this tradeoff has remained a persistent open problem. It has been known for some time that when Δ ≥ 1 3 there are schemes with constant additive stretch (distance d is stretched to at most f(d) = d + O(1)), and recent results of Abboud and Bodwin show that when Δ In this paper we show that the lower bound of Abboud and Bodwin is just the first step in a hierarchy of lower bounds that characterize the asymptotic behavior of the optimal stretch function f for sparsity parameter Δ ∈ (0,1 3). Specifically, for any integer k ≥ 2, any compression scheme with size [EQUATION] has a sublinear additive stretch function f: f(d) = d + Ω(d1−1 k). This lower bound matches Thorup and Zwick's (2006) construction of sublinear additive emulators. It also shows that Elkin and Peleg's (1 + ϵ, β)-spanners have an essentially optimal tradeoff between Δ, ϵ, and β, and that the sublinear additive spanners of Pettie (2009) and Chechik (2013) are not too far from optimal. To complement these lower bounds we present a new construction of (1 + ϵ, O(k ϵ)k−1)-spanners with size [EQUATION], where hk Our lower bound technique exhibits several interesting degrees of freedom in the framework of Abboud and Bodwin. By carefully exploiting these freedoms, we are able to obtain lower bounds for several related combinatorial objects. We get lower bounds on the size of (β, ϵ)-hopsets, matching Elkin and Neiman's construction (2016), and lower bounds on shortcutting sets for digraphs that preserve the transitive closure. Our lower bound simplifies Hesse's (2003) refutation of Thorup's conjecture (1992), which stated that adding a linear number of shortcuts suffices to reduce the diameter to polylogarithmic. Finally, we show matching upper and lower bounds for graph compression schemes that work for graph metrics with girth at least 2γ + 1. One consequence is that 's (2010) additive O(γ)-spanners with size [EQUATION] cannot be improved in the exponent. We propose a general methodology for the construction and analysis of essentially minimax estimators for a wide class of functionals of finite dimensional parameters, and elaborate on the case of discrete distributions, where the support size @math is unknown and may be comparable with or even much larger than the number of observations @math . We treat the respective regions where the functional is nonsmooth and smooth separately. In the nonsmooth regime, we apply an unbiased estimator for the best polynomial approximation of the functional whereas, in the smooth regime, we apply a bias-corrected version of the maximum likelihood estimator (MLE). We illustrate the merit of this approach by thoroughly analyzing the performance of the resulting schemes for estimating two important information measures: 1) the entropy @math and 2) @math . We obtain the minimax @math rates for estimating these functionals. In particular, we demonstrate that our estimator achieves the optimal sample complexity @math for entropy estimation. We also demonstrate that the sample complexity for estimating @math n S^ 1 S @math 1 , we show the minimax @math rate for estimating @math is @math for infinite support size, while the maximum @math rate for the MLE is @math . For all the above cases, the behavior of the minimax rate-optimal estimators with @math samples is essentially that of the MLE (plug-in rule) with @math samples, which we term “effective sample size enlargement.” We highlight the practical advantages of our schemes for the estimation of entropy and mutual information. We compare our performance with various existing approaches, and demonstrate that our approach reduces running time and boosts the accuracy. Moreover, we show that the minimax rate-optimal mutual information estimator yielded by our framework leads to significant performance boosts over the Chow–Liu algorithm in learning graphical models. The wide use of information measure estimation suggests that the insights and estimators obtained in this paper could be broadly applicable. In this paper, we attempt to approximate and index a d- dimensional (d ≥ 1) spatio-temporal trajectory with a low order continuous polynomial. There are many possible ways to choose the polynomial, including (continuous)Fourier transforms, splines, non-linear regressino, etc. Some of these possiblities have indeed been studied beofre. We hypothesize that one of the best possibilities is the polynomial that minimizes the maximum deviation from the true value, which is called the minimax polynomial. Minimax approximation is particularly meaningful for indexing because in a branch-and-bound search (i.e., for finding nearest neighbours), the smaller the maximum deviation, the more pruning opportunities there exist. However, in general, among all the polynomials of the same degree, the optimal minimax polynomial is very hard to compute. However, it has been shown thta the Chebyshev approximation is almost identical to the optimal minimax polynomial, and is easy to compute [16]. Thus, in this paper, we explore how to use the Chebyshev polynomials as a basis for approximating and indexing d-dimenstional trajectories.The key analytic result of this paper is the Lower Bounding Lemma. that is, we show that the Euclidean distance between two d-dimensional trajectories is lower bounded by the weighted Euclidean distance between the two vectors of Chebyshev coefficients. this lemma is not trivial to show, and it ensures that indexing with Chebyshev cofficients aedmits no false negatives. To complement that analystic result, we conducted comprehensive experimental evaluation with real and generated 1-dimensional to 4-dimensional data sets. We compared the proposed schem with the Adaptive Piecewise Constant Approximation (APCA) scheme. Our preliminary results indicate that in all situations we tested, Chebyshev indexing dominates APCA in pruning power, I O and CPU costs. We describe a general technique that yields the first Statistical Query lower bounds for a range of fundamental high-dimensional learning problems involving Gaussian distributions. Our main results are for the problems of (1) learning Gaussian mixture models (GMMs), and (2) robust (agnostic) learning of a single unknown Gaussian distribution. For each of these problems, we show a super-polynomial gap between the (information-theoretic) sample complexity and the computational complexity of any Statistical Query algorithm for the problem. Our SQ lower bound for Problem (1) is qualitatively matched by known learning algorithms for GMMs. Our lower bound for Problem (2) implies that the accuracy of the robust learning algorithm in DiakonikolasKKLMS16 is essentially best possible among all polynomial-time SQ algorithms. Our SQ lower bounds are attained via a unified moment-matching technique that is useful in other contexts and may be of broader interest. Our technique yields nearly-tight lower bounds for a number of related unsupervised estimation problems. Specifically, for the problems of (3) robust covariance estimation in spectral norm, and (4) robust sparse mean estimation, we establish a quadratic statistical--computational tradeoff for SQ algorithms, matching known upper bounds. Finally, our technique can be used to obtain tight sample complexity lower bounds for high-dimensional testing problems. Specifically, for the classical problem of robustly testing an unknown mean (known covariance) Gaussian, our technique implies an information-theoretic sample lower bound that scales linearly in the dimension. Our sample lower bound matches the sample complexity of the corresponding robust learning problem and separates the sample complexity of robust testing from standard (non-robust) testing. We are motivated by problems that arise in a number of applications such as Online Marketing and Explosives detection, where the observations are usually modeled using Poisson statistics. We model each observation as a Poisson random variable whose mean is a sparse linear superposition of known patterns. Unlike many conventional problems observations here are not identically distributed since they are associated with different sensing modalities. We analyze the performance of a maximum likelihood (ML) decoder, which for our Poisson setting involves a non-linear optimization but yet is computationally tractable. We derive fundamental sample complexity bounds for sparse recovery when the measurements are contaminated with Poisson noise. In contrast to the least-squares linear regression setting with Gaussian noise, we observe that in addition to sparsity, the scale of the parameters also fundamentally impacts @math error in the Poisson setting. We show that our upper bounds are tight under suitable regularity conditions. Specifically, we derive a minimax matching lower bound on the mean-squared error and show that our constrained ML decoder is minimax optimal for this regime. We study the recovery of sparse vectors from subsampled random convolutions via @math -minimization. We consider the setup in which both the subsampling locations as well as the generating vector are chosen at random. For a subgaussian generator with independent entries, we improve previously known estimates: if the sparsity @math is small enough, i.e., @math , we show that @math measurements are sufficient to recover @math -sparse vectors in dimension @math with high probability, matching the well-known condition for recovery from standard Gaussian measurements. If @math is larger, then essentially @math measurements are sufficient, again improving over previous estimates. Our results are shown via the so-called robust null space property which is weaker than the standard restricted isometry property. Our method of proof involves a novel combination of small ball estimates with chaining techniques which should be of independent interest. This note explores the connections and differences between three commonly used methods for constructing minimax lower bounds in nonparametric estimation problems: Le Cam’s, Assouad’s and Fano’s. Two connections are established between Le Cam’s and Assouad’s and between Assouad’s and Fano’s. The three methods are then compared in the context of two estimation problems for a smooth class of densities on [0,1]. The two estimation problems are for the integrated squared first derivatives and for the density function itself.