This result is rather surprising. While the empirical expectation is clearly convex when the loss is convex, the empirical standard deviation \(x \rightarrow \sqrt{\mathrm {Var}_{\hat{\mathbb {P}}_T}(\ell (x,\xi ))}\)  is in general non-convex even when the loss is convex [1]}, [2]}, [3]}. This implies that SVP is a sum of a convex and a non-convex function which is, in general, not convex. However, Proposition REF  shows that when the scaling \(\sqrt{2a_T/T}\)  of the standard deviation is small enough, the SVP predictor becomes convex (see Figure REF  for an illustration). Furthermore, the threshold of scaling for convexity is exactly the scaling for which the ellipsoid \(\left\lbrace \mathbb {P}^{\prime }\; : \;\Vert \mathbb {P}^{\prime }-\hat{\mathbb {P}}_T\Vert ^2_{\hat{\mathbb {P}}_T}\le \frac{a_T}{T}\right\rbrace \)  of the DRO expression of the SVP predictor (REF ) is contained in the probability simplex \(\mathcal {P}\) .
This result admits also a probabilistic interpretation which can be traced back to [2]}. As the empirical distribution \(\hat{\mathbb {P}}_T\)  is close to \(\mathbb {P}\in \mathcal {P}^{\mathrm {o}}\)  with increasing probability with \(T\) , and the scaling \(\sqrt{2a_T/T}\)  converges to 0 (subexponential regime), the convexity condition is verified with increasingly high probability with \(T\) . Hence, the SVP predictor is convex with high probability.
<FIGURE>