Vincent Guigues
email: vguigues@fgv.br

Anatoli Juditsky
email: anatoli.juditsky@imag.fr

Arkadi Nemirovski
email: nemirovs@isye.gatech.edu

Non-asymptotic confidence bounds for the optimal value of a stochastic program

Keywords: Sample Average Approximation, confidence interval, MinMax Stochastic Optimization, stochastically constrained problems

We discuss a general approach to building non-asymptotic confidence bounds for stochastic optimization problems. Our principal contribution is the observation that a Sample Average Approximation of a problem supplies upper and lower bounds for the optimal value of the problem which are essentially better than the quality of the corresponding optimal solutions. At the same time, such bounds are more reliable than "standard" confidence bounds obtained through the asymptotic approach. We also discuss bounding the optimal value of MinMax Stochastic Optimization and stochastically constrained problems. We conclude with a small simulation study illustrating the numerical behavior of the proposed bounds.

Introduction

Consider the following Stochastic Programming (SP) problem

Opt = min x [f (x) = E{F (x, ξ)}, x ∈ X] (1)
where X ⊂ R n is a nonempty bounded closed convex set, ξ is a random vector with probability distribution P on Ξ ⊂ R k and F : X × Ξ → R. There are two competing approaches for solving [START_REF] Andersen | The MOSEK optimization toolbox for MATLAB manual[END_REF] when a sample ξ N = (ξ 1 , ..., ξ N ) of realizations of ξ (or a device to sample from the distribution P ) is available -Sample Average Approximation (SAA) and the Stochastic Approximation (SA). The basic idea of the SAA method is to build an approximation of the "true" problem (1) by replacing the expectation f (x) with its sample average approximation

f N (x) = 1 N N t=1 F (x, ξ t ), x ∈ X.
The resulting optimization problem has been extensively studied theoretically and numerically (see, e.g., [START_REF] Kleywegt | The sample average approximation method for stochastic discrete optimization[END_REF][START_REF] Linderoth | The empirical behavior of sampling methods for stochastic programming[END_REF][START_REF] Mak | Monte carlo bounding techniques for determining solution quality in stochastic programs[END_REF][START_REF] Shapiro | Monte carlo sampling methods[END_REF][START_REF] Shapiro | On complexity of stochastic programming problems[END_REF][START_REF] Verweij | The sample average approximation method applied to stochastic routing problems: a computational study[END_REF], among many others). In particular, it was shown that the SAA method (coupled with a deterministic algorithm for minimizing the SAA) is often efficient for solving large classes of Stochastic Programs. The alternative SA approach was also extensively studied since the pioneering work by Robbins and Monro [START_REF] Robbins | A stochastic approximation method[END_REF]. Though possessing better theoretical accuracy estimates, SA was long time believed to underperform numerically. It was recently demonstrated (cf., [START_REF] Nemirovski | Stochastic approximation approach to stochastic programming[END_REF][START_REF] Bottou | Large-scale machine learning with stochastic gradient descent[END_REF][START_REF] Srebro | Stochastic optimization for machine learning[END_REF]) that a proper modification of the SA approach, based on the ideas behind the Mirror Descent algorithm [START_REF] Nemirovsky | Problem complexity and method efficiency in optimization[END_REF] can be competitive and can even significantly outperform the SAA method on a large class of convex stochastic programs. Note that in order to qualify the accuracy of approximate solutions (e.g., to build efficient stopping criteria) delivered by the stochastic algorithm of choice, one needs to construct lower and upper bounds for the optimal value Opt of problem (1) from stochastically sampled observations. Furthermore, the question of computing reliable upper and, especially, lower bounds for the optimal value is of interest in many applications. Such bounds allow statistical decisions (e.g., computing confidence intervals, testing statistical hypotheses) about the optimal value. For instance, using the approach to regret minimization, developed in [START_REF] Bubeck | Bounded regret in stochastic multi-armed bandits[END_REF][START_REF] Perchet | The multi-armed bandit problem with covariates[END_REF], they may be used to construct risk averse strategies for multi-armed bandits, and so on.

Note that an important methodological feature of the SAA approach is its asymptotic framework which explains how to provide asymptotic estimates of the accuracy of the obtained solution by computing asymptotic upper and lower bounds for the optimal value of the "true" problem (see, e.g., [START_REF] Dupacovà | Asymptotic behavior of statistical estimators and of optimal solutions of stochastic optimization problems[END_REF][START_REF] Shapiro | Asymptotic analysis of stochastic programs[END_REF][START_REF] King | Asymptotic theory for solutions in statistical estimation and stochastic programming[END_REF][START_REF] Pflug | Asymptotic stochastic programs[END_REF][START_REF] Mak | Monte carlo bounding techniques for determining solution quality in stochastic programs[END_REF], and references therein). However, as is always the case with techniques which are validated asymptotically, some important questions, such as "true" reliability of such bounds, cannot be answered by the asymptotic analysis. Note that the non-asymptotic accuracy of optimal solutions of the SAA problem was recently analysed (see [START_REF] Shapiro | Monte carlo sampling methods[END_REF][START_REF] Shapiro | On complexity of stochastic programming problems[END_REF]), yet, to the best of our knowledge, the literature does not provide any non-asymptotic construction of lower and upper bounds for the optimal value of (1) by SAA. On the other hand, non-asymptotic lower and upper bounds for the objective value by SA method were built in [START_REF] Lan | Validation analysis of mirror descent stochastic approximation method[END_REF].

Our objective in this work is to fill this gap, by building reliable finite-time evaluations of the optimal value of (1), which are also good enough to be of practical interest. Our basic methodological observation is Proposition 1 which states that the SAA of problem (1) comes with a "built-in" non-asymptotic lower and upper estimation of the "true" objective value. The accuracy of these estimations is essentially higher than the available theoretical estimation of the quality of the optimal solution of the SAA. Indeed, when solving a high-dimensional SAA problem, the (theoretical bound of) inaccuracy of the optimal solution becomes a function of dimension. In particular, when the set X is a unit Euclidean ball of R n , the accuracy of the SAA optimal solution may be by factor O(n) worse than the corresponding accuracy of the SA solution. In contrast to this, the optimal value of the SAA problem supplies an approximation of the "true" optimal value of accuracy which is (almost) independent of problem's dimension and may be used to construct non-trivial non-asymptotic confidence bounds for the true optimal value. This fact is surprising, because the bad theoretical accuracy bound for optimal solutions of SAA reflects their actual behavior on some problem instances (see Proposition 2 and the discussion in Section 2.1).

The paper is organized as follows. We present the construction of lower and upper confidence bounds for the optimal value of a stochastic problem in Section 2. Specifically, in Section 2.1, we develop confidence bounds for the optimal value of problem [START_REF] Andersen | The MOSEK optimization toolbox for MATLAB manual[END_REF]. Then in Section 2.2 we build lower and upper bounds for the optimal value of MinMax Stochastic Optimization and show how the confidence bounds can be constructed for an ǫ-underestimation of the optimal value of a (stochastically) constrained Stochastic Optimization problem.

Finally, several simulation experiments illustrating the properties of the bounds built in Section 2 are presented in Section 3. Proofs of theoretical statements are collected in the appendix.

Confidence bounds via Sample Average Approximation

Problem without stochastic constraints

Situation. In the sequel, we fix a Euclidean space E and a norm • on E. We denote by B • the unit ball of the norm • , and by • * the norm conjugate to • :

y * = max x ≤1
x, y .

Let us now assume that we are given a function ω(•) which is continuously differentiable on B • and strongly convex with respect to • , with parameter of strong convexity equal to one (in other words, a compatible with • distance-generating function) and such that ω(0) = 0 and ω ′ (0) = 0. We denote Ω = max

x: x ≤1 2ω(x). (2)
Let, further,

• X be a convex compact subset of E,

• R = R • [X] be the smallest radius of a • -ball containing X, and x[X] be the center of such a ball,

• P be a Borel probability distribution on R k , Ξ be the support of P , and

F (x, y) : E × Ξ → R
be a Borel function which is convex in x ∈ E and is P -summable for every x ∈ E, so that the function

f (x) = E{F (x, ξ)} : E → R
is well defined and convex.

The outlined data give rise to the stochastic program

Opt = min x∈X [f (x) = E{F (x, ξ)}]
and its Sample Average Approximation (SAA)

Opt N (ξ N ) = min x∈X f N (x, ξ N ) := 1 N N t=1 F (x, ξ t ) , (3)
where ξ N = (ξ 1 , ..., ξ N ), and ξ 1 , ξ 2 , ... are drawn independently from P . Our immediate goal is to understand how well the optimal value Opt N (ξ N ) of SAA approximates the true optimal value Opt. Our main result is as follows.

Proposition 1. Let L(x, ξ) = max { g -h * : g ∈ ∂ x F (x, ξ), h ∈ ∂f (x)} .
Assume that f is differentiable on X, and that for some positive M 1 , M 2 one has

(a) E e (F (x,ξ)-f (x)) 2 /M 2 1 ≤ e, (b) E e L 2 (x,ξ)/M 2 2 ≤ e (4)
for all x from an open set X + containing X. Define

a(µ, N ) = µM 1 √ N and b(µ, s, λ, N ) = µM 1 + Ω[1 + s 2 ] + 2λ M 2 R √ N ,
where Ω is as in [START_REF] Bottou | Large-scale machine learning with stochastic gradient descent[END_REF], and let α * = 0.557409... be the smallest positive real such that e t ≤ t + e αt 2 for all t ∈ R. Then for all N ∈ Z + and µ ∈ [0, 2

√ α * N ] Prob Opt N (ξ N ) > Opt + a(µ, N ) ≤ e -µ 2 4α * ; ( 5
)
and for all

N ∈ Z + , µ ∈ [0, 2 √ α * N ], s > 1 and λ ≥ 0, Prob Opt N (ξ N ) < Opt -b(µ, s, λ, N ) ≤ e -N (s 2 -1) + e -µ 2 4α * + e -λ 2 4α * . (6)
We have the following obvious corollary to this result.

Corollary 1. Under the premise of Proposition 1, let

Low SAA (µ 1 , N ) = Opt N (ξ N ) -a(µ 1 , N ), Up SAA (µ 2 , s, λ, N ) = Opt N (ξ N ) + b(µ 2 , s, λ, N ).

Then for all

N ∈ Z + , s > 1, λ ≥ 0, µ 1 , µ 2 ∈ [0, 2 √ α * N ] Prob Opt ∈ Low SAA (µ 1 , N ), Up SAA (µ 2 , s, λ, N ) ≥ 1 -β where β = e -µ 2 1 4α * + e -µ 2 2 4α * + e -N (s 2 -1) + e -λ 2 4α * .
Discussion. The result of Proposition 1 merits some comments.

1. "As is", Proposition 1 requires f (•) to be differentiable. This purely technical assumption is in fact not restrictive at all. Indeed, we can associate with (1) its "smoothed" approximation

min x∈X f ǫ (x) := Ξ×E F ǫ (x, [h; ξ])P (dξ)p(h)dh , F ǫ (x; [h; ξ]) = F (x + ǫh, ξ),
where p(h) is, say, the density of the uniform distribution U on the unit box in E. Assuming, as in Proposition 1, that (4) takes place for all x from an open set X + containing X, it is immediately seen that f ǫ is, for all small enough values of ǫ, a continuously differentiable on X function which converges, uniformly on X, to f as ǫ → +0. Given a possibility to sample from the distribution P , we can sample from the distribution P + := P × U on Ξ + = Ξ × E, and thus can build the SAA of the problem min x f ǫ (x). When ǫ is small, this smoothed problem satisfies the premise of Proposition 1, the parameters M 1 , M 2 remaining unchanged, and its optimal value can be made as close to Opt as we wish by an appropriate choice of ǫ. As a result, by passing from the SAA of the original problem to the SAA of the smoothed one, ǫ being small, we ensure, "at no cost," smoothness of the objective, and thus -applicability of the large deviation bounds stated in Proposition 1.

2. The standard theoretical results on the SAA of a stochastic optimization problem [START_REF] Andersen | The MOSEK optimization toolbox for MATLAB manual[END_REF], see, e.g. [START_REF] Nemirovski | Stochastic approximation approach to stochastic programming[END_REF][START_REF] Shapiro | Lectures on stochastic programming: modeling and theory[END_REF] and references therein, are aimed at quantifying the sample size N = N (ǫ) which, with overwhelming probability, ensures that an optimal solution x(ξ N ) to the SAA of the problem of interest satisfies the relation f (x(ξ N )) ≤ Opt + ǫ, for a given ǫ > 0. The corresponding bounds on N are similar, but not identical, to the bounds in Proposition 1. Let us consider, for instance, the simplest case of "Euclidean geometry" where x = x 2 = x, x , ω(x) = 1 2 x 2 , and X is the unit • 2 -ball. In this case Proposition 1 states that for a given ǫ > 0, the sample size N for which Opt(ξ N ) is, with probability at least 1α, ǫ-close to Opt, can be upper-bounded for small enough ǫ and α by

N ǫ = O(1) [M 1 + M 2 ] 2 ln(1/α)
ǫ 2 (here and in what follows, O(1)'s are positive absolute constants). It should be stressed that both the bound itself and the range of "small enough" values of ǫ, α for which this bound is valid are independent of the dimension n of the decision vector x. In contrast to this, available estimation of the complexity N (ǫ) is affected by problem's dimension: up to logarithmic terms, N (ǫ) = nN ǫ . This phenomenon -linear dependence on the problem's dimension n of the SAA sample size yielding, with high probability, an ǫ-optimal solution to a stochastic problem -is not an artifact stemming from an imperfect theoretical analysis of the SAA but reflects the actual performance of SAA on some instances. Indeed, we have the following: Proposition 2. For any n ≥ 3, and R, L > 0 one can point out a convex Lipschitz continuous with constant L function f on the Euclidean ball B 2 (R) of radius R, and convex in 2 2 ≤ L a.s., for all x ∈ B 2 (R), and such that with probability at least 1e -1 there is an optimal solution x(ξ N ) to the SAA

x integrand F (x, ξ) such that E ξ {F (x, ξ)} = f (x), F ′ (x, ξ) -f ′ (x)
min f N (x) = 1 N N i=1 F (x, ξ i ) : x ∈ B 2 (R) , sampled over N ≤ n i.i.d. realizations of ξ, satisfying f (x(ξ N )) -Opt ≥ c 0 LR, (7)
where c 0 is a positive absolute constant.

Note that for large-scale problems, the presence of the factor n in the sample size bound is a definite and serious drawback of SAA. A nice fact about the SAA approach as expressed by Proposition 1, is that as far as reliable ǫ-approximation of the optimal value (rather than building an ǫ-solution) is concerned, the performance of the SAA approach, at least in the case of favorable geometry, is not affected by the problem's dimension. It should be stressed that the crucial role in Proposition 1 is played by convexity which allows us to express the quality to which the SAA reproduces the optimal value in (1) in terms of how well f N (x, ξ N ) reproduces the first order information on f at a single point x * ∈ Argmin X f , see the proof of Proposition 1. In a "favorable geometry" situation, e.g., in the Euclidean geometry case, the corresponding sample size is not affected by problem's dimension. In contrast to this, to yield reliably an ǫ-solution, the SAA requires, in general, f N (x, ξ N ) to be ǫ-close to f uniformly on X with overwhelming probability; and the corresponding sample size, even in the case of Euclidean geometry, grows with problem's dimension.

3. Note that (at least in the case of Euclidean geometry) without additional, as compared to those in Proposition 1, restrictions on F and/or the distribution P , the quality of the SAA estimate Opt N (ξ N ) of Opt (and thus, the quality of the confidence interval for it provided by Corollary 1) is, within an absolute constant factor, the best allowed by the laws of Statistics. Namely, we have the following lower bound for the widths of the confidence intervals for the optimal value valid already for a class of linear stochastic problems.

Proposition 3. For any n ≥ 1, M 1 ≥ M 2 > 0, one can point out a family of linear stochastic optimization problems, i.e., linear functions f on the unit Euclidean ball B 2 of R n and corresponding linear in x integrands F (•, ξ) such that E ξ {F (x, ξ)} = f (x), satisfying the premises of Proposition 1 and Corollary 1, and such that the width of the confidence interval for Opt = min x∈B 2 f (x) of covering probability ≥ 1α cannot be less than

W = 2γErfInv(α) M 1 √ N , (8)
where ErfInv(•) is the inverse error function:

ErfInv(α) = t, 0 < α < 1, where α = (2π) -1/2 ∞ t exp{-s 2 /2}ds,
and γ > 0 is given by the relation

E ζ∼N (0,1) exp{γ 2 ζ 2 } = exp{1}, or, equivalently, γ 2 = 1 2 (1 -exp{-2}).
In Table 1, we provide the ratios R W of the widths of the confidence intervals, as given by Corollary 1 and their lower bounds for some combinations of risks α and parameters M 1 , M 2 and N .

α = 0.1 M 1 = M 2 = 1 M 1 = 10, M 2 = 1 M 1 = 100, M 2 =
α = 0.001 M 1 = M 2 = 1 M 1 = 10, M 2 = 1 M 1 = 100, M 2 =

Constrained case

Now consider a convex stochastic problem of the form

Opt = min x∈X f 0 (x) := Ξ F 0 (x, ξ)P (dξ) : f i (x) := Ξ F i (x, ξ)P (dξ) ≤ 0, 1 ≤ i ≤ m , (9)
where, similarly to the above, X is a convex compact set in a Euclidean space E, P is a Borel probability distribution on R k , Ξ is the support of P , and

F i (x, ξ) : E × Ξ → R, 0 ≤ i ≤ m,
are Borel functions convex in x and P -summable in ξ for every x, so that the functions f i , 0 ≤ i ≤ m, are convex. As in the previous section, we assume that E is equipped with a norm • , the conjugate norm being • * , and a compatible with • distance-generating function for the unit ball B • of the norm.

Assuming that we can sample from the distribution P , and given a sample size N , we can build Sample Average Approximations (SAA's) of functions f i , 0 ≤ i ≤ m:

f i,N (x, ξ N ) = 1 N N t=1 F i (x, ξ t ).
Here, as above, ξ 1 , ξ 2 , ... are drawn, independently of each other from P and ξ N = (ξ 1 , ..., ξ N ). Same as above, we want to use these SAA's of the objective and the constraints of ( 9) to infer conclusions on the optimal value of the problem of interest [START_REF] Lan | Validation analysis of mirror descent stochastic approximation method[END_REF]. Our first observation is that in the constrained case, one can hardly expect a reliable and tight approximation to Opt to be obtainable from noisy information. The reason is that in the general constrained case, even the special one where F i (and thus f i ) are affine in x, the optimal value is highly unstable: arbitrarily small perturbations of the data (e.g., the coefficients of affine functions F i in the special case or parameters of distribution P ) can result in large changes in the optimal value. As a result, with noisy observations of the data, one hardly could expect to get a good estimate of Opt via a sample of instance-independent size. The standard remedy is to impose an priori upper bound on the magnitude of optimal Lagrange multipliers for the problem of interest, e.g., by imposing the assumption that this problem is strictly feasible, with the level of strict feasibility

β := -min x∈X max[f 1 (x), ..., f m (x)] (10)
lower-bounded by a known in advance positive quantity. Since in many cases an priori lower bound on β is unavailable, we intend in the sequel to utilize an alternative approach, specifically, as follows. Let us associate with (9) the univariate (max-)function

Φ(r) = min x∈X max[f 0 (x) -r, f 1 (x), ..., f m (x)].
Clearly, Φ is a continuous convex nonincreasing function of r ∈ R such that Φ(r) → ∞ as r → -∞. This function has a zero if and only if ( 9) is feasible, and Opt is nothing but the smallest zero of Φ.

Definition 1. Given ǫ > 0, a real ρ ǫ-underestimates Opt if ρ ≤ Opt and Φ(ρ) ≤ ǫ. Note that Φ(ρ) ≤ ǫ implies that ρ ≥ Opt(ǫ) := min x∈X [f 0 (x) -ǫ : f i (x) ≤ ǫ, 1 ≤ i ≤ m] .
Thus, ρ ǫ-underestimates Opt if and only if ρ is in-between the optimal value of the problem of interest ( 9) and the problem obtained from ( 9) by "optimistic" ǫ-perturbation of the objective and the constraints.

Remark. Let ρ ǫ-underestimate Opt. When ( 9) is feasible and the magnitude λ of the left derivative Φ(•) taken at Opt is positive, from convexity of Φ it follows that

Opt - ǫ λ ≤ ρ < Opt.
Thus, unless λ is small, ρ is an O(ǫ)-tight lower bound on Opt. Note that when ( 9) is strictly feasible, λ indeed is positive, and it can be bounded away from zero. Indeed, we have the following Lemma 1. Let λ be the left derivative of Φ at Opt and assume that β given by (10) is positive.

Then λ ≥ β V + β , V = max x∈X f 0 (x) -Opt.
In respect to the constrained problem (9), our main result is as follows:

Proposition 4. Let L(x, ξ) = max 0≤i≤m { g -h * : g ∈ ∂ x F i (x, ξ), h ∈ ∂f i (x)} .
Assume that f i , 0 ≤ i ≤ m, are differentiable on X, and that for some positive M 1 , M 2 one has for i = 0, 1, ..., m:

E e (F i (x,ξ)-f i (x)) 2 /M 2 1 ≤ e, E e L 2 (x,ξ)/M 2 2 ≤ e
for all x from an open set X + containing X. Assume also that (9) is feasible. Assume that for

N ∈ Z + , s > 1, and λ, µ ∈ [0, 2 √ α * N ], ǫ and β satisfy ǫ > 2N -1/2 µM 1 + M 2 R Ω 2 [1 + s 2 ] + λ , β = e -N (s 2 -1) + e -λ 2 4α * + (m + 2)e -µ 2 4α * , ( 11
)
where Ω is given by (2), and α * is given in Proposition 1. Then the random quantity

Opt N (ξ N ) = min x∈X f 0,N (x, ξ N ) -µM 1 N -1/2 : f i,N (x, ξ N ) -µM 1 N -1/2 ≤ 0, 1 ≤ i ≤ m ǫ-underestimates Opt with probability ≥ 1 -β.
MinMax Stochastic Optimization. The proof of Proposition 4 also yields the following result which is of interest by its own right:

Proposition 5. In the notation and under assumptions of Proposition 4, consider the minimax problem Opt = min

x∈X max[f 1 (x), ..., f m (x)] (12)
along with its Sample Average Approximation

Opt N (ξ N ) = min x∈X max[f 1,N (x, ξ N ), ..., f m,N (x, ξ N )].
Then for every N ∈ Z + , s > 1 and λ, µ

∈ [0, 2 √ α * N ] one has Prob Opt N (ξ N ) > Opt + µM 1 N -1/2 ≤ me -µ 2 4α * (13)
and

Prob Opt N (ξ N ) < Opt -µM 1 + 2M 2 Ω 2 [1 + s 2 ] + 2λ N -1/2 ≤ e -µ 2 4α * + 2 e -N (s 2 -1) + e -λ 2 4α * . ( 14
)
An attractive feature of bounds ( 13) and ( 14) is that they are only weakly affected by the number m of components in the minimax problem [START_REF] Nemirovski | Stochastic approximation approach to stochastic programming[END_REF].

Numerical experiments

The goal of the experiments of this section is to illustrate numerically some ideas developed above.

Confidence intervals for problems without stochastic constraints

Here we consider three risk-averse optimization problems of the form (1) and we compare the properties of three confidence intervals for Opt computed for the confidence level 1α = 0.9:

1. the asymptotic confidence interval

C a (α) = fN (x(ξ N )) -q N 1 - α 2 σN √ N , fN (x(ξ N )) + q N 1 - α 2 σN √ N . (15)
Here x(ξ N ) is an optimal solution of the SAA (3) built using the N -sample ξ N and q N (α) stands for the α-quantile of the standard normal distribution. The values

fN (x(ξ N )) = 1 N N t=1 F (x(ξ N ), ξt ), σ2 N = 1 N N t=1 F (x(ξ N ), ξt ) 2 -fN (x(ξ N )) 2 (16)
are computed using the second sample ξN of size N independent of ξ N (for a justification, see [START_REF] Shapiro | Lectures on stochastic programming: modeling and theory[END_REF]).

2. The (non-asymptotic) confidence interval C SMD (α) is built using the offline accuracy certificates for the Stochastic Mirror Descent algorithm, cf. Section 3.2 and Theorem 2 of [START_REF] Lan | Validation analysis of mirror descent stochastic approximation method[END_REF]. The non-Euclidean algorithm with entropy distance-generating function provided the best results in these experiments and was used for comparison.

3. The (non-asymptotic) confidence interval, denoted C SAA (α), is based on bounds of Proposition 1. Specifically, we use the lower 1α/2-confidence bound Low SAA of Corollary 1. To construct the upper bound we proceed as follows: first we compute the optimal solution x(ξ N ) of the SAA using a simulation sample ξ N of size N ; then we compute an estimation f (x(ξ N )) of the objective value using the independent sample ξN as in [START_REF] Robbins | A stochastic approximation method[END_REF]. Finally, we build the upper confidence bound

Up ′ = f (x(ξ N )) + 2M 1 α * ln[4α -1 ] N ,
where α * and M 1 are as in Proposition 1 (cf. the bound ( 5)). Finally, the upper bound Up SAA computed as the minimum of Up ′ and the upper bound Up SAA by Proposition 1, tuned for the confidence level 1α/4, was used. 1For the sake of completeness, for three optimization problems considered in this section we provide the detail of computing of the constants involved in Appendix B. SAA formulations of these problems were solved numerically using Mosek Optimization Toolbox [START_REF] Andersen | The MOSEK optimization toolbox for MATLAB manual[END_REF].

Quadratic risk minimization

Consider the following instance of problem (1): let X be the standard simplex of

R n : X = {x ∈ R n : x i ≥ 0, n i=1 x i = 1}, Ξ is a part of the unit box {ξ = [ξ 1 ; ...; ξ n ] ∈ R n : ξ ∞ ≤ 1}, F (x, ξ) = α 0 ξ T x + α 1 2 ξ T x 2 , f (x) = α 0 µ T x + α 1 2 x T V x,
with α 1 ≥ 0 and µ = E{ξ}, V = E{ξξ T }.

In our experiments, α 0 = 0.1, α 1 = 0.9, and ξ has independent Bernoulli entries: Prob(ξ i = 1) = θ i , Prob(ξ i = -1) = 1θ i , with θ i drawn uniformly over [0, 1]. This implies that

µ i = 2θ i -1, V i,j = E{ξ i }E{ξ j } = (2θ i -1)(2θ j -1) for i = j, E{ξ 2 i } = 1 for i = j.
For several problem and sample sizes, we present in Table 2 the empirical "coverage probabilities" of the "asymptotic" confidence interval C a (α) for α = 0.1 ("target" coverage probability 1-α = 0.9) computed over 500 realizations (the coverage probabilities of the two non-asymptotic confidence intervals are equal to one for all parameter combinations). We observe that empirical coverage probabilities degrade when the problem size n increases (and, as expected, they tend to increase with the sample size). For instance, these probabilities are much smaller than the target coverage probability, unless the size N of the simulation sample is much larger than the problem dimension n. On the other hand, not surprisingly, the non-asymptotic bounds yield confidence intervals much larger than the asymptotic confidence interval. We report in Table 3 the mean ratio of the widths of non-asymptotic -C SAA (α) and C SMD (α) -and asymptotic confidence intervals C a (α). 2 These ratios increase significantly with problem size (in part because the asymptotic interval becomes indeed too short), and we observe that the confidence interval C SAA (α) based on Sample Average Approximation remains much smaller than the interval C SMD (α) yielded by Stochastic Approximation. Finally, on Figure 1 we compare average over 100 problem realizations "inaccuracies" of approximate solutions delivered by SAA and SMD for "typical" problem instances of size n = 100 for two combinations of parameters α 0 and α 1 .

Markowitz portfolio optimization

We consider the instance of problem (1) where X ⊂ R n is the standard simplex, ξ has normal distribution N (0, Σ) on R n with Σ i,i ≤ σ max , and that f (x) = α 1 2/π √ x T Σx. We generated instances of the problem of different size with α 0 = 0.9, α 1 = 0.1, and diagonal matrix Σ with diagonal entries drawn uniformly over [START_REF] Andersen | The MOSEK optimization toolbox for MATLAB manual[END_REF][START_REF] Juditsky | Large deviations of vector-valued martingales in 2smooth normed spaces[END_REF] (σ max = √ 6). We reproduce the experiments of the previous section in this setting, namely, for several problem and sample sizes, we compute empirical "coverage probabilities" of the confidence intervals over 500 realizations. We report the results for the "asymptotic" confidence interval C a (α) in Table 4 for "target" coverage probability 1α = 0.9 (same as above, coverage probabilities of non-asymptotic intervals are equal to one for all parameter combinations). We especially observe extremely low coverage probabilities for n = 100 and N = 20 or N = 100.

F (x, ξ) = α 0 ξ T x + α 1 |ξ T x|,
In Table 5 the average ratios of the widths of non-asymptotic and asymptotic confidence intervals are provided for the same experiment. Same as in the experiments described in the previous section, these ratios increase with problem size, and the confidence intervals by SMD are much more conservative than those by SAA.

On Figure 2 we present average over 100 problem realizations "inaccuracies" of approximate solutions delivered by SAA and SMD for "typical" problem instances of size n = 100.

CVaR optimization

We consider here the following CVaR optimization problem: given ε > 0, find

Opt ε = min x ′ α 0 E{ξ T x ′ } + α 1 CVaR ε (ξ T x ′ ) x ′ ∈ R n n i=1 x ′ i = 1, x ′ ≥ 0, (17)
where the support Ξ of ξ is a part of the unit box {ξ = [ξ 1 ; ...; ξ n ] ∈ R n : ξ ∞ ≤ 1}, and where is the Conditional Value-at-Risk of level 0 < ε < 1, see [START_REF] Rockafellar | Conditional value-at-risk for general loss distributions[END_REF]. Observing that |ξ T x ′ | ≤ 1 a.s., the above problem is clearly of the form (1) with

CVaR ε (ξ T x ′ ) = min x 0 ∈R {x 0 + E{ε -1 [ξ T x ′ -x 0 ] + }
X = {x = [x 0 ; x ′ 1 ; ...; x ′ n ] ∈ R n+1 : |x 0 | ≤ 1, x ′ 1 , ..., x ′ n ≥ 0, n i=1 x ′ i = 1} and F (x, ξ) = α 0 ξ T x ′ + α 1 x 0 + 1 ǫ [ξ T x ′ -x 0 ] + .
We consider random instances of the problem with α 0 , α 1 ∈ [0, 1], and ξ with independent Bernoulli entries: Prob(ξ i = 1) = θ i , Prob(ξ i = -1) = 1θ i , with θ i , i = 1, ..., n drawn uniformly from [0, 1]. We compare the non-asymptotic confidence interval C SAA (α) for Opt ε to the asymptotic confidence interval C a (α) with confidence level 1α = 0.9. We consider two sets of problem parameters: (α 0 , α 1 , ε) = (0.9, 0.1, 0.9) and the risk-averse variant (α 0 , α 1 , ε) = (0.1, 0.9, 0.1). The empirical coverage probabilities for the asymptotic confidence interval are reported in Table 6. As in other experiments, the coverage probability still below the target probability of 1α = 0.9 when the sample size is not much larger than the problem size. For SAA, the coverage probabilities are equal to one for all parameter combinations.

We report in Table 7 the average ratio of the widths of non-asymptotic and asymptotic confidence intervals. Note that the Lipschitz constant of F (•, ξ) is proportional to 1/ε when ε is small. This explains the fact that for small values of ǫ, the ratio of the widths of the proposed non-asymptotic and asymptotic confidence intervals grows up significantly, especially for problem size n + 1 = 3.

The experiments of this section also show that when the sample size is not much larger than the problem dimension, the asymptotic computations fail to provide the confidence set of the prescribed risk. In such case the proposed approach, though conservative, seems to be the only option available for constructing a reliable confidence interval.

Lower bounding the optimal value of a minimax problem

We illustrate here the application of Proposition 5 to lower bounding the optimal value of the MinMax problem [START_REF] Nemirovski | Stochastic approximation approach to stochastic programming[END_REF]. To this end we consider a toy problem Opt = min

x max f i (x), i = 1, ..., 3, x = [u; v] v ∈ R, u ∈ R n , n i=1 u i = 1, u ≥ 0 , (18)
where

f 1 (x) = v + E{ε -1 [ξ T u -v] + } + ρ 1 , f 2 (x) = E{ξ T u} + ρ 2 , f 3 (x) = ρ 3 -E{ξ T u},
ε and ρ being some given parameters. The SAA of the problem reads

Opt(ξ N ) = min x max f i,N (x), i = 1, ..., 3, x = [u; v] v ∈ R, u ∈ R n , n i=1 u i = 1, u ≥ 0 , (19)
with

f 1,N (x) = v + 1 N ε N t=1 [ξ T t u -v] + , f 2,N (x) = 1 N N t=1 ξ T t u + ρ 2 , f 3,N (x) = ρ 3 - 1 N N t=1 ξ T t u.
One can try to build an "asymptotic" lower bound for Opt as follows (note that here we are not concerned with theoretical validity of this construction): given the optimal solution x(ξ N ) to the SAA ( 19), compute empirical variances σ i,N of F i (x(ξ N ), ξ), then compute the lower bound "of asymptotic risk α" according to Opt(ξ N ) = max i=1,...,3

f i,N (x(ξ N )) -q N 1 - α 3 σ i,N √ N .
On Figure 4 we present the simulation results for the case of ξ ∈ R n with independent Bernoulli components: Prob(ξ i = 1) = θ i , Prob(ξ i = -1) = 1θ i , with θ i randomly drawn over [0, 1]; parameters ρ i , i = 1, 2, 3 are chosen in a way to ensure that f 1 -f 3 are approximately equal at the minimizer of [START_REF] Shapiro | Asymptotic analysis of stochastic programs[END_REF]. The results of 100 simulations of the problem with n = 2 and N = 128 are presented on Figure 4 for the value of CVaR parameter ε = 0.5 and ε = 0.1. Note that in this case the risk of the lower bound Opt(ξ N ) is significantly larger than the prescribed risk ε = 0.1 already for small problem dimension -the "asymptotic" lower bound failed for 33% of 7 realizations in the experiment with ε = 0.5, and for 36% of realizations in the experiment with ε = 0.1.

Optimal value of a stochastically constrained problem

An SAA of a stochastically constrained problem, even with a single linear constraint, can easily become unstable when the constraint is "stiff". As a simple illustration, let us consider a stochastically (linearly) constrained problem where

Opt ρ = min x f 0 (x) : f 1 (x) ≤ 0, x = [u; v], v ∈ R, u ∈ R n , n i=1 u i = 1, u ≥ 0 , (20)
f 0 (x) = v + E{ε -1 [ξ T u -v] + }, and f 1 (x) = ρ -E{ξ T u},
and ε and ρ are problem parameters. The SAA of the problem is

Opt ρ (ξ N ) = min x=[u;v] f 0,N (x) : f 1,N (x) ≤ 0, v ∈ R, u ∈ R n , n i=1 u i = 1, u ≥ 0 , (21)
where

f 0,N (x) = v + 1 N ε N t=1 [ξ T t u -v] + , and f 1,N (x) = ρ - 1 N N t=1 ξ T t u.
Consider now a toy example of the problem with u ∈ R 2 , ξ ∼ N (µ, Σ) with µ = [0.1; 0.5] and Σ = diag( [1; 4]). Let N = 128, ρ = 0.3, and ε = 0.1. One can expect that in this case the optimal value Opt(ξ N ) of the SAA is unstable (in fact, the problem ( 21) is infeasible with probability Prob

1 N N t=1 ξ t,2 < ρ = Prob 2N (0,1)
√ N ≤ -0.2 = 0.128...). We compare the solution to (21) with the SAA in which the r.-h.s. ρ of the stochastic constraint is replaced with ρδ where δ = q N (1-ε/n) σmax √ N 0.5815..., σ max = max i Σ i,i . On Figure 5 we present the simulation results of 100 independent realizations of the above problem. As expected, the SAA ( 21) is unstable; the problem turned infeasible in 22% of realizations. The SAA with the relaxed constraint exhibits much better stability.

A Proofs

A.1 Preliminaries: Large deviations of vector-valued martingales

The result to follow is a slightly simplified and refined version of the bounds on probability of large deviations for vector-valued martingales developed in [START_REF] Juditsky | Large deviations of vector-valued martingales in 2smooth normed spaces[END_REF][START_REF] Nemirovski | Stochastic approximation approach to stochastic programming[END_REF]. Let • be a norm on Euclidean space E, • * be the conjugate norm, and B • be the unit ball of the norm. Further, let ω be a continuously differentiable distance-generating function for B • compatible with the norm • and attaining its minimum on B • at the origin: ω ′ (0) = 0, with ω(0) = 0 and Ω = max x: x ≤1 2[ω(x)].

Lemma 2. Let d 1 , d 1 , ... be a scalar martingale-difference such that for some σ > 0 it holds

E{e d 2 t /σ 2 |d 1 , ..., d t-1 } ≤ e a.s., t = 1, 2, ... Then Prob N t=1 d t D N > λσ √ N ≤    e -λ 2 4α * , 0 ≤ λ ≤ 2 √ α * N , e -λ 2 3 , λ > 2 √ α * N , (22)
where α * is defined in Proposition 1.

Proof. Assuming without loss of generality that σ = 1 observe that under Lemma's premise we have E{e α * θ 2 d 2 t |d 1 , ..., d t-1 } ≤ e α * θ 2 whenever α * θ 2 ≤ 1 where α * is defined in Proposition 1, and therefore for almost all d t-1 = (d 1 , ..., d t-1 ) we have for 0

≤ θ ≤ 1 √ α * E e θdt d t-1 ≤ E θd t + e α * θ 2 d 2 t d t-1 = E e α * θ 2 d 2 t d t-1 ≤ e α * θ 2 . ( 23
)
Thus, for 0 ≤ θ ≤ 1 √ α * , we have E{e θD N } ≤ e α * θ 2 N , and ∀λ > 0

Prob{D N > λ √ N } ≤ e α * θ 2 N -λθ √ N .
When minimizing the resulting probability bound over 0 ≤ θ ≤ 1 √ α * we get the inequality [START_REF] Srebro | Stochastic optimization for machine learning[END_REF]

for λ ∈ [0, 2 √ α * N ]: Prob{D N > λ √ N } ≤ e -λ
Then for every s > 1, we have

Prob N t=1 χ t * > σ Ω √ N 2 [1 + s 2 ] + λ √ N ≤    e -N (s 2 -1) + e -λ 2 4α * , 0 ≤ λ ≤ 2 √ α * N, e -N (s 2 -1) + e -λ 2 3 , λ > 2 √ α * N , (25)
where α * is defined in Proposition 1 and Ω is given by (2).

Proof. By homogeneity, it suffices to consider the case when σ = 1, which we assume from now on.

1 0 . Let γ > 0. We denote

V x (u) = ω(u) -ω(x) -ω ′ (x), u -x [u, x ∈ B • ]
and consider the recurrence

x 1 = 0, x t+1 = argmin y∈B • [V xt (y) -γχ, y ] .
Observe that x t is a deterministic function of χ t-1 = (χ 1 , ..., χ t-1 ), and that by the standard properties of proximal mapping (see. e.g. [12, Lemma 2.1]),

∀(u ∈ B • ) : γ N t=1 χ t , u -x t ≤ V 0 (u) -V x N+1 (u) + γ 2 2 N t=1 χ t 2 * ≤ 1 2 Ω 2 + γ 2 2 N t=1 χ t 2 * . Thus max u∈B • N t=1 χ t , u ≤ Ω 2 2γ + γ 2 N t=1 χ t 2 * η N + N t=1 χ t , x t ζ N . Setting γ = Ω/ √ N , we arrive at max u∈B • N t=1 χ t , u ≤ Ω √ N 2 1 + η N N + ζ N . (26)
Invoking (24), we get E{e η N } ≤ e N (recall that σ = 1), whence

∀s > 0 : Prob η N > s 2 N ≤ min 1, e N (1-s 2 ) . ( 27
)
2 0 . When invoking (24) and taking into account that x t is a deterministic function of χ t-1 such that x t ≤ 1 (since

x t ∈ B • ), we get E{ χ t , x t |χ t-1 } = 0, E{e χt,xt 2 |χ t-1 } ≤ e (28)
Applying Lemma 2 to the random sequence d t = χ t , x t , t = 1, 2, ... (which is legitimate, with σ set to 1, by ( 28)), we get

Prob ζ N > λ √ N ≤    e -λ 2 4α * , 0 ≤ λ ≤ 2 √ α * N , e -λ 2 3 , λ > 2 √ α * N . (29)
In view of ( 27) and (29), relation (26) implies the bound (25) of the proposition.

A.2 Proof of Proposition 1

Let x * be an optimal solution to (SP), and let h = ∇f (x * ), so that by optimality conditions

h, x -x * ≥ 0 ∀x ∈ X. ( 30
)
1 0 . Setting δ(ξ) = F (x * , ξ) -f (x * ), invoking (4.
a) and applying Lemma 2 to the random sequence d t = δ(ξ t ) and σ = M 1 (which is legitimate by (4.a)), we get

∀(N ∈ Z + , µ ∈ [0, 2 α * N ]) : Prob 1 N N t=1 δ(ξ t ) > µM 1 N -1/2 ≤ e -µ 2 4α * . (31)
Since clearly

Opt N (ξ N ) ≤ f N (x * , ξ N ) = Opt + 1 N N t=1 δ(ξ t ), we get Prob Opt N (ξ N ) > Opt + µM 1 N -1/2 ≤ e -µ 2 4α * . ( 32
)
2 0 . It is immediately seen that under the premise of Proposition 1, for every measurable vectorvalued function g(ξ) ∈ ∂ x F (x * , ξ) we have

h = Ξ g(ξ)P (dξ). ( 33
) Observe that h N (ξ N ) = 1 N N t=1 g(ξ t ) is a subgradient of f N (x, ξ N ) at the point x * . Conse- quently, for all x ∈ X, f N (x, ξ N ) ≥ f N (x * , ξ N ) + h N (ξ N ), x -x * ≥ [f (x * ) + h, x -x * ]
≥Opt by ( 30)

+[[f N (x * , ξ N ) -f (x * )] + h N (ξ N ) -h, x -x * ] ≥ Opt + 1 N N t=1 δ(ξ t ) -h -h N (ξ N ) * x -x * ≥ Opt + 1 N N t=1 δ(ξ t ) -2 h -h N (ξ N ) * R
(the concluding inequality is due to x, x * ∈ X and thus x -

x * ≤ 2R by definition of R). It follows that Opt N (ξ N ) ≥ Opt + 1 N N t=1 δ(ξ t ) -2 h -h N (ξ N ) * R. (34)
Applying Lemma 2 to the random sequence d t = -δ(ξ t ) we, similarly to the above, get

∀(N, µ ∈ [0, 2 α * N ]) : Prob 1 N N t=1 δ(ξ t ) < -µM 1 N -1/2 ≤ e -µ 2 4α * . (35)
Further, setting ∆(ξ) = g(ξ) -∇f (x * ), the random vectors χ t = ∆(ξ t ), t = 1, 2, ..., are i.i.d., zero mean (by (33)), and satisfy the relation

E e χt 2 * /M 2 2 ≤ e by (4.b); besides this, h N (ξ N ) -h = 1 N N t=1 χ t . Applying Proposition 6, we get ∀(N ∈ Z + , s > 1, λ ∈ [0, 2 √ α * N ]) : Prob{ h -h N (ξ N ) * ≥ M 2 Ω 2 [1 + s 2 ] + λ N -1/2 } ≤ e -N (s 2 -1) + e -λ 2 4α * .
This combines with (34), and (35) to imply [START_REF] Juditsky | Large deviations of vector-valued martingales in 2smooth normed spaces[END_REF].

A.3 Proof of Proposition 2

Due to similarity reasons, it suffices to prove the proposition for L = R = 1. Let B 2 be the unit Euclidean ball of R n , and let for a unit v ∈ R n and 0 < θ ≤ π/2, h v,θ be the spherical cap of B 2 with "center" v and angle θ. In other words, if δ = 2 sin 2 (θ/2) is the "elevation" of the cap

h v,θ then h v,θ = {x ∈ B 2 : v T x ≥ 1 -δ}.
Observe that for any ϑ > 4θ we can straightforwardly build the system D θ of vectors in the n-dimensional unit sphere S n-1 in such a way that the angle between every two distinct vectors of the system is > 2θ, so that the spherical caps h v,θ with v ∈ D θ are mutually disjoint, while the spherical caps h v,ϑ cover S n-1 . If we denote A n-1 (ϑ) the area of the spherical cap of angle ϑ ≤ π/2, then Card(D θ )A n-1 (ϑ) ≥ s n-1 (1), where

s n-1 (r) = 2π n/2 r n-1 Γ(n/2)
is the area of the n-dimensional sphere of radius r. Note that A n-1 (ϑ) satisfies

A n-1 (ϑ) = ϑ 0 s n-2 (sin t)dt = s n-2 (1) ϑ 0 sin n-2 tdt ≤ s n-2 (1) ϑ 0 t n-2 dt = s n-2 (1)
ϑ n-1 n -1 .

We conclude that

Card(D θ ) ≥ s n-1 (1)(n -1) s n-2 (1)ϑ n-1 ≥ 3ϑ 1-n
for n ≥ 2. From now on we fix θ = 1/8 and when choosing ϑ arbitrarily close to 4θ = 1 2 , we conclude that for any n ≥ 2 one can build D θ such that Card(D θ ) ≥ 2 n . Now consider the following construction:

for v ∈ D θ , let g v,θ (•) : B 2 → R be defined according to g v,θ (x) = [v T x -(1 -δ)] + ,
F (x, ξ) = v∈D θ 2ξ v g v,θ (x)
v = 0} = Prob{ξ v = 1} = 1 2 . Note that E ξ {F (x, ξ)} = f (x) ∀x ∈ B 2 . Further, for x ∈ h v,θ , E ξ {F (x, ξ) 2 -f (x) 2 } = g 2 v,θ (x) ≤ δ 2 , and F ′ (x, ξ) -f ′ (x) 2 2 = (2ξ v -1)g ′ v,θ (x) 2 2 ≤ 1. Let us now consider the SAA f N (x) of f , f N (x) = 1 N N t=1 F (x, ξ t ) = v∈D θ 1 N N t=1 ξ t,v g v,θ (x) g N v,θ (x) , (36)
ξ t , t = 1, ..., N being independent realizations of ξ, and the problem of computing

Opt(ξ N ) = min[f N (x) : x ∈ B 2 ]. ( 37
)
Note that for a given v ∈ D θ , Prob{ N t=1 ξ t,v = 0} = 2 -N . Due to the independence of ξ v , we have

Prob N t=1 ξ t,v > 0, ∀v ∈ D θ = (1 -2 -N ) Card(D θ ) ≤ (1 -2 -N ) 2 n ≤ e -2 n 2 N ≤ exp(-1),
for N ≤ n. We conclude that for N ≤ n, with probability ≥ 1-e -1 , at least one of the summands in the right-hand side of (36), let it be g N v,θ (x), is identically zero on B 2 . The optimal value Opt(ξ N ) of (37) being zero, the point x(ξ N ) = v is clearly a minimizer of f N (x) on B 2 , yet f (x(ξ N )) = δ, i.e., [START_REF] King | Asymptotic theory for solutions in statistical estimation and stochastic programming[END_REF] holds with c 0 = δ.

A.4 Proof of Proposition 3 1 0 . Let us consider a family of stochastic optimization problems as follows. Let • = • 2 and let X be the unit • 2 -ball in R n . Given a unit vector ✚ ✚ g, h in R n , positive reals σ, s and δ, d, and setting ξ = [η; ζ] ∼ N (0, I 2 ), consider two integrants:

F 0 (x, ξ) = σηh T x + sζ, F 1 (x, ξ) = (δh + σηh) T x + (sζ -d), so that f 0 (x) := E ξ {F 0 (x, ξ)} = 0, f 1 (x) := E ξ {F 1 (x, ξ)} = δh T x -d.
Let us now check that F 0 and F 1 verify the premises of Proposition 1. In the notation of Proposition 1, we have for

F 1 L(x, ξ) = [δh + σηh] -δh 2 = σ|η|, whence, setting M 2 = σ/γ with γ 2 = 1 2 (1 -e -2
),

E ξ exp{L(x, ξ) 2 /M 2 2 } = exp{1}.
Similarly, setting M 1 = √ σ 2 + s 2 /γ, we have

E ξ exp{(ση + sζ) 2 /M 2 1 } = exp{1},
so that, for every z ∈ [-1, 1],

E ξ exp{(σηz + sζ) 2 /M 2 1 } ≤ exp{1}. When x ∈ R n and x 2 ≤ 1, we have F 1 (x, ξ) -f 1 (x) = σηh T x + sζ, therefore E ξ exp{(F 1 (x, ξ) -f 1 (x)) 2 /M 2 1 } ≤ exp{1}.
We conclude that F = F 1 satisfies the premise of Proposition 1 with

M 1 = σ 2 + s 2 /γ, M 2 = σ/γ.
It is immediately seen that F = F 0 satisfies the premise of Proposition 1 with the same M 1 , M 2 .

2 0 . Now, with X = {x ∈ R n : x 2 ≤ 1}, the optimal values in the problems of minimizing over X the functions f 0 and f 1 are, respectively, Opt 0 = 0, Opt 1 = -δd.

Suppose that there exists a procedure which, under the premise of Proposition 1 with some fixed M 1 , M 2 , is able, given N observations of ∇ x F (•, ξ t ), F (•, ξ t ), to cover Opt, with confidence 1α, by an interval of width W . Note that when W < |Opt 1 |, the same procedure can distinguish between the hypotheses stating that the observed first order information on f comes from F 0 or from F 1 , with risk (the maximal probability of rejecting the true hypothesis) α. On the other hand, when F = F 0 or F = F 1 , our observations are deterministic functions of the samples ω 1 ,...,ω N drawn from the 2-dimensional normal distribution N 0 0 , σ 2 0 0 s 2 for F = F 0 , and N δ d , σ 2 0 0 s 2 for F = F 1 . It is well known that deciding between such hypotheses with risk ≤ α is possible only if

δ 2 σ 2 + d 2 s 2 ≥ 2 √ N Erfinv(α).
We arrive at the following lower bound on W , given

M 1 , M 2 , with M 1 ≥ M 2 > 0: W ≥ max δ≥0, d≥0 δ + d : δ 2 γ 2 M 2 2 + d 2 γ 2 (M 2 1 -M 2 2 ) ≤ 2 √ N Erfinv(α) = 2γM 1 √ N Erfinv(α) = W.

A.5 Proof of Lemma 1

Without loss of generality we may assume that Opt = 0. Let x be such that f i (x) ≤ -β, 1 ≤ i ≤ m. Given δ > 0, there exists x δ ∈ X such that f 0 (x δ ) + δ ≤ Φ(-δ) and f i (x δ ) ≤ Φ(-δ), 1 ≤ i ≤ m; note that Φ(-δ) > 0 due to -δ < 0 = Opt. The point

x = Φ(-δ) β + Φ(-δ) x + β β + Φ(-δ) x δ
belongs to X and is feasible for (9), since for i ≥ 1 one has

f i (x) ≤ Φ(-δ) β + Φ(-δ) f i (x) + β β + Φ(-δ) f i (x δ ) ≤ - Φ(-δ)β β + Φ(-δ) + βΦ(-δ) β + Φ(-δ) = 0. As a result, 0 = Opt ≤ f 0 (x) ≤ Φ(-δ) β + Φ(-δ) f 0 (x) + β β + Φ(-δ) f 0 (x δ ) ≤ Φ(-δ)V β + Φ(-δ) + β β + Φ(-δ) [Φ(-δ) -δ].
The resulting inequality implies (Φ(-δ) -Φ(0))/δ = Φ(-δ)/δ ≥ β/(β + V ); when passing to the limit as δ → +0, we get λ ≥ β/(V + β).

A.6 Proof of Proposition 4

Let us fix parameters N , s, λ, µ satisfying the premise of the proposition, let ǫ, δ be associated with these parameters according to [START_REF] Mak | Monte carlo bounding techniques for determining solution quality in stochastic programs[END_REF]. We denote f0,N (x, ξ

N ) = f 0,N (x, ξ N ) -µM 1 N -1/2 , fi,N (x, ξ N ) = f i,N (x, ξ N ) -µM 1 N -1/2 , 1 ≤ i ≤ m,
and set Φ N (r, ξ N ) = min x∈X max f0,N (x, ξ N )r, f1,N (x, ξ N ), ..., fm,N (x, ξ N ) .

Then Φ N (r, ξ N ) is a convex nonincreasing function of r ∈ R such that Opt N (ξ N ) = min{r : Φ N (r, ξ N ) ≤ 0}.
Finally, let r be the smallest r such that Φ(r) ≤ ǫ. Since ( 9) is feasible and Φ(r) → ∞ as r → -∞, r is a well defined real which is < Opt (since Opt is the smallest root of Φ) and satisfies Φ(r) = ǫ.

Let us set Ξ = ξ N : Φ N (Opt, ξ N ) ≤ 0 Ξ 1 ∩ ξ N : Φ N (r, ξ N ) > 0 Ξ 2 . Since Φ N (r, ξ N ) is a nonincreasing function of r and Opt N (ξ N ) is the smallest root of Φ N (•, ξ N ), for ξ N ∈ Ξ we have r ≤ Opt N (ξ N ) ≤ Opt.
The left inequality here implies that Φ(Opt N (ξ N )) ≤ ǫ (recall that Φ is nonincreasing and Φ(r) = ǫ). The bottom line is that when ξ N ∈ Ξ, Opt N (ξ N ) ǫ-underestimates Opt. Consequently, all we need to prove is that ξ N ∈ Ξ with probability at most δ.

1 0 . Let x * be an optimal solution to [START_REF] Lan | Validation analysis of mirror descent stochastic approximation method[END_REF]. Same as in the proof of Proposition 1, for every i, 0 ≤ 1 ≤ m, we have (see (31))

Prob f i,N (x * , ξ N ) > f i (x * ) + µM 1 N -1/2 ≤ e -µ 2 4α * ,
whence for the event

Ξ ′ = ξ N : f i,N (x * , ξ N ) ≤ f i (x * ) + µM 1 N -1/2 , 0 ≤ i ≤ m it holds Prob ξ N ∈ Ξ ′ ≤ (m + 1)e -µ 2 4α * . (38)
By the origin of x * we have f 0 (x * ) ≤ Opt and

f i (x * ) ≤ 0, 1 ≤ i ≤ m. Therefore, for ξ N ∈ Ξ ′ it holds f0,N (x * , ξ N ) ≤ Opt and fi,N (x * , ξ N ) ≤ 0, 1 ≤ i ≤ m, that is, Φ N (Opt, ξ N ) ≤ max[ f0,N (x * , ξ N ) -Opt, f1,N (x * , ξ N ), ..., fm,N (x * , ξ N )] ≤ 0,
implying that ξ N ∈ Ξ 1 . We conclude that Ξ ′ ⊂ Ξ 1 , and, by (38),

Prob{ξ N ∈ Ξ 1 } ≤ (m + 1)e -µ 2 4α * . ( 39
)
2 0 . We have ǫ = Φ(r) = min x∈X max[f 0 (x)r, f 1 (x), ..., f m (x)], whence by von Neumann's Lemma there exist nonnegative λ i ≥ 0, 0 ≤ i ≤ m, summing up to 1, such that

ǫ = min x∈X [ℓ(x) := λ 0 (f 0 (x) -r) + m i=1 λ i f i (x)] = min x∈X Ξ λ 0 [F 0 (x, ξ) -r] + m i=1 λ i F i (x, ξ) L(x,ξ) P (dξ) .
Under the premise of the proposition, the integrand F satisfies all assumptions of Proposition 1. Setting

ℓ N (x, ξ N ) = 1 N N i=1 L(x, ξ i )
and applying Proposition 1 we get

Prob    ξ N : min x∈X ℓ N (x, ξ N ) < min x∈X ℓ(x) =ǫ -µM 1 + Ω[1 + s 2 ] + 2λ M 2 R N -1/2    ≤ e -N (s 2 -1) + e -µ 2 4α * + e -λ 2 4α * . Now, in view of ℓ N (x, ξ N ) = λ 0 [ f0,N (x, ξ N ) -r] + m i=1 λ i fi,N (x, ξ N ) lN (x,ξ N ) +µM 1 N -1/2 ,
and due to the evident relation min x∈X lN (x, ξ N ) ≤ Φ N (r, ξ N ), we get

Prob Φ N (r, ξ N ) < ǫ -µM 1 + Ω[1 + s 2 ] + 2λ M 2 R N -1/2 -µM 1 N -1/2 ≤ Prob min x∈X ℓ N (x, ξ N ) < ǫ -2N -1/2 µM 1 + M 2 R Ω 2 [1 + s 2 ] + λ ≤ e -µ 2 4α * + e -N (s 2 -1) + e -λ 2 4α * .
By [START_REF] Mak | Monte carlo bounding techniques for determining solution quality in stochastic programs[END_REF], we have

ǫ -2 µM 1 + M 2 R Ω 2 [1 + s 2 ] + λ N -1/2 > 0,
and we arrive at

Prob ξ N ∈ Ξ 2 = Prob Φ N (r, ξ N ) ≤ 0 ≤ e -µ 2 4α * + e -N (s 2 -1) + e -λ 2 4α * .
The latter bound combines with (39) to imply the desired relation Prob ξ N ∈ Ξ ≤ e -µ 2 4α * + e -N (s 2 -1) + e -λ 2 4α * + (m + 1)e -µ 2 4α * = β.

Indeed, for ξ ∈ Ξ and x ∈ X, we get

|F (x, ξ) -f (x)| ≤ |α 0 ||(ξ -µ) T x| + α 1 2 |x T (V -ξξ T )x| ≤ |α 0 | ξ -µ ∞ + α 1 2 V -ξξ T ∞ . Since V is positive semidefinite with V ∞ ≤ 1, and ξ ∞ ≤ 1, we have |x T (V -ξξ T )x| ≤ 1, and M 1,exp ≤ M 1,∞ ≤ |α 0 |(1 + µ ∞ ) + α 1 2 ≤ 2|α 0 | + α 1 2 .
Further, let us equip R n with the norm • = • 1 , so that • * = • ∞ , and endow the unit ball of the norm with the distance generating function 3

ω(x) = 1 pγ n i=1 |x i | p , p = 2 for n ≤ 2, 1 + 1/ ln(n) for n ≥ 3, , γ =    1, n ≤ 1 1 2 , n = 2, 1 e ln(n) , n ≥ 3 (42) resulting in Ω = 2 pγ
and R = 1. Now let x ∈ X and ξ ∈ Ξ, and let g be a subgradient of F (x, ξ) with respect to x, and h be a subgradient of f at x. We have

g = α 0 ξ + α 1 ξ(ξ T x), h = α 0 µ + α 1 V x, thus g -h * ≤ |α 0 | ξ -µ ∞ + α 1 V -ξξ ⊤ ∞ ≤ |α 0 |(1 + µ ∞ ) + α 1 . We conclude that M 2 ≤ |α 0 |(1 + µ ∞ ) + α 1 ≤ 2|α 0 | + α 1 .

B.3 Markowitz portfolio optimization

Here the situation is as follows:

• X = {x = [x 1 ; ...;

x n ] ∈ R n : x 1 , ..., x n ≥ 0, n i=1 x i = 1},

• ξ ∼ N (0, Σ) on R n , Σ ≻ 0,

• F (x, ξ) = α 0 ξ T x + α 1 |ξ T x|, with α 1 ≥ 0.

We have f (x) = 2 π α 1 σ x , with σ x = √ x T Σx. In this case one can set Ω and R as in (41), along with Taking into account that for all x ∈ X σ 2 x = x T Σx ≤ Σ ∞ , we arrive at

M 1 =
M 1,exp ≤ ν|α 0 | + √ 2α 1 Σ ∞ = ν|α 0 | + √ 2α 1 σ max . (43)
Let x ∈ X, and let g be a subgradient with respect to x of F (x, ξ), and h be a subgradient of f (x). We have g = α 0 ξ + α 1 ξχ with χ = χ(x, ξ) ∈ [-1, 1], so that

g ∞ ≤ [|α 0 | + α 1 ] ξ ∞ .
Note that ∂ √ x T Σx = x T Σx -1/2 Σx , x = 0, Σ 1/2 u, u 2 ≤ 1 , x = 0.

Therefore, for all h ∈ ∂f (x) one has

h ∞ ≤ α 1 2 π sup x =0 Σx ∞ √ x T Σx = α 1 2 π sup y =0 Σ 1/2 y ∞ y 2 = α 1 2 π Σ 1/2 2,∞ ≤ α 1 σ max 2 π , and
g -h * = g -h ∞ ≤ [|α 0 | + α 1 ] ξ ∞ + α 1 σ max 2 π ,
that is,

L(x, ξ) ≤ [|α 0 | + α 1 ] ξ ∞ + α 1 σ max 2 π .
We conclude that

π[L(x, •)] ≤ [|α 0 | + α 1 ]π[ ξ ∞ ] + α 1 σ max 2 π . ( 44
)
29

We now use the following simple result. 4 Lemma 3. Let ξ be a zero-mean Gaussian random vector in R n , and let σ2 ≥ max 1≤i≤n E{ξ 2 i }. Then for M ≥ σ 2(2 + ln n) E e ξ 2 ∞ /M 2 ≤ e.

Proof. Let η n = max 1≤i≤n |ξ i |. We have the following well-known fact: Note that e -x ≤ 1x/2 for 0 ≤ x ≤ 1. Thus for all n ≥ 1 and t ≤ σ 2(2 + ln n)

-1 , Let x ∈ X and ξ ∈ Ξ, and let g = [g 0 ; g ′ ] be a subgradient of F (x, ξ) with respect to x, and h be a subgradient of f at x. We clearly have

n 2t 2 σ2 1 -2t 2 σ2 ≤
g 0 = α 1 - α 1 ǫ χ 0 , g ′ = α 0 ξ + α 1 ǫ ξχ 1 , h 0 = α 1 - α 1 ǫ χ 2 ,
where χ i ∈

Figure 1 :

 1 Figure1: Quadratic risk minimization: empirical estimation of E{f (x N )} -Opt over 100 realizations as a function of N with approximate solution x N obtained using either SAA or SMD (logarithmic scale). Left plot: simulation results for a problem with α 0 = 0.1, α 1 = 0.9; right plot: results for a problem with α 0 = 0.9, α 1 = 0.1.

Figure 2 :

 2 Figure2: Markowitz portfolio optimization: empirical estimation of E{f (x N ) -Opt} as a function of N (in logarithmic scale). Left plot: simulation results for a problem with α 0 = 0.1, α 1 = 0.9; right plot: results for a problem with α 0 = 0.9, α 1 = 0.1.

Figure 3 :

 3 Figure 3: CVaR minimization: empirical estimation of E{f (x N ) -Opt} as a function of N (in logarithmic scale) on a typical problem instance with α 0 = 0.9, α 1 = 0.1, and ε = 0.1

Figure 4 :

 4 Figure 4: Optimal value Opt of the stochastic program (18) along with lower bound derived from the results of Proposition 5 and "asymptotic" lower bound Opt(ξ N ). The results for ε = 0.5 on the plot (a), for ε = 0.1 on plot (b).

Figure 5 :

 5 Figure 5: Plot (a): optimal value Opt of the stochastic program (20) with constraint r.-h.s. ρ and ρδ, along with corresponding optimal values of the SAA. Plot (b): "true value" of the linear form µ T x(ξ N ) at the SAA solution.

  where δ = 2 sin 2 (θ/2) = 0.0078023... is the elevation of h v,θ . Let us putf (x) = v∈D θ g v,θ (x),and consider the optimization problem Opt = min[f (x) :x ∈ B 2 ]. Since g v,δ is affine on h v,δand vanishes elsewhere on B 2 , and v 2 = 1, we conclude that f is Lipschitz continuous on B 2 with Lipschitz constant 1. Let now

  , where ξ v , v ∈ D θ are i.i.d. Bernoulli random variables with Prob{ξ

2e 2 e 2 - 1 2 π 2 .

 22122 |α 0 | + √ 2α 1 σ max , M 2 = (|α 0 | + α 1 )σ max 2(2 + ln n) + α 1 σ max 2 π ,where σ 2 max = max 1≤i≤n Σ i,i .Indeed, we have ξ T x ∼ N (0, σ 2 x ), we conclude that f (x) = α 1 σ x , whence|F (x, ξ)f (x)| ≤ |α 0 ||ξ T x| + α 1 ||ξ T x| -2/πσ x | = σ x |α 0 ||η x | + α 1 ||η x | -2/π|3 For details, see e.g., derivations of[START_REF] Juditsky | First order methods for nonsmooth convex large-scale optimization, I: general purpose methods[END_REF] Section 5.7] where η x = ξ T x/σ x ∼ N (0, 1). By direct computation we getπ[|η x |] = ν := 2e 2 e 2 -1 = 1.52...Next, setting κ = 2/π we observe that1 √ 2π exp{||s| -κ| 2 /2s 2 /2}ds = κ ∞ 0 exp{[s 2 -2κs + κ 2s 2 ]/2}ds = κ ∞ 0 exp{κ 2 /2 -κs}ds = exp{κ 2 /2} < exp{1}, implying that π[||η x | -2/π|] ≤ √ As a result, π[F (x, •)f (x)] ≤ σ x |α 0 |π[|η x |] + α 1 π[||η x | -2/π|] ≤ σ x ν|α 0 | + √ 2α 1 .

ψ 2 2σ 2 .- 1 ,E e t 2 η 2 n = - ∞ 0 e t 2 r 2 0 2t 2 2 ∞ σ√ 2 ln n r exp - ( 1 -

 2212020221 n (r) := Prob{η n ≥ r} ≤ min 1, ne -r Therefore, for |t| < ( √ 2σ) dψ n (r) = 1 + ∞ re t 2 r 2 ψ n (r)dr ≤ e 2t 2 σ2 ln n + 2nt 2t 2 σ2 )r 2 2σ 2 dr = e 2t 2 σ2 ln n + 2t 2 σ2 1 -2t 2 σ2 e 2t 2 σ2 ln n = n 2t 2 σ2 1 -2t 2 σ2 .

B. 4 4 2 n σ 2 max 1 -2t 2 n σ 2

 42212 the result of the lemma we conclude from (44) that one can take for M 2 the expression(|α 0 | + α 1 )σ max 2(2 + ln n) + α 1 σ max 2 CVaR optimizationConsider the portfolio problem of Section 3.1.3. With some terminology abuse, in what follows, we refer to the special case n = 1 with x 1 ≡ 1 as to the case of n = 0.• X = {x = [x 0 ; x 1 ; ...; x n ] ∈ R n+1 : |x 0 | ≤ 1, x 1 , ..., x n ≥ 0, n i=1 x i = 1},• Ξ be a part of the unit box {ξ = [ξ 1 ; ...; ξ n ] ∈ R n : ξ ∞ ≤ 1}, In fact, in the numerical experiments we have used a slightly better bound M2 which can be defined as follows. Let tn, 0 < tn < σmax be the unique solution of the equationhn(tn) = n 2t hn(•) is monotone on ]0, 1 √2σmax [, so tn can be computed using bisection). The same reasoning as in the proof of Lemma 3 results in the bound in the experiments of Section 3.1.2, for σmax = √ 6 and n ∈ {2, 10, 20, 100}, the values of 1/tn (resp. of its upper bound σmax 2(2 + ln n)) were 4.97, 6.46, 7.05, 8.27 (resp. 5.68, 7.19, 7.74, 8.90).

2 g≤ α 1 ǫ 2 + 4 α 0 + α 1 ǫ 2 while

 222 [0, 1]. Next, for n ≥ 2, |f ([x 0 ; x ′ ])f ([x 0 ; y ′ ])| = |α 0 µ T (x ′y ′ ) + α1 ε E{[ξ T x ′x 0 ] + } -E{[ξ T y ′x 0 ] + } | ≤ α 0 µ ∞ x ′y ′ 1 + α1 ε E{|ξ T (x ′y ′ )|} ≤ (α 0 + α1 ε ) x ′y ′ 1 . It follows that f ([x 0 ; x ′ ]) is Lipschitz continuous in x ′ with constant α 0 + α1 ε with respect to • 1 and we have h ′ ∞ ≤ α 0 + α1 ǫ .As a result, we obtain for n ≥ -h * = |g 0h 0 | 2 + g ′h ′ 2 ∞ gh * ≤ α1 ǫ for n = 1.We conclude that

Table 1 :

 1 Ratios R W of the widths of the confidence intervals as given by Corollary 1 and their lower bounds from Proposition 3.

	1

Table 2 :

 2 Quadratic risk minimization. Estimated coverage probabilities of the asymptotic confidence intervals C a (0.1).

	Sample		Problem size n
	size N	2	10	20	100
	20	0.94 0.68 0.59 0.10
	100	0.95 0.87 0.70 0.46
	10 000	0.94 0.95 0.91 0.85

Table 3 :

 3 with α 1 ≥ 0, so Quadratic risk minimization. Average ratio of the widths of the SAA and asymptotic confidence intervals.

	Sample size N	2	|C SAA (α)| |Ca(α)| , problem size n 10 20 100	200	2	|C SMD (α)| |Ca(α)| , problem size n 10 20 100	200
	100	6.37 9.18 10.18 29.50 47.43 30.57 65.87 78.5 274.63 474.68
	1000	3.27 4.33 4.52 13.92 22.46 15.52 32.56 36.98 134.67 232.32
	10 000	3.15 4.37 4.40 13.44 21.96 15.46 32.40 35.87 131.70 227.56

Table 4 :

 4 Markowitz portfolio optimization. Estimated coverage probabilities of asymptotic confidence intervals.

				Sample	Problem size n
				size N	2	10	20	100
				20		0.95 0.73 0.53 0.05
				100		0.9 0.78 0.48 0.006
				10 000	0.92 0.91 0.92 0.68
				100 000 0.94 0.92 0.92 0.92
	Sample size N	2	|C SAA (α)| |Ca(α)| for problem size n 10 20 100 200	2	|C SMD (α)| |Ca(α)| for problem size n 10 20 100	200
	20	4.42 6.15	6.11	6.27	6.35	40.16 112.38 133.80 183.61 205.66
	100	5.04 9.11 10.79 12.87 13.44 46.41 172.00 244.68 397.01 458.85
	10 000	5.27 12.17 16.29 26.65 30.28 49.15 237.79 386.31 974.32 1088.90

Table 5 :

 5 Markowitz portfolio optimization. Average ratio of the widths of the non-asymptotic and asymptotic confidence intervals.

Table 6 :

 6 CVaR optimization. Estimated coverage probabilities of asymptotic confidence intervals.

		Sample	ε = 0.1, problem size n	ε = 0.9, problem size n
		size N		3	11	21	101	3	11	21	101
		100		0.96 0.74 0.85 0.78 0.96 0.95 0.95 0.78
		1000		0.95 0.88 0.86 0.67 0.95 0.92 0.84 0.84
		10 000		0.92 0.93 0.91 0.94 0.92 0.95 0.96 0.96
	Sample	ε = 0.9, problem size n			ε = 0.1, problem size n
	size N	3	11	21	101		201	3	11	21	101	201
	100	3.09 3.69 7.33 14.25 13.79 293.47 27.61 9.14 14.32 14.44
	1000	3.25 3.67 8.63 35.04 36.72 294.16 27.04 8.72 34.43 37.42
	10 000	3.22 3.68 8.61 32.08 34.00 293.92 26.91 8.66 31.70 34.18

Table 7 :

 7 CVaR optimization. Average ratio |C SAA (α)| |Ca(α)| of the widths of the non-asymptotic and asymptotic confidence intervals.

  Proposition 6. Let (χ t ) t=1,2,... , χ t ∈ E, be a martingale-difference such that for some σ > 0 it holds E e χt 2

	2 4α * . The corresponding bound for λ > 2 √ is given by exactly the same reasoning as above in which (23) is substituted with the inequality α * N
	E e θdt d t-1 ≤ E e	3θ 2 8 +	2d 2 t 3	d t-1 ≤ e	3θ 2 8 + 2 3 ≤ e	3θ 2 4
	when θ > 1/ √ α * .

* /σ 2 χ 1 , ..., χ t-1 ≤ e a.s., t = 1, 2, ...

It is worth to mention that in our experiments the upper bound Up SAA was too conservative and was systematically "outperformed" by the upper bound Up ′ .

Note that asymptotic estimation σN of the noise variance often degenerates, to avoid related division by zero problems we only kept the realisations where asymptotic confidence intervals cover the true optimal value.

Research of the first author was supported by an FGV grant, CNPq grant 307287/2013-0, FAPERJ grants E-26/110.313/2014, and E-26/201.599/2014. The second author was supported by the CNRS-Mastodons project GARGANTUA, and the LabEx PERSYVAL-Lab (ANR-11-LABX-0025). Research of the third author was supported by NSF grants CMMI-1232623, CMMI-1262063, CCF-1415498.

B Evaluating approximation parameters

For the sake of completeness we provide here the straightforward derivations of the parameter estimates used to build the bounds in the numerical section.

B.1 Notation

Let P be a Borel probability distribution on R k and let Ξ be the support of P . Consider the space C of all Borel functions g(•) Given a convex compact set X ⊂ R n , a norm • on R n , and a continuously differentiable distance-generating function ω(•) for the unit ball B • which is compatible with this norm, let R be the radius of the smallest • -ball containing X. Given a Borel function F (x, ξ) : R n ×Ξ → R which is convex in x ∈ R n and P -summable in ξ for every x, let

Note that adding to F (x, ξ) a differentiable function g of x: F (x, ξ) → F (x, ξ) + g(x) does not affect the quantities M 1,∞ , M 1,exp , and M 2 .

Our goal is to compute upper bounds on M 1,∞ , M 1,exp , and M 2 in the different settings of Section 3.1.1.

B.2 Quadratic risk minimization

In this case

The parameters M 1 , M 2 , R and Ω of construction can be set according to:

R and Ω of construction can be set according to:

Indeed, denoting ξ x = ξ T x and µ i = E{ξ i }, we have

We conclude that

In what follows, for a vector from R n+1 , say, z = [z 0 ; z 1 ; ...; z n ], we set z


V Dubodelov

V Fikssen

M Slazhniev

M Goryuk

Iu Skorobagatko

E Seredenko

O Yashchenko

Modernization of casting magnetodynamic equipment

During last 10 years in the PTIMA NASU there is made the all-round modernization of magnetodynamic equipment for manufacturing of cast production from aluminium alloys, cast iron and steel. Such modernization had included both widening of functionality of magnetodynamic installations and development of concomitant MHD-technologies for preparation and pouring of high-quality alloys in the foundry, metallurgy and machine-building.

Introduction

Now the requirements to quality of cast production become tougher constantly. It is appeared in necessity to provide: -the high cleanness of alloys and wares from them from gases, non-metallics; -absence of casting defects; -maximal approaching of casting (ingot) to geometry of final ware; -advance of quality of alloys and castings (rise of physical, mechanical, technological, operating and special properties); -providing of automation; -rise of productivity; -improvement of ecology. Developed in the PTIMA NASU magnetodynamic devices for preparation and pouring of alloys are used widely for manufacturing of castings at foundry shops, metallurgical plants and machine-building enterprises. In the last 10 years, there is realized modernization of such equipment.

Results

As it is well known, magnetodynamic devices (installations & mixers-batchers) combines in one aggregate both induction channel furnace and electromagnetic pump [START_REF] Polishchuk | Magnetodynamic pumps for liquid metals, Kyiv, Naukova dumka[END_REF][START_REF] Dubodelov | International Symposium on Electromagnetic Processing of Materials EPM-1994[END_REF]. In comparison with similar electrotechnological equipments, it provides independent control of thermal state of melt due to regulated induction heating and guided electromagnetic stirring. At that, there are realized the processing of liquid ferrous and non-ferrous alloys, and also their controlled electromagnetic pouring into sand molds, chill molds (including die castings machines), crystallizers, pans. Electric current in melt in the magnetodynamic device is inducted due to Ohm's law [START_REF] Polishchuk | Magnetodynamic pumps for liquid metals, Kyiv, Naukova dumka[END_REF]:

             В Е j   , А/m 2 , (1)
where  jelectric current density, А/m 2 ; electric conduction, S;  Eelectric field intensity, V/m;  velocity of melt, m/sec;  Bmagnetic induction, T. Melt heating in the magnetodynamic equipments is provided accordingly to Joule law at carrying of electric current inducted in the melt (in the channels) [START_REF] Polishchuk | Magnetodynamic pumps for liquid metals, Kyiv, Naukova dumka[END_REF]:

             В Е j q  (or as scalar equation     R I Q 2 ), J, (2)
where q и Qheat generation in the melt, J; Ielectric current, А; Relectrical resistance, Ohm; time, sec. It is usual for any induction channel device. But, the principle feature of magnetodynamic devices is additional electromagnet [START_REF] Polishchuk | Magnetodynamic pumps for liquid metals, Kyiv, Naukova dumka[END_REF]. It creates the internal alternating magnetic field on the part of the channel (so called working area). At superposition of this field with electric current in melt, there is generated volume electromagnetic force [START_REF] Polishchuk | Magnetodynamic pumps for liquid metals, Kyiv, Naukova dumka[END_REF]:

            V V d B j F Re (or as scalar equation  cos V BIL F  ), N/m 3 , (3)
where Vvolume of working area, m 3 ; Llength of working area, m; phase-shift angle between electric current and magnetic field.

This force provides the melt moving. At that, modes (directions and intensities) of such moving determine by electric parameters of inductor and electromagnet. Practically, it is both circulation between crucible and channel (in fact stirring) and electromagnetic pouring of melt at set thermal and hydrodynamic terms. Generated in the magnetodynamic devices electromagnetic pressure is determined as [START_REF] Polishchuk | Magnetodynamic pumps for liquid metals, Kyiv, Naukova dumka[END_REF]:

α cos            L B j р
(or as scalar equation

 cos S BIL p  ), Pa, (4)
where Ssquare of working area, m 2 . One of main feature of magnetodynamic aggregates is pouring of melt directly from heating zoneinduction channel.

It allows realizing the developed in the MHD Department of PTIMA NASU technology of differentiated heating of liquid metal [START_REF] Dubodelov | International Congress on Electromagnetic Processing of Materials EPM-1997[END_REF][START_REF] Dubodelov | 5 th International PAMIR Conference on Fundamental and Applied MHD[END_REF]. It consists in holding of melt in crucible of the magnetodynamic device at low temperature and overheating up to pouring temperature only poured dose of melt during its moving through induction channel. In general, average overheating of melt between channel and crucible of the magnetodynamic aggregate makes [START_REF] Dubodelov | International Congress on Electromagnetic Processing of Materials EPM-1997[END_REF][START_REF] Dubodelov | 5 th International PAMIR Conference on Fundamental and Applied MHD[END_REF]: mass flow rate of liquid metal at its circulation between channel and crucible, kg/sec. At pouring, summary overheating of melt in the magnetodynamic aggregate makes:

circ ind c therm elec stat aver k Т Q c P .         , С, (5)
pour aver stat aver Т Т Т . .       , С, (6)
where pour aver Т .



average overheating of poured dose directly at its poring from the device, С. It is:

dose pour c ind c therm elec pour aver т М k Т         Q с Р .   , С, (7)
                dose pour c circ ind c therm elec т М k Т Q Q 1 с Р   , С (8)
For optimum consumption of power resources at dosage pouring the ratio of parameters should be the next:

    0 Р c c Q Q '                 cycle ind therm elec add pour pour pour pause circ t M t t М      , ( 9
)
where Мweight of metal in the aggregate, kg; ), sec.

For continuous processes the ratio (9) should be changed. So, in case of continuous adding of molten metal into the magnetodynamic aggregate without stopping of dosage pouring of melt from the device, the ratio (9) is the following: mass flow rate of melt adding continuously into the aggregate, kg/sec. At continuous pouring of metal with periodic adding of melt into the magnetodynamic device, the ratio (9) changes to:

                               0 c Q Р c Q Q , 0 Q Q ' cycle
    0 c Q Р '                t M t t M add pour cast pour add cast cast ind therm elec      , ( 11
)
where cast  the summary time, during which there is only pouring of melt doses from the device in the receiving device, sec;

add cast  
the summary time, during which there is synchronous pouring of metal from the magnetodynamic aggregate and adding of new portion of melt into the device, sec. For fully continuous processes (continuous adding of melt into the aggregate and continuous pouring of melt from the device), the ratio (9) transforms into the following:

  0 c Q Q Р '          t t add pour pour ind therm elec   (12)
Using ratios ( 9)-( 12), it is possible to optimize material & power consumptions and to provide high quality of production at casting processes with application of magnetodynamic equipment for preparation and pouring of alloys. There is developed multifunction casting MHD-complex for manufacturing of high-quality aluminium castings. The complex is able to work effectively in different being casting technologies. The main device of the complex is the magnetodynamic mixer-batcher (Fig. 1) that provides advanced technical parameters (induction heating, electromagnetic pressure, and mass flow rate at electromagnetic stirring & pouring of aluminium melt).

Fig. 1: Magnetodynamic mixer-batcher for preparation and pouring of aluminium alloys

Mixer-batcher operates at supply of three-phase AC by frequency 50-60 Hz and voltage 220/380 V. The complex provides the substantial improvement of structure and increasing of properties of aluminium alloys and castings due to: -high-speed dissolution of alloying additions and modifiers in melt, homogenizations of chemical composition and temperatures of liquid aluminium alloys at controlled electromagnetic stirring; -thermal & forced processing of melt [START_REF] Dubodelov | [END_REF], including possible combination of electromagnetic influence and MHD-effects with other high-energy actions, modulation of electromagnetic force [START_REF] Dubodelov | 3 rd International Symposium on Electromagnetic Processing of Materials EPM-2000[END_REF] and creation of controlled pinch-effect in the induction channel and working area of magnetodynamic mixer-batcher [START_REF] Dubodelov | 5 th International Symposium on Electromagnetic Processing of Materials EPM-2006[END_REF]; -realization of high efficiency refining of alloys (by argon blowingreduction of hydrogen content to 0,10-0,05 cm 3 /100 g of metal at the simultaneous economy to 50% argon and reducing on 30% time of treatment in comparison with existing technologies, by filtration with passing of electric current in meltremoval to 80% non-metallics) [START_REF] Lee | 12 th International Conference on Aluminium Alloys (ICAA)[END_REF]; -decreasing dosage error at electromagnetic pouring of metal no more than 1-2% from mass of dose [START_REF] Dubodelov | [END_REF]; -reduction of minimum mass flow rate of melt at pouring to 0.3 kg/sec and increasing of maximum mass flow rate up to 10 kg/sec; -realization of casting technological processes under low controlled electromagnetic pressure, including using of lost foam models and dispersed non-solidifying gating system [START_REF] Dubodelov | 6 th International Conference on Electromagnetic Processing of Materials EPM-2009[END_REF][START_REF] Fixsen | [END_REF]. Application of developed casting complex and magnetodynamic mixer-batcher provides manufacturing of high-quality aluminium alloys (hypoeutectic & hypereutectic silumins, high-strength Al -Cu alloys) and castings with improved structure and increased mechanical properties. In particular, thermal & forced processing of liquid alloys A356 & A390 in the MHD-mixer-batcher creates the conditions for break-up of microinhomogeneities (caused by negative metallurgical heredity) in the melt. It provides increasing to 2-4 times of elongation of indicated alloys [START_REF] Dubodelov | [END_REF]. Further progress of magnetodynamic equipment for aluminium alloys consists in providing of higher electromagnetic pressure for new casting technologies [START_REF] Dubodelov | 9 th International PAMIR Conference on Fundamental and Applied MHD[END_REF]. There is realized modernization of magnetodynamic devices for overheating and pouring of cast iron and steel (Fig. 2). Fig. 2: Magnetodynamic mixer-batcher for overheating and pouring of cast iron and steel So, it is developed the analog system based on using thyristor regulator of electric current for operation control of magnetodynamic mixer-batcher for cast iron. Comparing to similar well-known control systems for induction channel furnace, using such system for magnetodynamic devices has some features. Usually thyristor distorts the sinusoidal current which is important for generating of substantial electromagnetic pressure for different modes of stirring and pouring of melt by magnetodynamic mixer-batcher. This task was solved successfully, and such aggregate with new control system was applied in industry at manufacturing of castings from cast iron. It provides the economy to 20% of energy in comparison to using of control system on the base of autotransformers. In comparison of conventional ladle pouring, using of electromagnetic pouring of cast iron and steel by MHD-mixerbatcher at production of castings and ingots allowed to stabilize the thermal and hydrodynamic terms of mould filling and further forming of casting, to decrease the spoilage, to provide the improvement of cast structure of and increase of basic mechanical properties of alloys and castings on 10-15% [START_REF] Dubodelov | [END_REF]. Guided electromagnetic stirring of melt in the magnetodynamic mixer-batcher provides melt homogenization on temperature and chemical composition, necessary thermal and hydrodynamic terms for dissolution and distributing in melt volume of alloying and modifying additions [START_REF] Dubodelov | 5 th International Symposium of Electromagnetic Processing of Materials EPM-2006[END_REF]. Lately there is successful application of such aggregate as magnetodynamic tundish at continuous casting of steel [START_REF] Dubodelov | 5 th International Symposium of Electromagnetic Processing of Materials EPM-2006[END_REF].

Conclusion

Modernization of magnetodynamic devices for foundry and metallurgy has provided to improve the quality of manufactured cast production, to increase the technical and economic indices of process, to create the necessary prerequisites for further fundamental and applied researches and technological progress.

  and thermal efficiency of magnetodynamic device; c kpart of power released in channel in comparison with all power released in melt volume (for magnetodynamic devices с k = 0,7-0,8); ind Р inductor power, W; сheating capacity of melt, J/(kgС); circ Q

М

  where c mass of melt in the induction channel of the aggregate, kg; pour Q mass flow rate of melt at pouring, kg/sec; dose т mass of poured dose, kg. So, equation (6) transforms to:

  pause between pouring of two doses of metal, sec; ttemperature of metal in the device, С; pour Q mass flow of metal at pouring, kg/sec; metal portion, added into the aggregate, kg; ' t value of an necessary overheating of melt in the magnetodynamic aggregate (difference between the set pouring temperature of metal and temperature of metal, added into the device: