# Generalization error bound in case of collaborative learning

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?

• 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 Feb 12, 2022 at 11:59
• each agent learns its own unique 𝑓̂ 𝑖 from the data 𝐷𝑖? Yes Feb 12, 2022 at 17:09
• 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. Feb 12, 2022 at 17:22
• 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. Feb 12, 2022 at 17:37
• Cool, glad to know you figured it out by yourself ;) Feb 13, 2022 at 11:56

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$$.