← 研踪 PaperTrailarXiv:2611.17574 · v1
Fault Tolerant Coresets
首次提交 2026-11-13 06:53
版本更新 2026-11-13 06:53
雷达观测 2026-11-17 04:58
摘要
Coresets are small weighted summaries of large datasets that help quickly evaluate some loss objectives on the input dataset. We mainly focus on coresets for the -means objective, where the cost of the input dataset with respect to a set of centers is the sum of squared distances from each point to its closest center. A -means -coreset satisfies for every set of centers, where denotes the input dataset. A long line of work has established near optimal -coreset size bounds for -means. A key assumption in these works is that the coreset remains intact after construction. The question we ask is the following: if an adversary corrupts at most weighted entries of an -coreset, can we recover an -coreset via a decoding algorithm that is given only the corrupted coreset. This models situations where entries of the coreset can be corrupted during storage or transmission, and recovery must proceed without access to the original dataset. Our main result shows that increasing the usual coreset size by an additive yields a coreset that can be decoded into an -coreset after any adversarial corruptions. This bound is achieved by sensitivity sampling, a widely used method for constructing coresets. Our result is optimal in the sense that any fault tolerant coreset, whose decoding algorithm only keeps a subset of the points must also have size . Our experiments demonstrate recovery under adversarial corruptions.
作者备注:32 pages, 21 figures. NeurIPS 2026
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-13 06:53 · 最新观测版本
Fault Tolerant Coresets
Coresets are small weighted summaries of large datasets that help quickly evaluate some loss objectives on the input dataset. We mainly focus on coresets for the -means objective, where the cost of the input dataset with respect to a set of centers is the sum of squared distances from each point to its closest center. A -means -coreset satisfies for every set of centers, where denotes the input dataset. A long line of work has established near optimal -coreset size bounds for -means. A key assumption in these works is that the coreset remains intact after construction. The question we ask is the following: if an adversary corrupts at most weighted entries of an -coreset, can we recover an -coreset via a decoding algorithm that is given only the corrupted coreset. This models situations where entries of the coreset can be corrupted during storage or transmission, and recovery must proceed without access to the original dataset. Our main result shows that increasing the usual coreset size by an additive yields a coreset that can be decoded into an -coreset after any adversarial corruptions. This bound is achieved by sensitivity sampling, a widely used method for constructing coresets. Our result is optimal in the sense that any fault tolerant coreset, whose decoding algorithm only keeps a subset of the points must also have size . Our experiments demonstrate recovery under adversarial corruptions.
查看此版本解读 →查看此版本原文 ↗