
We then bound \(\mathrm {E}_{x,\sigma }[\cdot ]\) . Using Klei-Rio bound [1]}, with a probability \(1 - 2\delta \) , we have
\({\mathrm {E}_{x,\sigma }\left[\max \limits _{\theta \in \Omega (\widehat{r},s)} \left|\frac{1}{m}\sum _{i=1}^m \sigma _i (f(x_i^a;\theta ) - y(x_i^a))\nabla f(x_i^a;\theta )\right|\right]} \\& \le & 2\mathrm {E}_{\sigma }\left[\max \limits _{\theta \in \Omega (\widehat{r},s)} \left|\frac{1}{m}\sum _{i=1}^m \sigma _i (f(x_i^a;\theta ) - y(x_i^a))\nabla f(x_i^a;\theta ) \right|\right] + 2\widehat{r}\sqrt{\frac{\log (1/\delta )}{m}} + \frac{9F}{m}\log \frac{1}{\delta }\) 
