Learning in Graphs, Convexity Spaces, and Beyond

Abstract

We study computational learning problems in abstract convexity spaces and fine-grained aspects of learnability. While the problem of learning halfspaces in Euclidean space is one of the most fundamental and important problems in machine learning, the corresponding problem of learning halfspaces in convexity spaces or graphs has received much less attention. In the first part of this thesis, we build a bridge between computational learning theory and convexity theory with a focus on graph convexity theory. In the second part, we take a broader perspective and study two fine-grained variants of supervised learning for general hypothesis spaces.In the first part, we focus on the machine learning task of node classification. With the advent of social networks and graph-based machine learning in general, this learning task has received considerable attention. Most results in this line of work reflect the homophily principle, that is, the tendency of adjacent vertices to belong to the same class. We take a different perspective. Analogously to linear separability and convexity in Euclidean space, we assume that the clusters are graph halfspaces or convex in the graph; discrete variants of convexity rooted in abstract convexity theory. In this way we hope to exploit and strengthen the well-established machinery behind convexity in machine learning and extend it to domains beyond vector spaces. Our contributions are twofold: First, we characterise the learnability of halfspaces and convex sets in graphs and convexity spaces in terms of invariants of the convexity space, as well as properties of the graph. Second, we obtain efficient algorithms for learning halfspaces and convex sets on graphs in common learning settings, such as supervised, online, and active learning.In the second part, we study two variants of classical probably approximately correct (PAC) learning for general hypothesis spaces. Both variants go beyond the uniform nature of the classical formulation. In the first variant, we allow the constants in the learning rate to depend on the marginal distribution generating the data and fully characterise all possible learning rates in this regime. In the second variant, instead of learning the true label in a multiclass setting, we only require to learn to eliminate one single wrong label from a given list of labels. Here we obtain near-tight sample complexity bounds and a combinatorial characterisation of learnability similar to VC dimension.