REVIEW 7 cited by
New Frameworks for Offline and Streaming Coreset Constructions
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
A coreset for a set of points is a small subset of weighted points that approximately preserves important properties of the original set. Specifically, if $P$ is a set of points, $Q$ is a set of queries, and $f:P\times Q\to\mathbb{R}$ is a cost function, then a set $S\subseteq P$ with weights $w:P\to[0,\infty)$ is an $\epsilon$-coreset for some parameter $\epsilon>0$ if $\sum_{s\in S}w(s)f(s,q)$ is a $(1+\epsilon)$ multiplicative approximation to $\sum_{p\in P}f(p,q)$ for all $q\in Q$. Coresets are used to solve fundamental problems in machine learning under various big data models of computation. Many of the suggested coresets in the recent decade used, or could have used a general framework for constructing coresets whose size depends quadratically on what is known as total sensitivity $t$. In this paper we improve this bound from $O(t^2)$ to $O(t\log t)$. Thus our results imply more space efficient solutions to a number of problems, including projective clustering, $k$-line clustering, and subspace approximation. Moreover, we generalize the notion of sensitivity sampling for sup-sampling that supports non-multiplicative approximations, negative cost functions and more. The main technical result is a generic reduction to the sample complexity of learning a class of functions with bounded VC dimension. We show that obtaining an $(\nu,\alpha)$-sample for this class of functions with appropriate parameters $\nu$ and $\alpha$ suffices to achieve space efficient $\epsilon$-coresets. Our result implies more efficient coreset constructions for a number of interesting problems in machine learning; we show applications to $k$-median/$k$-means, $k$-line clustering, $j$-subspace approximation, and the integer $(j,k)$-projective clustering problem.
Forward citations
Cited by 7 Pith papers
-
Provable Pruning for Efficient 3D Gaussian Splatting via Coresets
3DGS admits resolution-dependent multiplicative coresets via sensitivity sampling (impossible unrestricted), and the resulting prune rule is SOTA under no or very short finetuning.
-
Tight Sensitivity Bounds For Smaller Coresets
New algorithms compute provably tight sensitivity bounds for matrix rows, yielding smaller coresets for LMS approximation of affine k-subspaces via an iterative exact method and a dimensionality-reduction trick.
-
Sensitivity Sampling with Predictions for k-Means Clustering
Predicted centers from prior snapshots enable sensitivity-sampling coresets for k-means that match optimal size bounds under coarser approximations and deliver better cost-runtime tradeoffs on data sequences.
-
Efficient Test-Time Finetuning of LLMs via Convex Reconstruction and Gradient Caching
HullFT performs test-time finetuning by sparse convex reconstruction of query embeddings followed by gradient caching on repeated examples, yielding better quality-efficiency tradeoffs than prior TTFT methods.
-
Creating Robust and Fair Graph Structures for Connectivity and Clustering
The thesis gives the first non-trivial dual fault-tolerant pairwise reachability preservers of size O(n^{4/3}|P|^{1/3}) and new approximation algorithms plus a streaming method for fair clustering in graphs.
-
Sketched MinDist
MinDist sketches using O(d/ε²) points preserve relative error for hyperplanes and Õ((L/ρ)·1/ε²) points for 2D shapes with min-distance ρ in domain L, with k³ factors and exact reconstruction for k-piece trajectories.
-
The Adversarial Robustness of Sketching and Streaming Algorithms
A survey monograph unifying the field of adversarially robust streaming: near-optimal robustness for insertion-only streams, poly(n)-space impossibility for turnstile linear sketches, and crypto-based white-box algorithms.
Discussion (0). Sign in to comment.