Breaking the Curse of Dimensionality with Distributed Neural Computation
Haitz Sáez de Ocáriz Borde Takashi Furuya Anastasis Kratsios Marc T. Law
We present a theoretical approach to overcome the curse of dimensionality
using a neural computation algorithm which can be distributed across several
machines. Our modular distributed deep learning paradigm, termed \textit{neural
pathways}, can achieve arbitrary accuracy while only loading a small number of
parameters into GPU VRAM. Formally, we prove that for every error level
$\varepsilon>0$ and every Lipschitz function $f:[0,1]^n\to \mathbb{R}$, one can
construct a neural pathways model which uniformly approximates $f$ to
$\varepsilon$ accuracy over $[0,1]^n$ while only requiring networks of
$\mathcal{O}(\varepsilon^{-1})$ parameters to be loaded in memory and
$\mathcal{O}(\varepsilon^{-1}\log(\varepsilon^{-1}))$ to be loaded during the
forward pass. This improves the optimal bounds for traditional non-distributed
deep learning models, namely ReLU MLPs, which need
$\mathcal{O}(\varepsilon^{-n/2})$ parameters to achieve the same accuracy. The
only other available deep learning model that breaks the curse of
dimensionality is MLPs with super-expressive activation functions. However, we
demonstrate that these models have an infinite VC dimension, even with bounded
depth and width restrictions, unlike the neural pathways model. This implies
that only the latter generalizes. Our analysis is validated experimentally in
both regression and classification tasks, demonstrating that our model exhibits
superior performance compared to larger centralized benchmarks.