  Training a one-node neural network with ReLU activation function
(One-Node-ReLU) is a fundamental optimization problem in deep learning. In this
paper, we begin with proving the NP-hardness of training One-Node-ReLU. We then
present an approximation algorithm to solve One-Node-ReLU whose running time is
$\mathcal{O}(n^k)$ where $n$ is the number of samples, $k$ is a predefined
integral constant. Except $k$, this algorithm does not require pre-processing
or tuning of parameters. We analyze the performance of this algorithm under
various regimes. First, given any arbitrary set of training sample data set, we
show that the algorithm guarantees a $\frac{n}{k}$-approximation for training
One-Node-ReLU problem. As a consequence, in the realizable case (i.e. when the
training error is zero), this approximation algorithm achieves the global
optimal solution for the One-Node-ReLU problem. Second, we assume that the
training sample data is obtained from an underlying one-node neural network
with ReLU activation function, where the output is perturbed by a Gaussian
noise. In this regime, we show that the same approximation algorithm guarantees
a much better asymptotic approximation ratio which is independent of the number
of samples $n$. Finally, we conduct extensive empirical studies and arrive at
two conclusions. One, the approximation algorithm together with some heuristic
performs better than gradient descent algorithm. Two, the solution of the
approximation algorithm can be used as starting point for gradient descent -- a
combination that works significantly better than gradient descent.
