Research map / Learning theory and algorithms / Optimal transport
Orlicz–Sobolev with Musielak: An Efficient Regularization Approach for Graph-based IPM
Tam Le, Truyen Nguyen, Hideitsu Hino, Kenji Fukumizu
Read the paperCheck your idea against 137,217 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 an Orlicz–Sobolev (Musielak–Orlicz) norm generalization of Sobolev IPM for probability measures on graphs, to decouple the critic regularization from the L^p geometry.
Problem
Sobolev IPM on graph metric spaces is tied to the L^p geometric structure, limiting its ability to incorporate other prior geometry beyond L^p, while classic optimal transport is flexible but costly.
Approach
Replaces the L^p-based Sobolev norm constraint on the critic with an Orlicz/Musielak-type norm, enabling a more flexible regularization of the IPM critic on graphs while retaining efficiency.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use regularized GSI-M instead of Orlicz-Wasserstein | Phi_1 and Phi_2 N-functions · AMAZON, 10K pairs, G_Log 1K nodes | computation time: OW 17-27 hours -> GSI-M under 22 seconds; 5100x and 2900x faster | Improved |
| use GSI-M instead of OW with the limit N-function Phi_0 | Phi_0 · AMAZON, G_Log 1K nodes | computation time: 90x faster | Improved |
| use Orlicz N-function Phi_1 instead of Phi_0 (linear) (ablation) | GSI-M · TWITTER, G_Log(10K,100K) | accuracy (%): 70.55 -> 72.68 | Improved |
| use Orlicz N-function Phi_2 instead of Phi_0 (ablation) | GSI-M · MPEG7 TDA, G_Log(1K,7K) | accuracy (%): 61.50 -> 78.33 | Improved |
| use Phi_1 instead of Phi_0 (ablation) | GSI-M · MPEG7 TDA, G_Sqrt(1K,32K) | accuracy (%): 65.17 -> 81.67 | Improved |
| use non-linear N-functions Phi_1 or Phi_2 instead of Phi_0 (ablation) | GSI-M · document classification and TDA | computation time | Hurt |
| use GSI-M instead of GST with same N-functions Phi_1, Phi_2 | graph-based kernel SVM · TWITTER and RECIPE document classification | accuracy | Improved |
| use random tree (OW-Phi_0-Tree) instead of full graph for OW | OW-Phi_0 · document classification | accuracy | Mixed |
| perturb graph edge weights slightly (random deviation in (0, 0.1)) (ablation) | GSI-M-Phi_1 · TWITTER, G_Log | accuracy (%): 72.68 -> 72.14 | No clear effect |
| perturb graph edge weights slightly (ablation) | GSI-M-Phi_2 · MPEG7 TDA, G_Log(1K,7K) | accuracy (%): 78.33 -> 76.17 | No clear effect |
| choose root node by cross-validation instead of randomly (ablation) | GSI-M-Phi_1 · MPEG7 TDA, G_Log | accuracy (%): 74.50 -> 75.00 | Improved |
| reduce graph size from 10K nodes to 100 nodes (ablation) | GSI-M-Phi_1 · TWITTER, G_Log | accuracy (%): 72.68 -> 71.92 | Hurt |
Experimental setup
Builds on: Sobolev IPM integral probability metric optimal transport
Closest papers by meaning
- Scalable Sobolev IPM for Probability Measures on a Graph (ICML 2025 · similarity 0.94)
- Generalized Sobolev Transport for Probability Measures on a Graph (ICML 2024 · similarity 0.90)
- An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph (NeurIPS 2025 · similarity 0.90)
- Sobolev Regularized MMD Gradient Flow (NeurIPS 2026 · similarity 0.85)
- Fast Wasserstein rates for estimating probability distributions of probabilistic graphical models (NeurIPS 2026 · similarity 0.85)
- Hierarchical Integral Probability Metrics: A distance on random probability measures with low sample complexity (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.
