Algorithm learns combinations of relu neural units quickly and accurately
Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time
Data Structures and AlgorithmsMachine Learning
Summary
This paper looks at how to efficiently learn certain kinds of simple neural networks made by adding together 'ReLU' units, which are basic building blocks in AI models. The authors created the first algorithm that can learn these networks quickly in terms of both running time and number of examples it needs, without making strong assumptions about the network. Their approach uses advanced math tools like tensors and special functions to identify and improve the components of the network step-by-step. This helps computers better understand the network’s structure with guaranteed accuracy.
What this means in practice
- •For machine learning engineers: Train neural network components made of ReLU units more efficiently and accurately without restrictive assumptions on weights.
- •For signal processing teams: Use this method to decompose complex signals modeled by sums of ReLU functions for clearer interpretation or processing.
Authors
Ilias Diakonikolas, Jelena Diakonikolas, Puqian Wang, Nikos Zarifis
Abstract
We study the fundamental problem of PAC learning positive linear combinations of $k$ arbitrary ReLU activations on $\mathbb{R}^d$ with respect to the Gaussian distribution, in $L_2$ loss. We give the first fully-polynomial time algorithm for this learning task. Specifically, our algorithm draws $\mathrm{poly}(d, k, 1/ε)$ samples, runs in $\mathrm{poly}(d, k, 1/ε)$ time, and outputs a hypothesis that is $ε$-close to the target concept with high probability. All prior algorithms for this problem require super-polynomial time in $k$ or $1/ε$, or leverage strong well-conditioned assumptions on the weight matrix. On a technical level, our approach develops a novel boosting procedure of a ``weak'' learner that recovers the hidden weight vectors to constant error, in a list-decodable manner. To develop this ``weak'' learning procedure, we leverage implicit tensor computation techniques to construct a low-degree filtering procedure based on Hermite tensors of the target function. This procedure amplifies separation among (clusters of) weight vectors to learn each of them to constant error. We then argue that the same procedure can be used for improving the estimation of hidden weight vectors, using gradient descent-like updates on the Euclidean sphere. A crucial ingredient of our algorithm is a pruning approach that ensures only relevant vectors that approximate the hidden weight vectors at target accuracy are maintained by the algorithm.