Given a triangulated region in the complex plane, a discrete vector field assigns a vector to every vertex. We call such a vector field holomorphic if it defines an infinitesimal deformation of the triangulation that preserves length cross ratios. We show that each holomorphic vector field can b…
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,742 papers · 148 categories
Trend · papers per month
48 results for “Quadratic assignment”
The Heights Theorem is extended to all Riemann surfaces with a first kind fundamental group.
problem Establishing the Heights Theorem for all Riemann surfaces.
method Extending the theorem to all surfaces with a first kind fundamental group, using measured laminations and straightening horizontal trajectories.
result The horizontal map is injective for arbitrary Riemann surfaces with a conformal hyperbolic metric.
A new method for few-shot learning using Laplacian regularization.
problem Few-shot learning with limited labeled data.
method Transductive Laplacian-regularized inference for feature embeddings.
result Our method outperforms state-of-the-art methods across various benchmarks.
Globally solving the Gromov-Wasserstein problem for point clouds in low dimensional Euclidean spacesmath.OC
Paper solves Gromov-Wasserstein for point clouds efficiently.
problem Quantifying similarity between two formations or shapes.
method Reformulates QAP as low-rank concave quadratic optimization problem.
result Global solution for large-scale problems with thousands of points.
We consider the problem of learning soft assignments of items to categories given two sources of information: an item-category similarity matrix, which encourages items to be assigned to categories they are similar to (and to not be assigned to categories they are dissimilar to), and an item-item similarity mat…
We investigate classification results for general quadratic functions on torsion abelian groups. Unlike the previously studied situations, general quadratic functions are allowed to be inhomogeneous or degenerate. We study the discriminant construction which assigns, to an integral lattice with a distinguished characte…
Graph matching aims at finding the vertex correspondence between two unlabeled graphs that maximizes the total edge weight correlation. This amounts to solving a computationally intractable quadratic assignment problem. In this paper we propose a new spectral method, GRAph Matching by Pairwise eigen-Alignments (GRAMPA)…
Inverse problems correspond to a certain type of optimization problems formulated over appropriate input distributions. Recently, there has been a growing interest in understanding the computational hardness of these optimization problems, not only in the worst case, but in an average-complexity sense under this same i…
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…
Given a triangulation of a closed surface, we consider a cross ratio system that assigns a complex number to every edge satisfying certain polynomial equations per vertex. Every cross ratio system induces a complex projective structure together with a circle pattern on the closed surface. In particular, there is an ass…
Kernels of Mallows Models under the Hamming Distance for solving the Quadratic Assignment Problemstat.ML
The Quadratic Assignment Problem (QAP) is a well-known permutation-based combinatorial optimization problem with real applications in industrial and logistics environments. Motivated by the challenge that this NP-hard problem represents, it has captured the attention of the optimization community for decades. As a resu…
In addition to finding meaningful clusters, centroid-based clustering algorithms such as K-means or mean-shift should ideally find centroids that are valid patterns in the input space, representative of data in their cluster. This is challenging with data having a nonconvex or manifold structure, as with images or text…
We analyze a new spectral graph matching algorithm, GRAph Matching by Pairwise eigen-Alignments (GRAMPA), for recovering the latent vertex correspondence between two unlabeled, edge-correlated weighted graphs. Extending the exact recovery guarantees established in the companion paper for Gaussian weights, in this work,…
The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differencescs.IT
Various applications involve assigning discrete label values to a collection of objects based on some pairwise noisy data. Due to the discrete---and hence nonconvex---structure of the problem, computing the optimal assignment (e.g.~maximum likelihood assignment) becomes intractable at first sight. This paper makes prog…
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 alignment problem solved with convex relaxations for correlated matrices.
problem Recovering hidden vertex permutations from correlated Gaussian matrices.
method Convex relaxations of the quadratic assignment problem over doubly stochastic matrices.
result The solution of the convex relaxation concentrates around the ground-truth permutation matrix for certain correlation parameters.
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…
Paper compares expressive power of GNNs, proving approximation guarantees for practical architectures.
problem Understanding the expressive power of Graph Neural Networks (GNNs).
method Theoretical framework comparing invariant and equivariant GNNs, proving approximation guarantees for practical architectures.
result Folklore Graph Neural Networks (FGNN) are the most expressive architectures for a given tensor order.
Following our approach to metric Lie algebras developed in math.DG/0312243 we propose a way of understanding pseudo-Riemannian symmetric spaces which are not semi-simple. We introduce cohomology sets (called quadratic cohomology) associated with orthogonal modules of Lie algebras with involution. Then we construct a fu…
Paper analyzes Birkhoff relaxation for graph alignment, providing theoretical guarantees.
problem Finding vertex correspondence between two graphs to maximize edge overlap.
method Birkhoff relaxation as a convex relaxation of the quadratic assignment problem (QAP).
result Theoretical guarantees on the performance of Birkhoff relaxation under specific conditions.
Paper introduces a new outer measure for continuous price paths with instant enforcement.
problem Defining a new outer measure for continuous price paths with instant enforcement.
method Introducing an outer measure on the space that assigns zero value to instantly blockable sets.
result Proves BDG inequalities and an Itô-type integral for the modified measure.
Improved R-QDA classifier performs well in unbalanced data settings.
problem High sensitivity of R-QDA to covariance matrix estimation noise in unbalanced data.
method Proposes an improved R-QDA with two regularization parameters and a modified bias.
result Significantly better classification performance compared to traditional R-QDA.
A weighted random survival forest is presented in the paper. It can be regarded as a modification of the random forest improving its performance. The main idea underlying the proposed model is to replace the standard procedure of averaging used for estimation of the random survival forest hazard function by weighted av…
Improved graph matching using covariates for network data integration.
problem Matching networks without unique identifiers.
method Two novel covariate-assisted seeded graph matching methods.
result Improved alignment accuracy through covariate information.
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 .
Sliced Gromov-Wassersteinstat.ML
Recently used in various machine learning contexts, the Gromov-Wasserstein distance (GW) allows for comparing distributions whose supports do not necessarily lie in the same metric space. However, this Optimal Transport (OT) distance requires solving a complex non convex quadratic program which is most of the time very…
This work optimizes RL algorithms using entropy regularisation for continuous-time LQ problems.
problem Designing RL algorithms to balance exploration and exploitation in noisy environments.
method Entropy regularisation in two formulations: exploratory control and proximal policy update.
result Regret of for both learning algorithms over episodes.
We propose a new method for supervised learning, especially suited to wide data where the number of features is much greater than the number of observations. The method combines the lasso () sparsity penalty with a quadratic penalty that shrinks the coefficient vector toward the leading principal components of …
Hypergraph partitioning is an important problem in machine learning, computer vision and network analytics. A widely used method for hypergraph partitioning relies on minimizing a normalized sum of the costs of partitioning hyperedges across clusters. Algorithmic solutions based on this approach assume that different p…
The paper develops a method for self-normalized inference in adaptive experiments.
problem Adaptive experiments require a fixed horizon for ATE estimation, but propensities can change.
method The method uses self-normalized martingale limit theory to estimate ATE.
result The Studentized statistic is asymptotically N(0,1) at the prespecified horizon.
Unified view on selective credit assignment for reinforcement learning.
problem Efficient credit assignment in reinforcement learning.
method Unified temporal-difference algorithms with selective weightings.
result New algorithms for backward credit assignment and off-policy learning.
Optimizes train schedules and maintenance using CP and QA.
problem Optimizing train schedules and maintenance considering constraints.
method Used Constraint Programming and Quantum Annealing to model and solve the problem.
result Both CP and QA approaches produce comparable results on real quantum computers.
The period mapping assigns to each rank n, marked metric graph Gamma a positive definite quadratic form on H_1(Gamma). This defines maps Phi* and Phi on Culler--Vogtmann's outer space CV_n, and its Torelli space quotient T_n, respectively. The map Phi is a free group analog of the classical period mapping that sends a …
New algorithms assign credit to past decisions based on hindsight.
problem Efficient credit assignment in reinforcement learning.
method Explicit credit assignment using new data in hindsight.
result Value functions can be rewritten to include hindsight credit assignment.
Graph matching plays a central role in such fields as computer vision, pattern recognition, and bioinformatics. Graph matching problems can be cast as two types of quadratic assignment problems (QAPs): Koopmans-Beckmann's QAP or Lawler's QAP. In our paper, we provide a unifying view for these two problems by introducin…
EgalMAB solves fair resource allocation in stochastic bandits.
problem Fair resource allocation in a stochastic multi-armed bandit setting.
method Design and analysis of UCB-based policy EgalUCB.
result Established upper bounds on cumulative regret.
New formulations for comparing metric measure spaces with arbitrary positive measures.
problem Comparing metric measure spaces with arbitrary positive measures.
method Two novel formulations: a divergence and a conic lifting approach.
result Efficiently solvable formulations for comparing metric spaces with arbitrary positive measures.
Error bounds based on worst likely assignments use permutation tests to validate classifiers. Worst likely assignments can produce effective bounds even for data sets with 100 or fewer training examples. This paper introduces a statistic for use in the permutation tests of worst likely assignments that improves error b…
Assignment methods are at the heart of many algorithms for unsupervised learning and clustering - in particular, the well-known K-means and Expectation-Maximization (EM) algorithms. In this work, we study several different methods of assignment, including the "hard" assignments used by K-means and the ?soft' assignment…
Hybrid Policy Optimization tackles reinforcement learning in hybrid spaces, improving performance over PPO.
problem Credit assignment issues and biased gradients in hybrid discrete-continuous action spaces.
method Mixed gradient estimator combining pathwise and score-function gradients, reformulating problems in hybrid form.
result HPO substantially outperforms PPO on inventory control and switched systems, with performance gaps increasing with continuous action dimension.
Would I have gotten that reward? Long-term credit assignment by counterfactual contribution analysiscs.LG
COCOA improves credit assignment in reinforcement learning by measuring contributions to rewards.
problem Improving sample efficiency in reinforcement learning through better credit assignment methods.
method Counterfactual Contribution Analysis (COCOA) for precise credit assignment.
result COCOA achieves lower bias and variance compared to Hindsight Credit Assignment (HCA), improving reinforcement learning performance.
Bayesian optimization method for permutations accelerates combinatorial search.
problem Optimizing expensive-to-evaluate objectives on permutation problems.
method LAW2ORDER, a batch Bayesian optimization method based on the acquisition weighted kernel.
result LAW2ORDER achieves sublinear batch cumulative regret, demonstrating accelerated search.
Matching one set of objects to another is a ubiquitous task in machine learning and computer vision that often reduces to some form of the quadratic assignment problem (QAP). The QAP is known to be notoriously hard, both in theory and in practice. Here, we investigate if this difficulty can be mitigated when some addit…
In this short note, we compare the combinatorial sign assignment of Manolescu, Ozsvath, Szabo and Thurston for grid homology of knots and links in 3-sphere with the sign assignment coming from a coherent system of orientations on Whitney disks. Although these constructions produce different signs, a small modification …
Doing well with less! On Sampling Techniques for Empirical Pairwise Loss Estimation/Minimizationstat.ML
Sampling a fraction of pairs can match full evaluation in machine learning losses.
problem High computational cost of full pairwise loss evaluation.
method Survey sampling techniques targeting informative pairs.
result Performance close to full pairwise evaluation achieved with frugal sampling.
New methods optimize personalized treatment assignment in trials with many arms.
problem Poor performance of standard methods in trials with many treatment arms.
method Regularized and clustered joint assignment forest algorithm.
result Gains in predicting arm-wise outcomes and utility gains from personalization.
Proposes unbiased estimators for training mixture of experts models.
problem Efficiently training large-scale mixture of experts models on modern hardware.
method Two unbiased estimators based on principled stochastic assignment procedures.
result Both estimators are more effective and robust than biased alternatives.
Optimizes balanced treatment assignment for experiments.
problem Balancing treatment groups in experiments for optimal results.
method Optimization of a two-sample test, using minimum spanning tree test.
result Optimal assignment algorithm with polynomial time complexity.