Research map / Learning theory and algorithms / Sample complexity

Defining Neural Network Architecture through Polytope Structures of Datasets

ICML 2024 · Learning theory and algorithms › Sample complexity · approach: Robust and surrogate-loss learning bounds · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Derives width upper/lower bounds for ReLU networks classifying a dataset from its polytope-basis cover, and proposes algorithms that extract such covers from trained networks, finding MNIST, Fashion-MNIST and CIFAR10 classes coverable by at most two polytopes.

Problem

Determining the minimal feasible neural network architecture (depth and widths) needed to classify a given dataset, and understanding how dataset geometry constrains it; the converse of asking what geometry trained networks reveal about data.

Approach

x

Key results

• Each class of MNIST, Fashion-MNIST and CIFAR10 can be covered by at most two convex polytopes, most with fewer than 30 faces (e.g., MNIST class 0 by one 4-face polytope).
• Swiss roll dataset classified by a three-layer ReLU network with 24 neurons in the first hidden layer per the paper's example.
• Noisy-label experiments show required face count rises with label noise (MNIST class 1: 3 faces at r=0 to 64.0 at r=0.5).

Measured effects reported in the paper

Surprising findings

• For Fashion-MNIST and MNIST noisy classes, the 50% corrupted set requires more faces than the fully mixed (r=0.9) set.

Limitations

• Optimality of the polytope-basis cover from the compressing algorithm is not established.
• Only fully-connected networks are considered; CNNs are not studied.

Experimental setup

Datasets: MNIST Fashion-MNIST CIFAR10 swiss roll (synthetic)

Benchmarks: MNIST Fashion-MNIST CIFAR10

Metrics: number of polytope faces classification accuracy (99.99% threshold)

Baselines: large-margin convex polytope machine

Builds on: input convex neural networks lottery ticket hypothesis implicit bias of gradient descent

Closest papers by meaning

• Deep Networks and the Multiple Manifold Problem (ICLR 2021 · similarity 0.86)
• Depth-Bounds for Neural Networks via the Braid Arrangement (NeurIPS 2025 · similarity 0.84)
• Geometric Inductive Biases of Deep Networks: The Role of Data and Architecture (ICLR 2025 · similarity 0.84)
• On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.84)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.84)
• Sharp feature-learning transitions and Bayes-optimal neural scaling laws in extensive-width networks (NeurIPS 2026 · similarity 0.84)