betaFeedback

WorksComputer Science

Fault Tolerant Coresets

Abstract

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 kk-means objective, where the cost of the input dataset with respect to a set of kk centers is the sum of squared distances from each point to its closest center. A kk-means ε\varepsilon-coreset ΩΩ satisfies cost(P,S)=(1±ε)cost(Ω,S)\mathrm{cost}(P,S)=(1\pm\varepsilon)\mathrm{cost}(Ω,S) for every set SS of kk centers, where PP denotes the input dataset. A long line of work has established near optimal ε\varepsilon-coreset size bounds for kk-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 ff weighted entries of an ε\varepsilon-coreset, can we recover an O(ε)O(\varepsilon)-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 O(fk/ε)O(fk/\varepsilon) yields a coreset that can be decoded into an O(ε)O(\varepsilon)-coreset after any ff 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 Ω(fk/ε)Ω(fk/\varepsilon). Our experiments demonstrate recovery under adversarial corruptions.

Paper details

vlnc:W_6cm94nr4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…