Optimal Approximation of Zonoids and Uniform Approximation by Shallow Neural Networks

Abstract We study the following two related problems. The first is to determine to what error an arbitrary zonoid in $${\mathbb {R}}^{d+1}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>R</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> </mml:math> can be approximated in the Hausdorff distance by a sum of n line segments. The second is to determine optimal approximation rates in the uniform norm for shallow ReLU $$^k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mmultiscripts> <mml:mrow/> <mml:mrow/> <mml:mi>k</mml:mi> </mml:mmultiscripts> </mml:math> neural networks on their variation spaces. The first of these problems has been solved for $$d\ne 2,3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>≠</mml:mo> <mml:mn>2</mml:mn> <mml:mo>,</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> , but when $$d=2,3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>=</mml:mo> <mml:mn>2</mml:mn> <mml:mo>,</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> a logarithmic gap between the best upper and lower bounds remains. We close this gap, which completes the solution in all dimensions. For the second problem, our techniques significantly improve upon existing approximation rates when $$k\ge 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , and enable uniform approximation of both the target function and its derivatives.