CS Paper Radar

Minimax Rates and Improved Spectral Convergence for Multi-Manifold Clustering

Haoyu Chen, Chenghui Li

cs.LG stat.ML ·submitted 2026-10-11 20:14 UTC · v1

Abstract

We study eigenpair estimation for the tensorized, density-weighted Laplace--Beltrami operator from $n$ independent data points sampled from a multi-manifold mixture distribution where manifolds may intersect. Let $d$ denote the largest intrinsic dimension of the manifold components and $s\geq2$ the smoothness of the sampling densities. For simple, nontrivial eigenpairs, we establish the minimax rate $n^{-s/(d+2s)}$ for approximating the eigenvalue and eigenfunction of the tensorized Laplace--Beltrami operator, and show that a continuum plug-in estimator based on kernel density estimation attains the same rate when the supporting manifolds are known. We further analyze a manifold-agnostic graph Laplacian estimator and prove that its eigenpairs converge to those of the tensorized Laplace--Beltrami operator at rate $n^{-1/(2.5d-1)}$, up to logarithmic factors, improving upon previously known spectral convergence rates for multi-manifold learning. Numerical experiments on synthetic multi-manifold data corroborate the rates guaranteed by our theorems. These results characterize the information-theoretic difficulty of multi-manifold spectral estimation and quantify the additional cost of learning without oracle component information.

Closest papers

Nearest neighbours by meaning across the whole index.

Online Covariance Estimation for Averaged Stochastic Gradient Descent on Riemannian Manifolds

cs.IT stat.MLcs.LGmath.OC+1 ·2026-10-24 ·Jingrong Guan, Liwei Jiang, Sen Na
similarity 0.65
Abstract · 60 pqges, 7 figures, 2 tables

We study online inference for averaged Riemannian stochastic gradient descent (RSGD) when the unknown parameter lies on a manifold. Although the averaged RSGD iterate is asymptotically normal, practical inference requires estimating the unknown covariance operator in its limiting distribution. Existing online batch-means methods cannot be applied directly because a general Riemannian manifold lacks an addition operation, and the tangent space containing the Riemannian gradient varies across iterations. Through vector transport, we construct overlapping and non-overlapping covariance estimators that adaptively combine information from successive batches while accounting for the changing tangent spaces. The proposed estimators are online, require neither Riemannian Hessian computations nor a prespecified terminal sample size, and attain the same convergence rates as their Euclidean counterparts (Zhu et al., 2023). Together with asymptotic normality, these estimators enable online statistical inference for RSGD on manifolds. We illustrate the proposed framework through a detailed study of streaming principal component analysis on Grassmann manifolds.

0.14

Low-Dimensional Embeddings for Gaussian Kernels on Manifolds

cs.CG cs.LG ·2026-09-14 ·Soumik Dutta, Kunal Dutta
theory similarity 0.61
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

Geometry-Aware Graph Construction via Adaptive Spectral Bandwidth Control

cs.LG eess.SP ·2026-09-03 ·Ecem Bozkurt, Antonio Ortega
published similarity 0.61
Abstract · Accepted at IEEE MLSP 2026. 6 pages, 4 figures

Kernelized graph methods - spectral clustering, diffusion maps, and sparse kernel -regression graphs - that use Gaussian kernels depend on the choice of Gaussian bandwidth sigma, which governs the spectral character of the local kernel operator. When sigma is too small, the kernel overestimates local complexity and treats each sample as an independent direction; when sigma is too large, the kernel collapses multiple directions together, the condition number diverges, and all geometric discrimination is lost. We propose a choice of scale to make the spectral complexity of the kernel consistent with the intrinsic complexity of the underlying manifold. We propose a per-node bandwidth criterion that operationalizes this principle by jointly matching the kernel's effective rank to the local intrinsic dimension estimated via minimum spanning tree, anchoring the search in the manifold-consistent log-log scaling regime. We evaluate SSL embeddings from six encoders on CIFAR-100, showing that adaptive bandwidth consistently improves leave-one-out (LOO) classification and label propagation (LP) accuracy over fixed-bandwidth methods and competing adaptive methods.

0.27

Minimax Rate for Diffusion-Guided Local Intrinsic Dimension Estimation based on Fokker-Planck Equation

cs.LG stat.MLmath.ST ·2026-09-04 ·Jaehee Seo, Wontae Jeong, Jisu Kim
theory similarity 0.59
Abstract · 35 pages, 1 figure

Diffusion-guided methods have recently emerged as effective tools for probing the intrinsic geometry of high-dimensional data. Understanding their accuracy requires quantifying both (i) finite-scale approximation error relative to the true local intrinsic dimension (LID) and (ii) estimation error from finite samples. We address these two questions for the FLIPD field (Kamkari et al., 2024; arXiv:2406.03537), defined at the population level through the logarithmic scale derivative of a Gaussian-smoothed density and admitting a Fokker--Planck representation. For $α$-smooth densities on a regular $d$-dimensional manifold, we establish a uniform $O(σ^2)$ approximation bound relative to the manifold dimension $d$. Under expected integrated squared loss, we prove a minimax lower bound of order $(nσ^d)^{-1}$ for estimating the FLIPD field from $n$ observations when $n^{-1/(2α+d)}\leσ\leσ_0$. A plug-in FLIPD estimator based on the empirical denoising score matching (DSM) solution attains a matching upper bound. Thus the minimax rate is of order $(nσ^d)^{-1}$ and it becomes $n^{-2α/(2α+d)}$ at its smallest scale.

0.31

A Finslerian Approach for Embedding Directed Data

cs.LG stat.ML ·2026-09-29 ·Gwendal Debaussart-Joniec, Théau Blanchard, Argyris Kalogeratos
theory similarity 0.58
Abstract

Many datasets carry an intrinsic directionality: citations point backward in time, cells differentiate along lineages, and traffic follows preferred routes. Spectral embedding methods, including most of their extensions to directed graphs, discard this information: they symmetrize the data and map it into a Euclidean space where asymmetry cannot be represented. We instead model directed data as sampled from a Finsler manifold, whose distance depends on the direction of travel, and study the kernel operator built from this asymmetric distance. Through a moment expansion of this operator, we show that its symmetric and antisymmetric parts separate geometry from direction. As the bandwidth of the kernel vanishes, the symmetric part converges to a weighted Laplacian, recovering diffusion maps in the Riemannian case, while the antisymmetric part converges to a first-order transport operator that encodes the directionality. We prove that the corresponding graph operators, built from finitely many samples, converge uniformly and almost surely to these limits. For Randers metrics, this vector field is explicit and yields an embedding algorithm recovering both the manifold structure, from the spectrum of the symmetric part, and the underlying drift. We illustrate the approach on synthetic directed graphs and point-clouds.

0.23

Bracketing Uncertainty in Clustering Under the Manifold Hypothesis

cs.LG stat.MLq-bio.QM ·2026-09-15 ·Savik Kinger, Luciano Dyballa, Steven W. Zucker
similarity 0.58
Abstract

The manifold hypothesis suggests a natural criterion for clustering: partition data according to the manifold component from which each point is drawn. Whether two components are separable depends on a geometric tradeoff: the ambient separation between components versus the largest gap in sampling. In practice, this tradeoff is rarely assessed explicitly, leading standard methods to over-commit to a single clustering assignment even when the data do not support a unique answer. We formalize this tradeoff by combining intrinsic manifold geometry (volume growth and reach) with sample-level quantities (fill distance and density), yielding a threshold phenomenon for mutual-$k$-nearest-neighbor graphs: when the offset-to-fill ratio exceeds a conservative upper threshold, component separation is preserved; below a lower threshold, components fuse. The gap between these thresholds defines a geometric uncertainty zone in which the number of clusters is not identifiable from the data. Nevertheless, conventional approaches still seek one: sweeping parameters (an engineering approach) or fitting a generative mixture model (a model-based approach). Rather than forcing a single estimate of the number of clusters, we propose Manifold-Based Clustering (MBC), which returns an explicit bracket interval to quantify the underlying data uncertainty. This bracket acts as an empirically calibrated diagnostic: it narrows when a single resolution is supported, widens when multiple resolutions coexist, and collapses to one when no separated structure is detectable. Empirically, we find that many real datasets lie within the uncertainty zone rather than admitting one clear answer. Our results suggest that ambiguity in cluster number is often intrinsic, and should be quantified rather than resolved.

0.47

Shape Operator PCA: Curvature-Aware Projections for Geometric Machine Learning

cs.LG cs.AIcs.CVstat.ML ·2026-08-15 ·Alexandre L. M. Levada
benchmark similarity 0.58
Abstract · 23 pages, 4 figures, 4 tables

In this paper, we propose SHOPCA (Shape Operator-based Principal Component Analysis), a novel method for unsupervised metric learning and dimensionality reduction that incorporates differential geometric information into the covariance structure of classical PCA. SHOPCA regularizes the global covariance matrix using the mean shape operator, defined as the average of the absolute local shape operators estimated from the data manifold, steering principal components toward directions of both maximum variance and informative curvature. A single trace-normalized mixing coefficient $α$ controls the regularization, recovering standard PCA at $α= 0$ and a curvature-driven embedding as $α\to \infty$. We further introduce a fully unsupervised criterion for selecting $α$ based on the spectral eigengap of the regularized covariance matrix, maximizing the relative separation between the top-$d$ and remaining eigenvalues without using class labels. We evaluate SHOPCA on more than 50 real-world benchmark datasets, comparing it with PCA, ISOMAP, and UMAP using Adjusted Rand Index (ARI), Normalized Mutual Information (NMI), Fowlkes-Mallows index (FM), and V-measure. Results show that SHOPCA consistently improves clustering quality over PCA across a broad range of datasets and surpasses UMAP on small-sample settings, where iterative neighborhood-based manifold estimation can degrade. SHOPCA is computationally tractable, parameter-efficient, and applicable to domains requiring fully unsupervised, geometry-aware dimensionality reduction.

0.10

Efficient Estimation of High Information Projections using Nearest Neighbours

cs.LG stat.ML ·2026-08-26 ·David P. Hofmeyr
similarity 0.58
Abstract

An intuitive method for dimensionality reduction is proposed, which is highly effective for finding interesting projections of multivariate data. Following similar intuitive motivation to a number of existing techniques, the proposed method is based on enhancing the nearest neighbour relationships in the data. The proposed projection arises from the spectral decomposition of a matrix designed to encode the local covariance structure in the data, where the local covariance at a point is captured by pairs of its nearest neighbours. We show that under standard regularity conditions this matrix is a consistent estimator of the so-called ``Density Information Matrix'' (DIM); a non-parametric analogue of the Fisher Information Matrix. Spectral decompositions of DIMs have been shown to be connected with the important problems of Independent Components Analysis and, in the supervised context, Sufficient Dimension Reduction. However, existing estimators of the DIM are computationally expensive to compute and only target the DIM of a surrogate density, which is proportional to the square of the true underlying density. In addition, we go on to explore the practical utility of our method in aiding the downstream tasks of cluster analysis and outlier detection.

0.22