{'fraction_non_alphanumeric': 0.05592979645341004, 'fraction_numerical': 0.019371518042457125, 'mean_word_length': 3.9201003224650663, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Why does Monte Carlo fail to work properly in high-dimensional optimization problems?

The paper proposes an answer to the question formulated in the title.

Section 1.6 in [8]). Specifically, the authors of [8] considered the minimax approach to the minimization of the class of Lipschitz functions and proved that, no matter what is the optimization method, it is possible to construct a problem which will require exponential (in the dimension) number of function evaluations. The "same" number of samples is required for the simplest MC method. Similar results can be found in [9], Theorem 1.1.2, where the construction of "bad" problems is exhibited. Below we present another example of such problems (with very simple objective functions, close to linear ones) which are very hard to optimize. Concluding this brief survey, we see that any advanced method of global optimization cannot outperform Monte Carlo when optimizing "bad" functions.
This explains our interest in the MC approach as applied to the optimization setup. In spite of the pessimistic results above, there might be a belief that, if Monte Carlo is applied to a "good" optimization problem (e.g., a convex one), the results would not be so disastrous. The goal of the present paper is to clarify the situation. We examine the "best" optimization problems (the minimization of a linear function on a ball or on a cube) and estimate the accuracy of the Monte Carlo method. Unfortunately, the dependence on the dimension remains exponential, and practical solution of these simplest problems via such an approach is impossible for high dimensions.
The second goal of the paper is to exhibit the same situation with multiobjective optimization [10]. We treat methods for the Pareto set discovery via the Monte Carlo technique and estimate their accuracy, which happens to be poor for large dimensions. These results are instructive for multiobjective optimization, because there exist many methods based on a similar approach (with regular grids instead of random grids), see [11,12].
An intuitive explanation of the effects under consideration can rely on the geometric nature of multidimensional spaces. Numerous facts of this sort can be found in Chapter 2 of the book [13], which is available in the internet. The titles of sections in [13] are very impressive: "The Volume is Near the Equator," "The Volume is in a Narrow Annulus," "The Surface Area is Near the Equator." Some of the results in the present paper clarify these statements by providing rigorous closed-form estimates for the minimum number of random points in the ball-shaped sets required to assess, with a given probability, the optimum of a linear function with given accuracy. These estimates are based on our previous results on the properties of the uniform distribution over a ball, [14] (see Section 2.2).
As far as the geometry of many-dimensional spaces is concerned, the highly advanced monograph [15] is worth mentioning; it deals with the geometrical structure of finite dimensional normed spaces, as the dimension grows to infinity, and presents numerous deep mathematical results in the area.
The rest of the paper is organized as follows. In Section 2, we propose a motivating example, formulate the two optimization problems, scalar and multiobjective, considered within the Monte Carlo setup, and present two known theorems on the uniform distribution over the l 2 -norm ball. These theorems will be used in Section 3 to derive new results related to the two optimization problems of interest for the case of the l 2 -norm ball. Section 4 deals with the scalar optimization problem for the case where Q is a box; use of various deterministic grids are also discussed. Brief concluding remarks are given in the last section.
A preliminary version of this paper is [16]. Several refinements are performed in the current text; first, we changed the overall structure of the exposition; then, we provide a new result on the probability of the empirical maximum of a linear function on a ball (Section 3.1), next, we add a result on the expected value (end of Section 3.2), present closed-form results for the l ∞ -and l 1 -norm balls (Section 4.1), discuss deterministic grids over a box (Section 4.2), and accompany these new results with numerical illustrations. Finally, the introduction section and the bibliography list are considerably modified and extended and various typos and inaccuracies are corrected.

Statement of the Problem
In this section, we propose a motivation for the research performed in this paper, formulate the problems of interest, and present two known facts which form the basis for deriving the new results in Section 3.

A Motivating Example
To motivate our interest in the subject of this paper, we present a simple example showing failure of stochastic global optimization methods in high-dimensional spaces. This example is constructed along the lines suggested in [8] (also, see [9], Theorem 1.1.2) and is closely related to one of the central problems discussed below, the minimization of a linear function over a ball in R n .
Consider an unknown vector c ∈ R n , c|| = 1, and the function to be minimized over the Euclidean ball Q ⊂ R n of radius r = 100 centered at the origin. Obviously, the function has one local minimum x 1 = −100c, with the function value f 1 = −0.5, and one global minimum x * = 100c, with the function value f * = −1. The objective function is Lipschitz with Lipschitz constant equal to 1, and max f (x) − min f (x) = 1. Any standard (not problem-oriented) version of stochastic global search (such as multistart, simulated annealing, etc.) will miss the domain of attraction of the global minimum with probability 1 − V 1 /V 0 , where V 0 is the volume of the ball Q, and V 1 is the volume of the set C = {x ∈ Q : c ⊤ x ≥ 99}. In other words, the probability of success is equal to where I(x; a, b) is the regularized incomplete beta function with parameters a and b (for use of this function, also see Theorem 1 in Section 3), and h is the height of the spherical cap C; in this example, h = 1. This probability quickly goes to zero as the dimension of the problem grows; say, for n = 15 it is of the order of 10 −15 . Hence, any "advanced" method of global optimization will find the minimum with relative error not less 50%; moreover, such methods are clearly seen to be no better than a straightforward Monte Carlo sampling. The same is true if our goal is to estimate the minimal value of the function f * (not the minimum point x * ). Various methods based on ordered statistics of sample values (see Section 2.3 in [3]) fail to reach the set C with high probability, so that the prediction will be close to These observations motivate our interest in the analysis of the performance of the MC schemes in optimization.

The Two Optimization Settings
Let Q ⊂ R n denote a unit ball in one or another norm and let ξ (i) N 1 = ξ (1) , . . . , ξ (N ) be a multisample of size N from the uniform distribution ξ ∼ U(Q).
We are targeted at solving the problems of the following sort.
I. Scalar Optimization: Given the scalar-valued linear function defined on the unit ball Q ⊂ R n , estimate its maximum value from the multisample. More specifically, let η * be the true maximum of g(x) on Q and let η = max{g (1) , . . . , g (N ) }, be the empirical maximum; we say that η approximates η * with accuracy at least δ if Then the problem is: Given a probability level p ∈ (0, 1) and accuracy δ ∈ (0, 1), determine the minimal length N min of the multisample such that, with probability at least p, the accuracy of approximation is at least δ (i.e., with high probability, the empirical maximum nicely evaluates the true one).
These problems are the subject of discussion in Sections 3.1 and 4.1.
II. Multiobjective Optimization: Consider now 1 < m < n scalar functions g j (x), j = 1, . . . , m, and the image of Q under these mappings. The problem is to "characterize" the boundary of the image set g(Q) ⊂ R m via the multisample ξ (i) N 1 from Q.
In rough terms, the problem is: Determine the minimal sample size N min which guarantees, with high probability, that the image of at least one sample fall close to the boundary of g(Q).
For the case where Q is the Euclidean ball, the mappings g j (x) are linear, and m = 2, this problem is discussed in Section 3.2; various statistics (such as the cumulative distribution function, mathematical expectation, mode) of a specific random variable associated with image points are evaluated.

Supporting Material
The results presented in Section 3 below are based on the following two facts established in [14]; they relate to the probability distribution of a specific linear or quadratic function of the random vector uniformly distributed on the Euclidean ball.
Fact 1 [14]. Let the random vector ξ ∈ R n be uniformly distributed on the unit Euclidean ball Q ⊂ R n . Assume that a matrix A ∈ R m×n has rank m ≤ n. Then the random variable where Γ(·) is the Euler gamma function.
Alternatively, the numerical coefficient in (3) writes The second fact is an asymptotic counterpart of Fact 1.
Fact 2 [14]. Assume that for every n ≥ m, the matrix A (n) ∈ R m×n has rank m, and ξ (n) is a random vector uniformly distributed over the unit ball Q in R n . Then, as n → ∞, the random vector Note that for n fixed, we have ρ (n) 2 = nρ; i.e., Facts 2 and 1 characterize the asymptotic distribution of the vector ρ (n) and exact distribution of its squared norm (normalized by the dimension).

Main Results: Ball-Shaped Sets
In this section we analyse the two optimization settings formulated in Section 2.2 for Q being the n-dimensional unit l 2 -ball.

Scalar Optimization
We consider the scalar case (1) and discuss first a qualitative result that follows immediately from Fact 1. Without loss of generality, let c = (1, 0, . . . , 0) ⊤ , so that the function g(x) = x 1 takes its values on the segment [−1, 1], and the true maximum of g(x) on Q is equal to 1 (respectively, −1 for the minimum) and is attained with x = c (respectively, x = −c). Let us compose the random variable which is the squared first component ξ 1 of ξ. By Fact 1 with m = 1 (i.e., A = c ⊤ ), for the probability density function (pdf) of ρ we have Straightforward analysis of this function shows that, as dimension grows, the mass of the distribution tends to concentrate closer the origin, meaning that the random variable (r.v.) ρ is likely to take values which are far from the maximum, equal to unity. To illustrate, Fig. 1 depicts the plot of the pdf (5) for n = 20. We next formulate the following rigorous result. Theorem 1. Let ξ be a random vector uniformly distributed over the unit Euclidean ball Q and let g(x) = x 1 , x ∈ Q. Given p ∈ (0, 1) and δ ∈ (0, 1), the minimal sample size N min that guarantees, with probability at least p, for the empirical maximum of g(x) to be at least a δ-accurate estimate of the true maximum, is given by where I(x; a, b) is the regularized incomplete beta function with parameters a and b.
Clearly, a correct notation should be N min = ⌈·⌉, i.e., rounding toward the next integer; we omit it, but it is implied everywhere in the sequel.
Proof We specify sample size N, and let ξ (i) N 1 be a multisample from the uniform distribution on Q; also introduce the random variable the empirical maximum of the function g(x) = a ⊤ x, a = (1, 0, . . . , 0) ⊤ , from this multisample. We now estimate the probability P{η > 1 − δ}. By Fact 1, the pdf of the r.v. ρ = g 2 (ξ) is given by (5), and its cumulative distribution function (cdf) is known to be referred to as the regularized incomplete beta function I x; 1 2 , n+1 2 with parameters 1 2 and n+1 2 , [17]. Due to the symmetry of the distribution of Letting P{η > 1 − δ} = p and inverting the last relation, we arrive at (6).
Numerical values of the function I(x; a, b) can be computed via use of the Matlab routine betainc. For instance, with modest values n = 10, δ = 0.05, and p = 0.95, this gives N min ≈ 8.9 · 10 6 , and this quantity grows quickly as the dimension n increases.
Since we are interested in small values of δ, i.e., in x close to unity, a "closed-form" lower bound for N min can be computed as formulated below.
Proof We have Further simplification of the lower bound can be obtained: This is doable by noting that ln(1 − ε) ≈ −ε for small ε > 0 and using the approximation B(a, b) ≈ Γ(a)b −a for the beta function with large b. These lower bounds are quite accurate; for instance, with n = 10, δ = 0.05, and p = 0.95, we have N min ≈ 8.8694 · 10 6 , while N appr ≈ 8.7972 · 10 6 and N appr = 8.5998 · 10 6 .

Multiobjective Optimization
Consider a (possibly nonlinear) mapping g : R n → R m , n ≫ m > 1; the goal is to characterize the boundary of the image of a set Q ⊂ R n under the mapping g. Apart from being of independent interest, this problem emerges in numerous applications. In particular, if a special part of the boundary, the Pareto front [10] is of interest, we arrive at a multiobjective optimization problem. Numerous examples (e.g., see [18]) show that, for n large, the images of the points sampled randomly uniformly in Q may happen to fall deep inside the true image set, giving no reasonable description of the boundary and the Pareto front of g(Q). We first present a qualitative explanation of this phenomenon by using the setup of Fact 2; i.e., the set Q is the unit Euclidean ball and the mappings are linear.
Since the squared norm of a standard Gaussian vector in R m has the χ 2 -distribution C(m) with m degrees of freedom [17], from Fact 2 and (4) we obtain nρ → C(m) in distribution as n → ∞. This is in compliance with the well-known result in the probability theory, namely, ν 2 B(ν 1 , ν 2 ) → C(ν 1 ) in distribution as ν 2 → ∞, [17]; here, B(ν 1 , ν 2 ) stands for the r.v. having the beta distribution with shape parameters ν 1 , ν 2 . For ν 1 = 1 (i.e., m = 2, the case most relevant to applications), Fig. 2 depicts the plots of the cumulative distribution functions B(ν 1 , ν 2 ) (see (11) below for the explicit formula) for ν 2 = 1, 2, 5, 10, 20, 40 (i.e., n = 2, 4, 10, 20, 40, 80). Hence, Fact 2 immediately implies the following important conclusion: Linear transformations essentially change the nature of the uniform distribution on a ball. Namely, as the dimension of the vector ξ grows, with the rank of the transformation matrix A being unaltered, the distribution of the vector Aξ tends to "concentrate closer the center" of the image set.
We now turn to Fact 1 and provide quantitative estimates; to this end, consider the simple case where m = 2 and the two mappings are linear: (i.e., A = c ⊤ 1 c ⊤ 2 in the notation of Fact 1); for instance, c 1 , c 2 may be any two different unit coordinate vectors, so that g 1 (x) = x i and g 2 (x) = x j , i = j, are the two different components of x. Then the image of Q is the unit circle centered at the origin.
Introduce now the random variable the squared norm of the image of ξ ∼ U(Q) under mapping (9) (i.e., ρ = ξ 2 i + ξ 2 j ). Then, by Fact 1 with m = 2, we have the closed-form expressions for the cdf F ρ and pdf f ρ of the r.v. ρ: With these in mind, let us evaluate the minimal length N of the multisample that guarantees a given accuracy with a given probability. To this end, recall that, given a multisample ζ (i) N 1 from the scalar cdf F ζ (x) with pdf f ζ (x), the random variable which is, in our case (11)-(12) writes We next evaluate several statistics of the r.v. η = max{ρ (1) , . . . , ρ (N ) }.
Probability: The theorem below determines the minimal sample size N min that guarantees, with high probability, that a random vector ξ ∼ U(Q) be mapped close to the boundary of the image set.
Theorem 2. Letting ξ be the random vector uniformly distributed over the unit Euclidean ball Q ⊂ R n , consider the linear mapping g(·) as in (9). Given p ∈ (0, 1) and δ ∈ (0, 1), the minimal sample size N min that guarantees, with probability at least p, that at least one sample be mapped at least δ-close to the boundary of the image set, is given by Proof Let us specify sample size N and estimate the probability for a sample to be mapped close to the boundary of the image set. To this end, denote the image of ξ ∼ U(Q) under mapping (9) by g(ξ) = g 1 (ξ), g 2 (ξ) ⊤ and introduce the r.v. κ = max{ g (1) , . . . , g (N ) }, the maximum of g(ξ) over the multisample ξ (i) N 1 . Also, consider the r.v. ρ = ρ(ξ) (10) for which we have and the r.v. η = max{ρ (1) , . . . , ρ (N ) }, the maximum of ρ over the multisample ξ (i) N 1 , for which we have P{η Hence, noting that η = κ 2 , for a small δ > 0 (i.e., letting x = 1 − δ), we see that the probability for at least one sample ξ (i) to be mapped at least δ-close to the boundary is equal to P{κ Let p ∈ (0, 1) be a desired confidence level; then, letting P{κ > 1 − δ} = p and inverting the last relation, we obtain the minimal required length of the multisample. The simple approximation for N min follows from the fact that ln(1 − ε) ≈ −ε for small ε > 0.
To illustrate, for modest dimension n = 10, accuracy δ = 0.05, and probability p = 0.95, one has to generate approximately N = 3.4 · 10 5 random samples to obtain, with probability 95%, a point which is δ-close to the boundary of the image set. A sharper illustration of this phenomenon for n = 50 is given in Fig. 3, which depicts the images of N = 100, 000 samples of ξ ∼ U(Q) under mapping (9). None of them falls closer than 0.35 to the boundary of the image set. Qualitatively, such a behavior can be explained by using geometric considerations and simple projection-type arguments discussed in [13].
Mode: The pdf (13) can be shown to be unimodular, and we find its mode by straightforward differentiating. Letting z = 1 − x, for the pdf we have Then f ′ (z) = 0 writes Simplifying, we obtain hence, We thus arrive at the following result.
Theorem 3. Letting ξ be the random vector uniformly distributed over the unit Euclidean ball Q ⊂ R n , consider the linear mapping g(·) as in (9) and the random variable the empirical maximum of the function ρ(x) = g(x) 2 from the multisample ξ (i) N 1 of size N. The mode of the distribution of η is given by For large n we have an approximation The quantity x max is seen to be essentially less than unity for large n, even if the sample size N is huge. This means the r.v. η takes values far from the boundary of the image. For instance, let n = 20; then, to "obtain a point in the 0.1 vicinity of the boundary," one has to generate N ≈ 10 10 random samples in Q. The family of the pdfs (13) is plotted in Fig. 4.

Expectation:
We now estimate the mathematical expectation E of the empirical maximum.
where B(·, ·) is the beta function.
Proof If a r.v. ζ is positive and defined on D = [0, d], then the expectation where F ζ (x) is the cdf of ζ. Hence, having N samples ξ (i) of ξ ∼ U(Q) and the respective r.v. ρ = ρ(ξ) (10) with support [0, 1], for the r.v. η = max{ρ (1) , . . . , ρ (N ) } we have where F η (x) is given by (14). By change of variables z = (1 − x) n/2 , we arrive at (15). For large n and N, numerical values of the expectation are close to those observed for the mode; this is seen from the shape of the pdf (13) depicted in Fig. 4. More formally, having the approximation B 2 n , N + 1 ≈ Γ( 2 n )(N + 1) −2/n for large N, from (15) we obtain For instance, with n = 20 and N = 10 9 , we have E(η) = 0.8802 for the expectation and x max = 0.8754 for the mode.

Main Results: Box-Shaped Sets
In this section, we consider the scalar optimization problem, however, for box-shaped sets, i.e,, not related to Facts 1 and 2. We consider the scalar setup described in Section 2.2 along with the deterministic approach based on use of regular grids.

A Direct Monte Carlo Approach
Consider the linear scalar optimization problem for the case where Q = [−1, 1] n . Clearly, the results heavily depend on the vector c in the optimized function g = c ⊤ x; we consider two extreme cases. where g (i) is the first component of the random vector ξ ∼ U(Q). Specifying δ ∈ (0, 1), we obtain P{η This quantity is seen to be independent of the dimension (which is obvious as it is). Now, specifying a probability level p ∈ [0, 1], we obtain that the minimal required sample size that guarantees accuracy δ with probability p is equal to For instance, with p = 0.95 and δ = 0.1, one has to generate just 59 points to obtain a 10%accurate estimate of the maximum with probability 95%, independently of the dimension.
Case 2. Now let c = (1, 1, . . . , 1) ⊤ ; i.e., the optimized function is g(x) = n i x i , so that the maximum is attained at x = c ⊤ and is equal to η * = n. In contrast to Case 1, Monte Carlo sampling exhibits a totally different behavior. Below, Vol(·) stands for the volume of a set.
For n = 10 and the same values δ = 0.1 and p = 0.95, we obtain a huge N min ≈ 1.12·10 10 . Even for n = 2, an "unexpectedly" large number N min ≈ 600 of samples are to be drawn. Theorem 6. Letting ξ be the random vector uniformly distributed over the unit l 1 -norm ball Q = {x ∈ R n : n i=1 |x i | ≤ 1}, consider the linear function g(x) = x 1 . Given p ∈ (0, 1) and δ ∈ (0, 1), the minimal sample size N min that guarantees, with probability at least p, for the empirical maximum of g(x) to be at least a δ-accurate estimate of the true maximum, is given by For small δ we have Proof The true maximum of g(x) on Q is equal to unity; we specify accuracy δ ∈ (0, 1) and consider the set We then have and the rest of the proof is the same as that of the previous theorem.
These results are in consistence with intuition, since the l 1 -norm ball is "closer" in shape to the "worst-case" conic set, while the l ∞ -norm ball with c = (1, 1, . . . , 1) ⊤ "takes an intermediate position" between l 2 and l 1 (obviously, closer to l 1 ).

Deterministic Grids
In this section we briefly discuss a natural alternative to random sampling the set Q. A belief is that use of various deterministic grids might outperform straightforward Monte Carlo. Again, we consider Q being the unit box [−1, 1] n , and the scalar function to be optimized is g(x) = n i=1 x i , so that the maximum is equal to n. We show that, even in such a simple setting, deterministic grids happen to be computationally intensive in high dimensions.
Uniform grid: Consider a positive integer M > 1 and the uniform mesh M on Q, with cell-size ∆ = 2/(M + 1); the mesh is assumed not to cover the boundary of Q. The total amount of points in the mesh is card M = M n and the maximum of g(x) over M is equal to g M = n(1 − ∆). To guarantee relative accuracy δ of approximation, i.e., g M = n·(1 − δ), one needs cell-size to be ∆ = δ, hence, the overall number of mesh points is equal to which amounts to a huge M ≈ 6.13 · 10 12 for modest n = 10 and δ = 0.1. Interestingly, to obtain the same accuracy with probability p = 0.99, Monte Carlo requires "just" N min = 1.7 · 10 10 samples! Sobol sequences: Another type of grids that can be arranged over boxes are lowdiscrepancy point sets or quasi-random sequences [19]. In practice, they share many properties of pseudorandom numbers, e.g., such as those produced by the rand routine in Matlab.
Among the variety of quasi-random sequences, so-called LP τ sequences introduced by I.M. Sobol in 1967, [20] (also see [11,12] for recent developments) are widely used in various application areas. This sophisticated mechanism heavily exploits the box shape of the set; it is much more efficient than purely deterministic uniform grids and may outperform straightforward Monte Carlo.
In the experiments, we considered the function g(x) = n i=1 x i defined on Q = [−1, 1] n and computed its maximum value over the points of an LP τ sequence of length N = 10 6 for various dimensions; this was performed by using the Matlab routine sobolset. The corresponding results are given in the row "LP τ " of Table 2. The row "Monte Carlo" presents empirical maxima obtained by using Monte Carlo sampling with the same sample size N (averaged over 100 realizations), and the row "Uniform grid" relates to the uniform mesh of cardinality N.  Table 2: l ∞ -box: Empirical maxima for the three methods with N = 10 6 .
It is seen that the uniform mesh exhibits a very poor relative performance as dimension grows, while the results of LP τ and Monte Carlo approaches are much better and similar to each other. Clearly, the absolute values are very far from the true maxima equal to n, since N = 10 6 samples are not sufficient to obtain reasonable accuracy for dimensions n > 5.
Instead of computing the sample size for fixed values of the accuracy δ as in Table 1, here we fix the sample size and compute the empirical maxima. The reason for such an "inversion" is that, given δ and the specific linear function g(x), it is not quite clear how to estimate the required length of the LP τ -sequence. To overcome this problem, one might fix a reasonable value of accuracy, compute the minimal sample size N min required for Monte Carlo, run the LP τ -approach with this length, and compare the results. However, for large dimensions n, the values of N min are huge, leading to very large computation times or even memory overflow.
The values obtained for the uniform mesh were computed by inverting relation (19) and using the actual grid with cardinality card M = ⌈N 1/n ⌉ n ≥ N, so the quantities presented in row "Uniform grid" of Table 2 are overly optimistic.
More importantly, the routine sobolset has several parameters, such as s = skip (choice of the initial point in the sequence) and ℓ = leap (selection of every ℓth point). These play the similar role as the seed value in Matlab pseudorandom number generators does, and may happen to be crucial for the quality of the resulting LP τ sequence. In the experiments, we used the default values s = ℓ = 1 (i.e., the first N points), though for different values of s, ℓ, the respective estimates of the empirical maximum may differ a lot. For instance, adopting ℓ = 133, for n = 5 we obtain a much better estimate 4.8653, while taking (intentionally bad) ℓ = 128 leads to very poor 2.8734. Finally, note that applications of uniform grids and LP τ sequences are limited to boxshaped sets. Sets different from boxes can in principle be embedded in tight enclosing boxes with subsequent use of rejection techniques; however, the rejection rate usually grows dramatically as the dimension increases.

Conclusions
The main contribution of the paper is a rigorous explanation of the reason why does a direct Monte Carlo approach show itself inefficient in high-dimensional optimization problems when estimating the maximum value of a function from a random sample in the domain of definition. First, attention was paid to linear functions and ball-shaped sets; using known results on the uniform distribution over the ball, we characterized the accuracy of the estimates obtained via a specific random variable associated with the function value. Also, a multiobjective optimization setup was discussed. The results obtained testify to a dramatic growth of computational complexity (required number of samples) as the dimension of the ball increases. Same flavor results are obtained for box-shaped sets; these also include analysis of deterministic grids.
The authors are indebted to an anonymous reviewer for the critical comments that led to a tangible progress in the presentation of the results.