Function-Counting Theory for Low-Dimensional Data Structures
2026-07-01 • Information Theory
Information TheoryMachine Learning
AI summaryⓘ
The authors develop a mathematical way to better understand how binary classifiers work when the data lies in a low-dimensional space, even if the data itself looks high-dimensional. They improve on an old theory by Cover that didn't consider this low-dimensional structure, showing how such structure affects the number of ways data can be separated (dichotomies) and how well models can generalize. Their work connects the geometric arrangement of data with classification performance in a more realistic setting.
binary classificationlow-dimensional dataCover's theoremfunction-counting theorydichotomy countsgeneral position assumptionseparation capacitygeneralizationmachine learning theorydata structure
Authors
Konstantin Häberle, Helmut Bölcskei
Abstract
The success of deep learning models in classification and regression is widely attributed to the low-dimensional structure that real-world data tend to exhibit, despite their high-dimensional representation. This work attempts to provide a mathematical framework for binary classification on low-dimensional data, building on Cover's (1965) function-counting theory. With our framework, we aim to address the question of how the low-dimensional structure of the data affects the classification capabilities of learning models. Cover's theory relies on a general position assumption that blinds it to the underlying data structure. We refine this assumption to account for the low-dimensionality of the data and derive dichotomy counts that reflect the data structure. We further extend Cover's separation capacity and problem of generalization to the low-dimensional setting, enabling the impact of the underlying data structure on both to be analyzed.