{"ID":5551627,"CreatedAt":"2026-07-02T01:54:51.863792489Z","UpdatedAt":"2026-07-04T14:41:19.486384794Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.01010","arxiv_id":"2607.01010","title":"Function-Counting Theory for Low-Dimensional Data Structures","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.","short_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, buildi...","url_abs":"https://arxiv.org/abs/2607.01010","url_pdf":"https://arxiv.org/pdf/2607.01010v1","authors":"[\"Konstantin Häberle\",\"Helmut Bölcskei\"]","published":"2026-07-01T14:47:36Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.IT\",\"cs.LG\",\"math.CA\",\"math.CO\"]","methods":"[]","has_code":false}