Research map / Optimization / Optimizers
Approximating Metric Magnitude of Point Sets
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.
Proposes fast approximations of metric magnitude of point sets (convex/iterative normalization, greedy and discrete-center subset selection) and applies magnitude to generalization prediction, NN regularization, and clustering.
Problem
Computing metric magnitude of a point cloud requires inverting an n×n similarity matrix, which is too costly for large datasets or repeated computation in model training.
Approach
Casts magnitude weight computation as a convex least-squares problem, proposes an Iterative Normalization update that avoids inversion, shows magnitude is not submodular in general but greedy selection works well empirically, and introduces a discrete-center hierarchy for fast subset-based approximation.
Key results
- Iterative Normalization computes magnitude for 2×10^4 points in 1.12 s versus 126.9 s for matrix inversion on the same GPU.
- Extending training trajectories from 5000 to 10000 raises the Average Granulated Kendall coefficient for Mag from 0.65 to 0.79 (Kendall tau 0.64 to 0.74).
- Magnitude regularization on MNIST MLPs (lambda=0.5) lowers the generalization gap from 0.0736 (unregularized) to 0.0499.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase trajectory length from 5000 to 10000 | Magnitude (Mag_n) · CIFAR10 training trajectories | Average Granulated Kendall (Ψ): 0.65 -> 0.79 | Helped |
| Increase trajectory length from 5000 to 10000 | Magnitude (Mag_n) · CIFAR10 training trajectories | Kendall tau (τ): 0.64 -> 0.74 | Helped |
| Increase trajectory length from 5000 to 10000 | Positive magnitude (PMag_n) · CIFAR10 training trajectories | Average Granulated Kendall (Ψ): 0.79 -> 0.88 | Helped |
| Increase trajectory length from 5000 to 10000 | Positive magnitude (PMag_n) · CIFAR10 training trajectories | Kendall tau (τ): 0.85 -> 0.90 | Helped |
| Add magnitude regularization (λ=0.5) | Two-hidden-layer fully connected network · MNIST | Test loss: 0.0757 -> 0.0602 | Helped |
| Add magnitude regularization (λ=0.5) | Two-hidden-layer fully connected network · MNIST | Generalization gap: 0.0736 -> 0.0499 | Helped |
| Increase magnitude regularization strength from λ=0 to λ=1 (ablation) | Two-hidden-layer fully connected network · MNIST | Generalization gap: 0.0736 -> 0.0464 | Helped |
| Increase magnitude regularization strength from λ=0.5 to λ=1 (ablation) | Two-hidden-layer fully connected network · MNIST | Test loss: 0.0602 -> 0.0631 | Hurt |
| Use Iterative Normalization instead of matrix inversion | Metric magnitude computation · 2×10^4 points sampled from N(0,1) in R² | Runtime (seconds): 126.9 -> 1.12 seconds | Helped |
| Use longer training trajectories | Mag_n and PMag_n correlation analysis · CIFAR10 training trajectories | Correlation coefficients | Helped |
| Use Discrete Centers instead of random subset selection | Magnitude subset approximation · Iris, Breast Cancer, Wine, MNIST, CIFAR10, CIFAR100 | Magnitude approximation quality | Helped |
| Use Discrete Centers instead of Greedy Maximization | Magnitude subset approximation · Iris, Breast Cancer, Wine, MNIST, CIFAR10, CIFAR100 | Computational cost | Helped |
Surprising findings
- Magnitude is not submodular in general: adding a single origin point to a cross-polytope-like set can increase magnitude by about 7.18 (t=5, D=500), far more than its own magnitude of 1.
- Iterative Normalization converges quickly and only requires O(n^2) per iteration, though it is not guaranteed to produce a weighting with nonnegative entries in general.
Limitations
- Magnitude is not submodular in general, so greedy approximation guarantees only hold for points on the real line.
- Empirical generalization results rely on a single architecture (ViT) and dataset (CIFAR10), which the authors note needs further investigation.
- Iterative Normalization and gradient methods may produce weightings with negative entries, which are not handled in general.
Experimental setup
Datasets: CIFAR10 CIFAR100 MNIST Iris Breast cancer (scikit-learn) Wine (scikit-learn) Swiss roll synthetic Gaussian blobs
Benchmarks: CIFAR10 (ViT training trajectories) MNIST (regularization) scikit-learn Iris/Breast cancer/Wine MNIST/CIFAR10/CIFAR100 subsamples
Metrics: runtime magnitude approximation accuracy granulated Kendall coefficient Kendall tau test loss generalization gap
Baselines: matrix inversion gradient descent SGD random subset selection k-means agglomerative (Ward) clustering DBSCAN
Builds on: metric magnitude (Leinster & Meckes) Nemhauser greedy submodular maximization magnitude-based generalization bounds (Andreeva et al.) Strassen algorithm
Closest papers by meaning
- Magnitude Distance: A Geometric Measure of Dataset Similarity (ICML 2026 · similarity 0.88)
- Metric Space Magnitude for Evaluating the Diversity of Latent Representations (NeurIPS 2024 · similarity 0.83)
- MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product (ICML 2025 · similarity 0.82)
- Scaling Laws for the Value of Individual Data Points in Machine Learning (ICML 2024 · similarity 0.82)
- Inferring Neural Signed Distance Functions by Overfitting on Single Noisy Point Clouds through Finetuning Data-Driven based Priors (NeurIPS 2024 · similarity 0.82)
- Fully Dynamic Algorithms for Chamfer Distance (NeurIPS 2025 · similarity 0.82)
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.