@averagewall already explained what depth 3 is. The explanation of poly time is a little bit lengthier. Let me briefly explain the PAC learning paradigm in the

@averagewall already explained what depth 3 is. The explanation of poly time is a little bit lengthier. Let me briefly explain the PAC learning paradigm in the context of this paper. Consider the set of all depth 3 neural networks with n dimensional input and k dimensional hidden layer whose weights have total norm 1. Let this set be called H. Note that this is a well defined set, parameterized by the weights of the neural networks. Let ∊ be an arbitrary positive error value and let δ be an arbitrary prob value. We are interested in ∊ ≈ 0 and δ ≈ 0. The solution of the PAC learning problem is an algorithm, say A, which takes a dataset D as input, generated from a dsitribution Π, and which runs in time that is polynomial in the size of D, and spits out a specific neural network h that lies in H. Furthermore, no matter what Π was, the probability that the neural net h, that A produced, has error that is at max ∊ above the optimal error achievable by any member of H, should be more than 1-δ. This is the PAC learning paradigm. The paper assumes that Π is a distribution over the n-dimensional unit sphere, so all examples have the same euclidean norm and constrains the weight vectors to have unit norm, AND WITH THESE ASSUMPTIONS, it gives a algorithm that requires |D| = poly(n, k, 1/∊) and runs in time poly(D).