Most Neural Networks Are Almost Learnable
Abstract
We present a PTAS for learning random constant-depth networks. We show that for any fixed $\epsilon>0$ and depth $i$, there is a poly-time algorithm that for any distribution on $\sqrt{d} \cdot \mathbb{S}^{d-1}$ learns random Xavier networks of depth $i$, up to an additive error of $\epsilon$. The algorithm runs in time and sample complexity of $(\bar{d})^{\mathrm{poly}(\epsilon^{-1})}$, where $\bar d$ is the size of the network. For some cases of sigmoid and ReLU-like activations the bound can be improved to $(\bar{d})^{\mathrm{polylog}(\epsilon^{-1})}$, resulting in a quasi-poly-time algorithm for learning constant depth random networks.
Cite
Text
Daniely et al. "Most Neural Networks Are Almost Learnable." Neural Information Processing Systems, 2023.Markdown
[Daniely et al. "Most Neural Networks Are Almost Learnable." Neural Information Processing Systems, 2023.](https://mlanthology.org/neurips/2023/daniely2023neurips-most/)BibTeX
@inproceedings{daniely2023neurips-most,
title = {{Most Neural Networks Are Almost Learnable}},
author = {Daniely, Amit and Srebro, Nati and Vardi, Gal},
booktitle = {Neural Information Processing Systems},
year = {2023},
url = {https://mlanthology.org/neurips/2023/daniely2023neurips-most/}
}