concave}
	Let $f:\mathbb{R}^d\mapsto\mathbb{R}$ be a concave function with maximizer $x^*$ over the convex set $\mc{C}$. Further, assume that $f$ is $G$-strongly concave with respect to $\ell_2$ norm in region $\mc{S}\cap\mc{C}$, where $\mathcal{S}=\Bp{x:\Norm{x-x^*}_2\leq A}$. If $f(x^*)-f(x)\leq\frac{AG}{2}$ and $c\in\mc{C}$, then $x\in\mathcal{S}$.
\end{lemma}
\begin{proof}
	By property of strong concavity, we know that, $f(x^*)-f(x)\geq\frac{G}{2}\Norm{x-x^*}_2$ for any $x\in\mathcal{S}\cap\mc{C}$. Now, suppose $x'$ satisfies $f(x^*)-f(x')\leq\frac{AG}{2}$, $x'\in\mc{C}$ and $x'\notin\mathcal{S}$. Then, we must have $\Norm{x'-x^*}_2>A$.
	
	Let $\gamma\in(0, 1)$ be some number such that $z=\gamma x'+(1-\gamma)x^*$ lies on the boundary of $\mathcal{S}$. By convexity, we also have $z\in\mc{C}$. Then, since $f$ is concave, we have $f(z)\geq\gamma f(x')+(1-\gamma)f(x^*)> f(x')$, where the second inequality is strict because $f$ is strongly concave in a region around $x^*$. Since $f(x^*)-f(x')\leq\frac{AG}{2}$, $f$ is $G$-strongly concave on $\mathcal{S}$ and $z$ lies on the boundary of $\mathcal{S}$, we have
	$$\frac{AG}{2}=\frac{G}{2}\Norm{z-x^*}_2\leq f(x^*)-f(z)< f(x^*)-f(x')\leq\frac{AG}{2}.$$
	This is a contradiction and thus we must have $x'\in\mathcal{S}$.
\end{proof}

The following lemma quantitatively describes how close $\widetilde{\Lambda}$ and $\Lambda^*$ needs to be to ensure an at most $\epsilon$ multiplicative constraint violation.
\begin{lemma}
\label{lmm:opt_guarantees}
Assume $\Norm{x}_2\leq M$ for any $x\in\mathcal{X}$. Let $\Sigma=\mathbb{E}_{X\sim\nu}\Mp{XX^\top}\succ\mathbf{0}$ and $\Lambda^*=\argmax_{\Lambda\succeq\bm{0}}\overline{D}(\Lambda)$. Then, for any $\epsilon>0$, if we have
$$\Norm{\widetilde{\Lambda}-\Lambda^*}_F\leq\frac{8\mu^2\lambda_{\min}(\Sigma)}{3M^2\lambda_{\max}(\Sigma)}\cdot\frac{\epsilon}{1+\epsilon},$$
then it holds that $y^\top\mathbb{E}_{X\sim\nu}\Mp{P_{\widetilde{\Lambda}}(X)XX^\top}^{-1}y\leq (1+\epsilon)c_\ell^2$ for any $y\in\mathcal{Y}_\ell$.
\end{lemma}
\begin{proof}
    Fix some $\epsilon>0$. First, notice that if we regard $P_\Lambda$ as a function of $q_\Lambda(x)=x^\top\Lambda x-1$, it then holds that
    $$\Norm{\nabla_{\Lambda}P_{\Lambda}(x)}_2=\Norm{\frac{\mathrm{d}P_{\Lambda}}{\mathrm{d}q_{\Lambda}}\nabla_{\Lambda}q_{\Lambda}(x)}_2\leq\abs{\frac{\mathrm{d}P_{\Lambda}}{\mathrm{d}q_{\Lambda}}}\Norm{xx^\top}_2\leq \abs{\frac{\mathrm{d}P_{\Lambda}}{\mathrm{d}q_{\Lambda}}}M^2\leq\frac{M^2}{8\mu},$$
    where we obtain the last inequality by using Lemma \ref{lmm:P_property}. Therefore, for any $x\in\mc{X}$ and $\widetilde{\Lambda}\succeq\bm{0}$, we have $\abs{P_{\widetilde{\Lambda}}(x)-P_{\Lambda^*}(x)}\leq\frac{M^2}{8\mu}\cdot\Norm{\widetilde{\Lambda}-\Lambda^*}_F$ by mean value theorem and Cauchy-Schwartz. inequality.
    
    Therefore, if we have $\Norm{\widetilde{\Lambda}-\Lambda^*}_F\leq\delta$, then 
    $$\abs{P_{\widetilde{\Lambda}}(x)-P_{\Lambda^*}(x)}\leq\frac{M^2\delta}{8\mu}\implies P_{\widetilde{\Lambda}}(x)\geq P_{\Lambda^*}(x)-\frac{M^2\delta}{8\mu}$$
    $$\implies\mathbb{E}_{X\sim\nu}\Mp{P_{\widetilde{\Lambda}}(X)XX^\top}\succeq\mathbb{E}_{X\sim\nu}\Mp{P_{\Lambda^*}(X)XX^\top}-\frac{M^2\delta}{8\mu}\mathbb{E}_{X\sim\nu}\Mp{XX^\top}.$$
    By Lemma \ref{lmm:schur_property}, we know that
    \begin{equation}
        \label{equ:ep_constraint}
        y^\top\mathbb{E}_{X\sim\nu}\Mp{P_{\widetilde{\Lambda}}(X)XX^\top}^{-1}y\leq c_\ell^2(1+\epsilon)\Longleftrightarrow\mathbb{E}_{X\sim\nu}\Mp{P_{\widetilde{\Lambda}}(X)XX^\top}\succeq\frac{yy^\top}{(1+\epsilon)c_\ell^2}.
    \end{equation}
    Let $\Sigma^*=\mathbb{E}_{X\sim\nu}\Mp{P_{\Lambda^*}(X)XX^\top}$. Therefore, to guarantee the condition in Eq. \eqref{equ:ep_constraint}, it is sufficient to guarantee that $\Sigma^*-\frac{M^2\delta}{8\mu}\Sigma\succeq\frac{yy^\top}{(1+\epsilon)c_\ell^2}$, which is equivalent to
    $$w^\top\Sigma^* w-\frac{M^2\delta}{8\mu}w^\top\Sigma w\geq\frac{(w^\top y)^2}{c_\ell^2(1+\epsilon)},\quad\forall\text{unit vector }w\in\mathbb{R}^d$$
    $$\Longleftrightarrow \frac{1}{w^\top\Sigma w}\cdot w^\top\Sp{\Sigma^*-\frac{yy^\top}{(1+\epsilon)c_\ell^2}}w\geq\frac{M^2\delta}{8\mu},\quad\forall\text{unit vector }w\in\mathbb{R}^d.$$
    
    Therefore, it is sufficient to choose $\delta$ such that
    $$\frac{M^2\delta}{8\mu}\leq \frac{1}{\lambda_{\max}(\Sigma)}\cdot \lambda_{\min}\Sp{\Sigma^*-\frac{yy^\top}{c_\ell^2(1+\epsilon)}}\leq\min_{w:\Norm{w}_2=1}\frac{1}{w^\top\Sigma w}\cdot w^\top\Sp{\Sigma^*-\frac{yy^\top}{(1+\epsilon)c_\ell^2}}w.$$
    Since $P_{\Lambda^*}$ satisfies the constraint defined in problem \eqref{equ:opt_barrier_2}, we have $\Sigma^*\succeq\frac{yy^\top}{c_\ell^2}$. Meanwhile, by Lemma \ref{lmm:P_property}, we know that $P_{\Lambda^*}(x)\geq\frac{\mu}{3}$ for any $x\in\mc{X}$, which means that $\Sigma^*\succeq\frac{\mu}{3}\cdot\Sigma$. That is, for any unit vector $w\in\mathbb{R}^d$, we have
    $$w^\top\Sigma^*w\geq\frac{\Sp{w^\top y}^2}{c_\ell^2}\quad\text{and}\quad w^\top\Sigma^*w\geq\frac{\mu}{3}\lambda_{\min}\Sp{\Sigma},$$
    which together implies $w^\top\Sigma^*w\geq\max\Bp{\frac{\mu}{3}\cdot\lambda_{\min}(\Sigma), \frac{\Sp{w^\top y}^2}{c_\ell^2}}$. Therefore, it holds that
    \begin{align*}
        w^\top\Sigma w-\frac{\Sp{w^\top y}^2}{(1+\epsilon)c_\ell^2}&\geq \max\Bp{\frac{\mu}{3}\cdot\lambda_{\min}(\Sigma), \frac{\Sp{w^\top y}^2}{c_\ell^2}}-\frac