CS Paper Radar

Learning Submanifolds for Subsequent Inference on Random Dot Product Graphs, Part 1: Theory

Michael W. Trosset, Carey E. Priebe

cs.LG stat.ML ·submitted 2026-09-16 19:29 UTC · v1

Abstract

We propose a framework for restricted inference on random dot product graphs whose latent positions lie on an unknown low-dimensional support manifold. For general decision problems, we propose semisupervised decision rules that use auxiliary data to learn the support manifold. Specifically, our rules use the Isomap manifold learning procedure to construct a low-dimensional Euclidean representation of the observed graph, in which space an isometrically invariant function maps configurations of points to actions. We study the behavior of the proposed rules as the quantity of auxiliary data sampled from the unknown support manifold increases. We show that, as the auxiliary sample size increases, the risk of the semisupervised rule converges to the risk of an oracle rule that relies on the maximal amount of low-dimensional Euclidean structure that can be extracted from the support manifold. Examples, applications, and simulation studies are deferred to a sequel.

Comment
23 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Deep Learning for Random Objects in Metric Spaces: Beyond Manifold Assumptions

cs.LG stat.MLmath.STstat.ME ·2026-10-22 ·Marcos Matabuena, Xiaokai Luo, Oscar Hernan Madrid Padilla
hot direction similarity 0.61
Abstract

Deep learning (DL) methods have substantially improved predictive performance across a wide range of downstream prediction tasks, enabling new discoveries in multiple domains. However, principled DL methods for non-Euclidean random objects remain relatively scarce, despite the growing importance of modern biomedical outcomes taking the form of probability distributions, random graphs, functions, and other random objects in metric spaces. Motivated by a new generation of digital and clinical biomarkers, we propose a deep learning framework for regression with random objects in metric spaces. Our approach operates directly on the metric structure of the response space, avoiding restrictive manifold or Euclidean embedding assumptions imposed by many existing methods. At the same time, it retains modern statistical guarantees under the stated statistical assumptions. We establish statistical consistency and convergence rates for the proposed estimator, and characterize conditions under which it can mitigate the curse of dimensionality for hierarchically compositional regression functions. Extensive simulation studies demonstrate competitive predictive performance, with gains over several competing approaches in multiple Euclidean and non-Euclidean configurations. Finally, we demonstrate the practical utility of the proposed framework in two digital health case studies with distribution-valued outcomes in Wasserstein spaces, using high-resolution accelerometry and continuous glucose monitoring data. Embedding-based deep-learning methods may be less suitable when no informative low-dimensional representation exists or when the learned embedding does not adequately preserve the intrinsic geometry of the response space.

0.50

Learning Random Geometric Graphs Drawn in Probabilistic Metric Spaces

cs.LG stat.MLstat.AP ·2026-08-19 ·Dalia Chakrabarty, Kangrui Wang, Chuqiao Zhang, Ye Liu
similarity 0.61
Abstract

We present a new data-driven learning of a Random Geometric Graph (RGG) of a multivariate dataset, where the graph is drawn in a probabilistic metric space. This graph learning works for generic datasets, irrespective of the type of the observables; their probability distributions; or size of the data. We identify a metric of the space that the graph is drawn in, as a probability distribution of a random variable that we introduce, namely, a variable that represents the disparity between the connectedness of two vertices of the graph, and the correlation between the two random variables that are attached to the respective vertex. It is the closed-form {\it{cdf}} of this disparity variable that we advance as the distance function of the host space of the learnt RGG, such that the edge exists between any two nodes, if this inter-nodal distance falls short of a chosen cutoff probability. Drawing the RGG in this probabilistic space leads to the graph being an Soft RGG, such that any edge - if it exists - exists with an identified probability. We forward a simple Rejection Sampling-based technique for learning the probability of any edge. The expected degree distribution of a vertex of this RGG is identified as local, and dependent on the inter-observable correlation matrix. If said correlation matrix is not known, it can be learnt given the data, using its closed-form posterior probability density function, that we forward. We illustrate our graph learning method by learning multiple RGGs of highly multivariate real datasets.

0.27

Geometric Stability and Sample Complexity for Compositional Function Priors

cs.LG stat.ML ·2026-11-14 ·Christopher L. Hammond
publishedtheory similarity 0.61
Abstract · 25 pages. An extended abstract was accepted at the NeurIPS 2026 Workshop on Symmetry and Geometry in Neural Representations (NeurReps), non-…

We study when compositional structure yields dimension reduction in supervised learning. We frame learning as empirical risk minimization with a function-space prior: a regularization functional selects a subset of functions with favorable approximation and metric entropy. The models are compositions $f(x)=g(Ax+Δh(x))$, where $A\in\mathbb{R}^{k\times d}$ is a linear base map, $Δh$ is a nonlinear correction, and $g$ is an outer function; that is, $f$ is an arbitrary smooth function of a $k$-dimensional representation of the input that is linear up to a correction. We prove covering-number bounds showing that the statistical complexity of this class interpolates between an intrinsic regime, parametric in the $kd$ entries of the linear map and nonparametric only in the representation dimension $k$, and an ambient $d$-dimensional nonparametric rate; the interpolation is controlled by the correction size $\varepsilon=\|Δh\|$. We then connect $\varepsilon$ to data geometry. If the data lie in a small tube around a $k$-dimensional manifold and the regression target depends on the input only through its nearest point on that manifold, then locally the target factorizes exactly as $g(Ax+Δh(x))$ with $A$ a tangent chart and a correction whose Sobolev norm scales linearly with curvature at the localization scale. Patching such local models over an atlas gives a finite-sample excess-risk bound for a least-squares estimator over a finite net of local models, whose ambient term vanishes with curvature. For a one-dimensional model problem we also prove a converse: on curved data, every affine compositional predictor faces an error floor unless its correction budget scales with curvature, while the matching curved model class attains the intrinsic rate. The correction size $\varepsilon$ is thus the effective-dimension parameter linking curvature to statistical complexity.

0.31

Nested Inductive Bias Framework for SPD Manifold Learning

cs.LG ·2026-09-03 ·Tushar Das
similarity 0.61
Abstract

In Geometric Deep Learning, inductive biases serve two primary functions: enforcing manifold constraints and embedding relational priors. Currently, representation learning on SPD manifolds frequently relies on pullback Euclidean metrics, such as the Log-Euclidean Metric, to satisfy the former. While computationally efficient in avoiding domain boundary violations, these metrics induce a flat geometry that may fail to capture the intrinsic relational priors of datasets. While metrics such as the Poincaré metric are widely utilized to induce domain-aligned relational priors, generalizing them from standard vector representations to the SPD manifold has remained a challenge. To bridge this gap, we introduce a Nested Inductive Bias framework that utilizes a two-stage diffeomorphic composition to formally pull back non-Euclidean target geometries onto the SPD manifold. This framework enables the construction of curvature-aligned Riemannian classifiers that simultaneously respect matrix constraints and the latent relational geometry of the data. Empirical evaluations on kinematic and signal processing benchmarks, together with synthetic experiments, demonstrate that deep manifold networks experience degradation in class separability unless the metric curvature aligns with the intrinsic data distribution. Furthermore, for standard vectorized architectures, we propose the Rational Conformal Metric (RCM), designed to establish state-of-the-art geometric robustness against outliers by bounding the representation space.

0.19

IsoAct: Geometry-Aware Post-hoc Debiasing via Isometric Actions

cs.LG ·2026-10-26 ·Sumin Park, Taero Kim, Minhyeong Cho, Subeen Park, Jong Hwan Lee +1 more
similarity 0.57
Abstract

Learning representations that are robust to nuisance factors is essential for reliable deployment, but remains challenging when the representations lie on non-Euclidean manifolds. Existing debiasing methods typically assume Euclidean representations or apply linear interventions, which can distort the geometry of structured latent spaces. We propose IsoAct, a post-hoc framework that accounts for geometry in both nuisance identification and representation editing. It identifies nuisance-predictive directions using Fisher discriminant analysis (FDA) in tangent coordinates and applies corrections through manifold-native actions that preserve manifold membership. Controlled and real-world experiments on hyperspherical, hyperbolic, and $\mathrm{SE}(3)$ representations evaluate nuisance reduction, utility preservation, and manifold validity jointly. IsoAct reduces nuisance recoverability while retaining competitive utility. Its clearest joint result is on KLIFS, combining reduced kinase-group recoverability, strong structural prediction, and valid rigid poses.

0.18

Low-Dimensional Embeddings for Gaussian Kernels on Manifolds

cs.CG cs.LG ·2026-09-14 ·Soumik Dutta, Kunal Dutta
theory similarity 0.57
Abstract · 57 pages, 3 figures

The Gaussian kernel is a widely used similarity measure underlying kernel methods such as kernel PCA and spectral clustering, but computing Gaussian kernel distances for many pairs of points can be expensive. Using Random Fourier Features (RFF), Chen and Phillips [ALT 2017] showed that for points in a $d$-dimensional Euclidean ball in ${\mathbb R}^N$, $t=Ω((d/\varepsilon^2)\log(dR/\varepsilon))$ features suffice to preserve all pairwise Gaussian kernel distances within a $(1\pm\varepsilon)$ factor with high probability. We establish a uniform relative-error embedding theorem for the more general setting of an arbitrary positive-reach submanifold $\mathcal M\subset{\mathbb R}^N$ of intrinsic dimension $d$. We show that $t=O((d/\varepsilon^2)\log(\operatorname{vol}(\mathcal M)^2N^{2d}/(\operatorname{vol}(B_1^d(0))^2\operatorname{rch}(\mathcal M)^{2d}\varepsilon^{2d+1}δ)))$, or approximately $O((d^2/\varepsilon^2)(\log N+\log(1/(\varepsilonδ))))$, RFFs suffice, with probability $1-δ$, to preserve the Gaussian kernel distance between every pair of manifold points up to relative error $\varepsilon$. Thus the bound depends only logarithmically on the ambient dimension and on manifold parameters such as volume and reach, while retaining the $1/\varepsilon^2$ Euclidean rate. We also prove a topological consequence: under the same RFF embedding, persistent homology is preserved in the sense that weighted Cech and Rips filtrations built from Gaussian kernel power distance are $(1\pm\varepsilon_\star)$-interleaved, where $\varepsilon_\star$ accounts for both distance distortion and kernel-weight approximation.

0.22

VC-Dimension and Generalization in Geometric Machine Learning with Applications to Active Learning

cs.LG stat.MLmath.DG ·2026-11-09 ·Gokul Bhusal, Delanna Do, Ekaterina Merkurjev, Kevin Miller, Stephan Wojtowytsch
theory similarity 0.56
Abstract · 19 pages + appendices

We compute the VC-dimension of metric ball classifiers in the model spaces of Riemannian geometry (Euclidean, spherical, hyperbolic) and present upper and lower bounds on the VC-dimension of metric balls in several other situations, including general normed vector spaces (potentially infinite VC-dimension), vector spaces with $\ell^p$-norms (VC-dimension grows at least linearly in the dimension, faster than Euclidean for $p=1$), flat tori, and general Riemannian manifolds (arbitrarily large VC-dimension after a conformal change). In several situations where the VC-dimension is large or even infinite, we prove generalization bounds under additional assumptions on the data distribution using covering arguments. Both in the VC-dimension and covering setting, we consider data on low-dimensional subsets of high-dimensional Euclidean spaces. As an application, we consider coverage-based algorithms in active learning.

0.29

Nonparametric In-Context Learning under Growing Geometric Complexity: Minimax Optimality and Local Geometry-Adaptivity of Transformers

cs.LG stat.MLmath.ST ·2026-09-25 ·Jaehee Seo, Jisu Kim
top venuetheory similarity 0.56
Abstract · 63 pages, 3 figures. Accepted at NeurIPS 2026

Transformers have become a central architecture for in-context learning (ICL), particularly through their state-of-the-art performance in large language models. This success motivates understanding how transformers exploit intrinsic geometry of real-world data. However, existing nonparametric ICL theory has largely focused on simplified settings, such as Euclidean domains or single manifold models, failing to fully explain its phenomenal empirical success in complex tasks. To address this gap, we study the prediction problem under unknown heterogeneous geometry, modeled by sample size-dependent mixtures of manifolds with heterogeneous dimensions, smoothness, and sampling masses. Under the growing geometric complexity model, we establish a minimax lower bound capturing the aggregate difficulty of the components and construct an oracle tangent local polynomial estimator with a matching upper bound. This estimator is connected to a structure-informed, two-stage softmax transformer with a geometric preconditioner and local polynomial solvers. The transformer achieves negligible approximation error relative to the minimax rate with logarithmic depth and polynomial size. Finally, we derive an in-context generalization bound for near empirical risk minimizers (ERM) over this class. Together, these results identify conditions under which the resulting predictor exploits local geometry and attains minimax rate.

0.57