We show that for a metric space with an even number of points there is a 1-Lipschitz map to a tree-like space with the same matching number. This result gives the first basic version of an unoriented Kantorovich duality. The study of the duality gives a version of global calibrations for 1-chains with coefficients in $…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “matching number”
Proves curvature of conference graphs and finds local matchings.
problem Proving precise values of curvature in conference graphs.
method Combining parameter relations and combinatorial approach.
result Existence of local perfect matchings in broader classes of graphs.
Optimizes matching in weighted graphs with semi-bandit sampling.
problem Finding optimal pairings in weighted graphs with sequential sampling.
method Leverages rank-1 assumption on adjacency matrix to reduce sample complexity and regret.
result Achieves linear dependency in the number of vertices for sample complexity and regret.
Given a pair of graphs with the same number of vertices, the inexact graph matching problem consists in finding a correspondence between the vertices of these graphs that minimizes the total number of induced edge disagreements. We study this problem from a statistical framework in which one of the graphs is an errorfu…
This paper proves a Faber-Krahn inequality for trees with given matching number.
problem Proving a Faber-Krahn inequality for trees with specific properties.
method Characterization of trees with given matching number.
result The Faber-Krahn inequality holds for trees with given matching number.
A novel method relaxes binary constraints to non-negative spheres for multi-matching and clustering.
problem Optimization problems over binary matrices with injectivity constraints.
method Non-negative spherical relaxation followed by conditional power iteration.
result Automatic adjustment of the continuous parameter related to universe size.
Seeded Graph Matchingstat.ML
Given two graphs, the graph matching problem is to align the two vertex sets so as to minimize the number of adjacency disagreements between the two graphs. The seeded graph matching problem is the graph matching problem when we are first given a partial alignment that we are tasked with completing. In this paper, we m…
New research shows semantic data matching can degrade SSDL performance.
problem The limits of semantic data set matching in semi-supervised learning.
method Demonstrated through simulations and a new dissimilarity measure.
result Semantic data matching can degrade SSDL performance under non-IID data.
Comparing and aligning large datasets is a pervasive problem occurring across many different knowledge domains. We introduce and study MREC, a recursive decomposition algorithm for computing matchings between data sets. The basic idea is to partition the data, match the partitions, and then recursively match the points…
The strength of association between a pair of data vectors is represented by a nonnegative real number, called matching weight. For dimensionality reduction, we consider a linear transformation of data vectors, and define a matching error as the weighted sum of squared distances between transformed vectors with respect…
GOAT improves graph matching speed and accuracy using optimal transport.
problem Efficiently matching large graphs in various applications.
method Replaces linear assignment with optimal transport methods.
result GOAT provides improvements in speed and accuracy.
We study graph matching with correlated Gaussian features and find thresholds for exact recovery.
problem Graph matching with correlated Gaussian features.
method Information-theoretic thresholds and conditions for exact and almost exact recovery.
result Contextual information introduces a richer structure, with thresholds for exact and almost exact recovery no longer coinciding.
New methods improve tool-to-tool matching in semiconductor manufacturing.
problem Challenges in obtaining static configuration data and extending methods to heterogeneous equipment.
method Novel TTTM analysis pipelines hypothesizing higher variance and modes for mismatched equipment.
result Best univariate method achieves correlation coefficients >0.95 and >0.5 with variance and modes, respectively.
Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environmentscs.LG
New algorithm guarantees domain generalization with few environments.
problem Performing well on unseen environments with limited training data.
method Iterative feature matching algorithm with theoretical guarantees.
result Guaranteed domain generalization with logarithmic environments.
Adaptive allocation with constraints using Thompson sampling.
problem Choosing allocations repeatedly with unknown returns and constraints.
method Thompson sampling approach with finite-sample regret bound.
result Prior-independent bound on expected regret for exponential allocations.
Develops a framework for clustering and distribution matching with bandit feedback.
problem Clustering and distribution matching problems with limited feedback.
method General framework using -armed bandit model, Track-and-Stop method, and Frank--Wolfe algorithm.
result Average number of arm pulls matches lower bound, with asymptotic convergence to fundamental limit.
Branching Flows generates sequences of varying lengths using binary trees.
problem Generating sequences of unknown lengths or fixed elements.
method A generative modeling framework that evolves states over binary trees, controlling sequence length.
result Branching Flows can generate sequences of varying lengths and mix different types of state spaces.
Decentralized learning for matching markets with time-varying preferences.
problem Matching between competing agents and supply arms with time-varying preferences.
method Linear contextual bandit framework, learning algorithms to identify latent environment and stable matchings.
result Achieve instance-dependent logarithmic regret, applicable for large markets.
Improved graph matching algorithm robust to noise.
problem Finding a bijection between vertex sets of two graphs.
method Uses multistage signature vectors to match vertices.
result Recover matching exactly with high probability for .
SMRL uses score matching for efficient RL with exponential family models.
problem Efficient reinforcement learning with unknown transition models.
method Score matching for parameter estimation of exponential family models.
result Achieves online regret of .
Whitehead doubles have matching meridional rank and bridge number.
problem Determining the meridional rank of Whitehead doubles.
method Analyzing algebraically tame knots and their Whitehead doubles.
result Meridional rank and bridge number coincide for Whitehead doubles of prime knots.
Gaussian and bootstrap methods improve ATE estimator accuracy.
problem Improving the accuracy of Average Treatment Effect (ATE) estimators.
method Gaussian approximation and bootstrap procedures.
result Precise bounds on ATE estimator accuracy quantifying key parameters.
Normal distributions ensure asymptotic variance reduction in moment matching Monte Carlo.
problem Asymptotic variance reduction in general integration problems.
method Characterization of conditions for asymptotic variance reduction using normal distributions.
result Asymptotic variance reduction is guaranteed for normal distributions in moment matching Monte Carlo.
The literature about history matching is vast and despite the impressive number of methods proposed and the significant progresses reported in the last decade, conditioning reservoir models to dynamic data is still a challenging task. Ensemble-based methods are among the most successful and efficient techniques current…
The study examines how the number of noise samples affects diffusion models' performance.
problem Understanding the balance between generalization and memorization in diffusion models.
method Theoretical analysis and empirical experiments with Denoising Score Matching (DSM) using random features.
result Precise expressions for test and train errors under specific conditions reveal the mechanisms of generalization and memorization.
Generative model uses ODEs and RKHSs for measure matching.
problem Minimum divergence generative modeling and sampling.
method Diffeomorphic matching and image registration principles applied to ODEs and RKHSs.
result Theoretical error bounds and extensive numerical experiments demonstrate the method's properties and applicability.
The disbalance of Supply and Demand is typically considered as the driving force of the markets. However, the measurement or estimation of Supply and Demand at price different from the execution price is not possible even after the transaction. An approach in which Supply and Demand are always matched, but the rate $I=…
New algorithms reduce matching regret by limiting frequent updates.
problem Minimizing regret in stochastic matching with rare optimization updates.
method Batched algorithms that limit matching updates to Θ(log log T) rounds.
result Achieve a regret bound of \(\widetilde{\mathcal{O}}(\sqrt{T})\) with reduced computational cost.
A new method for training diffusion models using likelihood matching.
problem Training efficient and accurate diffusion models.
method Likelihood Matching approach, quasi-likelihood approximation, score and Hessian estimation.
result Consistent matching of first two transitional moments between diffusion steps.
Correctly detecting the semantic type of data columns is crucial for data science tasks such as automated data cleaning, schema matching, and data discovery. Existing data preparation and analysis systems rely on dictionary lookups and regular expression matching to detect semantic types. However, these matching-based …
When pre-processing observational data via matching, we seek to approximate each unit with maximally similar peers that had an alternative treatment status--essentially replicating a randomized block design. However, as one considers a growing number of continuous features, a curse of dimensionality applies making asym…
Paper studies flow on hyperbolic surfaces to match boundary lengths.
problem Matching boundary lengths of hyperbolic surfaces.
method Combinatorial Yamabe flow on hyperbolic bordered surfaces.
result Flow converges exponentially to a surface with equal boundary lengths.
Poly-view contrastive learning improves image representation learning.
problem Learning representations from multiple related views in image data.
method Developed new representation learning objectives for poly-view tasks using information maximization and sufficient statistics.
result Poly-view contrastive models trained for fewer epochs and with smaller batch sizes outperform models trained for more epochs and with larger batch sizes.
FMCIT accelerates CI tests for causal discovery, maintaining power and efficiency.
problem High computational complexity in CI tests limits practical applicability of causal discovery methods.
method Flow Matching-based Conditional Independence Test (FMCIT) that leverages flow matching for fast CI tests.
result FMCIT effectively controls type-I error and maintains high testing power under the alternative hypothesis.
The ratio of two probability densities can be used for solving various machine learning tasks such as covariate shift adaptation (importance sampling), outlier detection (likelihood-ratio test), and feature selection (mutual information). Recently, several methods of directly estimating the density ratio have been deve…
Learning representations for counterfactual inference from observational data is of high practical relevance for many domains, such as healthcare, public policy and economics. Counterfactual inference enables one to answer "What if...?" questions, such as "What would be the outcome if we gave this patient treatment $t_…
Despite recent advances, the remaining bottlenecks in deep generative models are necessity of extensive training and difficulties with generalization from small number of training examples. We develop a new generative model called Generative Matching Network which is inspired by the recently proposed matching networks …
We propose a novel application of the Simultaneous Orthogonal Matching Pursuit (S-OMP) procedure for sparsistant variable selection in ultra-high dimensional multi-task regression problems. Screening of variables, as introduced in \cite{fan08sis}, is an efficient and highly scalable way to remove many irrelevant variab…
Bayesian approach models match and non-match score distributions over continuous covariates.
problem Complex evaluation of model performance over continuous covariates in biometric verification.
method Generative model of score distributions, mixture models, local basis functions, Bayesian inference.
result Accurate and effective method for studying model performance over continuous covariates.
The problem of finding the vertex correspondence between two noisy graphs with different number of vertices where the smaller graph is still large has many applications in social networks, neuroscience, and computer vision. We propose a solution to this problem via a graph matching matched filter: centering and padding…
Prime Match protects client stock trades from market price manipulation.
problem Protecting client stock trades from market price manipulation.
method Prime Match uses a two-round secure linear comparison protocol to match orders without revealing information.
result Prime Match reduces market impact and maintains client privacy.
New model for shape graph registration with partial matching constraints.
problem Shape graph registration with topological inconsistencies and partial matching.
method Higher order invariant Sobolev metrics, varifolds, inexact variational formulation, SFISTA algorithm.
result Existence of minimizers for variational problem with TV regularization.
The paper tackles matching a desired mean in causal systems through shift interventions.
problem Matching a desired mean in causal systems.
method Defining Markov equivalence classes, proposing active learning strategies, deriving lower bounds.
result Proposed active learning strategies require fewer interventions than previous approaches, especially for certain graph classes.
We propose an online convex optimization algorithm (RescaledExp) that achieves optimal regret in the unconstrained setting without prior knowledge of any bounds on the loss functions. We prove a lower bound showing an exponential separation between the regret of existing algorithms that require a known bound on the los…
New MPNNs match 2-WL, faster distinguishing graphs.
problem Improving graph neural network expressiveness.
method Introducing -walk MPNNs and second-order GNNs.
result Walk MPNNs match 2-WL and can distinguish graphs faster.
Model-based reinforcement learning (MBRL) aims to learn a dynamic model to reduce the number of interactions with real-world environments. However, due to estimation error, rollouts in the learned model, especially those of long horizons, fail to match the ones in real-world environments. This mismatching has seriously…
We consider the use of the Joint Clustering and Matching (JCM) procedure for the supervised classification of a flow cytometric sample with respect to a number of predefined classes of such samples. The JCM procedure has been proposed as a method for the unsupervised classification of cells within a sample into a numbe…
The pair-matching problem appears in many applications where one wants to discover good matches between pairs of entities or individuals. Formally, the set of individuals is represented by the nodes of a graph where the edges, unobserved at first, represent the good matches. The algorithm queries pairs of nodes and obs…