In this section we provide proofs for the Efficient-PAC theorems presented in Section . We also note that in this work we use the median-of-means estimate for the sample-mean (Definition REF ), instead of using the more standard empirical-mean estimate. It was recently demonstrated that the former has improved convergence results over the latter in the absence of information about the underlying distribution [1]}, [2]}, [3]}.
