Search

A control in feedback form is derived for linear quadratic, time-invariant optimal control problems subject to parabolic partial differential equations with coefficients depending on a countably infinite number of uncertain parameters. It is shown that the Riccati-based feedback operator depends analytically on the parameters provided that the system operator depends analytically on the parameters, as is the case, for instance, in diffusion problems when the diffusion coefficient is parameterized by a Karhunen--Lo\`eve expansion. These novel parametric regularity results allow the application of quasi-Monte Carlo (QMC) methods to efficiently compute an a-priori chosen feedback law based on the expected value. Moreover, under moderate assumptions on the input random field, QMC methods achieve superior error rates compared to ordinary Monte Carlo methods, independently of the stochastic dimension of the problem. Indeed, our paper for the first time studies Banach-space-valued integration by higher-order QMC methods.

Digital nets provide an efficient way to generate integration nodes of quasi-Monte Carlo (QMC) rules. For certain applications, as e.g. in Uncertainty Quantification, we are interested in obtaining a speed-up in computing products of a matrix with the vectors corresponding to the nodes of a QMC rule. In the recent paper "The fast reduced QMC matrix-vector product" (J. Comput. Appl. Math. 440, 115642, 2024), a speed up was obtained by using so-called reduced lattices and row reduced digital nets. In this work, we propose a different multiplication algorithm where we exploit the repetitive structure of column reduced digital nets instead of row reduced digital nets. This method has advantages over the previous one, as it facilitates the error analysis when using the integration nodes in a QMC rule. We also provide an upper bound for the quality parameter of column reduced digital nets, and numerical tests to illustrate the efficiency of the new algorithm.

We give an overview of certain aspects of tractability analysis of multivariate problems. This paper is not intended to give a complete account of the subject, but provides an insight into how the theory works for particular types of problems. We mainly focus on linear problems on Hilbert spaces, and mostly allow arbitrary linear information. In such cases, tractability analysis is closely linked to an analysis of the singular values of the operator under consideration. We also highlight the more recent developments regarding exponential and generalized tractability. The theoretical results are illustrated by several examples throughout the article.

We consider linear problems in the worst case setting. That is, given a linear operator and a pool of admissible linear measurements, we want to approximate the values of the operator uniformly on a convex and balanced set by means of algorithms that use at most $n$ such measurements. It is known that, in general, linear algorithms do not yield an optimal approximation. However, as we show in this paper, an optimal approximation can always be obtained with a homogeneous algorithm. This is of interest to us for two reasons. First, the homogeneity allows us to extend any error bound on the unit ball to the full input space. Second, homogeneous algorithms are better suited to tackle problems on cones, a scenario that is far less understood than the classical situation of balls. We use the optimality of homogeneous algorithms to prove solvability for a family of problems defined on cones. We illustrate our results by several examples.

A large literature specifies conditions under which the information complexity for a sequence of numerical problems defined for dimensions $1, 2, \ldots$ grows at a moderate rate, i.e., the sequence of problems is tractable. Here, we focus on the situation where the space of available information consists of all linear functionals and the problems are defined as linear operator mappings between Hilbert spaces. We unify the proofs of known tractability results and generalize a number of existing results. These generalizations are expressed as five theorems that provide equivalent conditions for (strong) tractability in terms of sums of functions of the singular values of the solution operators.

Let $f:[0,1]^d\to\mathbb{R}$ be a completely monotone integrand as defined by Aistleitner and Dick (2015) and let points $\boldsymbol{x}_0,\dots,\boldsymbol{x}_{n-1}\in[0,1]^d$ have a non-negative local discrepancy (NNLD) everywhere in $[0,1]^d$. We show how to use these properties to get a non-asymptotic and computable upper bound for the integral of $f$ over $[0,1]^d$. An analogous non-positive local discrepancy (NPLD) property provides a computable lower bound. It has been known since Gabai (1967) that the two dimensional Hammersley points in any base $b\ge2$ have non-negative local discrepancy. Using the probabilistic notion of associated random variables, we generalize Gabai's finding to digital nets in any base $b\ge2$ and any dimension $d\ge1$ when the generator matrices are permutation matrices. We show that permutation matrices cannot attain the best values of the digital net quality parameter when $d\ge3$. As a consequence the computable absolutely sure bounds we provide come with less accurate estimates than the usual digital net estimates do in high dimensions. We are also able to construct high dimensional rank one lattice rules that are NNLD. We show that those lattices do not have good discrepancy properties: any lattice rule with the NNLD property in dimension $d\ge2$ either fails to be projection regular or has all its points on the main diagonal. Complete monotonicity is a very strict requirement that for some integrands can be mitigated via a control variate.

We study the approximation of integrals $\int_D f(\boldsymbol{x}^\top A) \mathrm{d} \mu(\boldsymbol{x})$, where $A$ is a matrix, by quasi-Monte Carlo (QMC) rules $N^{-1} \sum_{k=0}^{N-1} f(\boldsymbol{x}_k^\top A)$. We are interested in cases where the main cost arises from calculating the products $\boldsymbol{x}_k^\top A$. We design QMC rules for which the computation of $\boldsymbol{x}_k^\top A$, $k = 0, 1, \ldots, N-1$, can be done fast, and for which the error of the QMC rule is similar to the standard QMC error. We do not require that $A$ has any particular structure. For instance, this approach can be used when approximating the expected value of a function with a multivariate normal random variable with a given covariance matrix, or when approximating the expected value of the solution of a PDE with random coefficients. The speed-up of the computation time is sometimes better and sometimes worse than the fast QMC matrix-vector product from [Dick, Kuo, Le Gia, and Schwab, Fast QMC Matrix-Vector Multiplication, SIAM J. Sci. Comput. 37 (2015)]. As in that paper, our approach applies to (polynomial) lattice point sets, but also to digital nets (we are currently not aware of any approach which allows one to apply the fast method from the aforementioned paper of Dick, Kuo, Le Gia, and Schwab to digital nets). Our method does not use FFT, instead we use repeated values in the quadrature points to derive a reduction in the computation time. This arises from the reduced CBC construction of lattice rules and polynomial lattice rules. The reduced CBC construction has been shown to reduce the computation time for the CBC construction. Here we show that it can also be used to also reduce the computation time of the QMC rule.

In this paper, we study an efficient algorithm for constructing point sets underlying quasi-Monte Carlo integration rules for weighted Korobov classes. The algorithm presented is a reduced fast component-by-component digit-by-digit (CBC-DBD) algorithm, which useful for to situations where the weights in the function space show a sufficiently fast decay. The advantage of the algorithm presented here is that the computational effort can be independent of the dimension of the integration problem to be treated if suitable assumptions on the integrand are met. The new reduced CBC-DBD algorithm is designed to work for the construction of lattice point sets, and the corresponding integration rules (so-called lattice rules) can be used to treat functions in different kinds of function spaces. We show that the integration rules constructed by our algorithm satisfy error bounds of almost optimal convergence order. Furthermore, we give details on an efficient implementation such that we obtain a considerable speed-up of a previously known CBC-DBD algorithm that has been studied before. This improvement is illustrated by numerical results.

Lattice rules are among the most prominently studied quasi-Monte Carlo methods to approximate multivariate integrals. A rank-$1$ lattice rule to approximate an $s$-dimensional integral is fully specified by its \emph{generating vector} $\boldsymbol{z} \in \mathbb{Z}^s$ and its number of points~$N$. While there are many results on the existence of ``good'' rank-$1$ lattice rules, there are no explicit constructions of good generating vectors for dimensions $s \ge 3$. This is why one usually resorts to computer search algorithms. In a recent paper by Ebert et al. in the Journal of Complexity, we showed a component-by-component digit-by-digit (CBC-DBD) construction for good generating vectors of rank-1 lattice rules for integration of functions in weighted Korobov classes. However, the result in that paper was limited to product weights. In the present paper, we shall generalize this result to arbitrary positive weights, thereby answering an open question posed in the paper of Ebert et al. We also include a short section on how the algorithm can be implemented in the case of POD weights, by which we see that the CBC-DBD construction is competitive with the classical CBC construction., Comment: arXiv admin note: text overlap with arXiv:2001.02978

In this paper we consider $L_p$-approximation, $p \in \{2,\infty\}$, of periodic functions from weighted Korobov spaces. In particular, we discuss tractability properties of such problems, which means that we aim to relate the dependence of the information complexity on the error demand $\varepsilon$ and the dimension $d$ to the decay rate of the weight sequence $(\gamma_j)_{j \ge 1}$ assigned to the Korobov space. Some results have been well known since the beginning of this millennium, others have been proven quite recently. We give a survey of these findings and will add some new results on the $L_\infty$-approximation problem. To conclude, we give a concise overview of results and collect a number of interesting open problems.

The proliferation of interconnected battlefield information-sharing devices, known as the Internet of Battlefield Things (IoBT), introduced several security challenges. Inherent to the IoBT operating environment is the practice of adversarial machine learning, which attempts to circumvent machine learning models. This work examines the feasibility of cost-effective unsupervised learning and graph-based methods for anomaly detection in the network intrusion detection system setting, and also leverages an ensemble approach to supervised learning of the anomaly detection problem. We incorporate a realistic adversarial training mechanism when training supervised models to enable strong classification performance in adversarial environments. The results indicate that the unsupervised and graph-based methods were outperformed in detecting anomalies (malicious activity) by the supervised stacking ensemble method with two levels. This model consists of three different classifiers in the first level, followed by either a Naive Bayes or Decision Tree classifier for the second level. The model maintains an F1-score above 0.97 for malicious samples across all tested level two classifiers. Notably, Naive Bayes is the fastest level two classifier averaging 1.12 seconds while Decision Tree maintains the highest AUC score of 0.98., Comment: Presented at AAAI FSS-21: Artificial Intelligence in Government and Public Sector, Washington, DC, USA

We study the efficient construction of good polynomial lattice rules, which are special instances of quasi-Monte Carlo (QMC) methods. The integration rules obtained are of particular interest for the approximation of multivariate integrals in weighted Walsh spaces. In particular, we study a construction algorithm which assembles the components of the generating vector, which is in this case a vector of polynomials over a finite field, of the polynomial lattice rule in a component-wise fashion. We show that the constructed QMC rules achieve the almost optimal error convergence order in the function spaces under consideration and prove that the obtained error bounds can, under certain conditions on the involved weights, be made independent of the dimension. We also demonstrate that our alternative component-by-component construction, which is independent of the underlying smoothness of the function space, can be implemented relatively easily in a fast manner. Numerical experiments confirm our theoretical findings., Comment: 23 pages, 2 figures. arXiv admin note: text overlap with arXiv:2008.08966

We consider the efficient construction of polynomial lattice rules, which are special cases of so-called quasi-Monte Carlo (QMC) rules. These are of particular interest for the approximate computation of multivariate integrals where the dimension $d$ may be in the hundreds or thousands. We study a construction method that assembles the generating vector, which is in this case a vector of polynomials over a finite field, of the polynomial lattice rule in a digit-by-digit (or, equivalently, coefficient-by-coefficient) fashion. As we will show, the integration error of the corresponding QMC rules achieves excellent convergence order, and, under suitable conditions, we can vanquish the curse of dimensionality by considering function spaces equipped with coordinate weights. The construction algorithm is based on a quality measure that is independent of the underlying smoothness of the function space and can be implemented in a fast manner (without the use of fast Fourier transformations). Furthermore, we illustrate our findings with extensive numerical results., Comment: 33 pages, 2 figures

We study the approximation of compact linear operators defined over certain weighted tensor product Hilbert spaces. The information complexity is defined as the minimal number of arbitrary linear functionals which is needed to obtain an $\varepsilon$-approximation for the $d$-variate problem. It is fully determined in terms of the weights and univariate singular values. Exponential tractability means that the information complexity is bounded by a certain function which depends polynomially on $d$ and logarithmically on $\varepsilon^{-1}$. The corresponding un-weighted problem was studied recently by Hickernell, Kritzer and Wo\'{z}niakowski with many negative results for exponential tractability. The product weights studied in the present paper change the situation. Depending on the form of polynomial dependence on $d$ and logarithmic dependence on $\varepsilon^{-1}$, we study exponential strong polynomial, exponential polynomial, exponential quasi-polynomial, and exponential $(s,t)$-weak tractability with $\max(s,t)\ge1$. For all these notions of exponential tractability, we establish necessary and sufficient conditions on weights and univariate singular values for which it is indeed possible to achieve the corresponding notion of exponential tractability. The case of exponential $(s,t)$-weak tractability with $\max(s,t)<1$ is left for future study.

In the present paper we study quasi-Monte Carlo rules for approximating integrals over the $d$-dimensional unit cube for functions from weighted Sobolev spaces of regularity one. While the properties of these rules are well understood for anchored Sobolev spaces, this is not the case for the ANOVA spaces, which are another very important type of reference spaces for quasi-Monte Carlo rules. Using a direct approach we provide a formula for the worst case error of quasi-Monte Carlo rules for functions from weighted ANOVA spaces. As a consequence we bound the worst case error from above in terms of weighted discrepancy of the employed integration nodes. On the other hand we also obtain a general lower bound in terms of the number $n$ of used integration nodes. For the one-dimensional case our results lead to the optimal integration rule and also in the two-dimensional case we provide rules yielding optimal convergence rates.

Lattice rules are among the most prominently studied quasi-Monte Carlo methods to approximate multivariate integrals. A rank-1 lattice rule to approximate an $s$-dimensional integral is fully specified by its generating vector $\mathbf{z} \in \mathbb{Z}^s$ and its number of points $N$. While there are many results on the existence of "good" rank-1 lattice rules, there are no explicit constructions for good generating vectors for dimensions $s \ge 3$. This is why one usually resorts to computer search algorithms. Motivated by earlier work of Korobov from 1963 and 1982, we present two variants of search algorithms for good lattice rules and show that the resulting rules exhibit a convergence rate in weighted function spaces that can be arbitrarily close to the optimal rate. Moreover, contrary to most other algorithms, we do not need to know the smoothness of our integrands in advance, the generating vector will still recover the convergence rate associated with the smoothness of the particular integrand, and, under appropriate conditions on the weights, the error bounds can be stated without dependence on $s$. The search algorithms presented in this paper are two variants of the well-known component-by-component (CBC) construction, one of which is combined with a digit-by-digit (DBD) construction. We present numerical results for both algorithms using fast construction algorithms in the case of product weights. They confirm our theoretical findings., Comment: 38 pages, 3 figures

It is known that for a $\rho$-weighted $L_q$-approximation of single variable functions $f$ with the $r$th derivatives in a $\psi$-weighted $L_p$ space, the minimal error of approximations that use $n$ samples of $f$ is proportional to $\|\omega^{1/\alpha}\|_{L_1}^\alpha\|f^{(r)}\psi\|_{L_p}n^{-r+(1/p-1/q)_+},$ where $\omega=\rho/\psi$ and $\alpha=r-1/p+1/q.$ Moreover, the optimal sample points are determined by quantiles of $\omega^{1/\alpha}.$ In this paper, we show how the error of best approximations changes when the sample points are determined by a quantizer $\kappa$ other than $\omega.$ Our results can be applied in situations when an alternative quantizer has to be used because $\omega$ is not known exactly or is too complicated to handle computationally. The results for $q=1$ are also applicable to $\rho$-weighted integration over unbounded domains.

We study adaptive approximation algorithms for general multivariate linear problems where the sets of input functions are non-convex cones. While it is known that adaptive algorithms perform essentially no better than non-adaptive algorithms for convex input sets, the situation may be different for non-convex sets. A typical example considered here is function approximation based on series expansions. Given an error tolerance, we use series coefficients of the input to construct an approximate solution such that the error does not exceed this tolerance. We study the situation where we can bound the norm of the input based on a pilot sample, and the situation where we keep track of the decay rate of the series coefficients of the input. Moreover, we consider situations where it makes sense to infer coordinate and smoothness importance. Besides performing an error analysis, we also study the information cost of our algorithms and the computational complexity of our problems, and we identify conditions under which we can avoid a curse of dimensionality.

In the analysis of using quasi-Monte Carlo (QMC) methods to approximate expectations of a linear functional of the solution of an elliptic PDE with random diffusion coefficient the sensitivity w.r.t. the parameters is often stated in terms of product-and-order-dependent (POD) weights. The (offline) fast component-by-component (CBC) construction of an $N$-point QMC method making use of these POD weights leads to a cost of $\mathcal{O}(s N \log(N) + s^2 N)$ with $s$ the parameter truncation dimension. When $s$ is large this cost is prohibitive. As an alternative Herrmann and Schwab introduced an analysis resulting in product weights to reduce the construction cost to $\mathcal{O}(s N \log(N))$. We here show how the reduced CBC method can be used for POD weights to reduce the cost to $\mathcal{O}(\sum_{j=1}^{\min\{s,s^*\}} (m-w_j+j) \, b^{m-w_j})$, where $N=b^m$ with prime $b$, $w_1 \le \cdots \le w_s$ are nonnegative integers and $s^*$ can be chosen much smaller than $s$ depending on the regularity of the random field expansion as such making it possible to use the POD weights directly. We show a total error estimate for using randomly shifted lattice rules constructed through the reduced CBC construction., Comment: 18 pages

In this paper, we study the approximation of $d$-dimensional $\rho$-weighted integrals over unbounded domains $\mathbb{R}_+^d$ or $\mathbb{R}^d$ using a special change of variables, so that quasi-Monte Carlo (QMC) or sparse grid rules can be applied to the transformed integrands over the unit cube. We consider a class of integrands with bounded $L_p$ norm of mixed partial derivatives of first order, where $p\in[1,+\infty].$ The main results give sufficient conditions on the change of variables $\nu$ which guarantee that the transformed integrand belongs to the standard Sobolev space of functions over the unit cube with mixed smoothness of order one. These conditions depend on $\rho$ and $p$. The proposed change of variables is in general different than the standard change based on the inverse of the cumulative distribution function. We stress that the standard change of variables leads to integrands over a cube; however, those integrands have singularities which make the application of QMC and sparse grids ineffective. Our conclusions are supported by numerical experiments.

In this article we consider the approximation of compact linear operators defined over tensor product Hilbert spaces. Necessary and sufficient conditions on the singular values of the problem under which we can or cannot achieve different notions of exponential tractability are given in a paper by Papageorgiou, Petras, and Wozniakowski. In this paper, we use the new equivalency conditions shown in a recent paper by the second and third authors of this paper to obtain these results in an alternative way. As opposed to the algebraic setting, quasi-polynomial tractability is not possible for non-trivial cases in the exponential setting.

We study approximations of compact linear multivariate operators defined over Hilbert spaces. We provide necessary and sufficient conditions on various notions of tractability. These conditions are mainly given in terms of sums of certain functions depending on the singular values of the multivariate problem. They do not require the ordering of these singular values which in many cases is difficult to achieve.

In this paper, we study an efficient algorithm for constructing node sets of high-quality quasi-Monte Carlo integration rules for weighted Korobov, Walsh, and Sobolev spaces. The algorithm presented is a reduced fast successive coordinate search (SCS) algorithm, which is adapted to situations where the weights in the function space show a sufficiently fast decay. The new SCS algorithm is designed to work for the construction of lattice points, and, in a modified version, for polynomial lattice points, and the corresponding integration rules can be used to treat functions in different kinds of function spaces. We show that the integration rules constructed by our algorithms satisfy error bounds of optimal convergence order. Furthermore, we give details on efficient implementation such that we obtain a considerable speed-up of previously known SCS algorithms. This improvement is illustrated by numerical results. The speed-up obtained by our results may be of particular interest in the context of QMC for PDEs with random coefficients, where both the dimension and the required numberof points are usually very large. Furthermore, our main theorems yield previously unknown generalizations of earlier results., Comment: 33 pages, 2 figures

In this paper, we analyse piecewise deterministic Markov processes, as introduced in Davis (1984). Many models in insurance mathematics can be formulated in terms of the general concept of piecewise deterministic Markov processes. In this context, one is interested in computing certain quantities of interest such as the probability of ruin of an insurance company, or the insurance company's value, defined as the expected discounted future dividend payments until the time of ruin. Instead of explicitly solving the integro-(partial) differential equation related to the quantity of interest considered (an approach which can only be used in few special cases), we adapt the problem in a manner that allows us to apply deterministic numerical integration algorithms such as quasi-Monte Carlo rules; this is in contrast to applying random integration algorithms such as Monte Carlo. To this end, we reformulate a general cost functional as a fixed point of a particular integral operator, which allows for iterative approximation of the functional. Furthermore, we introduce a smoothing technique which is applied to the integrands involved, in order to use error bounds for deterministic cubature rules. On the analytical side, we prove a convergence result for our PDMP approximation, which is of independent interest as it justifies phase-type approximations on the process level. We illustrate the smoothing technique for a risk-theoretic example, and provide a comparative study of deterministic and Monte Carlo integration.

The paper considers truncation errors for functions of the form $f(x_1,x_2,\dots)=g(\sum_{j=1}^\infty x_j\,\xi_j)$, i.e., errors of approximating $f$ by $f_k(x_1,\dots,x_k)=g(\sum_{j=1}^k x_j\,\xi_j)$, where the numbers $\xi_j$ converge to zero sufficiently fast and $x_j$'s are i.i.d. random variables. As explained in the introduction, functions $f$ of the form above appear in a number of important applications. To have positive results for possibly large classes of such functions, the paper provides sharp bounds on truncation errors in both the average and worst case settings. In the former case, the functions $g$ are from a Hilbert space $G$ endowed with a zero mean probability measure with a given covariance kernel. In the latter case, the functions $g$ are from a reproducing kernel Hilbert space, or a space of functions satisfying a H\"older condition.

We analyze a new random algorithm for numerical integration of $d$-variate functions over $[0,1]^d$ from a weighted Sobolev space with dominating mixed smoothness $\alpha\ge 0$ and product weights $1\ge\gamma_1\ge\gamma_2\ge\cdots>0$, where the functions are continuous and periodic when $\alpha>1/2$. The algorithm is based on rank-$1$ lattice rules with a random number of points~$n$. For the case $\alpha>1/2$, we prove that the algorithm achieves almost the optimal order of convergence of $\mathcal{O}(n^{-\alpha-1/2})$, where the implied constant is independent of the dimension~$d$ if the weights satisfy $\sum_{j=1}^\infty \gamma_j^{1/\alpha}<\infty$. The same rate of convergence holds for the more general case $\alpha>0$ by adding a random shift to the lattice rule with random $n$. This shows, in particular, that the exponent of strong tractability in the randomized setting equals $1/(\alpha+1/2)$, if the weights decay fast enough. We obtain a lower bound to indicate that our results are essentially optimal. This paper is a significant advancement over previous related works with respect to the potential for implementation and the independence of error bounds on the problem dimension. Other known algorithms which achieve the optimal error bounds, such as those based on Frolov's method, are very difficult to implement especially in high dimensions. Here we adapt a lesser-known randomization technique introduced by Bakhvalov in 1961. This algorithm is based on rank-$1$ lattice rules which are very easy to implement given the integer generating vectors. A simple probabilistic approach can be used to obtain suitable generating vectors., Comment: 17 pages

The paper considers linear problems on weighted spaces of multivariate functions of many variables. The main questions addressed are: When is it possible to approximate the solution for the original function of very many variables by the solution for the same function; however with all but the first $k$ variables set to zero, so that the corresponding error is small? What is the truncation dimension, i.e., the smallest number $k=k(\varepsilon)$ such that the corresponding error is bounded by a given error demand $\varepsilon$? Surprisingly, $k(\varepsilon)$ could be very small even for weights with a modest speed of convergence to zero.

We consider multivariate $\mathbb{L}_2$-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error $e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)$ of all algorithms that use $N$ information evaluations from the class $\Lambda$ in the $d$-dimensional case. The two classes $\Lambda$ considered in this paper are the class $\Lambda^{{\rm all}}$ consisting of all linear functionals and the class $\Lambda^{{\rm std}}$ consisting only of function evaluations. The focus lies on the dependence of $e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)$ on the dimension $d$. The main results are conditions for weak, polynomial, and strong polynomial tractability.