Algorithms and Complexity for Continuous Problems

In this talk, we discuss existence of global minima in optimisation problems over shallow neural networks. More explicitly, the function class over which we minimise is the family of all functions that can be expressed as artificial residual or feedforward neural networks with one hidden layer featuring a specified number of neurons with ReLU (or Leaky ReLU) activation. We give existence results. Moreover, we provide counterexamples that illustrate the relevance of the assumptions imposed in the theorems.

The mean squared error is one of the standard loss functions in supervised machine learning. However, calculating this loss for enormous data sets can be computationally demanding. Modifying a earlier approach [1], we present algorithms to reduce extensive data sets to a smaller size using rank-1 lattice rules. With this compression strategy in the precomputation step, every lattice point gets a pair of weights depending on the original data and responses, representing its relative importance. As a result, the compressed data makes iterative loss calculations in optimization steps much faster. The proposed compression strategy is highly beneficial for regression problems without an analytical solution. Our derivation of the formulas for the weights assumes that input functions have a convergent Fourier series and that the relevant Fourier coefficients form a hyperbolic cross. Accordingly, we have analyzed our algorithms’ error for functions whose Fourier coefficients decay sufficiently fast such that they lie in Wiener algebras.

In the framework of Information-Based Complexity we consider the adaption problem for linear solution operators in the randomized setting. Along with surveying recent advances we discuss a number of remaining/arising/related open questions.

The results presented are contained in the following papers:

Neural graphics primitives, parameterized by fully connected neural networks, can be costly to train and evaluate. We reduce this cost with a versatile new input encoding that permits the use of a smaller network without sacrificing quality, thus significantly reducing the number of floating point and memory access operations: a small neural network is augmented by a multiresolution hash table of trainable feature vectors whose values are optimized through stochastic gradient descent. The multiresolution structure allows the network to disambiguate hash collisions, making for a simple architecture that is trivial to parallelize on modern GPUs.

It is well-known that the integration problem as well as the problem of sampling recovery in the $L_2$-norm suffer from the curse of dimensionality on many classical function classes. This includes unweighted Korobov spaces (Sobolev spaces with mixed smoothness) as well as classical smoothness classes such as Hölder classes or the classes $C^k({[0,1]}^d)$. We show that those problems become (polynomially) tractable, even for $L_p$ approximation with , if we further impose the condition that the sum of Fourier coefficients is bounded.

The classes where we obtain tractability are unweighted (invariant under a reordering of the variables) and bigger than the corresponding weighted Korobov spaces. Tractability is achieved by the use of non-linear algorithms, while linear algorithms cannot do the job.

In fact, the tractability result is a relatively simple implication of powerful results by Rauhut and Ward [Appl. Comput. Harmon. Anal. 40 (2016), pp. 321-351] on ${\mathrm{\ell }}_1$-minimization. The approach is not limited to the Fourier system, but it remains to be seen whether any “interesting” classes of nonperiodic functions can be tackled.

The information complexity of the problem of approximating an operator $S_d:{ℱ}_d\to {𝒢}_d$ for normed spaces ${ℱ}_d$ and ${𝒢}_d$ is defined as the minimal number $\mathrm{comp}(\epsilon ,d)$ of information evaluations needed to find an $\epsilon$-approximation. A large literature specifies conditions under which the information complexity for a sequence of numerical problems defined for dimensions $d\in \{1,2,\mathrm{\dots }\}$ grows at a moderate rate when the error threshold $\epsilon$ decreases and/or the dimension increases, i.e., the sequence of problems is tractable.

In this talk, we give an overview of basic ideas in tractability analysis, highlight classical results for linear problems defined on Hilbert spaces, and outline some more recent results on this subject.

We study the numerical integration of functions from isotropic Sobolev spaces $W_p^s({[0,1]}^d)$ using finitely many function evaluations within randomized algorithms, aiming for the smallest possible probabilistic error guarantee $\epsilon >0$ at confidence level $1-\delta \in (0,1)$. This error criterion is more challenging than the classical root-mean-squared error which is usually taken for Monte Carlo algorithms within information-based complexity and where only $n$ and $\epsilon$ are put in relation. For spaces consisting of continuous functions, non-linear Monte Carlo methods with optimal confidence properties have already been known, in few cases even linear methods that succeed in that regard.[1] In this talk we promote a method called stratified control variates (SCV), see [2], and by it show that already linear methods achieve optimal probabilistic error rates in the high smoothness regime without the need to adjust algorithmic parameters to the uncertainty $\delta$. We also analysed a version of SCV in the low smoothness regime where $W_p^s({[0,1]}^d)$ may contain functions with singularities. Here, we observe a polynomial dependence of the error on ${\delta }^{-1}$ which cannot be avoided for linear methods. This is worse than what is known to be possible using non-linear algorithms where only a logarithmic dependence on ${\delta }^{-1}$ occurs if we tune in for a specific value of $\delta$. This new way of looking at randomized integration still leaves many questions open, for instance, precise lower bounds for linear methods in the low smoothness regime, as well as universal methods or optimality in mixed-smoothness spaces.

We study the problem of scattered-data approximation on ${ℝ}^d$, where we have given sample points and the corresponding function evaluations. We compare two approaches. In the first one we transform functions on ${ℝ}^d$ to ${𝕋}^d$, apply an approximation based on hyperbolic wavelet regression and transform the resulting function back. In fact, we transform the sample points to points on ${𝕋}^d$, evaluate the periodic basis functions at these points, create a matrix and solve the matrix equation with an LSQR-algorithm to get an approximation.
The other approach involves random Fourier features, where we draw frequencies ${\omega }_j\in {ℝ}^d$ at random and learn coefficients $a_j$ from the given data to construct the approximant, i.e.

We give error estimates for both cases, involving different function spaces. We truncate the ANOVA decomposition to approximate high-dimensional functions of low effective dimension.

We discuss ideas which lead to recent improvements of upper bounds for the minimal dispersion of a point set in the unit cube and its inverse. We also discuss sharpness of bounds. The talk is partially based on a joint work with G. Livshyts.

A seminal result of Beck shows that for any set of $N$ points on the $d$-dimensional sphere, there always exists a spherical cap such that the number of points in the cap deviates from the expected value by at least $N^{(1/2-1/2d)}$. We refine the result by removing a layer of averaging: we show that, when $d$ is not $1mod4$, there exists a set of real numbers such that for each $r>0$ in the set one is always guaranteed to find a spherical cap with radius $r$ for which Beck’s result holds. The main ingredient is a generalization of the notion of badly approximable numbers to the setting of Gegenbauer polynomials, which we call Gegenbadly approximable numbers. These are fixed numbers $x$ such that the sequence of Gegenbauer polynomials evaluated at $x$ avoids being close to $0$ in a precise quantitative sense.

We consider compact composite linear operators in Hilbert space, where the composition is given by some compact operator followed by some non-compact one possessing a non-closed range. Focus is on the impact of the non-compact factor on the overall behavior of the decay rates of the singular values of the composition.

The kernel interpolant in a reproducing kernel Hilbert space is optimal in the worst-case sense among all approximations of a function using the same set of function values. In this talk, we compare two search criteria to construct lattice point sets for use in lattice-based kernel approximation. The first candidate, $P_n^{\ast }$, is based on the power function that appears in machine learning literature. The second candidate, $S_n^{\ast }$, is a search criterion used for generating lattices for approximation using truncated Fourier series. We find that the empirical difference in error between the lattices constructed using the two search criteria is marginal. The criterion $S_n^{\ast }$ is preferred as it is computationally more efficient and has a bound with a superior convergence rate.

We study the complexity of pathwise approximation in $p$-th mean of the solution of a stochastic differential equation at the final time based on finitely many evaluations of the driving Brownian motion. First, we briefly review the case of equations with globally Lipschitz continuous coefficients, for which an error rate of at least $1/2$ in terms of the number of evaluations of the driving Brownian motion is always guaranteed by using the equidistant Euler-Maruyama scheme. Then we illustrate that giving up global Lipschitz continuity may lead to non-polynomial error rates for the Euler-Maruyama scheme or even for any method based on finitely many evaluations of the driving Brownian motion. Finally, we turn to recent complexity results in the case of equations with a drift coefficient that is not globally Lipschitz continuous. Here we focus on scalar equations with a Lipschitz continuous diffusion coefficient and a drift coefficient that satisfies piecewise smoothness assumptions or has fractional Sobolev regularity.

Following Mishra, Rusch (2021) and Longo, Mishra, Rusch, Schwab (2021) we consider the so-called “generalization error” which describes how well a trained DNN can approximate a function on the whole domain. In fact this is just the L2 approximation error if measured in the L2-norm. We start from the assumption that the underlying function is periodic and in any Korobov space with smoothness alpha. This is motivated by the periodic model of the random diffusion field when doing uncertainty quantification.

Digital net is an important class of Quasi-Monte Carlo methods used for multidimensional integration. In the talk, I am going to show digital net randomized by linear scrambling and digital shift exhibits surprising concentration behavior. Taking the median of several digital net averages can exclude outliers and boost the convergence rate from nearly cubic to super-polynomial when the integrand is smooth. I will end with some discussions on the difficulties in building confidence intervals.

In the talk, I will present the results of our joint work with David Krieg, Mario Ullrich and Tino Ullrich [1] on the recovery of functions based on function evaluations.

The main emphasis is made on the uniform recovery, however we provide a method to transfer results for $L_2$-approximation to rather general seminorms (including $L_p$, $1\le p\le \mathrm{\infty }$). The underlying (least squares) algorithm is based on a random construction and subsampling based on the solution of the Kadison-Singer problem.

Besides an explicit bound for the corresponding sampling widths, we also obtain some interesting inequalities between the sampling, Kolmogorov and Gelfand widths. Namely, we show that there is an absolute constant $c>0$, such that for a compact topological space $D$ and a compact subset $F$ of $C(D)$ the following holds

The bound in (1) is optimal up to constants, also if we consider only convex and symmetric $F$ and replace the Kolmogorov width $d_n$ by the Gelfand width $c_n$ on the right hand side. This means, that there are linear algorithms using $2n$ samples that are as good as all algorithms using arbitrary linear information up to a factor of at most $\sqrt{n}$. A result that cannot be true without oversampling [2]. Moreover, our results imply that linear sampling algorithms are optimal up to a constant factor for many reproducing kernel Hilbert spaces.

We will present a version of randomized Euler algorithm for approximation of solutions of stochastic differential equations when the drift is in integral form. We will show upper estimates for the error and some lower bounds in the worst-case model. We will show some relationship of the randomized Euler algorithm with perturbed SGD used in machine learning.

In this survey we consider two basic computational problems, integration and $L^2$-approximation, for functions of countably infinite real variables. For motivation we briefly refer to stochastic models based on iid-sequences of random variables, e.g., series expansions of stochastic processes and random fields.

Thereafter we discuss appropriate cost models (information cost) for infinite-variate problems as well as the general structure of the functions spaces (RKHS of tensor product form) that have been studied so far. Finally, we present results (decay of the minimal errors) and key ingredients of the proofs for tensor products of weighted spaces and of spaces of increasing smoothness.

We study integration and approximation on reproducing kernel Hilbert spaces with Gaussian kernels of tensor product form. We find new results in the infinite-variate case, and we improve some known results in the finite-variate case.

Our most important tool is a close relation between Gaussian spaces and Hermite spaces of infinite smoothness and tensor product form.

This relation allows us to transform any algorithm for integration or approximation on the Gaussian space into an algorithm for the same problem on the Hermite space and vice versa, preserving error and cost, which means that known upper and lower error bounds for one function space setting also apply to the other setting.

Dispersion is a measure of equidistribution of point sets. We give a brief introduction and survey known results with focus on a large number of points compared to the dimension. From the literature on coverings of Euclidean space and convex body approximation, we deduce implications for the spherical case and point to open problems.

As high-dimensional problems become increasingly prevalent in many applications, the effective evaluation of these problems within the limits of our current technology poses a great hurdle due to the exponential increase in computational cost as dimensionality increases. One class of strategies for evaluating such problems efficiently are quasi-Monte Carlo (QMC) methods.

In this talk, we explore the effectiveness of multi-level quasi-Monte Carlo methods for approximating solutions to elliptic partial differential equations with stochastic coefficients that depend periodically on the stochastic parameters. In particular, we are interested in fast approximation using kernel-based lattice point interpolation. We present some regularity results, theory on the convergence properties of errors of such approximations and the results of numerical experiments.

This is a survey talk to describe several different problems in the broad framework of well-distributed point configurations. Problems discussed include: low-discrepancy sets of points, minimizers of energy functionals, greedy sequences, problems on the sphere $S^2$ and minimizer of the logarithmic energy as well as the connection to the crystallization conjecture.

Latent diffusion models excel at producing high-quality images from text. Yet, concerns appear about the lack of diversity in the generated imagery. To tackle this, we introduce Diverse Diffusion, a method for boosting image diversity beyond gender and ethnicity, spanning into richer realms, including color diversity. Diverse Diffusion is a general unsupervised technique that can be applied to existing text-to-image models. Our approach focuses on finding vectors in the Stable Diffusion latent space that are distant from each other. We generate multiple vectors in the latent space until we find a set of vectors that meet the desired distance requirements and the required batch size. To evaluate the effectiveness of our diversity methods, we conduct experiments examining various characteristics, including color diversity, LPIPS metric, and ethnicity/gender representation in images featuring humans. The results of our experiments emphasize the significance of diversity in generating realistic and varied images, offering valuable insights for improving text-to-image models. Through the enhancement of image diversity, our approach contributes to the creation of more inclusive and representative AI-generated art.

We also present genetic crossovers for combining latent variables into a better latent variable.

After the seminar, we start a cool collaboration with Carola, Stefan, Dmitry, Laurent, for producing fantastic point configurations in high-dimensional point spaces.

Joint work ESIEE and Meta.

In this talk we give an overview of some recent and not so recent developments in the area of approximation of functions based on function evaluations. The emphasis is on information-based complexity and the worst-case setting, i.e., we ask for the minimal number of information (aka measurements) needed by any algorithm to achieve a prescribed error for all inputs, basically ignoring implementation issues.

However, it turned out that in many cases, certain (unregularized) least squares methods based on “random” information, like function evaluations, can catch up with arbitrary algorithms based on arbitrary linear information, i.e., the best we can do theoretically.

Using techniques developed recently in the field of compressed sensing we show new upper bounds for general (nonlinear) sampling numbers of (quasi-)Banach smoothness spaces in $L_2$. In particular, we show that in relevant cases such as mixed and isotropic weighted Wiener classes or Sobolev spaces with mixed smoothness, sampling numbers in $L_2$ can be upper bounded by best n-term trigonometric widths in $L_{\mathrm{\infty }}$. We describe a recovery procedure from m function values based on $l_1$-minimization (basis pursuit denoising). With this method, a significant gain in the rate of convergence compared to recently developed linear recovery methods is achieved. In this deterministic worst-case setting we see an additional speed-up of $m^{-1/2}$ (up to log factors) compared to linear methods in case of weighted Wiener spaces. For their quasi-Banach counterparts even arbitrary polynomial speed-up is possible. Surprisingly, our approach allows to recover mixed smoothness Sobolev functions belonging on the $d$-torus with a logarithmically better rate of convergence than any linear method can achieve when and $d$ is large. This effect is not present for isotropic Sobolev spaces.

The pair correlation statistic measures the behavior of gaps between the first elements of a sequence on a local scale. Although a generic independent, identically distributed random sequence drawn from uniform distribution has so-called Poissonian pair correlations, there are only few explicitly known such examples. The main reason why they are difficult to find is that it is in general hard to calculate the pair correlation statistic. In this talk, we therefore concentrate on computational aspects of the pair correlation and present some possible approaches. For instance, geometric properties like the gap structure, an underlying lattice structure of the sequence or the discrepancy turn out to be useful tools. We also present some recent combinatorial results.

The fixed vector algorithm offers a very simple solution to the problem of producing a lattice-based randomised algorithm for numerical integration with the optimal randomised error. We shift the construction of the generating vector of the lattice to a precomputation so that the only randomised element is to choose the number of function evaluations from a suitable range. In the talk, we will look at the existence result for such a fixed generating vector, a method to construct the vector and finally look at how the algorithm can be generalised to work in the half-period cosine space and with a lower smoothness parameter.

We are considering approximation of the identical embedding of finite-dimensional spaces $S_M:{\mathrm{\ell }}_1^M\to {\mathrm{\ell }}_{\mathrm{\infty }}^M$ by randomized algorithms. We establish a lower bound on the $n$-th minimal error which is, roughly speaking, of the form: there exists an $\epsilon >0$ such that if for all $M\in \mathrm{N}$

then

Here $e^{\text{ran-non}}(n,S)$ denotes the $n$-th minimal error which can be obtained when using randomized non-adaptive algorithms. This has at least two interesting consequences:

1. 1.

   We are able to give an example of a sequence of linear problems for which the $n$-th minimal error for randomized adaptive algorithms decreases much faster than the minimal error for randomized non-adaptive algorithms-a phenomenon which was only recently observed by S.Heinrich in the context of vector-valued mean computation.

2. 2.

   It enables us to show that the only operators which can be arbitrarily well approximated by randomized non-adaptive algorithms are compact operators- i.e. exactly the same operators which can be arbitrarily well approximated by deterministic algorithms.

Let $F,G$ be normed spaces (over $ℝ$) and $S:F\to G$ be linear and bounded. Suppose that for each $f\in F$, we have $n$ pieces of adaptive information

based on linear and continuous functionals on $F$. Let $A=\phi \circ N:F\to G$ be a linear algorithm with $\phi :{ℝ}^n\to G$.

Can we find $N^{\mathrm{non}}(f)=(L_1(f),\mathrm{\dots },L_n(f)),f\in F$, where $L_1,\mathrm{\dots },L_n:F\to ℝ$ are linear and (linear) $\tilde{\phi }:{ℝ}^n\to G$ such that $A=\tilde{\phi }\circ N^{\mathrm{non}}$?

This basic problem was solved completely using elementary means in a discussion with David Krieg, Robert Kunsch and Marcin Wnuk during the seminar.

Consider the following test for pseudorandomness: to any distinct, real numbers $x_1,\mathrm{\dots },x_n$, we associate a 4-regular graph $G$ as follows: using $\pi$ to denote the permutation ordering the elements, , we build a graph on $\{1,\mathrm{\dots },n\}$ by connecting $i$ and $i+1$ (cyclically) and $\pi (i)$ and $\pi (i+1)$ (cyclically).

One reason why these graphs are interesting is the following result for the second eigenvalue ${\lambda }_2$ of the adjacency matrix of such a graph.

As it turns out, this graph construction can indeed be effectively used for understanding the strength of a random number generator: if the numbers are truly random, the arising graphs are random in a “near-”optimal way [3].

One could now wonder what happens to these graphs when the underlying real numbers are far from “random” and two canonical examples are the Kronecker sequence and the van der Corput sequence. Fig. 2 shows the type of graph obtained from the van der Corput sequence in base 2

We observe the emergence of some strange topological features that are currently unexplained.

New open problem arise after recent results on the power of standard information (function values), and more general classes $\mathrm{\Lambda }$, indicate that already under mild assumptions on $\mathrm{\Lambda }$ we might hope for optimal approximations, i.e., that the corresponding minimal errors are of the same order as minimal errors based on arbitrary information. Several of related open problems can be found in the survey paper [1], which was nearly finished during the Dagstuhl Seminar 23351. A (simple, and too optimistic) version of an open problem was presented at the seminar, and already disproved in a subsequent discussion with David Krieg and Erich Novak.