Generalized Sobolev IPM for Graph-Based Measures

• URL: http://arxiv.org/abs/2510.25591v1
• Date: Wed, 29 Oct 2025 14:59:26 GMT
• Title: Generalized Sobolev IPM for Graph-Based Measures
• Authors: Tam Le, Truyen Nguyen, Hideitsu Hino, Kenji Fukumizu,
• Abstract summary: We study the Sobolev IPM problem for measures supported on a graph metric space, where critic function is constrained to lie within the unit ball defined by Sobolev norm.<n>We propose to generalize Sobolev IPM through the lens of emphOrlicz geometric structure, which employs convex functions to capture nuanced geometric relationships.<n>This generalization encompasses classical Sobolev IPM as a special case while accommodating diverse geometric priors beyond traditional $Lp$ structure.
• Score: 26.692344867327332
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study the Sobolev IPM problem for measures supported on a graph metric space, where critic function is constrained to lie within the unit ball defined by Sobolev norm. While Le et al. (2025) achieved scalable computation by relating Sobolev norm to weighted $L^p$-norm, the resulting framework remains intrinsically bound to $L^p$ geometric structure, limiting its ability to incorporate alternative structural priors beyond the $L^p$ geometry paradigm. To overcome this limitation, we propose to generalize Sobolev IPM through the lens of \emph{Orlicz geometric structure}, which employs convex functions to capture nuanced geometric relationships, building upon recent advances in optimal transport theory -- particularly Orlicz-Wasserstein (OW) and generalized Sobolev transport -- that have proven instrumental in advancing machine learning methodologies. This generalization encompasses classical Sobolev IPM as a special case while accommodating diverse geometric priors beyond traditional $L^p$ structure. It however brings up significant computational hurdles that compound those already inherent in Sobolev IPM. To address these challenges, we establish a novel theoretical connection between Orlicz-Sobolev norm and Musielak norm which facilitates a novel regularization for the generalized Sobolev IPM (GSI). By further exploiting the underlying graph structure, we show that GSI with Musielak regularization (GSI-M) reduces to a simple \emph{univariate optimization} problem, achieving remarkably computational efficiency. Empirically, GSI-M is several-order faster than the popular OW in computation, and demonstrates its practical advantages in comparing probability measures on a given graph for document classification and several tasks in topological data analysis.

Related papers

• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Towards A Unified PAC-Bayesian Framework for Norm-based Generalization Bounds [63.47271262149291]
  We propose a unified framework for PAC-Bayesian norm-based generalization.<n>The key to our approach is a sensitivity matrix that quantifies the network outputs with respect to structured weight perturbations.<n>We derive a family of generalization bounds that recover several existing PAC-Bayesian results as special cases.
  arXiv  Detail & Related papers  (2026-01-13T00:42:22Z)
• sparseGeoHOPCA: A Geometric Solution to Sparse Higher-Order PCA Without Covariance Estimation [8.802387139798808]
  We propose a novel framework for high-order principal component analysis (SHOPCA) that introduces a perspective to tensor-dependent decomposition.<n>We show that sparseGeoHOP supports in high-dimensional image settings and on ImageNet.
  arXiv  Detail & Related papers  (2025-06-10T10:30:48Z)
• An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph [26.692344867327332]
  We investigate optimal transport (OT) for measures on graph metric spaces with different total masses.<n>To mitigate the limitations of traditional $Lp$ geometry, Orlicz-Wasserstein (OW) and generalized Sobolev transport ( GST) employ Orlicz geometric structure.<n>We establish theoretical background to solve Orlicz-EPT using a binary search algorithmic approach.
  arXiv  Detail & Related papers  (2025-02-02T10:16:09Z)
• Scalable Sobolev IPM for Probability Measures on a Graph [26.28795508071077]
  We investigate the Sobolev IPM problem for probability measures supported on a graph metric space.<n>By exploiting the graph structure, we demonstrate that the regularized Sobolev IPM provides a emphclosed-form expression for fast computation.
  arXiv  Detail & Related papers  (2025-02-02T10:14:53Z)
• Generalized Sobolev Transport for Probability Measures on a Graph [26.64899319099165]
  We study the optimal transport (OT) problem for measures supported on a graph metric space. We leverage a specific class of convex functions for Orlicz structure to propose the generalized Sobolev transport ( GST) We empirically illustrate that GST is several-order faster than the Orlicz-Wasserstein (OW)
  arXiv  Detail & Related papers  (2024-02-07T01:49:03Z)
• Tempered Calculus for ML: Application to Hyperbolic Model Embedding [70.61101116794549]
  Most mathematical distortions used in ML are fundamentally integral in nature. In this paper, we unveil a grounded theory and tools which can help improve these distortions to better cope with ML requirements. We show how to apply it to a problem that has recently gained traction in ML: hyperbolic embeddings with a "cheap" and accurate encoding along the hyperbolic vsean scale.
  arXiv  Detail & Related papers  (2024-02-06T17:21:06Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• Bayesian Quadrature on Riemannian Data Manifolds [79.71142807798284]
  A principled way to model nonlinear geometric structure inherent in data is provided. However, these operations are typically computationally demanding. In particular, we focus on Bayesian quadrature (BQ) to numerically compute integrals over normal laws. We show that by leveraging both prior knowledge and an active exploration scheme, BQ significantly reduces the number of required evaluations.
  arXiv  Detail & Related papers  (2021-02-12T17:38:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.