Research map / Learning theory and algorithms / Kernels and regression theory
Topological Generalization Bounds for Discrete-Time Stochastic Optimization Algorithms
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 discrete-time topological generalization bounds using alpha-weighted lifetime sums (PH^0/MST) and a new positive magnitude measure, and shows they correlate with generalization gap for ViTs and GNNs.
Problem
Existing fractal/PH-dimension generalization bounds assume continuous or infinite-time training dynamics and geometric assumptions, so they do not apply to finite-time discrete stochastic optimizers like SGD and ADAM used in practice.
Approach
Replace the intrinsic fractal dimension with computable topological quantities (alpha-weighted lifetime sums and a positive-part variant of magnitude, PMag) that directly upper-bound the worst-case generalization error over a finite discrete training trajectory, using a total mutual information term and a Rademacher-magnitude link.
Key results
- Topological complexities E_1 and PMag(sqrt(n)) achieve average granulated Kendall coefficients close to 1 across ViT, CaiT, Swin on CIFAR10/CIFAR100.
- The proposed complexities consistently outperform PH-dim across vision transformers and GNNs (GatedGCN, GraphSage) on Super-pixel MNIST.
- Magnitude Mag(sqrt(n)) performs notably well for GNNs, better than PMag(sqrt(n)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed topological complexities instead of PH-dim | Vision transformers and GNNs · CIFAR10, CIFAR100, and Super-pixel MNIST | granulated Kendall coefficient | Helped |
| Use positive magnitude at scale s=√n instead of s=10^-2 (ablation) | Positive magnitude · Vision transformer and GNN experiments | granulated Kendall coefficient | Helped |
| Change the optimizer (ablation) | ViT on CIFAR10 · CIFAR10 | granulated Kendall coefficient | No clear effect |
| Use magnitude at scale √n instead of positive magnitude at scale √n (ablation) | GNNs · Super-pixel MNIST | granulated Kendall coefficient | Helped |
| Use E1 or positive magnitude at scale √n (ablation) | Proposed topological complexities · Image and graph experiments | granulated Kendall coefficient | No clear effect |
| Use data-dependent pseudometrics ρS or 01 instead of Euclidean distance (ablation) | Transformer topological complexities · CIFAR10 and CIFAR100 | granulated Kendall coefficient | Helped |
| Use 01-pseudometric instead of ρS (ablation) | Topological complexities · Vision transformer and GNN experiments | granulated Kendall coefficient | No clear effect |
| Evaluate at small learning rates (ablation) | Eα and positive magnitude at scale √n · ViT on CIFAR10 | correlation with generalization gap | Helped |
| Use SGD trajectories (ablation) | PH-dim with pseudometric ρS · ViT on CIFAR10 | granulated Kendall coefficient | Helped |
Surprising findings
- Magnitude with Euclidean distance correlates poorly for transformers, possibly due to random projections used for memory.
- Small positive-magnitude scale s=10^-2 still gives good correlation with generalization gap, though theory does not cover small s.
Limitations
- Information-theoretic total mutual information term is not computable in practice for billion-parameter models.
- Theory does not justify positive magnitude at small scale s, and Euclidean-based measures perform poorly possibly due to projections.
Experimental setup
Datasets: CIFAR10 CIFAR100 Super-pixel MNIST
Benchmarks: CIFAR10 CIFAR100 Super-pixel MNIST
Metrics: granulated Kendall coefficient Kendall tau generalization gap (accuracy gap)
Baselines: PH-dim magnitude dimension Euclidean-distance magnitude
Builds on: PH-dim generalization bounds (Birdal et al.) total mutual information bounds magnitude of metric spaces data-dependent pseudometric (Lipschitz loss)
Closest papers by meaning
- On the Limitations of Fractal Dimension as a Measure of Generalization (NeurIPS 2024 · similarity 0.92)
- Generalization at the Edge of Stability (NeurIPS 2026 · similarity 0.89)
- A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.88)
- No Wrong Turns: The Simple Geometry Of Neural Networks Optimization Paths (ICML 2024 · similarity 0.88)
- Towards Generalization beyond Pointwise Learning: A Unified Information-theoretic Perspective (ICML 2024 · similarity 0.87)
- Towards Scalable Topological Regularizers (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.