  Reduced bases have been introduced for the approximation of parametrized PDEs
in applications where many online queries are required. Their numerical
efficiency for such problems has been theoretically confirmed in
\cite{BCDDPW,DPW}, where it is shown that the reduced basis space $V_n$ of
dimension $n$, constructed by a certain greedy strategy, has approximation
error similar to that of the optimal space associated to the Kolmogorov
$n$-width of the solution manifold. The greedy construction of the reduced
basis space is performed in an offline stage which requires at each step a
maximization of the current error over the parameter space. For the purpose of
numerical computation, this maximization is performed over a finite {\em
training set} obtained through a discretization. of the parameter domain. To
guarantee a final approximation error $\varepsilon$ for the space generated by
the greedy algorithm requires in principle that the snapshots associated to
this training set constitute an approximation net for the solution manifold
with accuracy or order $\varepsilon$. Hence, the size of the training set is
the $\varepsilon$ covering number for $\mathcal{M}$ and this covering number
typically behaves like $\exp(C\varepsilon^{-1/s})$ for some $C>0$ when the
solution manifold has $n$-width decay $O(n^{-s})$. Thus, the shear size of the
training set prohibits implementation of the algorithm when $\varepsilon$ is
small. The main result of this paper shows that, if one is willing to accept
results which hold with high probability, rather than with certainty, then for
a large class of relevant problems one may replace the fine discretization by a
random training set of size polynomial in $\varepsilon^{-1}$. Our proof of this
fact is established by using inverse inequalities for polynomials in high
dimensions.
