initKmix generates better initial partitions for k-means clustering of mixed datasets.
problem Random initial partitions lead to inconsistent clustering results.
method initKmix runs k-means multiple times, using different attributes to create initial clusters, then combines results.
result initKmix produces more accurate and consistent clustering results.
Study exact partition recovery with same-cluster oracle, bounded error.
problem Exact recovery of partitions with same-cluster oracle in adversarial error.
method Novel connection to correlation clustering, Rényi-Ulam framework, upper and lower bounds, randomized algorithm analysis, adaptivity-query complexity study.
result Upper and lower bounds on worst-case query complexity, expected performance bounds of randomized algorithm.
Region-specific linear models are widely used in practical applications because of their non-linear but highly interpretable model representations. One of the key challenges in their use is non-convexity in simultaneous optimization of regions and region-specific models. This paper proposes novel convex region-specific…
We propose an incremental training method that partitions the original network into sub-networks, which are then gradually incorporated in the running network during the training process. To allow for a smooth dynamic growth of the network, we introduce a look-ahead initialization that outperforms the random initializa…
Exchangeable graphs arise via a sampling procedure from measurable functions known as graphons. A natural estimation problem is how well we can recover a graphon given a single graph sampled from it. One general framework for estimating a graphon uses step-functions obtained by partitioning the nodes of the graph accor…
Given iid observations from an unknown absolute continuous distribution defined on some domain Ω, we propose a nonparametric method to learn a piecewise constant function to approximate the underlying probability density function. Our density estimate is a piecewise constant function defined on a binary partition o…
Novel hybrid method for Bayesian network structure learning reduces computational time without sacrificing accuracy.
problem Bayesian network structure learning efficiency and accuracy trade-off.
method Partitioned PC (pPC), p-value adjacency thresholding (PATH), hybrid greedy initialization (HGI). result pHGS achieves significant computational reductions compared to the PC algorithm without sacrificing structure learning accuracy.
In this paper we develop and analyze Hydra: HYbriD cooRdinAte descent method for solving loss minimization problems with big data. We initially partition the coordinates (features) and assign each partition to a different node of a cluster. At every iteration, each node picks a random subset of the coordinates from tho…
Paper proposes a method to predict optimal data partitioning based on query execution costs.
problem Finding optimal data partitioning for improved system performance and scalability.
method Formal model abstraction of workload queries, genetic algorithm for optimization, evaluation using PostgreSQL's query optimizer.
result The approach effectively reduces workload execution cost and improves system performance.
Batch normalization improves deep networks by aligning their decision boundaries with data.
problem Improving the performance and generalization of deep networks.
method Theoretical analysis of batch normalization as a function approximation technique for continuous piecewise affine splines.
result Batch normalization adapts the geometry of a deep network's partition to match the data, improving learning and generalization.
Quantum algorithm speeds up Gibbs partition function estimation.
problem Estimating partition functions in sublinear time.
method Sublinear-time quantum algorithm using quantum phase and amplitude estimation.
result First sublinear-time speed-up for partition function estimation.
AIS method improves estimation of RBM partition function with reduced computational cost.
problem Efficiently estimating partition function of RBMs for large systems.
method Annealed Importance Sampling (AIS) with optimized initialization.
result Good estimation of partition function Z with reduced computational cost.
CM algorithm improves MMI classifications for unseen instances.
problem Improving classification accuracy for unseen instances using MMI criterion.
method Introduces CM algorithm for MMI classifications, combining semantic and Shannon channels for matching.
result Achieves high mutual information (99%) with minimal iterations in low-dimensional feature spaces.
Detect changes in noisy dynamical systems using empirical approximations and finite-sample bounds.
problem Change detection in noisy dynamical systems
method Partition-based empirical approximations and finite-state stationary distribution stability
result Finite-sample bound for empirical stationary density
PASCO speeds up graph clustering for large graphs.
problem Efficiently clustering large graphs with many communities.
method Overlay method combining coarsening and parallel clustering.
result PASCO accelerates clustering with improved efficiency and quality.
A new method detects concept drift in streaming data using k-means space partitioning.
problem Detecting distribution changes in streaming data.
method Equal intensity k-means space partitioning (EI-kMeans) and heuristic sensitivity improvement.
result EI-kMeans improves drift detection accuracy and sensitivity.
K-means fails catastrophically in high dimensions, Hartigan's avoids it.
problem K-means algorithm's failure in high-dimensional data.
method Proof of k-means failure and Hartigan's algorithm success.
result Hartigan's algorithm avoids the catastrophic failure of k-means in high dimensions.
Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) is demonstrated to efficiently solve eigenvalue problems for graph Laplacians that appear in spectral clustering. For static graph partitioning, 10-20 iterations of LOBPCG without preconditioning result in ~10x error reduction, enough to achieve 100% corr…
Geometrically proves Zabrodin-Wiegmann conjecture for integer QH states.
problem Proving a geometric version of Zabrodin-Wiegmann conjecture for integer Quantum Hall states.
method Using Riemann surfaces, canonical sections, and asymptotic expansions, the authors construct a canonical element in cohomology and relate its norm to the partition function.
result The constant term of the asymptotic expansion of the partition function matches a geometric version of Zabrodin-Wiegmann's prediction.
SOO uses bandit theory to optimize functions with limited evaluations.
problem Optimizing functions with a limited number of evaluations.
method SOO is a machine learning approach that uses domain partitioning and a tradeoff between exploration and exploitation.
result SOO provides guarantees on the returned solution and is numerically efficient.
Many complex systems generate multifractal time series which are long-range cross-correlated. Numerous methods have been proposed to characterize the multifractal nature of these long-range cross correlations. However, several important issues about these methods are not well understood and most methods consider only o…
Develops a new weighted Laplacian method for graph problems.
problem Graph partitioning and balanced minimum cut problems.
method Weighted Laplacian method based on graph theory and PDEs.
result Established equivalence relations among graph problems.
Given a singular Riemannian foliation on a compact Riemannian manifold, we study the mean curvature flow equation with a regular leaf as initial datum. We prove that if the leaves are compact and the mean curvature vector field is basic, then any finite time singularity is a singular leaf, and the singularity is of typ…
In this paper we make two novel contributions to hierarchical clustering. First, we introduce an anomalous pattern initialisation method for hierarchical clustering algorithms, called A-Ward, capable of substantially reducing the time they take to converge. This method generates an initial partition with a sufficiently…
This paper analyzes MFVBI for GMM using statistical mechanics.
problem Approximate fast computation of Gaussian Mixture Model.
method Statistical mechanics and MFVBI applied to GMM.
result Rigorous analysis and mathematical foundation for MFVBI applied to GMM.
The motivation of this work is to improve the performance of standard stacking approaches or ensembles, which are composed of simple, heterogeneous base models, through the integration of the generation and selection stages for regression problems. We propose two extensions to the standard stacking approach. In the fir…
DISCERN estimates K for K-Means clustering efficiently.
problem Estimating the number of clusters in data.
method A deterministic initialization method for K-Means++.
result Improves both K estimation and clustering performance.
Proposes PGPS for efficient Bayesian inference.
problem Efficient sampling from complex posterior distributions.
method Path-guided particle-based sampling with Log-weighted Shrinkage.
result PGPS generates samples closer to target distribution.
Optimizes parallel training of linear models, improving convergence.
problem Improving convergence of parallel training of linear models.
method Data partitioning scheme across threads to improve convergence.
result Achieved up to 42x speedup in convergence compared to state of the art implementations.
Proposes a method to partition univariate data into unimodal subsets.
problem Partitioning univariate multimodal data into unimodal subsets.
method Recursive splitting around valley points of the data density using properties of critical points on the convex hull of the ecdf plot.
result Obtains a hierarchical statistical model of the initial dataset as a mixture of UMMs.
We consider the problem of identifying underlying community-like structures in graphs. Towards this end we study the Stochastic Block Model (SBM) on k-clusters: a random model on n=km vertices, partitioned in k equal sized clusters, with edges sampled independently across clusters with probability q and within …
The study limits how many parts regular simplicial partitions can overlap.
problem Bounding the intersection number of regular simplicial partitions.
method Analyzing the properties of regular simplicial partitions.
result Established a maximum limit for the intersection number.
Paper introduces XBART for nonlinear regression, outperforming XGBoost.
problem Nonlinear regression problems, especially in speed and accuracy.
method Combines Bayesian modeling and recursive partitioning for efficient, accurate predictions.
result XBART provides faster and more accurate predictions than XGBoost.
Imputation-free method learns tabular data with missing values using transformer.
problem Machine learning on tabular data with missing values often leads to unreliable outcomes due to synthetic imputation.
method Incremental attention learning (IFIAL) using transformer with attention masks.
result IFIAL outperforms state-of-the-art methods in 17 diverse tabular data sets.
The problem of subgroups is ubiquitous in scientific research (ex. disease heterogeneity, spatial distributions in ecology...), and piecewise regression is one way to deal with this phenomenon. Morse-Smale regression offers a way to partition the regression function based on level sets of a defined function and that fu…
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 …
Parallel neural networks estimate TVD for merging over-clustered datasets.
problem Merging over-partitioned clusters in unsupervised learning.
method Use neural networks to estimate TVD between clusters in parallel.
result Neural network estimates of TVD lead to better merge decisions.
New method improves nearest neighbor search using neural networks and graph partitioning.
problem Efficient nearest neighbor search in high-dimensional spaces.
method Developed a new framework for space partitioning using neural networks and graph partitioning.
result Neural LSH partitions outperform existing methods on standard benchmarks.
Rectangular Bounding Process (RBP) improves partitioning efficiency in multi-dimensional spaces.
problem Creating many unnecessary divisions in sparse regions when describing dense regions.
method Introduces Rectangular Bounding Process (RBP) to efficiently partition multi-dimensional spaces using a bounding strategy.
result The RBP is self-consistent and can be extended to infinite space, offering rich yet parsimonious expressiveness.
GAP uses deep learning to efficiently partition graphs.
problem Graph partitioning to minimize edge cut.
method Deep learning approach with a differentiable loss function.
result GAP achieves competitive partitions and generalizes to unseen graphs.
In this paper, we propose a family of graph partition similarity measures that take the topology of the graph into account. These graph-aware measures are alternatives to using set partition similarity measures that are not specifically designed for graph partitions. The two types of measures, graph-aware and set parti…
The study examines the balancedness of random partition models and finds the rich-get-richer characteristic is a result of model assumptions.
problem The balancedness of random partition models is largely neglected in the literature.
method Formulated a framework to define and study the balancedness of exchangeable random partition models, analyzed using product-form exchangeability and projectivity assumptions.
result The 'rich-get-richer' characteristic is an inevitable consequence of the model assumptions.
The paper develops mixed-integer formulations for neural networks using partitioning.
problem Optimizing trained ReLU neural networks with balanced model size and tightness.
method Partitioning node inputs into groups, forming the convex hull via disjunctive programming.
result The proposed formulations outperform existing ones, especially with fewer partitions.
In this paper, we study different discrete data clustering methods, which use the Model-Based Clustering (MBC) framework with the Multinomial distribution. Our study comprises several relevant issues, such as initialization, model estimation and model selection. Additionally, we propose a novel MBC method by efficientl…
New partition designs reduce star discrepancy in high-dimensional sampling.
problem Improving the expected star discrepancy in high-dimensional sampling.
method Developed non-equal volume partitions to achieve lower expected star discrepancy.
result Explicit upper bounds for expected star discrepancy under non-equal volume partitions.
Online PaLD extends PaLD for semi-supervised online applications.
problem Scalability of unsupervised clustering algorithms for large datasets.
method Adapted partitioned local depth algorithm for online semi-supervised prediction.
result Online PaLD extends cohesion network to new data points efficiently.
The paper constructs Markov partitions for geodesic flow on hyperbolic surfaces.
problem Understanding Markov partitions for general hyperbolic flows.
method Rigorous construction of Markov partitions for geodesic flow on Riemann surfaces of constant negative curvature.
result Explicit forms of rectangles and local cross sections provided for the geodesic flow.
Paper presents an efficient algorithm for estimating Lipschitz functions from noisy data.
problem Estimating unknown Lipschitz functions from noisy observations.
method Extends max-affine methods to Lipschitz setting using nonlinear feature expansion and adaptive partitioning.
result Achieves minimax convergence rate with respect to intrinsic dimension, up to logarithmic factors.