Faster PAC Learning and Smaller Coresets via Smoothed Analysis

Abstract

PAC-learning usually aims to compute a small subset ($\epsilon$-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 $\epsilon \in (0,1)$. Coresets generalize this idea to support multiplicative error $1\pm \epsilon$. Inspired by smoothed analysis, we suggest a natural generalization: approximate the \emph{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 $\epsilon$-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.

References in corpus (8)

• Using coarse GPS data to quantify city-scale transportation system resilience to extreme events
• Optimal approximate matrix product in terms of stable rank
• A New Generalization of Chebyshev Inequality for Random Vectors
• A Derandomized Sparse Johnson-Lindenstrauss Transform
• Large Deviations of Vector-valued Martingales in 2-Smooth Normed Spaces
• On the Sensitivity of Shape Fitting Problems
• Introduction to Coresets: Accurate Coresets
• Tight Sensitivity Bounds For Smaller Coresets

Cited by in corpus (3)

• Compressed Deep Networks: Goodbye SVD, Hello Robust Low-Rank Approximation
• Coresets for Decision Trees of Signals
• Introduction to Coresets: Approximated Mean