Coresets For Monotonic Functions with Applications to Deep Learning.

RSS Source
Authors
Elad Tolochinsky, Dan Feldman

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.

Stay in the loop.

Subscribe to our newsletter for a weekly update on the latest podcast, news, events, and jobs postings.