Paper improves clustering risk bounds for kernel k-means.
problem Improving clustering risk bounds for kernel k-means.
method Analyzes kernel k-means and Nyström approximation.
result Achieves nearly optimal excess clustering risk bound.
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,695 papers · 148 categories
Trend · papers per month
48 results for “Bounded Clustering”
On clusters and the multi-isoperimetric profile in Riemannian manifolds with bounded geometrymath.DG
The study proves the existence and properties of isoperimetric clusters in Riemannian manifolds with bounded geometry.
problem Proving the existence and properties of isoperimetric clusters in Riemannian manifolds with bounded geometry.
method Proved the existence of isoperimetric clusters and compactness theorem for sequence of clusters, introduced Holder continuity of multi-isoperimetric profile.
result Existence and properties of isoperimetric clusters in Riemannian manifolds with bounded geometry.
New bounds for convex clustering under graph connectivity.
problem Understanding clustering performance under different graph connectivity structures.
method Random walks and concentration inequalities for random graph models.
result Improved rates of convergence for centroid recovery.
Convex clustering can only learn convex clusters, with significant gaps between clusters.
problem Understanding the limitations and capabilities of convex clustering.
method Analyzing convex clustering solutions, proving properties, and characterizing clusters.
result Convex clustering can only learn convex clusters with significant gaps between clusters.
New bounds on the cohesion of complete-link and other linkage methods for agglomeration clusteringcs.LG
New bounds improve linkage methods for clustering, distinguishing complete-link from single-link.
problem Improving bounds on linkage methods for clustering quality.
method Developed new bounds for complete-link and average-link methods in agglomeration clustering.
result Separated complete-link from single-link in terms of approximation for diameter.
We present a nonparametric method for selecting informative features in high-dimensional clustering problems. We start with a screening step that uses a test for multimodality. Then we apply kernel density estimation and mode clustering to the selected features. The output of the method consists of a list of relevant f…
We formulate weighted graph clustering as a prediction problem: given a subset of edge weights we analyze the ability of graph clustering to predict the remaining edge weights. This formulation enables practical and theoretical comparison of different approaches to graph clustering as well as comparison of graph cluste…
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.
Localized sum-of-norms clustering separates balls in data.
problem Clustering arbitrarily close data points in multivariate data.
method Localized sum-of-norms optimization for clustering.
result Proves a bound on clustering error in stochastic ball model.
New computational lower bounds for clustering and related problems.
problem Statistical-computational gaps in high-dimensional clustering problems.
method Investigation of low-degree polynomials in latent space models to derive lower bounds.
result New and sharper computational lower bounds for clustering, sparse clustering, and biclustering.
A new k-means algorithm using cover trees accelerates clustering.
problem Efficiently clustering large datasets with k-means.
method Combining cover trees with upper and lower bounds.
result Significantly reduces distance computations and improves clustering performance.
Paper establishes universal lower bounds and optimal rates for clustering sub-exponential mixture models.
problem Achieving optimal error rates in clustering sub-exponential mixture models.
method Establishes universal lower bounds and demonstrates iterative algorithms' optimality in sub-exponential mixture models.
result Iterative algorithms achieve the universal lower bound in sub-exponential mixture models.
The paper introduces explainable -means with axis-parallel hyperplanes for -dimensional data.
problem Creating explainable clustering with axis-parallel hyperplanes for complex data.
method An efficient algorithm that finds an explainable clustering with a near-optimal cost function.
result The algorithm achieves a near-optimal -means cost of for -dimensional data.
New method speeds up k-means clustering using sketch-and-solve.
problem Efficiently solving k-means clustering for large datasets.
method Sketch-and-solve approach with Peng-Wei semidefinite relaxation.
result Provides high-confidence lower bounds on k-means optimal value.
Beyond existing multi-view clustering, this paper studies a more realistic clustering scenario, referred to as incomplete multi-view clustering, where a number of data instances are missing in certain views. To tackle this problem, we explore spectral perturbation theory. In this work, we show a strong link between per…
Density mode clustering is a nonparametric clustering method. The clusters are the basins of attraction of the modes of a density estimator. We study the risk of mode-based clustering. We show that the clustering risk over the cluster cores --- the regions where the density is high --- is very small even in high dimens…
The classical -means algorithm for partitioning points in into clusters is one of the most popular and widely spread clustering methods. The need to respect prescribed lower bounds on the cluster sizes has been observed in many scientific and business applications. In this paper, we present an…
New clustering method for exponential family data.
problem Improving clustering for non-Gaussian data.
method Bregman Power k-Means algorithm.
result Outperforms existing methods in non-Gaussian data settings.
Algorithm clusters mixtures with bounded covariances under specific separation conditions.
problem Clustering mixtures of bounded covariance distributions with fine-grained separation.
method Introduced clustering refinement and efficient algorithm for accurate clustering.
result First poly-time algorithm for nearly uniform mixtures, and efficient refinement for general mixtures.
Paper bounds subspace estimator error from noisy projections.
problem Estimating subspaces from noisy data.
method Derives perturbation bound on optimal subspace estimator.
result Fundamental result with implications in matrix completion and clustering.
Kernelized convex clustering handles non-linear and non-convex data.
problem Lack of effective clustering methods for non-linear and non-convex data.
method Kernelized convex clustering in RKHS.
result Superior performance compared to state-of-the-art techniques.
We study the connections between spectral clustering and the problems of maximum margin clustering, and estimation of the components of level sets of a density function. Specifically, we obtain bounds on the eigenvectors of graph Laplacian matrices in terms of the between cluster separation, and within cluster connecti…
Overlapping clusters are common in models of many practical data-segmentation applications. Suppose we are given elements to be clustered into possibly overlapping clusters, and an oracle that can interactively answer queries of the form "do elements and belong to the same cluster?" The goal is to recov…
Study clusters distributions with known or unknown clusters using distribution testing.
problem Cluster distributions that are -far in total variation.
method Distribution testing approach to establish upper and lower bounds on sample complexity.
result Achieves tight sample complexity bounds for all regimes (up to a logarithmic factor).
Multilayer graphs are commonly used for representing different relations between entities and handling heterogeneous data processing tasks. New challenges arise in multilayer graph clustering for assigning clusters to a common multilayer node set and for combining information from each layer. This paper presents a theo…
New property identifies arithmetic lattices from nonuniform lattices.
problem Characterizing arithmetic lattices among nonuniform lattices.
method Introduced Bounded Clustering (B-C) property.
result B-C property uniquely identifies arithmetic lattices.
New lower bounds show challenges in clustering in moderate dimensions.
problem Clustering points from mixtures of isotropic Gaussians in moderate dimensions.
method Established low-degree polynomial lower bounds and developed a novel non-spectral algorithm.
result New lower bounds reveal a 'non-parametric rate' in moderate dimensions.
Construct locally minimizing -clusters with prescribed asymptotic geometry.
problem Minimizing clusters with prescribed asymptotic geometry.
method Develop a refined construction using the Hardt-Simon foliation.
result Produce a countably infinite family of distinct locally minimizing clusters asymptotic to a singular area-minimizing hypercone.
Empty core found in max-loss non-centroid clustering.
problem Core stability in non-centroid clustering under max-loss objective.
method Proof for all k≥3 and n≥9 agents, computer-aided proof for 2D Euclidean points.
result Core can be empty in non-centroid clustering under max-loss objective.
Spectral clustering has become one of the most widely used clustering techniques when the structure of the individual clusters is non-convex or highly anisotropic. Yet, despite its immense popularity, there exists fairly little theory about performance guarantees for spectral clustering. This issue is partly due to the…
Biological and social systems consist of myriad interacting units. The interactions can be represented in the form of a graph or network. Measurements of these graphs can reveal the underlying structure of these interactions, which provides insight into the systems that generated the graphs. Moreover, in applications s…
Two new algorithms improve online clustering of bandits by accelerating cluster identification without strong assumptions.
problem Challenges in accurately identifying unknown user clusters in online bandit settings.
method Proposes UniCLUB and PhaseUniCLUB algorithms with enhanced exploration mechanisms.
result Achieves comparable regret bounds to prior work with weaker assumptions.
In correlation clustering, we are given objects together with a binary similarity score between each pair of them. The goal is to partition the objects into clusters so to minimise the disagreements with the scores. In this work we investigate correlation clustering as an active learning problem: each similarity sc…
End-to-end deep learning for multi-view clustering improves accuracy across various data types.
problem Limited multi-view clustering methods for general data types and suboptimal two-stage process.
method Permutation-based canonical correlation objective for fused representations; pseudo-labels for clustering; theoretical error bound.
result Proposed model provides meaningful fused representations and effective clustering across multiple views.
New algorithm IAC recovers hidden communities in labeled SBM with optimal performance.
problem Recovering hidden communities in Labeled Stochastic Block Model with varying cluster sizes.
method IAC (Instance-Adaptive Clustering) algorithm, consisting of spectral clustering and iterative likelihood-based improvements.
result IAC achieves optimal performance matching instance-specific lower bounds in expectation and with high probability.
The paper tackles fair correlation clustering with fairness constraints.
problem Minimizing disagreements while adhering to fairness constraints for clustering.
method Two variants of fairness constraints are considered: equal distribution and relative bounds. Approximation algorithms are developed for these constraints.
result Approximation algorithms for fair correlation clustering with theoretical guarantees and empirical validation.
In many applications we want to find the number of clusters in a dataset. A common approach is to use the penalized k-means algorithm with an additive penalty term linear in the number of clusters. An open problem is estimating the value of the coefficient of the penalty term. Since estimating the value of the coeffici…
We study clustering algorithms based on neighborhood graphs on a random sample of data points. The question we ask is how such a graph should be constructed in order to obtain optimal clustering results. Which type of neighborhood graph should one choose, mutual k-nearest neighbor or symmetric k-nearest neighbor? What …
The paper analyzes the generalization performance of spectral clustering algorithms and proposes new methods to improve their effectiveness.
problem Theoretical analysis of spectral clustering's generalization performance.
method Theoretical analysis and development of new spectral clustering algorithms.
result The excess risk bounds of spectral clustering algorithms have a convergence rate.
CDL index improves clustering validation for non-convex data.
problem Selecting clustering algorithms and hyperparameters without labeled data.
method CDL uses compactness, centers, and covariances to compute a probabilistic description length bound.
result CDL outperforms conventional CVIs on synthetic and image benchmarks.
Integrates VAEs into EM for deep clustering and generation.
problem Clustering and generating new samples from complex distributions.
method Combines VAEs and EM, updating model parameters and refining cluster assignments.
result Superior clustering performance on MNIST and FashionMNIST.
We propose a general variational framework of fair clustering, which integrates an original Kullback-Leibler (KL) fairness term with a large class of clustering objectives, including prototype or graph based. Fundamentally different from the existing combinatorial and spectral solutions, our variational multi-term appr…
Representative Arm Identification: A fixed confidence approach to identify cluster representativescs.LG
New method identifies cluster representatives with minimal pulls.
problem Identifying cluster representatives in multi-armed bandits.
method Fixed confidence approach using confidence intervals.
result Sample complexity matches theoretical lower bound.
Spectral clustering is a widely studied problem, yet its complexity is prohibitive for dynamic graphs of even modest size. We claim that it is possible to reuse information of past cluster assignments to expedite computation. Our approach builds on a recent idea of sidestepping the main bottleneck of spectral clusterin…
Unified framework for differentiable graph partitioning with probabilistic cuts.
problem Lack of general guarantees and principled gradients in prior probabilistic relaxations of graph cuts.
method Unified probabilistic framework covering a wide class of cuts, including Normalized Cut, with tight analytic upper bounds.
result Rigorous, numerically stable foundation for scalable, differentiable graph partitioning.
This paper introduces Bounded Fuzzy Possibilistic Method (BFPM) by addressing several issues that previous clustering/classification methods have not considered. In fuzzy clustering, object's membership values should sum to 1. Hence, any object may obtain full membership in at most one cluster. Possibilistic clustering…
Polynomial-time algorithm finds planted hypercube vectors in Gaussian mixtures.
problem Clustering d-dimensional Gaussian mixtures with unknown covariance.
method Lattice-based methods using Lenstra--Lenstra--Lovasz reduction.
result Achieves statistically-optimal sample complexity of d+1 samples.
The only input to attain the portfolio weights of global minimum variance portfolio (GMVP) is the covariance matrix of returns of assets being considered for investment. Since the population covariance matrix is not known, investors use historical data to estimate it. Even though sample covariance matrix is an unbiased…