Study asset price bubbles using random matching and stochastic factors.
problem Understanding and modeling asset price bubbles through investor contagion.
method Developed a stochastic model of liquidity-based asset price bubbles using random matching mechanism.
result Derived conditions for arbitrage-free financial market models.
Efficiently matches random graphs with inhomogeneous edge probabilities.
problem Matching latent vertex correspondence between two correlated random graphs with inhomogeneous edge probabilities.
method Inspired by Ding et al. (2021), an efficient matching algorithm is developed with conditions on minimal average degree and minimal correlation.
result An efficient matching algorithm is obtained as long as the minimal average degree is at least Ω(log2n) and the minimal correlation is at least 1−O(log−2n). Polynomial-time algorithm matches correlated random graphs with non-vanishing correlation.
problem Matching correlated random graphs with non-vanishing edge correlation.
method Iterative algorithm for polynomial-time recovery of latent matching.
result Algorithm succeeds in recovering latent matching as long as edge correlation is non-vanishing.
Paper introduces new approximations for lognormal sums, matching comonotonicity and moments.
problem Approximating sums of lognormal random variables accurately.
method Introduces new approximations based on weighted distribution theory, emphasizing comonotonicity and moment matching.
result Approximations perform better than classical methods, especially in the right tail of the distribution.
We present an alternate formulation of the partial assignment problem as matching random clique complexes, that are higher-order analogues of random graphs, designed to provide a set of invariants that better detect higher-order structure. The proposed method creates random clique adjacency matrices for each k-skeleton…
The supplement proves the existence and properties of a dynamical system related to asset price bubbles.
problem Modeling asset price bubbles using liquidity and random matching.
method Proves the existence and properties of a dynamical system D.
result Existence and properties of the dynamical system D are proven.
The paper addresses statistical inference in matching markets with dependent missingness.
problem Statistical inference for two-sided matching markets with matching-induced dependence.
method Non-convex algorithm based on Grassmannian gradient descent, debiasing and projection framework.
result Near-optimal entrywise convergence rates for various matching mechanisms.
Generative model uses random convolutional features to create financial time series.
problem Generating realistic financial time series with limited data and avoiding overfitting.
method Train generators by matching random convolutional features of real and generated time series, using SOCK (SOft Competing Kernels) feature map.
result Generators trained with random SOCK features outperform baselines across various financial datasets.
Paper tackles robust graph matching in dense graphs with AMP type algorithm.
problem Matching recovery between correlated Gaussian Wigner matrices with adversarial perturbations.
method Approximate Message Passing (AMP) type iterative algorithm with time-dependent matrix multiplication.
result Algorithm succeeds in polynomial time for non-vanishing correlation and small perturbations.
Map matching of the GPS trajectory serves the purpose of recovering the original route on a road network from a sequence of noisy GPS observations. It is a fundamental technique to many Location Based Services. However, map matching of a low sampling rate on urban road network is still a challenging task. In this paper…
A faster method for density estimation using denoising score matching with random Fourier features.
problem Intractability of normalizing constant in density estimation.
method Denoising Score Matching with Random Fourier Features.
result The method is computationally faster and scalable to complex high-dimensional data.
Graph matching in noisy environments with Markovian errors.
problem Graph matching under time-dependent Markovian noise.
method Introduced edgelighter error model and analyzed graph matching thresholds.
result Graph matching thresholds and mixing times are of order Θ(n2logn) for Erdős-Rényi graphs, and O(nαlogn) for Stochastic Block Model graphs. Efficiently matches subgraphs in noisy data without node labels.
problem Subgraph isomorphism in noisy, real-valued graphs.
method Two-step approach: extract topology, then expand matches.
result Realistically sub-linear computational efficiency, robustness to noise.
We present a parallelized bijective graph matching algorithm that leverages seeds and is designed to match very large graphs. Our algorithm combines spectral graph embedding with existing state-of-the-art seeded graph matching procedures. We justify our approach by proving that modestly correlated, large stochastic blo…
OmniMatch algorithm perfectly matches graphs without edge correlation.
problem Graph matching in the absence of edge correlation.
method OmniMatch algorithm for seeded multiple graph matching.
result OmniMatch aligns O(sα) unseeded vertices across multiple networks efficiently and perfectly. This paper tackles matching two complete graphs with correlated edge weights in geometric models.
problem Matching two complete graphs with edge weights correlated through latent geometries.
method Derives an approximate maximum likelihood estimator for recovering hidden vertex correspondence.
result The estimator provably achieves perfect recovery under certain noise conditions.
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…
HTFM improves mode coverage and tail-statistic recovery for heavy-tailed data.
problem Tackles heavy-tailed data in various domains with rare events.
method Proposes a framework using clock-conditioned Gaussian sources and truncated logsignature features.
result Improves mode coverage, sample quality, and tail-statistic recovery over Gaussian flow matching and baselines.
Study sharpens threshold for matching correlated graphs without labels.
problem Matching latent vertex correspondences in correlated random graphs.
method Analyzes information-theoretic limits for correct vertex matching in sub-sampled graphs.
result Establishes a sharp information-theoretic threshold for vertex matching recovery.
In this work we study the degree distribution, the maximum vertex and edge flow in non-uniform random Delaunay triangulations when geodesic routing is used. We also investigate the vertex and edge flow in Erdös-Renyi random graphs, geometric random graphs, expanders and random k-regular graphs. Moreover we show that …
A new model combines diffusion and random features for better interpretability and comparable performance.
problem Lack of theoretical justification and computational expense in diffusion models, and limited interpretability in random feature models.
method Developed a deep random feature model inspired by diffusion models, derived generalization bounds using score matching.
result The model achieves comparable performance to fully connected neural networks and provides theoretical generalization bounds.
Graph matching with feature vectors is solved using a two-layer graph neural network.
problem Graph matching in the presence of sparse binary features.
method Two-layer graph neural network with graph structure.
result Graph neural network can recover correct mapping with high probability under certain conditions.
Study on matching nodes between graphs to preserve edges, focusing on limits and algorithms.
problem Matching nodes between graphs to preserve most edges, especially in random graphs.
method Investigates fundamental limits and designs algorithms to recover alignments in planted graphs.
result High probability guarantees on the success or failure of graph alignment algorithms.
A single slow-growing tree matches Random Forest's performance.
problem Matching Random Forest's performance with a single tree.
method SGT uses a learning rate to tame CART's greedy algorithm, improving on greedy ML algorithms.
result SGT and tree ensembles like Booging, BT, and RF improve performance.
Completely random measures (CRM) represent the key building block of a wide variety of popular stochastic models and play a pivotal role in modern Bayesian Nonparametrics. A popular representation of CRMs as a random series with decreasing jumps is due to Ferguson and Klass (1972). This can immediately be turned into a…
New matrix ensembles better match deep neural network spectral densities.
problem Theoretical spectral density models for deep networks do not match empirical observations.
method Introduced new matrix ensemble classes to better fit observed spectral densities.
result Theoretical models for deep networks are significantly flawed.
This paper resolves the all-or-nothing phase transition in graph matching.
problem Recovering vertex correspondence between edge-correlated random graphs.
method Analysis of mutual information, truncated second-moment computation, and maximum likelihood estimator.
result Sharp thresholds for correct matching in both dense and sparse graphs.
Study efficient iterative method for distribution matching using sliced optimal transport.
problem Efficiently match distributions using sliced optimal transport.
method Slice-matching scheme based on sliced optimal transport, with quantitative non-asymptotic rates derived.
result Derive quantitative non-asymptotic rates for convergence to target distribution.
Map matching of GPS trajectories from a sequence of noisy observations serves the purpose of recovering the original routes in a road network. In this work in progress, we attempt to share our experience of feature construction in a spatial database by reporting our ongoing experiment of feature extrac-tion in Conditio…
A new measure k-variance captures local distributional shape.
problem Summarizing distributional shape with local information.
method Random bipartite matchings and stochastic approximation.
result Easily approximated k-variance measures capture local distributional properties. New method improves matrix completion accuracy, especially in noisy data.
problem Noisy matrix completion in recommendation systems and signal processing.
method Residual Spectral Matching criterion and pseudo-gradient algorithms.
result Improved numerical performance in noisy data environments.
Score matching is a popular method for estimating unnormalized statistical models. However, it has been so far limited to simple, shallow models or low-dimensional data, due to the difficulty of computing the Hessian of log-density functions. We show this difficulty can be mitigated by projecting the scores onto random…
On compact surfaces, a Green-Wasserstein inequality cannot be improved without the sqrt(log n) factor.
problem Can the Green-Wasserstein inequality be improved without the sqrt(log n) factor?
method Contradiction proof using second-moment estimates and semi-discrete random matching asymptotics.
result It is impossible to remove the sqrt(log n) factor in the inequality on any compact connected surface.
Paper shows faster core identification in matching markets.
problem Core Identification Problem in one-sided matching markets.
method Randomized SVD on preference-derived Markov matrix.
result CIP solved in O(Ln) time, matching lower bound.
New lower bounds for gradient methods in strongly convex finite-sum optimization.
problem Developing tight lower bounds for randomized gradient methods in finite-sum optimization.
method Deriving tight lower complexity bounds for SAG, SAGA, SVRG, SARAH, and related methods.
result Tight matches between lower bounds and upper bounds for various methods under specific conditions.
New framework minimizes interference and selection bias in network A/B testing.
problem Interference and selection bias in network A/B testing.
method Proposes a principled framework that jointly minimizes interference and selection bias using edge spillover probability and cluster matching.
result Significantly lower error in causal effect estimation compared to existing solutions.
Two popular examples of first-order optimization methods over linear spaces are coordinate descent and matching pursuit algorithms, with their randomized variants. While the former targets the optimization by moving along coordinates, the latter considers a generalized notion of directions. Exploiting the connection be…
New method designs fairer transport plans with uncertainty.
problem Designing fair and balanced mass transport plans.
method Hierarchical fully probabilistic design (HFPD) for transport plans.
result Optimal hyperprior for transport plans with uncertain marginals.
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.
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 α≤1/(loglogn)C. GMMNs model cross-sectional dependence for better option pricing and simulation.
problem Modeling cross-sectional dependence between stochastic processes.
method Generative moment matching networks (GMMNs) for geometric Brownian motions and ARMA-GARCH models.
result GMMNs produce dependent quasi-random samples with variance reduction.
Study finds Calabi-Yau models' operator spectra match random matrix theory.
problem Understanding spectra of Calabi-Yau sigma models.
method Numerical methods for Ricci-flat metrics, averaging over complex structure moduli space.
result Spectrum matches Gaussian orthogonal ensemble of random matrix theory.
New inequalities for unbounded functions improve denoising score matching.
problem Statistical error bounds for denoising score matching with unbounded objective functions.
method Derive new concentration inequalities using McDiarmid's inequality and Rademacher complexity bounds.
result Improved statistical error bounds for denoising score matching.
Generative models learn latent process to match target distributions.
problem Training flow-matching models with auxiliary stochastic dynamics.
method Introduces latent process generator matching, treating generative state as a deterministic image of a Markov process.
result Learn generator of a stochastic process with same marginal distributions.
Greedy algorithm performs well in online matching despite non-i.i.d. connections.
problem Online matching in sparse random graphs with fixed degree distributions.
method Approximating stochastic processes with partial differential equations.
result GREEDY algorithm can outperform RANKING in certain configurations.
Study shows how diffusion models learn on low-dimensional manifolds.
problem Learning efficiency of diffusion models on manifolds.
method Analyzes denoising score matching with random feature neural networks.
result Sample complexity scales linearly with intrinsic dimension, not ambient dimension.
Tennis is a popular sport worldwide, boasting millions of fans and numerous national and international tournaments. Like many sports, tennis has benefitted from the popularity of rigorous record-keeping of game and player information, as well as the growth of machine learning methods for use in sports analytics. Of par…
We show that the Bregman divergence provides a rich framework to estimate unnormalized statistical models for continuous or discrete random variables, that is, models which do not integrate or sum to one, respectively. We prove that recent estimation methods such as noise-contrastive estimation, ratio matching, and sco…