# A Reliability Theory of Compromise Decisions for Large-Scale Stochastic
Programs

Shuotao Diao***Department of Industrial Engineering and Management Sciences,
Northwestern University, Evanston IL, 60208, USA, Suvrajeet Sen††footnotemark:
†††Epstein Department of Industrial and Systems Engineering, University of
Southern California, Los Angeles CA, 90089, USA
<EMAIL_ADDRESS><EMAIL_ADDRESS>
(First Version: )

###### Abstract

Stochastic programming models can lead to very large-scale optimization
problems for which it may be impossible to enumerate all possible scenarios.
In such cases, one adopts a sampling-based solution methodology in which case
the reliability of the resulting decisions may be suspect. For such instances,
it is advisable to adopt methodologies that promote variance reduction. One
such approach goes under a framework known as “compromise decision”, which
requires multiple replications of the solution procedure. This paper studies
the reliability of stochastic programming solutions resulting from the
“compromise decision” process. This process is characterized by minimizing an
aggregation of objective function approximations across replications,
presumably conducted in parallel. We refer to the post-parallel-processing
problem as the problem of “compromise decision”. We quantify the reliability
of compromise decisions by estimating the expectation and variance of the
“pessimistic distance” of sampled instances from the set of true optimal
decisions. Such pessimistic distance is defined as an estimate of the largest
possible distance of the solution of the sampled instance from the “true”
optimal solution set. The Rademacher average of instances is used to bound the
sample complexity of the compromise decision.

Keywords: Stochastic Programming, Sample Average Approximation, Rademacher
Average

##  1 Motivation

Artificial Intelligence, Machine Learning, and Data Science (AMD) have become
major sources of applications of stochastic optimization. In general, the
class of AMD models are often based on the idea of Empirical Risk Minimization
(ERM) in which vast amounts of data can be characterized via a class of
functions (e.g., affine, convex etc.) which can be used for predictive
purposes. Concomitantly, we are also witnessing the growth of decision and
design (DD) optimization for new applications in sustainable energy,
environment, and even health-care decisions using Sample Average Approximation
(SAA) [23]. These two classes of “applications” (AMD and DD) tend to have
slightly different algorithmic requirements: AMD problems tend to seek
functions which perform well across a range of plausible data using ERM, while
DD seeks a finite dimensional vector which is predicted to perform well across
a sampled collection of plausible scenarios using SAA. Statistically speaking,
ERM and SAA are cousins of each other, drawing from the same “well” of sample
complexity theory developed within the statistical learning (SL) literature.
However, there are real-world implications associated with models of
predictive and prescriptive analytics: in case of the former, small errors in
predictions are often “easily forgiven,” (e.g., errors in predicting
precipitation) whereas, errors in DD can often represent loss of coordination
among multi-variate choices (e.g., different product lines), and can lead to
operational havoc. Because coordination across multiple facets may contribute
to much of the value-proposition of DD, it is important to have plans which
dovetail well, even in the presence of significant uncertainty. For these
reasons, choices which are recommended in the DD setting often call for
greater reliability, especially because uncertainty has the potential to up-
end the entire plan. To accommodate such coordination, our prior work has put
forward the concept of “compromise decisions” for various versions of
stochastic programming (SP) structures (e.g., Stochastic LPs [35], Stochastic
Multi-Stage LPs [41], and Stochastic MIPs [42])). While the specifics of
compromise decisions for each class is designed to address the specific
structure of the model, they are all intended to enhance the reliability of
decisions. However unlike the above papers, which are computationally
motivated, this paper is envisioned as one providing mathematical/statistical
foundations for the concept of Compromise Decisions.

There are several challenges which present barriers to overcoming the goals
outlined above: a) Traditional SAA (as well as ERM) focuses on sample
complexity based on probability estimates of approximation quality, b) it is
not obvious how multiple sampling-based runs should be combined to provide one
decision for the purposes of implementation, c) it is also burdensome to
characterize the worst-case scenario (in distribution) of the estimated
solution generated by a given SP algorithm. One recommendation (due to
Nesterov) is to simply average outputs resulting from parallel runs (e.g.,
using multiple Stochastic Gradient Descent (SGD) runs). The challenge here is
that it is unclear whether the variability associated with decisions are to be
considered in some way. In this paper, we plan to provide sample complexity of
DD associated with convex SP models. We expect that future papers will present
more comprehensive theory to accommodate integer as well as other non-convex
settings.

Importance sampling is one popular approach to reduce the variance associated
with objective function estimates (of values as well as gradient/subgradient
estimates) when using Monte Carlo sampling [8]. It has been widely used to
reduce variance in gradient estimates for portfolio [44, 19] and credit risk
optimization [13]. Kozmík and Morton [24] also propose an importance sampling
methodology to reduce the variance of the upper bound estimate of optimal cost
from the Stochastic Dual Dynamic Programming (SDDP) algorithms in a risk-
averse setting. Carson and Maria [7] summarized that the key to the success of
importance sampling lies in the appropriate change of the probability measure
used for rare event simulation.

Additionally, other popular variance reduction methods include linear control
random variables method ([36]), in which a correlated random variable with
mean zero is added to the objective function, as well as using common random
numbers for variance reduction approach ([15], [22]). For a review of modern
variance reduction techniques in stochastic optimization, we refer the readers
to a survey by Homem-de-Mello and Bayraksan [17].
Other than the above-mentioned variance reduction techniques, Pasupathy and
Song [29] propose an adaptive sequential SAA framework where the inner loop
stopping criterion depends on the optimality gap and pointwise variance
estimates and the outer loop utilizes previously estimated solution as a warm
start.
When memory and computational time are no longer the bottleneck in computation
(e.g. [43]), performing several replications of sampling procedures, perhaps
in parallel, becomes an alternative to improve the objective function estimate
and/or optimal solution estimate. Sen and Liu [35] propose a closed-loop
methodology based on a composite function which aggregates the sum of
piecewise linear objective function approximations (from multiple independent
runs), together with a regularizing term which measures deviation from a
sample average of decisions. The above approximation is what [35] refers to as
the compromise problem, and the optimum solution of that problem is referred
to as the compromise decision. The computational results reported in the
aforementioned paper illustrates the power of aggregated approximations for
stochastic linear programming problems, and their computational results
demonstrate the variance reduction due to the compromise decision approach.

At approximately the same time as the publication of [35], the International
Conference on SP (ICSP-13 in 2016) was held in Buzios, Brazil where several SP
luminaries made the case for recommending general-purpose methodologies which
could support low variance decisions for SP problems. During that session it
was noted that while SP methodology was strongly supported by SAA-based
theory, most SP algorithns were not designed to provide computational support
for establishing the reliability of decisions proposed by SP software.

Motivated by the “disconnect” between SP theory and computations, we aim to
present a theory which is based on a small set of principles that can be used
to explain the computational success reported in the above-mentioned papers.
Indeed, we focus on studying the finite-sample complexity of the Compromise
Decision approach to solve the following generic stochastic program

$\min_{x\in X}\
f(x)\triangleq\mathbb{E}_{\tilde{\xi}}[F(x,\tilde{\xi})]\text{},$ (1)

where $\tilde{\xi}:\Omega\mapsto\Xi\subset\mathbb{R}^{d}$ is a random variable
with distribution $\mu$ defined on a probability space
$(\Omega,\Sigma_{\Omega},\mathbb{P})$, $X\subset\mathbb{R}^{p}$ is the
feasible region of $x$, and $F:X\times\Xi\mapsto\mathbb{R}$ is a
Carathéodorian function (i.e., continuous in $X$ and measurable for almost
every $\xi\in\Xi$).
Given $m$ ($m\geq 2$) replications, we let $\xi_{i}^{n}$,
$\hat{f}_{n}(x;\xi_{i}^{n})$ and $\hat{x}(\xi_{i}^{n})$ denote the sampled
data sets (each of size $n$), objective function approximations (based on
sampling-based estimates), and decision estimate in the $i^{\text{th}}$
replication of Monte Carlo sampling to recommend an approximate solution to
the problem in (1), respectively. The compromise decision problem for convex
SP, based on $m$ replications is formulated as follows:

$\min_{x\in X}\
\frac{1}{m}\sum_{i=1}^{m}\hat{f}_{n}(x;\xi_{i}^{n})+\frac{\rho}{2}\left\|x-\frac{1}{m}\sum_{i=1}^{m}\hat{x}_{n}(\xi_{i}^{n})\right\|^{2}.$
(2)

The addition of the quadratic regularizer to the objective function has been
widely used in SP algorithms such as the proximal point method [32], proximal
bundle method [21], mirror descent method [27], regularized SD [16],
regularized SDDP [1, 14], and more recently, SDLP [12]. Furthermore, the use
of the decision-based regularizer in (2) can be interpreted as one way of
countering overfitting. SP models in our setting often involve multi-
dimensional random variables and the sampling distribution $\hat{\mu}_{N}$
often involves $N$ which is so large, as to be untenable for constrained
optimization. In this sense, the size of $n$ which we use in SP is relatively
small as to be similar to the case of overfitting in statistics .

Algorithm 1 Compromise Decision Approach

Initialization: Set sample size $n\in\mathbb{Z}_{+}$, replication number
$m\in\mathbb{Z}_{+}$, $\rho\in(0,+\infty)$, and an Algorithm $\Upsilon$ for
the replication step.

Replication Step: For $i=1,2,\ldots,m$, use Algorithm $\Upsilon$ compute
estimated decision, $\hat{x}(\xi^{n}_{i})$, and function estimation,
$\hat{f}_{n}(x;\xi^{n}_{i})$, of the $i^{\text{th}}$ replication.

Aggregation Step: Aggregate function estimates
$\frac{1}{m}\sum_{i=1}^{m}\hat{f}_{n}(x;\xi_{i}^{n})$ with certain
augmentation. Aggregate estimated decisions as
$\frac{1}{m}\sum_{i=1}^{m}\hat{x}_{n}(\xi_{i}^{n})$. Obtain the
$\epsilon$-optimal solution of the compromise decision problem in (2).

The compromise decision problem consists of an estimated aggregation of
sampled value function approximations, and a penalty based on a distance to
the average decision estimate. It can also be interpreted as performing one
step of the proximal point method for solving
$\frac{1}{m}\sum_{i=1}^{m}\hat{f}_{n}(x;\xi_{i}^{n})$ given that the initial
estimate is $\frac{1}{m}\sum_{i=1}^{m}\hat{x}_{n}(\xi_{i}^{n})$. Let
$\bar{x}_{N}(\xi^{N})=\frac{1}{m}\sum_{i=1}^{m}\hat{x}_{(}\xi^{n}_{i})$ and
let $x^{c}_{N}(\xi^{N})$ denote the optimal solution of (2). It is obvious
that if $\bar{x}_{N}(\xi^{N})$ and $x^{c}_{N}(\xi^{N})$ agree, then both are
optimal to $\min\limits_{x\in X}\
\frac{1}{m}\sum_{i=1}^{m}\hat{f}_{n}(x;\xi_{i}^{n})$. This observation has
been transformed into a stopping rule for compromise SD ([35]). In short, the
Compromise Decision approach consists of two steps: a replication step and an
aggregation step. We summarize the Compromise Decision approach in Algorithm
1.
Motivated by the computational evidence of successful use of the Compromise
Decision problem [35, 41, 42], this paper aims to expound on a mathematical
foundation for those successes. In particular, we shall address the following
questions which will support a mathematical (as opposed to computational)
basis for Compromise Decisions:

  * 1.

How should one quantify the reliability of the estimated decisions of
stochastic programs?

  * 2.

What is the reliability of a compromise decision when a particular algorithm
is used in each replication?

  * 3.

More specifically, what is the reliability of compromise decisions with SD
algorithm involved in each replication of a stochastic QP?

The above agenda is not only novel, but it provides a theoretical
justification for reliable decision-making using SP. It is important to
recognize that in the absence of such a theory, sampling-based computational
algorithms for SP (including traditional SDDP [30]) are likely to lead to both
sub-optimality and/or lower reliability (i.e., greater variability).
Computational evidence of such risks, especially for multi-stage SP, are
presented in [41].

This paper is organized as follows. In section 2, we review Rademacher
complexity and its use in bounding the sample complexity of point estimates of
the objective function and its variance. In section 3, we present both exact
and inexact compromise decision problem formulation and its quantitative
reliability. In section 4, we discuss the sample complexity analysis of the
compromise decision when a cutting-plane-type algorithm is used to solve each
replication of the approximation problem. Finally, we provide the theoretical
evidence of the success of using SD algorithms for the compromise decision
problem in section 5.

###  1.1 Notations

We let $\tilde{\xi}:\Omega\mapsto\Xi\subset\mathbb{R}^{d}$ denote a random
vector defined on a probability space $(\Omega,\Sigma_{\Omega},\mathbb{P})$
and let $\xi$ denote one realization of $\tilde{\xi}$. Let
$\tilde{\xi}_{1},\tilde{\xi}_{2},\ldots,\tilde{\xi}_{n}$ denote independent
and identically distributed (i.i.d.) copies of $\tilde{\xi}$. For
$i=1,2,\ldots,n$, we let $\xi_{i}$ denote the realization of $\tilde{\xi}_{i}$
and let $\xi^{n}\triangleq\\{\xi_{1},\xi_{2},\ldots,\xi_{n}\\}$ denote the set
of realizations of $n$ i.i.d. copies of $\tilde{\xi}$. Let
$X\subset\mathbb{R}^{p}$ be a nonempty compact set of decisions, and let
$F:X\times\Xi\mapsto\mathbb{R}$ be a Carathéodorain function. We let
$\Pr\\{\cdot\\}$ denote the probability of an event, and let $\|\cdot\|$
denote the Euclidean norm.
Without further specification, we let $n$ denote the sample size of each
replication and let $m$ denote the number of replications. We let
$\xi^{n}_{i}$ denote the sample set with size $n$ in the $i^{\text{th}}$
replication. In particular, we let
$\xi^{n}_{i}=\\{\xi_{(i-1)n+j}\\}_{j=1}^{n}$. We let $N=mn$ denote the total
sample size and let $\xi^{N}=\cup_{i=1}^{m}\xi^{n}_{i}$ denote the mega-sample
set. Without loss of generality, we consider the case in which the sample size
for each replication is the same, although it is straightforward to extend the
analysis to the case of heterogeneous sample sizes among the replications.
As for the notations in the Rademacher complexity, we let
$\tilde{\sigma}_{1},\tilde{\sigma}_{2},\ldots,\tilde{\sigma}_{n}$ be i.i.d.
random variables with $\tilde{\sigma}_{i}$ for $i=1,2,\ldots,n$ being equally
likely to be $1$ or $-1$. That is,
$\Pr(\tilde{\sigma}=1)=\Pr(\tilde{\sigma}=-1)=\frac{1}{2}$. Furthermore, we
require that $\tilde{\sigma}_{i}$ are independent of $\tilde{\xi}$ for all
$i=1,2,\ldots,n$.
To study $\epsilon$-optimality of a solution, we shall define the following
metric to measure the pessimistic distance between two sets (see [10, 11, 29]
for similar uses).

######  Definition 1 (Pessimistic Distance).

Let $A$ and $B$ be two sets from an Euclidean space. The pessimistic distance
of $A$ to $B$ is defined as follows:

$\Delta(A,B)\triangleq\sup_{a\in A}\inf_{b\in B}~{}\|a-b\|.$ (3)

An interpretation of $\Delta(A,B)$ is that it is the largest distance from a
point of set $A$ to set $B$. For instance, if $A$ is the set of possible
estimated solutions and $B$ is the set of optimal solutions. Then
$\Delta(A,B)$ is the farthest distance from the estimated solution to the
optimal solution set.
The following theorem describes the Lipschitzian behavior of the
$\epsilon$-optimal solution set in terms of the metric defined in (3).

######  Theorem 1.1.

[10] Assume that $X$ is a nonempty compact convex set and
$f:X\mapsto\mathbb{R}$ is a lower semicontinuous convex function. Let the
following definitions hold: $D_{X}=\max_{x,x^{\prime}\in X}\|x-x^{\prime}\|$;
$\theta^{*}=\min_{x\in X}f(x)$; $\epsilon^{\prime}>\epsilon>0$,
$X_{\epsilon}=\\{x\in X:f(x)\leq\theta^{*}+\epsilon\\}$, and
$X_{\epsilon^{\prime}}=\\{x\in X:f(x)\leq\theta^{*}+\epsilon^{\prime}\\}$.
Then the following holds:

$\Delta(X_{\epsilon^{\prime}},X_{\epsilon})\leq\frac{\epsilon^{\prime}-\epsilon}{\epsilon}D_{X}.$

###### Proof.

See [10, Theorem 3.11]. ∎

The results of Theorem 1.1 relate the perturbation of the objective function
(e.g., estimation error from sampling) to the $\epsilon$-solution set. It will
be one of the major tools for studying the reliability of the compromise
decisions. When $\epsilon^{\prime}=\epsilon>0$,
$\Delta(X_{\epsilon^{\prime}},X_{\epsilon})=0$ and
$\frac{\epsilon^{\prime}-\epsilon}{\epsilon}D_{X}=0$. Hence, the inequality in
Theorem 1.1 still holds when $\epsilon^{\prime}=\epsilon>0$.
Finally, we summarize key notations and their use in computation and/or
analysis in Appendix A.

###  1.2 Contributions

The contributions of this paper are two-fold: (1) We propose a unifying
framework to compute compromise decisions by aggregating information from
multiple replications of SP runs; (2) We provide a quantitative way to measure
the reliability of the compromise decision.
Here, we summarize our contribution to the reliability of the compromise
decisions when a class of SP methods are involved in solving each replication
in Table 1. We say that if one compromise decision has better reliability than
another compromise decision, then the former one has a faster convergence rate
in both expectation and variance of the pessimistic distance (in Definition 1)
to the ($\epsilon$-)optimal solution set. Thus we use a 2-tuple to describe
the reliability of the compromise decision. In particular, the first element
(of the 2-tuple) will denote the expectation of the pessimistic distance,
whereas, the second element of the 2-tuple measures the variance of the
pessimistic distance to the ($\epsilon$-)optimal solution set. Due to the
sublinear convergence rate of SD for SQQP problems, we observe that the
compromise decision using SD (in section 5) has a higher reliability than the
one using SAA (in section 3) or cutting-plane-type methods (in section 4). It
is also expected that deterministic cutting-plane methods (such as Benders
Decomposition or L-shaped method) and SAA have the same reliability because a
deterministic method can only deliver what is permissible within the SAA
setup.

Method in the replication step | Problem type | Reliability
---|---|---
SAA | Convex | $\left(O(\frac{1}{n^{\lambda}}),O(\frac{1}{mn^{\lambda}}+\frac{1}{n^{2\lambda}}))\right),\ \lambda\in(0,\frac{1}{2})$
Cutting-plane-type methods | Convex | Same as above
SD | Two-stage SQQP | $\left(O(\frac{1}{n}),O(\frac{1}{mn}+\frac{1}{n^{2}})\right)$
Table 1: Reliability of Compromise Decisions

##  2 Background on Sample Complexity: Point Estimates and Rademacher Average

In order to set the stage for the goals outlined earlier, we begin by
reviewing the notion of Rademacher average and its use in bounding a sample
average approximation of the objective function and a sample variance of the
random cost function.

As mentioned by [3], “Rademacher complexity is commonly used to describe the
data-dependent complexity of a function class”. One key advantage of
(empirical) Rademacher average (or complexity) is that it can be measured from
a finite sample set (see [3] for i.i.d. cases, and [26] for non-i.i.d. cases).
As a result, it can be used to estimate the finite-sample error of a function
class. Rademacher average has been widely used in neural networks ([2]),
support vector machine ([39]), and decision trees ([18]).

The common finite-sample approximation of (1) is known as the sample average
approximation (SAA), and is written as follows.

$\min_{x\in
X}f_{n}(x;\xi^{n})\triangleq\frac{1}{n}\sum_{i=1}^{n}F(x,\xi_{i}).$ (4)

Since we will study multiple replications of sampling, we write the sample set
explicitly in the argument of the $f_{n}(x;\cdot)$ to distinguish different
sample sets. A similar notational style will apply to sample variance,
estimated solutions and compromise decisions.

The variance of the random cost function, $F(x,\tilde{\xi})$, parameterized by
the decision $x$, is defined as

$\text{Var}[F(x,\tilde{\xi})]\triangleq\mathbb{E}_{\tilde{\xi}}\left[\left(F(x,\tilde{\xi})-f(x)\right)^{2}\right].$

The unbiased estimate of the variance of $F(x,\tilde{\xi})$ is formulated as

$s^{2}_{n}(x;\xi^{n})\triangleq\frac{1}{n-1}\sum_{i=1}^{n}\left[F(x,\xi_{i})-\hat{f}_{n}(x)\right]^{2}.$
(5)

We let $Y$ denote a convex compact set in $\mathbb{R}$, and define a compound
function $H:X\times Y\times\Xi\mapsto\mathbb{R}$ with
$H(x,y,\xi)=(F(x,\xi)-y)^{2}$. As suggested in [11], the variance of
$F(x,\tilde{\xi})$ can be written as a compound function as follows:

$\text{Var}[F(x,\tilde{\xi})]=\mathbb{E}_{\tilde{\xi}}\left[H(x,\mathbb{E}_{\tilde{\xi}}[F(x,\tilde{\xi})],\tilde{\xi})\right]=\mathbb{E}_{\tilde{\xi}}\left[(F(x,\tilde{\xi})-\mathbb{E}_{\tilde{\xi}}[F(x,\tilde{\xi})])^{2}\right].$

Furthermore, the sample variance, $s_{n}^{2}(x)$, can be rewritten as the sum
of compound functions below.

$s_{n}^{2}(x;\xi^{n})=\frac{1}{n-1}\sum_{i=1}^{n}H(x,\frac{1}{n}F(x,\xi_{i}),\xi_{i}).$
(6)

Throughout the paper, we make the following assumptions:

######  Assumption 2.1.

Let $X\subset\mathbb{R}^{p}$ be a nonempty compact set of decisions, and let
$F:X\times\Xi\mapsto\mathbb{R}$ be a Carathéodorain function.

  1. 1.

$X\subset\mathbb{R}^{p}$ is a nonempty compact convex set contained in a cube
whose edge-length is $D$.

  2. 2.

$F(x,\xi)$ is Hölder continuous in $x$ with constant $L_{F}$ and
$\gamma\in(0,1]$ for all $\xi\in\Xi$. That is, $|F(x,\xi)-F(y,\xi)|\leq
L_{F}\|x-y\|^{\gamma}$ for all $x,y\in X$ and $\xi\in\Xi$.

  3. 3.

There exists $M_{F}\in(0,\infty)$ such that $\sup_{x\in
X,\xi\in\Xi}|F(x,\xi)|<M_{F}$. Let $Y\subset\mathbb{R}$ be
$Y\triangleq[-M_{F},M_{F}]$.

We note that the assumption of boundedness of the feasible region and the
objective function is common in the SP literature [38, 27, 11]. Also, the
Hölder continuity condition of the objective function is a generalization of
its Lipschitzian counterpart. The introduction of the soundness parameters and
Hölder continuity-related parameters are later used to bound the Rademacher
average of the random cost function and its variance.
Next we introduce the definition of the Rademacher average of a finite set of
vectors.

######  Definition 2 ([6]).

Let $\tilde{\sigma}_{1},\tilde{\sigma}_{2},\ldots,\tilde{\sigma}_{n}$ be
i.i.d. random variables with $\tilde{\sigma}_{i}$ for $i=1,2,\ldots,n$ being
equally likely to be $1$ or $-1$ (i.e.,
$\Pr(\tilde{\sigma}_{i}=1)=\Pr(\tilde{\sigma}_{i}=-1)=\frac{1}{2}$ for
$i\in\\{1,\ldots,n\\}$). Let $A\subset\mathbb{R}^{n}$ be a bounded set of
vectors $a=(a_{1},\ldots,a_{n})$, the Rademacher average associated with $A$
is defined below:

$R_{n}(A)=\mathbb{E}_{\tilde{\sigma}}\left[\sup_{a\in
A}\frac{1}{n}\left|\sum_{i=1}^{n}\tilde{\sigma}_{i}a_{i}\right|\right].$ (7)

The following lemma yields an upper bound of the Rademacher average of a
finite set. Note that it is a modification of [6, Theorem 3] which requires a
slight re-orientation.

######  Lemma 2.1.

If $A=\\{a^{(1)},\ldots,a^{(N)}\\}\subset\mathbb{R}^{n}$ is a finite set, then

$R_{n}(A)\leq\max_{j=1,\ldots,N}\|a^{(j)}\|\frac{\sqrt{2\log{{2}N}}}{n}$ (8)

###### Proof.

See the Appendix B.1. ∎

Lemma 2.1 is fundamental to the study of the upper bound of the Rademacher
average of a function class. The Rademacher average of a function class is
defined as follows.

######  Definition 3 ([11]).

Let $\tilde{\sigma}_{1},\tilde{\sigma}_{2},\ldots,\tilde{\sigma}_{n}$ be
i.i.d. random variables with $\tilde{\sigma}_{i}$ for $i=1,2,\ldots,n$ being
equally likely to be $1$ or $-1$. For a set of points
$(\xi_{1},\ldots,\xi_{n})=\xi^{n}$ in $\Xi$ and a sequence of functions
$\\{F(\cdot,\xi_{i}):X\mapsto\mathbb{R}\\}$, the Rademacher average of a
function class is defined as:

$R_{n}(F,\xi^{n})\triangleq\mathbb{E}_{\tilde{\sigma}}\left[\sup_{x\in
X}\left|\frac{1}{n}\sum_{i=1}^{n}\tilde{\sigma}_{i}F(x,\xi_{i})\right|\right].$
(9)

Furthermore, the Rademacher average of a family of functions
$\\{F(\cdot,\xi):X\mapsto\mathbb{R}\\}_{\xi\in\Xi}$ is defined as:

$R_{n}(F,\Xi)\triangleq\sup_{\xi_{1}\in\Xi,\ldots,\xi_{n}\in\Xi}R_{n}(F,\xi^{n}).$
(10)

The following lemma provides upper bounds of Rademacher average of a sequence
of functions studied by [11], although we modify the affected constant
resulting from Lemma 2.1. Note that the lemma below assumes that the feasible
region is discrete and it is free of the Assumption 2.1. Moreover, it should
be regarded as a building block for further results.

######  Lemma 2.2 ([11]).

Let the set $X\subset\mathbb{R}^{p}$ be discrete and contain a finite number
of elements $|X|\leq m^{p}$, and assume $\sup_{x\in X}|F(x,\xi_{i})|\leq
M(\xi_{i})\leq\max_{1\leq i\leq n}M(\xi_{i})=M_{n}(\xi^{n})$, then the
following holds:

$R_{n}(F,\xi^{n})\leq M_{n}(\xi^{n})\sqrt{2\log 2|X|/n}\leq
M_{n}(\xi^{n})\sqrt{2p(\log{2}m)/n}$ (11)

With the help of Lemma 2.2, we can derive the upper bound of Rademacher
average of the random cost function, $F(x,\xi)$, in the following lemma.

######  Lemma 2.3 ([11]).

Suppose that Assumption 2.1 holds. Then

$R_{n}(F,\xi^{n})\leq\left(L_{F}D^{\gamma}p^{\frac{\gamma}{2}}+M_{F}\sqrt{2({\log
2}+\frac{p}{2\gamma}\log n)}\right)/\sqrt{n},$ (12)

where $L_{F}$ and $\gamma$ are the constants in the Hölder continuity of
$F(\cdot,\xi)$, $n$ is the sample size, $p$ is the dimension of the decision,
$x$, and $D$ is the edge length of the cube that contains the feasible region,
$X$. Furthermore, for $\lambda\in(0,\frac{1}{2})$, we have

$R_{n}(F,\xi^{n})\leq\frac{N_{F}}{n^{\lambda}}$ (13)

where $N_{F}=L_{F}D^{\gamma}p^{\frac{\gamma}{2}}+{M_{F}\sqrt{2(\log
2)}}+\frac{M_{F}p^{1/2}}{\sqrt{\gamma(1-2\lambda)e}}$.

###### Proof.

See the Appendix B.2 ∎

Since the constant $N_{F}$ in Lemma 2.3 stays the same for any $\xi\in\Xi$, we
conclude that

$R_{n}(F,\Xi)=\sup_{\xi_{1}\in\Xi,\ldots,\xi_{n}\in\Xi}R_{n}(F,\xi^{n})\leq\frac{N_{F}}{n^{\lambda}}.$

To derive the upper bound of Rademacher average of the compound function,
$H(x,y,\xi)=(F(x,\xi)-y)^{2}$, we need to show that $H(x,y,\xi)$ is Lipschtiz
continuous in $(x,z)$ given that $F(x,\xi)$ is Hölder continuous in $x$ and
$F(x,\xi)$ is uniformly bounded.

######  Lemma 2.4.

Suppose that Assumption 2.1 holds. Then $H(x,y,\xi)\triangleq(F(x,\xi)-y)^{2}$
is Lipchitz continuous in $(x,y)$ with Lipschitz constant
$4M_{F}\sqrt{L_{F}^{2}+1}$ (i.e., $|H(x_{1},y_{1},\xi)-H(x_{2},y_{2},\xi)|\leq
4M_{F}\sqrt{L_{F}^{2}+1}\|(x_{1},y_{1})-(x_{2},y_{2})\|,\ \forall\
(x_{1},y_{1}),\ (x_{2},y_{2})\in X\times Y$). Furthermore, $H(x,y,\xi)$ is
Lipschitz continuous in $y$ with Lipschitz constant $4M_{F}$ and $H(x,y,\xi)$
is uniformly bounded by $4M_{F}^{2}$.

###### Proof.

See Appendix B.3. ∎

The upper bound of the Rademacher average of the compound function
$H(x,y,\xi)$ follows from Lemmas 2.3 and 2.4, which is summarized below.

######  Lemma 2.5.

Let $\tilde{\sigma}_{1},\tilde{\sigma}_{2},\ldots,\tilde{\sigma}_{n}$ be
i.i.d. random variables with $\tilde{\sigma}_{i}$ for $i=1,2,\ldots,n$ being
equally likely to be $1$ or $-1$. Let the Rademacher average of the set of
sequences of $H$ be

$R_{n}(H,\xi^{n})=\mathbb{E}_{\tilde{\sigma}}\sup_{x\in X,y\in
Y}\left|\frac{1}{n}\sum_{i=1}^{n}\tilde{\sigma}_{i}H(x,y,\xi_{i})\right|.$

Suppose that Assumption 2.1 holds. Let $L_{H}=4M_{F}\sqrt{L_{F}^{2}+1}$ and
$M_{H}=4M_{F}^{2}$. For any $\lambda\in(0,\frac{1}{2})$, we have the following
result:

$R_{n}(H,\xi^{n})\leq\frac{N_{H}}{n^{\lambda}},$ (14)

where $N_{H}=L_{H}D(p+1)^{\frac{1}{2}}+M_{H}\sqrt{2(\log
2)}+\frac{M_{F}(p+1)^{1/2}}{\sqrt{(1-2\lambda)e}}$.

###### Proof.

This is a direct result of combining Lemmas 2.3 and 2.4. ∎

In the following, we will use the Rademacher average to study the sampling
error of the objective function estimates. Given a sample set $\xi^{n}$, we
define the supremum of sampling error of the objective function estimate
below.

######  Definition 4.

Let $\xi^{n}=\\{\xi_{1},\xi_{2},\ldots,\xi_{n}\\}$ denote the realizations of
$n$ i.i.d. copies of $\tilde{\xi}$. The supremum of sampling error of the
objective function estimate is defined as follows:

$\delta_{n}^{f}(\xi^{n})=\sup_{x\in
X}\left|\frac{1}{n}\sum_{i=1}^{n}F(x,\xi_{i})-\mathbb{E}_{\tilde{\xi}}[F(x,\tilde{\xi})]\right|.$
(15)

In Appendix C, we explain how to use the Rademcaher average of a function
class, shadow random variables (i.e.,
$\xi_{1}^{\prime},\ldots,\xi_{n}^{\prime}$ so that
$\xi_{1}^{\prime},\ldots,\xi_{n}^{\prime},\xi_{1},\ldots,\xi_{n}$ are i.i.d.),
and symmetric argument to bound $\mathbb{E}[\delta_{n}^{f}(\tilde{\xi}^{n})]$.
For more details about the symmetric argument, please see [6].
We summarize the bound of $\delta_{n}^{f}(\xi^{n})$ derived by Ermoliev and
Norkin [11] using Rademcaher average of a function class in the following
theorem.

######  Theorem 2.6.

Suppose that Assumption 2.1 holds. Let $N_{F}$ be a constant defined in Lemma
2.3. For any $\lambda\in(0,\frac{1}{2})$, then the following holds:

  1. 1.

$\mathbb{E}[\delta_{n}^{f}(\tilde{\xi}^{n})]\leq
2R_{n}(F,\Xi)\leq\frac{2N_{F}}{n^{\lambda}},$

  2. 2.

$\Pr\left\\{n^{\lambda}\delta_{n}^{f}(\tilde{\xi}^{n})\geq
2N_{F}+t\right\\}\leq\exp\left(-\frac{t^{2}}{2M^{2}_{F}}\right).$

###### Proof.

See [11, Corollary 3.2]. ∎

By Assumption 2.1, we observe that
$|\frac{1}{n}\sum_{i=1}^{n}F(x,\xi_{i})-\mathbb{E}[F(x,\tilde{\xi})]|\leq
2M_{F}$, which implies that $\delta_{n}^{f}(\xi^{n})\leq 2M_{F}$. One direct
consequence of Theorem 2.6 is that

$\displaystyle\text{Var}[\delta_{n}^{f}(\tilde{\xi}^{n})]$
$\displaystyle=\mathbb{E}[(\delta_{n}^{f}(\tilde{\xi}^{n}))^{2}]-\mathbb{E}[\delta_{n}^{f}(\tilde{\xi}^{n})]^{2}$
(16)
$\displaystyle\leq\mathbb{E}[(\delta_{n}^{f}(\tilde{\xi}^{n}))^{2}]\leq\mathbb{E}[2M_{F}\delta_{n}^{f}(\xi^{n})]\leq\frac{4M_{F}N_{F}}{n^{\lambda}}.$

We derive the sample complexity of the sample variance in the next lemma.

######  Lemma 2.7.

Denote

$\delta_{n}^{h}(\xi^{n})=\sup_{x\in
X}\left|\frac{1}{n}\sum_{i=1}^{n}H\left(x,\frac{1}{n}\sum_{j=1}^{n}F(x,\xi_{j}),\xi_{i}\right)-\mathbb{E}_{\tilde{\xi}}\left[H\left(x,\mathbb{E}_{\tilde{\xi}}[F(x,\tilde{\xi})],\tilde{\xi}\right)\right]\right|$

and

$\hat{\delta}_{n}(\xi^{n})=\sup_{x\in X,y\in
Y}\left|\frac{1}{n}\sum_{i=1}^{n}H(x,y,\xi_{i})-\mathbb{E}_{\tilde{\xi}}\left[H(x,y,\tilde{\xi})\right]\right|.$

Suppose that Assumption 2.1 holds. Then the following holds:

  1. 1.

$\delta^{h}_{n}(\xi^{n})\leq
4M_{F}\delta^{f}_{n}(\xi^{n})+\hat{\delta}_{n}(\xi^{n})$

  2. 2.

$\displaystyle\mathbb{E}[\delta^{h}_{n}(\tilde{\xi}^{n})]$ $\displaystyle\leq
8M_{F}R_{n}(F,\Xi)+2R_{n}(H,\Xi)$
$\displaystyle\leq\frac{8M_{F}N_{H}+2N_{F}}{n^{\lambda}},$

where $\lambda\in(0,\frac{1}{2})$, $N_{F}$ is a constant defined in Lemma 2.3,
and $N_{H}$ is a constant defined in Lemma 2.5.

###### Proof.

See Appendix B.4. ∎

With a slight abuse of the notation, we let
$\sigma(x)=\text{Var}[F(x,\tilde{\xi})]$. We observe that

$\displaystyle\left|s_{n}^{2}(x)-\sigma^{2}(x)\right|$
$\displaystyle=\left|\frac{n}{n-1}\frac{1}{n}\sum_{i=1}^{n}H(x,\frac{1}{n}\sum_{i=1}^{n}F(x,\xi_{k}),\xi_{i})-\sigma^{2}(x)\right|$
(17)
$\displaystyle\leq\left|\frac{1}{n}\sum_{i=1}^{n}H(x,\frac{1}{n}\sum_{i=1}^{n}F(x,\xi_{k}),\xi_{i})-\sigma^{2}(x)\right|$
$\displaystyle\
+\frac{1}{n-1}\left|\frac{1}{n}\sum_{i=1}^{n}H(x,\frac{1}{n}\sum_{i=1}^{n}F(x,\xi_{k}),\xi_{i})\right|.$

By Lemmas 2.4 and 2.7, it follows from (17) that

$\sup_{x\in X}\left|s_{n}^{2}(x,\tilde{\xi}^{n})-\sigma^{2}(x)\right|\leq
4M_{F}\delta^{f}_{n}(\tilde{\xi}^{n})+\hat{\delta}_{n}(\tilde{\xi}^{n})+\frac{4M_{F}^{2}}{n-1},$
(18)

and hence,

$\displaystyle\mathbb{E}\left[\sup_{x\in
X}\left|s_{n}^{2}(x,\tilde{\xi}^{n})-\sigma^{2}(x)\right|\right]$
$\displaystyle\leq\frac{8M_{F}N_{H}+2N_{F}}{n^{\lambda}}+\frac{4M_{F}^{2}}{n-1}.$

Let $Z_{1-\frac{\alpha}{2}}$ be the Z score of two-sided $1-\alpha$ confidence
interval (i.e., $Z_{1-\frac{\alpha}{2}}=\Phi^{-1}(1-\frac{\alpha}{2})$, where
$\Phi^{-1}(\cdot)$ is the inverse of the cumulative distribution function of
standard normal distribution). Let $s^{2}_{n}(x;\xi^{n}_{i})$ be the sample
variance of $F(x,\xi)$ in the $i^{\text{th}}$ replication. With the bound in
(18), we could derive the sample complexity of the margin of error with $m$
replications as follows (see Appendix D for detailed derivation):

$\displaystyle\mathbb{E}\left[\frac{1}{m}\sqrt{\frac{\sum_{i=1}^{m}s^{2}_{n}(x;\tilde{\xi}^{n}_{i})}{n}}Z_{1-\frac{\alpha}{2}}\right]$
$\displaystyle\leq\sqrt{\frac{\sigma^{2}(x)}{mn}+\frac{8M_{F}N_{H}+2N_{F}}{mn^{(1+\lambda)}}+\frac{4M_{F}^{2}}{mn(n-1)}}Z_{1-\frac{\alpha}{2}}$
(19) $\displaystyle\leq O((mn)^{-\frac{1}{2}}).$

The upper bound given in (19) not only agrees with the common sense, which is
$\left(O\left((mn)^{-\frac{1}{2}}\right)\right)$, but also indicates that the
bias term
($\frac{8M_{F}N_{H}+2N_{F}}{mn^{(1+\lambda)}}+\frac{4M_{F}^{2}}{mn(n-1)}$)
diminishes faster than the unbiased term $\frac{\sigma^{2}(x)}{mn}$.

##  3 Sample Complexity of Compromise Decisions

In this section, we shall formulate an exact compromise decision problem and
its inxeact counterpart. We aim to study the quantitative reliability of the
associated compromise decisions. We make one additional convexity assumption
of the random cost function, $F(x,\xi)$, and one additional assumption on the
sampling scheme, below:

######  Assumption 3.1.

$F(x,\xi)$ is convex in $x\in X$ for every $\xi\in\Xi$.

######  Assumption 3.2.

Given integer replication number $m\in\mathbb{Z}_{+}$ and integer sample size
per replication $n\in\mathbb{Z}_{+}$. Let $N\triangleq mn$ denote the total
sample size. Assume that
$\tilde{\xi}_{1},\tilde{\xi}_{2},\ldots,\tilde{\xi}_{N}$ are i.i.d. random
variables which follow the distribution of $\tilde{\xi}$.
Furthermore, Let
$\tilde{\xi}^{N}\triangleq\\{\tilde{\xi}_{1},\tilde{\xi}_{2},\ldots,\tilde{\xi}_{N}\\}$
denote the collection of all samples. For $i\in\\{1,2,\ldots,m\\}$, let
$\tilde{\xi}^{n}_{i}\triangleq\\{\tilde{\xi}_{n(i-1)+1},\tilde{\xi}_{n(i-1)+2},\ldots,\tilde{\xi}_{ni}\\}$
denote the collection of samples used in the $i^{\text{th}}$ replication.

We start with a basic formulation where we can solve each replication of the
SAA problem to optimality and use it to give a brief introduction to the
compromise decision methodology. The compromise decision methodology consists
of two key steps, which are replication step and aggregation step (see
Algorithm 1). In the replication step, we build a SAA function for each
replication,

$f_{n}(x;\xi^{n}_{i})=\frac{1}{n}\sum_{j=1}^{n}F(x,\xi_{(i-1)n+j}),\
i=1,2,\ldots,m.$ (20)

Then we solve the SAA problem to obtain the minimizer of
$f_{n}(x;\xi^{n}_{i})$, which is denoted by $x_{n}(\xi^{n}_{i})$. The problem
below illustrates the replication step.

$x_{n}(\xi^{n}_{i})\in\arg\min_{x\in X}f_{n}(x;\xi^{n}_{i}),\ i=1,2,\ldots,m.$

In the aggregation step, we find the compromise decision that minimizes the
aggregation of the information from SAA functions and their corresponding
minimizers. Given a regularizer $\rho\in(0,\infty)$, this aggregation problem
(which we refer to as exact compromise decision problem) can be formulated as
follows:

$\min_{x\in
X}\frac{1}{m}\sum_{i=1}^{m}f_{n}(x;\xi^{n}_{i})+\frac{\rho}{2}\left\|x-\frac{1}{m}\sum_{i=1}^{m}x_{n}(\xi^{n}_{i})\right\|^{2}.$
(21)

We let $\tilde{x}_{N,\rho}(\xi^{N})$ denote the optimal solution of the exact
compromise decision problem in (21). Let $\theta_{N,\rho}(\xi^{N})$ and
$\theta^{*}$ denote the optimal values of exact compromise decision problem in
(21) and true problem in (1), respectively. We shall show that
$\mathbb{E}[|\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}|]\leq\frac{6m-4}{mn^{\lambda}}N_{F}$
and
$\text{Var}\left[|\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}|\right]\leq\frac{36M_{F}N_{F}}{mn^{\lambda}}+\frac{36N_{F}^{2}}{n^{2\lambda}}$,
for $\lambda\in(0,\frac{1}{2})$ and a problem-specific constant $N_{F}$
defined in Lemma 2.3.

In the second part of this section, we will focus on a more general case in
which only inexact optimal solutions from $m$ replications are accessible to
us. Let $X_{n,\epsilon}(\xi^{n}_{i})$ denote an $\epsilon$-optimal solution
set of the $i^{\text{th}}$ replication of the SAA problem:

$X_{n,\epsilon}(\xi^{n}_{i})=\bigg{\\{}x\in
X:f_{n}(x;\xi^{n}_{i})\leq\text{minimum}\Big{\\{}f_{n}(x;\xi^{n}_{i})|x\in
X\Big{\\}}+\epsilon\bigg{\\}}$ (22)

We let $x_{n,\epsilon}(\xi^{n}_{i})$ denote one element of
$X_{n,\epsilon}(\xi^{n}_{i})$ (i.e., $x_{n,\epsilon}(\xi^{n}_{i})\in
X_{n,\epsilon}(\xi^{n}_{i})$). As a result, the inexact compromise decision
problem which allows a collection of $\epsilon$-optimal solutions from all the
$m$ replications is written below:

$\min_{x\in
X}\frac{1}{m}\sum_{i=1}^{m}f_{n}(x;\xi^{n}_{i})+\frac{\rho}{2}\left\|x-\frac{1}{m}\sum_{i=1}^{m}x_{n,\epsilon}(\xi^{n}_{i})\right\|^{2}.$
(23)

Let $\hat{X}_{N,\rho,\epsilon}$ and $X^{*}_{\epsilon}$ denote
$\epsilon$-optimal solution sets of inexact compromise decision problem in
(23) and true problem in (1), respectively. We shall measure the reliability
of the compromise decisions to (23) by showing that

  1. 1.

$\mathbb{E}[\Delta(\hat{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X^{*}_{\epsilon})]\leq\frac{D_{X}N_{F}}{\epsilon}\frac{8m-4}{mn^{\lambda}}+2\sqrt{\epsilon/\rho}$.

  2. 2.

$\Pr\left\\{\frac{\epsilon
n^{\lambda}}{2D_{X}}\Delta(\hat{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})\geq
C+t\right\\}\leq
m\exp\left\\{-\frac{m^{2}t^{2}}{2M^{2}_{F}(2m-1)^{2}}\right\\}$ for $\rho=n$.

  3. 3.

$\text{Var}[\Delta(\hat{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})]\leq\frac{64D_{X}^{2}M_{F}N_{F}}{m\epsilon^{2}n^{\lambda}}+(\frac{8D_{X}N_{F}}{\epsilon
n^{\lambda}}+2\sqrt{\epsilon/\rho})^{2}.$

###  3.1 Sample Complexity of the Exact Compromise Decision Problem

In this subsection, we focus on deriving the sample complexity of the optimal
cost of the exact compromise decision problem (21). Recall that we let $f(x)$
denote the expectation of the random cost function (i.e.,
$f(x)=\mathbb{E}_{\tilde{\xi}}[F(x,\tilde{\xi})]$ ) and let $\theta^{*}$
denote the optimal cost of the true problem (i.e., $\theta^{*}=\min_{x\in
X}f(x)$).
We start with introducing several notations in the replication step. We let
$\theta_{n}(\xi^{n}_{i})$ denote the optimal cost of the $i^{\text{th}}$ SAA
problem:

$\theta_{n}(\xi^{n}_{i})=\min_{x\in X}f_{n}(x;\xi^{n}_{i}),\ i=1,2,\ldots,m.$
(24)

In the last section, we have defined the estimation error of objective
function estimate in each replication as follows:

$\displaystyle\delta^{f}_{n}(\xi^{n}_{i})=\sup_{x\in
X}|f_{n}(x;\xi^{n}_{i})-f(x)|,\ i=1,2,\ldots,m.$ (25)

With a symmetric argument (see [6, 11] or (106) in Appendix C), we have shown
that $\mathbb{E}[\delta^{f}_{n}(\tilde{\xi}^{n}_{i})]\leq
2R_{n}(F,\Xi)\leq\frac{2N_{F}}{n^{\lambda}}$ for any
$\lambda\in(0,\frac{1}{2})$.
Next, we provide a relation for deriving the upper bound of the variance of
interest. Given two non-negative random variables $X,Y$ so that $0\leq X\leq
Y\ a.s.$, we have the following relationship between $\text{Var}[X]$ and
$\text{Var}[Y]$:

$\text{Var}[X]=\mathbb{E}[X^{2}]-\left(\mathbb{E}[X]\right)^{2}\leq\mathbb{E}[X^{2}]\leq\mathbb{E}[Y^{2}]=\text{Var}[Y]+\left(\mathbb{E}[Y]\right)^{2},$
(26)

######  Theorem 3.1.

Suppose that Assumptions 2.1, 3.1, and 3.2 hold. Let $N_{F}$ be a constant
defined in Lemma 2.3. Then the following hold:

  1. 1.

$\mathbb{E}\left[|\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}|\right]\leq\frac{6m-4}{m}R_{n}(F,\Xi)\leq\frac{6m-4}{mn^{\lambda}}N_{F},$

  2. 2.

$\text{Var}\left[|\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}|\right]\leq\frac{36M_{F}N_{F}}{mn^{\lambda}}+\frac{36N_{F}^{2}}{n^{2\lambda}},$

where $R_{n}(F,\Xi)$ is the Rademacher average associated with $F$ and sample
size $n$ in Definition 3, and $\lambda\in(0,\frac{1}{2})$.

###### Proof.

To begin with, we give an overview of the proof strategy. The proof consists
of three steps. In step 1, we aim to use the supremum of the sampling error
defined in (15) to bound $|\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}|$. The
idea is based on the convexity of the objective function in Assumption 3.1 and
triangular inequality. By convexity, we observe that
$f_{n}\left(\frac{1}{m}\sum_{j=1}^{m}x_{n}(\tilde{\xi}^{n}_{j});\tilde{\xi}^{n}_{i}\right)\leq\frac{1}{m}\sum_{j=1}^{m}f_{n}\left(x_{n}(\tilde{\xi}^{n}_{j});\tilde{\xi}^{n}_{i}\right)$.
Note that $|f_{n}\left(x;\tilde{\xi}^{n}_{i}\right)-f(x)|$ is bounded above by
$\delta^{f}_{n}(\tilde{\xi}^{n}_{i})$ and
$|f_{n}\left(x;\tilde{\xi}^{n}_{j}\right)-f(x)|$ is bounded above by
$\delta^{f}_{n}(\tilde{\xi}^{n}_{j})$. Then by triangular inequality,
$|f_{n}\left(x;\tilde{\xi}^{n}_{i}\right)-f_{n}\left(x;\tilde{\xi}^{n}_{j}\right)|$
is bounded above by
$\delta^{f}_{n}(\tilde{\xi}^{n}_{i})+\delta^{f}_{n}(\tilde{\xi}^{n}_{j})$.
In step 2, we utilize Theorem 2.6 to derive the upper bound of the supremum of
the sampling error in expectation. In step 3, we use the variance relation in
(26) and the upper bound of the variance of supremum of the sampling error in
(16) to get the upper bound of
$\text{Var}\left[|\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}|\right]$.

(Step 1: Upper Bound of $|\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}|$). We
aim to derive the upper bound and lower bound of
$\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}$ separately. By optimality of the
problem (21), we have

$\displaystyle\theta_{N,\rho}(\tilde{\xi}^{N})$
$\displaystyle=\frac{1}{m}\sum_{i=1}^{m}f_{n}\left(\tilde{x}_{N,\rho}(\tilde{\xi}^{N});\tilde{\xi}^{n}_{i}\right)+\frac{\rho}{2}\left\|\tilde{x}_{N,\rho}(\tilde{\xi}^{N})-\frac{1}{m}\sum_{i=1}^{m}x_{n}(\tilde{\xi}^{n}_{i})\right\|^{2}$
(27)
$\displaystyle\leq\frac{1}{m}\sum_{i=1}^{m}f_{n}\left(\frac{1}{m}\sum_{j=1}^{m}x_{n}(\tilde{\xi}^{n}_{j});\tilde{\xi}^{n}_{i}\right)$
$\displaystyle\leq\frac{1}{m^{2}}\sum_{i=1}^{m}\sum_{j=1}^{m}f_{n}\left(x_{n}(\tilde{\xi}^{n}_{j});\tilde{\xi}^{n}_{i}\right)\quad\text{by
convexity of }f_{n}(\cdot;\tilde{\xi}^{n}_{i}).$

On the other hand, for $i,j\in\\{1,2,\ldots,m\\}$ and $i\neq j$, we have

$\displaystyle
f_{n}\left(x_{n}(\tilde{\xi}^{n}_{j});\tilde{\xi}^{n}_{i}\right)$
$\displaystyle=f_{n}\left(x_{n}(\tilde{\xi}^{n}_{j});\tilde{\xi}^{n}_{j}\right)+f_{n}\left(x_{n}(\tilde{\xi}^{n}_{j});\tilde{\xi}^{n}_{i}\right)-f_{n}\left(x_{n}(\tilde{\xi}^{n}_{j});\tilde{\xi}^{n}_{j}\right)$
(28)
$\displaystyle\leq\theta_{n}(\tilde{\xi}^{n}_{j})+\left|f_{n}\left(x_{n}(\tilde{\xi}^{n}_{j});\tilde{\xi}^{n}_{i}\right)-f_{n}\left(x_{n}(\tilde{\xi}^{n}_{j});\tilde{\xi}^{n}_{j}\right)\right|$
$\displaystyle\leq\theta_{n}(\tilde{\xi}^{n}_{j})+\left|f_{n}\left(x_{n}(\tilde{\xi}^{n}_{j});\tilde{\xi}^{n}_{i}\right)-f\left(x_{n}(\tilde{\xi}^{n}_{j})\right)\right|$
$\displaystyle\quad+\left|f_{n}\left(x_{n}(\tilde{\xi}^{n}_{j});\tilde{\xi}^{n}_{j}\right)-f\left(x_{n}(\tilde{\xi}^{n}_{j})\right)\right|$
$\displaystyle\leq\theta_{n}(\tilde{\xi}^{n}_{j})+\delta^{f}_{n}(\tilde{\xi}^{n}_{i})+\delta^{f}_{n}(\tilde{\xi}^{n}_{j}),\quad\text{
by (\ref{eq:estimate error})}.$

Let $x^{*}\in\arg\min_{x\in X}f(x)$, then we have

$\displaystyle\theta_{n}(\tilde{\xi}^{n}_{i})-\theta^{*}$ $\displaystyle\leq
f_{n}(x^{*};\tilde{\xi}^{n}_{i})-\theta^{*}\quad\quad\text{by the definition
of }\theta_{n}(\tilde{\xi}^{n}_{i})\text{ in (\ref{eq:optimal cost of one
replication of SAA})}$ (29)
$\displaystyle=f_{n}(x^{*};\tilde{\xi}^{n}_{i})-f(x^{*})$
$\displaystyle\leq\sup_{x\in
X}|f_{n}(x;\tilde{\xi}^{n}_{i})-f(x)|=\delta^{f}_{n}(\tilde{\xi}^{n}_{i}).$

Furthermore, we have

$\displaystyle\theta_{n}(\tilde{\xi}^{n}_{i})-\theta^{*}$ $\displaystyle\geq
f_{n}\left(x_{n}(\tilde{\xi}^{n}_{i});\tilde{\xi}^{n}_{i}\right)-f\left(x_{n}(\tilde{\xi}^{n}_{i})\right)$
$\displaystyle\text{ by
}f\left(x_{n}(\tilde{\xi}^{n}_{i})\right)\geq\theta^{*}$ (30)
$\displaystyle\geq-\sup_{x\in
X}\left|f_{n}(x;\tilde{\xi}^{n}_{i})-f(x)\right|=-\delta^{f}_{n}(\tilde{\xi}^{n}_{i}).$

The combination of (27) and (28) implies that

$\theta_{N,\rho}(\tilde{\xi}^{N})\leq\frac{1}{m}\sum_{i=1}^{m}\theta_{n}(\tilde{\xi}^{n}_{i})+\frac{1}{m^{2}}\sum_{\begin{subarray}{c}i,j=1,\\\
i\neq
j\end{subarray}}^{m}\left(\delta^{f}_{n}(\tilde{\xi}^{n}_{i})+\delta^{f}_{n}(\tilde{\xi}^{n}_{j})\right).$
(31)

By subtracting $\theta^{*}$ from both sides of (31), we have the upper bound
of $\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}$ shown below:

$\displaystyle\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}$
$\displaystyle\leq\frac{1}{m}\sum_{i=1}^{m}\left(\theta_{n}(\tilde{\xi}^{n}_{i})-\theta^{*}\right)+\frac{1}{m^{2}}\sum_{\begin{subarray}{c}i,j=1,\\\
i\neq
j\end{subarray}}^{m}\left(\delta^{f}_{n}(\tilde{\xi}^{n}_{i})+\delta^{f}_{n}(\tilde{\xi}^{n}_{j})\right)$
(32)
$\displaystyle\leq\frac{1}{m}\sum_{i=1}^{m}\delta^{f}_{n}(\tilde{\xi}^{n}_{i})+\frac{1}{m^{2}}\sum_{\begin{subarray}{c}i,j=1,\\\
i\neq
j\end{subarray}}^{m}\left(\delta^{f}_{n}(\tilde{\xi}^{n}_{i})+\delta^{f}_{n}(\tilde{\xi}^{n}_{j})\right).$

As for the lower bound of $\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}$, we
observe that

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}f_{n}(\tilde{x}_{N,\rho}(\tilde{\xi}^{N});\tilde{\xi}^{n}_{i})+\frac{\rho}{2}\left\|\tilde{x}_{N,\rho}(\tilde{\xi}^{N})-\frac{1}{m}\sum_{i=1}^{m}x_{n}(\tilde{\xi}^{n}_{i})\right\|^{2}$
$\displaystyle\geq\frac{1}{m}\sum_{i=1}^{m}f_{n}\left(\tilde{x}_{N,\rho}(\tilde{\xi}^{N});\tilde{\xi}^{n}_{i}\right)$
$\displaystyle\geq\frac{1}{m}\sum_{i=1}^{m}\theta_{n}(\tilde{\xi}^{n}_{i}).$

Hence, this implies that

$\displaystyle\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}$
$\displaystyle\geq\frac{1}{m}\sum_{i=1}^{m}\left(\theta_{n}(\tilde{\xi}^{n}_{i})-\theta^{*}\right)$
(33)
$\displaystyle\geq-\frac{1}{m}\sum_{i=1}^{m}\delta^{f}_{n}(\tilde{\xi}^{n}_{i})$

Combining (32) and (33) we derive the upper bound of
$\left|\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}\right|$ below:

$\left|\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}\right|\leq\frac{1}{m}\sum_{i=1}^{m}\delta_{n}(\tilde{\xi}^{n}_{i})+\frac{1}{m^{2}}\sum_{\begin{subarray}{c}i,j=1,\\\
i\neq
j\end{subarray}}^{m}\left(\delta^{f}_{n}(\tilde{\xi}^{n}_{i})+\delta^{f}_{n}(\tilde{\xi}^{n}_{j})\right).$
(34)

(Step 2: Upper bound of
$\mathbb{E}\left[\left|\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}\right|\right]$).
Taking expectation on both sides of (34) and applying Theorem 2.6, we get

$\displaystyle\mathbb{E}\left[\left|\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}\right|\right]$
$\displaystyle\leq 2R_{n}(F,\Xi)+\frac{4m(m-1)}{m^{2}}R_{n}(F,\Xi)$
$\displaystyle=\frac{6m-4}{mn^{\lambda}}N_{F}.$

(Step 3: Upper bound of
$\text{Var}\left[\left|\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}\right|\right]$).
Next, we will derive the upper bound of the variance of
$|\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}|$. According to (34), we have

$\left|\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}\right|\leq\sum_{i=1}^{m}\left(\frac{1}{m}+\frac{2(m-1)}{m^{2}}\right)\delta^{f}_{n}(\tilde{\xi}^{n}_{i})\leq\sum_{i=1}^{m}\frac{3}{m}\delta^{f}_{n}(\tilde{\xi}^{n}_{i}).$
(35)

By Assumption 3.2, $\tilde{\xi}^{n}_{i}$ is independent of
$\tilde{\xi}^{n}_{j}$ for $i\neq j$. Hence, we have

$\text{Var}\left[\sum_{i=1}^{m}\frac{3}{m}\delta^{f}_{n}(\tilde{\xi}^{n}_{i})\right]=\frac{9}{m^{2}}\sum_{i=1}^{m}\text{Var}\left[\delta^{f}_{n}(\tilde{\xi}^{n}_{i})\right]\leq\frac{36M_{F}N_{F}}{mn^{\lambda}}.$
(36)

The last inequality in (36) is obtained by using the upper bound of the
variance of $\delta^{f}_{n}(\tilde{\xi}^{n})$ in (16). Again, by Assumption
3.2, we have

$\mathbb{E}\left[\sum_{i=1}^{m}\frac{3}{m}\delta^{f}_{n}(\tilde{\xi}^{n}_{i})\right]\leq\frac{6N_{F}}{n^{\lambda}}.$
(37)

Hence, using the relation in (26), and combining (35) - (37), we have

$\text{Var}\left[\left|\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}\right|\right]\leq\frac{36M_{F}N_{F}}{mn^{\lambda}}+\frac{36N_{F}^{2}}{n^{2\lambda}}.$

∎

In Theorem 3.1, the upper bound of the variance of
$|\theta_{N,\rho}(\tilde{\xi}^{N})-\theta^{*}|$ consists of two components,
where $\frac{36M_{F}N_{F}}{mn^{\lambda}}$ is due to the average of $m$
replications of sample average approximation of the true function and
$\frac{36N_{F}^{2}}{n^{2\lambda}}$ is due to the sampling error from each
replication.

###  3.2 Sample Complexity of the Inexact Compromise Decision Problem

Here, we aim to study the reliability of the $\epsilon-$optimal compromise
decisions, $\hat{x}_{N,\rho,\epsilon}(\xi^{N})$, to the inexact compromise
decision problem (23). To achieve this goal, we first need to find a suitable
upper bound of the pessimistic distance,
$\Delta(\hat{X}_{N,\rho,\epsilon}(\xi^{N}),X_{\epsilon}^{*})$. With the help
of theorem of the Lipschtizan behavior of the $\epsilon$-optimal solution set
(Theorem 1.1), we will show that such upper bound could be further bounded by
a function of the supremum of the sampling error of the objective function
estimate (see Definition 4).
To begin with, we introduce several notations in the aggregation step to ease
the analysis. Let $\bar{f}_{N}(x;\xi^{N})$ denote the average of SAA functions
across $m$ replications:

$\bar{f}_{N}(x;\xi^{N})=\frac{1}{m}\sum_{i=1}^{m}f_{n}(x;\xi^{n}_{i}).$ (38)

We then let $\bar{\theta}_{N}(\xi^{N})$ denote the minimum of
$\bar{f}_{N}(x;\xi^{N})$ over $X$:

$\bar{\theta}_{N}(\xi^{N})=\min_{x\in X}\bar{f}_{N}(x;\xi^{N}).$ (39)

We further let $\bar{X}_{N,\epsilon}(\xi^{N})$ denote $\epsilon$-optimal
solution set of the aggregated SAA problem in (39):

$\bar{X}_{N,\epsilon}(\xi^{N})=\left\\{x\in
X:\bar{f}_{N}(x;\xi^{N})\leq\bar{\theta}_{N}(\xi^{N})+\epsilon\right\\}.$ (40)

We now proceed to introduce several notations for the inexact compromise
decision problem in (23). Given $x_{n,\epsilon}(\xi^{n}_{i})\in
X_{n,\epsilon}(\xi^{n}_{i}),\ i=1,\ldots,m$, defined in (22), we let
$\theta_{N,\rho,\epsilon}(\xi^{N})$ denote the optimal cost of the inexact
compromise decision problem:

$\theta_{N,\rho,\epsilon}(\xi^{N})=\min_{x\in
X}\bar{f}_{N}(x;\xi^{N})+\frac{\rho}{2}\left\|x-\frac{1}{m}\sum_{i=1}^{m}x_{n,\epsilon}(\xi^{n}_{i})\right\|^{2}.$
(41)

The associated $\epsilon$-optimal solution set of the inexact compromise
decision problem is defined as follows:

$\hat{X}_{N,\rho,\epsilon}(\xi^{N})=\left\\{x\in
X:\bar{f}_{N}(x;\xi^{N})+\frac{\rho}{2}\left\|x-\frac{1}{m}\sum_{i=1}^{m}x_{n,\epsilon}(\xi^{n}_{i})\right\|^{2}\leq\theta_{N,\rho,\epsilon}+\epsilon\right\\}.$
(42)

Recall that $\theta^{*}$ is the optimal cost of the true problem in (1).We let
$X^{*}_{\epsilon}$ denote the $\epsilon$-optimal solution set of the true
problem:

$X^{*}_{\epsilon}=\left\\{x\in X:f(x)\leq\theta^{*}+\epsilon\right\\}.$ (43)

The following lemma sets up the relationship among elements of
$\epsilon$-optimal solution set of the inexact compromise decision problem,
$m$ replications of SAA problems, and the true problem.

######  Lemma 3.2.

Let $\hat{X}_{N,\rho,\epsilon}(\xi^{N})$, $\bar{X}_{N,\epsilon}(\xi^{N})$,
$X_{\epsilon}^{*}$, and $X_{n,\epsilon}(\xi^{n}_{j})$ be defined in (42),
(40), (43), and (22), respectively. Let
$\hat{x}_{N,\rho,\epsilon}(\xi^{N})\in\hat{X}_{N,\rho,\epsilon}(\xi^{N})$,
$\bar{x}_{N,\epsilon}(\xi^{N})\in\bar{X}_{N,\epsilon}(\xi^{N})$,
$x_{\epsilon}^{*}\in X_{\epsilon}^{*}$, $x_{n,\epsilon}(\xi^{n}_{j})\in
X_{n,\epsilon}(\xi^{n}_{j})$, $j=1,2,\ldots,m$. Then the following relation
holds:

$\left\|\hat{x}_{N,\rho,\epsilon}(\xi^{N})-x_{\epsilon}^{*}\right\|\leq\left\|\bar{x}_{N,\epsilon}(\xi^{N})-\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})\right\|+\left\|\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})-x_{\epsilon}^{*}\right\|+2\sqrt{\epsilon/\rho}.$

###### Proof.

We provide a brief sketch here, and postpone the details to Appendix B.5. In
essence, we use the optimality of the compromise decision problem in (41) to
bound
$\left\|\hat{x}_{N,\rho,\epsilon}(\xi^{N})-\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})\right\|$.
The final result follows from an application of the triangle inequality. . ∎

With the upper bound of
$\|\hat{x}_{N,\rho,\epsilon}(\xi^{N})-x_{\epsilon}^{*}\|$ obtained in Lemma
3.2, we derive the upper bound of pessimistic distance of
$\hat{X}_{N,\rho,\epsilon}(\xi^{N})$ to $X_{\epsilon}^{*}$,
$\Delta(\hat{X}_{N,\rho,\epsilon}(\xi^{N}),X_{\epsilon}^{*})$, in the next
lemma.

######  Lemma 3.3.

Let $\hat{X}_{N,\rho,\epsilon}(\xi^{N})$, $\bar{X}_{N,\epsilon}(\xi^{N})$,
$X_{\epsilon}^{*}$, and $X_{n,\epsilon}(\xi^{n}_{j})$ be defined in (42),
(40), (43), and (22), respectively. Let
$\hat{x}_{N,\rho,\epsilon}(\xi^{N})\in\hat{X}_{N,\rho,\epsilon}(\xi^{N})$,
$\bar{x}_{N,\epsilon}(\xi^{N})\in\bar{X}_{N,\epsilon}(\xi^{N})$,
$x_{\epsilon}^{*}\in X_{\epsilon}^{*}$, $x_{n,\epsilon}(\xi^{n}_{j})\in
X_{n,\epsilon}(\xi^{n}_{j})$, $j=1,2,\ldots,m$. Then the following relation
holds:

$\displaystyle\Delta\left(\hat{X}_{N,\rho,\epsilon}(\xi^{N}),X_{\epsilon}^{*}\right)$
$\displaystyle\leq\inf_{x\in\bar{X}_{N,\epsilon}(\xi^{N})}\left\|\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})-x\right\|$
$\displaystyle\quad+\inf_{x\in
X_{\epsilon}^{*}}\left\|\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})-x\right\|+2\sqrt{\epsilon/\rho}.$

###### Proof.

See Appendix B.6. ∎

In the next result, we aim to use Theorem 1.1 and estimation errors defined in
(15) to bound
$\inf\limits_{x\in\bar{X}_{N,\epsilon}(\xi^{N})}\|\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})-x\|$.

######  Lemma 3.4.

Let $\bar{X}_{N,\epsilon}(\xi^{N})$ and $X_{n,\epsilon}(\xi^{n}_{j})$ be
defined in (40) and (22), respectively. Let $\delta_{n}^{f}(\cdot)$ be defined
in Definition 4. Let $x_{n,\epsilon}(\xi^{n}_{j})\in
X_{n,\epsilon}(\xi^{n}_{j})$, $j=1,2,\ldots,m$. Suppose that Assumptions 2.1,
3.1, and 3.2 hold. The following relation holds:

$\inf_{x\in\bar{X}_{N,\epsilon}(\xi^{N})}\left\|\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})-x\right\|\leq\frac{\frac{1}{m^{2}}\sum_{\begin{subarray}{c}i,j=1\\\
i\neq
j\end{subarray}}^{m}\Big{[}\delta_{n}^{f}(\xi^{n}_{j})+\delta^{f}_{n}(\xi^{n}_{j})\Big{]}}{\epsilon}D_{X}.$

###### Proof.

We first provide a proof sketch, which consists of two steps. In Step 1, we
show that $\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})$ is an
$\epsilon^{\prime}$-optimal solution of the problem in (39), where
$\epsilon^{\prime}=\epsilon+\frac{1}{m^{2}}\sum_{\begin{subarray}{c}i,j=1\\\
i\neq j\end{subarray}}^{m}(\delta_{n}(\xi^{n}_{i})+\delta_{n}(\xi^{n}_{j}))$.
The key part of the proof is to derive the following relation,

$f_{n}(x_{n,\epsilon}(\xi^{n}_{j});\xi^{n}_{i})\leq\theta_{n}(\xi^{n}_{j})+\epsilon+\delta_{n}(\xi^{n}_{i})+\delta_{n}(\xi^{n}_{j}),$

where $\theta_{n}(\xi^{n}_{j})$ is defined in (24). Note that if we evaluate
$f_{n}(x;\xi^{n}_{i})$ at the point $x_{n,\epsilon}(\xi^{n}_{j})$, it should
depend on three factors: (1) the minimum of $f_{n}(x;\xi^{n}_{i})$ over $X$;
(2) the systematic error $\epsilon$; (3) the sampling errors from
$f_{n}(x;\xi^{n}_{i})$ and $f_{n}(x;\xi^{n}_{j})$. In Step 2 of the proof, we
can apply Theorem 1.1 to derive the upper bound on
$\inf_{x\in\bar{X}_{N,\epsilon}(\xi^{N})}\left\|\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})-x\right\|$.
(Step 1: To show $\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})$ is an
$\epsilon^{\prime}$-optimal solution of the problem in (39)). We let
$\bar{x}_{N}(\xi^{N})\in\arg\min_{x\in X}\bar{f}_{N}(x;\xi^{N})$, where
$\bar{f}_{N}(x;\xi^{N})$ is defined in (38). First, by convexity assumption in
Assumption 3.1, we observe that

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}f_{n}\left(\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j});\xi^{n}_{i}\right)$
(44)
$\displaystyle\leq\frac{1}{m^{2}}\sum_{i=1}^{m}\sum_{j=1}^{m}f_{n}(x_{n,\epsilon}(\xi^{n}_{j});\xi^{n}_{i})\quad\text{by
convexity in Assumption \ref{assumption:part 2}}$
$\displaystyle=\frac{1}{m^{2}}\sum_{i=1}^{m}\sum_{j=1}^{m}\left[f_{n}(\bar{x}_{N}(\xi^{N});\xi^{n}_{j})+f_{n}^{i}(x_{n,\epsilon}(\xi^{n}_{j});\xi^{n}_{i})-f_{n}(\bar{x}_{N}(\xi^{N});\xi^{n}_{j})\right].$

Similar to the derivation in (28) from Theorem 3.1, for $i\neq j$, we have

$\displaystyle f_{n}(x_{n,\epsilon}(\xi^{n}_{j});\xi^{n}_{i})$
$\displaystyle=f_{n}(x_{n,\epsilon}(\xi^{n}_{j});\xi^{n}_{j})+f_{n}(x_{n,\epsilon}(\xi^{n}_{j});\xi^{n}_{i})-f_{n}(x_{n,\epsilon}(\xi^{n}_{j});\xi^{n}_{j})$
(45)
$\displaystyle\leq\theta_{n}(\xi^{n}_{j})+\epsilon+|f_{n}(x_{n,\epsilon}(\xi^{n}_{j});\xi^{n}_{i})-f_{n}(x_{n,\epsilon}(\xi^{n}_{j});\xi^{n}_{j})|$
$\displaystyle\leq\theta_{n}(\xi^{n}_{j})+\epsilon+\sup_{x\in
X}|f_{n}(x;\xi^{n}_{i})-f(x)|+\sup_{x\in X}|f_{n}(x;\xi^{n}_{j})-f(x)|$
$\displaystyle=\theta_{n}(\xi^{n}_{j})+\epsilon+\delta^{f}_{n}(\xi^{n}_{i})+\delta^{f}_{n}(\xi^{n}_{j}).$

The combination of (44) and (45) implies that

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}f_{n}\left(\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j});\xi^{n}_{i}\right)$
$\displaystyle\leq\frac{1}{m^{2}}\sum_{i=1}^{m}\sum_{j=1}^{m}\Bigg{[}f_{n}\left(\bar{x}_{N}(\xi^{N});\xi^{n}_{j}\right)+\theta_{n}(\xi^{n}_{j})+\epsilon$
(46)
$\displaystyle\quad+\big{(}\delta_{n}^{f}(\xi^{n}_{i})+\delta_{n}^{f}(\xi^{n}_{j})\big{)}\mathbb{I}(i\neq
j)-f_{n}(\bar{x}_{N}(\xi^{N});\xi^{n}_{j})\Bigg{]}$
$\displaystyle=\theta_{N}(\xi^{N})+\epsilon+\frac{1}{m^{2}}\sum_{j=1}^{m}\Big{[}\theta_{n}(\xi^{n}_{j})-f_{n}\Big{(}\bar{x}_{N}(\xi^{N});\xi^{n}_{j}\Big{)}\Big{]}$
$\displaystyle\quad+\frac{1}{m^{2}}\sum_{\begin{subarray}{c}i,j=1\\\ i\neq
j\end{subarray}}^{m}\Big{[}\delta^{f}_{n}(\xi^{n}_{i})+\delta^{f}_{n}(\xi^{n}_{j})\Big{]}$
$\displaystyle\leq\theta_{N}(\xi^{N})+\epsilon+\frac{1}{m^{2}}\sum_{\begin{subarray}{c}i,j=1\\\
i\neq
j\end{subarray}}^{m}\Big{[}\delta^{f}_{n}(\xi^{n}_{i})+\delta^{f}_{n}(\xi^{n}_{j})\Big{]}.$

Hence, equation (46) shows that $\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})$ is
the $\epsilon^{\prime}$-optimal solution of the problem $\min_{x\in
X}\bar{f}_{N}(x;\xi^{N})$, where
$\epsilon^{\prime}=\epsilon+\frac{1}{m^{2}}\sum_{\begin{subarray}{c}i,j=1\\\
i\neq
j\end{subarray}}^{m}[\delta^{f}_{n}(\xi^{n}_{i})+\delta^{f}_{n}(\xi^{n}_{j})]$.
(Step 2: To derive upper bound of
$\inf_{x\in\bar{X}_{N,\epsilon}}\|\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})-x\|$
using Theorem 1.1) Let
$\epsilon^{\prime}=\epsilon+\frac{1}{m^{2}}\sum_{\begin{subarray}{c}i,j=1\\\
i\neq
j\end{subarray}}^{m}(\delta^{f}_{n}(\xi^{n}_{i})+\delta^{f}_{n}(\xi^{n}_{j}))$,
then
$\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})\in\bar{X}_{N,\epsilon^{\prime}}(\xi^{N})$.
Hence, by Theorem 1.1, we have

$\displaystyle\inf_{x\in\bar{X}_{N,\epsilon}}\|\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})-x\|$
$\displaystyle\leq\Delta(\bar{X}_{N,\epsilon^{\prime}}(\xi^{N}),\bar{X}_{N,\epsilon}(\xi^{N}))$
(47)
$\displaystyle\leq\frac{\epsilon^{\prime}-\epsilon}{\epsilon}D_{X}\leq\frac{\frac{1}{m^{2}}\sum_{\begin{subarray}{c}i,j=1\\\
i\neq
j\end{subarray}}^{m}(\delta^{f}_{n}(\xi^{n}(\xi^{n}_{i})+\delta^{f}_{n}(\xi^{n}_{j}))}{\epsilon}D_{X}.$

∎

Similar to the proof of Lemma 3.4, we will apply Theorem 1.1 to obtain the
upper bound of $\inf\limits_{x\in
X^{*}_{\epsilon}}\|\frac{1}{m}\sum_{j=1}^{m}x^{j}_{n,\epsilon}-x\|$.

######  Lemma 3.5.

Let $X_{n,\epsilon}(\xi^{n}_{j})$ and $X_{\epsilon}^{*}$ be defined in (22)
and (43), respectively. Let $x_{n,\epsilon}(\xi^{n}_{j})\in
X_{n,\epsilon}(\xi^{n}_{j})$, $j=1,2,\ldots,m$. Let $\delta_{n}^{f}(\cdot)$ be
defined in Definition 4. Suppose that Assumptions 2.1, 3.1, and 3.2 hold. Then
the following relation holds:

$\inf_{x\in
X^{*}_{\epsilon}}\|\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})-x\|\leq\frac{\frac{2}{m}\sum_{j=1}^{m}\delta^{f}_{n}(\xi^{n}_{j})}{\epsilon}D_{X}.$

###### Proof.

The proof strategy is similar to Lemma 3.4. See Appendix B.7. ∎

With the bounds obtained in Lemmas 3.3 \- 3.5, we now present the finite-
sample complexity of the compromise decisions in the following theorem.

######  Theorem 3.6.

Suppose that Assumptions 2.1, 3.1, and 3.2 hold. Let
$\hat{X}_{N,\rho,\epsilon}(\xi^{N})$ be defined in (42). Let
$\lambda\in(0,\frac{1}{2})$ and $N_{F}$ be a constant defined in Lemma 2.3.
Let $\delta_{n}^{f}(\cdot)$ be defined in Definition 4.Then the following
hold:

  1. 1.

$\Delta(\hat{X}_{N,\rho,\epsilon}(\xi^{N}),X_{\epsilon}^{*})\leq\frac{\frac{2}{m}\sum_{j=1}^{m}\delta^{f}_{n}(\xi^{n}_{j})+\frac{1}{m^{2}}\sum_{\begin{subarray}{c}i,j=1\\\
i\neq
j\end{subarray}}^{m}\Big{[}\delta^{f}_{n}(\xi^{n}_{i})+\delta^{f}_{n}(\xi^{n}_{j})\Big{]}}{\epsilon}D_{X}+2\sqrt{\epsilon/\rho}.$
(48)

  2. 2.

$\mathbb{E}[\Delta(\hat{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})]\leq\frac{D_{X}N_{F}}{\epsilon}\frac{8m-4}{mn^{\lambda}}+2\sqrt{\epsilon/\rho}.$

  3. 3.

Further let $\rho=n$ and
$C=\frac{\epsilon^{\frac{3}{2}}}{D_{X}}+\frac{(4m-2)N_{F}}{m}$, then we have

$\Pr\left\\{\frac{\epsilon
n^{\lambda}}{2D_{X}}\Delta(\hat{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})\geq
C+t\right\\}\leq
m\exp\left\\{-\frac{m^{2}t^{2}}{2M^{2}_{F}(2m-1)^{2}}\right\\}.$

###### Proof.

As with some of the previous results, we begin with an overview of the proof.
Part 1 (48) of the theorem follows by directly combining the results of Lemmas
3.3, 3.4, and 3.5. Hence, we will skip the proof of Part 1. Part 2 of the
theorem follows by taking the expectation of both sides of (48) and then
applying Theorem 2.6.1. Part 3 of the theorem follows by applying Theorem
2.6.2 into (48).
(Proof of Part 2) By Theorem 2.6, note that
$\mathbb{E}[\delta^{f}_{n}(\tilde{\xi}^{n}_{i})]\leq 2R_{n}(F,\Xi)$ for
$i=1,2,\ldots,m$. By taking the expectation of both sides of (48) and by the
i.i.d assumption in Assumption 3.2, we have

$\displaystyle\mathbb{E}[\Delta(\hat{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})]$
$\displaystyle\leq\frac{4R_{n}(F,\Xi)+\frac{4m^{2}-4m}{m^{2}}R_{n}(F,\Xi)}{\epsilon}+2\sqrt{\epsilon/\rho}$
$\displaystyle\leq\frac{D_{X}N_{F}}{\epsilon}\frac{8m-4}{mn^{\lambda}}+2\sqrt{\epsilon/\rho}$
by Theorem 2.6.

(Proof of Part 3) Equation (48) implies that

$\displaystyle\Pr\left\\{\frac{\epsilon
n^{\lambda}}{2D_{X}}\Delta(\hat{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})\geq
C+t\right\\}$ (49)
$\displaystyle\leq\Pr\left\\{\frac{n^{\lambda}}{m}\sum_{j=1}^{m}\delta^{f}_{n}(\tilde{\xi}^{n}_{j})+\frac{n^{\lambda}}{2m^{2}}\sum_{\begin{subarray}{c}i,j=1\\\
i\neq
j\end{subarray}}^{m}\Big{[}\delta^{f}_{n}(\tilde{\xi}^{n}_{i})+\delta^{f}_{n}(\tilde{\xi}^{n}_{j})\Big{]}+\frac{\epsilon^{\frac{3}{2}}n^{\lambda}}{D_{X}n^{\frac{1}{2}}}\geq
C+t\right\\}$
$\displaystyle\leq\Pr\left\\{\frac{n^{\lambda}}{m}\sum_{j=1}^{m}\delta^{f}_{n}(\tilde{\xi}^{n}_{j})+\frac{n^{\lambda}}{2m^{2}}\sum_{\begin{subarray}{c}i,j=1\\\
i\neq
j\end{subarray}}^{m}\Big{[}\delta^{f}_{n}(\tilde{\xi}^{n}_{i})+\delta^{f}_{n}(\tilde{\xi}^{n}_{j})\Big{]}+\frac{\epsilon^{\frac{3}{2}}}{D_{X}}\geq
C+t\right\\}\ \text{because }\frac{n^{\lambda}}{n^{\frac{1}{2}}}\leq 1$
$\displaystyle\leq\Pr\left\\{\sum_{i=1}^{m}\frac{n^{\lambda}(2m-1)}{m^{2}}\delta^{f}_{n}(\tilde{\xi}^{n}_{i})\geq\frac{(4m-2)N_{F}}{m}+t\right\\}$

Given two random variables $X_{1},X_{2}$ and constants $\epsilon$, we have
$\Pr(X_{1}+X_{2}\geq\epsilon)\leq\Pr(X_{1}\geq\frac{\epsilon}{2})+\Pr(X_{2}\geq\frac{\epsilon}{2})$
(see [37, equation (5)] for a similar argument). Hence it follows from (49)
that

$\displaystyle\Pr\left\\{\sum_{i=1}^{m}\frac{n^{\lambda}(2m-1)}{m^{2}}\delta^{f}_{n}(\tilde{\xi}^{n}_{i})\geq\frac{(4m-2)N_{F}}{m}+t\right\\}$
(50)
$\displaystyle\leq\sum_{i=1}^{m}\Pr\left\\{\frac{n^{\lambda}(2m-1)}{m^{2}}\delta^{f}_{n}(\tilde{\xi}^{n}_{i})\geq\frac{(4m-2)N_{F}}{m^{2}}+\frac{t}{m}\right\\}$
$\displaystyle=\sum_{i=1}^{m}\Pr\left\\{n^{\lambda}\delta^{f}_{n}(\tilde{\xi}^{n}_{i})\geq
2N_{F}+\frac{mt}{2m-1}\right\\}$ $\displaystyle\leq
m\exp\left\\{-\frac{m^{2}t^{2}}{2M^{2}_{F}(2m-1)^{2}}\right\\}\quad\text{by
Theorem \ref{theorem:bound of function estimation error}.2 }.$

∎

Finally, we close this section by deriving the upper bound on the variance of
$\Delta(\hat{X}_{N,\rho,\epsilon}(\xi^{N}),X_{\epsilon}^{*})$ (i.e., the
largest distance from the $\epsilon$-optimal solution set of the compromise
decision problem to the $\epsilon$-optimal solution set of the true problem).

######  Theorem 3.7.

Suppose that Assumptions 2.1, 3.1, and 3.2 hold. Let
$\hat{X}_{N,\rho,\epsilon}(\xi^{N})$ and $X^{*}_{\epsilon}$ be defined in (42)
and (43), respectively. Let $\lambda\in(0,\frac{1}{2})$ and $N_{F}$ be a
constant defined in Lemma 2.3. Then the following holds:

$\text{Var}[\Delta(\hat{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})]\leq\frac{64D_{X}^{2}M_{F}N_{F}}{m\epsilon^{2}n^{\lambda}}+\left(\frac{8D_{X}N_{F}}{\epsilon
n^{\lambda}}+2\sqrt{\epsilon/\rho}\right)^{2}.$

Furthermore, let $K$ be a positive constant. Letting $\rho\geq Kn$, we have
$\mathbb{E}[\Delta(\hat{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})]=O(\frac{1}{n^{\lambda}})$
and
$\text{Var}[\Delta(\hat{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})]=O(\frac{1}{mn^{\lambda}}+\frac{1}{n^{2\lambda}})$.

###### Proof.

Here is a proof sketch: we use the relation in Theorem 3.6.1, relation in
(26), and, bound of variance of estimation error in (16) to derive the upper
bound of
$\text{Var}[\Delta(\hat{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})]$.
In particular, we make use of the assumption that the sample set in
replication $i$ is independent of the sample set in replication $j$ (given
$i\neq j$) to decompose the variance.
Next, we shall give the details of the proof. It follows from Theorem 3.6 that

$\displaystyle\Delta(\hat{X}_{N,\rho,\epsilon}(\xi^{N}),X_{\epsilon}^{*})$
$\displaystyle\leq\frac{\frac{2}{m}\sum_{j=1}^{m}\delta^{f}_{n}(\xi^{n}_{j})+\frac{1}{m^{2}}\sum_{\begin{subarray}{c}i,j=1\\\
i\neq
j\end{subarray}}^{m}[\delta^{f}_{n}(\xi^{n}_{i})+\delta^{f}_{n}(\xi^{n}_{j})]}{\epsilon}D_{X}+2\sqrt{\epsilon/\rho}$
(51)
$\displaystyle\leq\sum_{i=1}^{m}\frac{4D_{X}}{m\epsilon}\delta^{f}_{n}(\xi_{j}^{n})+2\sqrt{\epsilon/\rho}.$

According to (16), we have
$\text{Var}[\delta^{f}_{n}(\tilde{\xi}^{n})]\leq\frac{4M_{F}N_{F}}{n^{\lambda}}$.
Hence, by i.i.d. assumption in Assumption 3.2, we can derive the upper bound
of the variance of the right-hand side of 51 as follows:

$\displaystyle\text{Var}\left[\sum_{i=1}^{m}\frac{4D_{X}}{m\epsilon}\delta^{f}_{n}(\tilde{\xi}_{j}^{n})+2\sqrt{\epsilon/\rho}\right]$
$\displaystyle=\sum_{i=1}^{m}\frac{16D_{X}^{2}}{m^{2}\epsilon^{2}}\text{Var}[\delta^{f}_{n}(\tilde{\xi}_{j}^{n})]$
(52)
$\displaystyle\leq\frac{64D_{X}^{2}M_{F}N_{F}}{m\epsilon^{2}n^{\lambda}}.$

Using equations (51), (52), and Theorem 2.6.1, we can derive the upper bound
of the variance of
$\Delta(\hat{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})$ as
follows:

$\displaystyle\text{Var}\left[\Delta(\hat{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})\right]$
(53)
$\displaystyle\leq\text{Var}\left[\sum_{i=1}^{m}\frac{4}{m\epsilon}D_{X}\delta_{n}(\tilde{\xi}_{j}^{n})+2\sqrt{\epsilon/\rho}\right]+\left(\mathbb{E}\left[\sum_{i=1}^{m}\frac{4}{m\epsilon}D_{X}\delta_{n}(\tilde{\xi}_{j}^{n})+2\sqrt{\epsilon/\rho}\right]\right)^{2}$
$\displaystyle\leq\frac{64D_{X}^{2}M_{F}N_{F}}{m\epsilon^{2}n^{\lambda}}+\left(\frac{8D_{X}N_{F}}{\epsilon
n^{\lambda}}+2\sqrt{\epsilon/\rho}\right)^{2}.$

Finally, the big $O$ results follows by plugging $\rho\geq Kn$ into Theorem
3.6.2 and (53). ∎

##  4 Algorithms for Compromise Decision Problems

In the previous section, we have discussed the reliability of the compromise
decision using SAA in the replication step. There are two issues which remain
unresolved: (1) How should we solve the SAA problems in the replication step?
(2) How should we simplify the aggregated objective function estimate without
losing reliability?
In this section, we will continue studying the case in which a proper
algorithm is applied to solve each replication of the SAA problem. We aim to
provide a framework to combine the computational objects which are created
during a replication of a cutting-plane-type algorithm, and then use such
information to formulate an algorithm-augmented compromise decision problem.
Given a sample set $\xi^{n}$, we let $\hat{x}_{n}(\xi^{n})$ and
$\hat{f}_{n}(x;\xi^{n})$ denote the estimated solution and approximated
objective function of SAA objective function $f_{n}(x;\xi^{n})$ (i.e.,
$f_{n}(x;\xi^{n})=\frac{1}{n}\sum_{i=1}^{n}F(x,\xi_{i})$) output by the
algorithm. We assume that the algorithm constructs a piecewise linear outer
approximation of the SAA objective function.

######  Condition 1 (Outer Approximation).

$\hat{f}_{n}(x;\xi^{n})$ is a convex piecewise linear approximation of
$f_{n}(x;\xi^{n})$ (i.e., $\hat{f}_{n}(x;\xi^{n})=\max\limits_{\ell\in
L}\\{\alpha_{\ell}+\langle\beta_{\ell},x\rangle\\}$, where $L$ is the index
set of the pieces of $\hat{f}_{n}(x;\xi^{n})$), such that
$\hat{f}_{n}(x;\xi^{n})\leq f_{n}(x;\xi^{n})$ for all $x\in X$.

When the algorithm terminates, we assume that the following condition holds.

######  Condition 2 (Termination Condition).

Let $\hat{x}_{n}(\xi^{n})\in\arg\min\limits_{x\in X}\hat{f}_{n}(x;\xi^{n})$.
There exists $\epsilon_{1}\in(0,\infty)$ such that
$f_{n}\left(\hat{x}_{n}(\xi^{n});\xi^{n}\right)-\hat{f}_{n}\left(\hat{x}_{n}(\xi^{n});\xi^{n}\right)\leq\epsilon_{1}$.

Condition 1 ensures that it outputs an outer approximation of the SAA of the
objective function. Condition 2 is often used as a stopping criterion for
Benders’ type decomposition-based algorithms (see [4, Chapter 6.5] for an
example). For instance, Kelley’s Cutting Plane Methods ([20]) and other
Benders’ type decomposition-based algorithms ([28, 31, 33, 40]) will satisfy
the conditions above. Overall, Conditions 1 and 2 altogether ensure that an
algorithm yields an $\epsilon_{1}$-optimal solution of the SAA problem. To see
why, let $x_{n}(\xi^{n})\in\arg\min\limits_{x\in X}f_{n}(x;\xi^{n})$,
$\theta_{n}(\xi^{n})=\min\limits_{x\in X}f_{n}(x;\xi^{n})$, and
$\hat{\theta}_{n}(\xi^{n})=\min\limits_{x\in X}\hat{f}_{n}(x;\xi^{n})$. Then
by Conditions 1 and 2, we derive the following relation:

$\theta_{n}(\xi^{n})=f_{n}(x_{n}(\xi^{n});\xi^{n})\geq\hat{f}_{n}\left(x_{n}(\xi^{n});\xi^{n}\right)\geq\hat{\theta}_{n}(\xi^{n})=\hat{f}_{n}\left(\hat{x}_{n}(\xi^{n});\xi^{n}\right).$
(54)

Hence, by Condition 2 and inequality in (54), we have

$\displaystyle f_{n}\left(\hat{x}_{n}(\xi^{n});\xi^{n}\right)$
$\displaystyle=\hat{f}_{n}\left(\hat{x}_{n}(\xi^{n});\xi^{n}\right)+f_{n}\left(\hat{x}_{n}(\xi^{n});\xi^{n}\right)-\hat{f}_{n}\left(\hat{x}_{n}(\xi^{n});\xi^{n}\right)$
$\displaystyle\leq\theta_{n}(\xi^{n})+\epsilon_{1}$

To answer the second question, we discuss a necessary pre-processing in the
aggregation step. For $i=1,2,\ldots,m$, we let $\hat{x}_{n}(\xi^{n}_{i})$ and
$\hat{f}_{n}(x;\xi^{n}_{i})$ denote the estimated solution of
$\min\limits_{x\in X}f_{n}(x;\xi^{n}_{i})$ and surrogate function of
$f_{n}(x;\xi^{n}_{i})$ (i.e., $f_{n}(x;\xi^{n}_{i})$ is defined in (20)),
respectively. Given $\epsilon_{2}\geq 0$, in the pre-processing step, we
augment $\hat{f}_{n}(x;\xi^{n}_{i})$ by letting

$\check{f}_{n}(x;\xi^{n}_{i})=\max\\{\hat{f}_{n}(x;\xi^{n}_{i}),\max_{j=1,\ldots,m}\left\\{f_{n}(\hat{x}_{n}^{j};\xi^{n}_{i})+\langle\upsilon_{n,\epsilon_{2}}(\hat{x}_{n}^{j};\xi^{n}_{i}),x-\hat{x}^{j}_{n}\rangle-\epsilon_{2}\\}\right\\},$
(55)

where $\upsilon_{n,\epsilon_{2}}(\hat{x}_{n}^{j};\xi^{n}_{i})$ is the
$\epsilon_{2}$-subgradient of $f_{n}(\cdot;\xi^{n}_{i})$ at $\hat{x}_{n}^{j}$.
This pre-processing controls the deviation of the augmented function from its
associated SAA function at the candidate solution from each replication.
With the augmented functions and candidate solution from each replication, we
can set up the compromise decision program below:

$\min_{x\in
X}\frac{1}{m}\sum_{i=1}^{m}\check{f}_{n}(x;\xi^{n}_{i})+\frac{\rho}{2}\left\|x-\frac{1}{m}\sum_{j=1}^{m}\hat{x}_{n}(\xi^{n}_{j})\right\|^{2}.$
(56)

To distinguish (56) from previously introduced compromise decision problems in
section 3, we shall refer to the problem (56) as algorithm-augmented
compromise decision problem.
We let $\hat{\theta}_{N}(\xi^{N})$ denote the minimum of the average of the
approximation functions across $m$ replications:

$\hat{\theta}_{N}(\xi^{N})=\min_{x\in
X}\frac{1}{m}\sum_{i=1}^{m}\check{f}_{n}(x;\xi^{n}_{i}).$ (57)

Given a constant $\epsilon>0$, we then let $\hat{X}_{N,\epsilon}(\xi^{N})$
denote the $\epsilon$-optimal solution set of the problem in (57):

$\hat{X}_{N,\epsilon}(\xi^{N})=\left\\{x\in
X:\frac{1}{m}\sum_{i=1}^{m}\check{f}_{n}(x;\xi^{n}_{i})\leq\bar{\theta}_{N}(\xi^{N})+\epsilon\right\\}$
(58)

We let $\hat{\theta}_{N,\rho,\epsilon}(\xi^{N})$ and denote
$\check{X}_{N,\rho,\epsilon}(\xi^{N})$ the optimal cost and $\epsilon$-optimal
solution set of algorithm-augmented compromise decision problem in (56):

$\hat{\theta}_{N,\rho,\epsilon}(\xi^{N})=\min_{x\in
X}\frac{1}{m}\sum_{i=1}^{m}\check{f}_{n}(x;\xi^{n}_{i})+\frac{\rho}{2}\left\|x-\frac{1}{m}\sum_{i=1}^{m}\hat{x}_{n}(\xi^{n}_{i})\right\|^{2},$
$\check{X}_{N,\rho,\epsilon}(\xi^{N})=\left\\{x\in
X:\frac{1}{m}\sum_{i=1}^{m}f_{n}(x;\xi^{n}_{i})+\frac{\rho}{2}\left\|x-\frac{1}{m}\sum_{i=1}^{m}\hat{x}_{n}(\xi^{n}_{i})\right\|^{2}\leq\hat{\theta}_{N,\rho,\epsilon}(\xi^{N})+\epsilon\right\\}.$
(59)

By the same proof technique in Lemma 3.3, we can derive the upper bound of the
pessimistic distance of $\check{X}_{N,\rho,\epsilon}(\xi^{N})$ to
$X_{\epsilon}^{*}$:

$\displaystyle\Delta(\check{X}_{N,\rho,\epsilon}(\xi^{N}),X_{\epsilon}^{*})$
$\displaystyle\leq\inf_{x\in\hat{X}_{N,\epsilon}(\xi^{N})}\left\|\frac{1}{m}\sum_{j=1}^{m}\hat{x}_{n}(\xi^{n}_{j})-x\right\|$
$\displaystyle\quad+\inf_{x\in
X_{\epsilon}^{*}}\left\|\frac{1}{m}\sum_{j=1}^{m}\hat{x}_{n}(\xi^{n}_{j})-x\right\|+2\sqrt{\epsilon/\rho}.$

We derive the upper bounds of $\inf_{x\in
X_{\epsilon}^{*}}\|\frac{1}{m}\sum_{j=1}^{m}\hat{x}_{n}(\xi^{n}_{j})-x\|$ and
$\inf_{x\in\hat{X}_{N,\epsilon}(\xi^{N})}\|\frac{1}{m}\sum_{j=1}^{m}\hat{x}_{n}(\xi^{n}_{j})-x\|$
in the following two lemmas.

######  Lemma 4.1.

Let $X^{*}$ be defined in (43). Let $\hat{x}_{n}(\xi^{n}_{j})$ be the
candidate solution in the $j^{\text{th}}$ replication, for $j=1,2,\ldots,m$.
Let $\delta_{n}^{f}(\cdot)$ be defined in Definition 4. Suppose that
Assumptions 2.1, 3.1, and 3.2 hold. Further, suppose that Conditions 1 and 2
hold. If $\epsilon\leq\epsilon_{1}$, then the following relation holds:

$\inf_{x\in
X_{\epsilon}^{*}}\left\|\frac{1}{m}\sum_{j=1}^{m}\hat{x}_{n}(\xi^{n}_{j})-x\right\|\leq\frac{\tau_{1}+\frac{2}{m}\sum_{j=1}^{m}\delta^{f}_{n}(\xi^{n}_{j})}{\epsilon}D_{X},$

where $\tau_{1}=\epsilon_{1}-\epsilon$.

###### Proof.

We aim to show that $\frac{1}{m}\sum_{j=1}^{m}\hat{x}_{n}(\xi^{n}_{j})$ is an
$\epsilon^{\prime}$-optimal solution of true problem in (1), where
$\epsilon^{\prime}=\epsilon_{1}+\frac{2}{m}\sum_{j=1}^{m}\delta^{f}_{n}(\xi^{n}_{j})$.
Next, we can utilize Theorem 1.1 to finish the proof. See Appendix B.8 for
detailed proof. ∎

######  Lemma 4.2.

Let $\hat{X}_{N,\epsilon}(\xi^{N})$ be defined in (58). Let
$\hat{x}_{n}(\xi^{n}_{j})$ be the candidate solution in the $j^{\text{th}}$
replication, for $j=1,2,\ldots,m$. Let $\delta_{n}^{f}(\cdot)$ be defined in
Definition 4. Suppose that Assumptions 2.1, 3.1, and 3.2 hold. Further suppose
that Conditions 1 and 2 hold. If
$\epsilon\leq\epsilon_{1}+\frac{m-1}{m}\epsilon_{2}$, then the following
relation holds:

$\inf_{x\in\hat{X}_{N,\epsilon}(\xi^{N})}\left\|\frac{1}{m}\sum_{j=1}^{m}\hat{x}_{n}(\xi^{n}_{j})-x\right\|\leq\frac{\tau_{2}+\frac{1}{m^{2}}\sum_{\begin{subarray}{c}i,j=1\\\
i\neq
j\end{subarray}}^{m}\left(\delta^{f}_{n}(\xi^{n}_{i})+\delta^{f}_{n}(\xi^{n}_{j})\right)}{\epsilon}D_{X},$

where $\tau_{2}=\epsilon_{1}+\frac{m-1}{m}\epsilon_{2}-\epsilon$.

###### Proof.

Here, we aim to show that $\frac{1}{m}\sum_{j=1}^{m}\hat{x}_{n}(\xi^{n}_{j})$
is the $\epsilon^{\prime\prime}$-optimal solution of the aggregated problem in
(57), where
$\epsilon^{\prime\prime}=\tau_{2}+\frac{1}{m^{2}}\sum_{\begin{subarray}{c}i,j=1\\\
i\neq
j\end{subarray}}^{m}\left(\delta^{f}_{n}(\xi^{n}_{i})+\delta^{f}_{n}(\xi^{n}_{j})\right)$.
Then we can apply Theorem 1.1 to derive the upper bound of its associated
pessimistic distance. See Appendix B.9 for detailed proof. ∎

We derive the finite-sample complexity of the algorithm-augmented compromise
decision problem (56) in the following theorem.

######  Theorem 4.3.

Let $\check{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N})$ and $X^{*}_{\epsilon}$ be
defined in (59) and (43), respectively. Suppose that Assumptions 2.1, 3.1, and
3.2 hold. Further suppose that Conditions 1 and 2 hold. Let
$\lambda\in(0,\frac{1}{2})$ and $N_{F}$ be a constant defined in Lemma 2.3. If
$\epsilon\leq\epsilon_{1}$, then the following hold:

  * 1.

$\displaystyle\mathbb{E}\left[\Delta(\check{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})\right]$
$\displaystyle\leq\frac{D_{X}N_{F}}{\epsilon}\frac{8m-4}{mn^{\lambda}}+\frac{(\tau_{1}+\tau_{2})D_{X}}{\epsilon}+2\sqrt{\epsilon/\rho},$

where $\tau_{1}=\epsilon_{1}-\epsilon$ and
$\tau_{2}=\epsilon_{1}+\frac{m-1}{m}\epsilon_{2}-\epsilon$.

  * 2.

Furthermore, if $\epsilon_{1}=\epsilon$, $\epsilon_{2}=0$, $\rho=n$, and
$C=\frac{\epsilon^{\frac{3}{2}}}{D_{X}}+\frac{(4m-2)N_{F}}{m}$, then

$\Pr\left\\{\frac{\epsilon
n^{\lambda}}{2D_{X}}\Delta(\check{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})\geq
C+t\right\\}\leq
m\exp\left\\{-\frac{m^{2}t^{2}}{2M^{2}_{F}(2m-1)^{2}}\right\\}.$

###### Proof.

The proof strategy is similar to the Theorem 3.6. By Lemmas 4.1 and 4.2, we
have

$\displaystyle\Delta\left(\check{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*}\right)$
$\displaystyle\leq\frac{\tau_{1}+\frac{2}{m}\sum_{j=1}^{m}\delta^{f}_{n}(\tilde{\xi}^{n}_{j})}{\epsilon}D_{X}$
(60)
$\displaystyle\quad+\frac{\tau_{2}+\frac{1}{m^{2}}\sum_{\begin{subarray}{c}i,j=1\\\
i\neq
j\end{subarray}}^{m}\left(\delta^{f}_{n}(\tilde{\xi}^{n}_{i})+\delta^{f}_{n}(\tilde{\xi}^{n}_{j})\right)}{\epsilon}D_{X}+2\sqrt{\epsilon/\rho}$

According to Theorem 2.6, we have
$\mathbb{E}[\delta_{n}^{f}(\tilde{\xi}^{n}_{j})]\leq\frac{2N_{F}}{n^{\lambda}}$.
Hence, by taking the expectation of both sides of (60), we have

$\mathbb{E}\left[\Delta(\check{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})\right]\leq\frac{D_{X}N_{F}}{\epsilon}\frac{8m-4}{mn^{\lambda}}+\frac{(\tau_{1}+\tau_{2})D_{X}}{\epsilon}+2\sqrt{\epsilon/\rho}.$

Pick $\epsilon_{1}=\epsilon$, $\epsilon_{2}=0$, and
$C=\frac{\epsilon^{\frac{3}{2}}}{D_{X}}+\frac{(4m-2)N_{F}}{m}$. Then
$\tau_{1}=\tau_{2}=0$. Hence, we have

$\mathbb{E}\left[\Delta(\check{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})\right]\leq\frac{D_{X}N_{F}}{\epsilon}\frac{8m-4}{mn^{\lambda}}+2\sqrt{\epsilon/n}.$

Then rest of the proof is the same as the proof of Theorem 3.6. ∎

To end this section, we obtain the upper bound of the variance of
$\Delta(\check{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})$ in the
following theorem.

######  Theorem 4.4.

Suppose that Assumptions 2.1, 3.1, and 3.2 hold. Further suppose that
Conditions 1 and 2 hold. Let $\lambda\in(0,\frac{1}{2})$ and $N_{F}$ be a
constant defined in Lemma 2.3. If $\epsilon\leq\epsilon_{1}$, then the
following hold:

  * 1.

$\text{Var}\left[\Delta(\check{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})\right]\leq\frac{64D_{X}^{2}M_{F}N_{F}}{m\epsilon^{2}n^{\lambda}}+\left(\frac{8D_{X}N_{F}}{\epsilon
n^{\lambda}}+\frac{(\tau_{1}+\tau_{2})D_{X}}{\epsilon}+2\sqrt{\epsilon/\rho}\right)^{2},$

where $\tau_{1}=\epsilon_{1}-\epsilon$ and
$\tau_{2}=\epsilon_{1}+\frac{m-1}{m}\epsilon_{2}-\epsilon$.

  * 2.

Furthermore, let $K_{1}$ be a positive constant. For $\epsilon_{1}=\epsilon$,
$\epsilon_{2}=0$, and $\rho\geq K_{1}n$, we have

$\mathbb{E}[\Delta(\check{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})]=O(\frac{1}{n^{\lambda}}),\
\text{Var}[\Delta(\check{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})]=O(\frac{1}{mn^{\lambda}}+\frac{1}{n^{2\lambda}}).$

###### Proof.

The proof strategy is similar to Theorem 3.7. It follows from Theorem 4.3 that

$\displaystyle\Delta(\check{X}_{N,\rho,\epsilon}(\xi^{N}),X_{\epsilon}^{*})\leq\sum_{i=1}^{n}\frac{4D_{X}}{m\epsilon}\delta(\xi^{n}_{i})+\frac{(\tau_{1}+\tau_{2})D_{X}}{\epsilon}+2\sqrt{\epsilon/\rho}.$

Compared with Theorem 3.7, the only difference is that we have an extra term
$\frac{(\tau_{1}+\tau_{2})D_{X}}{\epsilon}$, which bounds the systematic error
in the algorithm. Furthermore, when $\epsilon_{1}=\epsilon$, $\epsilon_{2}=0$,
the upper bound of
$\Delta(\check{X}_{N,\rho,\epsilon}(\xi^{N}),X_{\epsilon}^{*})$ is reduced to
the one of Theorem 3.7. ∎

Inspired by the above results, we end this section with a mean-variance
optimization problem which summarizes the reliability of decisions in terms of
statistical estimates of the pessimistic distance to the set of optimal
decisions.

$\displaystyle\min_{n,m}$
$\displaystyle\mathbb{E}[\Delta(\check{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})]+\vartheta\text{Var}\left[\Delta(\check{X}_{N,\rho,\epsilon}(\tilde{\xi}^{N}),X_{\epsilon}^{*})\right]$
(61) s.t. $\displaystyle(\ref{eq:epsilon optimal solution set:true
problem})\text{ and }(\ref{eq:epsilon-optimal solution set}),a.s.$

Here $\vartheta>0$ is a parameter which reflects a decision-maker’s desire for
a choice which is near-optimum, even though it may be difficult (or even
impossible) to verify optimality (of the decision) with certainty.
Nevertheless, the mean and variance of the pessimistic distance provide a
statistical measure of optimality. The SSN instance [34] of the SP literature
is one such case.

##  5 Stochastic Decomposition for Compromise Decision Problem

In the previous two sections, we have discussed the reliability of the
compromise decisions for general convex stochastic programs. In this section,
we focus on deriving the sample complexity of compromise decisions for two-
stage stochastic quadratic programs with quadratic programming recourse (SQQP)
[25]. In particular, we consider that SD Algorithm is used to (approximately)
solve the SQQP problem in the replication step. We will later show that the
associated compromise decision has higher reliability under certain
assumptions.
First, we formulate the SQQP problem as follows:

$\displaystyle\min$ $\displaystyle
f(x)=\frac{1}{2}x^{\top}Qx+c^{\top}x+\mathbb{E}[h(x,\tilde{\xi})]$ (62) s.t.
$\displaystyle Ax\leq b,$

where $b$ and $c$ are $n_{1}$ dimensional vectors, $A$ is a $m_{1}\times
n_{1}$ matrix, $Q$ is a $n_{1}\times n_{1}$ symmetric and positive definite
matrix, and $h(x,\xi)$ is the minimum cost of the following second-stage
problem:

$\displaystyle h(x,\xi)=\min\ $ $\displaystyle\frac{1}{2}y^{\top}Py+d^{\top}y$
(63a) s.t. $\displaystyle Dy=e(\xi)-C(\xi)x,\quad[\lambda],$ (63b)
$\displaystyle y\geq 0,\quad[\gamma].$ (63c)

Here, $P$ is a $n_{2}\times n_{2}$ symmetric and positive definite matrix, $d$
is a $n_{2}$-dimensional vector, $D$ is a $m_{2}\times n_{2}$ matrix, $e(\xi)$
a $m_{2}$-dimensional random vector that depends on $\xi$, and $C(\xi)$ is a
$m_{2}\times n_{1}$ random matrix that also depends on $\xi$. We let $\lambda$
and $\gamma$ denote the dual multipliers of constraints (63b) and (63c).
According to [25], we make the following assumptions:

######  Assumption 5.1.

Let $X$ and $h(x,\xi)$ denote the first-stage feasible region and second-stage
recourse function, respectively.

  1. 1.

$Q$ and $P$ are symmetric and positive definite matrices.

  2. 2.

The first-stage feasible region $X=\\{x\in\mathbb{R}^{n_{1}}:Ax\leq b\\}$ is
compact. The set of possible realizations $\Xi$ is compact.

  3. 3.

The second-stage problem satisfies relatively complete recourse condition.

  4. 4.

The second-stage recourse function is uniformly bounded below by 0.

  5. 5.

Linear independence constraint qualification holds at the optimal solution
$x^{*}$ of (62).

  6. 6.

There exists $L_{h}\in(0,\infty)$ such that $|h(x_{1},\xi)-h(x_{2},\xi)|\leq
L_{h}\|x_{1}-x_{2}\|$ for almost every $\xi\in\Xi$.

  7. 7.

There exists a neighborhood $B(x^{*},\delta)$ with $\delta\in(0,\infty)$, such
that $h(x,\xi)$ is differentiable for all $x\in X$ and for almost every
$\xi\in\Xi$.

  8. 8.

The unique optimal solution $x^{*}$ is sharp.

  9. 9.

Strict complementarity holds at $x^{*}$.

Under the assumptions above, the optimal solution to the SQQP problem (62) is
unique. Let $x^{*}$ denoe the optimal solution to (62) and let
$X^{*}=\\{x^{*}\\}$. For the discussion about the validation of those
assumptions, we refer the readers to [25].

A sketch of the Stochastic Decomposition algorithm for SQQP is provided below.
In Algorithm 2, minorant generated in the $k^{\text{th}}$ iteration is an
inexact lower bound approximation of $\frac{1}{k}\sum_{i=1}^{k}h(x,\xi_{i})$.
SD stores previously visited faces of the polyhedral set to accelerate the
minorant construction. SD also rescales the previously generated minorants to
adapt to the incremental sampling scheme. The incumbent selection rule in SD
is used to maintain a sequence of incumbents with certain probabilistic
improvement in terms of minimizing the true objective function. Please see
[25, Algorithm 3.3] for detailed descriptions of the minorant construction and
incumbent selection rule.

Algorithm 2 Stochastic Decomposition for SQQP

Initialize $\\{\alpha_{k}\\}_{k}$, $x_{0}\in X$, $h_{0}(x)=0$, $k=0$, and
$\mathcal{J}_{0}=\\{0\\}$.

Set
$\hat{f}_{0}(x)=\frac{1}{2}x^{\top}Qx+c^{\top}x+\max\\{h^{k}_{j}(x),j\in\mathcal{J}_{0}\\}$.

while Stopping criterion is not satisfied do

Let $k\leftarrow k+1$.

Compute $x_{k}=\arg\min\limits_{x\in
X}\hat{f}_{k-1}(x)+\frac{1}{2\alpha_{k}}\|x-\hat{x}^{k-1}\|$.

Construct $\mathcal{J}_{k}$ to store active minorants at $x_{k}$.

Sample $\xi_{k}\sim\mathbb{P}_{\tilde{\xi}}$.

Compute dual optimal solutions $(\lambda_{k},\gamma_{k})$ of subproblem (63)
at $(x_{k},\xi_{k})$.

Store visited dual faces for accelerating computing future lower bounds.

Construct minorants, $h^{k}_{k}(x_{k},\xi_{k})$ and
$h^{k}_{-k}(x_{k},\xi_{k})$, of $\frac{1}{k}\sum_{i=1}^{k}h(x,\xi_{i})$ at
$\hat{x}^{k-1}$ and

$x^{k}$, respectively.

for $j\in\mathcal{J}_{k}$ do

Update minorant $h^{k}_{j}(x)\leftarrow\frac{|j|}{k}h^{|j|}_{j}(x)$

end for

Update $\mathcal{J}_{k}\leftarrow\mathcal{J}_{k}\cup\\{-k,k\\}$.

Update $\hat{x}^{k}$ according to the incumbent selection rule.

end while

The following theorem due to [25] derives the convergence rate of SD algorithm
for solving SQQP problems.

######  Theorem 5.1.

Suppose that Assumption 5.1 holds and samples used in SD are i.i.d random
variables following the distribution of $\tilde{\xi}$. Let
$\\{\hat{x}_{n}\\}_{n}$ denote the sequence of incumbent solutions generated
by SD. Choose the initial stepsize $\tau>0$ so that $\tau\theta_{\min}(Q)>1$,
where $\theta_{\min}(Q)$ is the smallest eigenvalue of $Q$. Set the sequence
of step sizes of SD to be $\frac{\tau}{n+1}$. Then there exists a constant
$K>0$ such that for large enough $n$, we have

$\mathbb{E}\left[\|\hat{x}_{n}-x^{*}\|\right]\leq\frac{K}{n}.$

###### Proof.

See [25, Theorem 4.9]. ∎

We leave a detailed explanation of the constant $K$ in Appendix E. In short,
the constant $K$ depends on the Lipschitz modulus of the objective function as
well as the Hessians of the first-stage objective and the quadratic pieces of
the second-stage recourse function.
By Markov’s inequality, given $t\in(0,\infty)$, we can further get the
following probabilistic bound from Theorem 5.1:

$\Pr\left\\{\|\hat{x}_{n}-x^{*}\|\geq
t\right\\}\leq\frac{\mathbb{E}[\|\hat{x}_{n}-x^{*}\|]}{t}\leq\frac{K}{tn}.$
(64)

We let $\hat{x}^{j}_{n}$ denote the incumbent decision generated by SD in the
$j^{\text{th}}$ replication and let $\hat{f}^{j}_{n}$ denote the local
approximation of $f_{n}^{j}$ also generated by SD. Let
$L_{f}=\max\limits_{x\in X}\|Qx\|+\|c\|+L_{h}$. Then both $f(x)$ and
$\\{\hat{f}^{i}_{n}\\}_{i}$ are Lipschitiz continuous with a constant $L_{f}$.
Hence, we observe that with probability at least $(1-\frac{K}{tn})$,

$f(\hat{x}_{n})-f(x^{*})\leq L_{f}\|\hat{x}_{n}-x^{*}\|.$ (65)

Combining (64) and (65), we observed that $\hat{x}_{n}$ is a $L_{f}t$-optimal
solution of problem (62) with probability at least $(1-\frac{K}{tn})$.

Compared with cutting-plane-type methods mentioned in section 4, which creates
a global approximation of the SAA objective function in each replication, SD
only creates a local approximation of the counterpart. As a result, the
function augmentation approach proposed in Section 4 is no longer valid here.
Alternatively, we augment the SD’s function approximation by including a lower
bound estimate of the optimal cost of (62). The following explains how we
augment the function estimate by SD. First of all, we pick a tolerance
constant $\epsilon^{\prime}>0$. Then for $i=1,2\ldots,m$, we augment
$\hat{f}^{i}_{n}$ by letting

$\check{f}^{i}_{n}(x)=\max\\{\hat{f}^{i}_{n}(x),\hat{f}^{i}_{n}(\hat{x}^{i}_{n})-\epsilon^{\prime}\\},$
(66)

where $\hat{f}^{i}_{n}(\hat{x}^{i}_{n})-\epsilon^{\prime}$ provides the
estimate of the lower bound of the optimal cost while ensuring the stability
of the later aggregation of the function estimates.
The augmentation of the function estimate ensures that the incumbent solution
from the $i^{\text{th}}$ replication, $\hat{x}^{i}_{n}$, is the
$\epsilon$-optimal solution of the problem $\min_{x\in
X}\check{f}^{i}_{n}(x)$, which further helps bound the later-introduced
pessimistic distance. Note that

$\check{f}^{i}_{n}(x)\geq\hat{f}^{i}_{n}(\hat{x}^{i}_{n})-\epsilon^{\prime},\
\forall x\in X,$

and

$\check{f}^{i}_{n}(\hat{x}^{i}_{n})=\hat{f}^{i}_{n}(\hat{x}^{i}_{n}).$

Hence, we have

$\check{f}^{i}_{n}(\hat{x}^{i}_{n})-\min_{x\in
X}\check{f}^{i}_{n}(x)\leq\epsilon^{\prime}.$ (67)

We introduce the following condition on the estimated solution of (62) as an
intermediate piece to derive the probabilistic bound of the reliability of the
compromise decision. At the end of this section, we will derive the
probability that such an intermediate condition holds.

######  Condition 3 (Intermediate Condition).

Given $t>0$, we have $\|\hat{x}^{j}_{n}-x^{*}\|\leq t,\ \forall
j\in\\{1,\ldots,m\\}$, where $x^{*}$ is the unique optimal solution of problem
(62).

With the incumbent solution and augmented location function approximation of
each replication introduced, we formulate the SD-augmented compromise problem
below:

$\min_{x\in
X}\frac{1}{m}\sum_{i=1}^{m}\check{f}^{i}_{n}(x)+\frac{\rho}{2}\left\|\frac{1}{m}\sum_{j=1}^{m}\hat{x}_{n}^{i}-x\right\|^{2}.$
(68)

We let $\check{X}_{N,\rho,\epsilon}$ denote the $\epsilon$-optimal solution
set of the SD-augmented compromise decision problem (68). The aggregated
problem without the regularizer is written below:

$\min_{x\in X}\frac{1}{m}\sum_{i=1}^{m}\check{f}^{i}_{n}(x).$ (69)

We let $\check{X}_{N,\epsilon}$ denote the $\epsilon$-optimal solution set of
the problem (69).
We start with deriving the upper bound of the pessimistic distance of
$\check{X}_{N,\rho,\epsilon}$ to $X^{*}$.

######  Lemma 5.2.

The following relation holds:

$\Delta(\check{X}_{N,\rho,\epsilon},X^{*})\leq\left\|\frac{1}{m}\sum_{i=1}^{m}\hat{x}_{n}^{i}-x^{*}\right\|+2\sqrt{\epsilon/\rho}+\inf_{x\in\check{X}_{N,\epsilon}}\left\|\frac{1}{m}\sum_{j=1}^{m}\hat{x}_{n}^{i}-x\right\|$

###### Proof.

Since $X^{*}=\\{x^{*}\\}$, we have
$\Delta(\check{X}_{N,\rho,\epsilon},X^{*})=\sup_{x\in\check{X}_{N,\rho,\epsilon}}\|x-x^{*}\|$.
By following the same proof technique of Lemma 3.2 (see Appendix B.5), we can
get

$\left\|\check{x}_{N,\rho,\epsilon}-\frac{1}{m}\sum_{i=1}^{m}\hat{x}_{n}^{i}\right\|\leq\left\|\check{x}_{N,\epsilon}-\frac{1}{m}\sum_{i=1}^{m}\hat{x}_{n}^{i}\right\|+2\sqrt{\epsilon/\rho}.$
(70)

Hence, inequality (70) implies that

$\left\|\check{x}_{N,\rho,\epsilon}-x^{*}\right\|\leq\left\|\check{x}_{N,\epsilon}-\frac{1}{m}\sum_{i=1}^{m}\hat{x}_{n}^{i}\right\|+\left\|\frac{1}{m}\sum_{i=1}^{m}\hat{x}_{n}^{i}-x^{*}\right\|+2\sqrt{\epsilon/\rho}$
(71)

We take the infimum of the right-hand side of (71) over
$\check{x}_{N,\epsilon}\in\check{X}_{N,\epsilon}$, and get

$\|\check{x}_{N,\rho,\epsilon}-x^{*}\|\leq\left\|\frac{1}{m}\sum_{i=1}^{m}\hat{x}_{n}^{i}-x^{*}\right\|+2\sqrt{\epsilon/\rho}+\inf_{x\in\check{x}_{N,\epsilon}}\left\|\frac{1}{m}\sum_{i=1}^{m}\hat{x}_{n}^{i}-x\right\|$
(72)

The final results follow by taking the supremum of the left-hand-side of (72)
over $\check{x}_{N,\rho,\epsilon}\in\check{X}_{N,\rho,\epsilon}$. ∎

By the construction of augmented local function approximation
$\check{f}_{n}^{i}$ in (66), we can derive the upper bound of
$\inf_{x\in\check{X}_{N,\epsilon}}\left\|\frac{1}{m}\sum_{i=1}^{m}\hat{x}^{i}_{n}-x\right\|$.

######  Lemma 5.3.

In the $i^{\text{th}}$ iteration ($i\in\\{1,2,\ldots,m\\}$), let
$\hat{x}^{i}_{n}$ be the incumbent generated by the SD (Algorithm 2). Suppose
that Condition 3 holds. If $\epsilon\leq 2L_{f}t+\epsilon^{\prime}$, then the
following relation holds:

$\inf_{x\in\check{X}_{N,\epsilon}}\left\|\frac{1}{m}\sum_{i=1}^{m}\hat{x}^{i}_{n}-x\right\|\leq\frac{2L_{f}t+\epsilon^{\prime}-\epsilon}{\epsilon}D_{X}$

###### Proof.

This proof consists of two steps. In the first step, we will show that
$\frac{1}{m}\sum_{i=1}^{m}\hat{x}^{i}_{n}$ is a
$(2L_{f}t+\epsilon^{\prime})$-optimal solution of the aggregated problem in
(69). In the second step, we can use Theorem 1.1 to obtain the upper bound of
its associated pessimistic distance.
Here is the detailed proof. By Condition 3, for $j\in\\{1,\ldots,m\\}$, we
have

$\displaystyle\left\|\frac{1}{m}\sum_{i=1}^{m}\hat{x}^{i}_{n}-\hat{x}^{j}_{n}\right\|$
$\displaystyle\leq\frac{1}{m}\sum_{i=1}^{m}\left\|\hat{x}^{i}_{n}-\hat{x}^{j}_{n}\right\|$
$\displaystyle\leq\frac{1}{m}\sum_{i=1}^{m}\left(\|\hat{x}^{i}_{n}-x^{*}\|+\|\hat{x}^{j}_{n}-x^{*}\|\right)$
$\displaystyle\leq 2t,$

which implies that

$\left|\check{f}_{n}^{j}(\frac{1}{m}\sum_{i=1}^{m}\hat{x}^{i}_{n})-\check{f}_{n}^{j}(\hat{x}^{j}_{n})\right|\leq
2L_{f}t.$ (73)

Let $y\in\arg\min\limits_{x\in
X}\frac{1}{m}\sum_{i=1}^{m}\check{f}^{k}_{i}(x)$ and let
$\check{\theta}_{N}=\min_{x\in
X}\frac{1}{m}\sum_{i=1}^{m}\check{f}_{n}^{i}(x)$, then we have

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}\check{f}_{n}^{i}\left(\frac{1}{m}\sum_{j=1}^{m}\hat{x}^{j}_{n}\right)$
$\displaystyle\leq\frac{1}{m}\sum_{i=1}^{m}\check{f}_{n}^{i}(\hat{x}_{n}^{i})+2L_{f}t\quad\text{
by (\ref{eq:lemma:bound 2 of algorithm for compromise sp00})}$ (74)
$\displaystyle\leq\frac{1}{m}\sum_{i=1}^{m}\left[\check{f}_{n}^{i}(\hat{x}_{n}^{i})-\check{f}_{n}^{i}(y)+\check{f}_{n}^{i}(y)\right]+2L_{f}t$
$\displaystyle\leq\check{\theta}_{N}+2L_{f}t+\epsilon^{\prime}\quad\text{ by
(\ref{eq:sd:lower bound})}.$

The inequality above implies that $\frac{1}{m}\sum_{j=1}^{m}\hat{x}^{j}_{n}$
is the $(2L_{f}t+\epsilon^{\prime})$-optimal solution of the problem

$\min\limits_{x\in X}\frac{1}{m}\sum_{i=1}^{m}\check{f}_{n}^{i}(x_{n}^{i}).$

Then the final result follows by Theorem 1.1.∎

In the following theorem below, we aim to derive the lower bound of
probability that Condition 3 holds and provide the probabilistic bound of
$\Delta(\check{X}_{N,\rho,\epsilon},X^{*})\leq\frac{2L_{f}t+\epsilon^{\prime}-\epsilon}{\epsilon}D_{X}+t+2\sqrt{\epsilon/\rho}$.

######  Theorem 5.4.

Suppose that Assumptions 3.2 and 5.1 hold. If $\epsilon\leq
2L_{f}t+\epsilon^{\prime}$, then the following holds:

$\Pr\left\\{\Delta(\check{X}_{N,\rho,\epsilon},X^{*})\leq\frac{2L_{f}t+\epsilon^{\prime}-\epsilon}{\epsilon}D_{X}+t+2\sqrt{\epsilon/\rho}\right\\}\geq\exp\left(-\frac{\frac{mK}{tn}}{1-\frac{K}{tn}}\right)$

###### Proof.

First, we note that $1-y\geq\exp(-\frac{y}{1-y})$ for $0\leq y<1$. By (64),
for $n>\frac{K}{t}$, we first note that

$\displaystyle\Pr\left\\{\|\hat{x}_{n}^{i}-x^{*}\|<t,\ \forall
i\in\\{1,\ldots,m\\}\right\\}$
$\displaystyle\geq\left(1-\frac{K}{tn}\right)^{m}$ (75)
$\displaystyle\geq\exp\left(-\frac{\frac{mK}{tn}}{1-\frac{K}{tn}}\right)$

Given $\|\hat{x}_{n}^{i}-x^{*}\|<t,\ \forall i\in\\{1,\ldots,m\\}$, it follows
from Lemmas 5.2 and 5.3 that,

$\displaystyle\Delta(\check{X}_{N,\rho,\epsilon},X^{*})$
$\displaystyle\leq\inf_{x\in\check{X}_{N,\epsilon}}\left\|\frac{1}{m}\sum_{j=1}^{m}\hat{x}^{j}_{n}-x\right\|+\left\|\frac{1}{m}\sum_{j=1}^{m}\hat{x}^{j}_{n}-x^{*}\right\|+2\sqrt{\epsilon/\rho}$
(76)
$\displaystyle\leq\frac{2L_{f}t+\epsilon^{\prime}-\epsilon}{\epsilon}D_{X}+t+2\sqrt{\epsilon/\rho}$

Thus, the final result follows from combining (75) and (76). ∎

Remark: We observe that there exists some freedom to choose parameters in
Theorem 5.4. We now let $t\in(0,1)$, $\alpha\in(0,3)$,
$\epsilon^{\prime}=L_{f}t$, $\rho=\frac{(3-\alpha)L_{f}}{t}$,
$\epsilon=(3-\alpha)L_{f}t$. Then it follows from Theorem 5.4 that

$\Pr\left\\{\Delta(\check{X}_{N,\rho,\epsilon},X^{*})\leq\frac{\alpha}{3-\alpha}D_{X}+3t\right\\}\geq\exp\left(-\frac{\frac{mK}{tn}}{1-\frac{K}{tn}}\right),$

where $\exp\left(-\frac{\frac{mK}{tn}}{1-\frac{K}{tn}}\right)$ goes to 1 as
$n\rightarrow\infty$.

In the next result, we aim to study the compromise decision’s impact on
variance reduction. We let $d_{n}^{i}=\|\hat{x}^{i}_{n}-x^{*}\|$, for
$i=1,2,\ldots,m$. We start with bounding
$\inf_{x\in\check{X}_{N,\epsilon}}\left\|\frac{1}{m}\sum_{j=1}^{m}\hat{x}^{j}_{n}-x\right\|$
using $d_{n}^{i}$ in the lemma below.

######  Lemma 5.5.

Suppose that Assumptions 3.2 and 5.1 hold. If $\epsilon\leq\epsilon^{\prime}$,
then the following relation holds:

$\inf_{x\in\check{X}_{N,\epsilon}}\left\|\frac{1}{m}\sum_{j=1}^{m}\hat{x}^{j}_{n}-x\right\|\leq\frac{\epsilon^{\prime}-\epsilon+\frac{2L_{f}}{m}\sum_{i=1}^{m}d_{n}^{i}}{\epsilon}D_{X}$

###### Proof.

The proof is similar to Lemma 5.3. We show that
$\frac{1}{m}\sum_{j=1}^{m}\hat{x}^{j}_{n}$ is
$(\epsilon^{\prime}+\frac{2L_{f}}{m}\sum_{i=1}^{m}d_{n}^{i})$-optimal solution
of the problem in (69) and then use Theorem 1.1 to finish the proof. See
Appendix B.10 for the complete proof. ∎

Finally, we conclude this section by providing the upper bounds on the
expectation and variance of the pessimistic distance of
$\check{X}_{N,\rho,\epsilon}$ to $X^{*}$,
$\Delta(\check{X}_{N,\rho,\epsilon},X^{*})$.

######  Theorem 5.6.

Suppose that Assumptions 3.2 and 5.1 holds. Let
$\tau_{3}=\frac{\epsilon^{\prime}-\epsilon}{\epsilon}D_{X}+2\sqrt{\epsilon/\rho}$.
If $\epsilon\leq\epsilon^{\prime}$, then the following hold:

  * 1.

$\mathbb{E}\left[\Delta(\check{X}_{N,\rho,\epsilon},X^{*})\right]\leq\left(1+\frac{2L_{f}D_{X}}{\epsilon}\right)\frac{K}{n}+\tau_{3},$

  * 2.

$\displaystyle\text{Var}\left[\Delta(\check{X}_{N,\rho,\epsilon},X^{*})\right]\leq\left(1+\frac{2L_{f}D_{X}}{\epsilon}\right)^{2}\frac{KD_{X}}{mn}+\left[\left(1+\frac{2L_{f}D_{X}}{\epsilon}\right)\frac{K}{n}+\tau_{3}\right]^{2}.$

  * 3.

Furthermore, let $K_{1}$ be a positive constant. Let
$\epsilon=\epsilon^{\prime}$ and $\rho\geq K_{1}n^{2}$. Then we have

$\mathbb{E}\left[\Delta(\check{X}_{N,\rho,\epsilon},X^{*})\right]=O(\frac{1}{n}),\
\text{Var}\left[\Delta(\check{X}_{N,\rho,\epsilon},X^{*})\right]=O(\frac{1}{mn}+\frac{1}{n^{2}}).$

###### Proof.

Generally speaking, the proof strategy is similar to Theorem 3.7. At first, we
show that the upper bound of the variance of the pessimistic distance,
$\Delta(\check{X}_{N,\rho,\epsilon},X^{*})$, can be expressed as a linear
combination of $d_{n}^{i}$ plus some systematic error. Then we can use the
fact that $d_{n}^{i}$ is independent of $d_{n}^{j}$ given $i\neq j$ by
Assumption 3.2 to decompose the upper bound of the variance of the pessimistic
distance. Finally, we make use of the compactness of the feasible region and
the convergence rate of the first moment of $d_{n}^{i}$ (by Theorem 5.1) to
finish the proof.
Let
$\tau_{3}=\frac{\epsilon^{\prime}-\epsilon}{\epsilon}D_{X}+2\sqrt{\epsilon/\rho}$.
By Lemma 5.5, it follows from Lemma 5.2 that,

$\displaystyle\Delta(\check{X}_{N,\rho,\epsilon},X^{*})$
$\displaystyle\leq\frac{1}{m}\sum_{i=1}^{m}d_{n}^{i}+\frac{\epsilon^{\prime}-\epsilon+\frac{2L_{f}}{m}\sum_{i=1}^{m}d_{n}^{i}}{\epsilon}D_{X}+2\sqrt{\epsilon/\rho}$
(77)
$\displaystyle=\frac{1}{m}\sum_{i=1}^{m}\left(1+\frac{2L_{f}D_{X}}{\epsilon}\right)d_{n}^{i}+\tau_{3}.$

Furthermore, since $d_{n}^{1},d_{n}^{2},\ldots,d_{n}^{m}$ are independent of
each other by Assumption 3.2 and $\tau_{3}$ is a constant, the variance of the
right-hand-side of (77) is

$\displaystyle\text{Var}\left[\frac{1}{m}\sum_{i=1}^{m}(1+\frac{2L_{f}D_{X}}{\epsilon})d_{n}^{i}+\tau_{3}\right]=\sum_{i=1}^{m}\frac{1}{m^{2}}\left(1+\frac{2L_{f}D_{X}}{\epsilon}\right)^{2}\text{Var}[d_{n}^{i}].$
(78)

Since $0\leq d_{n}^{i}\leq D_{X}$, we have
$\mathbb{E}[(d_{n}^{i})^{2}]\leq\mathbb{E}[d_{n}^{i}D_{X}]\leq\frac{KD_{X}}{n}$
for large enough $n$ by Theorem 5.1. This implies that
$\text{Var}[d_{n}^{i}]\leq\mathbb{E}[(d_{n}^{i})^{2}]\leq\frac{KD_{X}}{n}$.
Hence, it follows from (78) that

$\displaystyle\text{Var}\left[\frac{1}{m}\sum_{i=1}^{m}(1+\frac{2L_{f}D_{X}}{\epsilon})d_{n}^{i}+\tau_{3}\right]\leq\left(1+\frac{2L_{f}D_{X}}{\epsilon}\right)^{2}\frac{KD_{X}}{mn}.$
(79)

On the other hand,

$\displaystyle\mathbb{E}\left[\frac{1}{m}\sum_{i=1}^{m}(1+\frac{2L_{f}D_{X}}{\epsilon})d_{n}^{i}+\tau_{3}\right]\leq(1+\frac{2L_{f}D_{X}}{\epsilon})\frac{K}{n}+\tau_{3}$
(80)

Finally, using (26), (79), and (80), we derive the upper bound of the variance
of $\Delta(\check{X}_{N,\rho,\epsilon},X^{*})$ below:

$\displaystyle\text{Var}\left[\Delta(\check{X}_{N,\rho,\epsilon},X^{*})\right]\leq\left(1+\frac{2L_{f}D_{X}}{\epsilon}\right)^{2}\frac{KD_{X}}{mn}+\left[\left(1+\frac{2L_{f}D_{X}}{\epsilon}\right)\frac{K}{n}+\tau_{3}\right]^{2}.$
(81)

Finally, the big $O$ argument follows from direct algebraic derivation based
on (80) and (81). ∎

In Theorem 5.6, the reliability of the compromise decision could be understood
in the following way. The first part of the upper bound (i.e.,
$(1+\frac{2L_{f}D_{X}}{\epsilon})^{2}\frac{KD_{X}}{mn}$) of
$\text{Var}\left[\Delta(\check{X}_{N,\rho,\epsilon},X^{*})\right]$ derives
from the effect of averages of the solution and function estimate. The second
part of the upper bound of the variance is due to the systematic error from
the $\epsilon$-optimal solution and the expected distance of estimated
solution by SD to the optimal solution set. We also observe that smaller
$\epsilon$ is prone to have a more conservative (larger) upper bound on the
variance. That is, smaller $\epsilon$ tends to make the compromise decision
more adapted to the particular realization of the regularized objective in the
Compromise Decision problem.

##  6 Conclusion

In this paper, we have presented a theory of reliability for compromise
decisions in stochastic programming problems under one unifying framework. Our
theoretical findings not only validate the computational observations provided
in [35] and [41], but also extend the previous stopping rule to seeking a non-
dominated solution of an estimated mean-variance problem (61). From a
computational perspective, we suggest using parallel computing to implement
stopping rules which would lead to greater reliability as mentioned in [35].
These developments also underscore the differences between deterministic
optimization and truly large-scale stochastic optimization.
Based on our theory, we also provide some implementable guidance for choosing
the regularization coefficient, $\rho$, and tolerance, $\epsilon$ based on the
sample size, $n$. Let $K_{1}$ be a positive constant. If the “replication”
step involves a cutting-plane-type method, we require that $\rho\geq K_{1}n$,
$\epsilon_{1}=\epsilon$, and $\epsilon_{2}=0$. On the other hand, if the
“replication” step involves SD, we require that $\rho\geq K_{1}n^{2}$ and
$\epsilon=\epsilon^{\prime}$.
There remain several open questions about extensions of the compromise
decision framework. The first open question is whether it is possible to
connect our decision-based regularizer to a class of Distributionally Robust
Optimization (DRO) problems. In connection with this question, we note that a
study of DRO and robust statistics (Blanchet et al. [5]), reveals that
$\phi$-Divergence-Based DRO is related to the variance regularization problem
and optimal transport-based DRO is related to norm regularization of the
fitted parameters. In the context of SP, we observe that our decision-based
regularizer shares some properties which are similar to norm regularization. A
second open question is about how one might reformulate compromise decision
problems for nonconvex SP problems and problems with constraint sets that are
specified by nonlinear equations/inequalities such as those arising in Neural
Networks (NN). The latter have the reputation of being reasonably good on
average, and yet they can be unreliable. Perhaps, a study of reliability of
solutions for non-convex stochastic optimization models will lead to greater
reliability in algorithms for NN. In connection with these directions, one
could also investigate the impact of different regularizers (e.g., kernel
methods [42]) for compromise decisions.

## Acknowledgements

This research originated during the grant FA9550-20-1-0006 from AFOSR, but was
only completed due to a new grant DE-SC0023361 from the ASCR program of the
Department of Energy. We thank both sources for this invaluable support. We
also thank Roger Wets for highlighting the need for reliability of SP
decisions (ICSP conference in Buzios, Brazil, 2016), and his encouragement
since.

##  Appendix A Table of Notations

Notations | Description | Usage
---|---|---
$f_{n}(x;\xi^{n}_{i})$ |  Objective function of SAA problem given sample set $\xi^{n}_{i}$ | Computation and
| Analysis
$x_{n}(\xi^{n}_{i})$ |  Optimal solution of SAA problem given sample set $\xi^{n}_{i}$ | Computation and
| Analysis
$X_{n,\epsilon}(\xi^{n}_{i})$ |  $\epsilon$-optimal solution set of SAA problem given sample set $\xi^{n}_{i}$ | Analysis
$x_{n,\epsilon}(\xi^{n}_{i})$ |  $\epsilon$-optimal solution of SAA problem given sample set $\xi^{n}_{i}$ | Computation and
| Analysis
$\hat{X}_{N,\rho,\epsilon}(\xi^{N})$ |  $\epsilon$-optimal solution of the Compromise Decision problem | Analysis
$\bar{X}_{N,\epsilon}(\xi^{N})$ |  $\epsilon$-optimal solution of the aggregated SAA problem | Analysis
Table 2: Notations in Section 3 Notations | Description | Usage
---|---|---
$\hat{x}_{n}(\xi^{n}_{i})$ | Estimated decision (by a deterministic algorithm) | Computation and
of SAA problem given sample set $\xi^{n}_{i}$ | Analysis
$\hat{f}_{n}(x;\xi^{n}_{i})$ | Piecewise linear approximation | Computation and
of SAA objective function given sample set $\xi^{n}_{i}$ | Analysis
$\nu_{n,\epsilon_{2}}(x;\xi^{n}_{i})$ | $\epsilon_{2}$-subgradient of SAA objective function given sample set $\xi^{n}_{i}$ | Computation and
Analysis
$\hat{f}_{n}(x;\xi^{n}_{i})$ | Augmented piecewise linear approximation | Computation and
of SAA objective function given sample set $\xi^{n}_{i}$ | Analysis
$\hat{X}_{N,\epsilon}(\xi^{N})$ |  $\epsilon$-optimal solution of the problem $\min_{x\in X}\frac{1}{m}\sum_{i=1}^{m}\hat{f}_{n}(x;\xi^{n}_{i})$ | Analysis
$\check{X}_{N,\rho,\epsilon}(\xi^{N})$ |  $\epsilon$-optimal solution of the Compromise Decision problem | Analysis
Table 3: Notations in Section 4 Notations | Description | Usage
---|---|---
$\hat{x}^{i}_{n}$ | Incumbent solution at the $n^{\text{th}}$ iteration | Computation and
of SD in the $i^{\text{th}}$ replication | Analysis
$\hat{f}^{i}_{n}(x)$ | Approximation function at the $n^{\text{th}}$ iteration | Computation and
of SD in the $i^{\text{th}}$ replication | Analysis
$\check{f}^{i}_{n}(x)$ | Augmented approximation function at the $n^{\text{th}}$ iteration | Computation and
of SD in the $i^{\text{th}}$ replication | Analysis
$\check{X}_{N,\rho,\epsilon}$ |  $\epsilon$-optimal solution set of the Compromise Decision Problem | Analysis
$\check{X}_{N,\epsilon}$ |  $\epsilon$-optimal solution set of the problem $\min_{x\in X}\frac{1}{m}\sum_{i=1}^{m}\check{f}^{i}_{n}(x)$ | Analysis
Table 4: Notations in Section 5

##  Appendix B Some Proofs

###  B.1 Proof of Lemma 2.1.

###### Proof.

Let $\bar{A}$ be the symmetric hull of $A$, i.e., $\bar{A}=A\cup\\{-a:a\in
A\\}$. Then $|\bar{A}|\leq 2|A|=2N$ and $\max_{a\in
A}\|a\|^{2}=\max_{a\in\bar{A}}\|a\|^{2}$. Furthermore,

$\displaystyle\max_{a\in
A}\frac{1}{n}\left|\sum_{i=1}^{n}\tilde{\sigma}_{i}a_{i}\right|$
$\displaystyle\leq\max_{a\in\bar{A}}\frac{1}{n}\left|\sum_{i=1}^{n}\tilde{\sigma}_{i}a_{i}\right|$
$\displaystyle(A\subset\bar{A})$ (82)
$\displaystyle=\max_{a\in\bar{A}}\frac{1}{n}\sum_{i=1}^{n}\tilde{\sigma}_{i}a_{i}$
$\displaystyle(\bar{A}\text{ is symmetric})$

By taking the expectation over $\tilde{\sigma}_{1},\ldots,\tilde{\sigma}_{n}$
for both sides of (82) and by Definition 2, we have

$R_{n}(A)\leq
R_{n}(\bar{A})=\mathbb{E}_{\tilde{\sigma}}\left[\max_{a\in\bar{A}}\frac{1}{n}\sum_{i=1}^{n}\tilde{\sigma}_{i}a_{i}\right].$
(83)

We claim that the rest of the proof follows from the proof of [6, Theorem 3].
Here is why: for $a\in\bar{A}$ and $s>0$, we have

$\displaystyle\mathbb{E}_{\tilde{\sigma}}\left[\exp{\left(s\frac{1}{n}\sum_{i=1}^{n}\tilde{\sigma}_{i}a_{i}\right)}\right]$
$\displaystyle=\prod_{i=1}^{n}\mathbb{E}_{\tilde{\sigma}}\left[\exp{(s\frac{1}{n}\tilde{\sigma}_{i}a_{i})}\right]$
(by independence of $\\{\sigma_{i}\\}_{i=1}^{n}$) (84)
$\displaystyle\leq\prod_{i=1}^{n}\exp{\left(\frac{s^{2}a_{i}^{2}}{2n^{2}}\right)}$
(by Hoeffding’s inequality)
$\displaystyle=\exp{\left(\frac{s^{2}\|a\|^{2}}{2n^{2}}\right)}.$

Hence,

$\displaystyle\exp{(sR_{n}(A))}$
$\displaystyle\leq\exp{\left(s\mathbb{E}_{\tilde{\sigma}}\left[\sup_{a\in\bar{A}}\frac{1}{n}\sum_{i=1}^{n}\tilde{\sigma}_{i}a_{i}\right]\right)}$
(by 83) (85)
$\displaystyle\leq\mathbb{E}_{\tilde{\sigma}}\left[\exp{\left(s\sup_{a\in\bar{A}}\frac{1}{n}\sum_{i=1}^{n}\tilde{\sigma}_{i}a_{i}\right)}\right]$
(by Jensen’s inequality)
$\displaystyle\leq\sum_{a\in\bar{A}}\mathbb{E}_{\tilde{\sigma}}\left[\exp{(s\frac{1}{n}\sum_{i=1}^{n}\tilde{\sigma}_{i}a_{i})}\right]$
$\displaystyle\leq
2N\max_{a\in\bar{A}}\exp{\left(\frac{s^{2}\|a\|^{2}}{2n^{2}}\right)}$ (by 84)
$\displaystyle=2N\max_{a\in
A}\exp{\left(\frac{s^{2}\|a\|^{2}}{2n^{2}}\right)}$

The last equality of (85) follows because $\bar{A}$ is the symmetric hull of
$A$. Take the logarithm of both sides of (85), we have

$R_{n}(A)\leq\frac{1}{s}\log\left(2N\max_{a\in
A}\exp{\left(\frac{s^{2}\|a\|^{2}}{2n^{2}}\right)}\right)$ (86)

By minimizing the right-hand side of (86) over $s>0$, the final result
follows. ∎

###  B.2 Proof of Lemma 2.3.

###### Proof.

According to Lemma 2.2 and the proof of [11, Lemma B.2], we derive (12).
For any $\lambda\in(0,\frac{1}{2})$, we have

$\displaystyle R_{n}(F,\xi^{n})$
$\displaystyle\leq(L_{F}D^{\gamma}p^{\frac{\gamma}{2}}+M_{F}\sqrt{2(\log
2+\frac{p}{2\gamma}\log n)})/\sqrt{n}$ (87)
$\displaystyle\leq\left(L_{F}D^{\gamma}p^{\frac{\gamma}{2}}+M_{F}\sqrt{2(\log
2)}+M_{F}\sqrt{\frac{p}{\gamma}\log n}\right)/\sqrt{n}$
$\displaystyle\leq\frac{1}{n^{\lambda}}\left(\frac{L_{F}D^{\gamma}p^{\frac{\gamma}{2}}+M_{F}\sqrt{2(\log
2)}}{n^{\frac{1}{2}-\lambda}}+M_{F}p^{1/2}\gamma^{-1/2}\sqrt{\frac{\log{n}}{n^{1-2\lambda}}}\right)$
$\displaystyle\leq\left(L_{F}D^{\gamma}p^{\frac{\gamma}{2}}+M_{F}\sqrt{2(\log
2)}+\frac{M_{F}p^{1/2}}{\sqrt{\gamma(1-2\lambda)e}}\right)\frac{1}{n^{\lambda}}.$

∎

###  B.3 Proof of Lemma 2.4

###### Proof.

Pick $(x_{1},y_{1}),(x_{2},y_{2})\in X\times Y$. Note that both
$(x_{1},y_{1})$ and $(x_{1},y_{1})$ are $(p+1)$-dimensional vectors. For
$\xi\in\Xi$, we have

$\displaystyle|H(x_{1},y_{1},\xi)-H(x_{2},y_{2},\xi)|$ (88)
$\displaystyle=\left|(F(x_{1},\xi)-y_{1})^{2}-(F(x_{2},\xi)-y_{2})^{2}\right|$
$\displaystyle=\left|F(x_{1},\xi)-y_{1}+F(x_{2},\xi)-y_{2}\right|\left|F(x_{1},\xi)-y_{1}-F(x_{2},\xi)+y_{2}\right|$
$\displaystyle\leq
4M_{F}\left(|F(x_{1},\xi)-F(x_{2},\xi)|+|y_{1}-y_{2}|\right)$
$\displaystyle\leq
4M_{F}\left(L_{F}\|x_{1}-x_{2}\|^{\gamma}+|y_{1}-y_{2}|\right)$
$\displaystyle\leq 4M_{F}\left(L_{F}\|x_{1}-x_{2}\|+|y_{1}-y_{2}|\right)$
$\displaystyle\leq
4M_{F}\sqrt{L_{F}^{2}+1}\left\|(x_{1},y_{1})-(x_{2},y_{2})\right\|.$

The last inequality holds because

$\displaystyle(L_{F}^{2}+1)\|(x_{1},y_{1})-(x_{2},y_{2})\|^{2}-\left(L_{F}\|x_{1}-x_{2}\|+|y_{1}-y_{2}|\right)^{2}$
(89)
$\displaystyle=\|x_{1}-x_{2}\|^{2}+L_{F}^{2}(y_{1}-y_{2})^{2}-2L_{F}\|x_{1}-x_{2}\||y_{1}-y_{2}|$
$\displaystyle=\left(\|x_{1}-x_{2}\|-L_{F}|y_{1}-y_{2}|\right)^{2}\geq 0.$

Also note that for $x\in X$ and $y\in Y$, we have

$H(x,y,\xi)=(F(x,\xi)-y)^{2}\leq(2M_{F})^{2}=4M_{F}^{2}.$

By following the same proof strategy as in the first part of Lemma 2.4, we can
prove the rest of the second claim. ∎

###  B.4 Proof of Lemma 2.7

###### Proof.

The proof is similar to the proof of [11, Lemma 3.4]. Note that

$\displaystyle\delta^{h}_{n}(\xi^{n})$ $\displaystyle=\sup_{x\in
X}\left|\frac{1}{n}\sum_{i=1}^{n}H\left(x,\frac{1}{n}\sum_{i=1}^{n}F(x,\xi_{k}),\xi_{i}\right)-\mathbb{E}_{\tilde{\xi}}\left[H\left(x,\mathbb{E}_{\tilde{\xi}}[F(x,\tilde{\xi})],\tilde{\xi}\right)\right]\right|$
$\displaystyle\leq\sup_{x\in
X}\left|\frac{1}{n}\sum_{i=1}^{n}H\left(x,\frac{1}{n}\sum_{k=1}^{n}F(x,\xi_{k}),\xi_{i}\right)-\frac{1}{n}\sum_{i=1}^{n}H(x,\mathbb{E}_{\tilde{\xi}}[F(x,\tilde{\xi})],\xi_{i})\right|$
$\displaystyle\quad+\sup_{x\in
X}\left|\frac{1}{n}\sum_{i=1}^{n}H\left(x,\mathbb{E}_{\tilde{\xi}}[F(x,\tilde{\xi})],\xi_{i}\right)-\mathbb{E}_{\tilde{\xi}}\left[H\left(x,\mathbb{E}_{\tilde{\xi}}[F(x,\tilde{\xi})],\tilde{\xi}\right)\right]\right|$
$\displaystyle\leq\sup_{x\in
X}4M_{F}\left|\frac{1}{n}\sum_{k=1}^{n}F(x,\xi_{k})-\mathbb{E}_{\tilde{\xi}}[F(x,\tilde{\xi})]\right|$
$\displaystyle\quad+\sup_{x\in X,y\in
Y}\left|\frac{1}{n}\sum_{i=1}^{n}H(x,y,\xi_{i})-\mathbb{E}_{\tilde{\xi}}[H(x,y,\tilde{\xi})]\right|$
$\displaystyle=4M_{F}\delta^{f}_{n}(\xi^{n})+\hat{\delta}_{n}(\xi^{n}).$

The second claim follows based on the symmetric argument [6, 11]. ∎

###  B.5 Proof of Lemma 3.2

###### Proof.

By the definitions in (39), (40), and (42), we have

$\bar{f}_{N}\left(\bar{x}_{N,\epsilon}(\xi^{N});\xi^{N}\right)\leq\bar{\theta}_{N}(\xi^{N})+\epsilon\leq\bar{f}_{N}\left(\hat{x}_{N,\rho,\epsilon}(\xi^{N});\xi^{N}\right)+\epsilon,$
(90)

and

$\displaystyle\bar{f}_{N}\left(\hat{x}_{N,\rho,\epsilon}(\xi^{N});\xi^{N}\right)+\frac{\rho}{2}\left\|\hat{x}_{N,\rho,\epsilon}(\xi^{N})-\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})\right\|^{2}-\epsilon$
(91) $\displaystyle\leq\theta_{N,\rho,\epsilon}(\xi^{N})$
$\displaystyle\leq\bar{f}_{N}\left(\bar{x}_{N,\epsilon}(\xi^{N});\xi^{N}\right)+\frac{\rho}{2}\left\|\bar{x}_{N,\epsilon}(\xi^{N})-\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})\right\|^{2}.$

The combination of (90) and (91) implies that

$\displaystyle\bar{f}_{N}\left(\hat{x}_{N,\rho,\epsilon}(\xi^{N});\xi^{N}\right)+\frac{\rho}{2}\left\|\hat{x}_{N,\rho,\epsilon}(\xi^{N})-\frac{1}{m}\sum_{j=1}^{m}\hat{x}_{n,\epsilon}(\xi^{n}_{j})\right\|^{2}-\epsilon$
$\displaystyle\leq\bar{f}_{N}\left(\hat{x}_{N,\rho,\epsilon}(\xi^{N});\xi^{N}\right)+\epsilon+\frac{\rho}{2}\left\|\bar{x}_{N,\epsilon}(\xi^{N})-\frac{1}{m}\sum_{j=1}^{m}\hat{x}_{n,\epsilon}(\xi^{n}_{j})\right\|^{2}.$

This further implies that

$\displaystyle\left\|\hat{x}_{N,\rho,\epsilon}(\xi^{N})-\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})\right\|^{2}$
$\displaystyle\leq\left\|\bar{x}_{N,\epsilon}(\xi^{N})-\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})\right\|^{2}+\frac{4\epsilon}{\rho}$
$\displaystyle\leq\left(\left\|\bar{x}_{N,\epsilon}(\xi^{N})-\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})\right\|+2\sqrt{\epsilon/\rho}\right)^{2}.$

Hence, we have

$\left\|\hat{x}_{N,\rho,\epsilon}(\xi^{N})-\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})\right\|\leq\left\|\bar{x}_{N,\epsilon}(\xi^{N})-\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})\right\|+2\sqrt{\epsilon/\rho}.$
(92)

Finally, by triangular inequality and (92), we have

$\displaystyle\left\|\hat{x}_{N,\rho,\epsilon}(\xi^{N})-x_{\epsilon}^{*}\right\|$
$\displaystyle\leq\left\|\hat{x}_{N,\rho,\epsilon}(\xi^{N})-\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})\right\|+\left\|\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})-x_{\epsilon}^{*}\right\|$
(93)
$\displaystyle\leq\left\|\bar{x}_{N,\epsilon}(\xi^{N})-\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})\right\|+\left\|\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})-x_{\epsilon}^{*}\right\|+2\sqrt{\epsilon/\rho}$

∎

It is worth noting that the proof of Lemma 3.2 does not specify the form of
the approximation function $\bar{f}_{N}(x;\xi^{N})$, which provides certain
flexibility in the later analysis. For instance, $\bar{f}_{N}(x;\xi^{N})$ may
be replaced by its piecewise linear approximation or even some local inexact
approximation function.

###  B.6 Proof of Lemma 3.3

###### Proof.

First, we observe that

$\inf_{x\in
X_{\epsilon}^{*}}\left\|\hat{x}_{N,\rho,\epsilon}(\xi^{N})-x\right\|\leq\left\|\hat{x}_{N,\rho,\epsilon}(\xi^{N})-x_{\epsilon}^{*}\right\|.$

By Lemma 3.2, we have

$\displaystyle\inf_{x\in
X_{\epsilon}^{*}}\left\|\hat{x}_{N,\rho,\epsilon}(\xi^{N})-x\right\|$
$\displaystyle\leq\left\|\hat{x}_{N,\rho,\epsilon}(\xi^{N})-x_{\epsilon}^{*}\right\|$
(94)
$\displaystyle\leq\left\|\bar{x}_{N,\epsilon}(\xi^{N})-\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})\right\|$
$\displaystyle\quad+\left\|\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})-x_{\epsilon}^{*}\right\|+2\sqrt{\epsilon/\rho}.$

Take the supremum of the left-hand side of (94) over
$\hat{x}_{N,\rho,\epsilon}(\xi^{N})\in\hat{X}_{N,\rho,\epsilon}(\xi^{N})$, we
have

$\displaystyle\sup_{x^{\prime}\in\hat{X}_{N,\rho,\epsilon}(\xi^{N})}\inf_{x\in
X_{\epsilon}^{*}}\|x^{\prime}-x\|$ (95)
$\displaystyle\leq\left\|\bar{x}_{N,\epsilon}(\xi^{N})-\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})\right\|+\left\|\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})-x_{\epsilon}^{*}\right\|+2\sqrt{\epsilon/\rho}.$

Note that, by definition in (3),
$\Delta(\hat{X}_{N,\rho,\epsilon}(\xi^{N}),X_{\epsilon}^{*})=\sup_{x^{\prime}\in\hat{X}_{N,\rho,\epsilon}(\xi^{N})}\inf_{x\in
X_{\epsilon}^{*}}\|x^{\prime}-x\|$. Next, by minimizing the right-hand side of
(95) over $x^{*}_{\epsilon}\in X_{\epsilon}^{*}$, we have

$\displaystyle\Delta(\hat{X}_{N,\rho,\epsilon}(\xi^{N}),X_{\epsilon}^{*})$
$\displaystyle\leq\left\|\bar{x}_{N,\epsilon}(\xi^{N})-\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})\right\|$
(96) $\displaystyle\quad+\inf_{x\in
X_{\epsilon}^{*}}\left\|\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})-x\right\|+2\sqrt{\epsilon/\rho}.$

Finally, by taking the infimum of the right-hand side of (96) over
$\bar{x}_{N,\epsilon}(\xi^{N})\in\bar{X}_{N,\epsilon}(\xi^{N})$, we have

$\displaystyle\Delta(\hat{X}_{N,\rho,\epsilon}(\xi^{N}),X_{\epsilon}^{*})$
$\displaystyle\leq\inf_{x\in\bar{X}_{N,\epsilon}(\xi^{N})}\left\|\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})-x\right\|$
$\displaystyle\quad+\inf_{x\in
X_{\epsilon}^{*}}\left\|\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})-x\right\|+2\sqrt{\epsilon/\rho}.$

∎

###  B.7 Proof of Lemma 3.5

###### Proof.

By (29) from the proof of Theorem 3.1, we have

$\theta_{n}(\xi^{n}_{j})-\theta^{*}\leq\delta^{f}_{n}(\xi^{n}_{j}),\
j=1,2,\ldots,m,$

which implies that

$\frac{1}{m}\sum_{j=1}^{m}\theta_{n}(\xi^{n}_{j})\leq\theta^{*}+\frac{1}{m}\sum_{j=1}^{m}\delta^{f}_{n}(\xi^{n}_{j}).$
(97)

By convexity in Assumption 3.1, we also observe that

$\displaystyle
f\left(\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})\right)$
$\displaystyle\leq\frac{1}{m}\sum_{j=1}^{m}f\left(x_{n,\epsilon}(\xi^{n}_{j})\right)$
(98)
$\displaystyle=\frac{1}{m}\sum_{j=1}^{m}f_{n}\left(x_{n,\epsilon}(\xi^{n}_{j});\xi^{n}_{j}\right)+f\left(x_{n,\epsilon}(\xi^{n}_{j})\right)-f_{n}\left(x_{n,\epsilon}(\xi^{n}_{j});\xi^{n}_{j}\right)$
$\displaystyle\leq\frac{1}{m}\sum_{j=1}^{m}\left(\theta_{n}(\xi^{n}_{j})+\epsilon\right)+\frac{1}{m}\sum_{j=1}^{m}\delta^{f}_{n}(\xi^{n}_{j})$
$\displaystyle\leq\theta^{*}+\epsilon+\frac{2}{m}\sum_{j=1}^{m}\delta_{n}^{f}(\xi^{n}_{j}),\quad\text{
by (\ref{eq:lemma:compromise:relation4:01})}.$

Let
$\epsilon^{\prime}=\epsilon+\frac{2}{m}\sum_{j=1}^{m}\delta_{n}^{f}(\xi^{n}_{j})$,
then $\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})\in
X^{*}_{\epsilon^{\prime}}$ (i.e., the average of the estimated decisions
across all the replications is an $\epsilon^{\prime}$-optimal solution of the
true problem). Hence, by Theorem 1.1, we have

$\inf_{x\in
X^{*}_{\epsilon}}\|\frac{1}{m}\sum_{j=1}^{m}x_{n,\epsilon}(\xi^{n}_{j})-x\|\leq\frac{\epsilon^{\prime}-\epsilon}{\epsilon}D_{X}\leq\frac{\frac{2}{m}\sum_{j=1}^{m}\delta^{f}_{n}(\xi^{n}_{j})}{\epsilon}D_{X}.$
(99)

∎

###  B.8 Proof of Lemma 4.1

###### Proof.

By Conditions 1 and 2, we observe that

$f_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j})\leq\theta_{n}(\xi^{n}_{j})+\epsilon_{1}.$

By the inequality in (29) from the proof of Theorem 3.1, we have

$\theta_{n}(\xi^{n}_{j})\leq\theta^{*}+\delta^{f}_{n}(\xi^{n}_{j}).$

Furthermore, by the convexity of $f(x)$ according to Assumption 3.1, we have

$\displaystyle
f\left(\frac{1}{m}\sum_{j=1}^{m}\hat{x}_{n}(\xi^{n}_{j})\right)$
$\displaystyle\leq\frac{1}{m}\sum_{j=1}^{m}f\left(\hat{x}_{n}(\xi^{n}_{j})\right)$
$\displaystyle=\frac{1}{m}\sum_{j=1}^{m}\left(f_{n}\left(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j}\right)+f\left(\hat{x}_{n}(\xi^{n}_{j})\right)-f_{n}\left(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j}\right)\right)$
$\displaystyle\leq\frac{1}{m}\sum_{j=1}^{m}\left(\theta_{n}(\xi^{n}_{j})+\epsilon_{1}+f(\hat{x}_{n}(\xi^{n}_{j}))-f_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j})\right)$
$\displaystyle\leq\theta^{*}+\epsilon_{1}+\frac{2}{m}\sum_{j=1}^{m}\delta^{f}_{n}(\xi^{n}_{j}).$

Let
$\epsilon^{\prime}=\epsilon_{1}+\frac{2}{m}\sum_{j=1}^{m}\delta^{f}_{n}(\xi^{n}_{j})$,
then $\frac{1}{m}\sum_{j=1}^{m}\hat{x}_{n}(\xi^{n}_{j})\in
X^{*}_{\epsilon^{\prime}}$ and $\epsilon^{\prime}>\epsilon$. By Theorem 1.1,
we have

$\inf_{x\in
X^{*}_{\epsilon}}\left\|\frac{1}{m}\sum_{j=1}^{m}\hat{x}_{n}(\xi^{n}_{j})-x\right\|\leq\frac{\epsilon_{1}-\epsilon+\frac{2}{m}\sum_{j=1}^{m}\delta_{n}(\xi^{n}_{j})}{\epsilon}D_{X}.$

∎

###  B.9 Proof of Lemma 4.2

###### Proof.

We let $\hat{x}_{N}(\xi^{N})\in\arg\min\limits_{x\in
X}\frac{1}{m}\sum_{i=1}^{m}\check{f}_{n}(x;\xi^{n}_{i})$. By the convexity of
$\check{f}_{n}^{i}$ infered from Condition 1, we have

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}\check{f}_{n}\left(\frac{1}{m}\sum_{j=1}^{m}\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{i}\right)$
$\displaystyle\leq\frac{1}{m^{2}}\sum_{i=1}^{m}\sum_{j=1}^{m}\check{f}_{n}\left(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{i}\right)$
(100)
$\displaystyle=\frac{1}{m^{2}}\sum_{i=1}^{m}\sum_{j=1}^{m}\Bigg{[}\check{f}_{n}(\hat{x}_{N}(\xi^{N});\xi^{n}_{i})$
$\displaystyle\quad+\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{i})-\check{f}_{n}(\hat{x}_{N}(\xi^{N});\xi^{n}_{i})\Bigg{]}$

For $i\neq j$, we have

$\displaystyle\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{i})=\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j})+\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{i})-\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j}).$

By the definition of $\check{f}_{n}$ in (55) and Condition 1, we have $0\leq
f_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{i})-\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{i})\leq\epsilon_{2}$
and $0\leq
f_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j})-\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j})\leq\epsilon_{2}$.
Since

$\displaystyle\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{i})-f(\hat{x}_{n}(\xi^{n}_{j}))$
$\displaystyle=\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j}),\xi^{n}_{i})-f_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{i})$
$\displaystyle\quad+f_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{i})-f(\hat{x}_{n}(\xi^{n}_{j}))$
$\displaystyle\leq\delta_{n}^{f}(\xi^{n}_{i}),$

and

$\displaystyle
f(\hat{x}_{n}(\xi^{n}_{j}))-\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j})$
$\displaystyle=f(\hat{x}_{n}(\xi^{n}_{j}))-f_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j})$
$\displaystyle\quad+f_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j})-\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j})$
$\displaystyle\leq\epsilon_{2}+\delta_{n}^{f}(\xi^{n}_{j}),$

we have

$\displaystyle\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{i})-\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j})$
$\displaystyle\leq\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{i})-f(\hat{x}_{n}(\xi^{n}_{j}))$
$\displaystyle\quad+f(\hat{x}_{n}(\xi^{n}_{j}))-\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j})$
$\displaystyle\leq\epsilon_{2}+\delta_{n}(\xi^{n}_{i})+\delta_{n}(\xi^{n}_{j}).$

On the other hand, by Condition 2 and the property
$\check{f}_{n}(x;\xi^{n}_{j})\geq\hat{f}_{n}(x;\xi^{n}_{j})$ due to (55), we
have

$\check{f}_{n}\left(\hat{x}_{N}(\xi^{N});\xi^{n}_{j}\right)\geq\min_{x\in
X}\check{f}_{n}(x;\xi^{n}_{j})\geq\min_{x\in
X}\hat{f}_{n}(x;\xi^{n}_{j})=\hat{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j}),$
(101)

which implies that

$\displaystyle\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j})-\check{f}_{n}(\hat{x}_{N}(\xi^{N});\xi^{n}_{j})$
$\displaystyle\leq\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j})-\hat{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j})$
(102a) $\displaystyle\leq
f_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j})-\hat{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j})$
(102b) $\displaystyle\leq\epsilon_{1}.$ (102c)

The inequality in (102a) holds due to (101). The inequality in (102b) holds
because of Condition 1. The inequality in (102c) holds because of Condition 2.
For $i\neq j$, we have

$\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{i})-\check{f}_{n}(\hat{x}_{N}(\xi^{N});\xi^{n}_{j})\leq\epsilon_{1}+\epsilon_{2}+\delta_{n}(\xi^{n}_{i})+\delta_{n}(\xi^{n}_{j}).$

Hence, it follows from (100) that

$\displaystyle\frac{1}{m^{2}}\sum_{i=1}^{m}\sum_{j=1}^{m}\left[\check{f}_{n}(\hat{x}_{N}(\xi^{N});\xi^{n}_{i})+\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{i})-\check{f}_{n}(\hat{x}_{N}(\xi^{N});\xi^{n}_{i})\right]$
$\displaystyle\leq\frac{1}{m}\sum_{i=1}^{m}\check{f}_{n}(\hat{x}_{N}(\xi^{N});\xi^{n}_{i})+\frac{1}{m^{2}}\sum_{j=1}^{m}\left[\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{j})-\check{f}_{n}(\hat{x}_{N}(\xi^{N});\xi^{n}_{j})\right]$
$\displaystyle\quad+\frac{1}{m^{2}}\sum_{\begin{subarray}{c}i,j=1\\\ i\neq
j\end{subarray}}^{m}\left[\check{f}_{n}(\hat{x}_{n}(\xi^{n}_{j});\xi^{n}_{i})-\check{f}_{n}(\hat{x}_{N}(\xi^{N});\xi^{n}_{i})\right]$