  Many results in recent years established polynomial time learnability of
various models via neural networks algorithms. However, unless the model is
linear separable, or the activation is a polynomial, these results require very
large networks -- much more than what is needed for the mere existence of a
good predictor.
  In this paper we prove that SGD on depth two neural networks can memorize
samples, learn polynomials with bounded weights, and learn certain kernel
spaces, with near optimal network size, sample complexity, and runtime. In
particular, we show that SGD on depth two network with
$\tilde{O}\left(\frac{m}{d}\right)$ hidden neurons (and hence $\tilde{O}(m)$
parameters) can memorize $m$ random labeled points in $\mathbb{S}^{d-1}$.
