Statistical learning theory aims to understand when and why learning from random observations is possible. Classical theory explains learnability using uniform convergence arguments, which apply whenever the problem has a finite, suitably defined dimension. While this picture is satisfactory in textbook setups, it has considerable gaps both in theory and in practice. We resolve two such theoretical gaps in our work, showing that arguments beyond the uniform convergence paradigm are needed to understand the learnability phenomenon. Our first contribution is to prove a tight upper bound for the sample complexity of empirical risk minimizers when the learning problem is convex, a well-studied model in the literature. Our second contribution provides a correct characterization of multiclass learnability: (i) we prove that a dimensionality notion by Daniely-Shalev-Swartz is indeed correct for this setup, and (ii) use a recently developed topological construction by Januszkiewicz and Świątkowski to supply a counterexample, proving the insufficiency of several widely conjectured dimensionality notions. Our third contribution is to analyze graphs inspired by these topological constructions, and show that they exhibit nontrivial guarantees as small-set expanders, a structure of ongoing interest in computational complexity theory. Advisor: Prof. Amir Yehudayoff