COLT 2021 papers:

1) Size and Depth Separation in Approximating Benign Functions with Neural Networks - https://arxiv.org/pdf/2102.00314.pdf

As we show, this problem is more challenging than the corresponding problem for non-benign functions. We give complexity-theoretic barriers to showing depth-lower-bounds: Proving existence of a benign function that cannot be approximated by polynomial-sized networks of depth 4 would settle longstanding open problems in computational complexity

2) A law of robustness for two-layers neural networks - https://arxiv.org/pdf/2009.14444.pdf

We initiate the study of the inherent tradeoffs between the size of a neural network and its robustness, as measured by its Lipschitz constant. We make a precise conjecture that, for any Lipschitz activation function and for most datasets, any two-layers neural network with k neurons that perfectly fit the data must have its Lipschitz constant larger (up to a constant) than p n/k where n is the number of datapoints

3) On the Approximation Power of Two-Layer Networks of Random ReLUs - https://arxiv.org/pdf/2102.02336.pdf

This paper considers the following question: how well can depth-two ReLU networks with randomly initialized bottom-level weights represent smooth functions? We give near-matching upperand lower-bounds for L2-approximation in terms of the Lipschitz constant, the desired accuracy, and the dimension of the problem, as well as similar results in terms of Sobolev norms.

4) The Connection Between Approximation, Depth Separation an d Learnability in Neural Networks - https://arxiv.org/pdf/2102.00434.pdf

In this work we study the intricate connection between learnability and approximation capacity. We show that learnability with deep networks of a target function depends on the ability of simpler classes to approximate the target. Specifically, we show that a necessary condition for a function to be learnable by gradient descent on deep neural networks is to be able to approximate the function, at least in a weak sense, with shallow neural networks