Research map / Learning theory and algorithms / Prediction and decision losses
Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
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.
Shows that Gaussian JL dimension reduction to target dimension O(doubling dimension) preserves near-optimal solutions for Euclidean maximization problems (max matching, max TSP, max spanning tree, max k-coverage, remote-subgraph diversity), with matching lower bounds and empirical validation.
Problem
Dimensionality reduction for Euclidean maximization problems (max-matching, max-TSP, max spanning tree, diversity measures) whose target dimension should depend on intrinsic rather than ambient or dataset-size dependence.
Approach
Use a data-oblivious Gaussian JL map and tie the target dimension to the doubling dimension of the dataset; the guarantee holds simultaneously for all candidate solutions, so any algorithm can be run in the projected space, and matching lower bounds show the dependence is tight.
Key results
- Gaussian JL to O(epsilon^-2 lambda log(1/epsilon)) dimensions preserves max-matching, max-TSP, and max spanning tree values up to 1+epsilon w.h.p., for all candidate solutions simultaneously.
- Lower bound: for basis-vector datasets, max matching in projected space is at least (sqrt(2)-epsilon) times optimum for target dimensions up to about log(n)/log(1/epsilon), showing the sqrt(2) distortion barrier.
- Empirically, high-intrinsic-dimension datasets need much larger projection dimension than low-intrinsic-dimension ones to reach the same relative error, with speedups up to two orders of magnitude at dimension 20.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the low-intrinsic-dimension version instead of the high-intrinsic-dimension version | Gaussian JL projection for max matching on MNIST · MNIST '2' and MNIST '2' + Gaussian | relative error at a given projection dimension: 50 dimensions (high intrinsic dimension) -> approximately 20 dimensions (low intrinsic dimension) for the same relative | Helped |
| Reduce the projection dimension from the ambient dimension to 20 | Geometric optimization across the evaluated datasets and problems · MNIST, CIFAR embeddings, and synthetic datasets; max matching, remote-clique, and max k-coverage | runtime: up to two orders of magnitude | Helped |
| Use low-intrinsic-dimensional data instead of high-intrinsic-dimensional data | Dimensionality reduction for max matching, remote-clique, and max k-coverage · Evaluated datasets | projection dimension required for a given relative error | Helped |
| Reduce projection dimension | Dimensionality reduction for max matching · Evaluated datasets | relative error | Helped |
| Compare datasets by cardinality rather than intrinsic dimension | Dimensionality reduction for max matching, remote-clique, and max k-coverage · Synthetic datasets | relative error | No clear effect |
Surprising findings
- Max matching distortion stays at most sqrt(2) even down to constant target dimension, for general point sets.
- A dataset with half the points (low doubling dimension) can be projected more aggressively than a dataset with twice the points, showing point-set size does not govern dimensionality reduction performance here.
Limitations
- Guarantees depend on the doubling dimension, which may be hard to compute or may be large for real data.
- Experiments use only three problems and small datasets (1000 points), with greedy heuristics for NP-hard objectives.
Experimental setup
Datasets: MNIST CIFAR embeddings (ResNet penultimate layer) synthetic basis vectors
Benchmarks: MNIST '2' CIFAR-embeddings synthetic basis vectors
Metrics: relative error speedup
Builds on: Johnson-Lindenstrauss transform doubling dimension dimensionality reduction (facility location / k-center analys
Closest papers by meaning
- Generalized Dimension Reduction Using Semi-Relaxed Gromov-Wasserstein Distance (AAAI 2025 · similarity 0.86)
- Beyond Worst-Case Dimensionality Reduction for Sparse Vectors (ICLR 2025 · similarity 0.85)
- Dimension-free deterministic equivalents and scaling laws for random feature regression (NeurIPS 2024 · similarity 0.84)
- Optimization Can Learn Johnson Lindenstrauss Embeddings (NeurIPS 2024 · similarity 0.84)
- Enhancing Sufficient Dimension Reduction via Hellinger Correlation (ICML 2024 · similarity 0.84)
- Sparse Dimensionality Reduction Revisited (ICML 2024 · similarity 0.84)
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.