We prove a sharp bound between sampling numbers and entropy numbers in the uniform norm for bounded convex sets of bounded functions.

In recent work concerned with the approximation and expressive powers of deep neural networks, Daubechies, DeVore, Foucart, Hanin, and Petrova introduced a system of piecewise linear functions, which can be easily reproduced by artificial neural networks with the ReLU activation function, and showed that it forms a Riesz basis of $L_2([0, 1])$. Their work was subsequently generalized to the multivariate setting by Schneider and Vybíral. In the work at hand, we show that this system serves as a Riesz basis also for Sobolev spaces $W^s([0,1]^d)$ and Barron classes ${\mathbb B}^s([0,1]^d)$ with smoothness $0\lt s\lt 1$. We apply this fact to re-prove some recent results on the approximation of functions from these classes by deep neural networks. Our proof method avoids using local approximations and also allows us to track the implicit constants as well as to show that we can avoid the curse of dimension. Moreover, we also study how well one can approximate Sobolev and Barron functions by neural networks if only function values are known.

Abstract The dispersion of a point set $$P\subset [0,1]^d$$ P⊂[0,1]d is the volume of the largest box with sides parallel to the coordinate axes, which does not intersectP. It was observed only recently that, for any $$\varepsilon >0$$ ε>0 , certain randomized constructions provide point sets with dispersion smaller than $$\varepsilon $$ ε and number of elements growing only logarithmically ind. Based on deep results from coding theory, we present explicit, deterministic algorithms to construct such point sets in time that is only polynomial ind. Note that, however, the running-time will be super-exponential in $$\varepsilon ^{-1}$$ ε-1 . Our construction is based on the apparently new insight that low-dispersion point sets can be deduced from solutions of certaink-restriction problems, which are well-known in coding theory.

In the first part we have shown that, for L2-approximation of functions from a separable Hilbert space in the worst-case setting, linear algorithms based on function values are almost as powerful as arbitrary linear algorithms if the linear widths are square-summable. That is, they achieve the same polynomial rate of convergence. In this sequel, we prove a similar result for separable Banach spaces and other classes of functions.

It was recently shown by D. Krieg and M. Ullrich that, for L2-approximation of functions from a reproducing kernel Hilbert space, function values are almost as powerful as arbitrary linear information if the approximation numbers are square-summable. That is, en≲1kn∑j≥knaj2withkn≍nln(n),where en are the sampling numbers and ak are the approximation numbers. In particular, if (ak)∈ℓ2, then en and an are of the same polynomial order. For this, we presented an explicit (weighted least squares) algorithm based on i.i.d. random points and proved that this works with positive probability. This implies the existence of a good deterministic sampling algorithm. Here, we present a modification of our proof that shows that the same algorithm works with probability at least 1−n−c for any given c>0.

We prove that the spectral gap of the Swendsen--Wang dynamics for the random-cluster model is larger than the spectral gap of a single-bond dynamics, which updates only a single edge per step. For this we give a representation of the algorithms on the joint (Potts/random-cluster) model. Furthermore we obtain upper and lower bounds on the mixing time of the single-bond dynamics on the discrete $d$-dimensional torus of side length $L$ at the Potts transition temperature for $q$ large enough that are exponential in $L^{d-1}$, complementing a result of Borgs, Chayes, and Tetali [Probab. Theory Related Fields, 152 (2012), pp. 509--557].