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.

Function values are, in some sense, “almost as good” as general linear information for L2-approximation (optimal recovery, data assimilation) of functions from a reproducing kernel Hilbert space. This was recently proved by new upper bounds on the sampling numbers under the assumption that the singular values of the embedding of this Hilbert space into L2 are square-summable. Here we mainly prove new lower bounds. In particular we prove that the sampling numbers behave worse than the approximation numbers for Sobolev spaces with small smoothness. Hence there can be a logarithmic gap also in the case where the singular numbers of the embedding are square-summable. We first prove new lower bounds for the integration problem, again for rather classical Sobolev spaces of periodic univariate functions.

BACKGROUND: High-throughput proteomics techniques, such as mass spectrometry (MS)-based approaches, produce very high-dimensional data-sets. In a clinical setting one is often interested in how mass spectra differ between patients of different classes, for example spectra from healthy patients vs. spectra from patients having a particular disease. Machine learning algorithms are needed to (a) identify these discriminating features and (b) classify unknown spectra based on this feature set. Since the acquired data is usually noisy, the algorithms should be robust against noise and outliers, while the identified feature set should be as small as possible. RESULTS: We present a new algorithm, Sparse Proteomics Analysis (SPA), based on the theory of compressed sensing that allows us to identify a minimal discriminating set of features from mass spectrometry data-sets. We show (1) how our method performs on artificial and real-world data-sets, (2) that its performance is competitive with standard (and widely used) algorithms for analyzing proteomics data, and (3) that it is robust against random and systematic noise. We further demonstrate the applicability of our algorithm to two previously published clinical data-sets.

Support vector machines (SVMs) with the ℓ1-penalty became a standard tool in the analysis of highdimensional classification problems with sparsity constraints in many applications, including bioinformatics and signal processing. We give non-asymptotic results on the performance of ℓ1-SVM in identification of sparse classifiers. We show that an N-dimensional s-sparse classification vector can be (with high probability) well approximated from only O(s log(N)) Gaussian trials. We derive similar estimates also in the presence of misclassifications and for the so-called doubly regularized SVM, which combines the ℓ1- and the ℓ2-penalty. Similar bounds were obtained earlier in the analysis of LASSO and 1-Bit compressed sensing.

This paper presents a simple randomised algorithm for recovering high-dimensional sparse functions, i.e. functions ƒ : [0, 1]d→ ℝ which depend effectively only on k out of d variables, meaning ƒ(x1, …, xd) = g(xi1, …, xik), where the indices 1 ≤ i1< i2< … < ik≤ d are unknown. It is shown that (under certain conditions on g) this algorithm recovers the k unknown coordinates with probability at least 1–6 exp(−L) using only O(k(L+log k)(L+log d)) samples of ƒ.