In this paper, we introduce a novel, non-recursive, maximal matching algorithm for double auctions, which aims to maximize the amount of commodities to be traded. It differs from the usual equilibrium matching, which clears a market at the equilibrium price. We compare the two algorithms through experimental analyses, …
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.
169,291 papers · 148 categories
Trend · papers per month
48 results for “maximal matching”
Submodular functions have many applications. Matchings have many applications. The bitext word alignment problem can be modeled as the problem of maximizing a nonnegative, monotone, submodular function constrained to matchings in a complete bipartite graph where each vertex corresponds to a word in the two input senten…
A new online learning problem, CAB, tackles matching platforms to maximize user satisfaction.
problem Maximizing matches in a matching platform can lead to dissatisfaction and churn.
method Developed CAB, an online learning problem that maximizes arm satisfaction, and analyzed algorithms like UCB and Thompson sampling.
result CAB-UCB achieves higher cumulative satisfaction than baselines in experiments.
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=…
Improves EM algorithm for better local optima in mixture models.
problem EM algorithm's sensitivity to initialization and bad local optima.
method Big Learning principle applied to upgrade EM algorithm.
result BigLearn-EM delivers optimal solution with high probability.
Unified framework for self-supervised learning via latent distribution matching.
problem Lack of a unifying theoretical framework for diverse SSL methods.
method Casting SSL as latent distribution matching (LDM): maximizing alignment and uniformity.
result Derives a Bayesian filtering model and proves identifiable latent representations.
Paper develops a classification method using matrix-variate t-distributions.
problem Classifying matrix-valued observations with dependence structure.
method Develops an Expectation-Maximization algorithm for discriminant analysis.
result Method shows promise on various datasets.
Directly estimates Fisher score for likelihood maximization.
problem Intractable likelihood functions with model simulations.
method Gradient-based optimization using local score matching and linear parameterization.
result Efficient approximation of Fisher score improves likelihood maximization.
Unified framework for robust submodular optimization with various constraints.
problem Robust optimization in machine learning applications.
method Unified framework for minimization and maximization under combinatorial constraints.
result Scalable approximation algorithms for various submodular optimization problems.
Algorithm uses RBM to solve matching problems on weighted graphs.
problem Perfect matching problem on bipartite weighted graphs.
method Iterative RBM algorithm to maximize energy function and assignment.
result Algorithm successfully solves real-world matching problems.
New maximal acyclic matchings prove minimality of hyperplane arrangements.
problem Proving the minimality of hyperplane arrangements.
method Constructing maximal acyclic matchings on Salvetti complexes and applying discrete Morse theory.
result Explicit proof of minimality for hyperplane arrangements.
Optimizes long-term social welfare in recommender systems by matching users to providers.
problem Realistic recommender systems dynamics affect all agents, not just users.
method Formulated as an optimal constrained matching problem, solved using dynamical system equilibrium selection.
result Ensures maximal social welfare with diverse viable providers, improving over myopic matching.
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.
We consider the problem faced by a service platform that needs to match limited supply with demand but also to learn the attributes of new users in order to match them better in the future. We introduce a benchmark model with heterogeneous "workers" (demand) and a limited supply of "jobs" that arrive over time. Job typ…
This paper develops a learning framework for optimal strategies in multi-stage decentralized matching markets.
problem Optimal strategies in multi-stage decentralized matching markets with uncertain preferences.
method Nonparametric statistical approach and variational analysis.
result Participants can be better off with multi-stage matching compared to single-stage matching.
We formalize and verify double auctions for multiple-quantity trades.
problem Matching multiple-quantity trade requests in double auctions.
method Formalized algorithms, correctness proofs, Coq proof assistant, verified OCaml and Haskell programs.
result Automatic detection of violations in exchange systems.
Improved EM algorithm for faster convergence of mixture models.
problem Slow or invalid convergence of EM algorithm for mixture models.
method CM-EM algorithm with a step to optimize mixture ratios and maximize G.
result Global convergence proof for CM-EM algorithm using variational methods.
Partial soft-matching distance improves neural representation comparison by allowing some neurons to remain unmatched.
problem Neural representations are noisy and contain outliers, making traditional matching methods unreliable.
method Extends soft-matching distance to a partial optimal transport setting, allowing some neurons to remain unmatched.
result Partial soft-matching provides robust correspondences that are more reliable under noise and outliers.
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 .
Maximum Likelihood Training for Score-Based Diffusion ODEs by High-Order Denoising Score Matchingstat.ML
This work improves likelihood of score-based diffusion ODEs using high-order denoising score matching.
problem The gap between maximum likelihood and score matching objectives for score-based diffusion ODEs.
method High-order denoising score matching to maximize likelihood.
result Score-based diffusion ODEs achieve better likelihood on synthetic and CIFAR-10 data.
Improved VQ-VAE training technique enhances image generation and machine translation.
problem Training discrete latent variable models remains challenging and underperforms continuous counterparts.
method Alternate training technique inspired by Expectation Maximization (EM) algorithm.
result Improved image generation results on CIFAR-10 and non-autoregressive machine translation model.
An algorithm finds a compact Hankel submatrix for spectral learning.
problem Efficiently computing SVD for large Hankel matrices in spectral learning.
method Maximal bipartite matching algorithm to select rows and columns of Hankel matrix.
result Compact Hankel submatrix with full structural rank.
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.
Maximize revenue by guiding individuals to optimal locations anonymously.
problem Matching supply and demand in online to offline services efficiently.
method Employing maximum entropy principle for independent learning with local aggregated information.
result Significant improvement in joint and individual revenue with fairness.
Paper proposes MMI-ALI for scalable joint distribution matching across multiple domains.
problem Scalability issue in matching joint distributions across multiple domains.
method Adversarial training with Multivariate Mutual Information maximization.
result MMI-ALI achieves scalable joint distribution matching across multiple domains.
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.
Paper analyzes an algorithm for maximizing non-concave functions with budget constraints.
problem Maximizing non-concave functions with budget constraints under DR-submodularity.
method Generalized Sequential algorithm for online monotone DR-submodular function maximization.
result First competitive ratio bound matches known tight bound for linear objective functions.
New methods improve matching in high-dimensional data.
problem Matching in high-dimensional data is challenging due to the curse of dimensionality.
method Pseudo-metric learning approach using MLPs or siamese neural networks.
result Neural-net-based methods outperform traditional matching methods in simulations and real data.
Unsupervised ensemble classification for dependent data.
problem Classifying data with dependencies using multiple classifiers.
method Developed algorithms for sequential and networked data dependencies, using moment matching and Expectation Maximization.
result Improved classification performance on synthetic and real datasets.
Sensitivity analysis of the utility maximization problem with respect to model perturbationsq-fin.PM
Study sensitivity of utility maximization to market changes.
problem Sensitivity of utility maximization to market price of risk changes.
method Obtained second-order expansion of value function, first-order terminal wealth approximation, constructed trading strategies, reduced approximation to Kunita-Watanabe decomposition.
result Reduced sensitivity analysis to a Kunita-Watanabe decomposition.
New method for matching bipartite and unipartite graphs without collapsing.
problem Matching between bipartite and unipartite networks without losing information.
method Formulated as an undirected graphical model, aligns graphs without collapsing.
result Consistent method with conditions for exact recovery of matching solution.
Models predict soccer match outcomes with similar accuracy.
problem Predicting soccer match outcomes (win, draw, loss).
method Compared Bradley-Terry extensions and hierarchical Poisson log-linear model. Parameters estimated using log-likelihood or integrated nested Laplace approximations. Predictive performance assessed using temporal validation.
result Bradley-Terry extensions and hierarchical Poisson log-linear model perform similarly in predicting match outcomes.
Paper refutes EM convergence theory and introduces a new EM algorithm.
problem The convergence theory of the EM algorithm is incorrect and affects its performance.
method Proposes a new EM algorithm called the Channel Matching (CM) EM algorithm and provides an initialization map.
result The locally maximal Q can affect the convergent speed but not the global convergence.
Transforming sparse outcomes into dense process rewards for efficient reinforcement learning.
problem Training RL policies to maximize sparse outcomes.
method Incentivizing policy matching state-action visitations of successful episodes.
result Significantly faster RL finetuning performance.
Seeded graph matching for the correlated Gaussian Wigner model via the projected power methodmath.ST
PPM improves graph matching for correlated Gaussian Wigner models with high probability.
problem Graph matching in the Correlated Gaussian Wigner model with edge correlations.
method Seeded projected power method (PPM) for iterative improvement of initial partial matches.
result PPM recovers ground-truth matching with high probability in O(log n) iterations if seed is close enough.
The goal of cross-domain object matching (CDOM) is to find correspondence between two sets of objects in different domains in an unsupervised way. Photo album summarization is a typical application of CDOM, where photos are automatically aligned into a designed frame expressed in the Cartesian coordinate system. CDOM i…
Enhances DIM to match learned representations to a specific distribution.
problem Learning representations conforming to a specific distribution.
method Injecting noise into normalized outputs of the encoder while keeping the InfoMax training objective.
result Learning uniformly and normally distributed representations, as well as representations of other absolutely continuous distributions.
The spectrum of certain manifolds matches that of hyperbolic space if the bottom spectrum is maximal.
problem Investigating spectral rigidity of manifolds with Ricci bounded below and maximal bottom spectrum.
method Analyzing the spectrum of the Laplacian on manifolds with specific Ricci curvature bounds.
result The spectrum of the manifold coincides with that of hyperbolic space if the bottom spectrum is maximal.
Gradient matching method improves domain generalization across various datasets.
problem Machine learning's inability to generalize to unseen domains.
method Inter-domain gradient matching objective and first-order algorithm Fish.
result Fish method produces competitive results and surpasses baselines on 4 datasets.
Proposes a new RL method to fine-tune flow-based models with arbitrary rewards.
problem Challenges in fine-tuning continuous flow-based generative models with arbitrary reward functions.
method Online Reward-Weighted Conditional Flow Matching with Wasserstein-2 Regularization (ORW-CFM-W2)
result Achieves optimal policy convergence with controllable trade-offs between reward maximization and diversity preservation.
Bayesian rating system for large competitions improves prediction and efficiency.
problem Rating systems for large, competitive events like online programming contests.
method Developed a Bayesian rating system for many participants, proving robustness and runtime.
result The system outperforms existing systems in accuracy and computation speed.
The Gaussian mixture model is a classic technique for clustering and data modeling that is used in numerous applications. With the rise of big data, there is a need for parameter estimation techniques that can handle streaming data and distribute the computation over several processors. While online variants of the Exp…
Linear Stochastic Dividend Modelq-fin.MF
Proposes a new model for stock and dividend derivatives pricing.
problem Pricing stock and dividend derivatives with positive stock prices and non-negative dividends.
method Jointly specifies dynamics for stock price and dividend rate, using mean-reverting dividend rate.
result Closed-form expressions for stock and dividend futures prices, accurate option approximations.
A new algorithm for streaming submodular maximization with memory constraints.
problem Maximizing a submodular function in a stream with memory removal.
method STAR-T algorithm based on partitioning and thresholding.
result A simple greedy algorithm achieves constant-factor approximation after memory removal.
DIM learns deep representations by maximizing mutual information, outperforming unsupervised methods.
problem Learning useful representations from unlabeled data.
method Maximizing mutual information between input and output of a deep neural network encoder, incorporating prior knowledge.
result DIM outperforms other unsupervised learning methods and competes with fully-supervised learning on classification tasks.
A novel 3D shape registration method using spectral graph embedding and probabilistic matching.
problem Challenges in 3D shape analysis and registration, especially with large variability.
method Combining spectral graph matching with Laplacian embedding for large graphs, using commute-time embedding and PCA.
result A method to register shapes with different samplings and isometric deformations.
Novel alignment framework for text-to-image generation using diffusion models and flow matching.
problem Improving text-to-image generation with minimal computational resources.
method Proposes a novel alignment framework that decomposes the score function into pre-trained score plus a conditional expectation of the reward.
result Achieves comparable performance to finetuning-based models with reduced computational cost.
GRAMPA spectral method solves graph matching problem with high probability.
problem Finding vertex correspondence between unlabeled graphs.
method GRAMPA constructs a similarity matrix from weighted eigenvector comparisons, rounding to produce a matching.
result GRAMPA exactly recovers correct vertex correspondence with high probability for Gaussian models.