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.
Survey of mass partition problems in geometry and topology.
Online BSP-Forest improves space partitioning for large-scale classification and regression.
Hypergraph partitioning lies at the heart of a number of problems in machine learning and network sciences. Many algorithms for hypergraph partitioning have been proposed that extend standard approaches for graph partitioning to the case of hypergraphs. However, theoretical aspects of such methods have seldom received …
Fitting statistical models is computationally challenging when the sample size or the dimension of the dataset is huge. An attractive approach for down-scaling the problem size is to first partition the dataset into subsets and then fit using distributed algorithms. The dataset can be partitioned either horizontally (i…
A new method avoids partition function computation for Gibbs density estimation.
Survey on soap bubble partitions and their stability.
This paper tackles multi-modal label disentanglement in partition-based XMC.
Locally isoperimetric partitions minimize perimeter in space.
Novel method recursively partitions sample space for density estimation.
Study exact partition recovery with same-cluster oracle, bounded error.
Space partitions of underlie a vast and important class of fast nearest neighbor search (NNS) algorithms. Inspired by recent theoretical work on NNS for general metric spaces [Andoni, Naor, Nikolov, Razenshteyn, Waingarten STOC 2018, FOCS 2018], we develop a new framework for building space partitions re…
In this paper, we consider unsupervised partitioning problems, such as clustering, image segmentation, video segmentation and other change-point detection problems. We focus on partitioning problems based explicitly or implicitly on the minimization of Euclidean distortions, which include mean-based change-point detect…
New method unifies and formalizes data partitioning using a single vector.
New examples show non-rotational annuli in a ball, solving a uniqueness problem.
The study examines the balancedness of random partition models and finds the rich-get-richer characteristic is a result of model assumptions.
In this paper we propose an algorithm for exact partitioning of high-order models. We define a general class of -degree Homogeneous Polynomial Models, which subsumes several examples motivated from prior literature. Exact partitioning can be formulated as a tensor optimization problem. We relax this high-order combi…
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…
A new method for state space partitioning in block particle filtering reduces bias and variance.
Graph partitioning is the problem of dividing the nodes of a graph into balanced partitions while minimizing the edge cut across the partitions. Due to its combinatorial nature, many approximate solutions have been developed, including variants of multi-level methods and spectral clustering. We propose GAP, a Generaliz…
Proposes a partitioned least squares model for feature grouping.
Study on detecting hierarchical community structures in networks.
Exact partitioning of high-order planted models achieved through convex optimization.
In a series of recent works, we have generalised the consistency results in the stochastic block model literature to the case of uniform and non-uniform hypergraphs. The present paper continues the same line of study, where we focus on partitioning weighted uniform hypergraphs---a problem often encountered in computer …
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. …
New algorithms improve convergence rates for non-log-concave sampling and log-partition estimation.
In this paper we investigate the following existence problem for rational functions: for a given collection of partitions of a number to define whether there exists a rational function of degree for which is the branch datum. An important particular case when the answer to this problem is known is t…
This paper presents Sparse Partitioning, a Bayesian method for identifying predictors that either individually or in combination with others affect a response variable. The method is designed for regression problems involving binary or tertiary predictors and allows the number of predictors to exceed the size of the sa…
Both supervised and unsupervised machine learning algorithms have been used to learn partition-based index structures for approximate nearest neighbor (ANN) search. Existing supervised algorithms formulate the learning task as finding a partition in which the nearest neighbors of a training set point belong to the same…
Stochastic partition models divide a multi-dimensional space into a number of rectangular regions, such that the data within each region exhibit certain types of homogeneity. Due to the nature of their partition strategy, existing partition models may create many unnecessary divisions in sparse regions when trying to d…
The excessively increased volume of data in modern data management systems demands an improved system performance, frequently provided by data distribution, system scalability and performance optimization techniques. Optimized horizontal data partitioning has a significant influence of distributed data management syste…
Paper recovers lattice signal partitions efficiently.
We study the stability of partitions in convex domains involving simultaneous coexistence of three phases, viz. triple junctions. We present a careful derivation of the formula for the second variation of area, written in a suitable form with particular attention to boundary and spine terms, and prove, in contrast to t…
This study proposes a graph partitioning method to improve spatial prediction models.
We consider the problem of adaptive stratified sampling for Monte Carlo integration of a noisy function, given a finite budget n of noisy evaluations to the function. We tackle in this paper the problem of adapting to the function at the same time the number of samples into each stratum and the partition itself. More p…
We present Random Partition Kernels, a new class of kernels derived by demonstrating a natural connection between random partitions of objects and kernels between those objects. We show how the construction can be used to create kernels from methods that would not normally be viewed as random partitions, such as Random…
Study optimal partition problem for Q-curvature equations on Einstein manifolds.
Proposes SPFB method for optimizing partition functions in stochastic learning.
Given a vector of probability distributions, or arms, each of which can be sampled independently, we consider the problem of identifying the partition to which this vector belongs from a finitely partitioned universe of such vector of distributions. We study this as a pure exploration problem in multi armed bandit sett…
Motivated by a geometric problem, we introduce a new non-convex graph partitioning objective where the optimality criterion is given by the sum of the Dirichlet eigenvalues of the partition components. A relaxed formulation is identified and a novel rearrangement algorithm is proposed, which we show is strictly decreas…
Survey of Bayesian nonparametric space partition models and their applications.
Paper generalizes reward distribution in multi-armed bandits with temporally-partitioned rewards.
Improved neural network robustness certification through tighter convex relaxations.
This paper addresses the general problem of modelling and learning rank data with ties. We propose a probabilistic generative model, that models the process as permutations over partitions. This results in super-exponential combinatorial state space with unknown numbers of partitions and unknown ordering among them. We…
Study optimal partitions on spheres using fractional Q-curvature and variational methods.
LA-MCTS learns search space partition for black-box optimization using Monte Carlo Tree Search.
A new framework for federated learning tackles challenges with horizontally partitioned labels and stragglers.
New algorithm for multi-armed bandits with delayed, partially observed rewards.
The output scores of a neural network classifier are converted to probabilities via normalizing over the scores of all competing categories. Computing this partition function, , is then linear in the number of categories, which is problematic as real-world problem sets continue to grow in categorical types, such as …