Characterizations of Admissible Objective Functions for Hierarchical Clustering

• URL: http://arxiv.org/abs/2604.23628v1
• Date: Sun, 26 Apr 2026 09:44:01 GMT
• Title: Characterizations of Admissible Objective Functions for Hierarchical Clustering
• Abstract summary: We introduce a new class of objective functions for hierarchical clustering, where cluster interactions are measured by maximum rather than aggregate similarity.<n>These results provide new theoretical insights into hierarchical clustering and clarify the scope of algorithmic guarantees for optimizing them.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hierarchical clustering is a fundamental task in data analysis, yet for a long time it lacked a principled objective function. Dasgupta [STOC 2016] initiated a formal framework by introducing a discrete objective function for cluster trees. This framework was subsequently expanded by Cohen-Addad et al. [J. ACM 2019], who introduced the notion of admissibility -- a criterion ensuring that, whenever the input similarities admit consistent hierarchical representations, the minimizers of an objective function recover them. They also provided a necessary and sufficient condition for admissibility within a broad class of objective functions, which we refer to as sum-type objective functions. Our contributions are twofold. First, we characterize admissible sum-type objective functions when the scaling function g is a symmetric polynomial of degree at most two, together with sufficient conditions in the degree-three case. For admissible objective functions in this class, we show that the recursive sparsest cut algorithm achieves an O($φ$)-approximation ratio, where $φ$ denotes the approximation factor of the sparsest cut subroutine. Second, we introduce a new class of objective functions for hierarchical clustering, which we term max-type objective functions, where cluster interactions are measured by maximum rather than aggregate similarity. For this class, we establish a general characterization of admissibility for arbitrary scaling functions g, and a complete characterization when g is a symmetric polynomial of degree at most two. These results provide new theoretical insights into admissible objective functions for hierarchical clustering and clarify the scope of algorithmic guarantees for optimizing them.

Related papers

• Universal NP-Hardness of Clustering under General Utilities [11.62669179647184]
  We formalise the common optimisation core motivating a diverse-time computable partition utility over a finite metric space.<n>By mapping ten major paradigms -- including k-means, GMMs, DBSCAN, spectral clustering, and affinity propagation -- to the UCP framework, we demonstrate that each inherits this fundamental inability.
  arXiv  Detail & Related papers  (2026-02-27T13:08:15Z)
• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  We propose a new analysis framework for clustering $M$ items into an unknown number of $K$ distinct groups using noisy and actively collected responses.<n>We establish a fundamental lower bound on the expected number of queries needed to achieve a desired confidence in the accuracy of the clustering.<n>We develop a computationally feasible variant of the Generalized Likelihood Ratio statistic and show that its performance gap to the lower bound can be accurately empirically estimated.
  arXiv  Detail & Related papers  (2026-02-05T14:16:47Z)
• Convergence of a class of gradient-free optimisation schemes when the objective function is noisy, irregular, or both [4.258175645355975]
  We investigate a class of algorithms designed to minimize a potentially non-smooth and noisy objective function.<n>The convergence results are obtained under very weak assumptions on the regularity of the objective function.<n>We illustrate the relevance of these algorithms and our convergence results through a challenging classification example from machine learning.
  arXiv  Detail & Related papers  (2025-12-02T21:05:41Z)
• Interpetable Target-Feature Aggregation for Multi-Task Learning based on Bias-Variance Analysis [53.38518232934096]
  Multi-task learning (MTL) is a powerful machine learning paradigm designed to leverage shared knowledge across tasks to improve generalization and performance. We propose an MTL approach at the intersection between task clustering and feature transformation based on a two-phase iterative aggregation of targets and features. In both phases, a key aspect is to preserve the interpretability of the reduced targets and features through the aggregation with the mean, which is motivated by applications to Earth science.
  arXiv  Detail & Related papers  (2024-06-12T08:30:16Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
  We propose IAC (Instance-Adaptive Clustering), the first algorithm whose performance matches the instance-specific lower bounds both in expectation and with high probability.<n>IAC maintains an overall computational complexity of $ mathcalO(n, textpolylog(n) $, making it scalable and practical for large-scale problems.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• An Algorithm and Complexity Results for Causal Unit Selection [16.307996243413967]
  Unit selection problem aims to identify objects, called units, that are most likely to exhibit a desired mode of behavior when subjected to stimuli. We propose the first exact algorithm for finding optimal units given a broad class of causal objective functions and a fully specified structural causal model.
  arXiv  Detail & Related papers  (2023-02-28T08:46:51Z)
• Expanding the class of global objective functions for dissimilarity-based hierarchical clustering [0.0]
  We introduce a broad new class of objective functions which satisfy desirable properties studied in prior work. Many common agglomerative and divisive clustering methods are shown to be greedy algorithms for these objectives.
  arXiv  Detail & Related papers  (2022-07-28T20:50:43Z)
• Gradient Based Clustering [72.15857783681658]
  We propose a general approach for distance based clustering, using the gradient of the cost function that measures clustering quality. The approach is an iterative two step procedure (alternating between cluster assignment and cluster center updates) and is applicable to a wide range of functions.
  arXiv  Detail & Related papers  (2022-02-01T19:31:15Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• An objective function for order preserving hierarchical clustering [0.0]
  We present a theory and an objective function for similarity-based hierarchical clustering of probabilistic partial orders.<n>Specifically, given elements $x le y$ in the partial order, and their respective clusters $[x]$ and $[y]$, the theory yields an order relation $le'$ on the clusters such that $[x]le'[y]$.
  arXiv  Detail & Related papers  (2021-09-09T13:35:01Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.