Bayesian learning is often hampered by large computational expense. As a powerful generalization of popular belief propagation, expectation propagation (EP) efficiently approximates the exact Bayesian computation. Nevertheless, EP can be sensitive to outliers and suffer from divergence for difficult cases. To address t…
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,051 papers · 148 categories
Trend · papers per month
48 results for “Relaxed Matching Prediction”
Prediction suffix trees (PST) provide an effective tool for sequence modelling and prediction. Current prediction techniques for PSTs rely on exact matching between the suffix of the current sequence and the previously observed sequence. We present a provably correct algorithm for learning a PST with approximate suffix…
Proposes GM-PLL for better partial label learning.
problem Learning from data with partially labeled instances.
method Reformulates PLL as graph matching problem, incorporating GM scheme and extending matching algorithm.
result Superior performance compared to state-of-the-art methods.
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.
We propose a unified data-driven framework based on inverse optimal transport that can learn adaptive, nonlinear interaction cost function from noisy and incomplete empirical matching matrix and predict new matching in various matching contexts. We emphasize that the discrete optimal transport plays the role of a varia…
Study improves denoising score matching under relaxed manifold assumptions.
problem Improving denoising score matching under relaxed manifold assumptions.
method Model density with nonparametric Gaussian mixtures, relax manifold assumption, derive non-asymptotic bounds.
result Non-asymptotic bounds on approximation and generalization errors, rates of convergence determined by intrinsic dimension.
In applications such as recommendation systems and revenue management, it is important to predict preferences on items that have not been seen by a user or predict outcomes of comparisons among those that have never been compared. A popular discrete choice model of multinomial logit model captures the structure of the …
In this work we study convex relaxations of quadratic optimisation problems over permutation matrices. While existing semidefinite programming approaches can achieve remarkably tight relaxations, they have the strong disadvantage that they lift the original -dimensional variable to an -d…
Paper solves graph matching problem using convex relaxation to the simplex.
problem Finding the best alignment between two graphs.
method Introduces a new convex relaxation onto the unit simplex and uses mirror descent scheme.
result Shows exact recovery of ground truth permutation with high probability.
Graph matching---aligning a pair of graphs to minimize their edge disagreements---has received wide-spread attention from both theoretical and applied communities over the past several decades, including combinatorics, computer vision, and connectomics. Its attention can be partially attributed to its computational dif…
GRAMPA algorithm recovers latent vertex correspondence in correlated graphs with high probability.
problem Recovering latent vertex correspondence between unlabeled, edge-correlated weighted graphs.
method Spectral graph matching algorithm, GRAMPA, with exact recovery guarantees for Erdős-Rényi graphs.
result GRAMPA exactly recovers latent vertex correspondence with high probability for Erdős-Rényi graphs with edge correlation coefficient and average degree at least when .
Graphs provide an efficient tool for object representation in various computer vision applications. Once graph-based representations are constructed, an important question is how to compare graphs. This problem is often formulated as a graph matching problem where one seeks a mapping between vertices of two graphs whic…
Matching correlated VAR time series databases by recovering matching permutations.
problem Matching perturbed and permuted correlated VAR time series.
method Probabilistic framework modeling, maximum likelihood estimator (MLE), linear assignment, convex relaxations.
result Recovery guarantees for perfect or partial recovery of matching permutations, thresholds for .
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.
Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometrymath.OC
Quantized Stochastic Primal-Dual Methods for Distributed Optimization
problem Distributed optimization with stochastic gradients and finite-bit communication
method q-PDGD, a quantized stochastic primal-dual method
result Linear contraction to an explicit neighborhood under RSI, O(1/k) convergence under PL inequality
In this work we study permutation synchronisation for the challenging case of partial permutations, which plays an important role for the problem of matching multiple objects (e.g. images or shapes). The term synchronisation refers to the property that the set of pairwise matchings is cycle-consistent, i.e. in the full…
Unified framework for fair regression in aware and unaware settings.
problem Lack of principled methods for fair regression in unawareness settings.
method Formulated as an optimal transport problem, unifying aware and unaware settings.
result Characterizes optimal prediction functions via optimal transport maps under different penalties.
A new method for fair classification using characteristic function distance.
problem Fairness in high-stakes decision-making with sensitive groups.
method Proposes a novel approach based on characteristic function distance to ensure minimal sensitive information in learned representations.
result Consistently matches or achieves better fairness and predictive accuracy than existing methods.
The Gromov-Hausdorff distance provides a metric on the set of isometry classes of compact metric spaces. Unfortunately, computing this metric directly is believed to be computationally intractable. Motivated by applications in shape matching and point-cloud comparison, we study a semidefinite programming relaxation of …
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.
New calibration measure SCDL improves trust in AI predictions.
problem Improving trust in AI predictions by ensuring they are both actionable and testable.
method Introducing SCDL, a new calibration measure that is fully actionable and testable.
result SCDL is the first calibration measure that is fully actionable and testable.
Hidden Quantum Markov Models (HQMMs) can be thought of as quantum probabilistic graphical models that can model sequential data. We extend previous work on HQMMs with three contributions: (1) we show how classical hidden Markov models (HMMs) can be simulated on a quantum circuit, (2) we reformulate HQMMs by relaxing th…
Graph clustering method uses templates to match vertices and outperforms classical methods.
problem Graph clustering with additional structural information.
method Formulates graph clustering as template matching, using orthonormal matrices for embedding.
result Method outperforms classical methods, especially for challenging cases.
In this paper we study a class of Riemannian metrics on the space of unparametrized curves and develop a method to compute geodesics with given boundary conditions. It extends previous works on this topic in several important ways. The model and resulting matching algorithm integrate within one common setting both the …
We propose an SDP relaxation for the Gromov-Wasserstein distance, providing globally optimal solutions.
problem Matching objects between incomparable spaces using the Gromov-Wasserstein distance.
method Semi-definite programming (SDP) relaxation of the GW distance.
result The SDP relaxation provides globally optimal solutions for the GW distance in some instances.
Structured prediction is used in areas such as computer vision and natural language processing to predict structured outputs such as segmentations or parse trees. In these settings, prediction is performed by MAP inference or, equivalently, by solving an integer linear program. Because of the complex scoring functions …
Relaxing the I.I.D. Assumption: Adaptively Minimax Optimal Regret via Root-Entropic Regularizationstat.ML
Adapting Hedge algorithm for semi-adversarial data with root-entropy regularization.
problem Minimizing regret in prediction with expert advice under varying distributions.
method Follow-the-Regularized-Leader (FTRL) with root-entropy regularization.
result Adaptive minimax optimal regret across all levels of constraint sets.
Paper tackles distribution matching by partially matching distributions, achieving robust results.
problem Robustly aligning two probability distributions.
method Developed a partial Wasserstein adversarial network (PWAN) to efficiently approximate the partial Wasserstein-1 (PW) discrepancy.
result The PWAN effectively produces highly robust matching results, outperforming state-of-the-art methods.
A biclustering algorithm finds dense disjoint subgraphs in weighted bipartite graphs.
problem Finding dense disjoint bicliques in a weighted bipartite graph.
method Semidefinite programming-based branch-and-cut algorithm with upper and lower bounds.
result The algorithm can solve much larger instances than general-purpose solvers.
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 conditions ensure Dantzig-Wolfe relaxation matches rank-constrained optimization problems.
problem Rank-constrained optimization problems with linear matrix inequalities.
method Investigates Dantzig-Wolfe relaxation and develops conditions for exactness.
result Conditions for extreme point, convex hull, and objective exactness.
Renet: Principled and Efficient Relaxation for the Elastic Net via Dynamic Objective Selectionstat.ME
Renet improves Elastic Net by dynamically selecting between convex blending and refitting, enhancing prediction accuracy.
problem Elastic Net's shrinkage bias limits its prediction accuracy in high-dimensional settings.
method Adaptive relaxation procedure that dynamically dispatches between convex blending and efficient sub-path refitting.
result Renet consistently outperforms standard Elastic Net and Adaptive Elastic Net in high-dimensional, low signal-to-noise ratio, and high-multicollinearity scenarios.
We relax demographic parity in regression by enforcing parity at quantile levels and score thresholds.
problem Enforcing full distributional fairness in regression can lead to substantial accuracy loss.
method Introduce (, Z)-fair predictor, derive closed-form solutions, and develop post-processing algorithm.
result The risk gap to the continuous optimum vanishes as the grid is refined, and we enable targeted fairness corrections.
New method optimizes fairness in predictive models for continuous sensitive attributes.
problem Enforcing full statistical independence on continuous sensitive attributes is too restrictive.
method Functional bilevel optimization (FBO) and ITD algorithms.
result Achieves lowest or near-lowest fairness-accuracy regret on synthetic and real datasets.
A new GP interpolation method for better predictive distributions in ranges of interest.
problem Improving predictive distributions in specific ranges of interest.
method Relaxed Gaussian process interpolation, relaxing interpolation constraints outside ranges of interest.
result Better predictive distributions in ranges of interest, especially in non-stationary cases.
New method for fair regression using optimal transport.
problem Learning fair regression models under counterfactual fairness constraints.
method Causal uncertainty view, optimal transport, post-processing method.
result High-probability fairness guarantees with decay.
A new method for efficient causal structure learning at scale.
problem Causal structure learning is computationally challenging at scale.
method Relaxed sparsest-permutation formulation with support-level relaxation and masked zero-fill incomplete Cholesky factorization.
result The method enables scalable comparison of candidate orderings and matches the accuracy of slower baselines.
New method improves robust point matching under probabilistic settings.
problem Insufficient theoretical understanding of existing point matching methods.
method Distance profiles and modified matching procedure.
result Improved robustness under probabilistic settings.
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.
LP-SparseMAP relaxes SparseMAP for more complex structures.
problem SparseMAP's tractable MAP inference oracle limits its applicability.
method Local polytope relaxation for factor graphs.
result LP-SparseMAP outperforms SparseMAP and Structured SVM in structured prediction tasks.
New approach for fair predictions under changing data distributions.
problem Fairness in classification algorithms under covariate shift.
method Proposes a robust predictor that satisfies fairness and maintains statistical properties of source data.
result Demonstrates improved fairness and target performance on benchmark tasks.
The paper examines the optimality of kernel methods in high-dimensional clustering.
problem Understanding the optimality of kernel methods in high-dimensional data clustering.
method High-dimensional Gaussian clustering, exponential kernel function, kernel k-means, semi-definite relaxation.
result The exponential kernel function optimally recovers clusters in high-dimensional data, matching information-theoretic limits up to a factor of √2.
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.
Statistical framework for inexact graph matching with errorfully observed graphs.
problem Finding a correspondence between graphs with errors.
method Introducing a corrupting channel model and using maximum likelihood estimation.
result Maximum likelihood estimation is a solution to the inexact graph matching problem.
Random forest model predicts tennis match outcomes with 80% accuracy.
problem Predicting tennis match outcomes before the game starts.
method Used a large database of tennis match information and a random forest model.
result Identified serve strength as a key predictor of match outcome.
New algorithms achieve better regret bounds for online classification with relaxed benchmarks.
problem Competing with worst-case optimal binary loss in online classification.
method Comparing against predictors robust to small input perturbations, performing well under Gaussian smoothing, or maintaining a prescribed output margin.
result Regret guarantees depend only on VC dimension and instance space complexity, with an dependence on the generalized margin.
The study revisits portfolio diversification by relaxing assumptions for skewed, multi-regime, and leptokurtic asset returns.
problem Underestimation of risk in portfolio diversification due to assumptions that are inconsistent with real-world asset returns.
method Calibrated a Markov-modulated Levy process model to equity market data to demonstrate the merits of the approach.
result The calibrated models effectively match empirical moments and show the importance of relaxing assumptions in portfolio diversification.
The paper relaxes constraints on predictive coding models, making them more biologically plausible.
problem Neurophysiological models of predictive coding are not fully biologically plausible.
method The paper relaxes constraints on standard predictive coding algorithms by removing neurally implausible features.
result The removal of neurally implausible features does not significantly affect learning performance.