# Faster PAC Learning and Smaller Coresets via Smoothed Analysis

arXiv: https://arxiv.org/abs/2006.05441 · HTML: https://mlsanity.com/paper/2006.05441/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2020.

## Built on by (most cited first, 2 of 2)

- [Coresets for Decision Trees of Signals](https://mlsanity.com/paper/2110.03195/) (2021)
- [Introduction to Coresets: Approximated Mean](https://mlsanity.com/paper/2111.03046/) (2021)

## Abstract (arXiv)

PAC-learning usually aims to compute a small subset (varepsilon-sample/net) from n items, that provably approximates a given loss function for every query (model, classifier, hypothesis) from a given set of queries, up to an additive error varepsilon∈(0,1). Coresets generalize this idea to support multiplicative error 1±varepsilon. Inspired by smoothed analysis, we suggest a natural generalization: approximate the average (instead of the worst-case) error over the queries, in the hope of getting smaller subsets. The dependency between errors of different queries implies that we may no longer apply the Chernoff-Hoeffding inequality for a fixed query, and then use the VC-dimension or union bound. This paper provides deterministic and randomized algorithms for computing such coresets and varepsilon-samples of size independent of n, for any finite set of queries and loss function. Example applications include new and improved coreset constructions for e.g. streaming vector summarization [ICML'17] and k-PCA [NIPS'16]. Experimental results with open source code are provided.