Estimate an inner product from ℓ2-sampling access

If $y=0$, the prescribed output $0$ equals $⟨x,y⟩$ and has zero error. Suppose henceforth $y\mathrm{\ne }0$. For one sample $I\sim D_x$, query $x_I$ and $y_I$ and define $Z=\mathrm{\parallel }x{\mathrm{\parallel }}_2^2{y}_I\mathrm{/}{x}_I$ when $x_I\mathrm{\ne }0$ and $Z=0$ when $x_I=0$. Since a zero coordinate has sampling probability zero, [F1] gives $\mathbb{E}Z={\sum }_{i:x_i\mathrm{\ne }0}{x}_i{y}_i=⟨x,y⟩$.

Directly from the sampling law [F1], $\mathbb{E}[Z^2]=\mathrm{\parallel }x{\mathrm{\parallel }}_2^2{\sum }_{i:x_i\mathrm{\ne }0}{y}_i^2\le \mathrm{\parallel }x{\mathrm{\parallel }}_2^2\mathrm{\parallel }y{\mathrm{\parallel }}_2^2$. Hence $\mathrm{Var}(Z)\le \mathbb{E}[Z^2]\le \mathrm{\parallel }x{\mathrm{\parallel }}_2^2\mathrm{\parallel }y{\mathrm{\parallel }}_2^2$.

Partition $mr$ independent samples into $r$ disjoint blocks of size $m$. Let $M_b$ be the mean of $Z$ in block $b$ and define $\widehat{\mu }$ to be the $\lceil r\mathrm{/}2\rceil$-th order statistic of $M_1,\dots ,M_r$ (the lower median). Independence gives each block mean variance at most $\mathrm{\parallel }x{\mathrm{\parallel }}_2^2\mathrm{\parallel }y{\mathrm{\parallel }}_2^2\mathrm{/}m$. Apply [F2] with the positive threshold $t=ϵ\mathrm{\parallel }x{\mathrm{\parallel }}_2\mathrm{\parallel }y{\mathrm{\parallel }}_2$; each block mean is outside the target interval with probability at most $1\mathrm{/}(m{ϵ}^2)\le 1\mathrm{/}16$.

If the median $\widehat{\mu }$ lies outside the target interval, at least $\lceil r\mathrm{/}2\rceil$ block means lie outside it. For each fixed subset of that size the probability all its blocks fail is at most $(1\mathrm{/}16{)}^{\lceil r\mathrm{/}2\rceil }$ by [F3]; there are at most $2^r$ such subsets. By [F4], the failure probability is at most $2^r(1\mathrm{/}16{)}^{\lceil r\mathrm{/}2\rceil }\le 2^{-r}\le \delta$.