We investigate the problem of identity testing for multidimensional histogram distributions. A distribution @math , where @math , is called a @math -histogram if there exists a partition of the domain into @math axis-aligned rectangles such that @math is constant within each such rectangle. Histograms are one of the most fundamental non-parametric families of distributions and have been extensively studied in computer science and statistics. We give the first identity tester for this problem with sub-learning sample complexity in any fixed dimension and a nearly-matching sample complexity lower bound. More specifically, let @math be an unknown @math -dimensional @math -histogram and @math be an explicitly given @math -histogram. We want to correctly distinguish, with probability at least @math , between the case that @math versus @math . We design a computationally efficient algorithm for this hypothesis testing problem with sample complexity @math . Our algorithm is robust to model misspecification, i.e., succeeds even if @math is only promised to be close to a @math -histogram. Moreover, for @math , we show a nearly-matching sample complexity lower bound of @math when @math . Prior to our work, the sample complexity of the @math case was well-understood, but no algorithm with sub-learning sample complexity was known, even for @math . Our new upper and lower bounds have interesting conceptual implications regarding the relation between learning and testing in this setting.
Abstract 2.1. Limitations of the parametric methods. In the previous sections we have studied the efficiency of various methods of estimating the force of mortality. The most efficient of these is, at least for large samples, the one given by the maximum likelihood method, and the rest of them have to be compared to this best estimate. However in this discussion the notion of efficiency is based on the assumption that the mortality intensity can be expressed by Makeham’s formula. How realistic is this in practice? 1. Introduction 2. Basic estimation problems with monotonicity constraints 3. Asymptotic theory for the basic monotone problems 4. Other univariate problems involving monotonicity constraints 5. Higher dimensional problems 6. Lower bounds on estimation rates 7. Algorithms and computation 8. Shape and smoothness 9. Testing and confidence intervals 10. Asymptotic theory of smooth functionals 11. Pointwise asymptotic distribution theory for univariate problems 12. Pointwise asymptotic distribution theory for multivariate problems 13. Asymptotic distribution of global deviations. 