AI Paper Atlas

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

NeurIPS 2026 · Learning theory and algorithms › Optimal transport · approach: Sinkhorn and entropic OT algorithms

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 changedWhereMeasuredEffect
use regularized GSI-M instead of Orlicz-WassersteinPhi_1 and Phi_2 N-functions · AMAZON, 10K pairs, G_Log 1K nodescomputation time: OW 17-27 hours -> GSI-M under 22 seconds; 5100x and 2900x fasterImproved
use GSI-M instead of OW with the limit N-function Phi_0Phi_0 · AMAZON, G_Log 1K nodescomputation time: 90x fasterImproved
use Orlicz N-function Phi_1 instead of Phi_0 (linear) (ablation)GSI-M · TWITTER, G_Log(10K,100K)accuracy (%): 70.55 -> 72.68Improved
use Orlicz N-function Phi_2 instead of Phi_0 (ablation)GSI-M · MPEG7 TDA, G_Log(1K,7K)accuracy (%): 61.50 -> 78.33Improved
use Phi_1 instead of Phi_0 (ablation)GSI-M · MPEG7 TDA, G_Sqrt(1K,32K)accuracy (%): 65.17 -> 81.67Improved
use non-linear N-functions Phi_1 or Phi_2 instead of Phi_0 (ablation)GSI-M · document classification and TDAcomputation timeHurt
use GSI-M instead of GST with same N-functions Phi_1, Phi_2graph-based kernel SVM · TWITTER and RECIPE document classificationaccuracyImproved
use random tree (OW-Phi_0-Tree) instead of full graph for OWOW-Phi_0 · document classificationaccuracyMixed
perturb graph edge weights slightly (random deviation in (0, 0.1)) (ablation)GSI-M-Phi_1 · TWITTER, G_Logaccuracy (%): 72.68 -> 72.14No clear effect
perturb graph edge weights slightly (ablation)GSI-M-Phi_2 · MPEG7 TDA, G_Log(1K,7K)accuracy (%): 78.33 -> 76.17No clear effect
choose root node by cross-validation instead of randomly (ablation)GSI-M-Phi_1 · MPEG7 TDA, G_Logaccuracy (%): 74.50 -> 75.00Improved
reduce graph size from 10K nodes to 100 nodes (ablation)GSI-M-Phi_1 · TWITTER, G_Logaccuracy (%): 72.68 -> 71.92Hurt

Experimental setup

Builds on: Sobolev IPM integral probability metric optimal transport

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy