Algorithm solves two-sided matching markets with unknown preferences and constraints.
problem Two-sided online matching markets with complementary preferences and quota constraints.
method Formulated as a bandit learning problem, proposed MMTS algorithm combining Thompson Sampling and double matching.
result MMTS achieves stability and linear Bayesian regret with respect to quota and time horizon.
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.
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.
RFM improves CNFs by adding a boundary constraint term and matching velocity fields.
problem Flow matching on constrained domains leads to unnatural samples.
method RFM adds a boundary constraint term and matches velocity fields in a simulation-free manner.
result RFM achieves comparable or better results on standard image benchmarks and produces high-quality samples.
NeuroMatch efficiently matches subgraphs in large graphs using neural networks.
problem Determining the presence and location of a query graph in a large target graph.
method NeuroMatch decomposes graphs into subgraphs, embeds them using graph neural networks, and matches them directly in the embedding space.
result NeuroMatch is 100x faster and 18% more accurate than existing methods.
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.
New method for comparing curves with flexible matching constraints.
problem Comparing plane curves with general elastic metrics.
method Combining transform for elastic metrics with parametrization-invariant fidelity metrics.
result Simple optimization problem for discretized curves.
New approach to sparse optimal transport for matching tokens with experts.
problem Sparse matching of tokens with experts in neural networks.
method Sparsity-constrained optimal transport with cardinality constraints.
result Solves nonconvex cardinality constraints with gradient methods.
Efficiently learns matching rewards in two-sided markets with matrix completion.
problem Learning high-dimensional matching rewards in matching markets with limited data.
method Utilizes matrix completion with a novel approach to handle matching interference.
result Near-optimal guarantees for reward learning under matching interference.
Robust optimization is becoming increasingly important in machine learning applications. In this paper, we study a unified framework of robust submodular optimization. We study this problem both from a minimization and maximization perspective (previous work has only focused on variants of robust submodular maximizatio…
Partial Label Learning (PLL) aims to learn from the data where each training example is associated with a set of candidate labels, among which only one is correct. The key to deal with such problem is to disambiguate the candidate label sets and obtain the correct assignments between instances and their candidate label…
The paper models market dynamics using a limit order book system to explain slippage and inefficiency.
problem Inefficiency in matching markets due to structural liquidity constraints and slippage.
method Introduces a market microstructure framework with a latent preference state matrix and a dynamic discrete choice execution model.
result Persistent slippage and regional invariance of preference orderings are explained by liquidity thresholds.
Proposes a non-adversarial method for distribution matching.
problem Stability and optimization challenges in adversarial matching methods.
method Non-adversarial VAE-based matching method with alignment upper bounds.
result Demonstrates applicability of non-adversarial matching methods without modifying original architectures.
Level-set optimization formulations with data-driven constraints minimize a regularization functional subject to matching observations to a given error level. These formulations are widely used, particularly for matrix completion and sparsity promotion in data interpolation and denoising. The misfit level is typically …
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…
Study dynamic matching in heterogeneous networks using ODE model.
problem Dynamic matching in heterogeneous networks with compatibility restrictions.
method Introduced an ODE model to evaluate matching algorithms.
result Demonstrated trade-off between quick matching and optimal matching.
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…
Registration, which aims to find an optimal 1-1 correspondence between shapes, is an important process in different research areas. Conformal mappings have been widely used to obtain a diffeomorphism between shapes that minimizes angular distortion. Conformal registrations are beneficial since it preserves the local ge…
A new algorithm tackles submodular bandit problems with multiple constraints.
problem Addressing diversified retrieval and online learning with budget constraints.
method Non-greedy algorithm focusing on upper-confidence bounds.
result High-probability upper bound of an approximation regret matching fast offline algorithm's ratio.
We consider a non-stationary sequential stochastic optimization problem, in which the underlying cost functions change over time under a variation budget constraint. We propose an Lp,q-variation functional to quantify the change, which yields less variation for dynamic function sequences whose changes are constrai…
In urban environments, supply resources have to be constantly matched to the "right" locations (where customer demand is present) so as to improve quality of life. For instance, ambulances have to be matched to base stations regularly so as to reduce response time for emergency incidents in EMS (Emergency Management Sy…
Study develops a new method for creating fair models.
problem Ensuring equal outcomes for different protected groups.
method Introduces a new group-fair constraint based on transport maps.
result Develops a novel algorithm FTM for training group-fair models.
This paper tackles robust submodular minimization for image segmentation and correspondence.
problem Robust submodular minimization for image segmentation and correspondence.
method Constrained submodular minimization with scalable approximation algorithms for various combinatorial constraints.
result First work on robust submodular minimization under broad combinatorial constraints.
DALI improves inference for GANs by matching prior and conditional distributions.
problem Effective inference for generative adversarial models (GANs).
method Explicitly matches prior and conditional distributions in data and code spaces, constraining dependency structure.
result Significantly improves reconstruction and generation compared to other GAN inference models.
Unified framework for combinatorial and rounding algorithms in experimental design.
problem Designing and analyzing combinatorial and rounding algorithms for experimental design problems.
method Local search framework for combinatorial algorithms and regret minimization framework for rounding algorithms.
result Unified approach to match and improve all known results in D/A/E-design and obtain new results in unknown settings.
New framework improves generative models with prediction and consistency constraints.
problem Improving generative models with sparse labeled data.
method Optimizes variational autoencoders with prediction and consistency constraints.
result Promising image classification performance, especially in semi-supervised scenarios.
Paper tackles constrained bandit problems with a new learning framework.
problem Optimizing a black-box reward function subject to a black-box constraint function over a continuous space.
method Rectified Pessimistic-Optimistic Learning (RPOL) framework, incorporating optimistic and pessimistic GP bandit learning.
result RPOL achieves sublinear regret and minimal cumulative constraint violation.
Graph Energy Matching improves generation quality for molecular graphs.
problem Discrete energy-based models struggle with efficient and high-quality sampling for graph generation.
method Inspired by transport-map optimization, Graph Energy Matching learns a permutation-invariant potential energy to guide sampling.
result GEM matches or surpasses discrete diffusion baselines on molecular graph benchmarks.
New algorithm ensures fair matching in resource allocation.
problem Ensuring fairness in matching algorithms for scarce resources.
method Introduces a modified Sinkhorn algorithm and two relaxation strategies for group fairness in Optimal Transport.
result Demonstrates improved matching quality and fairness trade-off.
Embedding models for entities and relations are extremely useful for recovering missing facts in a knowledge base. Intuitively, a relation can be modeled by a matrix mapping entity vectors. However, relations reside on low dimension sub-manifolds in the parameter space of arbitrary matrices---for one reason, compositio…
This paper characterizes the equilibrium in a continuous time financial market populated by heterogeneous agents who differ in their rate of relative risk aversion and face convex portfolio constraints. The model is studied in an application to margin constraints and found to match real world observations about financi…
New method extracts joint and individual signals from multi-view data.
problem Extract joint and individual signals from multi-view data.
method Double-matched matrix decomposition with optimization and iterative algorithm.
result Superior signal estimation performance compared to single-matching methods.
Optimistic algorithm reduces regret and constraint violations in online convex optimization with adversarial constraints.
problem Online convex optimization with adversarial constraints.
method Improved algorithm using accurate predictions of loss and constraint functions.
result Improved bounds on regret and cumulative constraint violations.
In this paper, we study a certain class of online optimization problems, where the goal is to maximize a function that is not necessarily concave and satisfies the Diminishing Returns (DR) property under budget constraints. We analyze a primal-dual algorithm, called the Generalized Sequential algorithm, and we obtain t…
New bounds for learning near-optimal policies in CMDPs with constraints.
problem Optimizing policies in CMDPs with constraints.
method Model-based algorithm addressing relaxed and strict feasibility.
result Near-optimal sample complexity bounds for CMDPs.
The matching of multiple objects (e.g. shapes or images) is a fundamental problem in vision and graphics. In order to robustly handle ambiguities, noise and repetitive patterns in challenging real-world settings, it is essential to take geometric consistency between points into account. Computationally, the multi-match…
ACOL learns constraints from human preferences in driving simulations.
problem Learning constraints from human preferences in driving simulations.
method Adaptive Constraint Learning (ACOL) algorithm for constrained linear best-arm identification.
result ACOL's sample complexity matches worst-case lower bound and is significantly tighter in the average case.
Graph matching involves combinatorial optimization based on edge-to-edge affinity matrix, which can be generally formulated as Lawler's Quadratic Assignment Problem (QAP). This paper presents a QAP network directly learning with the affinity matrix (equivalently the association graph) whereby the matching problem is tr…
In standard reinforcement learning (RL), a learning agent seeks to optimize the overall reward. However, many key aspects of a desired behavior are more naturally expressed as constraints. For instance, the designer may want to limit the use of unsafe actions, increase the diversity of trajectories to enable exploratio…
AR-CSM models use derivatives of univariate log-conditionals to estimate joint distributions efficiently.
problem Scalability and stability issues in training autoregressive models.
method Parameterize joint distribution using derivatives of univariate log-conditionals and introduce Composite Score Matching (CSM) for efficient training.
result AR-CSM models are more scalable and stable compared to previous score matching algorithms.
Improves k-NN for monotonic data with robustness against noise.
problem Class noise in real-life data violates monotonic constraints in k-NN.
method Monotonic Fuzzy k-NN (MonFkNN) with new fuzzy membership calculation.
result Significant accuracy improvements and robustness against monotonic noise.
Optimization results are one method for understanding neural computation from Nature's perspective and for defining the physical limits on neuron-like engineering. Earlier work looks at individual properties or performance criteria and occasionally a combination of two, such as energy and information. Here we make use …
BAICS identifies best arm with fairness constraints on subpopulations.
problem Identify the best arm while ensuring fairness across subpopulations.
method Formulated and solved BAICS problem, analyzed complexity, designed algorithm.
result Algorithm's sample complexity matches theoretical lower bound.
This paper explores combinatorial optimization for problems of max-weight graph matching on multi-partite graphs, which arise in integrating multiple data sources. Entity resolution-the data integration problem of performing noisy joins on structured data-typically proceeds by first hashing each record into zero or mor…
Study best arm identification with safety constraints in bandit problems.
problem Real-world decision-making with safety constraints.
method Analyzed linear and monotonic reward and safety constraints, proposed algorithms.
result Guaranteed safe learning in both linear and general reward/safety constraint settings.
Unified framework for unlearning in diffusion models using KL divergence and likelihood constraints.
problem Removing undesirable data or concepts while preserving utility of pretrained models.
method Constrained optimization framework based on reverse and forward KL divergences, and likelihood constraints.
result Our KL-constrained approach achieves superior retention-unlearning tradeoffs compared to weight-based baselines.
New framework for distributed nonparametric estimation under slow communication.
problem Efficiently estimate nonparametric models across multiple nodes with limited communication.
method Developed a general framework for nonparametric estimation under communication constraints.
result Derived minimax lower and upper bounds for various models.
Study connects database alignment and planted matching using Gaussian features.
problem Identify matching between correlated user features in anonymized databases.
method Derived results for database alignment and planted matching, showing connections and thresholds.
result Performance thresholds for database alignment converge to planted matching when feature dimensionality is sufficiently high.