Search

We consider the algorithm for verified integration of piecewise analytic functions presented in Petras’ paper (Petras, 2002). The analysis of the algorithm contained in that paper is limited to a narrow class of functions and gives upper bounds only. We present an estimate of the cost (measured by the number of evaluations of the integrand) of the algorithm, both upper and lower bounds, for a wider class of functions. We show examples of functions with cost Θ ( ∣ ln ε ∣ / ε p − 1 ) , for any p > 1 , where ε is the desired accuracy of the computed integral. [ABSTRACT FROM AUTHOR]

In many industrial applications, follow-up experimental designs are often used to explore the relationship between inputs (factors) and outputs (responses) step by step. Some extra factors with two or three levels may be added in the follow-up stage since they are quite important but may be neglected in the initial stage. In this paper, mixed-level column augmented uniform designs are proposed under the uniformity criterion, wrap-around L 2 -discrepancy (WD). The multi-stage augmented procedure is also investigated. We present the analytical expressions and the corresponding lower bounds on the WD of the column augmented designs. It is shown that the column augmented uniform designs are also the optimal designs under the non-orthogonality criterion, E (f N O D). Furthermore, a construction algorithm for column augmented uniform designs is provided. Some examples show that the lower bounds are tight and the construction algorithm is effective. [ABSTRACT FROM AUTHOR]

Abstract Doubly stochastic learning algorithms are scalable kernel methods that perform very well in practice. However, their generalization properties are not well understood and their analysis is challenging since the corresponding learning sequence may not be in the hypothesis space induced by the kernel. In this paper, we provide an in-depth theoretical analysis for different variants of doubly stochastic learning algorithms within the setting of nonparametric regression in a reproducing kernel Hilbert space and considering the square loss. Particularly, we derive convergence results on generalization error for the studied algorithms either with or without an explicit penalty term. To the best of our knowledge, the derived results for the unregularized variants are the first of this kind, while the results for the regularized variants improve those in the literature. The novelties in our proof are a sample error bound that requires controlling the trace norm of a cumulative operator, and a refined analysis of bounding initial error. [ABSTRACT FROM AUTHOR]

Abstract It is known that, for systems of initial-value problems, algorithms using adaptive information perform much better in the worst case setting than the algorithms using nonadaptive information. In the latter case, lower and upper complexity bounds significantly depend on the number of equations. However, in contrast with adaptive information, existing lower and upper complexity bounds for nonadaptive information are not asymptotically tight. In this paper, we close the gap in the complexity exponents, showing asymptotically matching bounds for nonadaptive standard information, as well as for a more general class of nonadaptive linear information. [ABSTRACT FROM AUTHOR]

We study numerical integration for a weighted Korobov space of analytic periodic functions for which the Fourier coefficients decay exponentially fast. In particular, we are interested in how the error depends on the dimension d. Many recent papers deal with this problem or similar problems and provide matching necessary and sufficient conditions for various notions of tractability. In most cases even simple algorithms are known which allow to achieve these notions of tractability. However, there is a gap in the literature: while for the notion of exponential-weak tractability one knows matching necessary and sufficient conditions, so far no explicit algorithm has been known which yields the desired result. In this paper we close this gap and prove that Korobov lattice rules are suitable algorithms in order to achieve exponential-weak tractability for integration in weighted Korobov spaces of analytic periodic functions. [ABSTRACT FROM AUTHOR]

The standard method for constructing generating vectors for good lattice point sets is the component-by-component construction. Numerical experiments have shown that the generating vectors found by these constructions sometimes tend to have recurring components, which can lead to the problem of having projections with all lattice points lying on the main diagonal. In this paper we combine methods of Dick and Kritzer to avoid this problem with a reduced fast component-by-component construction. That is, we give a variation of the standard component-by-component construction which avoids repeated components and simultaneously results in a considerable speed-up in comparison to the standard construction. [ABSTRACT FROM AUTHOR]

When a plain Monte Carlo estimate on n samples has variance σ 2 / n , then scrambled digital nets attain a variance that is o (1 / n) as n → ∞. For finite n and an adversarially selected integrand, the variance of a scrambled (t , m , s) -net can be at most Γ σ 2 / n for a maximal gain coefficient Γ < ∞. The most widely used digital nets and sequences are those of Sobol'. It was previously known that Γ ⩽ 2 t 3 s for any nets in base 2. For digital nets, Dick and Pillichshammer (2010) obtained the bound 2 t + s. In this paper we study digital nets in base 2 and show that Γ ⩽ 2 t + s − 1 for such nets. This bound is a simple, but apparently unnoticed, consequence of a microstructure analysis by Niederreiter and Pirsic in 2001. We obtain a sharper bound that is smaller than this for some digital nets. Our main finding is that all nonzero gain coefficients must be powers of two. A consequence of this latter fact is a simplified algorithm for computing gain coefficients of digital nets in base 2. [ABSTRACT FROM AUTHOR]

Computing large Riemann–Roch spaces for plane projective curves still constitutes a major algorithmic and practical challenge. Seminal applications concern the construction of arbitrarily large algebraic geometry error correcting codes over alphabets with bounded cardinality. Nowadays such codes are increasingly involved in new areas of computer science such as cryptographic protocols and "interactive oracle proofs". In this paper, we design a new probabilistic algorithm of Las Vegas type for computing Riemann–Roch spaces of smooth divisors, in characteristic zero, and with expected complexity exponent 2.373 (a feasible exponent for linear algebra) in terms of the input size. [ABSTRACT FROM AUTHOR]

In this paper, we study average sampling numbers of the multivariate periodic function space L ̊ 2 with a Gaussian measure μ in the L q metric for 1 ≤ q ≤ ∞ , and obtain their asymptotical orders, where the Cameron–Martin space of the measure μ is an anisotropic periodic Sobolev space. Moreover, we show that in the average case setting, the Lagrange interpolating operators are asymptotically optimal linear algorithms in the L q metric for all 1 ≤ q ≤ ∞ . This is different from the situation in the worst case setting, where the Lagrange interpolating operators are not asymptotically optimal linear algorithms in the L q metric for q = 1 or ∞ . [ABSTRACT FROM AUTHOR]

The uniform experimental design (UD), a major kind of space-filling design, is widely used in applications. The majority of UD tables (UDs) with good uniformity are generated under the centralized L 2 -discrepancy (CD) and the wrap-around L 2 -discrepancy (WD). Recently, the mixture L 2 -discrepancy (MD) is proposed and shown to be more reasonable than CD and WD in terms of uniformity. In this paper we review lower bounds for MD of two-level designs from a different point of view and provide a new lower bound. Following the same idea we obtain a lower bound for MD of three-level designs. Moreover, we construct UDs under the measurement of MD by the threshold accepting (TA) algorithm, and finally we attach two new UD tables with good properties derived from TA under the measurement of MD. [ABSTRACT FROM AUTHOR]

In this paper, we present algorithms for the approximation of multivariate periodic functions by trigonometric polynomials. The approximation is based on sampling of multivariate functions on rank-1 lattices. To this end, we study the approximation of periodic functions of a certain smoothness. Our considerations include functions from periodic Sobolev spaces of generalized mixed smoothness. Recently an algorithm for the trigonometric interpolation on generalized sparse grids for this class of functions was investigated by Griebel and Hamaekers (2014). The main advantage of our method is that the algorithm is based mainly on a single one-dimensional fast Fourier transform, and that the arithmetic complexity of the algorithm depends only on the cardinality of the support of the trigonometric polynomial in the frequency domain. Therefore, we investigate trigonometric polynomials with frequencies supported on hyperbolic crosses and energy norm based hyperbolic crosses in more detail. Furthermore, we present an algorithm for sampling multivariate functions on perturbed rank-1 lattices and show the numerical stability of the suggested method. Numerical results are presented up to dimension d = 10 , which confirm the theoretical findings. [ABSTRACT FROM AUTHOR]

Functional linear model is a fruitfully applied general framework for regression problems, including those with intrinsically infinite-dimensional data. Online gradient descent methods, despite their evidenced power of processing online or large-sized data, are not well studied for learning with functional data. In this paper, we study reproducing kernel-based online learning algorithms for functional data, and derive convergence rates for the expected excess prediction risk under both online and finite-horizon settings of step-sizes respectively. It is well understood that nontrivial uniform convergence rates for the estimation task depend on the regularity of the slope function. Surprisingly, the convergence rates we derive for the prediction task can assume no regularity from slope. Our analysis reveals the intrinsic difference between the estimation task and the prediction task in functional data learning. [ABSTRACT FROM AUTHOR]

We study approximation of multivariate periodic functions from Besov and Triebel–Lizorkin spaces of dominating mixed smoothness by the Smolyak algorithm constructed using a special class of quasi-interpolation operators of Kantorovich-type. These operators are defined similar to the classical sampling operators by replacing samples with the average values of a function on small intervals (or more generally with sampled values of a convolution of a given function with an appropriate kernel). In this paper, we estimate the rate of convergence of the corresponding Smolyak algorithm in the L q -norm for functions from the Besov spaces B p , θ s (T d) and the Triebel–Lizorkin spaces F p , θ s (T d) for all s > 0 and admissible 1 ≤ p , θ ≤ ∞ as well as provide analogues of the Littlewood–Paley-type characterizations of these spaces in terms of families of quasi-interpolation operators. [ABSTRACT FROM AUTHOR]

In this paper we study exponential tractability of multivariate approximation problem for weighted Korobov spaces in the worst case setting. The considered algorithms are constructive and use the class Λ std of only function evaluations. We give matching necessary and sufficient conditions for notions of EC-quasi-polynomial tractability and EC-uniform weak tractability in terms of two weight parameters of the problem. [ABSTRACT FROM AUTHOR]

In this paper, we study tractability of L 2 -approximation of one-periodic functions from weighted Korobov spaces in the worst-case setting. The considered weights are of product form. For the algorithms we allow information from the class Λ all consisting of all continuous linear functionals and from the class Λ std , which only consists of function evaluations. We provide necessary and sufficient conditions on the weights of the function space for quasi-polynomial tractability, uniform weak tractability, weak tractability and (σ , τ) -weak tractability. Together with the already known results for strong polynomial and polynomial tractability, our findings provide a complete picture of the weight conditions for all current standard notions of tractability. [ABSTRACT FROM AUTHOR]

The efficient evaluation of multivariate polynomials at many points is an important operation for polynomial system solving. Kedlaya and Umans have recently devised a theoretically efficient algorithm for this task when the coefficients are integers or when they lie in a finite field. In this paper, we assume that the set of points where we need to evaluate is fixed and "sufficiently generic". Under these restrictions, we present a quasi-optimal algorithm for multi-point evaluation over general fields. We also present a quasi-optimal algorithm for the opposite interpolation task. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm which computes the characteristic polynomial of a matrix over a field within the same asymptotic complexity, up to constant factors, as the multiplication of two square matrices. Previously, this was only achieved by resorting to genericity assumptions or randomization techniques, while the best known complexity bound with a general deterministic algorithm was obtained by Keller-Gehrig in 1985 and involves logarithmic factors. Our algorithm computes more generally the determinant of a univariate polynomial matrix in reduced form, and relies on new subroutines for transforming shifted reduced matrices into shifted weak Popov matrices, and shifted weak Popov matrices into shifted Popov matrices. [ABSTRACT FROM AUTHOR]

This paper studies the equivalence of tractability for classes of Λ std of function evaluations and Λ all of all continuous linear functionals for L 2 -approximation in the average-case setting. For the normalized error criterion, we show that the power of Λ std is the same as that of Λ all for all notions of exponential tractability and algebraic tractability, in the sense that there exist algorithms using function values at some deterministic points which enjoy the same tractability properties as those using optimally chosen linear functionals. Moreover, for the absolute error criterion, we also show that the power of Λ std is the same as that of Λ all for all notions of exponential tractability and algebraic tractability under certain assumptions on the trace of the covariance operators. In particular, we give a partial answer to three problems raised by E. Novak and H. Woźniakowski in the book " Tractability of multivariate problems" (Open problems 116-118, EMS Tracts in Mathematics, vol.18, Zürich, 2012) , proving that the same results hold under weaker conditions. Finally, we apply our results to the tensor product L 2 -approximation. [ABSTRACT FROM AUTHOR]