Let $\epsilon>0$ and consider constructing a set $S_\epsilon\subseteq S^{d-1}$ of points on the sphere $\{x\in\mathbb R^d \mid ||x||_2=1\}$, such that $$ \mathbb E\left[\min_{y\in S_\epsilon}||x-y||_2^2\right]\le \epsilon, $$
where $x$ is a random point on the sphere and the expectation is with respect to the choice of $x$.
How big must $S_\epsilon$ be?
I'm looking for a lower bound, although an upper bound may be interesting as well.
The motivation for this problem comes from an attempt to prove a lower bound on the number of bits that are needed to send a real-valued vector $x\in\mathbb R^d$ such that the receiver can estimate $x$ to within an ($\ell_2$ squared) error of $\epsilon||x||_2^2$. The formulation requires a few extra steps (including Yao's Minimax principle), but this is the component I'm missing.
If $\epsilon$ is small so the number of points is large you can ignore the curvature and consider packing $d$ dimensional balls into $d$ dimensional space. For dimensions up to $8$ the densest lattice packings are known. For higher dimensions the densest packing is unknown and is suspected to often be nonlattice.
You can compute the $d$ volume of the $d$ sphere, divide by the $d$ volume of a $d$ ball of diameter $\epsilon$ and multiply by the packing density to get an approximation to the number of points you need.