\section{Proof of Lemma~\ref{lemma:SubOptFeas}}\label{appendix:OptFeasLin}
\begin{comment}
\subsection{Proof of Lemma~\ref{lemma:boundOnCf} (Bound on Curvature Constant)}\label{appendix:BoundonCf}
Here we derive an upper bound on the curvature constant of the concave function, $g(\cdot)$. Let $f(\cdot) = -g(\cdot)$ be a convex function, for which the second order condition is written as,
\begin{equation*}
f(\mathcal{B}(Y)) \leq f(\mathcal{B}(X)) + \nabla f(\mathcal{B}(X))^T (Y-X) + 
\frac{1}{2} (Y-X)^T\nabla^2 f(\mathcal{B}(X)) (Y-X)
\end{equation*}
and the curvature constant of $g(\cdot)$ is,
\begin{equation*}
\begin{split}
C_f &= \sup_{\substack{X,S\in \mathcal{S},\\ Y = X + \gamma(S-X),\\ \gamma \in [0,1]}} \frac{2}{\gamma^2} (f(\mathcal{B}(Y)) - f(\mathcal{B}(X)) - \nabla f(\mathcal{B}(X))^T (Y-X))\\
&\leq \sup \frac{1}{\gamma^2} (Y-X)^T\nabla^2 f(\mathcal{B}(X)) (Y-X)\\
&\leq \lambda_{\textup{max}} (\nabla^2 f(X)) \alpha^2.
\end{split}
\end{equation*}

Let $z \in \mathbb{R}^{2d}$ be a vector such that $z_i = e^{M(\mathcal{A}(X)_i - b_i)}$ and $z_{d+i} = e^{M(b_i - \mathcal{A}(X)_i)}$. This is done for the simplicity of writing the expressions in the proof.

The function, $f(\cdot)$, is then defined as,
\begin{equation}
f(\mathcal{B}(X)) = -\langle C, X\rangle + \frac{\beta}{M}\log \sum_{i=1}^{d}(z_i+z_{d+i}).
\end{equation}

The first and second derivatives are respectively written as,
\begin{equation*}
\nabla f(\mathcal{B}(X)) = -C + \frac{\beta}{\sum_{i=1}^{d}(z_i+z_{d+i})} \sum_{i=1}^{d} A_i (z_i - z_{d+i}),
\end{equation*}
and
\begin{equation*}
\begin{split}
\nabla^2 f(\mathcal{B}(X)) &= \frac{\beta}{\left(\sum_{i=1}^{d}(z_i+z_{d+i})\right)^2} \sum_{j=1}^{d}\sum_{i=1}^{d} M A_i\cdot A_j (z_j - z_{d+j}) (z_i - z_{d+i})\\
&\ \ \ + \frac{\beta}{\sum_{i=1}^{d}(z_i+z_{d+i})} \sum_{i=1}^{d} M A_i \cdot A_i (z_i + z_{d+i})\\
&\preceq \frac{\beta M}{\sum_{i=1}^{d}(z_i+z_{d+i})} \sum_{i=1}^{d} A_i \cdot A_i (z_i + z_{d+i}).\\
\end{split}
\end{equation*}

Thus, $\lambda_{\textup{max}}(\nabla^2 f(\mathcal{B}(X))) \leq \beta M \lambda_{\textup{max}}\left(\frac{1}{\sum_{i=1}^{d}(z_i+z_{d+i})} \sum_{i=1}^{d} A_i \cdot A_i (z_i + z_{d+i})\right) \leq \beta M \omega^2$. The last inequality follows since we have convex combination of $A_i \cdot A_i$ here. Thus, we have
\begin{equation*}
\begin{split}
C_g &= C_f\\
&\leq M\beta \omega^2 \alpha^2.
\end{split}
\end{equation*}
\end{comment}

\begin{proof}
There are three inequalities to prove.

\paragraph{Lower bound on the objective function value, $\langle C, \widehat{X}_{\epsilon} \rangle$.}
Let $X^\star_{FW}$ be an optimal solution to~\eqref{prob:LogPenalty}. After the stopping criteria of Algorithm~\ref{Algo1} is satisfied, the following holds:
\begin{equation}\label{eqn:SubOptimalSolPenaltyProb}
g(\mathcal{B}(\widehat{X}_{\epsilon})) \geq g(\mathcal{B}(X^{\star}_{FW})) - \epsilon \geq g(\mathcal{B}(X^{\star}_{SDP})) - \epsilon
\end{equation}
since $X^{\star}_{SDP}$ is feasible for~\eqref{prob:LogPenalty}. Thus,
\begin{equation}
\langle C, \widehat{X}_{\epsilon} \rangle - \beta \phi_M (\mathcal{A}(\widehat{X}_{\epsilon})-b) \geq \langle C, X^{\star}_{SDP}\rangle - \beta \phi_M (\mathcal{A}(X^{\star}_{SDP})-b) - \epsilon.
\end{equation}
The lower bound in~\eqref{eqn:OptBound} follows since $\phi_M(\mathcal{A}(X^{\star}_{SDP})-b) \leq \phi_M(\mathcal{A}(\widehat{X}_{\epsilon})-b)$.

\paragraph{Upper bound on the objective function value, $\langle C, \widehat{X}_{\epsilon} \rangle$.} 
Let the Lagrangian of~\eqref{prob:SDPlin} be defined as
\begin{equation*}
L(X,y) = \langle C,X\rangle - y^T(\mathcal{A}(X) - b).
\end{equation*}


For a primal-dual optimal pair, ($X^{\star}_{SDP},y^{\star}_{SDP}$) and any $X\succeq 0$, the following holds,
\begin{equation}\label{eqn:LagrangianIneq}
L(X,y^{\star}_{SDP}) \leq L(X^{\star}_{SDP},y^{\star}_{SDP}).
\end{equation}


Since $\widehat{X}_{\epsilon}\succeq 0$, from~\eqref{eqn:LagrangianIneq}, we can write
\begin{equation}
\begin{split}
\langle C, \widehat{X}_{\epsilon} \rangle - y^{\star T}_{SDP}(\mathcal{A}(\widehat{X}_{\epsilon}) - b) &\leq \langle C, X^{\star}_{SDP}\rangle - y^{\star T}_{SDP}(\mathcal{A}(X^{\star}_{SDP}) - b)\\
&= \langle C, X^{\star}_{SDP}\rangle.
\end{split}
\end{equation}

The upper bound on $\langle C, \widehat{X}_{\epsilon} \rangle$ can be written as,
\begin{align}
\langle C, \widehat{X}_{\epsilon} \rangle &\leq \langle C, X^{\star}_{SDP}\rangle + y^{\star T}_{SDP}(\mathcal{A}(\widehat{X}_{\epsilon}) - b)\\
&\leq \langle C, X^{\star}_{SDP}\rangle + \| y^{\star}_{SDP} \|_1 \| \mathcal{A}(\widehat{X}_{\epsilon}) - b\|_{\infty}. \label{eqn:upperbound}
\end{align}

\paragraph{Bound on infeasibility, $\| \mathcal{A}(\widehat{X}_{\epsilon}) - b\|_{\infty}$.}

We rewrite~\eqref{eqn:SubOptimalSolPenaltyProb} as,
\begin{equation*}
\begin{split}
\beta \phi_M (\mathcal{A}(\widehat{X}_{\epsilon})-b) &\leq \langle C, \widehat{X}_{\epsilon} \rangle - \langle C, X^{\star}_{SDP}\rangle + \beta \phi_M (\mathcal{A}(X^{\star}_{SDP})-b) + \epsilon\\
&\leq \| y^{\star}_{SDP} \|_1 \| \mathcal{A}(\widehat{X}_{\epsilon}) - b\|_{\infty} + \beta \phi_M (\mathcal{A}(X^{\star}_{SDP})-b) + \epsilon  \ \ \ \textup{(from~\eqref{eqn:upperbound})}.
\end{split}
\end{equation*}

Now $\phi_M (\mathcal{A}(X^{\star}_{SDP})-b) = \frac{\log(2d)}{M}$ and, from Proposition~\ref{prop:BoundPenalty}, we know that $\| \mathcal{A}(\widehat{X}_{\epsilon}) - b\|_{\infty} \leq \phi_M (\mathcal{A} (\widehat{X}_{\epsilon})-b)$. So,
\begin{equation}
\beta \| \mathcal{A}(\widehat{X}_{\epsilon}) - b\|_{\infty} \leq \| y^{\star}_{SDP} \|_1 \| \mathcal{A}(\widehat{X}_{\epsilon}) - b\|_{\infty} + \beta \frac{\log(2d)}{M} + \epsilon.
\end{equation}

Since $\beta > \| y^{\star}_{SDP} \|_1$ by assumption,
\begin{align*}
&\left(\beta - \| y^{\star}_{SDP} \|_1\right)  \| \mathcal{A}(\widehat{X}_{\epsilon}) - b\|_{\infty} \leq  \beta \frac{\log(2d)}{M} + \epsilon\\
&\Rightarrow\| \mathcal{A}(\widehat{X}_{\epsilon}) - b\|_{\infty} \leq \frac{\beta \frac{\log(2d)}{M} + \epsilon}{\beta - \| y^{\star}_{SDP} \|_1}. \label{eqn:BoundonInfeas}
\end{align*}

So, we get a bound on infeasibility that depends on $\| y^{\star}_{SDP} \|_1$, $M$ and $\beta$.


\paragraph{Revisiting the upper bound on $\langle C, \widehat{X}_{\epsilon} \rangle$.}

Substituting the bound on infeasibility into~\eqref{eqn:upperbound} gives
\begin{equation*}
\langle C, \widehat{X}_{\epsilon} \rangle \leq \langle C, X^{\star}_{SDP}\rangle + \| y^{\star}_{SDP} \|_1 \frac{\beta \frac{\log(2d)}{M} + \epsilon}{\beta - \| y^{\star}_{SDP} \|_1}.\qedhere
\end{equation*}
\end{proof}

\begin{comment}
\paragraph{Bound on curvature constant.}
The number of iterations required for convergence is directly proportional to the curvature constant. It thus, becomes necessary to look at bound on the curvature constant of the objective function in~\eqref{prob:LogPenalty}. To calculate curvature constant, we can ignore the linear term, $\langle C, X\rangle$. So the curvature constant of the objective function $f(X)$ is,
\begin{equation}
\begin{split}
C_f &\leq 2\beta \omega^2 M\alpha^2\\
&= \frac{2c\| y^{**}\|_1 \omega^2 \log(2d)\alpha^2}{\epsilon}.
\end{split}
\end{equation}
\end{comment}
{"config": "arxiv", "file": "2006.10945/AppendixA.tex"}