# Coresets For Monotonic Functions with Applications to Deep Learning.

Coreset (or core-set) in this paper is a small weighted \emph{subset} $Q$ ofthe input set $P$ with respect to a given \emph{monotonic} function$f:\mathbb{R}\to\mathbb{R}$ that \emph{provably} approximates its fitting loss$\sum_{p\in P}f(p\cdot x)$ to \emph{any} given $x\in\mathbb{R}^d$. Using $Q$ wecan obtain approximation to $x^*$ that minimizes this loss, by running\emph{existing} optimization algorithms on $Q$. We provide: (i) a lower boundthat proves that there are sets with no coresets smaller than $n=|P|$ , (ii) aproof that a small coreset of size near-logarithmic in $n$ exists for\emph{any} input $P$, under natural assumption that holds e.g. for logisticregression and the sigmoid activation function. (iii) a generic algorithm thatcomputes $Q$ in $O(nd+n\log n)$ expected time, (iv) novel technique forimproving existing deep networks using such coresets, (v) extensiveexperimental results with open code.oving existing deep networks using suchcoresets, (v) extensive experimental results with open code.