\widehat{\delta}_{s}=\sqrt{\frac{\widetilde{S}}{\widetilde{X}}}(R^{\top}R)\widetilde{P}\frac{1}{\sqrt{\widetilde{X}\widetilde{S}}}(\widetilde{\delta}_{t}+\widetilde{\delta}_{\Phi}),$

$\widehat{\delta}_{x}$ and $\widehat{\delta}_{s}$ match the definition in
Definition B.6.
2\. In each iteration, when the algorithm reaches MakeFeasible(Algorithm 20)
on Line 28 of Main (Algorithm 18), the following holds:

$\displaystyle
x-\big{(}(\mathrm{mp}_{t}.u_{1})+(\mathrm{mp}_{t}.G)\cdot(\mathrm{mp}_{t}.u_{2})\big{)}-\big{(}(\mathrm{mp}_{\Phi}.u_{1})+(\mathrm{mp}_{\Phi}.G)\cdot(\mathrm{mp}_{\Phi}.u_{2})\big{)}=x^{(0)}+\sum_{i=1}^{j}\widetilde{\delta}_{x}^{(i)}$
$\displaystyle
s+\big{(}(\mathrm{mp}_{t}.u_{3})+(\mathrm{mp}_{t}.M)\cdot(\mathrm{mp}_{t}.u_{4})\big{)}+\big{(}(\mathrm{mp}_{\Phi}.u_{3})+(\mathrm{mp}_{\Phi}.M)\cdot(\mathrm{mp}_{\Phi}.u_{4})\big{)}=s^{(0)}+\sum_{i=1}^{j}\widetilde{\delta}_{s}^{(i)}.$

3\. $\overline{x}\approx_{\epsilon_{\mathrm{tiny}}}x$,
$\overline{s}\approx_{\epsilon_{\mathrm{tiny}}}s$ with high probability.

###### Proof.

For simplicity, we only prove these three statements for $x$. The case for $s$
follows from similar reasons. Since we have two data structures sharing the
same code, we denote $q_{x,t}$, $q_{x,\Phi}$, $p_{x,t}$, $p_{x,\Phi}$ as the
$q_{x}$ and $p_{x}$ defined on Line 17 and 18 of UpdateQuery (Algorithm 23) in
data structure $\mathrm{mp}_{t}$ and $\mathrm{mp}_{\Phi}$ respectively. Also,
We denote $c_{t}$ as the output of ScalarC (Algorithm 22) of data structure
$\mathrm{mp}_{t}$, and $c_{\Phi}$ corresponds to $\mathrm{mp}_{\Phi}$. From
the description of ScalarC, we have

$\displaystyle c_{t}:=(\frac{t^{\operatorname{new}}}{t}-1)\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
c_{\Phi}:=-\frac{\epsilon}{2}\cdot
t^{\operatorname{new}}\cdot\frac{1}{\sqrt{t}\|\nabla\Phi_{\lambda}(\widetilde{\mu}/t-1)\|_{2}}.$
(71)

And recall $f_{t}$, $f_{\Phi}$ defined in Line 13, Algorithm 18) are

$\displaystyle f_{t}(x):=\sqrt{x}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
f_{\Phi}(x):=\nabla\Phi_{\lambda}(x)/\sqrt{x}.$ (72)

In UpdateQuery (Algorithm 23), the two data structure approximate
$w^{\operatorname{appr}}$ and $h^{\operatorname{appr}}$ in the same way, so
their $\widetilde{w}$ (Line 10) and $\widetilde{\mu}$ (Line 10 and 13) are the
same. So they also have the same $\widetilde{x}$ and $\widetilde{s}$ (Line
16). Note that $\widetilde{w}$, $\widetilde{\mu}$, $\widetilde{x}$,
$\widetilde{s}$ calculated in the data structure all matches Definition B.4.

We first show the following that will be used in both Part 1 and 2:

$\displaystyle c_{t}\cdot f_{t}(\widetilde{\mu})+c_{\Phi}\cdot
f_{\Phi}(\widetilde{\mu}/t)=$ $\displaystyle\leavevmode\nobreak\
(\frac{t^{\operatorname{new}}}{t}-1)\cdot\sqrt{\widetilde{\mu}}-\frac{\epsilon}{2}\cdot
t^{\operatorname{new}}\cdot\frac{1}{\sqrt{t}\|\nabla\Phi_{\lambda}(\widetilde{\mu}/t-1)\|_{2}}\cdot\nabla\Phi_{\lambda}(\widetilde{\mu}/t)/\sqrt{\widetilde{\mu}/t}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\frac{1}{\sqrt{\widetilde{\mu}}}\left((\frac{t^{\operatorname{new}}}{t}-1)\cdot\widetilde{\mu}-\frac{\epsilon}{2}\cdot
t^{\operatorname{new}}\cdot\frac{\nabla\Phi_{\lambda}(\widetilde{\mu}/t)}{\|\nabla\Phi_{\lambda}(\widetilde{\mu}/t-1)\|_{2}}\right)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\frac{1}{\sqrt{\widetilde{\mu}}}(\widetilde{\delta}_{t}+\widetilde{\delta}_{\Phi})=\frac{1}{\sqrt{\widetilde{X}\widetilde{S}}}(\widetilde{\delta}_{t}+\widetilde{\delta}_{\Phi}),$
(73)

where the first step is by the definition of $c$ and $f$ (Eq.(71),(72)), the
third step is by the definition of $\widetilde{\delta}_{t}$ and
$\widetilde{\delta}_{\Phi}$ (Definition B.4), the last step is by
$\widetilde{\mu}=\widetilde{x}\widetilde{s}$.

Part 1.  First we calculate $q_{x,t}+q_{x,\Phi}$:

$\displaystyle
q_{x,t}+q_{x,\Phi}=\sqrt{\frac{\widetilde{X}}{\widetilde{S}}}\left(c_{t}\cdot
f_{t}(\widetilde{\mu})+c_{\Phi}\cdot
f_{\Phi}(\widetilde{\mu}/t)\right)=\sqrt{\frac{\widetilde{X}}{\widetilde{S}}}\frac{1}{\sqrt{\widetilde{X}\widetilde{S}}}(\widetilde{\delta}_{t}+\widetilde{\delta}_{\Phi})$
(74)

where the first step is by assignment of $q_{x}$ (Line 17 of UpdateQuery,
Algorithm 23), the second step is by Eq.(I.2).

Next, we calculate $p_{x,t}+p_{x,\Phi}$. Note that the output $r$ of Query is
calculated in the same way as before, so by Lemma D.7 we have

$\displaystyle
r=R[l]^{\top}R[l]\sqrt{W^{\operatorname{appr}}}A^{\top}(AW^{\operatorname{appr}}A^{\top})^{-1}A\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})=R[l]^{\top}R[l]\widetilde{P}f(h^{\operatorname{appr}}).$
(75)

Therefore,

$\displaystyle p_{x,t}+p_{x,\Phi}=$ $\displaystyle\leavevmode\nobreak\
\sqrt{\frac{\widetilde{X}}{\widetilde{S}}}\left(c_{t}\cdot r_{t}+c_{\Phi}\cdot
r_{\Phi}\right)=\sqrt{\frac{\widetilde{X}}{\widetilde{S}}}\left(c_{t}\cdot
R[l]^{\top}R[l]\widetilde{P}f_{t}(\widetilde{\mu})+c_{\Phi}\cdot
R[l]^{\top}R[l]\widetilde{P}f_{\Phi}(\widetilde{\mu}/t)\right)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\sqrt{\frac{\widetilde{X}}{\widetilde{S}}}R[l]^{\top}R[l]\widetilde{P}(c_{t}\cdot
f_{t}(\widetilde{\mu})+c_{\Phi}\cdot
f_{\Phi}(\widetilde{\mu}/t))=\sqrt{\frac{\widetilde{X}}{\widetilde{S}}}R[l]^{\top}R[l]\widetilde{P}\frac{1}{\sqrt{\widetilde{X}\widetilde{S}}}\cdot(\widetilde{\delta_{t}}+\widetilde{\delta}_{\Phi}),$

where the first step is by assignment of $p_{x}$ (Line 18 of UpdateQuery,
Algorithm 23), the second step is by Eq.(75), the last step is by Eq.(I.2).

Then as we calculate $\widehat{\delta}_{x}$ in line 8 of OneStepCentralPath
(Algorithm 19),

$\displaystyle\widehat{\delta}_{x}=$ $\displaystyle\leavevmode\nobreak\
q_{t,x}+q_{\Phi,x}-(p_{t,x}+p_{\Phi,x})$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
\sqrt{\frac{\widetilde{X}}{\widetilde{S}}}\frac{1}{\sqrt{\widetilde{X}\widetilde{S}}}(\widetilde{\delta}_{t}+\widetilde{\delta}_{\Phi})-\sqrt{\frac{\widetilde{X}}{\widetilde{S}}}R[l]^{\top}R[l]\widetilde{P}\frac{1}{\sqrt{\widetilde{X}\widetilde{S}}}\cdot(\widetilde{\delta_{t}}+\widetilde{\delta}_{\Phi})$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\sqrt{\frac{\widetilde{X}}{\widetilde{S}}}\left(I-R[l]^{\top}R[l]\widetilde{P}\right)\frac{1}{\sqrt{\widetilde{X}\widetilde{S}}}\cdot(\widetilde{\delta_{t}}+\widetilde{\delta}_{\Phi}).$

Part 2. We prove Part 2 by induction. In the basic case when $j=0$, we
initialize $x\leftarrow x^{(0)}$, so it is true.

When $j>0$, let $j_{1}<j$ be the last iteration that we call Initialize on
Line 32 and 33 of Main (Algorithm 18). In the $j_{1}$-th iteration, the Main
algorithm executes Line 30: $x\leftarrow
x-(\mathrm{mp}_{t}.u_{1}+\mathrm{mp}_{t}.G\cdot\mathrm{mp}_{t}.u_{2})-(\mathrm{mp}_{\Phi}.u_{1}+\mathrm{mp}_{\Phi}.G\cdot\mathrm{mp}_{\Phi}.u_{2})$
, and then re-initialize
$\mathrm{mp}_{t}.u_{1}\leftarrow\mathrm{mp}_{t}.u_{2}\leftarrow\mathrm{mp}_{\Phi}.u_{1}\leftarrow\mathrm{mp}_{\Phi}.u_{2}\leftarrow
0$. Therefore by induction on $j$, we have
$x^{(j_{1})}=x^{(0)}+\sum_{i=1}^{j_{1}}\widetilde{\delta}_{x}^{(i)}$.

Now apply Part 3 of Lemma I.3, we have that

$\displaystyle\big{(}(\mathrm{mp}_{t}.u_{1})+(\mathrm{mp}_{t}.G)\cdot(\mathrm{mp}_{t}.u_{2})\big{)}+\big{(}(\mathrm{mp}_{\Phi}.u_{1})+(\mathrm{mp}_{\Phi}.G)\cdot(\mathrm{mp}_{\Phi}.u_{2})\big{)}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\sum_{i=j_{1}+1}^{j}c_{t}^{(i)}\cdot\sqrt{W^{\operatorname{appr},(i)}}\widetilde{P}^{(i)}f_{t}(\widetilde{\mu}^{(i)})+\sum_{i=j_{1}+1}^{j}c_{\Phi}^{(i)}\cdot\sqrt{W^{\operatorname{appr},(i)}}\widetilde{P}^{(i)}f_{\Phi}(\widetilde{\mu}^{(i)}/t^{(i)})$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\sum_{i=j_{1}+1}^{j}\sqrt{\frac{\widetilde{X}^{(i)}}{\widetilde{S}^{(i)}}}\widetilde{P}^{(i)}\frac{1}{\sqrt{\widetilde{X}^{(i)}\widetilde{S}^{(i)}}}(\widetilde{\delta}_{t}^{(i)}+\widetilde{\delta}_{\Phi}^{(i)}).$

where the first step is by Part 3 of Lemma I.3, the second step is by
Eq.(I.2).

Also notice that in every iteration, we add $q_{t,x}+q_{\Phi,x}$ to $x$ in
OneStepCentralPath (Line 10 of Algorithm 19), so

$\displaystyle
x^{(j)}-x^{(j_{1})}=\sum_{i=j_{1}+1}^{j}(q_{t,x}^{(i)}+q_{\Phi,x}^{(i)})=\sum_{i=j_{1}+1}^{j}\sqrt{\frac{\widetilde{X}^{(i)}}{\widetilde{S}^{(i)}}}\frac{1}{\sqrt{\widetilde{X}^{(i)}\widetilde{S}^{(i)}}}(\widetilde{\delta}_{t}^{(i)}+\widetilde{\delta}_{\Phi}^{(i)}).$

where the last step is by Eq.(74).

Therefore,

$\displaystyle
x^{(j)}-\big{(}(\mathrm{mp}_{t}.u_{1})+(\mathrm{mp}_{t}.G)\cdot(\mathrm{mp}_{t}.u_{2})\big{)}-\big{(}(\mathrm{mp}_{\Phi}.u_{1})+(\mathrm{mp}_{\Phi}.G)\cdot(\mathrm{mp}_{\Phi}.u_{2})\big{)}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
x^{(j_{1})}+\sum_{i=j_{1}+1}^{j}\left(\sqrt{\frac{\widetilde{X}^{(i)}}{\widetilde{S}^{(i)}}}\frac{1}{\sqrt{\widetilde{X}^{(i)}\widetilde{S}^{(i)}}}(\widetilde{\delta}_{t}^{(i)}+\widetilde{\delta}_{\Phi}^{(i)})-\sqrt{\frac{\widetilde{X}^{(i)}}{\widetilde{S}^{(i)}}}\cdot\widetilde{P}^{(i)}\cdot\frac{1}{\sqrt{\widetilde{X}^{(i)}\widetilde{S}^{(i)}}}(\widetilde{\delta}_{t}^{(i)}+\widetilde{\delta}_{\Phi}^{(i)})\right)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
x^{(j_{1})}+\sum_{i=j_{1}+1}^{j}\widetilde{\delta}_{x}^{(i)}$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\
x^{(0)}+\sum_{i=1}^{j}\widetilde{\delta}_{x}^{(i)}.$

Part 3. Consider a fixed coordinate $i$. We use $j_{i}$ to denote the last
iteration that the algorithm includes $i$ into $\widehat{S}$ when enter the
MakeFeasible procedure on Line 28 of Main (Algorithm 18) or when re-
initialize. We prove the following properties in order to apply Lemma I.5.

  1. 1.

$\overline{x}_{i}^{(j_{i})}=x_{i}^{(j_{i})}$. If the algorithm enter the
Initialize procedure, we have $\overline{x}_{i}^{(j_{i})}=x_{i}^{(j_{i})}$.
Otherwise we enter the MakeFeasible procedure, and according to the updating
rule $\overline{x}_{\widehat{S}}\leftarrow x_{\widehat{S}}$ (Line 4 of
MakeFeasible, Algorithm 20), we also have
$\overline{x}_{i}^{(j_{i})}=x_{i}^{(j_{i})}$.

  2. 2.

$t^{(j)}>t^{(j_{i})}/2$ and $j-j_{i}\leq\sqrt{n}$, since the algorithm re-
Initialize whenever it passes $\sqrt{n}$ iterations or $t$ changes too much
(Line 29 in Main, Algorithm 18).

  3. 3.

For all $l\in\\{j_{i}+1,\cdots,j\\}$,
$w^{\operatorname{appr},(l)}\in[w^{\operatorname{old}}/2,2w^{\operatorname{old}}]$,
since the algorithm doesn’t include coordinate $i$ in $\widetilde{S}$ during
iteration $l$.

Then by Lemma I.5, $x_{i}^{(j)}\approx_{\epsilon_{x}}\overline{x}_{i}^{(j)}$
holds with probability at least $1-\delta$, where
$\epsilon_{x}=\frac{200n^{1/4}}{\sqrt{b}}\cdot\log(n/\delta)\epsilon\leq\frac{\epsilon_{\mathrm{mp}}\cdot\epsilon}{3200\log^{3}n}$
by our assignment of $b=10^{12}\sqrt{n}\log^{8}n/\epsilon_{\mathrm{mp}}^{2}$
(Line 7 of Main, Algorithm 18) and $\delta=1/\operatorname{poly}(n)$. This
satisfies the requirement of Def. I.1.

By choosing $\delta$ to be $1/n^{10}$ and union bound on all coordinates $i$,
$x^{(j)}\approx_{\epsilon_{\mathrm{tiny}}}\overline{x}^{(j)}$ holds w.h.p. ∎

The following lemma proves the invariants that are true throughout the
algorithm. It is used to prove Theorem I.2. This lemma should be seen as a
complement of Section D, and we directly use results proved in that section.

######  Lemma I.3 (Invariants).

In the end of the $j$-th iteration, the following invariants hold:

  1. 1.

$G=\widetilde{V}A^{\top}(AVA^{\top})^{-1}A$.

  2. 2.

$u_{3}+Mu_{4}=\sum_{i=j_{1}+1}^{j}c^{(i)}\cdot
A^{\top}(AW^{\operatorname{appr},(i)}A^{\top})^{-1}A\sqrt{W^{\operatorname{appr},(i)}}f(h^{\operatorname{appr},(i)})$,

  3. 3.

$u_{1}+Gu_{2}=\sum_{i=j_{1}+1}^{j}c^{(i)}\cdot
W^{\operatorname{appr},(i)}A^{\top}(AW^{\operatorname{appr},(i)}A^{\top})^{-1}A\sqrt{W^{\operatorname{appr},(i)}}f(h^{\operatorname{appr},(i)})$,

where $j_{1}$ is the last iteration we call Initialize, and $c^{(j)}$ is
defined as in ScalarC:
in data structure $\mathrm{mp}_{t}$,

$\displaystyle c:=$ $\displaystyle\leavevmode\nobreak\
(\frac{t^{\operatorname{new}}}{t}-1),$

and in data structure $\mathrm{mp}_{\Phi}$,

$\displaystyle c:=$ $\displaystyle\leavevmode\nobreak\
-\frac{\epsilon}{2}\cdot
t^{\operatorname{new}}\cdot\frac{1}{\sqrt{t}\|\nabla\Phi_{\lambda}(\widetilde{\mu}/t-1)\|_{2}}.$

###### Proof.

We consider the $j$-th iteration in this proof. Throughout the proof, we call
the updated version of all date structure members at the end of the $j$-th
iteration as the “new” version, with a “new” superscript in the notation, e.g.
$u_{1}^{\operatorname{new}}$.

Part 1. Note that $V$, $\widetilde{V}$ and $G$ are only updated in
MatrixUpdate and PartialMatrixUpdate.

Case 1. MatrixUpdate (Algorithm 25). On Line 12, $G$ is updated to be
$W^{\operatorname{appr}}M^{\mathrm{tmp}}$, where $W^{\operatorname{appr}}$ is
the new value of $\widetilde{V}$ (Line 18), and $M^{\mathrm{tmp}}$ is the new
value of $M$ (Line 16). We have

$\displaystyle
G^{\operatorname{new}}=\widetilde{V}M=\widetilde{V}A^{\top}(AVA^{\top})^{-1}A,$

since in Lemma D.17 we proved that the invariant of $M$ still holds.

Case 2. PartialMatrixUpdate (Algorithm 26). First note that $V$ and $M$ are
not updated in PartialMatrixUpdate. On Line 14, $G$ is updated to be
$W^{\operatorname{appr}}M$, where $W^{\operatorname{appr}}$ is the new value
of $\widetilde{V}$, so the invariant of $G$ still holds.

Part 2. It suffices to prove that the additive term in the $j$-th iteration is

$\displaystyle
u_{3}^{\operatorname{new}}+M^{\operatorname{new}}u_{4}^{\operatorname{new}}-(u_{3}+Mu_{4})=c\cdot
A^{\top}(AW^{\operatorname{appr}}A^{\top})^{-1}A\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}}).$

Then starting from the $j_{1}$-th iteration where we re-initialize and set
$u_{3}^{(j_{1})}=u_{4}^{(j_{1})}=0$, we can inductively prove the statement
for iterations $i\in\\{j_{1}+1,\cdots,j\\}$.

There are three cases that we update $u_{3}$ and $u_{4}$ in the $j$-th
iteration: in MatrixUpdate, PartialMatrixUpdate, or Query. Note that even
though we might enter Query after executing MatrixUpdate or
PartialMatrixUpdate, $u_{3}$ and $u_{4}$ won’t change inside Query since they
were already updated in MatrixUpdate or PartialMatrixUpdate. So we can
consider the updates to $u_{3}$ and $u_{4}$ in these three procedures
separately.

Case 1, MatrixUpdate (Algorithm 25).

$\displaystyle
u_{3}^{\operatorname{new}}+M^{\operatorname{new}}u_{4}^{\operatorname{new}}-(u_{3}+Mu_{4})=$
$\displaystyle\leavevmode\nobreak\ u_{3}+Mu_{4}+c\cdot
M^{\mathrm{tmp}}\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})+M^{\operatorname{new}}\cdot
0-(u_{3}+Mu_{4})$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\ c\cdot
M^{\mathrm{tmp}}\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\ c\cdot
A^{\top}(AW^{\operatorname{appr}}A^{\top})^{-1}A\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}}),$

where the first step is by the assignment of $u_{3}^{\operatorname{new}}$
(Line 14), $u_{4}^{\operatorname{new}}$ (Line 15), the last step is by
$M^{\mathrm{tmp}}=A^{\top}(AW^{\operatorname{appr}}A^{\top})^{-1}A$ that we
already proved in Lemma D.17.

Case 2, PartialMatrixUpdate (Algorithm 26).

$\displaystyle
u_{3}^{\operatorname{new}}+M^{\operatorname{new}}u_{4}^{\operatorname{new}}-(u_{3}+Mu_{4})$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
M(u_{4}^{\operatorname{new}}-u_{4})$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ M\cdot
c\cdot\left(\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})-\mathbf{1}_{S^{\operatorname{new}}}B^{\mathrm{tmp}}\mathcal{L}_{r}[(M_{S^{\operatorname{new}}})^{\top}]\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})\right)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
c\cdot\left(M-\mathcal{L}_{c}[M_{S^{\operatorname{new}}}]B^{\mathrm{tmp}}\mathcal{L}_{r}[(M_{S^{\operatorname{new}}})^{\top}]\right)\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
c\cdot\left(M-\mathcal{L}_{c}[M_{S^{\operatorname{new}}}]\cdot\mathcal{L}_{*}[\left((\Delta_{S^{\operatorname{new}},S^{\operatorname{new}}}^{\operatorname{new}})^{-1}+M_{S^{\operatorname{new}},S^{\operatorname{new}}}\right)^{-1}]\cdot\mathcal{L}_{r}[(M_{S^{\operatorname{new}}})^{\top}]\right)\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\ c\cdot
A^{\top}(AW^{\operatorname{appr}}A^{\top})^{-1}A\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}}),$

where the first step is by $u_{3}^{\operatorname{new}}=u_{3}$ and
$M^{\operatorname{new}}=M$ since they are not modified in PartialMatrixUpdate,
the second step is by the assignment of $u_{4}^{\operatorname{new}}$ (Line
17), the fourth step is by the invariant on $B^{\mathrm{tmp}}$ (Part 10 of
Assumption D.1), the fifth step is by Woodbury identity (Lemma C.8) and
$M=A^{\top}(AVA^{\top})^{-1}A$.

Case 3, Query (Algorithm 24).

$\displaystyle
u_{3}^{\operatorname{new}}+M^{\operatorname{new}}u_{4}^{\operatorname{new}}-(u_{3}+Mu_{4})$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
M(u_{4}^{\operatorname{new}}-u_{4})$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ M\cdot
c\cdot\left(\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})+\mathbf{1}_{S^{\operatorname{new}}}(\gamma^{\mathrm{tmp}}-\gamma_{1}-\partial\gamma)\right)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
c\cdot\left(M-\mathcal{L}_{c}[M_{S^{\operatorname{new}}}]\cdot\mathcal{L}_{*}[((\Delta^{\operatorname{new}}_{S^{\operatorname{new}},S^{\operatorname{new}}})+M_{S^{\operatorname{new}},S^{\operatorname{new}}})^{-1}]\cdot
L_{r}[(M_{S^{\operatorname{new}}})^{\top}]\right)\cdot\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\ c\cdot
A^{\top}(AW^{\operatorname{appr}}A^{\top})^{-1}A\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}}),$

where the first step is by $u_{3}^{\operatorname{new}}=u_{3}$ and
$M^{\operatorname{new}}=M$ since they are not modified in MatrixUpdate, the
second step is by the assignment of $u_{4}^{\operatorname{new}}$(Line 25), the
third step is by the close-form formula of
$\gamma^{\mathrm{tmp}}-\gamma_{1}-\partial\gamma$ (Eq. (D.1)), the fourth step
is by Woodbury identity (Lemma C.8) and $M=A^{\top}(AVA^{\top})^{-1}A$.

Part 3. The proof for $u_{1}+Gu_{2}=\sum_{i=j_{1}+1}^{j}c^{(i)}\cdot
W^{\operatorname{appr},(i)}A^{\top}(AW^{\operatorname{appr},(i)}A^{\top})^{-1}A\sqrt{W^{\operatorname{appr},(i)}}f(h^{\operatorname{appr},(i)})$
follows from similar reasons as that of Part 2. We omit the details here.

∎

###  I.3 Bounding $x$ and $\overline{x}$

In this section we prove that the explicit $\overline{x}$ is always within an
error of $\epsilon_{\mathrm{tiny}}$ with the implicitly maintained $x$. This
fact is used to prove Part 3 of Theorem I.2. Similar as in previous sections,
we use a superscript $(j)$ to denote the variable at the beginning of the
$j$-th iteration.

######  Remark I.4.

Our entire analysis is an induction-based argument. In the $j$-th iteration,
the induction hypothesis allows us to assume that Assumption B.5 is true for
the $(j-1)$-th iteration, it also allows us to assume the following Lemma I.5
is true for $x^{(j)}$ and $\overline{x}^{(j)}$.

Using these two induction hypothesis we proved that Assumption B.5 is still
true for the $j$-th iteration in Section I.1.

Then we further use these two induction hypothesis together with _Assumption
B.5 for the $j$-th iteration_ to prove the following Lemma I.5.

######  Lemma I.5 ($x$ and $\overline{x}$ are close).

Consider a fixed coordinate $i\in[n]$ and a fixed iteration number
$k\leq\sqrt{n}$. Let $b$ denote the size of sketching matrix. If the following
are true: (1) $x^{(0)}_{i}=\overline{x}^{(0)}_{i}$. (2) $t^{(k)}>t^{(0)}/2$.
(3) There is a constant $w>0$ such that for all $j\in[k]$,
$w^{\operatorname{appr},(j)}_{i}\in[w/2,2w]$. (4) Inductively Assumption B.5
is true for iterations $1,2,\dots,k$. Then we have:

$\displaystyle|(x_{i}^{(k)})^{-1}(\overline{x}_{i}^{(k)}-x_{i}^{(k)})|\leq\epsilon_{x}$

holds with probability $1-\delta$ over the randomness of sketching matrices
$R^{(1)},\cdots,R^{(k)}\in\mathbb{R}^{b\times n}$, where
$\epsilon_{x}=\frac{200n^{1/4}}{\sqrt{b}}\cdot\log(n/\delta)\epsilon$.

###### Proof.

We denote $t=t^{(k)}$. Since $t^{(0)}\leq 2t^{(k)}$ and the central path
iteration will only decrease $t^{(j)}$, we have $t\leq t^{(j)}\leq 2t$ for all
$j\in[k]$.

From the definition of $\widetilde{\delta}_{x}$ (Definition B.4) and
$\widehat{\delta}_{x}$ (Definition B.6), we have

$\displaystyle\widetilde{\delta}_{x}-\widehat{\delta}_{x}=$
$\displaystyle\leavevmode\nobreak\
\frac{\widetilde{X}}{\sqrt{\widetilde{X}\widetilde{S}}}(I-\widetilde{P})\frac{1}{\sqrt{\widetilde{X}\widetilde{S}}}\widetilde{\delta}_{\mu}-\frac{\widetilde{X}}{\sqrt{\widetilde{X}\widetilde{S}}}(I-R^{\top}R\widetilde{P})\frac{1}{\sqrt{\widetilde{X}\widetilde{S}}}\widetilde{\delta}_{\mu}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\frac{\widetilde{X}}{\sqrt{\widetilde{X}\widetilde{S}}}(\widetilde{P}-R^{\top}R\widetilde{P})\frac{1}{\sqrt{\widetilde{X}\widetilde{S}}}\widetilde{\delta}_{\mu}=\sqrt{W^{\operatorname{appr}}}(\widetilde{P}-R^{\top}R\widetilde{P})\frac{1}{\sqrt{\widetilde{X}\widetilde{S}}}\widetilde{\delta}_{\mu}.$
(76)

Then the difference between $x^{(k)}_{i}$ and $\overline{x}^{(k)}_{i}$ can be
written as

$\displaystyle|x_{i}^{(k)}-\overline{x}_{i}^{(k)}|=$
$\displaystyle\leavevmode\nobreak\
\Big{|}\big{(}x^{(0)}_{i}+\sum_{j=1}^{k}\widetilde{\delta}_{x,i}^{(j)}\big{)}-\big{(}\overline{x}^{(0)}_{i}+\sum_{j=1}^{k}\widehat{\delta}_{x,i}^{(j)}\big{)}\Big{|}=\Big{|}\sum_{j=1}^{k}(\widetilde{\delta}_{x,i}^{(j)}-\widehat{\delta}_{x,i}^{(j)})\Big{|}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\Big{|}\sum_{j=1}^{k}\sqrt{w^{\operatorname{appr},(j)}}_{i}\big{(}(\widetilde{P}^{(j)}-R^{\top(j)}R^{(j)}\widetilde{P}^{(j)})\frac{1}{\sqrt{\widetilde{X}^{(j)}\widetilde{S}^{(j)}}}\widetilde{\delta}_{\mu}^{(j)}\big{)}_{i}\Big{|},$
(77)

where the second step is by $x^{(0)}_{i}=\overline{x}^{(0)}_{i}$, the third
step is by Eq.(I.3).

We define a random vector $Y_{j}$ for the $j$-th iteration:
$Y_{j}=\sqrt{w^{\operatorname{appr},(j)}}_{i}\Big{(}(I-R^{(j)\top}R^{(j)})\widetilde{P}^{(j)}\frac{\widetilde{\delta}_{\mu}^{(j)}}{\sqrt{\widetilde{X}^{(j)}\widetilde{S}^{(j)}}}\Big{)}_{i}$.

We first bound the $\ell_{2}$ norm of the right part
$\frac{\widetilde{\delta}_{\mu}^{(j)}}{\sqrt{\widetilde{X}^{(j)}\widetilde{S}^{(j)}}}$:

$\displaystyle\Big{\|}\frac{\widetilde{\delta}_{\mu}^{(j)}}{\sqrt{\widetilde{X}^{(j)}\widetilde{S}^{(j)}}}\Big{\|}_{2}\leq\operatorname*{{\bf{Sup}}}\Big{[}\frac{1}{\sqrt{\widetilde{X}^{(j)}\widetilde{S}^{(j)}}}\Big{]}\cdot\|\widetilde{\delta}_{\mu}^{(j)}\|_{2}\leq\frac{1.1}{\sqrt{t^{(j)}}}\cdot\|\widetilde{\delta}_{\mu}^{(j)}\|_{2}\leq
2.2\epsilon\sqrt{t^{(j)}}\leq 5\epsilon\sqrt{t},$

where the first step is by $\|a\cdot
b\|_{2}\leq\operatorname*{{\bf{Sup}}}[a]\cdot\|b\|_{2}$, the second step is by
the inductive Assumption B.5 that
$\widetilde{X}^{(j)}\widetilde{S}^{(j)}\approx_{0.1}t^{(j)}$, the third step
is by $\|\widetilde{\delta}_{\mu}^{(j)}\|_{2}\leq 2\epsilon t^{(j)}$ (Fact
B.9), the last step is by $t^{(j)}\leq 2t$.

By Lemma B.14, for each $j$ and with randomness over $R^{(j)}$, and use the
fact that $w^{\operatorname{appr},(j)}_{i}\in[w/2,2w]$ for all $j\in[k]$, we
have

$\displaystyle\operatorname*{{\mathbb{E}}}[Y_{j}]=0\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{and}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\operatorname*{{\mathbb{E}}}[(Y_{j})^{2}]\leq\frac{w^{\operatorname{appr},(j)}_{i}}{b}\Big{\|}\frac{\widetilde{\delta}_{\mu}^{(j)}}{\sqrt{\widetilde{X}^{(j)}\widetilde{S}^{(j)}}}\Big{\|}_{2}^{2}\leq(2w)\cdot
25\epsilon^{2}t/b,$

and with probability $1-\delta/n$,

$\displaystyle|Y_{j}|\leq\sqrt{w^{\operatorname{appr},(j)}_{i}}\cdot\Big{\|}\frac{\widetilde{\delta}_{\mu}^{(j)}}{\sqrt{\widetilde{X}^{(j)}\widetilde{S}^{(j)}}}\Big{\|}_{2}\cdot\frac{\log(n/\delta)}{\sqrt{b}}\leq(\sqrt{2w})\cdot
5\epsilon\sqrt{t}\frac{\log(n/\delta)}{\sqrt{b}}:=M.$

Now, we apply Bernstein inequality on these zero-mean independent random
variable $\\{Y_{j}\\}_{j=1}^{k}$ (Lemma A.3), $\forall\tau>0$,

$\displaystyle\Pr\Big{[}|\sum_{j=1}^{k}(Y_{j})|>\tau\Big{]}\leq
2\exp\Big{(}-\frac{\tau^{2}/2}{\sum_{j=1}^{k}\operatorname*{{\mathbb{E}}}[(Y_{j})^{2}]+M\tau/3}\Big{)}$

Choosing $\tau=64\frac{\sqrt{wkt}}{\sqrt{b}}\log(n/\delta)^{2}\epsilon$, we
have

$\displaystyle\Pr\Big{[}|\sum_{j=1}^{k}(Y_{j})|>\tau\Big{]}\leq
2\exp\Big{(}-\frac{\tau^{2}/2}{50wk\epsilon^{2}t/b+\tau\cdot
5\epsilon\sqrt{2wt}\frac{\log(n/\delta)}{3\sqrt{b}}}\Big{)}\leq
2\exp(-10\log(n/\delta)).$

Then take a union bound on all events that $|Y_{j}|\leq M$, we have
$|\sum_{j=1}^{k}(Y_{j})|\leq\tau$ with probability at least $1-\delta$.
Therefore,

$\displaystyle|x^{(k)}_{i}-\overline{x}^{(k)}_{i}|\leq$
$\displaystyle\leavevmode\nobreak\
|\sum_{j=1}^{k}(Y_{j})|\leq\tau\leq\frac{64\sqrt{wkt}}{\sqrt{b}}\cdot\log(n/\delta)^{2}\epsilon$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
x^{(k)}_{i}\cdot\frac{200\sqrt{k}}{\sqrt{b}}\cdot\log(n/\delta)^{2}\epsilon\leq
x^{(k)}_{i}\cdot\frac{200n^{1/4}}{\sqrt{b}}\cdot\log(n/\delta)^{2}\epsilon\leq
x^{(k)}_{i}\epsilon_{x},$

where the first step is by Eq.(I.3), the fourth step is by $wt\leq
2w^{(\operatorname{appr}),(k)}_{i}\cdot
2t^{(k)}\leq(2x^{(k)}_{i}/s^{(k)}_{i})\cdot(3x^{(k)}_{i}s^{(k)}_{i})\leq
6(x^{(k)}_{i})^{2}$ by Assumption B.5, the fifth step is by $k\leq\sqrt{n}$. ∎

###  I.4 Running time of feasible data structure

######  Lemma I.6.

It takes $O(n)$ time to execute ScalarC.

###### Proof.

The proof is straightforward. ∎

######  Lemma I.7.

In the procedure MatrixUpdate, it takes

  1. 1.

$O(n^{2})$ time to compute $G\leftarrow
W^{\operatorname{appr}}M^{\mathrm{tmp}}$

  2. 2.

$O(n^{2})$ time to compute $u_{1}\leftarrow u_{1}+Gu_{2}+c\cdot
W^{\operatorname{appr}}M^{\mathrm{tmp}}\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})$

  3. 3.

$O(n^{2})$ time to compute $u_{3}\leftarrow u_{3}+Mu_{4}+c\cdot
M^{\mathrm{tmp}}\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})$

Overall, refreshing $G$, $u_{1}$, $u_{2}$ takes $O(n^{2})$ time.

###### Proof.

This lemma directly follows from the algorithm of MatrixUpdate (ALgorithm 25).
∎

######  Lemma I.8.

In the procedure PartialMatrixUpdate, it takes

  1. 1.

$O(n^{1+a})$ time to compute $G\leftarrow
G+(W^{\operatorname{appr}}-\widetilde{V})\cdot M$.

  2. 2.

$O(n^{1+a})$ time to compute $u_{1}\leftarrow
u_{1}+(W^{\operatorname{appr}}-\widetilde{V})\cdot Mu_{2}$.

  3. 3.

$O(n^{1+a})$ time to compute $u_{2}\leftarrow
u_{2}+c\left(\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})-\mathbf{1}_{S^{\operatorname{new}}}B^{\mathrm{tmp}}\mathcal{L}_{r}[(M_{S^{\operatorname{new}}})^{\top}]\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})\right)$.
And computing $u_{4}$ takes the same time.

Overall, refreshing $G$, $u_{1}$, $u_{2}$, $u_{4}$ takes $O(n^{1+a})$ time.

###### Proof.

From Lemma E.1, we have that when entering PartialUpdate,
$\|w^{\operatorname{appr}}-\widetilde{v}\|_{0}\leq O(n^{a})$, and
$|S^{\operatorname{new}}|\leq O(n^{a})$.

Part 1. Since $(W^{\operatorname{appr}}-\widetilde{V})$ is a $O(n^{a})$-sparse
diagonal matrix, multiplying it with a $n\times n$ matrix $M$ takes
$O(n^{1+a})$ time. By memory operation, adding
$(W^{\operatorname{appr}}-\widetilde{V})M$ on $G$ also takes $O(n^{1+a})$
time.

Part 2. Multiplying a $O(n^{a})$-sparse diagonal matrix
$(W^{\operatorname{appr}}-\widetilde{V})$ with a $n\times n$ matrix $M$ and
then with a $n\times 1$ vector $u_{2}$ takes $O(n^{1+a})$ time.

Part 3. Computing $\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})$
takes $O(n)$ time. Multiplying a $O(n^{a})\times n$ matrix
$\mathcal{L}_{r}[(M_{S^{\operatorname{new}}})^{\top}]$ with a $n\times 1$
vector $\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})$ takes
$O(n^{1+a})$ time. Multiplying a $O(n^{a})\times O(n^{a})$ matrix
$B^{\mathrm{tmp}}$ with a $O(n^{a})\times 1$ vector
$\mathcal{L}_{r}[(M_{S^{\operatorname{new}}})^{\top}]\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})$
takes $O(n^{2a})$ time. Finally multiplying a $n\times O(n^{a})$ matrix
$\mathbf{1}_{S^{\operatorname{new}}}$ that only has $O(n^{a})$ non-zero
entries with a $O(n^{a})\times 1$ vector
$B^{\mathrm{tmp}}(M_{S^{\operatorname{new}}})^{\top}\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})$
takes $O(n)$ time. Thus in total this step takes $O(n^{1+a})$ time. ∎

######  Remark I.9.

Note that this running time of $O(n^{1+a})$ is always dominated by the
$O({\cal T}_{\mathrm{mat}}(n,n^{a},\widetilde{k}))$ time of other computations
of PartialMatrixUpdate (see Lemma E.18).

######  Lemma I.10.

In the procedure Query, it takes

  1. 1.

$O(n^{a+\widetilde{a}})$ time to compute $u_{1}\leftarrow
u_{1}+c\cdot(W^{\operatorname{appr}}-\widetilde{V})\Big{(}\beta_{2}+M\cdot\big{(}\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})-\sqrt{V}f(g)+\mathbf{1}_{S^{\operatorname{new}}}(\gamma^{\mathrm{tmp}}-\gamma_{1}-\partial\gamma)\big{)}\Big{)}$.

  2. 2.

$O(n)$ time to compute $u_{2}\leftarrow
u_{2}+c\cdot\left(\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})+\mathbf{1}_{S^{\operatorname{new}}}(\gamma^{\mathrm{tmp}}-\gamma_{1}-\partial\gamma)\right)$.
And computing $u_{4}$ takes the same time.

Overall, calculating $u_{1}$, $u_{2}$, $u_{4}$ takes $O(n^{a+\widetilde{a}})$
time.

###### Proof.

When entering Query, from Lemma E.1, we have that
$\|w^{\operatorname{appr}}-v\|_{0}\leq n^{a}$ and
$\|h^{\operatorname{appr}}-g\|_{0}\leq n^{a}$, thus
$\|\sqrt{W}^{\operatorname{appr}}f(h^{\operatorname{appr}})-\sqrt{V}f(g)\|_{0}\leq
O(n^{a})$. From Lemma E.1, we also have that
$\|w^{\operatorname{appr}}-\widetilde{v}\|_{0}\leq n^{\widetilde{a}}$, and
$|S^{\operatorname{new}}|\leq O(n^{a})$.

Part 1. We need to compute the following four parts:

  1. 1.

Multiplying a $n\times n$ diagonal matrix
$W^{\operatorname{appr}}-\widetilde{V}$ with a $n\times 1$ vector $\beta_{2}$
takes $O(n)$ time.

  2. 2.

Multiplying a $n^{\widetilde{a}}$-sparse $n\times n$ diagonal matrix
$W^{\operatorname{appr}}-\widetilde{V}$ with a $n\times n$ matrix $M$ and then
with a $O(n^{a})$-sparse $n\times 1$ vector
$(\sqrt{W^{\operatorname{appr}}}f(h^{\operatorname{appr}})-\sqrt{V}f(g))$
takes $O(n^{a+\widetilde{a}})$ time.

  3. 3.

Computing
$\mathbf{1}_{S^{\operatorname{new}}}(\gamma^{\mathrm{tmp}}-\gamma_{1}-\partial\gamma)$
takes $O(n)$ time. Multiplying a $n^{\widetilde{a}}$-sparse $n\times n$
diagonal matrix $W^{\operatorname{appr}}-\widetilde{V}$ with a $n\times n$
matrix $M$ and then with a $O(n^{a})$-sparse $n\times 1$ vector
$\mathbf{1}_{S^{\operatorname{new}}}(\gamma^{\mathrm{tmp}}-\gamma_{1}-\partial\gamma)$
takes $O(n^{a+\widetilde{a}})$ time.

So overall this step takes $O(n^{a+\widetilde{a}})$ time.

Part 2. Computing $\sqrt{W^{\operatorname{appr}}}\cdot
f(h^{\operatorname{appr}})$ takes $O(n)$ time. And multiplying a $n\times
O(n^{a})$ matrix $\mathbf{1}_{S^{\operatorname{new}}}$ that only has
$O(n^{a})$ non-zero entries with a $O(n^{a})\times 1$ vector
$(\gamma^{\mathrm{tmp}}-\gamma_{1}-\partial\gamma)$ takes $O(n)$ time. Thus in
total this step takes $O(n)$ time. ∎

######  Remark I.11.

Note that this running time of $O(n^{a+\widetilde{a}})$ is the same as other
computations of Query (see Lemma E.3).

######  Lemma I.12.

The amortized running time of procedure MakeFeasible is

$\displaystyle(C_{1}/\epsilon_{\mathrm{mp}}+C_{2}/\epsilon^{2}_{\mathrm{mp}})\cdot
n^{1.5}.$

###### Proof.

In this proof, we will use superscript notations that are consistent with
section F. Let $\overline{w}^{(j+1)}$ denote the input
$w^{\operatorname{new}}$ of UpdateQuery in the $j$-th iteration. Let
$w^{\operatorname{appr},(j+1)}$ be the output of UpdateQuery in the $j$-th
iteration. Let $w^{\operatorname{old},(j)}$ be the values of
$w^{\operatorname{old}}$ at the beginning of the $j$-th iteration. Let
$\widehat{S}^{(j)}:=\\{i:|w^{\operatorname{old},(j)}_{i}-w^{\operatorname{appr},(j+1)}_{i}|>w^{\operatorname{old},(j)}_{i}/2\\}$,
and we define $\widehat{k}_{j}:=|\widehat{S}^{(j)}|$. Note that in the $j$-th
iteration, procedure MakeFeasible takes worst-case $O(n\cdot\widehat{k}_{j})$
time. We use a similar amortized argument as that of Lemma F.19.

We define the following potential function

$\displaystyle\Phi_{j}=\sum_{i=1}^{n}\psi(w_{i}^{(j)}/w_{i}^{\operatorname{old},(j)}-1),$

where the function $\psi$ is defined as Definition F.4. We let
$g\in\mathbb{R}^{n}$ be the all one vector. Applying Lemma F.23 (set $v^{(j)}$
of the lemma statement to be $w^{\operatorname{old},(j)}$), we have

$\displaystyle(w\text{\leavevmode\nobreak\ move})^{(j)}:=$
$\displaystyle\leavevmode\nobreak\
\sum_{i=1}^{n}g_{i}\cdot\operatorname*{{\mathbb{E}}}\left[\psi(w^{(j+1)}_{i}/w^{\operatorname{old},(j)}_{i}-1)-\psi(w^{(j)}_{i}/w^{\operatorname{old},(j)}_{i}-1)\leavevmode\nobreak\
\Big{|}\leavevmode\nobreak\ w^{(j)},w^{\operatorname{old},(j)}\right]$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
O(C_{1}+C_{2}/\epsilon_{\mathrm{mp}})\cdot\|g\|_{2}=O((C_{1}+C_{2}/\epsilon_{\mathrm{mp}})\cdot\sqrt{n}).$
(78)

From Section I.1, we have
$w^{\operatorname{appr},(j+1)}\approx_{\epsilon_{\mathrm{mp}}}\overline{w}^{(j+1)}$.
And from Lemma I.5 we have
$\overline{w}^{(j+1)}\approx_{\epsilon_{\mathrm{tiny}}}w^{(j+1)}$. So
$w^{\operatorname{appr},(j+1)}\approx_{\epsilon_{\mathrm{mp}}+\epsilon_{\mathrm{tiny}}}w^{(j+1)}$.
For every $i\in\widehat{S}^{(j)}$, we have
$|w^{\operatorname{appr},(j+1)}_{i}/w^{\operatorname{old},(j)}_{i}-1|>1/2$ by
definition of $\widehat{S}^{(j)}$, thus

$\displaystyle|w^{(j+1)}_{i}/w^{\operatorname{old},(j)}_{i}-1|=$
$\displaystyle\leavevmode\nobreak\
|(w^{\operatorname{appr},(j+1)}_{i}/w^{\operatorname{old},(j)}_{i})\cdot(w^{(j+1)}_{i}/w^{\operatorname{appr},(j+1)}_{i})-1|$
$\displaystyle>$ $\displaystyle\leavevmode\nobreak\
1/2-2\epsilon_{\mathrm{mp}}-2\epsilon_{\mathrm{tiny}}>2\epsilon_{\mathrm{mp}},$

where the last step follows from $\epsilon_{\mathrm{mp}}<\frac{1}{10}$
(Assumption F.5) and
$\epsilon_{\mathrm{tiny}}<\frac{\epsilon_{\mathrm{mp}}}{1000}$ (Def. I.1).
Thus
$\psi(w^{(j+1)}_{i}/w^{\operatorname{old},(j)}_{i}-1)>\epsilon_{\mathrm{mp}}$
from the definition of $\psi$. Since for $i\in\widehat{S}^{(j)}$,
$w^{\operatorname{old},(j+1)}_{i}$ is updated to be
$w^{\operatorname{appr},(j+1)}_{i}$, we have

$\displaystyle|w^{(j+1)}_{i}/w^{\operatorname{old},(j+1)}_{i}-1|=|w^{(j+1)}_{i}/w^{\operatorname{appr},(j+1)}_{i}-1|\leq\epsilon_{\mathrm{mp}}+\epsilon_{\mathrm{tiny}}<1.1\epsilon_{\mathrm{mp}}.$

Thus
$\psi(w^{(j+1)}_{i}/w^{\operatorname{old},(j+1)}_{i}-1)<0.6\epsilon_{\mathrm{mp}}$
from the definition of $\psi$ (Definition F.4).

So we have

$\displaystyle(v\text{\leavevmode\nobreak\ move})^{(j)}:=$
$\displaystyle\leavevmode\nobreak\
\sum_{i=1}^{n}\operatorname*{{\mathbb{E}}}\left[\psi(w^{(j+1)}_{i}/w^{\operatorname{old},(j)}_{i}-1)-\psi(w^{(j+1)}_{i}/w^{\operatorname{old},(j+1)}_{i}-1)\leavevmode\nobreak\
\Big{|}\leavevmode\nobreak\ w^{(j)},w^{\operatorname{old},(j)}\right]$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
\sum_{i\in\widehat{S}^{(j)}}\operatorname*{{\mathbb{E}}}\left[\psi(w^{(j+1)}_{i}/w^{\operatorname{old},(j)}_{i}-1)-\psi(w^{(j+1)}_{i}/w^{\operatorname{old},(j+1)}_{i}-1)\leavevmode\nobreak\
\Big{|}\leavevmode\nobreak\ w^{(j)},w^{\operatorname{old},(j)}\right]$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
\sum_{i\in\widehat{S}^{(j)}}(\epsilon_{\mathrm{mp}}-0.6\epsilon_{\mathrm{mp}})=\Omega(\epsilon_{\mathrm{mp}}\widehat{k}_{j+1}).$
(79)

Combining Eq. (I.4) and Eq. (I.4), we have

$\displaystyle\operatorname*{{\mathbb{E}}}[\Phi_{T}]-\Phi_{0}=\sum_{j=0}^{T-1}((w\text{\leavevmode\nobreak\
move})^{(j)}-(v\text{\leavevmode\nobreak\ move})^{(j)})\leq
T\cdot(C_{1}+C_{2}/\epsilon_{\mathrm{mp}})\cdot\sqrt{n}-\sum_{j=1}^{T}\Omega(\epsilon_{\mathrm{mp}}\widehat{k}_{j}).$

Since when initialize we set $w^{\operatorname{old}}$ to be $w_{0}$, we have
$\Phi_{0}=0$. And since $\operatorname*{{\mathbb{E}}}[\Phi_{T}]\geq 0$, we
have

$\displaystyle\sum_{j=1}^{T}\widehat{k}_{j}\leq
T\cdot(C_{1}/\epsilon_{\mathrm{mp}}+C_{2}/\epsilon^{2}_{\mathrm{mp}})\cdot\sqrt{n}.$

Thus the amortized running time of MakeFeasible is
$(C_{1}/\epsilon_{\mathrm{mp}}+C_{2}/\epsilon^{2}_{\mathrm{mp}})\cdot
n^{1.5}.$ ∎

######  Remark I.13.

Note that the amortized time of MakeFeasible is dominated by the amortized
time of MatrixUpdate (Lemma F.19).

##  Appendix J History of Matrix Multiplication and LP

Year | Reference | $\omega$ | Reference | $\alpha$
---|---|---|---|---
1969 | [Str69] | $2.808$ |  |
1978 | [Pan78] | $2.796$ |  |
1979 | [BCRL79] | $2.78$ |  |
1981 | [Sch81] | $2.548$ |  |
1982 | [Rom82] | $2.517$ | [Cop82] | $0.172$
1982 | [CW82] | $2.496$ |  |
1986 | [Str86] | $2.479$ |  |
1987 | [CW87] | $2.376$ |  |
1997 |  |  | [Cop97] | $0.29462$
2012 | [Wil12] | $2.3729$ |  |
2014 | [LG14] | $2.37286$ | [LG14] | $0.30298$
2018 |  |  | [GU18] | $0.31389$
Table 16: The history of exponent of matrix multiplication $\omega$ and the dual exponent of matrix multiplication $\alpha$. Year | Author | Reference | Complexity
---|---|---|---
1947 | Dantzig | [Dan47] | $2^{O(n)}$
1979 | Khachiyan | [Kha80] | $n^{6}$
1984 | Karmarkar | [Kar84] | $n^{3.5}$
1986 | Renegar | [Ren88] | $n^{3}$
1987 | Vaidya | [Vai87] | $n^{3}$
1989 | Vaidya | [Vai89] | $n^{2.5}$
1994 | Nesterov, Nemirovskii | [NN94] | $n^{2.5}$
2014 | Lee, Sidford | [LS14] | $n^{2.5}$
2015 | Lee, Sidford | [LS15] | $n^{2.5}$
2019 | Cohen, Lee, Song | [CLS19] | $n^{\omega}+n^{2.5-\alpha/2}+n^{2+1/6}$
2019 | Lee, Song, Zhang | [LSZ19] | $n^{\omega}+n^{2.5-\alpha/2}+n^{2+1/6}$
2020 | Brand | [Bra20] | $n^{\omega}+n^{2.5-\alpha/2}+n^{2+1/6}$
2020 | Brand, Lee, Sidford, Song | [BLSS20] | $n^{3}$
2020 |  | This paper | $n^{\omega}+n^{2.5-\alpha/2}+n^{2+1/18}$
Table 17: Let $\omega$ denote the exponent of the current matrix
multiplication. LP has $n$ variables, $d=\Theta(n)$ constraints, and all
number can be encoded in $L$ bits. The running time of all these algorithms
has a nearly linear dependence on $L$. We consider the case where $A$ is a
dense full rank matrix. $\omega$ denotes the exponent of matrix
multiplication, and $\alpha$ denotes the dual exponent of matrix
multiplication. We remark that in some previous papers the running time is
presented with explicit $d$ and $\operatorname{nnz}(A)$. Here we present the
running time assuming $d=\Theta(n)$, $\operatorname{rank}(A)=n$ and
$\operatorname{nnz}(A)=n^{2}$.