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 needed to obtain an ε-approximation for the d-variate problem which 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 that depends polynomially on d and logarithmically on ε−1. The corresponding unweighted problem was studied in Hickernell et al. (2020) 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 ε−1, we study exponential strong polynomial, exponential polynomial, exponential quasi-polynomial, and exponential (s,t)-weak tractability with max(s,t)≥1. 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. The paper uses some general results obtained in Hickernell et al. (2020) and Kritzer and Woźniakowski (2019).

We explain why information-based complexity uses the real number model. Results in the real number model are essentially the same as in floating point arithmetic with fixed precision modulo two important assumptions, namely • we use only stable algorithms, • the approximation error is not too small, compared to the product of the condition number, the roundoff unit of floating point arithmetic, and the accumulation constant of a stable algorithm. We illustrate this by an example of solving nonlinear equations by bisection. We also indicate the possible tradeoffs between complexity and stability, and the need of using multiple or varying precision for ill-conditioned problems.

Recently, quasi-Monte Carlo algorithms have been successfully used for multivariate integration of high dimensiond, and were significantly more efficient than Monte Carlo algorithms. The existing theory of the worst case error bounds of quasi-Monte Carlo algorithms does not explain this phenomenon. This paper presents a partial answer to why quasi-Monte Carlo algorithms can work well for arbitrarily larged. It is done by identifying classes of functions for which the effect of the dimensiondis negligible. These areweightedclasses in which the behavior in the successive dimensions is moderated by a sequence of weights. We prove that the minimalworst caseerror of quasi-Monte Carlo algorithms does not depend on the dimensiondiff the sum of the weights is finite. We also prove that the minimal number of function values in the worst case setting needed to reduce the initial error by ε is bounded byCε−p, where the exponentp∈ [1, 2], andCdepends exponentially on the sum of weights. Hence, the relatively small sum of the weights makes some quasi-Monte Carlo algorithms strongly tractable. We show in a nonconstructive way that many quasi-Monte Carlo algorithms are strongly tractable. Even random selection of sample points (done once for the whole weighted class of functions and then the worst case error is established for that particular selection, in contrast to Monte Carlo where random selection of sample points is carried out for a fixed function) leads to strong tractable quasi-Monte Carlo algorithms. In this case the minimal number of function values in theworst casesetting is of order ε−pwith the exponentp= 2. The deterministic construction of strongly tractable quasi-Monte Carlo algorithms as well as the minimal exponentpis open.

This paper deals with the worst case setting for approximating multivariate tensor product linear operators defined over Hilbert spaces. Approximations are obtained by using a number of linear functionals from a given class of information. We consider the three classes of information: the class of all linear functionals, the Fourier class of inner products with respect to given orthonormal elements, and the standard class of function values. We wish to determine which problems are tractable and which are strongly tractable. The complete analysis is provided for approximating operators of rank two or more. The problem of approximating linear functionals is fully analyzed in the first two classes of information. For the third class of standard information we show that the possibilities are very rich. We prove that tractability of linear functionals depends on the given space of functions. For some spaces all nontrivial normed linear functionals are intractable, whereas for other spaces all linear functionals are tractable. In “typical” function spaces, some linear functionals are tractable and some others are not.

The topological complexity of zero-finding is studied using a BSS machine over the reals with an information node. The topological complexity depends on the class of functions, the class of arithmetic operations, and on the error criterion. For the root error criterion the following results are established. If only Hölder operations are permitted as arithmetic operations then the topological complexity is roughly −log2ϵ and bisection is optimal. This holds even for the small class of linear functions. On the other hand, for the class of all increasing functions, if we allow the sign function or division, together with log and exp, then the topological complexity drops to zero. For the residual error criterion, results can be totally different than for the root error criterion. For example, the topological complexity can be zero for the residual error criterion, and roughly −log2ϵ for the root error criterion.

We study multivariate tenser product problems in the worst case and average case settings. They are defined on functions of d variables. For arbitrary d, we provide explicit upper bounds on the costs of algorithms which compute an ϵ-approximation to the solution. The cost bounds are of the form (c(d) + 2)β1(β2 + β3(ln 1/ϵ)/(d − 1))β4(d − 1)(1/ϵ)β5. Here c(d) is the cost of one function evaluation (or one linear functional evaluation), and βi′s do not depend on d; they are determined by the properties of the problem for d = 1. For certain tensor product problems, these cost bounds do not exceed c(d)Kϵ−p for some numbers K and p, both independent of d. However, the exponents p which we obtain are too large. We apply these general estimates to certain integration and approximation problems in the worst and average case settings. We also obtain an upper bound, which is independent of d, for the number, n(ϵ, d), of points for which discrepancy (with unequal weights) is at most ϵ, n(ϵ, d) ≤ 7.26ϵ−2.454, ∀d, ϵ ≤ 1.

Linear multivariate problems are defined as the approximation of linear operators on functions of d variables. We study the complexity of computing an ϵ-approximation in different settings. We are particularly interested in large d and/or large ϵ−1. Tractability means that the complexity is bounded by c(d) K(d, ϵ), where c(d) is the cost of one information operation and K(d, ϵ) is a polynomial in d and/or in ϵ−1. Strong tractability means that K(d, ϵ) is a polynomial in ϵ−1, independent of d. We provide necessary and sufficient conditions for linear multivariate problems to be tractable or strongly tractable in the worst case, average case, randomized, and probabilistic settings. This is done for the class Λall where an information operation is defined as the computation of any continuous linear functional. We also consider the class Λstd where an information operation is defined as the computation of a function value. We show under mild assumptions that tractability in the class Λall is equivalent to tractability in the class Λstd. The proof is, however, not constructive. Finally, we consider linear multivariate problems over reproducing kernel Hilbert spaces, showing that such problems are strongly tractable even in the worst case setting.

We analyze the complexity of verifying whether a given element is within ε the solution element. This may be contrasted with the complexity of computing an element that is within ε of the solution element. For discrete problems with ε = 0 verification is no harder than computation in any setting. For IBC problems verification can be easier or harder than computation. We will show that the worst case complexity of verification for IBC problems is often infinite. We therefore switch to the probabilistic case and study the probabilistic complexity of verification as a function of the error tolerance ε and the probability of failure δ. We assume that the solution element is specified by a linear continuous functional defined on a Banach space equipped with a Gaussian measure. For fixed δ and small ε, the complexity of verification is zero, whereas for fixed ε and small δ the complexity of verification is essentially a function of only δ and may be exponentially harder than the complexity of computation.

We study the average case complexity of linear multivariate problems, that is, the approximation of continuous linear operators on functions of d variables. The function spaces are equipped with Gaussian measures. We consider two classes of information. The first class Λstd consists of function values, and the second class Λall consists of all continuous linear functionals. Tractability of a linear multivariate problem means that the average case complexity of computing an ϵ-approximation is O((1/ε)p) with p independent of d. The smallest such p is called the exponent of the problem. Under mild assumptions, we prove that tractability in Λall is equivalent to tractability in Λstd and that the difference of the exponents is at most 2. The proof of this result is not constructive. We provide a simple condition to check tractability in Λall. We also address the issue of how to construct optimal (or nearly optimal) sample points for linear multivariate problems. We use relations between average case and worst case settings. These relations reduce the study of the average case to the worst case for a different class of functions. In this way we show how optimal sample points from the worst case setting can be used in the average case. In Part II we shall apply the theoretical results to obtain optimal or almost optimal sample points, optimal algorithms, and average case complexity functions for linear multivariate problems equipped with the folded Wiener sheet measure. Of particular interest will be the multivariate function approximation problem.

We apply the theoretical results of Part I (H. Woźniakowski, 1992, J. Complexity 8, in press) to linear multivariate problems LMP equipped with the folded Wiener sheet measure. We are particularly interested in multivariate weighted integration and multivariate function approximation. We prove that any LMP which satisfies (A.1) of Part I is tractable and its exponent is at most 2. We show that optimal or nearly optimal sample points can be derived from hyperbolic cross points, and exhibit nearly optimal algorithms. In particular, we find the order of the average case complexity of multivariate function approximation in Λstd.

When observations can be made without noise, it is known that adaptive information is no more powerful than nonadaptive information for approximation of linear problems with Gaussian measure. When the noise is additive, independent of the true value, and normal, once again adaption does not help (Theorem 1 in Section 4). However, when those conditions are not satisfied, Examples 1 and 2 of Section 4 show that adaptive information can be much more powerful than nonadaptive information. Finally if orthogonal observations are used with the sample size as well as the number of repetitions fixed, and only the directions of observations are chosen adaptively, then once again adaption does not help (Theorem 2 in Section 5). The issue is analogous to whether sequential designs are more powerful than fixed sample size designs in Bayesian statistics.

The complexity of approximating a continuous linear functional defined on a separable Banach space equipped with a Gaussian measure is studied. The quality of the approximation is measured by a relative error criterion. The complexity is studied in the worst case, average case, and probabilistic settings. In the worst and average case settings, the complexity is infinite. In the probabilistic setting, the complexity is finite under a mild assumption. Tight lower and upper complexity bounds are established and an almost optimal algorithm is constructed. We briefly indicate how some of the results generalize for linear operators. In particular, in the worst case setting the complexity remains infinite, whereas in the average case setting the complexity becomes finite if the dimension of the range of a linear operator is at least two.

Suppose one wants to compare worst case and average complexities for approximation of a linear operator. In order to get a fair comparison the complexities have to be obtained for the same domain of the linear operator. In previous papers, average complexity was studied when the domain was the entire space. To avoid trivial results, worst case complexity has been studied for bounded domains, and in particular, for balls of finite radius. In this paper we study the average complexity for approximation of linear operators whose domain is a ball of finite radius q. We prove that the average complexities even for modest q and for q = +∞ are closely related. This and existing results enable us to compare the worst case and average complexities for balls of finite radius. We also analyze the average complexity for the normalized and relative errors. The paper is illustrated by integration of functions of one variable and by approximation of functions of d variables which are equipped with a Wiener measure.

We study the probabilistic (ϵ, δ)-complexity for linear problems equipped with Gaussian measures. The probabilistic (ϵ, δ)-complexity, comprob(ϵ, δ), is understood as the minimal cost required to compute approximations with error at most ϵ on a set of measure at least 1 − δ. We find estimates of compprob(ϵ, δ) in terms of eigenvalues of the correlation operator of the Gaussian measure over elements which we want to approximate. In particular, we study the approximation and integration problems. The approximation problem is studied for functions of d variables which are continuous after r times differentiation with respect to each variable. For the Wiener measure placed on rth derivatives, the probabilistic compprob(ϵ, S) is estimated by Θ((√2 ln(1δ/ϵ)1(r+a)(ln(√2 ln(1δ)/ϵ))(d−1)(r+1)r+a), where a = 1 for the lower bound and a = 0.5 for the upper bound. The integration problem is studied for the same class of functions with d = 1. In this case, compprob(ϵ, δ) = Θ((√2 ln(1δ)/ϵ)1(r+1)).

The information-based study of the optimal solution of large linear systems is initiated by studying the case of Krylov information. Among the algorithms that use Krylov information are minimal residual, conjugate gradient, Chebyshev, and successive approximation algorithms. A "sharp" lower bound on the number of matrix-vector multiplications required to compute an å-approximation is obtained for any orthogonally invariant class of matrices. Examples of such classes include many of practical interest such as symmetric matrices, symmetric positive definite matrices, and matrices with bounded condition number. It is shown that the minimal residual algorithm is within at most one matrix-vector multiplication of the lower bound. A similar result is obtained for the generalized minimal residual algorithm. The lower bound is computed for certain classes of orthogonally invariant matrices. How the lack of certam properties (symmetry, positive definiteness) increases the lower bound is shown. A conjecture and a number of open problems are stated.

This note proposes a statistical perturbation scheme to protect a statistical database against compromise. The proposed scheme can handle the security of numerical as well as nonnumerical sensitive fields. Furthermore, knowledge of some records in a database does not help to compromise unknown records. We use Chebyshev's inequality to analyze the trade-offs among the magnitude of the perturbations, the error incurred by statistical queries, and the size of the query set to which they apply. We show that if the statistician is given absolute error guarantees, then a compromise is possible, but the cost is made exponential in the size of the database.

An optmaal convergence condmon for Newton ~teratmn m a Banach space ts estabhshed It ~s shown that there exist problems for whtch the ~teraUon converges but the complextty ts unbounded Thus for actual computation convergence ~s not enough What stronger condmon must be unposed to also assure "good complextty" ~s shown KEY WORDS AND PHRASES Newton ~teratton, operator equations, optunal algontlun, convergence, complexity CR CATEGORIES 5 15, 5 25 IntroductwnNumerous papers have analyzed sufficient conditions for the convergence of algonthms for the solution of nonlinear problems.In addRion to convergence, we consider another fundamental question.What stronger conditions must be imposed to assure "good complexity?"This is deafly one of the crucial issues (m addmon to stability) if one is interested in actual computation.We beheve it is also a most interesting theoretical quesUon.We consider Newton iteration for a simple zero of a nonlinear operator in a Banach space of finite or infmite dimension.We establish the opUmal radius of the ball of convergence with respect to a certain functional.There exist problems where the iteration converges but the complexity increases logarithmically to infinity as the initial iterate approaches the boundary of the ball of convergence.(This phenomenon does not occur in the Kantorovich theory of operator equations; see Section 3.) We estabhsh the optimal radius of the ball of good complexity.In this paper we limit ourselves to the important case of Newton iteration.In other papers [8-10] we study optimal convergence and complexRy for classes of iterations.We summarize the results of this paper.Definitions and theorems concerning the optimal ball of convergence are given in Section 2. We conclude this section by giving conditions under which the radius of the ball of convergence is a constant fraction of the radius of the ball of analytioty of the operator.Complexity of Newton iteration ~s studied in Secuon 3. We show that Newton iteration may converge but have arbitrarily high complexity and conjecture that thts is a general phenomenon.We establish the radms of the ball of good complexity as well as a lower bound on the complexity of Newton iteration. Convergence of Newton IterationWe consider the solution of the nonlinear equation Permission to copy wRhout fee all or part of this material ~s granted prowded that the copies are not made or distributed for direct ccommercml advantage, the ACM copyright notice and the title of the publicatton and its date appear, and nottce ts given that copying Is by permtsslon of the AssocmUon for Computmg Machinery To copy otherwtse, or to repubhsh, reqmres a fee and/or speofic permlsston This research was supported m part by the Nauonal Science Foundation under Grant MCS75-222-55 and the Office of Naval Research under Contract N0014-76-C-0370,