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.
A biclustering algorithm finds dense disjoint subgraphs in weighted bipartite graphs.
We give polynomial-time algorithms for the exact computation of lowest-energy (ground) states, worst margin violators, log partition functions, and marginal edge probabilities in certain binary undirected graphical models. Our approach provides an interesting alternative to the well-known graph cut paradigm in that it …
A RL-enhanced quantum-inspired algorithm solves combinatorial optimization problems.
We consider the problem of classifying data manifolds where each manifold represents invariances that are parameterized by continuous degrees of freedom. Conventional data augmentation methods rely upon sampling large numbers of training examples from these manifolds; instead, we propose an iterative algorithm called M…
New algorithm clusters Gaussian mixtures with unknown covariance efficiently.
New 2-spheres of revolution with simple cut locus structures.
A new reinforcement learning method improves Max-Cut solutions without needing training data.
Financial portfolios are often optimized for maximum profit while subject to a constraint formulated in terms of the Conditional Value-at-Risk (CVaR). This amounts to solving a linear problem. However, in its original formulation this linear problem has a very large number of linear constraints, too many to be enforced…
Study sub-Riemannian geodesics on a Heisenberg 3D nil-manifold.
Let φ(G) be the minimum conductance of an undirected graph G, and let 0=λ_1 <= λ_2 <=... <= λ_n <= 2 be the eigenvalues of the normalized Laplacian matrix of G. We prove that for any graph G and any k >= 2, φ(G) = O(k) λ_2 / \sqrt{λ_k}, and this performance guarantee is achieved by the spectral partitioning algorithm. …
The maximum a posteriori (MAP) configuration of binary variable models with submodular graph-structured energy functions can be found efficiently and exactly by graph cuts. Max-product belief propagation (MP) has been shown to be suboptimal on this class of energy functions by a canonical counterexample where MP conver…
Differentiable cutting-plane layers solve parametric mixed-integer linear optimization problems.
Truncated Singular Value Decomposition (SVD) calculates the closest rank- approximation of a given input matrix. Selecting the appropriate rank defines a critical model order choice in most applications of SVD. To obtain a principled cut-off criterion for the spectrum, we convert the underlying optimization prob…
Deep Reinforcement Learning (DRL) algorithms for continuous action spaces are known to be brittle toward hyperparameters as well as \cut{being}sample inefficient. Soft Actor Critic (SAC) proposes an off-policy deep actor critic algorithm within the maximum entropy RL framework which offers greater stability and empiric…
Max-Cut decision tree improves classification accuracy and reduces computation time.
Paper proposes quantum methods for optimizing machine learning functions.
Stochastic cutting planes improve data-driven optimization speed.
We study the problem of partitioning a small sample of individuals from a mixture of product distributions over a Boolean cube according to their distributions. Each distribution is described by a vector of allele frequencies in . Given two distributions, we use to denote the average $\el…
Spectral Clustering as a relaxation of the normalized/ratio cut has become one of the standard graph-based clustering methods. Existing methods for the computation of multiple clusters, corresponding to a balanced -cut of the graph, are either based on greedy techniques or heuristics which have weak connection to th…
We consider the Lie group PSL(2) (the group of orientation preserving isometries of the hyperbolic plane) and a left-invariant Riemannian metric on this group with two equal eigenvalues that correspond to space-like eigenvectors (with respect to the Killing form). For such metrics we find a parametrization of geodesics…
We consider a left invariant Riemannian metric on SO(3) with two equal eigenvalues. We find the cut locus and the equation for the cut time. We find the diameter of such metric and describe the set of all most distant points from the identity. Also we prove that the cut locus and the cut time converge to the cut locus …
Quantum algorithm speeds up MIP solving by a near-quadratic factor.
When it comes to clustering nonconvex shapes, two paradigms are used to find the most suitable clustering: minimum cut and maximum density. The most popular algorithms incorporating these paradigms are Spectral Clustering and DBSCAN. Both paradigms have their pros and cons. While minimum cut clusterings are sensitive t…
Spectral clustering is sensitive to how graphs are constructed from data particularly when proximal and imbalanced clusters are present. We show that Ratio-Cut (RCut) or normalized cut (NCut) objectives are not tailored to imbalanced data since they tend to emphasize cut sizes over cut values. We propose a graph partit…
NeuralCut learns to select cutting planes by looking ahead, outperforming traditional methods.
Study on semiconcavity of solutions to gradient obstacle problems on compact manifolds.
Spectral clustering methods which are frequently used in clustering and community detection applications are sensitive to the specific graph constructions particularly when imbalanced clusters are present. We show that ratio cut (RCut) or normalized cut (NCut) objectives are not tailored to imbalanced cluster sizes sin…
New method calculates cut locus on surfaces without boundary.
We consider the structured-output prediction problem through probabilistic approaches and generalize the "perturb-and-MAP" framework to more challenging weighted Hamming losses, which are crucial in applications. While in principle our approach is a straightforward marginalization, it requires solving many related MAP …
Study shows convergence rates for Cheeger cuts on data clouds.
Inference in general Markov random fields (MRFs) is NP-hard, though identifying the maximum a posteriori (MAP) configuration of pairwise MRFs with submodular cost functions is efficiently solvable using graph cuts. Marginal inference, however, even for this restricted class, is in #P. We prove new formulations of deriv…
New Karger-like algorithms solve graph cuts, useful for image segmentation.
This work reviews left-invariant optimal control problems on Lie groups.
We present and analyze a central cutting surface algorithm for general semi-infinite convex optimization problems, and use it to develop a novel algorithm for distributionally robust optimization problems in which the uncertainty set consists of probability distributions with given bounds on their moments. Moments of a…
Integer programming (IP) is a general optimization framework widely applicable to a variety of unstructured and structured problems arising in, e.g., scheduling, production planning, and graph optimization. As IP models many provably hard to solve problems, modern IP solvers rely on many heuristics. These heuristics ar…
The Ryu-Takayanagi (RT) formula relates the entanglement entropy of a region in a holographic theory to the area of a corresponding bulk minimal surface. Using the max flow-min cut principle, a theorem from network theory, we rewrite the RT formula in a way that does not make reference to the minimal surface. Instead, …
Develops a new weighted Laplacian method for graph problems.
Reduced sub-Riemannian time on a specific group structure.
In this paper we relate the partition function to the max-statistics of random variables. In particular, we provide a novel framework for approximating and bounding the partition function using MAP inference on randomly perturbed models. As a result, we can use efficient MAP solvers such as graph-cuts to evaluate the c…
Paper provides a performance guarantee for spectral clustering.
The design of good heuristics or approximation algorithms for NP-hard combinatorial optimization problems often requires significant specialized knowledge and trial-and-error. Can we automate this challenging, tedious process, and learn the algorithms instead? In many real-world applications, it is typically the case t…
New method calculates cut locus on Riemannian manifolds using optimal transport.
We propose a new method to model multi-way similarities into hypergraphs for clustering.
ABM automates feature engineering and variable selection for loss-based models.
Graph cuts find global optima for Potts models in slight perturbations.
We consider complete non-compact manifolds with either a sub-quadratic growth of the norm of the Riemann curvature, or a sub-quadratic growth of both the norm of the Ricci curvature and the squared inverse of the injectivity radius. We show the existence on such a manifold of a distance-like function with bounded gradi…
NeVI-Cut uses neural networks to efficiently propagate uncertainty without feedback.
Paper connects probability density cuts to graph theory eigenfunctions.