  Many algorithms in machine learning and computational geometry require, as
input, the intrinsic dimension of the manifold that supports the probability
distribution of the data. This parameter is rarely known and therefore has to
be estimated. We characterize the statistical difficulty of this problem by
deriving upper and lower bounds on the minimax rate for estimating the
dimension. First, we consider the problem of testing the hypothesis that the
support of the data-generating probability distribution is a well-behaved
manifold of intrinsic dimension $d_1$ versus the alternative that it is of
dimension $d_2$, with $d_{1}<d_{2}$. With an i.i.d. sample of size $n$, we
provide an upper bound on the probability of choosing the wrong dimension of
$O\left( n^{-\left(d_{2}/d_{1}-1-\epsilon\right)n} \right)$, where $\epsilon$
is an arbitrarily small positive number. The proof is based on bounding the
length of the traveling salesman path through the data points. We also
demonstrate a lower bound of $\Omega \left( n^{-(2d_{2}-2d_{1}+\epsilon)n}
\right)$, by applying Le Cam's lemma with a specific set of $d_{1}$-dimensional
probability distributions. We then extend these results to get minimax rates
for estimating the dimension of well-behaved manifolds. We obtain an upper
bound of order $O \left( n^{-(\frac{1}{m-1}-\epsilon)n} \right)$ and a lower
bound of order $\Omega \left( n^{-(2+\epsilon)n} \right)$, where $m$ is the
embedding dimension.
