We show that the perturbation set and perturbation function models are equivalent. U ( x): = { g ( x): g 2G }, which completes the proof of this direction. B.1 Proper -Probabilistically Robust PAC Learning for finite G We show that if G is finite then VC classes are -probabilistically robustly learnable. Since A ( S) 2H, by construction of H, there are at least m points in C where A is not probabilistically robustly correct. Using a variant of Markov's inequality, gives We now use the same reasoning in Montasser et al. [2019], to show that no proper learning rule works.

We show that the perturbation set and perturbation function models are equivalent. U ( x): = { g ( x): g 2G }, which completes the proof of this direction. B.1 Proper -Probabilistically Robust PAC Learning for finite G We show that if G is finite then VC classes are -probabilistically robustly learnable. Since A ( S) 2H, by construction of H, there are at least m points in C where A is not probabilistically robustly correct. Using a variant of Markov's inequality, gives We now use the same reasoning in Montasser et al. [2019], to show that no proper learning rule works.

Despite the impressive advancements in modern machine learning, achieving robustness in Domain Generalization (DG) tasks remains a significant challenge. In DG, models are expected to perform well on samples from unseen test distributions (also called domains), by learning from multiple related training distributions. Most existing approaches to this problem rely on single-valued predictions, which inherently limit their robustness. We argue that set-valued predictors could be leveraged to enhance robustness across unseen domains, while also taking into account that these sets should be as small as possible. We introduce a theoretical framework defining successful set prediction in the DG setting, focusing on meeting a predefined performance criterion across as many domains as possible, and provide theoretical insights into the conditions under which such domain generalization is achievable. We further propose a practical optimization method compatible with modern learning architectures, that balances robust performance on unseen domains with small prediction set sizes. We evaluate our approach on several real-world datasets from the WILDS benchmark, demonstrating its potential as a promising direction for robust domain generalization.

The Fundamental Theorem of Statistical Learning states that a hypothesis space is PAC learnable if and only if its VC dimension is finite. For the agnostic model of PAC learning, the literature so far presents proofs of this theorem that often tacitly impose several measurability assumptions on the involved sets and functions. We scrutinize these proofs from a measure-theoretic perspective in order to extract the assumptions needed for a rigorous argument. This leads to a sound statement as well as a detailed and self-contained proof of the Fundamental Theorem of Statistical Learning in the agnostic setting, showcasing the minimal measurability requirements needed. We then discuss applications in Model Theory, considering NIP and o-minimal structures. Our main theorem presents sufficient conditions for the PAC learnability of hypothesis spaces defined over o-minimal expansions of the reals.

The fat-shattering dimension characterizes the uniform convergence property of real-valued functions. The state-of-the-art upper bounds feature a multiplicative squared logarithmic factor on the sample complexity, leaving an open gap with the existing lower bound. We provide an improved uniform convergence bound that closes this gap.

Recently, Montasser et al. [2019] showed that finite VC dimension is not sufficient for proper adversarially robust PAC learning. In light of this hardness, there is a growing effort to study what type of relaxations to the adversarially robust PAC learning setup can enable proper learnability. In this work, we initiate the study of proper learning under relaxations of the worst-case robust loss. We give a family of robust loss relaxations under which VC classes are properly PAC learnable with sample complexity close to what one would require in the standard PAC learning setup. On the other hand, we show that for an existing and natural relaxation of the worst-case robust loss, finite VC dimension is not sufficient for proper learning. Lastly, we give new generalization guarantees for the adversarially robust empirical risk minimizer.

The parameters of a machine learning model are typically learned by minimizing a loss function on a set of training data. However, this can come with the risk of overtraining; in order for the model to generalize well, it is of great importance that we are able to find the optimal parameter for the model on the entire population -- not only on the given training sample. In this paper, we construct valid confidence sets for this optimal parameter of a machine learning model, which can be generated using only the training data without any knowledge of the population. We then show that studying the distribution of this confidence set allows us to assign a notion of confidence to arbitrary regions of the parameter space, and we demonstrate that this distribution can be well-approximated using bootstrapping techniques.

An earlier introduced characterization of nonuniform learnability that allows the sample size to depend on the hypothesis to which the learner is compared has been redefined using the measure-theoretic approach. Where nonuniform learnability is a strict relaxation of the Probably Approximately Correct (PAC) framework. Introduction of a new algorithm, Generalize Measure Learnability framework (GML), to implement this approach with the study of its sample and computational complexity bounds. Like the Minimum Description Length (MDL) principle, this approach can be regarded as an explication of Occam's razor. Furthermore, many situations were presented (Hypothesis Classes that are countable where we can apply the GML framework) which we can learn to use the GML scheme and can achieve statistical consistency.