New algorithm finds k-centers from noisy distance estimates.
problem Finding k-centers in unknown metric spaces with noisy distance queries.
method Active algorithms using UCB, Thompson Sampling, and Track-and-Stop.
result Approximation ratio of two with high probability.
Algorithm learns nearest neighbor graph from noisy distance queries.
problem Learning nearest neighbor graph from noisy distance samples.
method Active algorithm to find graph with high probability, analyzing query complexity.
result Empirically and theoretically efficient, needing only O(n log(n)Delta^-2) queries.
New method recovers manifold distances from noisy data.
problem Reconstructing manifold geometry from noisy distance measurements.
method Develops new framework to estimate L2-norms of expectation-functions, uses geometric clusters to recover distances.
result Recovery of true distances up to an additive error of O(ε log ε⁻¹) under mild geometric assumptions.
DDPMs are robust to noisy score estimates and achieve optimal convergence rates in Wasserstein-2 distance.
problem Evaluating the quality of DDPMs in Wasserstein distance with noisy score estimates.
method Established finite-sample guarantees in Wasserstein-2 distance for DDPMs, considering noisy score estimates.
result Optimal convergence rates in Wasserstein-2 distance for DDPMs, matching Gaussian case.
New method beats volumetric barrier for manifold recovery.
problem Reconstructing latent geometry from noisy distances.
method Orthogonal Ring Distance Estimation Routine (ORDER).
result Achieves pointwise distance estimation of order n−2/(d+5). WAR method improves classifier robustness in noisy label datasets.
problem Learning robust classifiers in presence of noisy labels.
method Adversarial regularization based on Wasserstein distance.
result WAR method outperforms state-of-the-art competitors on noisy label datasets.
Reconstructs a manifold from noisy intrinsic distances.
problem Reconstructing a smooth Riemannian manifold from intrinsic distances of points.
method Uses random sample points and noisy distances to construct an approximation of the manifold.
result It is possible to construct an approximation of the Riemannian manifold with high probability when N is large enough. New metric compares noisy neural trajectories using optimal transport.
problem Existing metrics fail to capture differences in noisy, dynamic neural responses.
method Proposed an optimal transport distance metric for Gaussian processes.
result Metric effectively compares neural dynamics in different systems.
The paper sets sample complexity bounds for learning high-dimensional simplices in noisy data.
problem Learning high-dimensional simplices from noisy data.
method Sample compression techniques and Fourier-based method for noisy observations.
result Established sample complexity bounds for simplex learning in noisy regimes.
Bayesian neural flows improve Gaia distance estimates and dust modeling.
problem Improving precision of distance estimates from Gaia DR2 data.
method Normalizing flow for learning flexible color-magnitude diagrams.
result Distance posteriors improved by more than 48% over raw Gaia data.
Algorithm identifies nearest mode in noisy data.
problem Identifying the point with the minimum k-th nearest neighbor distance in unknown multivariate probability density.
method Sequential learning algorithm using noisy oracle queries to adaptively decide which points to query.
result Upper bounds on query complexity show significant improvement over baselines.
New ABC method improves Bézier simplex fitting for noisy data.
problem Overfitting in Bézier simplex fitting when sample points are not on the Pareto set.
method Extended Bézier simplex model to a probabilistic one and proposed a new learning algorithm based on approximate Bayesian computation (ABC) with Wasserstein distance.
result The new algorithm converges on a finite sample and outperforms deterministic methods on noisy instances.
Improved reSGLD accelerates convergence in non-convex learning problems.
problem Inefficient swaps due to noisy energy estimators in reSGLD.
method Variance reduction for noisy energy estimators, theoretical analysis, and numerical experiments.
result Exponential acceleration in convergence for non-convex learning problems.
Learn ODEs from noisy data using RKHS and optimization.
problem Learning nonparametric ODEs from noisy data.
method Using RKHS theory, solve a constrained optimization problem iteratively with penalty methods and Euler approximations.
result Prove a generalization bound for L2 distance between true and estimated solutions.
The paper analyzes how noise affects distances in high-dimensional data and when they remain useful.
problem Noise corrupts distances in high-dimensional data, making them unreliable for identifying true nearest and farthest neighbors.
method The paper uses asymptotic probabilistic expressions to characterize noise effects and decomposes data into ground truth and noise components.
result Under certain conditions, empirical neighborhood relations remain truthful even when distance concentration occurs.
Paper tackles noisy comparison oracle for robust clustering algorithms.
problem Finding robust clustering algorithms under noisy comparison oracle.
method Develops algorithms for k-center clustering and agglomerative hierarchical clustering using noisy comparison oracle.
result Proves robust algorithms achieve good approximation guarantees with high probability.
This work incorporates topological features via persistence diagrams to classify point cloud data arising from materials science. Persistence diagrams are multisets summarizing the connectedness and holes of given data. A new distance on the space of persistence diagrams generates relevant input features for a classifi…
A novel weighted distance improves fuzzy c-means clustering accuracy.
problem Improving fuzzy c-means clustering performance with weighted distances.
method Proposed Canberra Weighted Distance to enhance FCM algorithm.
result Experimental results show superior performance of the proposed method.
Study improves estimation of functions from noisy data using convex penalties.
problem Estimating functions from noisy point evaluations of linear operators.
method Tikhonov regularization with convex and p-homogeneous penalty functionals. result Derives concentration rates for regularized solutions in symmetric Bregman distance.
The paper introduces a Hessian-based method to improve generalization in fine-tuned deep neural networks.
problem Improving generalization in fine-tuned deep neural networks, especially in noisy conditions.
method PAC-Bayesian analysis to identify a Hessian-based distance measure, proving generalization bounds, and developing an algorithm with a generalization error guarantee.
result Hessian-based distance measure correlates well with observed generalization gaps and can match the scale of these gaps in practice.
Paper proposes a method to recover point configurations from noisy distance data.
problem Recovering point configurations from noisy distance data.
method Robust Euclidean Distance Geometry via Dual Basis (RoDEoDB) algorithm.
result Exact recovery guarantees for point configuration and Gram matrix under mild conditions.
The paper introduces uncertainty estimates for embedding objects based on noisy triplet comparisons.
problem Learning from ordinal data without a distance metric.
method Bootstrap and Bayesian approaches to estimate uncertainty for embedding algorithms.
result Empirical uncertainty estimates are well-calibrated and useful for selecting parameters or quantifying uncertainty.
Although recovering an Euclidean distance matrix from noisy observations is a common problem in practice, how well this could be done remains largely unknown. To fill in this void, we study a simple distance matrix estimate based upon the so-called regularized kernel estimate. We show that such an estimate can be chara…
A new topology design improves zero-shot classification performance in contrastive learning.
problem Improving zero-shot classification performance in contrastive visual-textual alignment.
method Proposed an alternative topology design using multiple class tokens and an oblique manifold with negative inner product.
result Improves zero-shot classification performance by an average of 6.1%.
A new method detects small holes in noisy data.
problem Detecting small holes in high-density regions from noise.
method Robust Density-Aware Distance (RDAD) filtration, incorporating distance-to-measure concept.
result The RDAD filtration prolongs the persistences of small holes, making them distinguishable from noise.
Method counters noisy labels by discounting distant samples.
problem Training models with noisy labels in medical and autonomous domains.
method Discounting distant samples from class centroids in latent space.
result Significant improvements in classification accuracy.
Improved fine-tuning with regularization and robustness for noisy labels.
problem Fine-tuning pre-trained models on small datasets can lead to overfitting and memorization.
method PAC-Bayes generalization bound analysis, layer-wise regularization, self-label-correction, label-reweighting.
result Improves performance by 1.76% on average for image classification tasks and 0.75% for few-shot classification.
Most existing distance metric learning methods assume perfect side information that is usually given in pairwise or triplet constraints. Instead, in many real-world applications, the constraints are derived from side information, such as users' implicit feedbacks and citations among articles. As a result, these constra…
A new method ODR-BINDy improves model discovery from noisy data.
problem Discovering models from noisy datasets with error-in-variable problem.
method ODR-BINDy uses orthogonal distance regression with Bayesian model selection.
result ODR-BINDy consistently outperforms existing methods in recovering correct models.
Local regularization improves geometric estimates from noisy data.
problem Improving geometric understanding from noisy, perturbed data.
method Local regularization of noisy point clouds to define similarity.
result Locally regularized similarity leads to better geometric recovery.
Study rates of convergence for approximate solutions to linear ill-posed problems in Hilbert scales.
problem Linear ill-posed inverse problems with noisy data.
method Approximate reconstructions from random noisy data using regularization schemes in Hilbert scale.
result Explicitly established error bounds for smooth regression functions.
Paper relaxes symmetry conditions for universal feature selection in noisy data.
problem Feature selection in noisy data with weak symmetry.
method Developed a universal feature selection framework using singular value decomposition of canonical dependence matrix.
result Selected features achieve asymptotically optimal error exponents up to a residual term.
Estimates curvature of network manifolds to understand community structure.
problem Understanding the geometry of network models to infer community structure.
method Develops hypothesis tests to determine manifold type, dimension, and curvature from noisy distance matrices.
result Consistently estimates manifold type, dimension, and curvature from Riemannian manifolds of constant curvature.
URerF learns geodesic distances in noisy manifolds.
problem Learning geodesic distances in noisy high-dimensional data.
method Unsupervised random forest (URerF) with Bayesian Information Criterion.
result URerF outperforms other methods in estimating geodesic distances on noisy data.
Unified framework for hyperbolic embeddings from mixed data types.
problem Computing hyperbolic embeddings from noisy metric and non-metric data.
method Semidefinite programming and spectral factorization methods.
result Efficient computation of hyperbolic embeddings from arbitrary data.
A new robust metric compares distributions more accurately than existing methods.
problem Sensitivity to outliers and sampling discrepancy in Wasserstein distances.
method Introducing k-RPW, a partial p-Wasserstein distance.
result k-RPW converges faster to true distance and is more robust to outliers.
We address noisy Euclidean distances in high dimensions, estimating noise levels and correcting distances.
problem Distorted pairwise Euclidean distances due to heteroskedastic noise.
method Developed a hyperparameter-free approach to jointly estimate noise magnitudes and correct distances.
result Our method provides accurate noise magnitude estimates and corrected distances in high-dimensional settings.
Proposes a method to compare noisy high-dimensional datasets with low-dimensional manifolds.
problem Comparing distributions on manifolds in noisy high-dimensional datasets.
method Linking low-rank structure to manifold geometry, developing a scale-invariant distance measure.
result Superior robustness and statistical power compared to existing methods.
Adaptive sampling theory has shown that, with proper assumptions on the signal class, algorithms exist to reconstruct a signal in Rd with an optimal number of samples. We generalize this problem to the case of spatial signals, where the sampling cost is a function of both the number of samples taken and t…
Improved PQM for pattern classification on quantum computers.
problem Pattern classification in quantum computing.
method Parametric Probabilistic Quantum Memory (PQM) with quantum circuit.
result Classical evaluation and quantum experiments validate PQM viability.
Reconstructing manifolds from partial distance and heat kernel data.
problem Reconstructing a manifold from noisy distance measurements and heat kernel data.
method Approximate reconstruction of a manifold from partial distance and heat kernel data with noise.
result A stable reconstruction of the manifold can be achieved from noisy heat kernel data.
IDA adapts to non-iid data in federated learning for medical imaging.
problem Statistical heterogeneity in federated learning data, especially in medical imaging.
method IDA (Inverse Distance Aggregation) is a novel adaptive weighting approach for clients based on meta-information.
result IDA outperforms Federated Averaging in handling unbalanced and non-iid data in federated learning.
Paper tackles NNS under uncertainty with improved algorithms.
problem Efficient nearest neighbor search with noisy distance estimates.
method Combines cover trees and multi-armed bandits for optimal performance.
result Optimal dependence on dataset size and unknown geometry achieved.
Motivation: Public and private repositories of experimental data are growing to sizes that require dedicated methods for finding relevant data. To improve on the state of the art of keyword searches from annotations, methods for content-based retrieval have been proposed. In the context of gene expression experiments, …
Classical multidimensional scaling is an important dimension reduction technique. Yet few theoretical results characterizing its statistical performance exist. This paper provides a theoretical framework for analyzing the quality of embedded samples produced by classical multidimensional scaling. This lays the foundati…
DW-KNN improves KNN by integrating distance and neighbor reliability for better prediction accuracy.
problem Standard KNN assumes all neighbors are equally reliable, leading to unreliable predictions in heterogeneous feature spaces.
method DW-KNN integrates exponential distance with neighbor validity, providing instance-level interpretability and reducing hyperparameter sensitivity.
result DW-KNN achieves 0.8988 average accuracy, ranks 2nd among six methods, and has the lowest cross-validation variance.
Many modern data-intensive computational problems either require, or benefit from distance or similarity data that adhere to a metric. The algorithms run faster or have better performance guarantees. Unfortunately, in real applications, the data are messy and values are noisy. The distances between the data points are …
Understanding and developing a correlation measure that can detect general dependencies is not only imperative to statistics and machine learning, but also crucial to general scientific discovery in the big data age. In this paper, we establish a new framework that generalizes distance correlation --- a correlation mea…