Improved Learning with Structure: Fine-Grained Complexity of Minimum Consistent Subset

R. Ganian M. Vasilakis Simon Wietheger

Jul 2026 · arXiv.org · Vol abs/2607.28240 · 0 citations · 28 references

Computer Science

TL;DR

A comprehensive fine-grained complexity map of MCS on both unweighted and weighted graphs is developed and the results strictly delineate the algorithmic boundaries of consistent subset selection across diverse metric structures.

Abstract

Instance selection is a vital technique for mitigating the computational bottlenecks of nearest-neighbor classification in large-scale supervised clustering. A classical theoretical formulation of this objective is the Minimum Consistent Subset (MCS) problem. While recent research has explored its complexity on unweighted graphs to uncover structural boundaries of tractability, arbitrary metric spaces are much more accurately modeled by (edge-)weighted graphs. In this paper, we develop a comprehensive fine-grained complexity map of MCS on both unweighted and weighted graphs. As our main result, we introduce a $3^{c \cdot(\mathrm{tw}+1)}\cdot n^{\mathrm{tw}+\mathcal{O}(1)}$ algorithm for $n$-vertex $c$-colored MCS instances on weighted graphs of treewidth $\mathrm{tw}$, substantially improving upon the previous state-of-the-art algorithm for unweighted MCS on trees both in terms of generality and running time. We complement this positive result with a series of lower bounds that rule out asymptotic improvements to the running time for both weighted and unweighted graphs under the Exponential Time Hypothesis (ETH). Moreover, we improve the recent slightly superexponential vertex-cover based algorithm for unweighted MCS (AAAI 2026) to a single-exponential one, and rule out further improvements to subexponential running times under the ETH. Together, our results strictly delineate the algorithmic boundaries of consistent subset selection across diverse metric structures.

DOI arXiv Semantic Scholar

View source

Similar papers

Preprint Aug 2026

Sparse PPMI Graph Averaging for Random Indexing Embeddings

A specific sparse post-processing pipeline for Random Indexing on kinship analogies in a small fairytales corpus is studied; the results do not establish a generally effective embedding method.

S. Loganathan, Gokul Anand, A. B. Bo et al. · 0 citations

Preprint Jul 2026

Lloyd's $K$-Means Clustering Algorithm Is Frank-Wolfe in Disguise

Lloyd's $K$-means algorithm, also known as na\"{i}ve $K$-means, is a widely used ad hoc optimization heuristic, designed to minimize the sum of squared errors (SSE) across all $K$-partitions of a dataset via iterative cluster refinement. In this work, we establish a novel connection between Lloyd's algorithm and the Frank-Wolfe (FW) algorithm, a prominent first-order method for projection-free optimization. We demonstrate that Lloyd's algorithm is a special case of FW. Leveraging recent advances in FW methods for concave objectives, we derive a non-asymptotic $\mathcal{O}(1/t)$ convergence rate to a local minimum of the SSE objective. To account for empty clusters, an outcome possible under Lloyd's greedy assignment, we develop an FW variant for semismooth objectives while retaining the same convergence rate that is solely controlled by the initial SSE value. We illustrate our findings with a simulation study for spherical Gaussian mixtures and a real-world image segmentation dataset.

Michael Pokojovy, J. Jobe, Simon Lacoste-Julien · 0 citations

Jul 2026

Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue

This work refine the existing parameter estimation guarantees under the fatness assumption, improving the prior sample complexity to $O( \log n / \epsilon^2)$ for $\ell_\infty$-recovery, matching the untruncated minimax rate.

Rohan Chauhan, Ioannis Panageas · arXiv.org · 0 citations

Preprint Aug 2026

Efficient Coreset Selection via K-Nearest Neighbor Graphs

Experiments show that KNNG-CS achieves accuracy comparable to representative gradient-approximation coreset methods, while reducing selection time by $2.3\times$-$41.2\times$ and peak memory to $0.3\%$-$7.5\%$ of the baselines.

Yingfan Liu, Leiyu Zhang, Jiadong Xie et al. · 0 citations

Preprint Jul 2026

Finding Adam in noisy trees

It is proved that, as long as $p=o(\log n /n)$, for any $\varepsilon>0$, one can construct a confidence set of vertices of size $K(\varepsilon)$ that depends only on $\varepsilon$ and not on $n$, such that it contains the root with probability at least $1-\varepsilon$.

Luc Devroye, Gábor Lugosi, Neeladri Maitra · 1 citation · ⚡1

Preprint Jul 2026

Hierarchical $\mathcal{F}$-Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs

The framework applies whenever the corresponding flat clustering problem, which is called Hierarchical Clustering, admits a natural ILP formulation together with a rounding procedure with provable approximation guarantees, and it is shown that both Hierarchical Clustering into trees and into bounded diameter graphs cannot be approximated within any constant factor under the Small Set Expansion Hypothesis.

Michal Szyfelbein, D. Dereniowski · 0 citations