Abstract
We analyze the sample complexity of learning from multiple experiments wherethe experimenter has a total budget for obtaining samples. In this problem, thelearner should choose a hypothesis that performs well with respect to multipleexperiments, and their related data distributions. Each collected sample isassociated with a cost which depends on the particular experiments. In oursetup, a learner performs $m$ experiments, while incurring a total cost $C$. Wefirst show that learning from multiple experiments allows to improveidentifiability. Additionally, by using a Rademacher complexity approach, weshow that the gap between the training and generalization error is$O(C^{-1/2})$. We also provide some examples for linear prediction, two-layerneural networks and kernel methods.