Research map / Optimization / Optimizers
OT4P: Unlocking Effective Orthogonal Group Path for Permutation Relaxation
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 OT4P, a temperature-controlled differentiable map from unconstrained vectors to the orthogonal group that concentrates matrices near permutation matrices, enabling gradient-based and stochastic optimization over permutations.
Problem
Optimization over permutation matrices is NP-hard; existing continuous relaxations mostly use the Birkhoff polytope, while relaxations onto the orthogonal group remain underexplored.
Approach
Map R^{n(n-1)/2} to SO(n) via the matrix exponential of a skew-symmetric matrix, then move the orthogonal matrix toward its nearest permutation along the geodesic in the tangent space at that permutation using a power O^tau with temperature tau; a re-parameterization trick gives a gradient estimator for latent permutations.
Key results
- On mode connectivity, OT4P (tau=0.3/0.5/0.7) recovers the ground-truth permutation with 100% precision on MLP5 and ResNet18 and 100% on VGG11 for tau=0.3 and 0.7, whereas Sinkhorn reaches only 63.08% precision on VGG11.
- On neuron identity inference with Known 5%, OT4P (tau=0.3) achieves 100% precision and log-likelihood -130.9, versus -2256 for Gumbel-Sinkhorn and -3040 for Naive.
- On permutation synchronization (WILLOW-ObjectClass), OT4P consistently outperforms Reg, OrthReg, RiemanBirk and Sinkhorn in F-score and is robust to tau.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OT4P (τ = 0.3) instead of Weight Matching | mode connectivity optimization · MLP5 | log(1 + ℓ1): 0.000 ±0.00 vs 0.000 ±0.00 | No clear effect |
| Use OT4P (τ = 0.3) instead of Weight Matching | mode connectivity optimization · VGG11 | log(1 + ℓ1): 0.000 ±0.00 vs 0.000 ±0.00 | No clear effect |
| Use OT4P (τ = 0.3) instead of Weight Matching | mode connectivity optimization · ResNet18 | log(1 + ℓ1): 1.215 ±2.72 -> 0.000 ±0.00 | Helped |
| Use OT4P (τ = 0.3) instead of Gumbel-Sinkhorn | neuron identity inference · Known 5% | Precision: 62.08 ±16.0 -> 100.0 ±0.00 | Helped |
| Use OT4P (τ = 0.3) instead of Gumbel-Sinkhorn | neuron identity inference · Known 10% | Precision: 98.16 ±1.95 -> 100.0 ±0.00 | Helped |
| Use OT4P (τ = 0.3) instead of Gumbel-Sinkhorn | neuron identity inference · Known 20% | Precision: 99.84 ±0.358 -> 100.0 ±0.00 | No clear effect |
| Increase OT4P temperature from τ = 0.3 to τ = 0.5 (ablation) | mode connectivity optimization · VGG11 | log(1 + ℓ1): 0.000 ±0.00 -> 0.818 ±1.83 | Hurt |
| Increase OT4P temperature from τ = 0.3 to τ = 0.7 (ablation) | mode connectivity optimization · MLP5 | log(1 + ℓ1): 0.000 ±0.00 -> 0.000 ±0.00 | No clear effect |
| Increase OT4P temperature from τ = 0.3 to τ = 0.7 (ablation) | neuron identity inference · Known 5% | Precision: 100.0 ±0.00 -> 74.16 ±35.9 | Hurt |
| Increase OT4P temperature from τ = 0.3 to τ = 0.7 (ablation) | neuron identity inference · Known 10% | Precision: 100.0 ±0.00 -> 100.0 ±0.00 | No clear effect |
Surprising findings
- Sinkhorn-based relaxation yields poor results on VGG11 in weight matching, which the authors attribute to unreliable local minima on the Birkhoff polytope.
- OT4P at tau=0.7 performed suboptimally in the Known 5% neuron identity setting (74.16% precision) despite near-perfect results at other settings.
Limitations
- Eigendecomposition cost becomes prohibitive for very large matrices (n > 1000).
- Boundary issues with permutation matrices having eigenvalue -1 hinder use as a building block inside deep networks.
- The re-parameterization noise distribution may not capture latent permutations well.
Experimental setup
Datasets: WILLOW-ObjectClass PyTorch pretrained VGG11/ResNet18 weights synthetic linear dynamical system neuron data (n=250, 1000 samples)
Benchmarks: WILLOW-ObjectClass mode connectivity weight matching (MLP5, VGG11, ResNet18) C. elegans neuron identity inference (synthetic)
Metrics: l1-distance precision recall Hamming distance marginal log-likelihood F-score
Baselines: Weight Matching Sinkhorn Naive Gumbel-Sinkhorn Reg OrthReg RiemanBirk
Builds on: Sinkhorn operator Gumbel-Sinkhorn Lezcano-Casado dynamic trivialization Weight Matching OrthReg
Closest papers by meaning
- Differentiable extensions with rounding guarantees for combinatorial optimization over permutations (NeurIPS 2025 · similarity 0.87)
- From Sorting Algorithms to Scalable Kernels: Bayesian Optimization in High-Dimensional Permutation Spaces (ICLR 2026 · similarity 0.86)
- Kissing to Find a Match: Efficient Low-Rank Permutation Representation (NeurIPS 2023 · similarity 0.86)
- Graph Alignment via Birkhoff Relaxation (NeurIPS 2025 · similarity 0.84)
- Polynomial Time Learning Augmented Algorithms for NP-hard Permutation Problems (ICML 2025 · similarity 0.83)
- SymmetricDiffusers: Learning Discrete Diffusion on Finite Symmetric Groups (ICLR 2025 · similarity 0.83)
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.