  We consider in this paper the optimal approximations of convex univariate
functions with feed-forward Relu neural networks. We are interested in the
following question: what is the minimal approximation error given the number of
approximating linear pieces? We establish the necessary and sufficient
conditions and uniqueness of optimal approximations, and give lower and upper
bounds of the optimal approximation errors. Relu neural network architectures
are then presented to generate these optimal approximations. Finally, we
propose an algorithm to find the optimal approximations, as well as prove its
convergence and validate it with experimental results.
