\section{Proof of Corollary \ref{cor::gap}} \label{sec:proofcorollary}

Consider the two following functions:
\begin{align*}
	f(C) & = \min_{X \in \mathcal{C}} \dotprod{C, X}, &
	h(C) & = \max_{X \in \mathcal{C}} \dotprod{C, X}.
\end{align*}
By assumption on $X$,
\begin{align*}
	\dotprod{C, X} - \dotprod{-W, X} = \dotprod{(C+W), X} \leq f(C+W) + \varepsilon_f.
\end{align*}
We can rearrange and get:
\begin{align*}
	\dotprod{C, X} \leq f(C+W) + \varepsilon_f + \dotprod{-W, X} \leq f(C+W) + \varepsilon_f + h(-W).
\end{align*}
Moreover,
\begin{align*}
 f(C+W) & = \min_{X \in \mathcal{C}} \left( \dotprod{C, X} + \dotprod{W, X} \right) \leq f(C) + h(W).
\end{align*}
Overall, we get a bound on the optimality gap, using that $f(C) = f^\star$:
\begin{align*}
	\dotprod{C, X} - f^\star \leq \varepsilon_f + h(W) + h(-W).
\end{align*}
To conclude, observe that
\begin{align*}
	h(W) = \max_{X \in \mathcal{C}} \dotprod{W, X} \leq \|W\|_{\mathrm{op}} \max_{X \in \mathcal{C}} \Tr{X} \leq \|W\|_{\mathrm{op}}R,
\end{align*}
where we used that $\Tr{X} \leq R$ for all $X \in \mathcal{C}$. The same bound applies to $h(-W)$.
{"config": "arxiv", "file": "1806.03763/AppendixF.tex"}