# On Monte-Carlo methods in convex stochastic optimization

Daniel Bartl  Department of Mathematics, Vienna University, Austria
<EMAIL_ADDRESS>and  Shahar Mendelson  Mathematical Sciences
Institute, The Australian National University Canberra, Australia
<EMAIL_ADDRESS>
###### Abstract.

We develop a novel procedure for estimating the optimizer of general convex
stochastic optimization problems of the form
$\min_{x\in\mathcal{X}}\mathbf{E}[F(x,\xi)]$, when the given data is a finite
independent sample selected according to $\xi$. The procedure is based on a
median-of-means tournament, and is the first procedure that exhibits the
optimal statistical performance in heavy tailed situations: we recover the
asymptotic rates dictated by the central limit theorem in a non-asymptotic
manner once the sample size exceeds some explicitly computable threshold.
Additionally, our results apply in the high-dimensional setup, as the
threshold sample size exhibits the optimal dependence on the dimension (up to
a logarithmic factor). The general setting allows us to recover recent results
on multivariate mean estimation and linear regression in heavy-tailed
situations and to prove the first sharp, non-asymptotic results for the
portfolio optimization problem.

###### Key words and phrases:

stochastic optimization, sample-path optimization, stochastic counterpart
method, finite sample / non-asymptotic concentration inequality

###### 2010 Mathematics Subject Classification:

90C15,90B50,62J02

###### Contents

  1. 1 Introduction and appetizer
  2. 2 Main results
    1. 2.1 Difficulties caused by non-Gaussian tails
    2. 2.2 What to expect when tails are Gaussian
    3. 2.3 Recovering Gaussian rates without sub-Gaussian tails
    4. 2.4 The procedure
    5. 2.5 Related literature
  3. 3 Applications
    1. 3.1 Multivariate mean estimation
    2. 3.2 Linear regression
    3. 3.3 Ridge regression
    4. 3.4 Portfolio optimization
  4. 4 On the smallest singular value of general random matrix ensembles
  5. 5 Proofs of the main results
    1. 5.1 Estimation error, the quadratic term
    2. 5.2 Estimation error, the multiplier term
    3. 5.3 Prediction error
    4. 5.4 Proof under a deterministic lower bound of the Hessian
  6. 6 Proofs for the portfolio optimization problem
    1. 6.1 The proof of Corollary 3.7
    2. 6.2 The proof of Corollary 2.10
  7. 7 Concluding remarks

##  1\. Introduction and appetizer

_Stochastic optimization_ is widely used as a way of solving certain problems
numerically. It appears in diverse areas of mathematics, with a generic convex
stochastic optimization problem taking the following form: One is given a
random variable $\xi$ whose range is a measurable space $\Xi$, a convex set of
actions $\mathcal{X}\subseteq\mathbb{R}^{d}$, and a function
$F\colon\mathcal{X}\times\Xi\to\mathbb{R}$ that is convex in its first
argument. The objective is to solve the optimization problem

(SO) $\displaystyle\min_{x\in\mathcal{X}}f(x)\quad\text{where}\quad
f(x):=\mathbf{E}[F(x,\xi)].$

In typical situations, however, one does not have access to the function $f$
directly. Rather, the information one is given is the set of values
$F(\cdot,\xi_{i})_{i=1}^{N}$, where $(\xi_{i})_{i=1}^{N}$ is an independent
_sample_ , selected according to $\xi$ and of cardinality $N$. This type of
random data is natural, for example, if the distribution of $\xi$ is not known
and the only possibility is to sample it; or when an exact computation of $f$
is unfeasible and one relies on Monte-Carlo methods to evaluate it instead. We
refer the reader to Shapiro, Dentcheva, and Ruszczyński [35] or to Kim,
Pasupathy, and Henderson [12] for introductions on such aspects of stochastic
optimization.

Regardless of the reason why one uses a random sample, the fundamental
question remains unchanged: to what degree (SO) can be recovered when the
given data is a random sample?

To be more accurate, assume that (SO) admits a unique optimal action
$x^{\ast}$ and denote by $\widehat{x}_{N}^{\ast}$ a candidate for the optimal
action that is selected using some sample-based procedure. Given a prescribed
error $r>0$, one seeks to bound the probability that the _estimation error_
$\|\widehat{x}_{N}^{\ast}-x^{\ast}\|$ or the _prediction error_ / _optimality
gap_ $f(\widehat{x}_{N}^{\ast})-f(x^{\ast})$ exceeds $r$ in terms of the
sample size $N$.

It should be stressed that the norm $\|\cdot\|$ need not be the Euclidean
norm. Rather, the right choice of $\|\cdot\|$ turns out to be a natural
Hilbertian structure endowed by the Hessian of $f$. The reason for that is
clarified in what follows.

The typical approach used to produce $\widehat{x}_{N}^{\ast}$ is called
_sample average approximation_ (SAA) and is denoted in what follows by
$\widehat{x}^{\text{SAA}}_{N}$. The choice is very natural:
$\widehat{x}^{\text{SAA}}_{N}$ is a minimizer of the empirical mean
$\widehat{f}_{N}:=\frac{1}{N}\sum_{i=1}^{N}F(\cdot,\xi_{i})$.

Asymptotic properties of the SAA solution have been thoroughly investigated.
Roughly and inaccurately put, the SAA solution behaves asymptotically as one
would expect based on the central limit theorem. However, as we shall explain
immediately, these asymptotic results can be misleading. In fact, unless one
imposes _highly restrictive integrability assumptions_ , when given a finite
sample the SAA solution behaves poorly: it exhibits drastically weaker rates
than what one may expect based on the asymptotic behaviour.

In contrast to the SAA solution, we propose a _novel procedure_ that aims at
selecting the optimal action when given a finite random sample. This procedure
exhibits the best possible performance regarding the estimation and prediction
errors, and it does so in completely heavy tailed situations. Our results are
based on the methods developed by G. Lugosi and the second named author in
[18, 19, 20].

Before explaining what we mean by “highly restrictive integrability
assumptions” and indicating the very poor behaviour of SAA in their absence,
let us interject with an example of an important convex stochastic
optimization problem. This example will accompany us throughout the article
and will help concretize the results and assumptions of this article.

######  Example 1.1 (Portfolio optimization).

Modern portfolio theory was initiated by Markowitz [21] and is among the
central optimization problems in mathematical finance. Without going into
details, the _portfolio optimization problem_ has three ingredients:

  * •

a $d$-dimensional random vector $X$, which is interpreted as (discounted)
future prices of some stocks/goods;

  * •

a random variable $Y$, which is interpreted as the (random) future payoff;

  * •

a concave, increasing utility function $U\colon\mathbb{R}\to\mathbb{R}$.

We assume that the stocks $X$ are available for buying and selling today at
the prices $\pi$ so that a trading strategy $x\in\mathbb{R}^{d}$ bears the
cost $\langle\pi,x\rangle:=\sum_{i=1}^{d}\pi_{i}x_{i}$ and gives the (random,
future) payoff $\langle X,x\rangle$. After trading according to the strategy
$x$, the investor’s terminal wealth is $Y+\langle X-\pi,x\rangle$ and her goal
is to maximize the expected utility, namely

$\max_{x\in\mathcal{X}}\mathbf{E}\big{[}U\big{(}Y+\langle
X-\pi,x\rangle\big{)}\big{]},$

where $\mathcal{X}\subseteq\mathbb{R}^{d}$ is closed and convex. (For instance
$\mathcal{X}=[0,\infty)^{d}$ corresponds to short-selling constraints.) We
refer, e.g., to Föllmer and Schied [7, Chapter 3] or to Shapiro, Dentcheva,
and Ruszczynski [35, Section 1.4] for a more elaborate introduction to the
portfolio optimization problem.

Setting $F(x,\xi):=\ell(-Y-\langle X-\pi,x\rangle)$ with $\xi:=(X,Y)$ and
$\ell:=-U(-\,\cdot\,)$, the portfolio optimization problem is indeed a special
instance of (SO).

It is important to stress that the portfolio optimization problem highlights
the natural presence of _heavy tails_ : for one, even if the input $X$ is
light-tailed (e.g. Gaussian, as is the case in the Bachelier model), the
composition with the utility function $U$ can render the problem heavy-tailed.
This is particularly true for the exponential utility function
$U=-\exp(-\,\cdot\,)$, which is arguably (among) the most important utility
functions. Additionally, $X$ itself is often heavy tailed; for instance, in
the famous Black-Scholes model $X$ is log-normal.

Before explaining the new procedure, it is worthwhile to outline what is known
on the statistical performance of the sample average approximation method. As
we already mentioned, the vast majority of known results are of an
_asymptotic_ nature. To ease notation we assume here and for the rest of this
section that $\nabla^{2}f(x^{\ast})=\mathrm{Id}$ (recall that $x^{\ast}$ is
the unique minimizer of $f$).

One can show that under suitable regularity and mild integrability
assumptions, $\sqrt{N}(\widehat{x}^{\mathrm{SAA}}_{N}-x^{\ast})$ is
asymptotically a multivariate Gaussian with zero mean and covariance matrix
$\mathrm{\mathbf{C}ov}[\nabla F(x^{\ast},\xi)]$, see e.g. [35, Chapter 5]. In
particular, if we set

$\sigma^{2}:=\lambda_{\max}(\mathrm{\mathbf{C}ov}[\nabla F(x^{\ast},\xi)])$

to be the largest eigenvalue of the covariance matrix of the gradient of $F$
at $x^{\ast}$ and denote by $\|\cdot\|_{2}$ the Euclidean norm, it follows
that

$\displaystyle\mathbf{P}\Big{[}\|\widehat{x}^{\mathrm{SAA}}_{N}-x^{\ast}\|_{2}\geq
r\Big{]}\approx
2\exp\Big{(}-cN\frac{r^{2}}{\sigma^{2}}\Big{)}\quad\text{asymptotically as
}N\to\infty.$

This error rate is often used to calculate the minimal sample size $N$
required to guarantee that the estimation error is below the wanted threshold
$r$ with some prescribed confidence $1-\delta$. However, as we shall explain
in Section 2.1 below, unless (restrictive) integrability assumptions are
imposed, the asymptomatic exponential decay really does hold _only
asymptotically_. Indeed, it may very well be possible that the _non-
asymptotic_ (or, finite sample) rate

$\displaystyle\mathbf{P}\Big{[}\|\widehat{x}^{\mathrm{SAA}}_{N}-x^{\ast}\|_{2}\geq
r\Big{]}\leq\frac{c\sigma^{2}}{Nr^{2}}\quad\text{for all }N\geq 1$

cannot be improved, meaning that the finite sample rate decays linearly in $N$
rather than exponentially.

The meaning of this significant gap between asymptotic and finite sample
behaviour is that the asymptotic estimate is misleading: while it suggests
that $\frac{\sigma^{2}}{r^{2}}\cdot\log(\frac{2}{\delta})$ samples are enough
to guarantee a confidence of $1-\delta$, one actually needs
$\frac{\sigma^{2}}{r^{2}}\cdot\frac{1}{\delta}$ samples. For small values of
$\delta$ this gap in the required sample size is significant.

_Our contribution_ is the following. We construct a procedure that estimates
the optimal action $\widehat{x}_{N}^{\ast}$ — but it is not SAA. Recalling
that $\nabla^{2}f(x^{\ast})=\mathrm{Id}$ throughout this section for
notational simplicity, given a finite sample, the procedure recovers the
optimal Gaussian rate under modest integrability assumptions: for (small)
$r>0$ we have

$\displaystyle\mathbf{P}\Big{[}\|\widehat{x}^{\ast}_{N}-x^{\ast}\|_{2}\geq
r\Big{]}\leq 2\exp\Big{(}-CN\frac{r^{2}}{\sigma^{2}}\Big{)}\quad\text{whenever
}N\geq N_{0}(r),$

where $N_{0}(r)$ can be controlled explicitly and depends only on certain low-
order moments of the random variables involved (see Theorem 2.9 for the
precise statement). As a matter of fact, in typical situations

$N_{0}(r)\lesssim\max\Big{\\{}d\log(d),\frac{\mathrm{trace}(\mathrm{\mathbf{C}ov}[\nabla
F(x^{\ast},\xi)])}{r^{2}}\Big{\\}}.$

It is worthwhile mentioning that the prediction error is one order of
magnitude smaller than the estimation error, namely, for $N\geq N_{0}(r)$

$\mathbf{P}\Big{[}f(\widehat{x}_{N}^{\ast})\geq f(x^{\ast})+r^{2}\Big{]}\leq
2\exp\Big{(}-CN\frac{r^{2}}{\sigma^{2}}\Big{)}.$

Although this is a trivial consequence of the first order condition for
optimality if $\mathcal{X}=\mathbb{R}^{d}$, it is far less obvious if
$\mathcal{X}$ is a proper subset of $\mathbb{R}^{d}$ and $x^{\ast}$ lies on
the boundary of $\mathcal{X}$.

######  Remark 1.2.

While our procedure showcases the possibility of drastically improving the
statistical properties of the SAA, this improvement does not come for free. A
major advantage of SAA is its computational simplicity, and unfortunately, our
procedure is the outcome of a (rather complex) tournament that takes place
between the actions in $\mathcal{X}$. As a result, its computational cost is
quite high (see Section 2.4). Tournament based procedures are used in other
natural statistical problems and there are ongoing attempts to obtain
alternative procedures that maintain the tournament’s optimal statistical
performance in a computationally feasible way—see, for example [6, 11].
Finding procedures that do the same for stochastic optimization is a
worthwhile challenge.

Plan of the article. We begin Section 2 with a detailed explanation of the
devastating effect heavy-tailed random variables can have on SAA; we then
formulate our main result (Theorem 2.9), discuss its application to the
portfolio optimization problem, and survey related literature. Section 3
contains a description of several other applications of our main result. In
Section 4 we lay the groundwork for the proof of Theorem 2.9 by establishing a
high probability lower bound on the smallest singular value of a general
random matrix ensemble (see Theorem 4.4 and Corollary 4.5)—a result that is of
independent interest. This lower bound will be used in Section 5, where we
prove our main result. Proofs related to the portfolio optimization problem
are presented in Section 6. Finally, Section 7 contains two concluding
remarks.

##  2\. Main results

###  2.1. Difficulties caused by non-Gaussian tails

Let us revisit our claim that heavy tails drastically change the statistical
performance of the sample average approximation. As a starting point, consider
the more basic problem of estimating the mean $\mu:=\mathbf{E}[\xi]$ of a one-
dimensional, square integrable random variable $\xi$. It should be noted that
by setting $F(x,\xi):=\frac{1}{2}x^{2}-\xi x$, one-dimensional mean estimation
becomes a stochastic optimization problem.

Following the SAA approach, the corresponding estimator for the mean is
$\widehat{\mu}_{N}:=\frac{1}{N}\sum_{i=1}^{N}\xi_{i}$. The central limit
theorem then guarantees that

(2.1) $\displaystyle\mathbf{P}[|\widehat{\mu}_{N}-\mu|\geq r]\leq
2\exp\Big{(}-N\frac{r^{2}}{2\sigma^{2}}\Big{)}\quad\text{asymptotically as
}N\to\infty,$

where $\sigma^{2}:=\mathrm{\mathbf{V}ar}[\xi]$ denotes the variance of $\xi$.
On the other hand, invoking Markov’s inequality to bound the probability in
(2.1) for finite $N$ only implies that

(2.2) $\displaystyle\mathbf{P}[|\widehat{\mu}_{N}-\mu|\geq
r]\leq\frac{\sigma^{2}}{Nr^{2}}\quad\text{for every }N\geq 1$

and that dictates a much slower rate than the bound obtained in (2.1). It
should be stressed that the weaker bound is not caused by looseness in
Markov’s inequality; in fact, there are examples where (2.2) is sharp (up to a
constant). Indeed, let $r$ and $N$ such that $Nr^{2}\geq 1$, and let $\xi$ be
the symmetric random variable taking the values $\pm Nr$ with probability
$\frac{1}{2(Nr)^{2}}$ and $0$ with probability $1-\frac{1}{(Nr)^{2}}$. Then
$\mu=0$ and $\sigma^{2}=1$. Moreover, given a sample of cardinality $N$, a
straightforward computation shows that there is an absolute constant $C$ such
that the following holds: with probability at least $\frac{C}{Nr^{2}}$,
exactly one of the sample points is nonzero. On that event we clearly have
$|\widehat{\mu}_{N}-\mu|=r$, showing that the estimate in Markov’s inequality
(2.2) is sharp (up to the absolute multiplicative constant $C$).

In order to improve (2.2) one needs to impose a stronger integrability
assumption and, eventually, one can show that (2.1) holds for all $N\geq 1$ if
and only if $\xi$ has sub-Gaussian tails in the sense that
$\mathbf{P}[|\xi-\mathbf{E}[\xi]|\geq t]$ is at most of the order
$\exp(-c\frac{t^{2}}{\sigma^{2}})$ for $t\geq c^{\prime}\sigma$.

At this point, sub-Gaussian tails seem unavoidable if one’s goal is to have
finite sample estimates that match the asymptotic ones (as dictated by the
central limit theorem). There is, however, one important possibility that so
far has been neglected: we are free to come up with an alternative estimator
instead of the empirical average. To explain, at an intuitive level, how this
might be a way out of our predicament, note that the non-optimal performance
of the empirical mean stems from the fact that, in the presence of heavy
tails, some of the observations will have untypically large values. These
observations, while few in numbers, offset the empirical mean from its true
counterpart, and the hope is that getting rid of those outliers would lead to
a better statistical performance. The so-called _median-of-means_ estimator is
a simple yet powerful estimator that does just that. It goes back at least to
Nemirovsky and Yudin [27].

Partition the sample $\\{1,\dots,N\\}=\cup_{j=1}^{n}I_{j}$ into $n$ disjoint
blocks $I_{j}$ of cardinality $m:=3\frac{\sigma^{2}}{r^{2}}$ (w.l.o.g. assume
that $n$ and $m$ are integers). By (2.2), we have that

$\mathbf{P}[|\widehat{\mu}_{I_{j}}-\mu|\geq
r]\leq\frac{1}{3}\quad\text{where}\quad\widehat{\mu}_{I_{j}}:=\frac{1}{m}\sum_{i\in
I_{j}}\xi_{i}$

and a basic Binomial calculation reveals that the probability that the
majority of the $n$ blocks satisfy $|\widehat{\mu}_{I_{j}}-\mu|\geq r$ is of
the order of $\exp(-cn)$. Since $n=N\frac{r^{2}}{3\sigma^{2}}$, we conclude
that

$\mathbf{P}\Big{[}\Big{|}\mathop{\mathrm{median}}_{j=1,\dots,n}\,\widehat{\mu}_{I_{j}}-\mu\Big{|}\geq
r\Big{]}\leq 2\exp\Big{(}-CN\frac{r^{2}}{\sigma^{2}}\Big{)}\quad\text{for all
}N\geq 1.$

In other words, the median-of-means estimator exhibits the best possible
performance (2.1) (up to a multiplicative constant) under the sole assumption
that $\xi$ has a finite second moment.

Appealing as this sounds, it is important to stress that the median is a one-
dimensional object and has no simple vector-valued analogue. In fact, the
question of an optimal multivariate mean estimation procedure, assuming only
that the vector has a finite mean and covariance, remained open until it was
resolved recently in [19]. In contrast, stochastic optimization is a multi-
dimensional problem, and just like multivariate mean estimation, simply
minimizing the functional $\mathop{\mathrm{median}}_{j}\frac{1}{m}\sum_{i\in
I_{j}}F(\cdot,\xi_{i})$ does not lead to an optimal estimator. What has a
better chance of success is the _tournament procedure_ which happens to be a
powerful extension of the idea of median-of-means. We will explain the
procedure in Section 2.4 below.

###  2.2. What to expect when tails are Gaussian

Ignoring for a second the difficulties caused by non-Gaussian tails, let us
explain the kind of result one could hope for in general convex stochastic
optimization problems and how the underlying dimension $d$ enters the picture.
This will serve as our benchmark in what follows.

To that end, consider the case where $F$ is a _quadratic function_ defined on
the whole of $\mathbb{R}^{d}$, that is,

(2.3) $\displaystyle F(x,\xi):=\langle b,x\rangle+\frac{1}{2}\langle
Ax,x\rangle\qquad\text{for }x\in\mathcal{X}:=\mathbb{R}^{d},$

where $b=b(\xi)$ is a $d$-dimensional Gaussian vector with zero mean and
$A=A(\xi)$ is a random positive definite symmetric $(d\times d)$-matrix
specified in what follows. Although this example appears to be very special,
it should not be considered as a toy example: by a second order Taylor
expansion, every convex function is approximately a quadratic function, at
least locally, around the minimizer.

By (2.3), it follows that

$\nabla^{2}f(x^{\ast})=\mathbf{E}[A],\quad\quad\nabla
F(x^{\ast},\xi)=b\quad\text{and}\quad\nabla^{2}F(x^{\ast},\xi)=A,$

and we assume throughout that $\mathbf{E}[A]$ is non-degenerate (i.e.
$\mathbf{E}[A]$ has full rank). Setting
$\|z\|:=\langle\nabla^{2}f(x^{\ast})z,z\rangle^{\frac{1}{2}}$ for
$z\in\mathbb{R}^{d}$ and recalling that $b$ has zero mean, it is evident that
$f=\frac{1}{2}\|\cdot\|^{2}$; thus, the optimal action is given by
$x^{\ast}=0$.

######  Remark 2.1.

To get a clearer picture of this setup, it might help the reader to first
consider the case $\nabla^{2}f(x^{\ast})=\mathrm{Id}$, and then $\|\cdot\|$ is
just the Euclidean norm.

The advantage of using the quadratic function considered here is that the
sample average approximation optimizer has a particularly simple form:
$\widehat{x}_{N}^{\text{SAA}}$ is any element satisfying

(2.4)
$\displaystyle\Big{(}\frac{1}{N}\sum_{i=1}^{N}A_{i}\Big{)}\widehat{x}_{N}^{\text{SAA}}=\frac{1}{N}\sum_{i=1}^{N}b_{i}.$

To explain the statistical behavior of $\widehat{x}_{N}^{\text{SAA}}$, let us
first focus on the gradient and assume for the sake of simplicity that the
_Hessian is deterministic_ , that is, $A=\mathbf{E}[A]$. In that case,
$\nabla^{2}f(x^{\ast})\widehat{x}_{N}^{\text{SAA}}$ is Gaussian with mean
$x^{\ast}=0$ and covariance $\frac{1}{N}\mathrm{\mathbf{C}ov}[\nabla
F(x^{\ast},\xi)]$. A straightforward computation (noting that
$\|\cdot\|=\|\nabla^{2}f(x^{\ast})^{\frac{1}{2}}\cdot\|_{2}$) reveals the
following: for the estimation error
$\|\widehat{x}_{N}^{\text{SAA}}-x^{\ast}\|$ to be smaller than $r$ with
constant probability (say, with probability at least $\frac{1}{2}$), it is
necessary to have a sample size of cardinality larger than $N\geq
N_{\mathrm{G}}(r)$, where

(2.5) $\displaystyle N_{\mathrm{G}}(r)$
$\displaystyle:=\frac{1}{r^{2}}\mathop{\mathrm{trace}}\Big{(}\nabla^{2}f(x^{\ast})^{-1}\cdot\mathrm{\mathbf{C}ov}[\nabla
F(x^{\ast},\xi)]\Big{)}.$

On the other hand, for large $N$, it follows from the concentration of a
Lipschitz function of the Gaussian vector that the probability that the
estimation error exceeds $r$ is of the order
$2\exp(-cN\frac{r^{2}}{\sigma^{2}})$. And the variance parameter is

(2.6) $\displaystyle\sigma^{2}$
$\displaystyle:=\lambda_{\max}\Big{(}\nabla^{2}f(x^{\ast})^{-1}\cdot\mathrm{\mathbf{C}ov}[\nabla
F(x^{\ast},\xi)]\Big{)}.$

To summarize, when the quadratic function has a deterministic Hessian, the
minimal sample size needed to guarantee that the estimation error does not
exceed $r$ with constant probability is $N_{\mathrm{G}}(r)$, whereas the
correct variance parameter (namely $\sigma^{2}$) dictates the high-probability
regime. Note that the latter, of course, matches the variance parameter of
[35, Chapter 5], as stated in Section 1.

In a next step, still within the setting of the quadratic function (2.3), let
us remove the assumption that the Hessian is deterministic. In that case, if
one wishes to make any statement regarding the estimation (or, prediction)
error, the empirical Hessian $\frac{1}{N}\sum_{i=1}^{N}A_{i}$ on the left hand
side of (2.4) must not be degenerate. One can readily verify that, unless some
specific assumptions are made, the empirical Hessian is singular with
probability 1 whenever $N<d$. Thus, $N\geq d$ is another restriction on the
minimal sample size (though, at this point, it is far from obvious that a
sample of size $d$ or proportional to $d$ would suffice to guarantee a non-
degenerate Hessian with, say, constant probability).

Following these observations one can make a very _optimistic guess_ on the
estimate one can hope to obtain: that there exists a procedure
$\widehat{x}^{N}_{\ast}$ such that for

$N\geq\max\\{N_{\mathrm{G}}(r),d\\},$

with probability at least

$1-2\exp\Big{(}-cN\frac{r^{2}}{\sigma^{2}}\Big{)},$

we have that

$\|\widehat{x}_{N}^{\ast}-x^{\ast}\|\leq r.$

######  Remark 2.2.

This is indeed an optimist guess, and is “very gaussian”. The minimal sample
size $\max\\{N_{\mathrm{G}}(r),d\\}$ is the result of rather trivial
obstructions; their removal is necessary if the estimation error is to have
any chance of being smaller than $r$ with _constant_ probability. Furthermore,
the variance term $\sigma^{2}$, which dictates the _high_ probability regime
(for large $N$), is effectively one dimensional: it corresponds to the worst
direction of the gradient (w.r.t. the norm $\|\cdot\|$).

Before we proceed with the main (affirmative) result of this article, let us
conclude this section with a comment regarding the relation between the
estimation error and the prediction error / the optimality gap, in a more
general setup than the simple example we presented previously.

If $\mathcal{X}=\mathbb{R}^{d}$, a Taylor expansion and the first order
condition for optimality of $x^{\ast}$ immediately implies that

$\displaystyle f(x)-f(x^{\ast})$
$\displaystyle=\frac{1}{2}\langle\nabla^{2}f(y)(x-x^{\ast}),x-x^{\ast}\rangle$

where $y$ is some mid-point between $x^{\ast}$ and $x$. In particular, setting
$\|B\|_{\mathrm{op}}:=\sup_{z\in\mathbb{R}^{d}\text{ s.t.\ }\|z\|\leq
1}\langle Bz,z\rangle$ to be the operator norm111 Note that
$\|\cdot\|_{\mathrm{op}}$ is indeed the operator norm from
$(\mathbb{R}^{d},\|\cdot\|)$ to $(\mathbb{R}^{d},\|\cdot\|_{\ast})$, where
$\|\cdot\|_{\ast}$ is the dual norm of $\|\cdot\|$, i.e.
$\|y\|_{\ast}:=\sup_{\|x\|\leq 1}\langle x,y\rangle$.  of a positive semi-
definite $(d\times d)$-matrix $B$, and

(2.7) $\displaystyle c_{\mathrm{H}}:=\sup_{y\in\mathcal{X}\text{ s.t.\
}\|y-x^{\ast}\|<1}\,\,\frac{1}{2}\|\nabla^{2}f(y)\|_{\mathrm{op}}$

it is clear that

$f(x)-f(x^{\ast})\leq c_{\mathrm{H}}r^{2}\quad\text{whenever
}\|x-x^{\ast}\|\leq r$

and $r<1$. Thus, one can make another _highly optimistic guess_ : that there
exists a procedure $\widehat{x}_{N}^{\ast}$ for which the prediction error /
optimality gap is smaller than the estimation error by at least one order of
magnitude.

What makes this guess optimistic (and nontrivial), is that the above argument
crucially relies on the fact that $\mathcal{X}=\mathbb{R}^{d}$; or, more
generally, that $x^{\ast}$ lies in the interior of $\mathcal{X}$. That need
not be the case.

###  2.3. Recovering Gaussian rates without sub-Gaussian tails

This section contains the main result of the article, formulated in Theorem
2.9 below. It provides affirmative answers to the optimistic guesses made in
the previous section (under some mild assumptions, of course). The assumptions
might appear technical at first glance, and to help the reader put them in
context, each assumption will be explained in the case of portfolio
optimization, and in a heuristic manner; the detailed analysis will be
presented in Section 6.

######  Assumption 2.3 (Convexity and coercivity).

The following hold:

  1. (a)

$\mathcal{X}\subseteq\mathbb{R}^{d}$ is closed and convex;

  2. (b)

$x\mapsto F(x,\gamma)$ is convex and twice continuously differentiable222 If
$\mathcal{X}$ is not open, we mean by “continuously differentiable” that there
is a continuous function $\nabla F(\cdot,\gamma)$ such that
$F(y,\gamma)-F(x,\gamma)=\int_{0}^{1}\langle\nabla
F(x+t(y-x),\gamma),y-x\rangle\,dt$. A similar notion holds for $\nabla^{2}F$
for the “twice continuously differentiable”. for every $\gamma\in\Xi$;

  3. (c)

$F(x,\xi)$, and $\nabla^{2}F(x,\xi)$ are integrable and $\nabla F(x,\xi)$ is
square integrable for every $x\in\mathcal{X}$.

Further, there exists an _optimal action_ $x^{\ast}\in\mathcal{X}$ that
satisfies $f(x^{\ast})=\inf_{x\in\mathcal{X}}f(x)$, and the seminorm induced
by the Hessian of $f$ at $x^{\ast}$ given by

$\|z\|:=\langle\nabla^{2}f(x^{\ast})z,z\rangle^{\frac{1}{2}}\quad\text{for
}z\in\mathbb{R}^{d}$

is a true norm (i.e. $\|z\|=0$ implies $z=0$).

######  Remark 2.4.

While $f$ clearly inherits convexity from $F$, it is not clear a priori that
$f$ is twice continuously differentiable (in the same sense as $F$ if
$\mathcal{X}$ is not open). This follows once Assumption 2.7 below is imposed,
as we shall explain in the beginning of Section 5.

Note that the minimizer $x^{\ast}$ in Assumption 2.3 is unique, as $\|\cdot\|$
is a norm. In fact, the latter relates to a standard assumption in stochastic
optimization—the so called _quadratic growth condition_ : that there is a
constant $\kappa>0$ such that

$\displaystyle f(x)\geq f(x^{\ast})+\kappa\|x-x^{\ast}\|_{2}^{2}$

for all $x$ close to $x^{\ast}$. Indeed, denoting
$\tilde{\kappa}:=\lambda_{\min}(\nabla^{2}f(x^{\ast}))$, the smallest
eigenvalue of the Hessian of $f$ at $x^{\ast}$, we have that
$\tilde{\kappa}>0$ whenever $\|\cdot\|$ is true norm. Moreover, a Taylor
expansion shows that the quadratic growth condition holds with constant
$\kappa=\tilde{\kappa}$ for all $x$ in an infinitesimal neighbourhood of
$x^{\ast}$ (or with constant $\kappa=\frac{\tilde{\kappa}}{2}$ in a
sufficiently small neighbourhood). Conversely, at least when $x^{\ast}$ lies
in the interior of $\mathcal{X}$, the quadratic growth condition readily
implies $\tilde{\kappa}\geq\kappa$ and in particular that $\|\cdot\|$ is a
true norm.

> Let us now give an intuitive interpretation of Assumption 2.3 in the context
> of the portfolio optimization example. To ease notation, we shall assume
> that $\pi=\mathbf{E}[X]=0$ and that $\mathrm{\mathbf{C}ov}[X]=\mathrm{Id}$.
> The convexity and differentiability parts of the assumption are clear, and
> it is straightforward to verify that
>
> $\displaystyle\nabla F(x,\xi)$ $\displaystyle=-\ell^{\prime}(-Y-\langle
> X,x\rangle)\cdot X,$ $\displaystyle\nabla^{2}F(x,\xi)$
> $\displaystyle=\ell^{\prime\prime}(-Y-\langle X,x\rangle)\cdot X\otimes X.$
>
> In particular
>
> $\|z\|^{2}=\mathbf{E}[\ell^{\prime\prime}(-Y-\langle
> X,x^{\ast}\rangle)\cdot\langle X,z\rangle^{2}].$
>
> Ignoring the $\ell^{\prime\prime}$-term inside the expectation for the
> moment, this would imply that $\|\cdot\|=\|\cdot\|_{2}$. In general, when
> accounting for the $\ell^{\prime\prime}$-term, a minor integrability
> assumption will be used to guarantee that $\|\cdot\|$ and $\|\cdot\|_{2}$
> are equivalent norms.

In Section 2.2 we argued that unless the Hessian has a specific form, the
empirical Hessian is singular whenever $N\leq d$. However, without further
assumptions, believing that a sample of cardinality $d$ is enough to guarantee
a non-degenerate empirical Hessian (say with constant probability) is too
optimistic—certainly in the general setting we are interested in here.
Degeneracy can happen even in dimension $d=1$: if $\nabla^{2}F(x^{\ast},\xi)$
takes the value $\frac{1}{\varepsilon}$ with probability $\varepsilon>0$ and
is zero otherwise, the endowed norm $\|\cdot\|$ is simply the absolute
value—regardless of the choice of $\varepsilon$. However, with probability
$(1-\varepsilon)^{N}$, all observations in a sample of size $N$ are zero, and
for small $\varepsilon$, e.g. $\varepsilon=\frac{1}{N^{2}}$, that probability
converges to 1 as $N\to\infty$.

As it happens, the following modest integrability assumption on the Hessian
prevents such behavior.

######  Assumption 2.5 (Integrability of the Hessian).

There is a constant $L$ such that

$\mathbf{E}[\langle\nabla^{2}F(x^{\ast},\xi)z,z\rangle^{2}]\leq L$

for every $z\in\mathbb{R}^{d}$ with $\|z\|=1$.

Another way of formulating Assumption 2.5 is in the sense of _norm-
equivalence_ : for every $z\in\mathbb{R}^{d}$, we have that

(2.8)
$\displaystyle\mathbf{E}[\langle\nabla^{2}F(x^{\ast},\xi)z,z\rangle^{2}]^{\frac{1}{4}}\leq
L^{\frac{1}{4}}\cdot\mathbf{E}[\langle\nabla^{2}F(x^{\ast},\xi)z,z\rangle]^{\frac{1}{2}},$

i.e. the $L_{4}$-norm and the $L_{2}$-norm of the forms
$\langle\nabla^{2}F(x^{\ast},\xi)z,z\rangle^{\frac{1}{2}}$ are
equivalent333Note that the reverse inequality to (2.8) is trivially true with
constant $1$, by Hölder’s inequality.. Therefore the constant $L$ pertains to
the worst direction $z\in\mathbb{R}^{d}$ (and not e.g. the average over
different directions). As such, $L$ typically does not depend on the dimension
$d$.

Under Assumption 2.5 one can prove a lower bound on the smallest singular
value of the empirical Hessian whenever $N\gtrsim d\log(d)$.

> To check Assumption 2.5 in the portfolio optimization example, note that
>
>
> $\mathbf{E}[\langle\nabla^{2}F(x^{\ast},\xi)z,z\rangle^{2}]=\mathbf{E}[\ell^{\prime\prime}(-Y-\langle
> X,x^{\ast}\rangle)^{2}\cdot\langle X,z\rangle^{4}].$
>
> Thus, Assumption 2.5 is a simple consequence of Hölder’s inequality and a
> minor integrability condition.

######  Remark 2.6.

Let us stress that Assumption 2.5 is just a tractable way of ensuring that our
argument works; it could be replaced by the more general assumption that
$\nabla^{2}F(x^{\ast},\xi)$ satisfies a so-called _stable lower bound_ , see
Remark 7.2. The stable lower bound and its role in obtaining lower bounds on
the smallest singular values of rather general random matrix ensembles is
described in Theorem 4.4 and in Corollary 4.1.

There is another reason why the minimal sample should be at least a (large
constant) multiple of $d$, namely, because $F$ need not be quadratic. In the
example in Section 2.2 $F$ was a quadratic function, and as a result the
Hessian did not depend on the action $x$. In general, when invoking a second
order Taylor expansion, the Hessian does depend on some mid-point
$x^{\ast}+t(x-x^{\ast})$. At the same time, Assumption 2.5 only takes into
account the Hessian at the optimizer; therefore, some continuity assumption is
needed if one is to control the deviation from quadratic, which is governed by

$\displaystyle\mathcal{E}_{\mathrm{H}}(x):=\sup_{t\in[0,1]}\Big{|}\Big{\langle}\Big{(}\nabla^{2}F(x^{\ast}\\!\\!+\\!t(x\\!-\\!x^{\ast}),\xi)-\nabla^{2}F(x^{\ast},\xi)\Big{)}(x-x^{\ast}),x-x^{\ast}\Big{\rangle}\Big{|}$

for $x\in\mathcal{X}$.

Note that $\mathcal{E}_{\mathrm{H}}(x)$ is likely to be of order
$\|x-x^{\ast}\|^{3}$ under a suitable Lipschitz condition on the Hessian.
Assumption 2.7 is there to ensure that $\mathcal{E}_{\mathrm{H}}(x)$ is
sufficiently small.

######  Assumption 2.7 (Continuity of the Hessian).

There exists a radius $r_{0}\in(0,1)$ such that the following hold.

  1. (a)

There is a Hölder coefficient $\alpha\in(0,1]$ and a measurable function
$K\colon\Xi\to[0,\infty)$ such that $\mathbf{E}[K(\xi)]<\infty$ and for all
$x,y\in\mathcal{X}$ with $\|x-x^{\ast}\|,\|y-x^{\ast}\|\leq r_{0}$, we have
that

$\displaystyle\Big{\|}\nabla^{2}F(x,\xi)-\nabla^{2}F(y,\xi)\Big{\|}_{\mathrm{op}}$
$\displaystyle\leq\|x-y\|^{\alpha}\cdot K(\xi).$

  2. (b)

For some given constant $c_{1}$ (which will be specified in Theorem 2.9 and
depends only on the parameter $L$ of Assumption 2.5) and for all
$x\in\mathcal{X}$ with $\|x-x^{\ast}\|\leq r_{0}$, we have that

$\displaystyle\mathbf{P}\Big{[}\mathcal{E}_{\mathrm{H}}(x)\leq\frac{\|x-x^{\ast}\|^{2}}{8}\Big{]}$
$\displaystyle\geq(1-c_{1}).$

Assumption 2.7 implies that, setting

(2.9) $\displaystyle N_{\mathrm{H},\mathcal{E}}$
$\displaystyle:=\frac{d}{\alpha}\log\Big{(}r_{0}^{\alpha}\mathbf{E}[K(\xi)]+2\Big{)},$

whenever $N\gtrsim N_{\mathrm{H},\mathcal{E}}$, the error caused by replacing
$F$ by its quadratic approximation does not distort the outcome by too much.

######  Remark 2.8.

At a first glance it might seem as if part (b) of Assumption 2.7 follows from
part (a). It is true that
$\mathcal{E}_{\mathrm{H}}(x)\leq\|x-x^{\ast}\|^{2+\alpha}\cdot K(\xi)$, but
there is one important difference: in typical situations,
$\mathcal{E}_{\mathrm{H}}$ does not depend on the dimension $d$, while $K$
does (we shall see this phenomenon in the portfolio optimization problem). In
particular, estimating $\mathcal{E}_{\mathrm{H}}$ using $K(\xi)$ will
unnecessarily force the threshold radius $r_{0}$ to depend on the dimension,
which is something we wish to avoid. On the other hand, the dimension-
dependent term $\mathbf{E}[K(\xi)]$ only appears through a logarithmic factor
in the minimal sample size.

> Returning to the portfolio optimization problem, let us, for the sake of a
> simplified exposition, pretend that $\ell^{\prime\prime}$ is $1$-Lipschitz
> continuous, and recall that $\|\cdot\|_{2}$ and $\|\cdot\|$ are equivalent
> norms. Then
>
> (2.10)
> $\displaystyle\begin{split}&\big{|}\big{\langle}(\nabla^{2}F(x,\xi)-\nabla^{2}F(y,\xi))z,z\big{\rangle}\big{|}\\\
> &=|\ell^{\prime\prime}(-Y-\langle X,x\rangle)-\ell^{\prime\prime}(-Y-\langle
> X,y\rangle)|\cdot\langle X,z\rangle^{2}\\\ &\leq|\langle
> X,x-y\rangle|\cdot\langle X,z\rangle^{2}.\end{split}$
>
> Thus $\mathcal{E}_{\mathrm{H}}(x)\leq|\langle X,x-x^{\ast}\rangle|^{3}$ and,
> under some mild integrability assumption, the latter term behaves like
> $\|x-x^{\ast}\|_{2}^{3}$ on average. Markov’s inequality and the fact that
> $\|\cdot\|$ and $\|\cdot\|_{2}$ are equivalent norms imply that
>
>
> $\mathbf{P}\Big{[}\mathcal{E}_{\mathrm{H}}(x)>\frac{1}{8}\|x-x^{\ast}\|^{2}\Big{]}\leq\frac{8\mathbf{E}[\mathcal{E}_{\mathrm{H}}(x)]}{\|x-x^{\ast}\|^{2}}\leq\frac{c8\mathbf{E}[\mathcal{E}_{\mathrm{H}}(x)]}{\|x-x^{\ast}\|_{2}^{2}}$
>
> is of order $\|x-x^{\ast}\|_{2}$.
>
> On the other hand, (2.10) implies that
>
> $\|\nabla^{2}F(x,\xi)-\nabla^{2}F(y,\xi)\|_{\mathrm{op}}\leq
> K(\xi)\cdot\|x-y\|_{2},$
>
> for $K(\xi):=\|X\|_{2}^{3}$ which typically scales like $d^{\frac{3}{2}}$.

With all the definitions set in place let us turn to the formulation of our
main result. Recall that $N_{\mathrm{G}}(r)$, $\sigma^{2}$, $c_{\mathrm{H}}$,
and $N_{\mathrm{H},\mathcal{E}}$ were defined in (2.5), (2.6), (2.7), and
(2.9) respectively.

######  Theorem 2.9 (Estimation and prediction error).

There are constants $c_{1},c_{2},c_{3}$ depending only on $L$ such that the
following holds. Assume that Assumptions 2.3, 2.5, 2.7 hold, let
$r\in(0,r_{0})$ and consider

$N\geq c_{2}\max\\{d\log(2d),N_{\mathrm{H},\mathcal{E}},N_{\mathrm{G}}(r)\\}.$

Then there is a procedure $\widehat{x}_{N}^{\ast}$ such that, with probability
at least

$1-2\exp\Big{(}-c_{3}N\min\Big{\\{}1,\frac{r^{2}}{\sigma^{2}}\Big{\\}}\Big{)},$

we have that

$\displaystyle\|\widehat{x}_{N}^{\ast}-x^{\ast}\|$ $\displaystyle\leq r,$
$\displaystyle\ f(\widehat{x}_{N}^{\ast})$ $\displaystyle\leq
f(x^{\ast})+2c_{\mathrm{H}}\cdot r^{2}.$

The procedure is described in Section 2.4.

Theorem 2.9 implies that our procedure recovers (up to multiplicative
constants) the optimal asymptotic rates for the sample average approximation
[35, Chapter 5] in a non-asymptotic fashion and when the random variables
involved can be heavy tailed.

> To complete the heuristics pertaining to the portfolio optimization problem,
> one has to compute $N_{\mathrm{G}}(r),\sigma^{2}$ and $c_{\mathrm{H}}$.
> Again, for the sake of simplicity we shall ignore $\ell^{\prime}$ and
> $\ell^{\prime\prime}$ at every appearance (keeping in mind that some minor
> integrability assumptions guarantee that this simplification does not shift
> the results by too much from the truth).
>
> In this case, $\mathrm{\mathbf{C}ov}[\nabla F(x^{\ast},\xi)]=\mathrm{Id}$
> and $\nabla^{2}f(x^{\ast})=\mathrm{Id}$, and in particular
>
> $\sigma^{2}=\lambda_{\max}(\mathrm{Id})=1\ \ \text{and}\ \
> N_{\mathrm{G}}(r)=\frac{\mathrm{trace}(\mathrm{Id})}{r^{2}}=\frac{d}{r^{2}}.$
>
> Moreover, ignoring $\ell^{\prime\prime}$ also clearly implies that
> $c_{\mathrm{H}}=1$.

In Corollary 3.7 we specify all the assumptions that are needed to make this
heuristic argument hold; but for now let us state a particularly simple case
which is of interest in its own right: the exponential portfolio optimization
in the Bachelier model.

Recall that in this model $U(\cdot)=-\exp(-\,\cdot)$ is the exponential
utility function and $X$ is zero-mean Gaussian. We assume that the covariance
matrix of $X$ is non-degenerate and that both $Y$ and $U(2Y)$ are integrable.
Under these assumptions, we shall see that there exists a unique optimal
action $x^{\ast}\in\mathcal{X}$. Set

$\displaystyle\bar{\sigma}^{2}$
$\displaystyle:=\mathbf{E}\big{[}\exp(-Y-\langle
X,x^{\ast}\rangle)^{2}\big{]}^{\frac{1}{2}},$

and assume that Assumption 2.5 holds true. While the latter assumption can be
verified via some integrability conditions (we shall see this in context of
the general portfolio optimization problem in Lemma 6.2), the obtained bounds
may fail to be sharp. To showcase that Assumption 2.5 can sometimes be easily
verified by other means, consider for a moment $Y=\langle
X,\tilde{x}\rangle+W$ for some $\tilde{x}\in\mathcal{X}$ and $W$ that is
independent of $X$. Then $x^{\ast}=\tilde{x}$ and Gaussian norm equivalence
(i.e. there is an absolute constant $C$ such that $\mathbf{E}[\langle
X,z\rangle^{4}]^{\frac{1}{4}}\leq C\mathbf{E}[\langle
X,z\rangle^{2}]^{\frac{1}{2}}$ for every $z\in\mathbb{R}^{d}$) together with
independence of $X$ and $W$ readily implies that Assumption 2.5 is satisfied
with

$L=\frac{C^{4}\mathbf{E}[\exp(W)^{2}]}{\mathbf{E}[\exp(W)]^{2}}.$

######  Corollary 2.10 (Exponential portfolio optimization).

Under the above assumptions, there are constants $c_{1},c_{2},c_{3},c_{4}>0$
depending only on $L$ and $\mathbf{E}[|Y+\langle X,x^{\ast}\rangle|]$ such
that the following holds. For
$r\in(0,\min\\{1,\frac{c_{1}}{\bar{\sigma}^{2}}\\})$ and

$N\geq
c_{2}\max\Big{\\{}\frac{d\bar{\sigma}^{2}}{r^{2}},\,d^{\frac{3}{2}}\,\Big{\\}},$

there is a procedure $\widehat{x}_{N}^{\ast}$ such that, with probability at
least

$1-2\exp\Big{(}-c_{3}N\min\Big{\\{}1,\frac{r^{2}}{\bar{\sigma}^{2}}\Big{\\}}\Big{)},$

we have that

$\displaystyle\|\widehat{x}_{N}^{\ast}-x^{\ast}\|$ $\displaystyle\leq r,$
$\displaystyle u(\widehat{x}_{N}^{\ast})$ $\displaystyle\geq
u(x^{\ast})-c_{4}r^{2}.$

######  Remark 2.11.

The origin of the (somewhat unfamiliar) term $d^{\frac{3}{2}}$ appearing in
the minimal sample size in Corollary 2.10 is $N_{\mathrm{H},\mathcal{E}}$.
However, as our previous heuristics indicate, that term should be of order
$d\log(d)$.

As it happens, the source of this difference is the exponential utility
function. Indeed, the heuristic presentation was based on a simplifying
assumption: that $\ell^{\prime\prime\prime}$ was bounded by 1. That allowed us
to conclude that $\mathbf{E}[K(\xi)]$ was of the order $d^{3}$, resulting in
$N_{\mathrm{H},\mathcal{E}}$ of order $d\log(d^{3})=3d\log(d)$. Here, however,
$\ell^{\prime\prime\prime}$ is the exponential function; the term
$\mathbf{E}[K(\xi)]$ is actually of order $\exp(\sqrt{d})$ resulting in
$N_{\mathrm{H},\mathcal{E}}$ that is of order
$d\log(\exp(\sqrt{d}))=d^{\frac{3}{2}}$.

It should be stressed that although the term $d^{\frac{3}{2}}$ in the minimal
sample size of Corollary 2.10 could be off by a factor of $\sqrt{d}$,
Corollary 2.10 is, to the best of our knowledge, the first non-asymptotic
estimate for the exponential portfolio optimization problem.

In some of the examples we will present later, the Hessian additionally
satisfies a deterministic lower bound:

######  Assumption 2.12 (Deterministic lower bound of the Hessian).

There is $r_{0}\in(0,1)$ and $\varepsilon>0$ such that

$\nabla^{2}F(x,\xi)\succeq\varepsilon\nabla^{2}f(x^{\ast})$

for all $x\in\mathcal{X}$ with $\|x-x^{\ast}\|\leq r_{0}$.

Moreover, $\nabla f(x)=\mathbf{E}[\nabla F(x,\xi)]$ and
$\nabla^{2}f(x)=\mathbf{E}[\nabla^{2}F(x,\xi)]$ for all $x\in\mathcal{X}$ with
$\|x-x^{\ast}\|<r_{0}$.

When Assumption 2.12 holds true, the two Assumptions 2.5 and 2.7 that were
imposed to control the smallest singular value of the Hessian are not needed,
and Theorem 2.9 can be simplified as follows.

######  Theorem 2.13 (Estimation and prediction error, simplified).

There are constants $c_{1},c_{2}$ depending only on $\varepsilon$ such that
the following holds. Assume that Assumptions 2.3 and 2.12 hold, let
$r\in(0,r_{0})$, and consider

$N\geq c_{1}N_{\mathrm{G}}(r).$

Then there is a procedure $\widehat{x}_{N}^{\ast}$ such that, with probability
at least

$1-2\exp\Big{(}-c_{2}N\min\Big{\\{}1,\frac{r^{2}}{\sigma^{2}}\Big{\\}}\Big{)},$

we have that

$\displaystyle\|\widehat{x}_{N}^{\ast}-x^{\ast}\|$ $\displaystyle\leq r,$
$\displaystyle\ f(\widehat{x}_{N}^{\ast})$ $\displaystyle\leq
f(x^{\ast})+2c_{\mathrm{H}}\cdot r^{2}.$

Before presenting the procedure $\widehat{x}_{N}^{\ast}$ in detail, let us
compare the outcome of Theorem 2.9 with the current state of the art. Our
focus is on recent non-asymptotic results by Oliveira and Thompson [28, 29]; a
general literature review will be presented in Section 2.5.

For a clearer comparison, let us restate Theorem 2.9 (pertaining to the
prediction error) as follows:

given some fixed confidence level $\delta\in(0,1)$, small $r>0$, and

$N\geq c_{2}\max\\{d\log(2d),N_{\mathrm{H},\mathcal{E}},N_{\mathrm{G}}(r)\\},$

the prediction error is bounded by $r^{2}$ with probability at least
$1-\delta$, whenever the sample $N$ satisfies

(2.11) $\displaystyle
N\gtrsim\frac{\sigma^{2}}{r^{2}}\log\Big{(}\frac{2}{\delta}\Big{)}$

In contrast, the main result of Oliveira and Thompson [29, Theorem 3]
regarding general convex stochastic optimization problems is the following.
There is a random variable $\widehat{\Sigma}_{N}$ (which we shall not define
here) that satisfies

$\widehat{\Sigma}_{N}^{2}\gtrsim d\cdot\Big{(}\mathbf{E}[\|\nabla
F(x^{\ast},\xi)\|^{2}]+\frac{1}{N}\sum_{i=1}^{N}\|\nabla
F(x^{\ast},\xi_{i})\|^{2}\Big{)}$

and in order to guarantee that the prediction error is bounded by $r^{2}$ with
probability at least $1-\delta$ one should have

(2.12)
$\mathbf{P}\Big{[}N\geq\frac{\widehat{\Sigma}_{N}^{2}}{r^{2}}\log\Big{(}\frac{2}{\delta}\Big{)}\Big{]}\geq
1-\delta.$

There are two _major_ differences between these two results. The first one,
which should not come as a great surprise following the discussion in Section
2.1, is that $\widehat{\Sigma}_{N}^{2}$ does not concentrate around its mean
with high probability in heavy tailed situations. Thus, (2.12) forces $N$ to
grow like $(\frac{1}{\delta})^{\frac{1}{p}}$ for some power $p>1$ depending on
the integrability of $\|\nabla F(x^{\ast},\xi)\|$. For small $\delta$ (i.e. if
one is interested in high confidence) this is in stark contrast to the order
$\log(\frac{1}{\delta})$ in (2.11). The second difference is the dependence of
$\widehat{\Sigma}_{N}^{2}$ on the dimension $d$. Indeed, even if we neglect
the integrability issues and replace $\widehat{\Sigma}_{N}^{2}$ by its mean,
what we end up with is not the correct variance parameter (which appears in
the central limit theorem). For instance, if $\|\cdot\|$ is the Euclidean
norm, then

$\widehat{\Sigma}_{N}^{2}\gtrsim
d\cdot\mathrm{trace}(\mathrm{\mathbf{C}ov}[\nabla F(x^{\ast},\xi)]),$

which is at least $d$ times (possibly even $d^{2}$ times) larger than the true
variance parameter $\sigma^{2}=\lambda_{\max}(\mathrm{\mathbf{C}ov}[\nabla
F(x^{\ast},\xi)])$. In high-dimensional problems such as the portfolio
optimization problem, where $d$ is the number of stocks and is likely to be a
large number, this difference is significant. As a result, even for moderate
confidence levels $\delta$, the required sample size jumps up by a factor of
$d$ (or even $d^{2}$) from what we would expect.

###  2.4. The procedure

As we already explained previously, to have any hope of optimal performance,
the procedure $\widehat{x}_{N}^{\ast}$ _cannot_ be the sample average
approximation. Instead, $\widehat{x}_{N}^{\ast}$ will be determined through
median-of-mean tournaments conducted between all $x\in\mathcal{X}$, following
the method introduced in [20].

The first phase of the procedure returns a set of candidates, each with a
small estimation error.

  1. (Step 1)

For some (small) tuning parameter $\theta$ to be specified later, set

$n:=\theta
N\min\Big{\\{}1,\frac{r^{2}}{\sigma^{2}}\Big{\\}}\quad\text{and}\quad
m:=\frac{N}{n}.$

Without loss of generality assume that $m$ and $n$ are integers. Partition

$\\{1,\dots,N\\}=\bigcup_{j=1}^{n}I_{j}$

into $n$ disjoint blocks $I_{j}$, each of equal cardinality $|I_{j}|=m$.

  2. (Step 2)

For every $x\in\mathcal{X}$, compute the empirical mean of $F(x,\xi)$ on the
$j$-th block

$\widehat{f}_{I_{j}}(x):=\frac{1}{m}\sum_{i\in I_{j}}F(x,\xi_{i}).$

We then say that $x\in\mathcal{X}$ _defeats_ $y\in\mathcal{X}$ _on the $j$-th
block_ if $\widehat{f}_{I_{j}}(x)<\widehat{f}_{I_{j}}(y)$, and that $x$ _wins
the match against_ $y$ if

$\widehat{f}_{I_{j}}(x)<\widehat{f}_{I_{j}}(y)\quad\text{on more than
}\frac{n}{2}\text{ blocks}\ j,$

i.e. if $x$ defeats $y$ on a majority of the blocks.

Denote by $\tilde{\mathcal{X}}_{N}^{\ast}\subseteq\mathcal{X}$ the set of
_champions_ , i.e.

$\tilde{\mathcal{X}}_{N}^{\ast}:=\Big{\\{}x\in\mathcal{X}:\begin{array}[]{l}x\text{
wins the match against every}\\\ y\in\mathcal{X}\text{ that satisfies
}\|x-y\|\geq r\end{array}\Big{\\}}.$

The following proposition shows that elements in
$\tilde{\mathcal{X}}_{N}^{\ast}$ satisfy the part of Theorem 2.9 pertaining to
the estimation error.

######  Proposition 2.14 (Estimation error).

In the setting of Theorem 2.9, with probability at least $1-2\exp(-c_{3}n)$,
we have that $x^{\ast}\in\tilde{\mathcal{X}}_{N}^{\ast}$ and every
$x\in\tilde{\mathcal{X}}_{N}^{\ast}$ satisfies $\|x-x^{\ast}\|\leq r$.

As we already explained, if $\mathcal{X}=\mathbb{R}^{d}$ or, more generally,
if $x^{\ast}$ lies in the interior of $\mathcal{X}$, the first order condition
for optimality immediately implies that $f(x)\leq
f(x^{\ast})+c_{\mathrm{H}}r^{2}$ for every $x\in\mathcal{X}$ with
$\|x-x^{\ast}\|\leq r$. In particular, in that case, it follows from
Proposition 2.14 that any choice
$\widehat{x}_{N}^{\ast}\in\tilde{\mathcal{X}}_{N}^{\ast}$ satisfies the
assertion of Theorem 2.9.

However, in general, if one wishes to find
$x\in\tilde{\mathcal{X}}_{N}^{\ast}$ with a small prediction error, one
requires an additional procedure, which we describe now.

To simplify notation, assume without loss of generality that the set
$\tilde{\mathcal{X}}_{N}^{\ast}$ has already been determined, and that we can
run an additional second procedure, for which we are given a new (independent)
sample $F(\cdot,\xi_{i})_{i=N+1}^{2N}$.

Again partition $\\{N+1,\dots,2N\\}$ into $n$ disjoint blocks $I_{j}^{\prime}$
of cardinality $|I_{j}^{\prime}|=m$ with the same $n$ and $m$, and denote by
$\widehat{f}_{I_{j}^{\prime}}(\cdot)$ the empirical mean on the block
$I_{j}^{\prime}$.

  1. (Step 3)

We say that $x\in\mathcal{X}$ _wins its home match_ against $y\in\mathcal{X}$
if

$\widehat{f}_{I_{j}^{\prime}}(x)\leq\widehat{f}_{I_{j}^{\prime}}(y)+\frac{c_{\mathrm{H}}r^{2}}{4}\quad\text{
on more than }\frac{n}{2}\text{ blocks }j.$

Denote by $\widehat{\mathcal{X}}_{N}^{\ast}$ the _winners_ , i.e.,

$\widehat{\mathcal{X}}_{N}^{\ast}:=\Big{\\{}x\in\tilde{\mathcal{X}}_{N}^{\ast}:\begin{array}[]{l}x\text{
wins its home match }\\\ \text{against every
}y\in\tilde{\mathcal{X}}_{N}^{\ast}\end{array}\Big{\\}}.$

In light of Proposition 2.14, the crucial advantage here is that, with high
probability, matches are only carried out between competitors that are close
to $x^{\ast}$. The following proposition shows that any
$\widehat{x}_{N}^{\ast}\in\widehat{\mathcal{X}}_{N}^{\ast}$ satisfies the
requirements in Theorem 2.9:

######  Proposition 2.15 (Prediction error).

In the setting of Theorem 2.9, with probability at least $1-2\exp(-c_{3}n)$,
we have that $x^{\ast}\in\widehat{\mathcal{X}}_{N}^{\ast}$ and every
$x\in\widehat{\mathcal{X}}_{N}^{\ast}$ satisfies
$f(x)<f(x^{\ast})+2c_{\mathrm{H}}r^{2}$.

###  2.5. Related literature

Stochastic optimization and the statistical properties of the sample average
approximation method have been studied intensively for several decades; it is
therefore impossible to mention every single contribution. Instead, we refer
to Kim, Pasupathy, and Henderson [12], Shapiro, Dentcheva, and Ruszczyński
[35], Kleywegt, Shapiro, Homem-de-Mello [13], Shapiro [34], or Homem-de-Mello
and Bayraksan [10]. As we already mentioned, the statistical analysis in these
works is always of asymptotic nature. Let us also refer to Banholzer, Fliege,
and Werner [2] for a recent study of asymptotic almost sure convergence rates
and an up-to date review on the asymptotic convergence analysis, and to
Bertsimas, Gupta, and Kallus [4] who raise concerns that most statistical
results for sample average approximation are of asymptotic nature.

Shifting to a non-asymptotic analysis of the performance of the SAA, the
available literature gets considerably less diverse. An early reference here
is Pflug [30, 31], who relies on Talagrand’s deviation inequality for the
supremum of Gaussian processes (which is obviously suitable only in very
special, light-tailed scenarios). Similar methods were adapted by Römisch [32]
and Vogel [41] and (for the error of the value—i.e.
$\min_{x\in\mathcal{X}}f(x)$) by Guigues, Juditsky, and Nemirovski in [9]. The
two recent papers by Oliveira and Thompson [28, 29] which have been mentioned
at the end of Section 2 contain results that are closest to ours.

The portfolio optimization problem is often listed as a prime example of a
stochastic optimization problem, see e.g. [35, Section 1.4]. As such, and with
the exception of perhaps more applied studies like [8, 42, 44], existing
estimates on the problem have been derived as applications of general
results—much like in our work.

There are other (optimization) problems in mathematical finance that have been
analyzed via sampling, such as the estimation of risk measures. We refer the
reader to Weber [43] (which relies on large deviation methods) for an early
reference and to [3] for a more recent review. We believe that our methods can
be applied to those type of problems as well, and defer it to future work.

We should mention that the statistical analysis of the SAA has close ties to
the statistical analysis of problems in high-dimensional statistics, such as
linear regression. But despite obvious similarities, the two fields have grown
adrift. The current focus in statistical learning literature is on non-
asymptotic statements that hold under increasingly relaxed assumptions. Among
the outcomes of this approach were [20, 23, 24]—alternatives to the sample
average approximation in statistical learning problems that recover the
Gaussian rates in completely heavy tailed situations. We believe that pursuing
the same direction in the context of stochastic optimization would lead to
intriguing questions. Indeed, there are many variants of (convex) stochastic
optimization problems that are not covered in this article. For example, among
these questions is _chance constrained stochastic optimization_ , where the
optimization takes place only over actions $x\in\mathcal{X}$ satisfying
probabilistic constraints of the form $\mathbf{E}[G(x,\xi)]\leq 0$. We are
confident that our methods can be adapted to these settings as well, though we
shall leave this for future work.

##  3\. Applications

Before continuing with the portfolio optimization problem (in its general
form), we present three of Theorem 2.9.

###  3.1. Multivariate mean estimation

As a first application of Theorem 2.9, let us return to the problem of mean
estimation—this time for a square integrable $d$-dimensional random vector
$\xi$. Mean estimation is a stochastic optimization problem because

$\mathbf{E}[\xi]=\mathrm{argmin}\big{\\{}\mathbf{E}[\|x-\xi\|_{2}^{2}]:x\in\mathbb{R}^{d}\big{\\}}.$

This suggests that one should set

$F(x,\xi):=\frac{1}{2}\|x-\xi\|_{2}^{2}\quad\text{for
}x\in\mathcal{X}:=\mathbb{R}^{d}$

so that $x^{\ast}=\mathbf{E}[\xi]$. (The factor $\frac{1}{2}$ has only a
normalizing purpose to make the computations below clearer.) As an intimidate
consequence of Theorem 2.13 we obtain the following.

######  Corollary 3.1 (Multivariate mean estimation).

There are absolute constants $C_{1},C_{2}$ such that the following holds. Let
$r>0$ and let

$N\geq
C_{1}\frac{\mathop{\mathrm{trace}}(\mathrm{\mathbf{C}ov}[\xi])}{r^{2}}.$

Then there is a procedure $\widehat{x}_{N}^{\ast}$ such that, with probability
at least

$1-2\exp\Big{(}-C_{2}N\min\Big{\\{}1,\frac{r^{2}}{\lambda_{\mathrm{max}}(\mathrm{\mathbf{C}ov}[\xi])}\Big{\\}}\Big{)},$

we have that

$\displaystyle\big{\|}\widehat{x}_{N}^{\ast}-\mathbf{E}[\xi]\big{\|}_{2}$
$\displaystyle\leq r.$

Let us once again mention that the question of finding an estimator of the
mean of a heavy tailed random vector that exhibits Gaussian rates remained
open until very recently: it was settled in [19, Theorem 1]; see also [17] for
a recent survey. Corollary 3.1 recovers [19, Theorem 1].

###### Proof of Corollary 3.1.

For every $x\in\mathcal{X}$, we have that

$\displaystyle\nabla F(x,\xi)$ $\displaystyle=x-\xi,$
$\displaystyle\nabla^{2}F(x,\xi)$ $\displaystyle=\mathrm{Id}.$

In particular $\|\cdot\|=\|\cdot\|_{2}$ and Assumption 2.3 is clearly
satisfied. Actually, as the Hessian is deterministic and independent of the
action $x$, we are in the setting of Theorem 2.13 and it remains to compute
the parameters $N_{\mathrm{G}}(r)$ and $\sigma^{2}$. To that end, it suffices
to note that $\nabla^{2}f(x^{\ast})^{-1}=\mathrm{Id}$ and
$\mathrm{\mathbf{C}ov}[\nabla F(x^{\ast},\xi)]=\mathrm{\mathbf{C}ov}[\xi]$;
hence

$\displaystyle N_{\mathrm{G}}(r)$
$\displaystyle=\frac{1}{r^{2}}\mathop{\mathrm{trace}}(\mathrm{\mathbf{C}ov}[\xi]),$
$\displaystyle\sigma^{2}$
$\displaystyle=\lambda_{\mathrm{max}}(\mathrm{\mathbf{C}ov}[\xi]).$

The proof therefore follows from Theorem 2.13. ∎

###  3.2. Linear regression

Linear regression is one of the fundamental problems studied in statistics.
Given a one-dimensional random variable $Y$ and a $d$-dimensional random
vector $X$, the task is to find the best possible forecast of $Y$ based on
linear combinations of $X$. To be more precise, one seeks the minimizer of
$x\mapsto\mathbf{E}[(\langle X,x\rangle-Y)^{2}]$ over $x\in\mathbb{R}^{d}$ (or
a subset thereof). This problem clearly falls within the scope of this article
by considering

$F(x,\xi):=\frac{1}{2}(\langle X,x\rangle-Y)^{2}\quad\text{where }\xi:=(X,Y)$

with $\mathcal{X}\subseteq\mathbb{R}^{d}$. (The purpose of the factor
$\frac{1}{2}$ is again only for convenience.) In order to lighten notation, we
shall impose a standard assumption on $X$: that it is centred and isotropic.
The latter means that its covariance matrix is the identity.

######  Assumption 3.2.

The set $\mathcal{X}\subseteq\mathbb{R}^{d}$ is closed and convex, $X$ is
centred and isotropic, and there is a constant $L_{X}$ such that

(3.1) $\displaystyle\mathbf{E}[\langle X,x\rangle^{4}]^{\frac{1}{4}}$
$\displaystyle\leq L_{X}\mathbf{E}[\langle X,x\rangle^{2}]^{\frac{1}{2}}$

for every $x\in\mathbb{R}^{d}$. Further,

$\bar{\sigma}^{2}:=\mathbf{E}[(\langle
X,x^{\ast}\rangle-Y)^{4}]^{\frac{1}{2}}$

is finite.

The assumption (3.1), which means that the $L_{4}$ and $L_{2}$ norms of linear
forms of $X$ are equivalent, is a typical assumption made in high-dimensional
statistics and it is not too restrictive.

######  Corollary 3.3 (Linear Regression).

If Assumption 3.2 is satisfied, there are constants $c_{1}$ and $c_{2}$
depending only on $L_{X}$ such that the following holds. Let $r>0$ and

$N\geq
c_{1}\max\Big{\\{}d\log(2d)\,,\,\frac{d\cdot\bar{\sigma}^{2}}{r^{2}}\Big{\\}}.$

Then there is a procedure $\widehat{x}_{N}^{\ast}$ such that, with probability
at least

$1-2\exp\Big{(}-c_{2}N\min\Big{\\{}1,\frac{r^{2}}{\bar{\sigma}^{2}}\Big{\\}}\Big{)},$

we have that

$\displaystyle\|\widehat{x}_{N}^{\ast}-x^{\ast}\|_{2}$ $\displaystyle\leq r,$
$\displaystyle\mathbf{E}_{X,Y}[(\langle
X,\widehat{x}_{N}^{\ast}\rangle-Y)^{2}]$ $\displaystyle\leq\mathbf{E}[(\langle
X,x^{\ast}\rangle-Y)^{2}]+2r^{2}.$

Here, $\mathbf{E}_{X,Y}[\cdot]$ denotes the expectation taken only over $X$
and $Y$ (and, of course, not the sample $(X_{i},Y_{i})_{i=1}^{N}$ used for the
computation of $\widehat{x}_{N}^{\ast}$).

Compared to the benchmark result on linear regression in a heavy tailed
scenario [20], Corollary 3.3 has an additional $\log(2d)$ term in the estimate
on the sample size. This term is merely an artifact of the generality of our
main result. Its origin lies in the matrix-Bernstein inequality, which we use
in the process of bounding the smallest singular value of a general random
matrix ensemble (namely $\nabla^{2}F(x^{\ast},\xi)$); that extra factor is not
needed in this example and can be easily removed.

###### Proof of Corollary 3.3.

For every $x\in\mathcal{X}$, we have that

$\displaystyle\nabla F(x,\xi)$ $\displaystyle=(\langle X,x\rangle-Y)X,$
$\displaystyle\nabla^{2}F(x,\xi)$ $\displaystyle=X\otimes X.$

As $X$ is isotropic, this implies $\nabla^{2}f(x^{\ast})=\mathrm{Id}$ and in
particular $\|\cdot\|=\|\cdot\|_{2}$. Also, as $(\langle X,x^{\ast}\rangle-Y)$
and $X$ are both in $L_{4}$ by assumption, the Cauchy-Schwartz inequality
shows that $\nabla F(x^{\ast},\xi)$ is square integrable. In particular,
Assumption 2.3 is satisfied. Employing the norm equivalence of $X$ (3.1), we
obtain

$\displaystyle\mathbf{E}[\langle\nabla^{2}F(x^{\ast},\xi)z,z\rangle^{2}]$
$\displaystyle=\mathbf{E}[\langle X,z\rangle^{4}]$ $\displaystyle\leq
L_{X}^{4}\|z\|^{4}$

for every $z\in\mathbb{R}^{d}$; thus Assumption 2.5 is satisfied with
$L=L_{X}^{4}$. Finally, as the Hessian is independent of the action $x$,
Assumption 2.7 is clearly satisfied with $\alpha=1$ , $K\equiv 0$ and an
arbitrary $r_{0}$; in particular, $N_{\mathrm{H},\mathcal{E}}\leq d$.

It remains to compute the parameters $N_{\mathrm{G}}(r),\sigma^{2}$, and
$c_{\mathrm{H}}$. Using once again that the Hessian is independent of the
action $x$, it is evident that $c_{\mathrm{H}}=1$. Turning to $\sigma^{2}$ and
$N_{\mathrm{G}}(r)$, recall that $\nabla^{2}f(x^{\ast})=\mathrm{Id}$, and let
us estimate the largest eigenvalue and the trace of
$\mathrm{\mathbf{C}ov}[\nabla F(x^{\ast},\xi)]$.

For every $z\in\mathbb{R}^{d}$, the Cauchy-Schwartz inequality together with
(3.1) imply

(3.2) $\displaystyle\begin{split}\langle\mathrm{\mathbf{C}ov}[\nabla
F(x^{\ast},\xi)]z,z\rangle&=\mathrm{\mathbf{V}ar}[(\langle
X,x^{\ast}\rangle-Y)\langle X,z\rangle]\\\
&\leq\mathbf{E}\big{[}\big{(}(\langle X,x^{\ast}\rangle-Y)\langle
X,z\rangle\big{)}^{2}\big{]}\\\ &\leq\mathbf{E}[(\langle
X,x^{\ast}\rangle-Y)^{4}]^{\frac{1}{2}}\mathbf{E}[\langle
X,z\rangle^{4}]^{\frac{1}{2}}\\\
&\leq\bar{\sigma}^{2}L_{X}^{2}\|z\|_{2}^{2}.\end{split}$

This clearly implies $\sigma^{2}\leq L_{X}^{2}\bar{\sigma}^{2}$ and, taking
the standard Euclidean basis $z=e_{i}$ in (3.2), we conclude
$\mathrm{\mathbf{C}ov}[\nabla
F(x^{\ast},\xi)]_{ii}\leq\bar{\sigma}^{2}L_{X}^{2}$, hence

$\displaystyle N_{\mathrm{G}}(r)$
$\displaystyle=\frac{1}{r^{2}}\sum_{i=1}^{d}\mathrm{\mathbf{C}ov}[\nabla
F(x^{\ast},\xi)]_{ii}\leq\frac{\bar{\sigma}^{2}L_{X}^{2}d}{r^{2}}.$

The proof now follows from Theorem 2.9. ∎

###  3.3. Ridge regression

A popular modification of linear regression is _ridge regression_ (also known
as _weight decay regression_ and _$\ell_{2}$ -regularized regression_ in the
machine learning community). The idea is that one penalizes a large Euclidean
norm of $x$ by setting

$F(x,\xi):=(\langle X,x\rangle-Y)^{2}+\|x\|_{2}^{2}$

where $\xi:=(X,Y)$ and $x\in\mathcal{X}\subseteq\mathbb{R}^{d}$. The aim of
this sort of penalization is to counteract _over-fitting_.

In contrast to the estimate we obtain in linear regression, the factor
$d\log(2d)$ in the minimal sample is not needed here:

######  Corollary 3.4.

If Assumption 3.2 is satisfied, there are absolute constants $C_{1}$ and
$C_{2}$ such that the following holds. Let $r>0$ and set

$N\geq C_{1}\frac{d\cdot\bar{\sigma}^{2}}{r^{2}}.$

Then there is a procedure $\widehat{x}_{N}^{\ast}$ such that, with probability
at least

$1-2\exp\Big{(}-C_{2}N\min\Big{\\{}1,\frac{r^{2}}{\bar{\sigma}^{2}}\Big{\\}}\Big{)},$

satisfies that

$\displaystyle\|\widehat{x}_{N}^{\ast}-x^{\ast}\|_{2}$ $\displaystyle\leq r,$
$\displaystyle\mathbf{E}_{X,Y}[(\langle
X,\widehat{x}_{N}^{\ast}\rangle-Y)^{2}]+\|\widehat{x}_{N}^{\ast}\|_{2}^{2}$
$\displaystyle\leq\mathbf{E}[(\langle
X,x^{\ast}\rangle-Y)^{2}]+\|x^{\ast}\|_{2}^{2}+2r^{2}.$

###### Proof.

For every $x\in\mathcal{X}$, we have that

$\displaystyle\nabla^{2}F(x,\xi)$ $\displaystyle=2X\otimes X+2\mathrm{Id},$
$\displaystyle\nabla^{2}f(x)$ $\displaystyle=4\mathrm{Id};$

hence we are in the setting of Theorem 2.13. All that remains is to estimate
the parameters $N_{\mathrm{G}}(r)$ and $\sigma^{2}$, and this can be done
exactly as in the proof of Corollary 3.3. ∎

###  3.4. Portfolio optimization

As a final example, we address the portfolio optimization problem in its
general form, that is, we apply Theorem 2.9 to the problem

$F(x,\xi):=\ell(V_{x})\quad\text{where }\begin{array}[]{l}V_{x}:=-Y-\langle
X,x\rangle,\\\ \hskip 6.00006pt\xi:=(X,Y),\end{array}$

for $x\in\mathcal{X}\subseteq\mathbb{R}^{d}$ that is closed and convex.
Moreover, $\ell\colon\mathbb{R}\to\mathbb{R}$ is strictly convex, increasing,
bounded from below, and we assume that it is three times continuously
differentiable.

We shall impose the following two assumptions on the zero-mean random vector
$X$. Firstly, assume that $X$ satisfies a (directional) $L_{6}$-$L_{2}$ norm
equivalence, i.e. there is a constant $L_{X}$ such that

(3.3) $\displaystyle\mathbf{E}[\langle X,z\rangle^{6}]^{\frac{1}{6}}\leq
L_{X}\cdot\mathbf{E}[\langle X,z\rangle^{2}]^{\frac{1}{2}}<\infty$

for all $z\in\mathbb{R}^{d}$. In addition, we assume that the following no-
arbitrage condition holds

(3.4) $\displaystyle\mathbf{P}[\langle X,z\rangle<0]>0\quad\text{for all
}z\in\mathbb{R}^{d}\setminus\\{0\\}.$

######  Remark 3.5.

The classical no-arbitrage condition used in mathematical finance reads as
follows: for every $z\in\mathbb{R}^{d}$, we have that

$\mathbf{P}[\langle X,z\rangle<0]=0\text{ implies that }\mathbf{P}[\langle
X,z\rangle>0]=0;$

i.e. it is not possible to make profit without taking any risk. Under this
condition, it is well-known that one can decompose $\mathbb{R}^{d}=V\oplus
V^{\perp}$ into an orthogonal sum such that $\mathbf{P}[\langle
X,v\rangle<0]>0$ for all $v\in V\setminus\\{0\\}$ and $\mathbf{P}[\langle
X,w\rangle=0]=1$ for all $w\in V^{\perp}$, see e.g. [7, Section 1.3]. In
particular, replacing $\mathcal{X}$ by $\mathcal{X}\cap V$ viewed as a subset
of $\mathbb{R}^{\mathrm{dim}(V)}$ does not affect the outcome of the portfolio
optimization problem but guarantees that (3.4) holds.

Moreover, we shall assume that part (c) of Assumption 2.3, pertaining the
integrability of $F,\nabla F,\nabla^{2}F$, is satisfied. By Hölder’s
inequality and (3.3), this is the case if, for example,
$\ell(V_{x}),\ell^{\prime}(V_{x})^{4},\ell^{\prime\prime}(V_{x})^{2}$ are
integrable for every $x\in\mathcal{X}$. Then $f$ is real-valued, and standard
arguments building on the no-arbitrage condition, show that $f$ is strictly
convex and coercive. In particular, a unique optimal action
$x^{\ast}\in\mathcal{X}$ exists; see e.g. [7, Section 3.1].

Finally, denoting by $\mathcal{B}_{1}^{\ast}$ the ball of radius 1 w.r.t. the
norm $\|\cdot\|$ centered at $x^{\ast}$ and restricted to $\mathcal{X}$, we
assume that

$\displaystyle\bar{\sigma}^{2}$
$\displaystyle:=\mathbf{E}[(\tfrac{\ell^{\prime}(V_{x^{\ast}})^{2}}{\ell^{\prime\prime}(V_{x^{\ast}})})^{2}]^{\frac{1}{2}},$
$\displaystyle v_{1}$ $\displaystyle:=\mathbf{E}[|V_{x^{\ast}}|],$
$\displaystyle v_{2}$
$\displaystyle:=\mathbf{E}[\ell^{\prime\prime}(V_{x^{\ast}})^{6}]^{\frac{1}{6}},$
$\displaystyle v_{K}$
$\displaystyle:=\mathbf{E}[\sup\nolimits_{x\in\mathcal{B}_{1}^{\ast}}\ell^{\prime\prime\prime}(V_{x})^{2}]^{\frac{1}{2}},$
$\displaystyle v_{\mathcal{E}_{\mathrm{H}}}$
$\displaystyle:=\sup\nolimits_{x\in\mathcal{B}_{1}^{\ast}}\mathbf{E}[\sup\nolimits_{t\in[0,1]}\ell^{\prime\prime\prime}(V_{x^{\ast}+t(x-x^{\ast})})^{2}]^{\frac{1}{2}}$

are all finite.

######  Remark 3.6.

If, for instance, $\ell^{\prime\prime\prime}$ is non-negative and increasing,
the terms $v_{K}$ and $v_{\mathcal{E}_{\mathrm{H}}}$ can be simplified as

$\displaystyle\sup_{x\in\mathcal{B}_{1}^{\ast}}\ell^{\prime\prime\prime}(V_{x})$
$\displaystyle=\ell^{\prime\prime\prime}(V_{x^{\ast}}+\|X\|_{\ast}),$
$\displaystyle\sup_{t\in[0,1]}\ell^{\prime\prime\prime}(V_{x^{\ast}+t(x-x^{\ast})})$
$\displaystyle\leq\ell^{\prime\prime\prime}(V_{x^{\ast}}+|\langle
X,x-x^{\ast}\rangle|)$

where $\|\cdot\|_{\ast}:=\sup_{x\in\mathbb{R}^{d}\text{ s.t.\ }\|x\|\leq
1}\langle x,\cdot\rangle$ denotes the dual norm of $\|\cdot\|$. (Note that if
$\|\cdot\|$ is (equivalent to) the Euclidean norm, then its dual norm is
(equivalent to) the Euclidean norm too).

Under these assumptions, we obtain the following:

######  Corollary 3.7 (Portfolio optimization).

There are constants $c_{1},c_{2},c_{3},c_{4}$ depending only on
$L_{X},v_{1},v_{2}$ such that the following holds. For
$r\in(0,\min\\{1,\frac{c_{1}}{v_{\mathcal{E}_{\mathrm{H}}}}\\})$ and

$N\geq
c_{1}\max\Big{\\{}\frac{d\cdot\bar{\sigma}^{2}}{r^{2}},\,d\log(d(v_{K}+2))\,\Big{\\}},$

there is a procedure $\widehat{x}_{N}^{\ast}$ such that, with probability at
least

$1-2\exp\Big{(}-c_{2}N\min\Big{\\{}1,\frac{r^{2}}{\bar{\sigma}^{2}}\Big{\\}}\Big{)},$

we have that

$\displaystyle\|\widehat{x}_{N}^{\ast}-x^{\ast}\|$ $\displaystyle\leq r,$
$\displaystyle u(\widehat{x}_{N}^{\ast})$ $\displaystyle\geq
u(x^{\ast})-c_{4}r^{2}.$

We postpone the proof of Corollary 3.7; it will be presented in Section 6,
where we also show how to recover the estimate in the exponential portfolio
optimization problem (i.e. Corollary 2.10).

##  4\. On the smallest singular value of general random matrix ensembles

In the course of the analysis needed in the proof of Theorem 2.9, a crucial
ingredient is that sampling can exhibit that
$\langle\nabla^{2}F(x^{\ast},\xi)(x-x^{\ast}),x-x^{\ast}\rangle$ is
sufficiently large. Put differently, it is essential to derive a suitable
lower bound on the smallest singular value of the empirical random matrix of
$\nabla^{2}F(x^{\ast},\xi)$.

Results of this type have been studied extensively [1, 14, 33, 36, 39, 45],
however (to the best of our knowledge) the focus was on random matrix
ensembles that had some additional special structure, like iid rows/columns.
Unfortunately such special structure need not exist in our setting.

In this section, let $A$ be a real, square integrable, positive-semidefinite
$(d\times d)$-random matrix and let $(A_{i})_{i\geq 1}$ be independent copies
of $A$. (in the context of this article, the case that interests us is
$A=\nabla^{2}F(x^{\ast},\xi)$.) Denote its expectation by
$\mathbb{A}:=\mathbf{E}[A]$, the semi-norm endowed by $\mathbb{A}$ is

$\|x\|:=\langle\mathbb{A}x,x\rangle^{\frac{1}{2}}=\mathbf{E}[\langle
Ax,x\rangle]^{\frac{1}{2}}$

and the corresponding unit sphere is

$S:=\\{x\in\mathbb{R}^{d}:\|x\|=1\\}.$

To simplify the presentation, assume that $\|\cdot\|$ is a true norm, i.e.
$\|x\|=0$ implies that $x=0$. Next, for any $(d\times d)$-matrix $B$, its
operator norm is given by

$\|B\|_{\mathrm{op}}:=\max_{x,y\in S}\langle Bx,y\rangle.$

Before stating the main result of this section (Theorem 4.4) let us begin with
one of its outcomes.

######  Corollary 4.1.

Assume that there is a constant $L>0$ such that

(4.1) $\displaystyle\mathbf{E}[\langle Ax,x\rangle^{2}]^{\frac{1}{4}}\leq
L\quad\text{for all }x\in S.$

Then there are constants $c_{1}$ and $c_{2}$ that depend only on $L$ such that
the following holds. Let $\gamma\in(0,1)$ and assume that

$N\geq c_{1}\frac{d}{\gamma^{2}}\log\Big{(}\frac{2d}{\gamma}\Big{)}.$

Then, with probability at least

$1-2\exp\big{(}-c_{2}N\gamma^{2}\big{)},$

we have that

$\lambda_{\min}\Big{(}\frac{1}{N}\sum_{i=1}^{N}A_{i}\Big{)}\geq(1-\gamma)\lambda_{\min}(\mathbf{E}[A]).$

(Here, of course, $\lambda_{\min}$ denotes the smallest singular value.)

As the results of this section will be used in the proof of Theorem 2.9 for
the construction of a median-of-means tournament, we also need a median-of-
means version of Corollary 4.1. To that end, as before, let $N=nm$ for two
integers $n$ and $m$, and consider a partition of $\\{1,\dots,N\\}$ into $n$
disjoint blocks $I_{j}$, each one of cardinality $|I_{j}|=m$. Throughout this
article, we make the _notational convention_ that the letter $j$ always refers
blocks, i.e. $j$ is always an element of $\\{1,\dots,n\\}$. In addition,
$0<C,C_{0},C_{1},\dots$ denote absolute constants independent of all
parameters. They are allowed to change their values from line to line.

We often encounter the so-called _Rademacher random variables_
$(\varepsilon_{i})_{i\geq 1}$, which are independent, symmetric random signs
(i.e. $\mathbf{P}[\varepsilon_{i}=\pm 1]=\frac{1}{2}$) that are also
independent of all the other random variables that appear in the analysis; in
particular, they are independent of $(A_{i})_{i=1}^{N}$.

We have already seen in the introduction that the smallest empirical singular
value of a random matrix cannot be bounded (even with constant probability)
without imposing some of assumption. While an integrability assumption as in
(4.1) will do the job, the following definition from [25] contains the essence
of what is actually needed.

######  Definition 4.2 (Stable lower bound).

A set $H\subseteq L_{2}$ of real-valued functions satisfies a _stable lower
bound_ with parameters $(m,\gamma,l,k)$ if the following holds: for every
$h\in H$ and independent copies $(h_{i})_{i\geq 1}$ of $h$, with probability
at least $1-2\exp(-k)$, for all $J\subseteq\\{1,\dots,m\\}$ with $|J|\leq l$,
we have that

$\frac{1}{m}\sum_{i\in\\{1,\dots,m\\}\setminus
J}h_{i}^{2}\geq(1-\gamma)\mathbf{E}[h^{2}].$

We say that a (symmetric, positive semi-definite, $d\times d$) random matrix
$A$ satisfies a stable lower bound with parameters $(m,\gamma,l,k)$ if
$H:=\\{\langle Ax,x\rangle^{\frac{1}{2}}:x\in S\\}$ does (with the same
parameters).

The stable lower bound can be seen as an extension of the _small ball
property_. Recall that a set $H$ is said to satisfy a small ball property with
parameters $(\kappa,\delta)$ if

$\mathbf{P}\big{[}h^{2}\geq\kappa^{2}\cdot\mathbf{E}[h^{2}]\big{]}\geq\delta\quad\text{for
all }h\in H.$

This condition is used frequently in problems involving a quadratic term (see,
e.g. [15, 22, 26]).

######  Remark 4.3.

Let $H=\\{\langle Ax,x\rangle^{\frac{1}{2}}:x\in S\\}$. Then the following
hold.

  1. (i)

If $H$ satisfies the small ball property with constants $(\kappa,\delta)$,
then $H$ satisfies a stable lower bound with parameters

$(m,\gamma,k,l)=\Big{(}m,1-\frac{\delta\kappa^{2}}{2},s_{1}\delta
m,s_{2}\delta m\Big{)}$

for every $m$, where $s_{1},s_{2}>0$ are absolute constants.

  2. (ii)

If $H$ is bounded in $L_{p}$ for some $p>2$, that is,

$\mathbf{E}[|h|^{p}]^{\frac{1}{p}}\leq L\quad\text{for all }h\in H$

where $L$ is a fixed constant, then $H$ satisfies a stable lower bound with
parameters

$(m,\gamma,k,l)=\Big{(}m,\gamma,s_{1}m\gamma^{\frac{p}{p-2}},s_{2}m\gamma^{\max\\{\frac{p}{p-2},2\\}}\Big{)}$

where $s_{1},s_{2}>0$ are constants depending only on $p$ and $L$.

The first statement is an immediate consequence of a Binomial concentration
inequality and second statement can be found in [25, Section 2.1] together
with a more thorough discussion and analysis of stable lower bounds.

The following theorem is the main result of this section. To formulate it,
recall that for a random matrix $A$, $\mathbf{E}[A]$ is denoted by
$\mathbb{A}$.

######  Theorem 4.4.

There are absolute constants $C_{1}$ and $C_{2}$ such that the following
holds. Fix $\gamma,\tau\in(0,1)$ and assume that

  1. (a)

the random matrix $A$ satisfies a stable lower bound with parameters
$(m,\frac{\gamma}{2},2l,k)$ were $k\geq\max\\{4,2\log(\frac{4}{\tau})\\}$,

  2. (b)

the sample size satisfies

$N\geq
C_{1}\max\Big{\\{}\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}},\frac{dm}{\tau
k}\log\Big{(}\frac{\log(3d)\mathbf{E}[\|A\mathbb{A}^{-1}A\|_{\mathrm{op}}]}{\gamma\tau\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}}}\Big{)}\Big{\\}}.$

Then, with probability at least

$1-2\exp\Big{(}-C_{2}N\tau\min\Big{\\{}\frac{l}{m},\frac{k}{m}\Big{\\}}\Big{)},$

for every $x\in\mathbb{R}^{d}$ and every $J_{j}\subseteq I_{j}$ with
$|J_{j}|\leq l$ for all $j$, we have that

$\Big{|}\Big{\\{}j:\frac{1}{m}\sum_{i\in I_{j}\setminus J_{j}}\langle
A_{i}x,x\rangle\geq(1-\gamma)\|x\|^{2}\Big{\\}}\Big{|}\geq(1-\tau)n.$

The formulation in Theorem 4.4 is tailer-made for the median-of-means analysis
which is presented in the next section (as part of the proof of Theorem 2.9).
It ensures a stability property that is stronger than a mere lower bound on
the quadratic form (and therefore, a lower estimate on the smallest singular
value). Rather, it gives a useful lower bound even if a proportion of the
sample is arbitrarily modified or removed. This will be useful in the proof of
Theorem 2.9 when passing from the Hessian evaluated at the optimizer to the
Hessian evaluated at mid-points. In addition, Theorem 4.4 provides an almost
isometric lower bound (i.e. when $\gamma$ is close to zero) while the analysis
for Theorem 2.9 actually only requires an isomorphic lower bound.

Finally, let us formulate the following immediate consequence of Theorem 4.4.

######  Corollary 4.5.

There are absolute constants $C_{1}$ and $C_{2}$ such that the following
holds. Fix $\gamma\in(0,1)$ and assume that

  1. (a)

the random matrix $A$ satisfies a stable lower bound with parameters
$(N,\frac{\gamma}{2},2l,k)$ for some $k\geq 4$,

  2. (b)

the sample size satisfies

$N\geq
C_{1}\max\Big{\\{}\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}},\frac{dN}{k}\log\Big{(}\frac{\log(3d)\mathbf{E}[\|A\mathbb{A}^{-1}A\|_{\mathrm{op}}]}{\gamma\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}}}\Big{)}\Big{\\}}.$

Then, with probability at least

$1-2\exp\Big{(}-C_{2}N\min\Big{\\{}\frac{l}{N},\frac{k}{N}\Big{\\}}\Big{)},$

we have that

$\lambda_{\min}\Big{(}\frac{1}{N}\sum_{i=1}^{N}A_{i}\Big{)}\geq(1-\gamma)\lambda_{\min}(\mathbf{E}[A]).$

###### Proof.

Applying Theorem 4.4 with $n=1$ (hence $m=N$), $\tau=0.6$, and
$J_{j}=\emptyset$ yields the following: with probability at least
$1-2\exp(-C_{2}N\min\\{\frac{l}{N},\frac{k}{N}\\})$, for every
$x\in\mathbb{R}^{d}$, we have that

$\displaystyle\Big{\langle}\frac{1}{N}\sum_{i=1}^{N}A_{i}x,x\Big{\rangle}$
$\displaystyle\geq(1-\gamma)\langle\mathbf{E}[A]x,x\rangle.$

A twofold application of the extremal expression
$\lambda_{\min}(\cdot)=\min_{x\in\mathbb{R}^{d}\text{ s.t.\
}\|x\|_{2}=1}\langle\,\cdot\,x,x\rangle$ of the smallest singular value
completes the proof. ∎

In order to recover Corollary 4.1 from Corollary 4.5 (and later also to apply
Theorem 4.4 in the proof of Theorem 2.9) we need two simple observations,
showing that under a $L_{4}-L_{2}$ norm equivalence, the estimate on the
sample size in Corollary 4.5 and Theorem 4.4 can be simplified.

######  Lemma 4.6.

We have that

(4.2) $\displaystyle
1\leq\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}}\leq\mathbf{E}[\|A\mathbb{A}^{-1}A\|_{\mathrm{op}}]\leq
d\cdot\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}}.$

###### Proof.

We start with the final inequality in (4.2). Recall that
$\mathbb{A}=\mathbf{E}[A]$ and note that the relation
$\|\cdot\|=\|\mathbb{A}^{\frac{1}{2}}\cdot\|_{2}$ transfers to the operator
norm in the following sense: for any $(d\times d)$-matrix $B$, we have that

(4.3)
$\displaystyle\begin{split}\|B\|_{\mathrm{op}}&=\|\mathbb{A}^{-\frac{1}{2}}B\mathbb{A}^{-\frac{1}{2}}\|_{\mathrm{op}_{2}}\quad\text{where}\\\
\|B\|_{\mathrm{op}_{2}}&:=\max_{x,y\in\mathbb{R}^{d}\text{ s.t.\
}\|x\|_{2},\|y\|_{2}\leq 1}\langle Bx,y\rangle.\end{split}$

Indeed, $\\{x\in\mathbb{R}^{d}:\langle\mathbb{A}x,x\rangle\leq 1\\}$ is the
ellipsoid $\mathbb{A}^{-\frac{1}{2}}B_{2}^{d}$ (where $B_{2}^{d}$ is the unit
ball w.r.t. the Euclidean norm).

The norm $\|\cdot\|_{\mathrm{op}_{2}}$ is the usual spectral norm which, for
positive semidefinite matrices, equals the largest singular value
$\lambda_{\max}(\cdot)$.

Setting $F:=\mathbb{A}^{-\frac{1}{2}}A\mathbb{A}^{-\frac{1}{2}}$ which is
positive semidefinite, we thus have

$\displaystyle\mathbf{E}[\|A\mathbb{A}^{-1}A\|_{\mathrm{op}}]$
$\displaystyle=\mathbf{E}[\|F^{2}\|_{\mathrm{op}_{2}}]$
$\displaystyle=\mathbf{E}[\lambda_{\max}(F^{2})]\leq\sum_{i=1}^{d}\mathbf{E}[(F^{2})_{ii}],$

where the last inequality follows by bounding the largest singular value by
the trace. On the other hand, for every $i=1,\dots,d$, taking the Euclidean
unit vector $x=y=e_{i}$ in (4.3) shows that

$\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}}=\|\mathbf{E}[F^{2}]\|_{\mathrm{op}_{2}}\geq\mathbf{E}[(F^{2})_{ii}]$

and hence the last inequality of the lemma follows.

The second inequality in (4.2) is trivial and the first inequality follows
from (4.3) and Jensen’s inequality for matrices (which states that
$\mathbf{E}[F^{2}]\succeq\mathbf{E}[F]^{2}=\mathrm{Id}$). This completes the
proof. ∎

######  Lemma 4.7.

Assume that there is a constant $L$ such that $\mathbf{E}[\langle
Ax,x\rangle^{2}]^{\frac{1}{4}}\leq L$ for all $x\in S$. Then

$\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}}\leq dL^{4}.$

###### Proof.

Recall that $F:=\mathbb{A}^{-\frac{1}{2}}A\mathbb{A}^{-\frac{1}{2}}$ and that,
by (4.3),

$\displaystyle\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}}=\|\mathbf{E}[F^{2}]\|_{\mathrm{op}_{2}}=\max_{x\in\mathbb{R}^{d}\text{
s.t.\ }\|x\|_{2}\leq 1}\mathbf{E}[\langle F^{2}x,x\rangle].$

Moreover, for every $x\in\mathbb{R}^{d}$, we have

$\displaystyle\langle F^{2}x,x\rangle$ $\displaystyle=\langle
FF^{\frac{1}{2}}x,F^{\frac{1}{2}}x\rangle$
$\displaystyle\leq\|F\|_{\mathrm{op}_{2}}\|F^{\frac{1}{2}}x\|_{2}^{2},$

which, in combination with the Cauchy-Schwartz inequality, yields that

$\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}}\leq\max_{x\in\mathbb{R}^{d}\text{
s.t.\ }\|x\|_{2}\leq
1}\mathbf{E}[\|F\|_{\mathrm{op}_{2}}^{2}]^{\frac{1}{2}}\mathbf{E}[\|F^{\frac{1}{2}}x\|_{2}^{4}]^{\frac{1}{2}}.$

At this point, recall that
$\\{x\in\mathbb{R}^{d}:\langle\mathbb{A}x,x\rangle\leq 1\\}$ is the ellipsoid
$\mathbb{A}^{-\frac{1}{2}}B_{2}^{d}$, and note that an equivalent formulation
of (4.1) is

$\displaystyle\mathbf{E}[\|F^{\frac{1}{2}}x\|_{2}^{4}]^{\frac{1}{2}}$
$\displaystyle=\mathbf{E}[\langle Fx,x\rangle^{2}]^{\frac{1}{2}}$
$\displaystyle\leq L^{2}\mathbf{E}[\langle Fx,x\rangle]$

for every $x\in\mathbb{R}^{d}$, and that $\mathbf{E}[\langle Fx,x\rangle]=1$
for every $x\in\mathbb{R}^{d}$ with $\|x\|_{2}=1$. Hence, bounding
$\|F\|_{\mathrm{op}_{2}}=\lambda_{\max}(F)$ by the trace of $F$,

$\displaystyle\mathbf{E}[\|F\|_{\mathrm{op}_{2}}^{2}]^{\frac{1}{2}}$
$\displaystyle\leq\sum_{i=1}^{d}\mathbf{E}[(F_{ii})^{2}]^{\frac{1}{2}}$
$\displaystyle=\sum_{i=1}^{d}\mathbf{E}[\langle
Fe_{i},e_{i}\rangle^{2}]^{\frac{1}{2}}\leq dL^{2}.$

In conclusion $\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}}\leq dL^{4}$, as
claimed. ∎

###### Proof of Corollary 4.1.

By Remark 4.3 (ii), the random matrix $A$ satisfies a stable lower bound with
parameters $(N,\frac{\gamma}{2},s_{1}N\gamma^{2},s_{2}N\gamma^{2})$ for
constants $s_{1}$ and $s_{2}$ depending only on $L$. The proof therefore
follows from Corollary 4.5 together with Lemma 4.6 and Lemma 4.7. ∎

Throughout this article, we often aim to prove statements that are supposed to
hold with high probability, uniformly over (uncountable) sets; for example
that for all $x\in S$, most coordinates of $(\langle
A_{i}x,x\rangle)_{i=1}^{N}$ are suitably large. The proofs of such statements
follow (in principle) a recurring scheme: in a first step, we prove that a
slightly stronger variant of the statement holds with high probability for a
single element (i.e. Lemma 4.8 below). By a trivial union bound, this allows
to extend the validity of the statement to a finite set of high cardinality,
and we shall choose such a set with an extra feature: it approximates the
original set in a suitable sense (i.e. Lemma 4.10 below). It then remains to
show that the oscillations caused by passing from the approximating set to the
whole set do not distort the outcome by too much (i.e. Lemma 4.14 below). From
now on, we shall continue under the same assumptions used in the formulation
of Theorem 4.4 without mentioning these assumptions at every instance.

######  Lemma 4.8.

There is an absolute constant $C$ such that the following holds. For every
$x\in S$, with probability at least $1-2\exp(-CN\tau\frac{k}{m})$, for all
choices $J_{j}\subseteq I_{j}$ with $|J_{j}|\leq 2l$, we have that

$\displaystyle\Big{|}\Big{\\{}j:\frac{1}{m}\sum_{i\in I_{j}\setminus
J_{j}}\langle A_{i}x,x\rangle\geq
1-\frac{\gamma}{2}\Big{\\}}\Big{|}\geq\Big{(}1-\frac{\tau}{2}\Big{)}n.$

In particular, for a set $\bar{S}\subseteq S$ satisfying
$\log(|\bar{S}|)\leq\frac{1}{2}C\tau N\frac{k}{m}$, the above statement holds
uniformly over $x\in\bar{S}$.

###### Proof.

The proof follows from an application of Bennett’s inequality and is
essentially the same as the proof of [25, Lemma 4.3]. For completeness, we
sketch the argument. Fix some $x\in S$ and, for every $j$, set

$\delta(j):=\begin{cases}0&\text{if }\frac{1}{m}\sum_{i\in I_{j}\setminus
J_{j}}\langle A_{i}x,x\rangle\geq 1-\frac{\gamma}{2}\text{ for all
}J_{j}\subseteq I_{j}\text{ with }|J_{j}|\leq 2l,\\\
1&\text{otherwise.}\end{cases}$

By definition of the stable lower bound, we have that

$\delta:=\mathbf{P}[\delta(j)=1]\leq 2\exp(-k)\leq\frac{3}{4}.$

If $\delta=0$, there is nothing to prove, so assume otherwise. Now make use of
Bennett’s inequality [5, Theorem 2.9]: for every $u\geq 2$ with probability at
least $1-2\exp(-C\delta n\cdot u\log(u))$, we have that

$|\\{j:\delta(j)=1\\}|\leq u\delta n.$

Apply this to

$u:=\frac{\tau}{2\delta}\geq\exp\Big{(}\frac{k}{2}\Big{)}\geq 2$

(where the second inequality follows as
$\tau\geq\frac{1}{4}\exp(-\frac{k}{2})$ by assumption) and observe that

$\displaystyle C\delta n\cdot u\log(u)$ $\displaystyle=\frac{1}{2}C\tau
n\log\Big{(}\frac{\tau}{2\delta}\Big{)}$ $\displaystyle\geq\frac{C\tau
nk}{4}=\frac{C\tau Nk}{4m}.$

This completes the first part of the proof. The “in particular” part is a
consequence of the union bound. ∎

In a next step we choose a subset of $S$ of high cardinality which “covers”
$S$ w.r.t. the natural metric.

######  Definition 4.9.

Let $(S,d)$ be a metric space and let $\rho>0$. A set $\bar{S}\subset S$ is a
$\rho$-cover of $S$ with respect to the metric $d$ if for every $s\in S$ there
is $\bar{s}\in\bar{S}$ such that $d(s,\bar{s})\leq\rho$.

For now, let $C$ be the absolute constant from Lemma 4.8 and set $C_{1}$ to be
the constant from assumption (b) in Theorem 4.4. Recall that we have the
freedom to choose $C_{1}$ as we see fit, and set $C_{0}$ to be a constant
specified in what follows.

######  Lemma 4.10.

Let

$\rho:=\frac{C_{0}\gamma\tau\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}}}{\log(3d)\mathbf{E}[\|A\mathbb{A}^{-1}A\|_{\mathrm{op}}]}.$

Then there is a $\rho$-cover $\bar{S}\subseteq S$ (w.r.t. the norm
$\|\cdot\|$) of log-cardinality at most $\frac{1}{2}C\tau N\frac{k}{m}$.

###### Proof.

By a simple volumetric argument (see e.g. [38, Exercise 2.2.14]) there is a
set

$\bar{S}_{2}\subseteq S_{2}:=\\{x\in\mathbb{R}^{d}:\|x\|_{2}=1\\}$

such that, for every $x\in S_{2}$ there is $y=y(x)\in\bar{S}_{2}$ with
$\|x-y\|_{2}\leq\rho$ with cardinality

$\displaystyle\log(|\bar{S}_{2}|)$ $\displaystyle\leq
d\log\Big{(}\frac{6}{\rho}\Big{)}$ $\displaystyle\leq
C_{3}d\log\Big{(}\frac{\log(3d)\mathbf{E}[\|A\mathbb{A}^{-1}A\|_{\mathrm{op}}]}{\gamma\tau\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}}}\Big{)},$

where $C_{3}$ depends only on $C_{0}$. By assumption (b) on the sample size in
Theorem 4.4 we conclude that $\log(|\bar{S}_{2}|)\leq\frac{1}{2}C\tau
N\frac{k}{m}$ once the constant $C_{1}$ (in assumption (b)) is chosen
sufficiently large. Finally, the relation
$\|\cdot\|=\|\mathbb{A}^{\frac{1}{2}}\cdot\|_{2}$ readily implies that the set

$\bar{S}:=\\{\mathbb{A}^{-\frac{1}{2}}y:y\in\bar{S}_{2}\\}$

satisfies the statement of the lemma. ∎

The final step in the proof consist of showing that the transition from a
$\rho$-cover $\bar{S}$ to the whole $S$ does not distort the wanted outcome by
too much. To that end, we fix from now on the $\rho$-cover $\bar{S}$ of Lemma
4.10 and denote by $y=y(x)\in\bar{S}$ the element satisfying
$\|x-y\|\leq\rho$. Also, for every $x\in S$, set

$\Delta(x):=\langle Ax,x\rangle-\langle Ay,y\rangle.$

######  Remark 4.11.

The following two preliminary lemmas are stated here to maintain a
chronological order within the proofs. However, it might be helpful to skip to
(the proof of) Lemma 4.14 where their role is clarified and return here
afterwards.

######  Lemma 4.12.

We have that

$\mathbf{E}[|\Delta(x)|]\leq 3\rho\quad\text{for every }x\in S.$

###### Proof.

Fix some $x\in S$. As $A$ is symmetric and positive semidefinite, it follows
from the triangle inequality that

$\big{|}\langle Ax,x\rangle^{\frac{1}{2}}-\langle
Ay,y\rangle^{\frac{1}{2}}\big{|}\leq\langle A(x-y),x-y\rangle^{\frac{1}{2}}.$

Combined with the fact that $|a^{2}-b^{2}|\leq 2|a-b|\max\\{a,b\\}$ for
$a,b\geq 0$, we have

$\displaystyle|\Delta(x)|$ $\displaystyle\leq 2\langle
A(x-y),x-y\rangle^{\frac{1}{2}}\cdot\max\big{\\{}\langle
Ax,x\rangle^{\frac{1}{2}},\langle Ay,y\rangle^{\frac{1}{2}}\big{\\}},$

and by the Cauchy-Schwartz inequality

$\displaystyle\mathbf{E}[|\Delta(x)|]^{2}$ $\displaystyle\leq
4\mathbf{E}[\langle A(x-y),x-y\rangle]\cdot\big{(}\mathbf{E}[\langle
Ax,x\rangle]+\mathbf{E}[\langle Ay,y\rangle]\big{)}$
$\displaystyle=4\|x-y\|^{2}\cdot(\|x\|^{2}+\|y\|^{2})$
$\displaystyle=8\|x-y\|^{2},$

where the second equality follows by definition of the norm $\|\cdot\|$ and
the final one holds because $x,y\in S$. ∎

######  Lemma 4.13.

Let $C_{T}$ be the absolute constant in Talagrand’s concentration inequality
[37]. Moreover, set $b:=\gamma\frac{m}{l}$, let $(A_{i})_{i=1}^{N}$ be
independent copies of $A$ and set $(\varepsilon_{i})_{i\geq 1}$ to be
independent Rademacher random variables that are independent of
$(A_{i})_{i=1}^{N}$. Then we have that

$\mathbf{E}\Big{[}\sup_{x\in
S}\Big{|}\frac{1}{N}\sum_{i=1}^{N}\varepsilon_{i}(|\Delta_{i}(x)|\wedge
b)\Big{|}\Big{]}\leq\frac{\gamma\tau}{C_{T}16}$

once $C_{0}$ (the absolute constant of Lemma 4.10) is small enough.

###### Proof.

As a preliminary step, we invoke the contraction inequality for Bernoulli
processes [16, Corollary 3.17] conditionally on $(A_{i})_{i=1}^{N}$, and
applied to the $1$-Lipschitz map $t\mapsto|t|\wedge b$ which passes through
the origin. It follows that

$\displaystyle\mathbf{E}\Big{[}\sup_{x\in
S}\Big{|}\frac{1}{N}\sum_{i=1}^{N}\varepsilon_{i}(|\Delta_{i}(x)|\wedge
b)\Big{|}\Big{]}$ $\displaystyle\leq 2\mathbf{E}\Big{[}\sup_{x\in
S}\Big{|}\frac{1}{N}\sum_{i=1}^{N}\varepsilon_{i}\Delta_{i}(x)\Big{|}\Big{]}.$

Rewriting

$\Delta_{i}(x)=\langle A_{i}(x+y),x-y\rangle$

we have that

$\displaystyle\Big{|}\frac{1}{N}\sum_{i=1}^{N}\varepsilon_{i}\Delta_{i}(x)\Big{|}$
$\displaystyle=\Big{|}\Big{\langle}\Big{(}\frac{1}{N}\sum_{i=1}^{N}\varepsilon_{i}A_{i}\Big{)}(x+y),x-y\Big{\rangle}\Big{|}$
$\displaystyle\leq
2\rho\Big{\|}\frac{1}{N}\sum_{i=1}^{N}\varepsilon_{i}A_{i}\Big{\|}_{\mathrm{op}},$

because $\|x+y\|\leq 2$ and $\|x-y\|\leq\rho$. Next, set
$F_{i}:=\varepsilon_{i}\mathbb{A}^{-\frac{1}{2}}A_{i}\mathbb{A}^{-\frac{1}{2}}$
for every $i$ and recall the relation between $\|\cdot\|_{\mathrm{op}}$ and
the spectral norm $\|\cdot\|_{\mathrm{op}_{2}}$ stated in (4.3). The Matrix-
Bernstein inequality [40, Theorem I] implies that

$\displaystyle\mathbf{E}\Big{[}\Big{\|}\sum_{i=1}^{N}\varepsilon_{i}A_{i}\Big{\|}_{\mathrm{op}}\Big{]}$
$\displaystyle=\mathbf{E}\Big{[}\Big{\|}\sum_{i=1}^{N}F_{i}\Big{\|}_{\mathrm{op}_{2}}\Big{]}$
$\displaystyle\leq\Big{(}C(d)N\|\mathbf{E}[F^{2}]\|_{\mathrm{op}_{2}}\Big{)}^{\frac{1}{2}}+C(d)\mathbf{E}\Big{[}\max_{1\leq
i\leq N}\|F_{i}\|_{\mathrm{op}_{2}}^{2}\Big{]}^{\frac{1}{2}}$

where

$\displaystyle C(d)$ $\displaystyle=4(1+2\log(2d))\leq 22\log(2d).$

Further, estimating the maximum by the sum and using that
$\|F\|_{\mathrm{op}_{2}}^{2}=\|F^{2}\|_{\mathrm{op}_{2}}$, we trivially have

$\displaystyle\mathbf{E}\Big{[}\max_{1\leq i\leq
N}\|F_{i}\|_{\mathrm{op}_{2}}^{2}\Big{]}$ $\displaystyle\leq
N\mathbf{E}[\|F\|_{\mathrm{op}_{2}}^{2}]$
$\displaystyle=N\mathbf{E}[\|A\mathbb{A}^{-1}A\|_{\mathrm{op}}].$

Putting everything together, we therefore obtain

$\displaystyle\mathbf{E}\Big{[}\sup_{x\in
S}\Big{|}\frac{1}{N}\sum_{i=1}^{N}\varepsilon_{i}(|\Delta_{i}(x)|\wedge
b)\Big{|}\Big{]}$ $\displaystyle\leq 4\rho
C(d)\Big{(}\Big{(}\frac{\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}}}{N}\Big{)}^{\frac{1}{2}}+\Big{(}\frac{\mathbf{E}[\|A\mathbb{A}^{-1}A\|_{\mathrm{op}}]}{N}\Big{)}^{\frac{1}{2}}\Big{)}$
$\displaystyle\leq 4\rho
C(d)\Big{(}1+\Big{(}\frac{\mathbf{E}[\|A\mathbb{A}^{-1}A\|_{\mathrm{op}}]}{\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}}}\Big{)}^{\frac{1}{2}}\Big{)},$

where the second inequality follows from assumption (b) in Theorem 4.4: that
on the sample size satisfies
$N\geq\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}}$. By Lemma 4.6, the
expectation of the operator norm is always larger than the operator norm of
the expectation, hence

$\displaystyle\mathbf{E}\Big{[}\sup_{x\in
S}\Big{|}\frac{1}{N}\sum_{i=1}^{N}\varepsilon_{i}(|\Delta_{i}(x)|\wedge
b)\Big{|}\Big{]}$ $\displaystyle\leq 8\rho
C(d)\frac{\mathbf{E}[\|A\mathbb{A}^{-1}A\|_{\mathrm{op}}]}{\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}}}.$

Recalling the value of $\rho$ from Lemma 4.10 shows that the latter term is at
most $\frac{\gamma\tau}{C_{T}16}$. This completes the proof. ∎

######  Lemma 4.14.

There exists an absolute constant $C$ such that the following holds. For every
$x\in S$ and every $j$, let

$J_{j}^{\ast}(x):=\\{\text{largest }l\text{ coordinates of
}(|\Delta_{i}(x)|)_{i\in I_{j}}\\}\subseteq I_{j}.$

Then, with probability at least $1-2\exp(-C_{2}N\tau\frac{l}{m})$, we have
that

(4.4) $\displaystyle\sup_{x\in S}\Big{|}\Big{\\{}j:\frac{1}{m}\sum_{i\in
I_{j}\setminus
J_{j}^{\ast}(x)}|\Delta_{i}(x)|>\frac{\gamma}{2}\Big{\\}}\Big{|}\leq\frac{\tau
n}{2}.$

###### Proof.

Set $b:=\gamma\frac{m}{l}$. We claim that, for every $x\in S$ and every $j$,

(4.5) $\displaystyle\begin{split}\frac{1}{m}\sum_{i\in I_{j}\setminus
J_{j}^{\ast}(x)}|\Delta_{i}(x)|&>\frac{\gamma}{2}\quad\text{implies}\quad\\\
\frac{1}{m}\sum_{i\in I_{j}}(|\Delta_{i}(x)|\wedge
b)&>\frac{\gamma}{2}.\end{split}$

Indeed, if $|\Delta_{i}(x)|\leq b$ for $i\in I_{j}\setminus J_{j}^{\ast}(x)$,
the second sum in (4.5) is trivially at least as big as the first one.
Otherwise, if there is $i_{0}\in I_{j}\setminus J_{j}^{\ast}(x)$ for which
$|\Delta_{i_{0}}(x)|>b$, then by definition of $J_{j}^{\ast}(x)$, there are
least $l$ coordinates $i\in I_{j}$ for which $|\Delta_{i}(x)|>b$. In
particular, the second sum in (4.5) is at least $\frac{1}{m}lb=\gamma$, and
(4.5) holds. Therefore, it suffices to show that $R\leq\frac{1}{4}\gamma\tau$
holds with high probability, where

$R:=\sup_{x\in S}\frac{1}{N}\sum_{i=1}^{N}(|\Delta_{i}(x)|\wedge b).$

To that end, Talagrand’s concentration inequality for bounded empirical
processes [37] (see also [5]): there is an absolute constant $C_{T}$ such that

$\displaystyle\mathbf{P}\Big{[}R\leq
R_{1}+C_{T}\big{(}R_{2}+R_{3}+R_{4}\big{)}\Big{]}\geq 1-2\exp(-u)$

for every $u\geq 0$, where

$\displaystyle R_{1}$ $\displaystyle:=\sup_{x\in
S}\mathbf{E}[|\Delta(x)|\wedge b],$ $\displaystyle R_{2}$
$\displaystyle:=\sup_{x\in S}\mathbf{E}[(|\Delta(x)|\wedge
b)^{2}]^{\frac{1}{2}}\cdot\Big{(}\frac{u}{N}\Big{)}^{\frac{1}{2}},$
$\displaystyle R_{3}$ $\displaystyle:=\sup_{x\in S}\||\Delta(x)|\wedge
b\|_{L^{\infty}}\cdot\frac{u}{N},$ $\displaystyle R_{4}$
$\displaystyle:=\mathbf{E}\Big{[}\sup_{x\in
S}\Big{|}\frac{1}{N}\sum_{i=1}^{N}\varepsilon_{i}(|\Delta_{i}(x)|\wedge
b)\Big{|}\Big{]}.$

Thus, to conclude the proof, let us show that for $u=CN\tau\frac{l}{m}$, the
sum $R_{1}+C_{T}(R_{2}+R_{3}+R_{4})$ is smaller than $\frac{1}{4}\gamma\tau$.

We now proceed to bound $R_{1},\dots,R_{4}$. First, recall that $C_{0}$ is the
absolute constant of Lemma 4.10 which we are still able to choose as small as
we want, and note that

$\rho=\frac{C_{0}\gamma\tau\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}}}{\log(3d)\mathbf{E}[\|A\mathbb{A}^{-1}A\|_{\mathrm{op}}]}\leq\frac{C_{0}\gamma\tau}{\log(3)}\leq
C_{0}\gamma\tau,$

where the first inequality holds by Lemma 4.6 and the second one by absorbing
$\frac{1}{\log(3)}$ into $C_{0}$.

By Lemma 4.12 we have that $\mathbf{E}[|\Delta(x)|]\leq 3\rho$ for every $x\in
S$; thus

$R_{1}\leq 3\rho\leq\frac{\gamma\tau}{16}$

as soon as $C_{0}<\frac{1}{48}$.

For the terms $R_{2}$ and $R_{3}$, which involve $u=CN\tau\frac{l}{m}$, note
that

$\mathbf{E}[(|\Delta(x)|\wedge b)^{2}]\leq 3\rho b\quad\text{for every }x\in
S.$

Indeed, this follows from the trivial estimate $(|\Delta(x)|\wedge
b)^{2}\leq|\Delta(x)|b$ and Lemma 4.12 once again. Recalling that
$b=\gamma\frac{m}{l}$, we therefore have

$\displaystyle R_{2}$ $\displaystyle\leq\Big{(}\frac{3\rho
bu}{N}\Big{)}^{\frac{1}{2}}$
$\displaystyle\leq\big{(}3C_{0}C\gamma^{2}\tau^{2}\big{)}^{\frac{1}{2}}\leq\frac{\gamma\tau}{C_{T}16}$

once $C_{0}$ is small enough. Moreover,

$R_{3}\leq\frac{bu}{N}=C\gamma\tau\leq\frac{\gamma\tau}{C_{T}16}$

provided that $C$ is small enough.

Finally, by Lemma 4.13, we have $R_{4}\leq\frac{\gamma\tau}{C_{T}16}$. This
completes the proof ∎

###### Proof of Theorem 4.4.

The statement of Theorem 4.4 is clearly homogeneous in $x\in\mathbb{R}^{d}$,
hence it suffices to restrict to $x\in S$. The proof follows from a
combination of Lemma 4.8 and Lemma 4.14. Indeed, using the notation of Lemma
4.14, for every $x\in S$, $y=y(x)$, and every $J_{j}\subseteq I_{j}$ with
$|J_{j}|\leq l$, we write

$\displaystyle\frac{1}{m}\sum_{i\in I_{j}\setminus J_{j}}\langle
A_{i}x,x\rangle$ $\displaystyle\geq\frac{1}{m}\sum_{i\in
I_{j}\setminus(J_{j}\cup J_{j}^{\ast}(x))}\langle A_{i}x,x\rangle$ (4.6)
$\displaystyle\geq\frac{1}{m}\sum_{i\in I_{j}\setminus(J_{j}\cup
J_{j}^{\ast}(x))}\langle A_{i}y,y\rangle-\frac{1}{m}\sum_{i\in
I_{j}\setminus(J_{j}\cup J_{j}^{\ast}(x))}|\Delta_{i}(x)|.$

By Lemma 4.8, with probability at least $1-2\exp(-C\tau N\frac{k}{m})$, for
every $x$, $y$, and sets $J_{j}$ as above, we have that

$\frac{1}{m}\sum_{i\in I_{j}\setminus(J_{j}\cup J_{j}^{\ast}(x))}\langle
A_{i}y,y\rangle\geq 1-\frac{\gamma}{2}\quad\text{on at least
}\Big{(}1-\frac{\tau}{2}\Big{)}n\text{ blocks }.$

Next, by Lemma 4.14, with probability at least $1-2\exp(-C\tau N\frac{l}{m})$,
for every $x$, $y$, and sets $J_{j}$ as above, we have that

$\frac{1}{m}\sum_{i\in I_{j}\setminus(J_{j}\cup
J_{j}^{\ast}(x))}|\Delta_{i}(x)|\leq\frac{\gamma}{2}\quad\text{on at least
}\Big{(}1-\frac{\tau}{2}\Big{)}n\text{ blocks }.$

Taking the intersection of the two high probability events yields the claim. ∎

##  5\. Proofs of the main results

In addition to the _notational conventions_ already explained in Section 4,
set $c,c_{0},c_{1},\dots$ to be constants that may depend on $L$ (the
parameter appearing in Assumption 2.5). As before, these constants may change
their values from line to line. Moreover, $0<\theta<\tau<\frac{1}{4}$ are
constants that may depend on $L$ as well. For the sake of a clearer
presentation, rather than stating the explicit values of $\theta$ and $\tau$
now, we collect constraints on their values along the way.

Next recall that

$n=\theta
N\min\Big{\\{}1,\frac{r^{2}}{\sigma^{2}}\Big{\\}}\quad\text{and}\quad
m=\frac{N}{n},$

where we assume without loss of generality that $m$ and $n$ are integers.
Thus, $N=nm$ and $m\geq\frac{1}{\theta}$. Finally, set

$\displaystyle\mathcal{B}_{r}^{\ast}$
$\displaystyle:=\\{x\in\mathcal{X}:\|x-x^{\ast}\|\leq r\\},$
$\displaystyle\mathcal{S}_{r}^{\ast}$
$\displaystyle:=\\{x\in\mathcal{X}:\|x-x^{\ast}\|=r\\}$

to be the ball and sphere of radius $r$ around $x^{\ast}$ restricted to
$\mathcal{X}$, respectively. Recall the constant $r_{0}$ of Assumption 2.7 and
assume throughout that $r\leq r_{0}$.

The proof of Theorem 2.9 relies on the following decomposition: for every $j$
and every $x\in\mathcal{X}$, a Taylor expansion implies that

$\displaystyle\widehat{f}_{I_{j}}(x)-\widehat{f}_{I_{j}}(x^{\ast})$
$\displaystyle=\frac{1}{m}\sum_{i\in I_{j}}\langle\nabla
F(x^{\ast},\xi_{i}),x-x^{\ast}\rangle+\frac{1}{2}\frac{1}{m}\sum_{i\in
I_{j}}\langle\nabla^{2}F(z_{i},\xi_{i})(x-x^{\ast}),x-x^{\ast}\rangle$
$\displaystyle=:M_{x,x^{\ast}}(j)+\frac{1}{2}Q_{x,x^{\ast}}(j),$

where $z_{i}$ are midpoints between $x$ and $x^{\ast}$ (and each $z_{i}$ may
depend on $\xi_{i}$). For obvious reasons we call $Q_{x,x^{\ast}}$ the
_quadratic term_ and $M_{x,x^{\ast}}$ the _multiplier term_.

We start with the proof of the estimation error, formulated in Proposition
2.14. With the decomposition of
$\widehat{f}_{I_{j}}(x)-\widehat{f}_{I_{j}}(x^{\ast})$ into a multiplier and a
quadratic term at hand, the _strategy of the proof_ that $x^{\ast}$ defeats
any competitor $x\in\mathcal{S}_{r}^{\ast}$ on the $j$-th block (i.e. that
$\widehat{f}_{I_{j}}(x)-\widehat{f}_{I_{j}}(x^{\ast})>0$), consists of showing
that the quadratic term is likely to be positive (of order $r^{2}$) and the
multiplier term is likely not to be too negative:

######  Lemma 5.1.

There is a constant $c$ such that the following holds. With probability at
least $1-2\exp(-c\tau^{2}n)$, for every $x\in\mathcal{S}_{r}^{\ast}$, we have
that

(5.1)
$\displaystyle\Big{|}\Big{\\{}j:\frac{1}{2}Q_{x,x^{\ast}}(j)\geq\frac{r^{2}}{8}\Big{\\}}\Big{|}$
$\displaystyle\geq(1-\tau)n,$ (5.2)
$\displaystyle\Big{|}\Big{\\{}j:M_{x,x^{\ast}}(j)\geq-\frac{r^{2}}{16}\Big{\\}}\Big{|}$
$\displaystyle\geq(1-\tau)n.$

Let us show that Lemma 5.1 implies Proposition 2.14:

###### Proof of Proposition 2.14.

On the high probability event from Lemma 5.1, for every
$x\in\mathcal{S}_{r}^{\ast}$, we have that

$\widehat{f}_{I_{j}}(x)-\widehat{f}_{I_{j}}(x^{\ast})\geq\frac{r^{2}}{16}>0\quad\text{on
at least }(1-2\tau)n\text{ blocks }j.$

Therefore, as $\tau<\frac{1}{4}$, on that event, $x^{\ast}$ wins the match
against every $x\in\mathcal{S}_{r}^{\ast}$.

The extension to all $x\in\mathcal{X}$ with $\|x-x^{\ast}\|\geq r$ is a simple
consequence of convexity. Indeed, let $x\in\mathcal{X}$ with
$\|x-x^{\ast}\|\geq r$ and set

$y:=x^{\ast}+\frac{r}{\|x-x^{\ast}\|}(x-x^{\ast})\in\mathcal{S}_{r}^{\ast}.$

Note now that (for every sample)
$\widehat{f}_{I_{j}}(\cdot)-\widehat{f}_{I_{j}}(x^{\ast})$ is a convex
function which equals zero at $x^{\ast}$. Hence, if this function is strictly
positive in $y$, then, by convexity, it is also strictly positive on

$\\{x^{\ast}+t(y-x^{\ast}):t\geq 1\\}\cap\mathcal{X},$

which is the subset of the ray that originates from $x^{\ast}$ and passed
through $y$, consisting of the points that are “beyond” $y$. Taking
$t=\frac{1}{r}\|x-x^{\ast}\|$, we see that $x^{\ast}$ defeats $x$ (at least)
on the same blocks on which it defeats $y$. In conclusion, on the high
probability event of the lemma, $x^{\ast}$ wins the match against $x$. ∎

######  Remark 5.2.

By Assumption 2.3, the functions $F$, $\nabla F$ and $\nabla^{2}F$ are so-
called Carathéodory functions and therefore are jointly measurable. Moreover,
by Assumption 2.7 and the dominated convergence theorem, one can readily
verify that $f$ is twice continuously differentiable near $x^{\ast}$ with

$\nabla f(x)=\mathbf{E}[\nabla
F(x,\xi)]\quad\text{and}\quad\nabla^{2}f(x)=\mathbf{E}[\nabla^{2}F(x,\xi)]$

for all $x\in\mathcal{X}$ with $\|x-x^{\ast}\|<r_{0}$. In particular, from
this we get that
$\|\cdot\|=\mathbf{E}[\langle\nabla^{2}F(x^{\ast},\xi)\cdot,\cdot\rangle]^{\frac{1}{2}}$.

###  5.1. Estimation error, the quadratic term

This subsection contains the proof of (5.1) from Lemma 5.1: we show that the
quadratic term is likely to be at least of order $r^{2}$. The proof relies on
the results of Section 4 and the strategy is the following. In a first step,
we ignore the fact that the Hessian in the definition of $Q_{x,x^{\ast}}$ is
evaluated at a midpoint between $x^{\ast}$ and $x$, considering instead the
Hessian evaluated at the optimizer $x^{\ast}$. We employ the median-of-mean-
type lower bound on the smallest singular value of the random matrix
$\nabla^{2}F(x^{\ast},\xi)$ established in Section 4, which is summarized in
the following lemma.

######  Lemma 5.3.

There are constants $s_{1},c>0$ depending only on $L$ such that the following
holds. With probability at least $1-2\exp(-c\tau N)$, for every
$x\in\mathcal{S}_{r}^{\ast}$ and every choices of subsets $J_{j}\subseteq
I_{j}$ with $|J_{j}|\leq s_{1}m$, we have that

(5.3) $\displaystyle\Big{|}\Big{\\{}j:\frac{1}{m}\sum_{i\in I_{j}\setminus
J_{j}}\langle\nabla^{2}F(x^{\ast},\xi_{i})(x-x^{\ast}),x-x^{\ast}\rangle\geq\frac{r^{2}}{2}\Big{\\}}\Big{|}$
$\displaystyle\geq\Big{(}1-\frac{\tau}{2}\Big{)}n.$

###### Proof.

We apply Theorem 4.4 with $A:=\nabla^{2}F(x^{\ast},\xi)$. By Remark 4.3, the
random matrix $A$ satisfies a stable lower bound with parameters

$\Big{(}m,\frac{\gamma}{2},2l,k\Big{)}=\Big{(}m,\frac{1}{4},2s_{1}m,s_{2}m\Big{)}$

for constants $s_{1},s_{2}$ that depend only on $L$. Moreover, once $\theta$
is sufficiently small, we have that

$k=s_{2}m\geq\frac{s_{2}}{\theta}\geq\max\Big{\\{}4,2\log\Big{(}\frac{4}{\tau}\Big{)}\Big{\\}},$

showing that assumption (a) in Theorem 4.4 is satisfied. Lemma 4.7 and Lemma
4.6 imply that

$\displaystyle\max\Big{\\{}\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}},\frac{dm}{\tau
k}\log\Big{(}\frac{\log(3d)\mathbf{E}[\|A\mathbb{A}^{-1}A\|_{\mathrm{op}}]}{\gamma\tau\|\mathbf{E}[A\mathbb{A}^{-1}A]\|_{\mathrm{op}}}\Big{)}\Big{\\}}$
$\displaystyle\leq\max\Big{\\{}c_{0}d,\frac{ds_{2}}{\tau}\log\Big{(}\frac{\log(3d)2d}{\tau}\Big{)}\Big{\\}}$
$\displaystyle\leq c_{0}d\log(2d)$

for a constant $c_{0}$ that depends only $L$ and $\tau$. And, as $\tau$
depends only on $L$, $c_{0}$ actually only depends only on $L$.

Recall that Theorem 2.9 has the requirement that $N\geq c_{2}d\log(2d)$ for a
constant $c_{2}$ that may depend on $L$ and which we are free to choose to be
as large as we went. Doing so shows that assumption (b) of Theorem 4.4 holds
as well.

Setting $c:=C_{2}\min\\{s_{1},s_{2}\\}$ where $C_{2}$ is the constant from
Theorem 4.4, it follows from that theorem that (5.3) holds with probability at
least $1-2\exp(-c\tau N)$. ∎

From now on, we fix the constant $s_{1}$ from Lemma 5.3. As $s_{1}$ depends
only on $L$, all constants $\theta,\tau,c,c_{1},\dots$ which are allowed to
depend on $L$ may also depend on $s_{1}$.

In a next step, we show that replacing the Hessian at a midpoint with the
Hessian at $x^{\ast}$ does not come at a high cost. Clearly, in Lemma 5.3 we
may arbitrarily modify / delete $s_{1}m$ coordinates from each block $j$, and
we shall argue in the following that the errors

$\mathcal{E}_{\mathrm{H},i}(x)=\sup_{t\in[0,1]}\Big{|}\Big{\langle}\Big{(}\nabla^{2}F(x^{\ast}+t(x-x^{\ast}),\xi_{i})-\nabla^{2}F(x^{\ast},\xi_{i})\Big{)}(x-x^{\ast}),x-x^{\ast}\Big{\rangle}\Big{|}$

are well behaved on the remaining blocks. As before, the proof has two
components. In the first one, we analyze what happens for a single
$x\in\mathcal{S}_{r}^{\ast}$. Here the error is governed by the probability
that $\mathcal{E}_{\mathrm{H}}(x)$ is large, where we recall that $r<r_{0}$
and by Assumption 2.7

$\sup_{x\in\mathcal{S}_{r}^{\ast}}\mathbf{P}\Big{[}\mathcal{E}_{\mathrm{H}}(x)\geq\frac{r^{2}}{8}\Big{]}\leq
c_{1}$

for a constant $c_{1}$ which we are free to choose depending on $L$—hence,
$c_{1}$ may depend on $s_{1}$.

######  Lemma 5.4.

There is a constant $c$ such that, for every $x\in\mathcal{S}_{r}^{\ast}$ and
every $j$, with probability at least $1-2\exp(-cm)$, we have that

$\displaystyle\Big{|}\Big{\\{}i\in
I_{j}:\mathcal{E}_{\mathrm{H},i}(x)\leq\frac{r^{2}}{8}\Big{\\}}\Big{|}$
$\displaystyle\geq\Big{(}1-\frac{s_{1}}{2}\Big{)}m.$

###### Proof.

Fix some $x\in\mathcal{S}_{r}^{\ast}$. Setting $c_{1}:=\frac{s_{1}}{4}$,
Assumption 2.7 implies that

$\delta:=\mathbf{P}\Big{[}\mathcal{E}_{\mathrm{H}}(x)\geq\frac{r^{2}}{8}\Big{]}\leq\frac{s_{1}}{4}.$

If $\delta=0$ there is nothing to prove, so assume otherwise and apply the
Binomial concentration inequality [5, Corollary 2.11]: there is an absolute
constant $C>0$ such that, for every $u\geq 0$, with probability at least
$1-2\exp(-Cm\delta\min\\{u,u^{2}\\})$, we have that

$\Big{|}\Big{\\{}i\in
I_{j}:\mathcal{E}_{\mathrm{H},i}(x)\geq\frac{r^{2}}{8}\Big{\\}}\Big{|}\leq
m\delta(1+u).$

Applying this to $u:=\frac{s_{1}}{2\delta}-1\geq 1$ completes the proof (with
$c=\frac{Cs_{1}}{4}$). ∎

Next, let us show that most blocks have many indices $i$ for which the errors
$\mathcal{E}_{\mathrm{H},i}(x)$ are small.

######  Lemma 5.5.

There is a constant $c$ such that, for every $x\in\mathcal{S}_{r}^{\ast}$,
with probability at least $1-2\exp(-c\tau N)$, we have that

$\displaystyle\Big{|}\Big{\\{}j:\big{|}\big{\\{}i\in
I_{j}:\mathcal{E}_{\mathrm{H},i}(x)\leq\tfrac{r^{2}}{8}\big{\\}}\big{|}\geq\big{(}1-\tfrac{s_{1}}{2}\big{)}m\Big{\\}}\Big{|}$
$\displaystyle\geq\Big{(}1-\frac{\tau}{4}\Big{)}n.$

In particular, the statement holds uniformly over sets
$\bar{\mathcal{S}}_{r}^{\ast}\subseteq\mathcal{S}_{r}^{\ast}$ of cardinality
at most $\log(|\bar{\mathcal{S}}_{r}^{\ast}|)\leq\frac{1}{2}c\tau N$.

###### Proof.

Fix $x\in\mathcal{S}_{r}^{\ast}$ and, for every $j$, set

$\delta(j):=\begin{cases}1,&\text{if }|\\{i\in
I_{j}:\mathcal{E}_{\mathrm{H},i}(x)\leq\frac{1}{8}r^{2}\\}|\geq(1-\frac{1}{2}s_{1})m\\\
0,&\text{otherwise}.\end{cases}$

By Lemma 5.4 we have that

$\delta:=\mathbf{P}[\delta(j)=1]\leq 2\exp(-c_{0}m)$

for a constant $c_{0}$.

Now recall that $m\geq\frac{1}{\theta}$ and therefore $\delta\leq\frac{3}{4}$
once $\theta$ is small enough (i.e.
$\theta\leq\frac{1}{c_{0}}\log(\frac{8}{3})$ suffices). By Bennett’s
inequality, exactly as in the proof of Lemma 4.8, we have that for every
$u\geq 2$, with probability at least $1-2\exp(-C\delta nu\log(u))$,

$|\\{j:\delta(j)=1\\}|\leq u\delta n.$

To complete the proof, set $u:=\frac{\tau}{4\delta}$ so that
$u\geq\exp(\frac{c_{0}m}{2})\geq 2$, again once $\theta$ is small enough. ∎

The final step is to extend the outcome of the lemma from the net
$\bar{\mathcal{S}}_{r}^{\ast}$ to the whole $\mathcal{S}_{r}^{\ast}$. To that
end, recall that by Assumption 2.7

$\|\nabla^{2}F(x,\xi)-\nabla^{2}F(y,\xi)\|_{\mathrm{op}}\leq\|x-y\|^{\alpha}\cdot
K(\xi)$

for all $x,y\in\mathcal{B}_{r}^{\ast}$.

######  Remark 5.6.

In what follows we shall, from time to time, divide by $\mathbf{E}[K(\xi)]$;
therefore, we shall assume without loss of generality that
$\mathbf{E}[K(\xi)]>0$. Note that if $\mathbf{E}[K(\xi)]=0$ then the Hessian
is constant in $\mathcal{B}_{r}^{\ast}$ and there is nothing to prove:
$\mathcal{E}_{\mathrm{H}}(x)=0$ for every $x\in\mathcal{B}_{r}^{\ast}$.

######  Lemma 5.7.

Let $c_{0}$ be the constant of Lemma 5.5 and let $C_{0}$ be an absolute
constant to be specified later. Set

$\rho:=\Big{(}\frac{C_{0}\tau
s_{1}}{r_{0}^{\alpha}\mathbf{E}[K(\xi)]}\Big{)}^{\frac{1}{\alpha}}.$

Then $\mathcal{S}_{r}^{\ast}$ contains a $\rho r$-cover with respect to the
norm $\|\cdot\|$, which is denoted by $\bar{\mathcal{S}}_{r}^{\ast}$, and

$\log(|\bar{\mathcal{S}}_{r}^{\ast}|)\leq\frac{1}{2}c_{0}\tau N.$

###### Proof.

If $\rho\geq 1$ there is nothing to prove; thus we may assume without loss of
generality that $0<\rho<1$. By a standard volumetric argument (see e.g. [38,
Exercise 2.2.14]) there is a $\rho r$ cover
$\bar{\mathcal{S}}_{r}^{\ast}\subseteq\mathcal{S}_{r}^{\ast}$, and

$\displaystyle\log(|\bar{\mathcal{S}}_{r}^{\ast}|)$ $\displaystyle\leq
d\log\Big{(}\frac{12}{\rho}\Big{)}$
$\displaystyle=\frac{d}{\alpha}\log\Big{(}\frac{r_{0}^{\alpha}\mathbf{E}[K(\xi)]}{C_{0}\tau
s_{1}}\Big{)}.$

By assumption we have

$N\geq c_{2}N_{\mathrm{H},\mathcal{E}}\equiv
c_{2}\frac{d}{\alpha}\log\Big{(}r_{0}^{\alpha}\mathbf{E}[K(\xi)]+2\Big{)}$

for a constant $c_{2}$ which we are free to choose large enough. Then
$\log(|\bar{\mathcal{S}}_{r}^{\ast}|)\leq\frac{1}{2}c_{0}\tau N$, as claimed.
∎

######  Lemma 5.8.

Let $\bar{\mathcal{S}}_{r}^{\ast}$ be as in Lemma 5.7, and for every
$x\in\mathcal{S}_{r}^{\ast}$ set $y=y(x)$ to be the nearest point to $x$ in
$\bar{\mathcal{S}}_{r}^{\ast}$.

There is an absolute constant $C$ such that the following holds. With
probability at least $1-2\exp(-C\tau^{2}n)$, for every
$x\in\mathcal{S}_{r}^{\ast}$, we have that

$\Big{|}\Big{\\{}j:\big{|}\big{\\{}i\in
I_{j}:|\mathcal{E}_{\mathrm{H},i}(x)-\mathcal{E}_{\mathrm{H},i}(y)|\geq\tfrac{r^{2}}{8}\big{\\}}\big{|}\leq\tfrac{s_{1}m}{2}\Big{\\}}\Big{|}\geq\Big{(}1-\frac{\tau}{4}\Big{)}n.$

###### Proof.

Let

$\Psi:=\sup_{x\in\mathcal{S}_{r}^{\ast}}\frac{1}{n}\sum_{j=1}^{n}1_{|\\{i\in
I_{j}:|\mathcal{E}_{\mathrm{H},i}(x)-\mathcal{E}_{\mathrm{H},i}(y)|\geq\frac{1}{8}r^{2}\\}|\geq\frac{1}{2}s_{1}m}$

and observe that it suffices to show that
$\mathbf{P}[\Psi\geq\frac{\tau}{4}]\leq 2\exp(-C\tau^{2}n)$. By the bounded
differences inequality [5, Theorem 6.2], we have that for every $u\geq 0$,

$\mathbf{P}[\Psi\geq\mathbf{E}[\Psi]+u]\leq 2\exp(-Cnu^{2}),$

and setting $u:=\frac{\tau}{8}$, all that remains to show is that
$\mathbf{E}[\Psi]\leq\frac{\tau}{8}$.

Note that

$\displaystyle 1_{|\\{i\in
I_{j}:|\mathcal{E}_{\mathrm{H},i}(x)-\mathcal{E}_{\mathrm{H},i}(y)|\geq\frac{1}{8}r^{2}\\}|\geq\frac{1}{2}s_{1}m}$
$\displaystyle\leq\frac{16}{r^{2}s_{1}}\frac{1}{m}\sum_{i\in
I_{j}}|\mathcal{E}_{\mathrm{H},i}(x)-\mathcal{E}_{\mathrm{H},i}(y)|$

for every $j$; hence,

(5.4) $\displaystyle\Psi$
$\displaystyle\leq\frac{16}{r^{2}s_{1}}\sup_{x\in\mathcal{S}_{r}^{\ast}}\frac{1}{N}\sum_{i=1}^{N}|\mathcal{E}_{\mathrm{H},i}(x)-\mathcal{E}_{\mathrm{H},i}(y)|.$

To control the difference of the $\mathcal{E}$’s, for simpler notation, for
$(t,z)\in[0,1]\times\mathcal{S}_{r}^{\ast}$ set

$A^{tz}_{i}:=\nabla^{2}F(x^{\ast}+t(z-x^{\ast}),\xi_{i})-\nabla^{2}F(x^{\ast},\xi_{i}),$

and observe that

$\mathcal{E}_{\mathrm{H},i}(z)=\sup_{t\in[0,1]}|\langle
A^{tz}_{i}(z-x^{\ast}),z-x^{\ast}\rangle|$

for every $z\in\mathcal{S}_{r}^{\ast}$. Now, for every $t\in[0,1]$ and every
$x\in\mathcal{S}_{r}^{\ast}$ (and $y=y(x)$),

$\displaystyle\big{|}\langle A^{tx}_{i}(x-x^{\ast}),x-x^{\ast}\rangle-\langle
A^{ty}_{i}(y-x^{\ast}),y-x^{\ast}\rangle\big{|}$ $\displaystyle=\big{|}\langle
A^{tx}_{i}(x-x^{\ast}+y-x^{\ast}),x-y\rangle-\langle(A^{ty}_{i}-A^{tx}_{i})(y-x^{\ast}),y-x^{\ast}\rangle\big{|}$
$\displaystyle\leq 2\rho
r^{2}\|A^{tx}_{i}\|_{\mathrm{op}}+r^{2}\|A^{ty}_{i}-A^{tx}_{i}\|_{\mathrm{op}},$

where the last inequality holds by definition of the operator norm and by
noting that $\|x-y\|\leq\rho r$, $\|x-x^{\ast}+y-x^{\ast}\|\leq 2r$, and
$\|y-x^{\ast}\|\leq r$. Invoking the subadditivity of “$\sup_{t}(\cdot)$” and
the triangle inequality,

$\displaystyle|\mathcal{E}_{\mathrm{H}_{i}}(x)-\mathcal{E}_{\mathrm{H}_{i}}(x)|$
$\displaystyle\leq 2\rho
r^{2}\sup_{t\in[0,1]}\|A^{tx}_{i}\|_{\mathrm{op}}+r^{2}\sup_{t\in[0,1]}\|A^{ty}_{i}-A^{tx}_{i}\|_{\mathrm{op}}$
$\displaystyle\leq 2\rho
r^{2}r^{\alpha}K(\xi_{i})+r^{2}(r\rho)^{\alpha}K(\xi_{i})$ (5.5)
$\displaystyle\leq 3r^{2}(\rho r)^{\alpha}K(\xi_{i})$

where the second inequality holds by Assumption 2.7 on the continuity of the
Hessian and as we may assume without loss of generality that $\rho\leq 1$ (and
hence $\rho\leq\rho^{\alpha}$).

Plugging (5.5) into (5.4) implies that

$\displaystyle\Psi$ $\displaystyle\leq\frac{16}{r^{2}s_{1}}\cdot 3r^{2}(\rho
r)^{\alpha}\frac{1}{N}\sum_{i=1}^{N}K(\xi_{i})$

and therefore

$\displaystyle\mathbf{E}[\Psi]$
$\displaystyle\leq\frac{48\rho^{\alpha}r_{0}^{\alpha}\mathbf{E}[K(\xi)]}{s_{1}}.$

Setting

$\rho=\Big{(}\frac{C_{0}\tau
s_{1}}{r_{0}^{\alpha}\mathbf{E}[K(\xi)]}\Big{)}^{\frac{1}{\alpha}}$

just as in Lemma 5.7, and recalling that we are free to choose $C_{0}$ small
enough, it follows that $\mathbf{E}[\Psi]\leq\frac{\tau}{8}$, as required. ∎

We are now ready for the

###### Proof of Proposition 5.1, quadratic part.

For every $x\in\mathcal{S}_{r}^{\ast}$ and $j$, set

$J_{j}^{\ast}(x):=\\{\text{largest $s_{1}m$ coordinates of
}(\mathcal{E}_{\mathrm{H},i}(x))_{i\in I_{j}}\\}\subseteq I_{j}.$

For every $j$, recalling the definition of $\mathcal{E}_{\mathrm{H}}(x)$ and
the fact that $\nabla^{2}F(z,\xi)$ is positive semidefinite, it follows that

$\displaystyle Q_{x,x^{\ast}}(j)$ $\displaystyle\geq\frac{1}{m}\sum_{i\in
I_{j}\setminus
J_{j}^{\ast}(x)}\inf_{t\in[0,1]}\big{\langle}\nabla^{2}F(x^{\ast}+t(x-x^{\ast}),\xi_{i})(x-x^{\ast}),x-x^{\ast}\big{\rangle}$
$\displaystyle\geq\frac{1}{m}\sum_{i\in I_{j}\setminus
J_{j}^{\ast}(x)}\big{\langle}\nabla^{2}F(x^{\ast},\xi_{i})(x-x^{\ast}),x-x^{\ast}\big{\rangle}-\frac{1}{m}\sum_{i\in
I_{j}\setminus J_{j}^{\ast}(x)}\mathcal{E}_{\mathrm{H},i}(x)$
$\displaystyle=:A_{x}(j)+B_{x}(j)$

As $|J_{j}^{\ast}(x)|\leq s_{1}m$ for every $x\in\mathcal{S}_{r}^{\ast}$ by
definition, Lemma 5.3 implies that, with probability at least $1-2\exp(-c\tau
n)$, for every $x\in\mathcal{S}_{r}^{\ast}$, we have that

$A_{x}(j)\geq\frac{r^{2}}{2}\quad\text{on more than
}\Big{(}1-\frac{\tau}{2}\Big{)}n\text{ of the blocks }j.$

Moreover, combining Lemma 5.5 and Lemma 5.8 implies that, with probability at
least $1-2\exp(-c\tau^{2}n)$, for every $x\in\mathcal{S}_{r}^{\ast}$, we have
that

$\displaystyle\Big{|}\Big{\\{}j:\big{|}\big{\\{}i\in
I_{j}:\mathcal{E}_{\mathrm{H},i}(x)\leq\tfrac{r^{2}}{4}\big{\\}}\big{|}\geq(1-s_{1})m\Big{\\}}\Big{|}$
$\displaystyle\geq\Big{(}1-\frac{\tau}{2}\Big{)}n,$

and on that event clearly

$B_{x}(j)\geq-\frac{r^{2}}{4}\quad\text{on more than
}\Big{(}1-\frac{\tau}{2}\Big{)}n\text{ of the blocks }j.$

In particular, combining the estimates on $A_{x}(j)$ and $B_{x}(j)$ gives:
with probability at least $1-2\exp(-c\tau^{2}n)$, for every
$x\in\mathcal{S}_{r}^{\ast}$, we have that

$Q_{x,x^{\ast}}(j)\geq\frac{r^{2}}{4}\quad\text{on more than }(1-\tau)n\text{
of the blocks }j.$

This completes the proof. ∎

###  5.2. Estimation error, the multiplier term

This subsection contains the proof of (5.2) from Lemma 5.1, stating that the
multiplier term

$M_{x,x^{\ast}}(j)=\frac{1}{m}\sum_{i\in I_{j}}\langle\nabla
F(x^{\ast},\xi_{i}),x-x^{\ast}\rangle$

is likely to be at most of order $r^{2}$. To ease notation, set

$\displaystyle\mathbb{H}$
$\displaystyle:=\nabla^{2}f(x^{\ast})=\mathbf{E}[\nabla^{2}F(x^{\ast},\xi)],$
$\displaystyle\mathbb{G}$ $\displaystyle:=\mathrm{\mathbf{C}ov}[\nabla
F(x^{\ast},\xi)],$

ı.e., $\mathbb{H}$ is the Hessian of $f$ at $x^{\ast}$ and $\mathbb{G}$ is the
covariance matrix of the gradient of $F(\cdot,\xi)$ at $x^{\ast}$. In
particular, a straightforward computation shows that

(5.6) $\displaystyle N_{\mathrm{G}}(r)$
$\displaystyle=\frac{1}{r^{2}}\mathrm{trace}(\mathbb{H}^{-1}\mathbb{G})=\frac{1}{r^{2}}\mathrm{trace}(\mathbb{H}^{-\frac{1}{2}}\mathbb{G}\mathbb{H}^{-\frac{1}{2}}),$
(5.7)
$\displaystyle\begin{split}\sigma^{2}&=\lambda_{\max}(\mathbb{H}^{-1}\mathbb{G})\\\
&=\lambda_{\max}(\mathbb{H}^{-\frac{1}{2}}\mathbb{G}\mathbb{H}^{-\frac{1}{2}})=\|\mathbb{G}\|_{\mathrm{op}}.\end{split}$

As before, we analyze what happens for a single $x\in\mathcal{S}_{r}^{\ast}$;
the high probability estimate we obtain allows us to control a net in
$\mathcal{S}_{r}^{\ast}$; we then show that passing from the net to the entire
set $\mathcal{S}_{r}^{\ast}$ does not distort the outcome by too much.

######  Lemma 5.9.

There is an absolute constant $C$ such that, for every
$x\in\mathcal{S}_{r}^{\ast}$, with probability at least
$1-2\exp(-C\tau^{2}n)$, we have that

$\Big{|}\Big{\\{}j:M_{x,x^{\ast}}(j)\geq-\frac{r^{2}}{32}\Big{\\}}|\geq\Big{(}1-\frac{\tau}{2}\Big{)}n.$

In particular, the statement holds uniformly over a set
$\bar{\mathcal{S}}_{r}^{\ast}\subseteq\mathcal{S}_{r}^{\ast}$ of cardinality
at most
$\log(\frac{1}{2}|\bar{\mathcal{S}}_{r}^{\ast}|)\leq\frac{1}{2}C\tau^{2}n$.

###### Proof.

Fix some $x\in\mathcal{S}_{r}^{\ast}$ and define for $1\leq i\leq N$,

$\displaystyle U_{i}$ $\displaystyle:=\langle\nabla
F(x^{\ast},\xi_{i})-\mathbf{E}[\nabla F(x^{\ast},\xi)],x-x^{\ast}\rangle$
$\displaystyle=\langle\nabla
F(x^{\ast},\xi_{i}),x-x^{\ast}\rangle-\langle\nabla
f(x^{\ast}),x-x^{\ast}\rangle.$

If $x^{\ast}$ lies in the interior of $\mathcal{X}$, the first order condition
for optimality implies that $\langle\nabla f(x^{\ast}),x-x^{\ast}\rangle$
equals zero. In general, the first order condition implies that this term is
non-negative. In either case, we get that

$\displaystyle\Big{|}\frac{1}{m}\sum_{i\in I_{j}}U_{i}\Big{|}$
$\displaystyle\leq\frac{r^{2}}{32}\quad\text{implies}\quad
M_{x,x^{\ast}}(j)\geq-\frac{r^{2}}{32}$

and we shall show that the former happens on most blocks.

To that end, consider first a single block $j$. As the $U_{i}$’s are i.i.d.
zero mean random variables, Markov’s inequality together with the Cauchy-
Schwartz inequality implies that

(5.8) $\displaystyle\begin{split}\mathbf{P}\Big{[}\Big{|}\frac{1}{m}\sum_{i\in
I_{j}}U_{i}\Big{|}\geq\frac{r^{2}}{32}\Big{]}&\leq\frac{32}{r^{2}}\mathbf{E}\Big{[}\Big{|}\frac{1}{m}\sum_{i\in
I_{j}}U_{i}\Big{|}\Big{]}\\\
&\leq\frac{32}{r^{2}}\Big{(}\frac{\mathbf{E}[|U_{1}|^{2}]}{m}\Big{)}^{\frac{1}{2}}.\end{split}$

By the definition of $\sigma$ (or rather, by the alternative expression in
(5.7)) and as $\|x-x^{\ast}\|=r$, we have that

(5.9)
$\displaystyle\begin{split}\mathbf{E}[|U_{1}|^{2}]&=\langle\mathbb{G}(x-x^{\ast}),x-x^{\ast}\rangle\\\
&\leq r^{2}\sigma^{2}.\end{split}$

Combining (5.8) and (5.9) and using that $m\geq\tfrac{\sigma^{2}}{\theta
r^{2}}$, we conclude that

$\displaystyle\mathbf{P}\Big{[}\Big{|}\frac{1}{m}\sum_{i\in
I_{j}}U_{i}\Big{|}\geq\frac{r^{2}}{32}\Big{]}$
$\displaystyle\leq\frac{32r\sigma}{r^{2}\sqrt{m}}$ $\displaystyle\leq
32\sqrt{\theta}\leq\frac{\tau}{4}$

as soon as $\theta$ is sufficiently small.

The claim now follows from a Binomial estimate—just as in the proof of Lemma
5.4: the probability that a single block $j$ has the wanted property is at
least $1-\frac{\tau}{4}$ (by the above); therefore, the probability that the
number of desirable blocks $j$ is smaller than the mean (which is at least
$(1-\frac{\tau}{4})n$) by more than $\frac{\tau}{4}n$ is at most
$2\exp(-Cn\tau^{2})$. ∎

######  Lemma 5.10.

Let $C_{0}$ be the absolute constant of Lemma 5.9. Then there is an absolute
constant $C_{1}$ and a set
$\bar{\mathcal{S}}_{r}^{\ast}\subseteq\mathcal{S}_{r}^{\ast}$ with cardinality
$\log(\frac{1}{2}|\bar{\mathcal{S}}_{r}^{\ast}|)\leq\frac{1}{2}C_{0}n\tau^{2}$
such that the following holds. Let

$\rho:=\Big{(}\frac{\mathrm{trace}(\mathbb{H}^{-1}\mathbb{G})}{C_{1}\tau^{2}n}\Big{)}^{\frac{1}{2}}.$

For every $x\in\mathcal{S}_{r}^{\ast}$ there is
$y=y(x)\in\bar{\mathcal{S}}_{r}^{\ast}$ with

(5.10) $\displaystyle\langle\mathbb{G}(x-y),x-y\rangle^{\frac{1}{2}}$
$\displaystyle\leq 2\rho r\quad\text{and },$ (5.11)
$\displaystyle\langle\nabla f(x^{\ast}),x-y\rangle$ $\displaystyle\geq 0.$

###### Proof.

As a first step, we ignore (5.11) and construct a set
$\tilde{\mathcal{S}}_{r}^{\ast}$ with log-cardinality satisfying
$\log(\frac{1}{2}|\tilde{\mathcal{S}}_{r}^{\ast}|)\leq\frac{1}{2}C_{0}n\tau^{2}$
such that (5.10) holds with $\rho r$ instead of $2\rho r$. To that end,
observe that covering the sphere
$\\{x\in\mathbb{R}^{d}:\langle\mathbb{H}x,x\rangle=1\\}$ w.r.t. to the norm
endowed by $\mathbb{G}$ is equivalent to covering the Euclidean sphere
$\\{x\in\mathbb{R}^{d}:\langle x,x\rangle=1\\}$ w.r.t. the norm endowed by
$\mathbb{H}^{-\frac{1}{2}}\mathbb{G}\mathbb{H}^{-\frac{1}{2}}$. Hence,
denoting by $\mathcal{G}$ the standard Gaussian vector in $\mathbb{R}^{d}$,
the dual Sudakov inequality (see e.g. [16, Theorem 3.18]) guarantees the
existence of a $\rho r$ cover of
$\tilde{\mathcal{S}}_{r}^{\ast}\subseteq\mathcal{S}_{r}^{\ast}$ with respect
to the norm $\langle\mathbb{G}\cdot,\cdot\rangle^{\frac{1}{2}}$ such that

$\log\Big{(}\frac{|\tilde{\mathcal{S}}_{r}^{\ast}|}{2}\Big{)}\leq
C_{2}\Big{(}\frac{\mathbf{E}[\langle\mathbb{H}^{-\frac{1}{2}}\mathbb{G}\mathbb{H}^{-\frac{1}{2}}\mathcal{G},\mathcal{G}\rangle^{\frac{1}{2}}]}{\rho}\Big{)}^{2};$

thus, for every $x\in\mathcal{S}^{\ast}_{r}$ there is
$y=y(x)\in\tilde{\mathcal{S}}_{r}^{\ast}$ with
$\langle\mathbb{G}(y-x),y-x\rangle^{\frac{1}{2}}\leq\rho r$. Observe that

$\displaystyle\mathbf{E}[\langle\mathbb{H}^{-\frac{1}{2}}\mathbb{G}\mathbb{H}^{-\frac{1}{2}}\mathcal{G},\mathcal{G}\rangle^{\frac{1}{2}}]^{2}$
$\displaystyle=\mathbf{E}[\|(\mathbb{H}^{-\frac{1}{2}}\mathbb{G}\mathbb{H}^{-\frac{1}{2}})^{\frac{1}{2}}\mathcal{G}\|_{2}]^{2}$
$\displaystyle\leq\mathbf{E}[\|(\mathbb{H}^{-\frac{1}{2}}\mathbb{G}\mathbb{H}^{-\frac{1}{2}})^{\frac{1}{2}}\mathcal{G}\|_{2}^{2}]$
$\displaystyle=\mathop{\mathrm{trace}}(\mathbb{H}^{-\frac{1}{2}}\mathbb{G}\mathbb{H}^{-\frac{1}{2}})=\mathrm{trace}(\mathbb{H}^{-1}\mathbb{G}),$

(where the last equality was already observed in (5.6)). Thus,

$\displaystyle\begin{split}\log\Big{(}\frac{|\tilde{\mathcal{S}}_{r}^{\ast}|}{2}\Big{)}&\leq\frac{C_{2}\mathrm{trace}(\mathbb{H}^{-1}\mathbb{G})}{\rho^{2}}\\\
&=C_{2}C_{1}\tau^{2}n\leq\frac{1}{2}C_{0}\tau^{2}n,\end{split}$

once $C_{1}$ is sufficiency small.

Next, we modify $\tilde{\mathcal{S}}_{r}^{\ast}$, ensuring that both equations
(5.10) and (5.11) hold: for every $z\in\tilde{\mathcal{S}}_{r}^{\ast}$, pick
some

$y(z)\in\mathop{\mathrm{argmin}}\Big{\\{}\langle\nabla
f(x^{\ast}),y\rangle:y\in\mathcal{S}_{r}^{\ast}\text{ s.t.\
}\langle\mathbb{G}(y-z),(y-z)\rangle^{\frac{1}{2}}\leq\rho r\Big{\\}};$

thus, $y(z)$ is the minimizer of $\langle\nabla f(x^{\ast}),y\rangle$ with the
$\rho r$-ball (with respect to the norm
$\langle\mathbb{G}\cdot,\cdot\rangle^{\frac{1}{2}}$) centred at $z$.

It is straightforward to verify that the set

$\bar{\mathcal{S}}_{r}^{\ast}:=\\{y(z):z\in\tilde{\mathcal{S}}_{r}^{\ast}\\}$

satisfies the statement of the lemma. ∎

######  Lemma 5.11.

Let $\bar{\mathcal{S}}_{r}^{\ast}$ and $y=y(x)$ be as in Lemma 5.10. There is
an absolute constant $C$ such that the following holds. With probability at
least $1-2\exp(-C\tau^{2}n)$, for every $x\in\mathcal{S}_{r}^{\ast}$, we have
that

$\Big{|}\Big{\\{}j:M_{x,x^{\ast}}(j)\geq
M_{y,x^{\ast}}(j)-\frac{r^{2}}{32}\Big{\\}}\Big{|}\geq\Big{(}1-\frac{\tau}{2}\Big{)}n.$

###### Proof.

For every $x\in\mathcal{X}$ and $j$, set

$\displaystyle\Delta_{x}(j)$
$\displaystyle:=M_{x,x^{\ast}}(j)-M_{y,x^{\ast}}(j)$
$\displaystyle\bar{\Delta}_{x}(j)$
$\displaystyle:=\Delta_{x}(j)-\mathbf{E}[\Delta_{x}(j)]$
$\displaystyle=\frac{1}{m}\sum_{i\in I_{j}}\langle\nabla
F(x^{\ast},\xi_{i})-\mathbf{E}[\nabla F(x^{\ast},\xi)],x-y\rangle.$

Recalling that $\mathbf{E}[\Delta_{x}(j)]\geq 0$ by Lemma 5.10 and setting

$\Psi:=\sup_{x\in\mathcal{S}_{r}^{\ast}}\frac{1}{n}\sum_{j=1}^{n}1_{\\{|\bar{\Delta}_{x}(j)|\geq\frac{1}{32}r^{2}\\}},$

the statement of the lemma therefore follows if $\Psi\leq\frac{\tau}{2}$ holds
with probability at least $1-2\exp(-C\tau^{2}n)$.

To that end, we once more rely on the bounded difference inequality [5,
Theorem 6.2]: for every $u\geq 0$, we have that

$\mathbf{P}[\Psi\geq\mathbf{E}[\Psi]+u]\leq 2\exp(-Cnu^{2}).$

Setting $u:=\frac{\tau}{4}$, all that is left is to show that
$\mathbf{E}[\Psi]\leq\frac{\tau}{4}$.

First, observe that $1_{|a|\geq b}\leq\frac{1}{b}|a|$. Hence,

$\displaystyle\Psi$
$\displaystyle\leq\frac{32}{r^{2}}\sup_{x\in\mathcal{S}_{r}^{\ast}}\frac{1}{n}\sum_{j=1}^{n}|\bar{\Delta}_{x}(j)|$
$\displaystyle\leq\frac{32}{r^{2}}\Big{(}\sup_{x\in\mathcal{S}_{r}^{\ast}}\mathbf{E}[|\bar{\Delta}_{x}(1)|]+\sup_{x\in\mathcal{S}_{r}^{\ast}}\frac{1}{n}\sum_{j=1}^{n}\Big{|}\bar{\Delta}_{x}(j)\big{|}-\mathbf{E}[|\bar{\Delta}_{x}(j)|]\Big{|}\Big{)}$
$\displaystyle=:\frac{32}{r^{2}}\Big{(}R_{1}+R_{2}\Big{)}.$

In particular $\mathbf{E}[\Psi]\leq\frac{32}{r^{2}}(R_{1}+\mathbf{E}[R_{2}])$.

To estimate $R_{1}$, recall that $\bar{\Delta}_{x}(j)$ is a sum of
independent, zero mean random variables. Thus,

$\displaystyle\mathbf{E}[|\bar{\Delta}_{x}(1)|]$
$\displaystyle\leq\Big{(}\frac{\langle\mathbb{G}(x-y),x-y\rangle}{m}\Big{)}^{\frac{1}{2}}$
$\displaystyle\leq