  In deep learning (DL) the instability phenomenon is widespread and well
documented, most commonly using the classical measure of stability, the
Lipschitz constant. While a small Lipchitz constant is traditionally viewed as
guarantying stability, it does not capture the instability phenomenon in DL for
classification well. The reason is that a classification function -- which is
the target function to be approximated -- is necessarily discontinuous, thus
having an 'infinite' Lipchitz constant. As a result, the classical approach
will deem every classification function unstable, yet basic classification
functions a la 'is there a cat in the image?' will typically be locally very
'flat' -- and thus locally stable -- except at the decision boundary. The lack
of an appropriate measure of stability hinders a rigorous theory for stability
in DL, and consequently, there are no proper approximation theoretic results
that can guarantee the existence of stable networks for classification
functions. In this paper we introduce a novel stability measure
$\mathscr{S}(f)$, for any classification function $f$, appropriate to study the
stability of discontinuous functions and their approximations. We further prove
two approximation theorems: First, for any $\epsilon > 0$ and any
classification function $f$ on a \emph{compact set}, there is a neural network
(NN) $\psi$, such that $\psi - f \neq 0$ only on a set of measure $< \epsilon$,
moreover, $\mathscr{S}(\psi) \geq \mathscr{S}(f) - \epsilon$ (as accurate and
stable as $f$ up to $\epsilon$). Second, for any classification function $f$
and $\epsilon > 0$, there exists a NN $\psi$ such that $\psi = f$ on the set of
points that are at least $\epsilon$ away from the decision boundary.
