I am reading the paper "Collaborative PAC Learning" by Blum et al. So I will try to setup the problem here as to avoid reading the complete section (personalized setting).

Assume there are $k$ agents that are learning a labelling function $f^{*} \in \mathcal{H}$ of Hypothesis class $\mathcal{H}$ and observe a distinct data distribution $D_i,\; i \in [k]$.

Now, the idea for cooperative learning is quite intuitive. If you find a good candidate hypothesis that has observed $m_{\epsilon/4,\delta}$ samples over average distribution $D=(1/k)\Sigma_{i\in[k]}D_i$ there will be atleast $k/2$ agents that have error less than $\epsilon/2$ which can be seen if you apply markov with expectation being $\epsilon k / 4$.

Now, here is the part where I am stuck. We ask all the agents by passing a set of $O(\frac{1}{\epsilon}log(\frac{|N|}{\epsilon\delta}))$ samples if their error is lower than $3\epsilon/4$. Here $N$ is set of agents at each iteration which are not pruned.

The authors assert that if the risk $err_{D_i}(f)\leq\epsilon/2$ then empirical risk for the test sample cannot be greater than $3\epsilon/4$ and if a agent has empirical risk less than $3\epsilon/4$ then true risk is less than $\epsilon$.

Here is my attempt:

Let $R_T$ be the true risk and $R_E$ be the empirical risk then we know from VC theorem.

$$ |R_T-R_E| \leq \frac{1}{\delta}\frac{4+\sqrt{dlog(2em/d)}}{\sqrt{2m}} $$ Here $m$ is the number of samples and $d$ is the VCdim.

A further simplification would be $$ |R_T-R_E| \leq \frac{1}{\delta}\sqrt{\frac{dlog(2em/d)}{2m}} $$

assuming $\sqrt{d}>>4$ which is a fair assumption. Now, following the line of reasoning from "Understanding machine learning" shai-shalev book chapter on VC dimension, I get

$$m\geq O(\frac{1}{\epsilon^2\delta^2})$$ which is much bigger than the sample size of samples we initially used. Where am I going wrong?

  • 1
    $\begingroup$ To understand your question better: each agent learns its own unique $\hat f_i$ from the data $D_i$? Also, what exactly is this average distribution $D$? I find it quite unusual to average on the distribution, since it has the effect of lowering the inherent distribution's standard deviation (which means that $D$ is drawn from a different distribution than any of the $D_i$s). In practical terms, it means that if you learn over $D$ when $k$ is large enough, you will learn to label only one point approximately. Therefore I would like to know what exactly is $D$ used for in this process, thanks $\endgroup$
    – nir shahar
    Feb 12, 2022 at 11:59
  • $\begingroup$ each agent learns its own unique 𝑓̂ 𝑖 from the data 𝐷𝑖? Yes $\endgroup$
    – Naren
    Feb 12, 2022 at 17:09
  • $\begingroup$ what exactly is this average distribution 𝐷? This is a good question. Each distribution is essentially PDF over the input space $\mathcal{X}$, So when I say average, you are thinking in the right direction. If there is a common subset of $A\subset X$ that has non zero probability according to all $D_i$ then that subset will be boosted in probability in distribution $D$. Also, I forgot to add the assumption is $k\sim O(d)$ that is number of agents is upper-bounded by VC dimension so it can't be too large. $\endgroup$
    – Naren
    Feb 12, 2022 at 17:22
  • $\begingroup$ A more subtle but valid implicit data distribution assumption is that a lot of the same data that is being observed by each agent. For example, multiple self-driving cars are observing sensor information and the probability of observing a car on the road for all cars is higher than observing a plant for example. $\endgroup$
    – Naren
    Feb 12, 2022 at 17:37
  • 1
    $\begingroup$ Cool, glad to know you figured it out by yourself ;) $\endgroup$
    – nir shahar
    Feb 13, 2022 at 11:56

1 Answer 1


So, I realized this because these are $\epsilon/4$-representative samples or $$ |R_E-R_T| <= \epsilon/4 $$ by construction. So, if empirical error $3\epsilon/4$ given true error is at most $\epsilon/2$. We can say true error is at most $\epsilon$ if estimated error is $3\epsilon/4$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.