$\psi^{\mathrm{d}}(z,\overline{U})$.

######  Lemma 6.8.

For the polarizing partition ${\widehat{B}}\cup{\widehat{N}}=[n]$ let
$Y\subseteq\pi_{\widehat{N}}(\hat{x}^{-1}W)$ be a subspace and let
$\overline{Y}=\operatorname{comp}_{z,{\widehat{N}}}(Y)$. Analogously let
$Z\subseteq\pi_{\widehat{B}}(\hat{s}^{-1}W^{\perp})$ be a subspace and let
$\overline{Z}=\operatorname{comp}_{z,{\widehat{B}}}(Z)$. Then,

$\displaystyle\psi^{\mathrm{p}}(z,\overline{Y})\sigma_{\min}\left({\left.\kern-1.2pt\widehat{\ell}_{z}\vphantom{\big{|}}\right|_{\overline{Y}}}\right)$
$\displaystyle\leq
4n+\left(\frac{2}{\gamma}\cdot\frac{\mu_{1}}{\mu}+1\right)n^{1.5}\left\|{\left.\kern-1.2pt\widehat{\ell}_{z}\vphantom{\big{|}}\right|_{Y}}\right\|\,,\quad\text{and}$
$\displaystyle\psi^{\mathrm{d}}(z,\overline{Z})\sigma_{\min}\left({\left.\kern-1.2pt\widehat{\ell}_{z}^{\perp}\vphantom{\big{|}}\right|_{\overline{Z}}}\right)$
$\displaystyle\leq
4n+\left(\frac{2}{\gamma}\cdot\frac{\mu_{1}}{\mu}+1\right)n^{1.5}\left\|{\left.\kern-1.2pt\widehat{\ell}_{z}\vphantom{\big{|}}\right|_{Z}}\right\|\,.$

###### Proof.

We only prove the first statement, since the second statement can be shown
analogously. From Lemma 2.4 and Proposition 2.10, we have

$\displaystyle\|\widehat{\ell}_{z}(\xi_{\widehat{N}}-\hat{x}^{-1}_{\widehat{N}}x(\mu_{1})_{\widehat{N}})\|$
$\displaystyle\leq\|\xi_{\widehat{B}}-\hat{x}^{-1}_{\widehat{B}}x(\mu_{1})_{\widehat{B}}\|\leq\|\xi_{\widehat{B}}\|+\|\hat{x}^{-1}_{\widehat{B}}x(\mu_{1})_{\widehat{B}}\|$
(45)
$\displaystyle\leq\sqrt{n}+(1+\beta)\|x^{-1}(\mu)_{\widehat{B}}x(\mu_{1})_{\widehat{B}}\|<4n\,.$

Since
$\sigma_{\min}\left({\left.\kern-1.2pt\widehat{\ell}_{z}\vphantom{\big{|}}\right|_{\overline{Y}}}\right)$
is the smallest singular value of
${\left.\kern-1.2pt\widehat{\ell}_{z}\vphantom{\big{|}}\right|_{\overline{Y}}}$,
we can bound

$\displaystyle\psi^{\mathrm{p}}(z,\overline{Y})\sigma_{\min}\left({\left.\kern-1.2pt\widehat{\ell}_{z}\vphantom{\big{|}}\right|_{\overline{Y}}}\right)$
$\displaystyle\leq\|\widehat{\ell}_{z}(\Pi_{\overline{Y}}(\xi_{\widehat{N}}-\hat{x}^{-1}_{\widehat{N}}x^{\mathrm{cp}}(\mu_{1})_{\widehat{N}}))\|$
(46)
$\displaystyle=\|\widehat{\ell}_{z}(\xi_{\widehat{N}}-\hat{x}^{-1}_{\widehat{N}}x^{\mathrm{cp}}(\mu_{1})_{\widehat{N}})-\widehat{\ell}_{z}(\Pi_{Y}(\xi_{\widehat{N}}-\hat{x}^{-1}_{\widehat{N}}x^{\mathrm{cp}}(\mu_{1})_{\widehat{N}}))\|$
$\displaystyle\leq\|\widehat{\ell}_{z}(\xi_{\widehat{N}}-\hat{x}^{-1}_{\widehat{N}}x^{\mathrm{cp}}(\mu_{1})_{\widehat{N}})\|+\|\widehat{\ell}_{z}(\Pi_{Y}(\xi_{\widehat{N}}-\hat{x}^{-1}_{\widehat{N}}x^{\mathrm{cp}}(\mu_{1})_{\widehat{N}}))\|$
$\displaystyle\leavevmode\kern-64.05568pt\mathrel{\mathop{\leq}\limits^{\eqref{eq:bound_empirical_gradient}}}4n+\left\|{\left.\kern-1.2pt\widehat{\ell}_{z}\vphantom{\big{|}}\right|_{Y}}\right\|\|\Pi_{Y}(\xi_{\widehat{N}}-\hat{x}^{-1}_{\widehat{N}}x^{\mathrm{cp}}(\mu_{1})_{\widehat{N}})\|$
$\displaystyle\leq
4n+\left\|{\left.\kern-1.2pt\widehat{\ell}_{z}\vphantom{\big{|}}\right|_{Y}}\right\|\left(\|\Pi_{Y}(\xi_{\widehat{N}})\|+\|\Pi_{Y}(\hat{x}^{-1}_{\widehat{N}}x^{\mathrm{cp}}(\mu_{1})_{\widehat{N}})\|\right)$
$\displaystyle\leq
4n+\left\|{\left.\kern-1.2pt\widehat{\ell}_{z}\vphantom{\big{|}}\right|_{Y}}\right\|\left(\sqrt{n}+\|\Pi_{Y}(\hat{x}^{-1}_{\widehat{N}}x^{\mathrm{cp}}(\mu_{1})_{\widehat{N}})\|\right)\,,$

where the last inequality used
$\|\Pi_{Y}(\xi_{\widehat{N}})\|\leq\|\xi_{\widehat{N}}\|\leq\|\xi\|=\sqrt{n}$.
From Proposition 2.10 and Corollary 4.3 we have that

$\displaystyle\|\hat{x}_{\widehat{N}}^{-1}x^{\mathrm{cp}}(\mu_{1})_{\widehat{N}}\|$
$\displaystyle\leq\sqrt{1+\beta}\|x(\mu)^{-1}_{\widehat{N}}x^{\mathrm{cp}}(\mu_{1})_{\widehat{N}}\|\leq\sqrt{(1+\beta)n}\|x(\mu)^{-1}_{\widehat{N}}x^{\mathrm{cp}}(\mu_{1})_{\widehat{N}}\|_{\infty}$
(47) $\displaystyle\leq 2n^{1.5}\mu_{1}\mu^{-1}\gamma^{-1}\,.$

The claim follows by substituting this in (46). ∎

###  6.5 Overall Analysis

The main result of this section is Theorem 6.10, which shows that in case that
the residuals are small enough, then within a single step we either come
within polynomial factors of the end of the polarized segment, or the smallest
singular value of the expensive subspace becomes polynomial. Theorem 6.1 is
then a simple consequence.

We define

$\zeta(z)\coloneqq\left|\left\\{i:\sigma_{i}(\widehat{\ell}_{z})>\frac{\tau}{n^{1.5}}\right\\}\right|\,$
(48)

as the number of singular values of $\widehat{\ell}_{z}$ (and
$\widehat{\ell}_{z}^{\perp}$) that are larger than $\frac{\tau}{n^{1.5}}$.

######  Theorem 6.9.

Let $\mathrm{CP}[\mu_{1},\mu_{0}]$ be $\gamma$-polarized and let
$z=(x,s)\in\mathcal{N}(\beta)$ be an iterate with parameter
$\overline{\mu}(z)\in(\mu_{1},\mu_{0})$ and assume that the polarizing and
associated partition agree, that is, $B\coloneqq{\widehat{B}}=\widetilde{B}$
and $N\coloneqq{\widehat{N}}=\widetilde{N}$. Further, let
$z^{+}=(x^{+},s^{+})$ be the next iterate of IPM with subspace LLS where the
subspaces used by the algorithm are denoted by $\widetilde{V}$ and
$\widetilde{U}$. Let
$\overline{V}\coloneqq\operatorname{comp}_{z,N}(\widetilde{V})$ and
$\overline{U}\coloneqq\operatorname{comp}_{z,B}(\widetilde{U})$, and assume

$\psi^{\mathrm{p}}\big{(}z,\overline{V}\big{)}+\psi^{\mathrm{d}}\big{(}z,\overline{U}\big{)}+4n^{1.5}\gamma^{-1}\frac{\mu_{1}}{\mu}\leq\frac{1}{16}\enspace.$
(49)

If $\zeta(z)=0$, then

$\overline{\mu}(z^{+})=O\left(\frac{n^{4.5}}{\gamma}\cdot\mu_{1}\right)\,.$

If $\zeta(z)>0$

$\overline{\mu}(z^{+})=O\left(\frac{n^{4.5}}{\gamma}\left(\mu_{1}+\sigma_{\zeta(z)}(\widehat{\ell}_{z})^{-1}\mu\right)\right)\,.$

###### Proof.

As the partitions agree we can set
$\ell_{z}\coloneqq\widehat{\ell}_{z}=\widetilde{\ell}_{z}$. By Lemma 6.7,
$\|\varrho^{\mathrm{p},\widetilde{U}}_{B}\|+\|\varrho^{\mathrm{d},\widetilde{V}}_{N}\|\leq
1/16$ and together with Proposition 2.10 we can therefore bound

$\displaystyle\|\delta_{N}^{\mathrm{p},\widetilde{V}}\|_{\infty}$
$\displaystyle=\|\varrho_{N}^{\mathrm{p},\widetilde{V}}-\xi_{N}\|_{\infty}\leq\|\varrho_{N}^{\mathrm{p},\widetilde{V}}\|_{\infty}+\|\xi\|_{\infty}\leq\frac{1}{16}+\sqrt{1+\beta}\leq
2\,,$ (50) $\displaystyle\|\delta_{B}^{\mathrm{d},\widetilde{U}}\|_{\infty}$
$\displaystyle=\|\varrho_{B}^{\mathrm{d},\widetilde{U}}-\xi_{B}\|_{\infty}\leq\|\varrho_{B}^{\mathrm{d},\widetilde{U}}\|_{\infty}+\|\xi\|_{\infty}\leq\frac{1}{16}+\sqrt{1+\beta}\leq
2\,.$

Recall from Lemma 6.3 that

$\|\delta^{x}_{B}\|\leq\tau\sqrt{n},\,\quad\mbox{and}\quad\|\delta^{s}_{N}\|\leq\tau\sqrt{n}\,.$

Consequently,

$\displaystyle\left\|\frac{\Delta x^{\mathrm{\ell}}\Delta
s^{\mathrm{\ell}}}{\mu}\right\|^{2}$
$\displaystyle=\|\delta^{\mathrm{p},\widetilde{V}}\delta^{\mathrm{d},\widetilde{U}}\|^{2}$
(51)
$\displaystyle=\|\delta_{B}^{\mathrm{p},\widetilde{V}}\delta_{B}^{\mathrm{d},\widetilde{U}}\|^{2}+\|\delta_{N}^{\mathrm{p},\widetilde{V}}\delta_{N}^{\mathrm{d},\widetilde{U}}\|^{2}$
$\displaystyle\leq\|\delta_{B}^{\mathrm{p},\widetilde{V}}\|^{2}\|\delta_{B}^{\mathrm{d},\widetilde{U}}\|^{2}+\|\delta_{N}^{\mathrm{p},\widetilde{V}}\|^{2}\|\delta_{N}^{\mathrm{d},\widetilde{U}}\|^{2}$
$\displaystyle\leq
4(\|\delta_{B}^{\mathrm{p},\widetilde{V}}\|^{2}+\|\delta_{N}^{\mathrm{d},\widetilde{U}}\|^{2})$
$\displaystyle\leq 8n\tau^{2}\,.$

Note that this bound gives us for $(\Delta x^{\mathrm{\ell}},\Delta
s^{\mathrm{\ell}})$ the assumptions of Lemma 2.12 as
$\sqrt{8n}\tau\leq\beta/4$.

Further, note that

$\displaystyle\left\|\frac{(x+\Delta x^{\mathrm{\ell}})(s+\Delta
s^{\mathrm{\ell}})}{\mu}\right\|^{2}$
$\displaystyle=\left\|\frac{(x_{B}+\Delta x^{\mathrm{\ell}}_{B})(s_{B}+\Delta
s^{\mathrm{\ell}}_{B})}{\mu}\right\|^{2}$ (52)
$\displaystyle\quad+\left\|\frac{(x_{N}+\Delta
x^{\mathrm{\ell}}_{N})(s_{N}+\Delta s^{\mathrm{\ell}}_{N})}{\mu}\right\|^{2}$
$\displaystyle=\|(\xi_{B}+\delta^{x}_{B})(\xi_{B}+\delta^{s}_{B})\|^{2}+\|(\xi_{N}+\delta^{x}_{N})(\xi_{N}+\delta^{s}_{N})\|^{2}$
$\displaystyle=\|\varrho^{\mathrm{p},\widetilde{V}}_{B}\varrho^{\mathrm{d},\widetilde{U}}_{B}\|^{2}+\|\varrho^{\mathrm{p},\widetilde{V}}_{N}\varrho^{\mathrm{d},\widetilde{U}}_{N}\|^{2}$
$\displaystyle\leq\|\varrho^{\mathrm{p},\widetilde{V}}_{B}\|_{\infty}^{2}\|\varrho^{\mathrm{d},\widetilde{U}}_{B}\|^{2}+\|\varrho^{\mathrm{p},\widetilde{V}}_{N}\|^{2}\|\varrho^{\mathrm{d},\widetilde{U}}_{N}\|^{2}_{\infty}$
$\displaystyle\leq
4\left(\|\varrho^{\mathrm{d},\widetilde{U}}_{B}\|^{2}+\|\varrho^{\mathrm{p},\widetilde{V}}_{N}\|^{2}\right)$
$\displaystyle\leq
4\left(\|\varrho^{\mathrm{d},\widetilde{U}}_{B}\|+\|\varrho^{\mathrm{p},\widetilde{V}}_{N}\|\right)^{2},$

where the penultimate inequality used that

$\|\varrho_{B}^{\mathrm{p},\widetilde{V}}\|_{\infty}\leq\|\xi_{B}\|_{\infty}+\|\delta^{x}_{B}\|_{\infty}\leq\sqrt{1+\beta}+\sqrt{n}\tau\leq
2\,,$ (53)

due to Proposition 2.10 and Lemma 6.3. Analogously,
$\|\varrho_{N}^{\mathrm{d},\widetilde{U}}\|_{\infty}\leq 2$. Together with
Lemma 6.7, we get

$\left\|\frac{(x+\Delta x^{\mathrm{\ell}})(s+\Delta
s^{\mathrm{\ell}})}{\mu}\right\|\leq
2\left(\|\varrho^{\mathrm{d},\widetilde{U}}_{B}\|+\|\varrho^{\mathrm{p},\widetilde{V}}_{N}\|\right)\leq
2\psi^{\mathrm{p}}(z,\overline{V})+2\psi^{\mathrm{d}}(z,\overline{U})+\frac{8n^{1.5}}{\gamma}\cdot\frac{\mu_{1}}{\mu}\,.$

Lemma 2.12 guarantees a step-length

$\alpha=1-\frac{4}{\beta}\left\|\frac{(x+\Delta x^{\mathrm{\ell}})(s+\Delta
s^{\mathrm{\ell}})}{\mu}\right\|$ (54)

such that $z^{+}\coloneqq(x+\alpha\Delta x^{\mathrm{\ell}},s+\alpha\Delta
s^{\mathrm{\ell}})\in\overline{\mathcal{N}}^{2}(2\beta)$ and

$\displaystyle\overline{\mu}(z^{+})$
$\displaystyle\leq\left(1+\frac{3}{2}\frac{\beta}{\sqrt{n}}\right)(1-\alpha)\mu\leq\frac{8\mu}{\beta}\left\|\frac{(x+\Delta
x^{\mathrm{\ell}})(s+\Delta s^{\mathrm{\ell}})}{\mu}\right\|$ (55)
$\displaystyle\leq\frac{16}{\beta}\left(\frac{4\sqrt{n}}{\gamma}\cdot\mu_{1}+\psi^{\mathrm{p}}(z,\overline{V})\mu+\psi^{\mathrm{d}}(z,\overline{U})\mu\right).$

If $\zeta(z)=0$, then the statement of the theorem follows, since
$\overline{V}=\overline{U}=\\{\mathbf{0}\\}$ and therefore
$\psi^{\mathrm{p}}(z,\overline{V})=\psi^{\mathrm{d}}(z,\overline{U})=0$.

For the rest of the proof, assume $\zeta(z)>0$. Let
$p\coloneqq\dim(\overline{V})$, $r\coloneqq\dim(\overline{U})$ and
$q\coloneqq\dim(\operatorname{im}(\ell_{z}))=\dim(\operatorname{im}(\ell_{z}^{\perp}))$.
As Lemma 6.2 implies
$\|{\left.\kern-1.2pt\ell_{z}^{\perp}\vphantom{\big{|}}\right|_{\widehat{U}}}\|,\|{\left.\kern-1.2pt\ell_{z}\vphantom{\big{|}}\right|_{\widehat{V}}}\|\leq\tau$
we have with Lemma 5.4 that

$\sigma_{p}(\ell_{z})\geq\sigma_{\min}({\left.\kern-1.2pt\ell\vphantom{\big{|}}\right|_{\overline{V}}})\geq\frac{1}{\sqrt{n}}\frac{\|\ell_{z}(\mathbf{V}_{|N|-p+1})\|}{\|\mathbf{V}_{|N|-p+1}\|}>\frac{1}{\sqrt{n}}\cdot\frac{\tau}{n}=\frac{\tau}{n^{1.5}}\,,$
(56)

where the third inequality follows by definition of $V$. This in particular
implies that $p\leq\zeta(z)$ by (48) and so
$\sigma_{p}(\ell_{z})\geq\sigma_{\zeta(z)}(\ell_{z})$. Further, we have by
Lemma 5.4 that

$\sigma_{\min}({\left.\kern-1.2pt\ell\vphantom{\big{|}}\right|_{\overline{V}}})\geq\frac{1}{n^{1.5}}\sigma_{p}(\ell_{z})\,.$
(57)

Analogously, we have that

$\sigma_{r}(\ell_{z})\geq\sigma_{\zeta(z)}(\ell_{z})\quad\text{ and
}\quad\sigma_{\min}({\left.\kern-1.2pt\ell\vphantom{\big{|}}\right|_{\overline{U}}})\geq\frac{1}{n^{1.5}}\sigma_{r}(z)\,.$
(58)

Together with Lemma 6.8 with $Y\coloneqq\widetilde{V}$,
$Z\coloneqq\widetilde{U}$, we have

$\displaystyle\psi^{\mathrm{p}}(z,\overline{V})\sigma_{\zeta(z)}(\ell_{z})$
$\displaystyle\leq\psi^{\mathrm{p}}(z,\overline{V})\sigma_{p}(\ell_{z})$ (59)
$\displaystyle\leavevmode\kern-35.59727pt\mathrel{\mathop{\leq}\limits^{\eqref{eq:sig-
ov-z-
upper}}}n^{1.5}\psi^{\mathrm{p}}(z,\overline{V})\sigma_{\min}({\left.\kern-1.2pt\ell\vphantom{\big{|}}\right|_{\overline{V}}})$
$\displaystyle\leq
n^{1.5}(4n+\left(2\mu_{1}\mu^{-1}\gamma^{-1}+1\right)n^{1.5}\tau)$
$\displaystyle\leq
n^{1.5}(4n+\left(2\gamma^{-1}+1\right)n^{3}\sigma_{\zeta(z)}(\ell_{z}))\,,$

where the last inequality follows by definition of the index $\zeta(z)$.
Analogously we get on the dual side

$\psi^{\mathrm{d}}(z,\overline{U})\sigma_{\zeta(z)}(\ell_{z})\leq
n^{1.5}(4n+\left(2\gamma^{-1}+1\right)n^{3}\sigma_{\zeta(z)}(\ell_{z}))\,.$
(60)

Plugging these into (55), we get

$\overline{\mu}(z^{+})\leq\frac{256}{\beta\gamma}\left(\sqrt{n}\mu_{1}+n^{4.5}\mu[\sigma_{\zeta(z)}(\ell_{z})]^{-1}\right)\,,$
(61)

which proves the theorem. ∎

With Theorem 6.9 at hand we can show Theorem 6.10: either _(i)_ the _smallest
large_ singular value at $z$ indexed by $\zeta(z)$ becomes bounded at the next
iterate $z^{+}$ or _(ii)_ the gap of the next iterate $\overline{\mu}(z^{+})$
is close to or beyond the end of the segment.

######  Theorem 6.10.

Let $\mathrm{CP}[\mu_{1},\mu_{0}]$ be $\gamma$-polarized with polarizing
partition $B\cup N=[n]$ for $\gamma\in[0,1]$. Then, given an iterate
$z=(x,s)\in\mathcal{N}^{2}(\beta)$ with parameter
$\overline{\mu}(z)\in(\mu_{1},\mu_{0})$, let
$z^{+}=(x^{+},s^{+})\in\mathcal{N}^{2}(\beta)$ denote the next iterate in IPM
with subspace LLS (Algorithm 1). If $\zeta(z)>0$, then one of the following
hold:

  1. (i)

$\sigma_{\zeta(z)}(\widehat{\ell}_{z^{+}})=O(n^{6.5}\gamma^{-3})$,

  2. (ii)

$\overline{\mu}(z^{+})\leq O(n^{4.5}\gamma^{-2}\mu_{1})$.

If $\zeta(z)=0$, then (ii) holds.

###### Proof.

Let $\mu\coloneqq\overline{\mu}(z)$. Recall that Algorithm 1 runs the subspace
LLS with the associated partition $\widetilde{B}\cup\widetilde{N}=[n]$. For
the case $\zeta(z)=0$, the case (ii) is immediate by Theorem 6.9.

For the rest of the proof, we assume $\zeta(z)>0$. We show the following
crucial claim:

######  Claim 6.11.

$\overline{\mu}(z^{+})=O\left(\frac{n^{4.5}}{\gamma}\left(\mu_{1}+\sigma_{\zeta(z)}(\widehat{\ell}_{z})^{-1}\mu\right)\right)\,.$

###### Proof.

We distinghuish two cases based on whether the polarizing and associated
partition agree.

  1. Case I.

Assume that the associated and polarizing partitions agree, i.e.,
$B:={\widehat{B}}=\widetilde{B}$ and $N:={\widehat{N}}=\widetilde{N}$. Let
$\overline{V}\coloneqq\operatorname{comp}_{z,N}(\widetilde{V}),\overline{U}\coloneqq\operatorname{comp}_{z,B}(\widetilde{U})$.
We further distinguish two cases based on whether the terms
$\psi^{\mathrm{p}}(z,\overline{V})$ and $\psi^{\mathrm{d}}(z,\overline{U})$
are small.

    1. Case I.1.

$\psi^{\mathrm{p}}(z,\overline{V})+\psi^{\mathrm{d}}(z,\overline{U})+4n^{1.5}\gamma^{-1}\frac{\mu_{1}}{\mu}\leq\frac{1}{16}\enspace.$

The claim is immediate by Theorem 6.9.

    2. Case I.2.

$\psi^{\mathrm{p}}(z,\overline{V})+\psi^{\mathrm{d}}(z,\overline{U})+4n^{1.5}\gamma^{-1}\frac{\mu_{1}}{\mu}>\frac{1}{16}\enspace.$

By Lemma 6.2 and Lemma 6.8 with we have that

$\displaystyle\frac{1}{16}$
$\displaystyle<\psi^{\mathrm{p}}(z,\overline{V})+\psi^{\mathrm{d}}(z,\overline{U})+4n^{1.5}\gamma^{-1}\frac{\mu_{1}}{\mu}$
(62) $\displaystyle\leq
2\cdot\left(4n+\left(2\gamma^{-1}\frac{\mu_{1}}{\mu}+1\right)n^{1.5}\tau\right)\sigma_{\zeta(z)}(\widehat{\ell}_{z})^{-1}+4n^{1.5}\gamma^{-1}\frac{\mu_{1}}{\mu}\enspace.$

In particular, for the next iterate $z^{+}$, we have

$\displaystyle\overline{\mu}(z^{+})$ $\displaystyle\leq\mu$
$\displaystyle\leavevmode\kern-18.36113pt\mathrel{\mathop{\leq}\limits^{\eqref{eq:sdfwef}}}16\cdot
2\cdot\left(4n+\left(2\gamma^{-1}\frac{\mu_{1}}{\mu}+1\right)n^{1.5}\tau\right)\sigma_{\zeta(z)}(\widehat{\ell}_{z})^{-1}\mu+4n^{1.5}\gamma^{-1}\mu_{1}$
$\displaystyle\leq
32\cdot\left(4n+\left(2\gamma^{-1}+1\right)n^{1.5}\tau\right)\sigma_{\zeta(z)}(\widehat{\ell}_{z})^{-1}\mu+4n^{1.5}\gamma^{-1}\mu_{1}$
$\displaystyle=O(n^{1.5}\gamma^{-1}(\mu_{1}+\sigma_{\zeta(z)}(\widehat{\ell}_{z})^{-1}\mu))\,.$

which follows by choice of $\tau$ in (30). Thus, the claim follows.

  2. Case II.

The associated and polarizing partitions do not agree.

Let $\widehat{V}\coloneqq V^{*}_{z,{\widehat{N}}}(\tau)$ and
$\widehat{U}\coloneqq U^{*}_{z,{\widehat{B}}}(\tau)$ as defined in Definition
5.2. Clearly,
$\left\|{\left.\kern-1.2pt\widehat{\ell}_{z}\vphantom{\big{|}}\right|_{V}}\right\|,\left\|{\left.\kern-1.2pt\widehat{\ell}^{\perp}_{z}\vphantom{\big{|}}\right|_{U}}\right\|\leq\tau$.
Applying Lemma 6.7 for these subspaces, it follows that

$\psi^{\mathrm{p}}(z,\operatorname{comp}_{z,{\widehat{N}}}(\widehat{V}))+\psi^{\mathrm{d}}(z,\operatorname{comp}_{z,{\widehat{B}}}(\widehat{U}))+4n^{1.5}\gamma^{-1}\frac{\mu_{1}}{\mu}>\frac{1}{16}\enspace.$

We can now use the same argument as in Case I.2 for the subspaces
$\widehat{V}$, $\widehat{U}$ and the partition
$({\widehat{B}},{\widehat{N}})$.

∎

From the above claim, if
$\mu_{1}\geq\sigma_{\zeta(z)}(\widehat{\ell}_{z})^{-1}\mu$, then
$\overline{\mu}(z^{+})=O(n^{4.5}\gamma^{-1}\mu_{1})$, so we are in case (ii)
of the theorem. Otherwise,
$\overline{\mu}(z^{+})=O(n^{4.5}\gamma^{-1}\sigma_{\zeta(z)}(\widehat{\ell}_{z})^{-1}\mu)$.
By Lemma 6.5 we have that

$\sigma(\widehat{\ell}_{z^{+}})\leq
4n^{2}\gamma^{-2}\overline{\mu}(z^{+})\mu^{-1}\sigma(\widehat{\ell}_{z})\,.$
(63)

In particular,

$\sigma_{\zeta(z)}(\widehat{\ell}_{z^{+}})\leq\frac{4n^{2}}{\gamma^{2}}\cdot\frac{\overline{\mu}(z^{+})}{\mu}\sigma_{\zeta(z)}(\widehat{\ell}_{z})=O(n^{6.5}\gamma^{-3}).$
(64)

Hence, we are in case (i) of the theorem. The proof is now complete. ∎

From Theorem 6.10 we can now derive the proof of the main theorem as follows.

###### Proof of Theorem 6.1.

Consider any two consecutive iterates $z=(x,s)$ and $z^{+}=(x^{+},s^{+})$ in
IPM with subspace LLS. In case (ii) of Theorem 6.10, the end of the polarized
segment will be reached within $O(\sqrt{n}\log(n/\gamma))$ iterations, since
the affine scaling step itself leads to an $1-\beta/\sqrt{n}$ decrease in the
normalized gap, and we always choose the better of the two steps.

In case (i) of Theorem 6.10, we have
$\sigma_{\zeta(z)}(\widehat{\ell}_{z^{+}})=O(n^{6.5}\gamma^{-3})$. After
$O(\sqrt{n}\log(n/\gamma))$ additional iterations, we know that by Lemma 6.5,
any subsequent iterate $z^{++}=(x^{++},s^{++})$ satisfies
$\sigma_{\zeta(z)}(\widehat{\ell}_{z^{++}})<\tau/n^{1.5}$. By definition of
$\zeta(\cdot)$ in (48), we have $\zeta(z^{++})<\zeta(z)$ for all these
iterates. Clearly, such an event may occur at most $n$ times. ∎

##  7 Amortization over segments

In this section we prove Theorem 1.4. The proof is immediate from the
following two theorems. The first one gives a bound in terms of the changes
between the consecutive polarized partitions.

######  Theorem 7.1.

For any $T\in\mathbb{N}$ let
$0\leq\mu^{(T)}<\mu^{(T-1)}<\ldots<\mu^{(1)}<\mu^{(0)}$ such that for all
$1\leq i\leq T$ we have that $\mathrm{CP}[\mu^{(i)},\mu^{(i-1)}]$ is
$\gamma$-polarized with polarizing partition $B^{(i)}\cup N^{(i)}$ such that
w.l.o.g. $N^{(i)}\neq N^{(i-1)}$ for all $1\leq i\leq T$. Let
$N^{(0)}\coloneqq\emptyset$. Then, Algorithm 1, starting from any point
$z^{(0)}\in\mathcal{N}^{2}(\beta)$ such that
$\overline{\mu}(z^{(0)})\leq\mu^{(0)}$ finds a point
$z\in\overline{\mathcal{N}}^{2}(\beta)$ such that
$\overline{\mu}(z)\leq\mu^{(T)}$ in

$O\left(\sqrt{n}\log(n/\gamma)\sum_{i=1}^{T}\left|N^{(i)}\Delta
N^{(i-1)}\right|\right)$ (65)

many iterations.

Note that Theorem 1.1 is an immediate consequence since each term in the sum
is $\leq n$. To obtain Theorem 1.4, our second main ingredient however shows
that from primal only straight-line complexity bounds we can already obtain
strong bounds on primal-dual polarization.

######  Theorem 7.2.

Let $\theta\in(0,1)$ and $\mu_{0}\geq\mu_{1}\geq 0$. The segment
$\mathrm{CP}[\mu_{1},\mu_{0}]$ can be decomposed into a sequence of
$\frac{1-\theta}{32n}$-polarized segments with partitions $(B^{(k)},N^{(k)})$,
$k\in[T]$ such that

$\sum_{k=1}^{T}|N^{(k)}\Delta N^{(k-1)}|\leq
2\min\left\\{\sum_{i=1}^{n}\operatorname{SLC}^{\mathrm{p}}_{\theta,i}(n\mu_{1},n\mu_{0}),\sum_{i=1}^{n}\operatorname{SLC}^{\mathrm{d}}_{\theta,i}(n\mu_{1},n\mu_{0})\right\\}\,,$

where $N^{(0)}\coloneqq\emptyset$.

We prove Theorem 7.1 in Section 7.1 and Theorem 7.2 in Section 7.2.

###  7.1 Bounding by changes in the partition

The crucial statement towards proving Theorem 7.1 is the following lemma on
lifting operators for different partitions. Recall that for a linear operator
$L$, we define $\sigma_{i}(L)=0$ for all $i>\operatorname{rk}(L)$.

######  Lemma 7.3.

Given any subspace $W\subseteq\mathbb{R}^{n}$ and given two partitions $B\cup
N=[n]$ and $\hat{B}\cup\hat{N}=[n]$ we have for the lifting maps
$\ell\coloneqq\ell_{N}^{W}$ and $\hat{\ell}\coloneqq\ell_{\hat{N}}^{W}$ that

$\sigma_{i}(\ell)\geq\sigma_{i+|N\Delta\hat{N}|}(\hat{\ell})\,$ (66)

for all $i\geq 1$.

The proof makes use of following alternative min-max characterization to (32)
of the singular values.

######  Lemma 7.4.

For a matrix $\mathbf{M}\in\mathbb{R}^{m\times n}$ let
$T\subseteq\mathbb{R}^{n}$ be a subspace such that
$T\subseteq\ker(\mathbf{M})$. Then, for $i\leq n-\dim(T)$ we have

$\sigma_{i}(\mathbf{M})=\min_{\begin{subarray}{c}\dim(S)+\dim(T)=n-i+1,\\\
S\perp T\end{subarray}}\,\max_{u\in
S\setminus\\{\mathbf{0}\\}}\frac{\|\mathbf{M}u\|}{\|u\|}$ (67)

###### Proof.

The $\leq$ direction in (67) is immediate from (32). We need to show that
equality holds. Let $\mathbf{M}=\mathbf{U}\mathbf{\Sigma}\mathbf{V}^{\top}$ be
a singular value decomposition of $\mathbf{M}$ such that
$\operatorname{im}(\mathbf{V}_{\geq n-\dim(T)+1})=T$ and the diagonal of
$\mathbf{\Sigma}$ is non-increasing. Such a decomposition exists as
$T\subseteq\ker(\mathbf{M})$. By standard arguments we have that
$\sigma_{i}(\mathbf{M})=\mathbf{\Sigma}_{i,i}$. For $i\leq n-\dim(T)$, the
minimum in (67) is attained by choosing
$S=\operatorname{im}(\mathbf{V}_{\\{i,\ldots,n-\dim(T)\\}})$.∎

######  Corollary 7.5.

For a subspace $W\subseteq\mathbb{R}^{n}$, and a lifting map
$\ell\colon\mathbb{R}^{N}\to W$ for $N\subseteq[n]$ we have for
$i\leq\dim(\pi_{N}(W))$

$\sigma_{i}(\ell)=\min_{\begin{subarray}{c}S\subseteq\pi_{N}(W)\\\
\dim(S)=\dim(\pi_{N}(W))-i+1\end{subarray}}\sigma_{\max}\left({\left.\kern-1.2pt\ell\vphantom{\big{|}}\right|_{S}}\right),$
(68)

###### Proof.

Use Lemma 7.4 with $T=\pi_{N}(W)^{\perp}\subseteq\ker(\ell)$. The result
follows as $|N|$ is the dimension of the space and
$\dim(\pi_{N}(W))=|N|-\dim(\pi_{N}(W)^{\perp})$. ∎

###### Proof of Lemma 7.3.

Let $\bar{N}\coloneqq N\cap\hat{N}$,
$\bar{B}\coloneqq[n]\setminus\bar{N}=B\cup\hat{B}$, and define
$\bar{\ell}\coloneqq\ell_{\bar{N}}^{W}$.

First, we are going to prove that for all $i\in\mathbb{N}$ we have
$\sigma_{i}(\ell)\geq\sigma_{i+|N\setminus\bar{N}|}(\bar{\ell})$. Note that
$\dim(\pi_{N}(W))\geq\dim(\pi_{\bar{N}}(W))$. For $i>\dim(\pi_{N}(W))$, we
have $\sigma_{i}(\ell)=\sigma_{i+|N\setminus\bar{N}|}(\bar{\ell})=0$. Assume
now $i\leq\dim(\pi_{N}(W))$. By Corollary 7.5, there exists a subspace
$S^{(i)}\subseteq\pi_{N}(W)$, $\dim(S)=\dim(\pi_{N}(W))-i+1$ with

$\sigma_{i}(\ell)=\sigma_{\max}\left({\left.\kern-1.2pt\ell\vphantom{\big{|}}\right|_{S^{(i)}}}\right)\,.$
(69)

Consider $T^{(i)}\coloneqq S^{(i)}\cap\mathbb{R}_{\bar{N}}^{N}$. Note that
$\dim(\pi_{\bar{N}}(T^{(i)}))=\dim(T^{(i)})$ as
$\pi_{N\setminus\bar{N}}(T^{(i)})=\\{\mathbf{0}_{N\setminus\bar{N}}\\}$ by
definition. Further, $\pi_{\bar{N}}(T^{(i)})\subseteq\pi_{\bar{N}}(W)$ by
construction. Therefore, we have that

$\displaystyle\dim(\pi_{\bar{N}}(T^{(i)}))$
$\displaystyle=\dim(T^{(i)})\geq\dim(S^{(i)})-|N\setminus\bar{N}|$ (70)
$\displaystyle=\dim(\pi_{N}(W))-i+1-|N\setminus\bar{N}|\,,$

where the inequality follows as $T^{(i)}$ arises from $S^{(i)}$ by adding
$N\setminus\bar{N}$ homogeneous linear equations to its defining system.
Finally, note that for any $v\in\pi_{\bar{N}}(T^{(i)})$ we have that

$\|\bar{\ell}(v)\|=\min_{w\in
W,w_{\bar{N}}=v}\|w_{[n]\setminus\bar{N}}\|\leq\min_{\begin{subarray}{c}w\in
W,w_{\bar{N}}=v,\\\
w_{N\setminus\bar{N}}=\mathbf{0}_{N\setminus\bar{N}}\end{subarray}}\|w_{[n]\setminus\bar{N}}\|=\|\ell(\mathbf{0}_{N\setminus\bar{N}},v)\|\,,$
(71)

and so in particular

$\sigma_{\max}\left({\left.\kern-1.2pt\bar{\ell}\vphantom{\big{|}}\right|_{\pi_{\bar{N}}(T^{(i)})}}\right)\leq\sigma_{\max}\left({\left.\kern-1.2pt\ell\vphantom{\big{|}}\right|_{T^{(i)}}}\right)\,.$
(72)

From here, since $\dim(\pi_{\bar{N}}(W))\leq\dim(\pi_{N}(W))$ we get that

$\displaystyle\sigma_{i+|N\setminus\bar{N}|}(\bar{\ell})$
$\displaystyle\leavevmode\kern-28.61118pt\mathrel{\mathop{\leq}\limits^{\eqref{eq:dim-
bound}}}\sigma_{\dim(\pi_{N}(W))-\dim(\pi_{\bar{N}}(T^{(i)}))+1}(\bar{\ell})\stackrel{{\scriptstyle\text{Cor.}~{}\ref{cor:alternative-
min-max-
principle}}}{{\leq}}\sigma_{\max}\left({\left.\kern-1.2pt\bar{\ell}\vphantom{\big{|}}\right|_{\pi_{\bar{N}}(T^{(i)})}}\right)$
(73)
$\displaystyle\leavevmode\kern-39.04175pt\mathrel{\mathop{\leq}\limits^{\eqref{eq:dom-
lift-bar-
lift}}}\sigma_{\max}\left({\left.\kern-1.2pt\ell\vphantom{\big{|}}\right|_{T^{(i)}}}\right)\leq\sigma_{\max}\left({\left.\kern-1.2pt\ell\vphantom{\big{|}}\right|_{S^{(i)}}}\right)=\sigma_{i}(\ell)\,.$

It remains to show that we can use similar shift argumentation between the
operators $\bar{\ell}$ and $\hat{\ell}$. This corresponds to adding the
elements in $\hat{N}\setminus N$ to $\bar{N}$. But note that using Lemma 2.18
this is equivalent to considering the adjoint operator
$\ell_{\bar{B}}^{W^{\perp}}=-\operatorname{ad}[\ell_{\bar{N}}^{W}]$ where
$\bar{B}=[n]\setminus\bar{N}$ and removing the elements in $\hat{B}\setminus
B$ from $\bar{B}$. Thus, applying the same arguments we used to obtain (73) we
get the dual statement

$\sigma_{i}(\operatorname{ad}[\bar{\ell}])\geq\sigma_{i+|\bar{B}\setminus\hat{B}|}(\operatorname{ad}[\hat{\ell}])\,,$
(74)

for all $i\geq 1$. Now, using Lemma 2.18 we get for all $i\geq 1$ that

$\sigma_{i}(\bar{\ell})=\sigma_{i}(\operatorname{ad}[\bar{\ell}])\geq\sigma_{i+|\bar{B}\setminus\hat{B}|}(\operatorname{ad}[\hat{\ell}])=\sigma_{i+|\hat{N}\setminus\bar{N}|}(\hat{\ell})\,$
(75)

holds, where we use that
$|\hat{N}\setminus\bar{N}|=|\bar{B}\setminus\hat{B}|$. Combining (73) and (75)
gives the result as now

$\displaystyle\sigma_{i}(\ell)$
$\displaystyle\geq\sigma_{i+|N\setminus\bar{N}|}(\bar{\ell})=\sigma_{i+|N\setminus\hat{N}|}(\bar{\ell})\geq\sigma_{i+|N\setminus\hat{N}|+|\hat{N}\setminus\bar{N}|}(\hat{\ell})$
(76) $\displaystyle=\sigma_{i+|N\setminus\hat{N}|+|\hat{N}\setminus
N|}(\hat{\ell})=\sigma_{i+|N\Delta\hat{N}|}(\hat{\ell})\,$

for all $i$. ∎

We need few more preparations to prove Theorem 7.1. First, consider the
iterates $z^{(0)},\ldots,z^{(K)}$ of the algorithm, with $z^{(K)}$ being the
first iterate with $\overline{\mu}(z^{(K)})\leq\mu^{(T)}$. Without loss of
generality we can assume that
$\mu^{(1)}<\overline{\mu}(z^{(0)})\leq\mu^{(0)}$.

Let $t_{0}\coloneqq 0$ and for $i\in[T]$, define $t_{i}$ as the largest index
of an iterate with $\mu(z^{(t_{i})})>\mu^{(i)}$. Thus, $t_{T}=K-1$. Further,
let $y^{(0)}\coloneqq z^{(0)}$ and for $i\in[T]$, let
$y^{(i)}\in\overline{\mathcal{N}}^{2}(\beta)$ be any point with
$\overline{\mu}(y^{(i)})=\mu^{(i)}$.

Let us extend the notation (48) to

$\zeta^{(i)}(z)\coloneqq\left|\left\\{j:\sigma_{j}(\ell_{z,N^{(i)}})>\frac{\tau}{n^{1.5}}\right\\}\right|\,.$
(77)

We start by giving an outline of the proof of Theorem 7.1. Consider the
behaviour of the algorithm on any polarized segment $(B^{(i)},N^{(i)})$.
Theorem 6.10 guarantees that after every iterate $z^{(t)}$, the next iterate
$z^{(t+1)}$ is either near the end of the segment, or beyond this segment, or
$\sigma_{\zeta^{(i)}(z^{(t)})}(\ell_{z^{(t+1)},N^{(i)}})=O(n^{6.5}\gamma^{-3})$.
Recall from Lemma 6.5 that the singular values are scaling down near-linearly
along any polarized segment: for $z,\tilde{z}\in\mathcal{N}^{2}(\beta)$ with
$\mu=\overline{\mu}(z)>\overline{\mu}(\tilde{z})=\tilde{\mu}$, we have
$\sigma(\ell_{\tilde{z},N^{(i)}})\leq(4n^{2}/\gamma^{2})\cdot(\tilde{\mu}/\mu)\sigma(\ell_{z,N^{(i)}})$.
Since $\overline{\mu}(z)$ decreases by at least a factor $1-\beta/\sqrt{n}$ in
each iteration, we get that within every $O(\sqrt{n}\log(n/\gamma))$
iterations, either we reach the end of the segment, or ${\zeta^{(i)}(\cdot)}$
decreases.

Let us now assume that the bound were simply
$\sigma(\ell_{\tilde{z},N^{(i)}})\leq(\tilde{\mu}/\mu)\sigma(\ell_{z,N^{(i)}})$,
without the $(4n^{2}/\gamma^{2})$ factor. Then, $\zeta^{(i)}(\cdot)$ would
decrease monotonically in $\overline{\mu}(z)$ along each polarized segment.
When it reaches the endpoint of segment $(B^{(i)},N^{(i)})$ at $y^{(i)}$,
Lemma 7.3 controls the handover to the next segment:
$\zeta^{(i+1)}(y^{(i)})\leq\zeta^{(i)}(y^{(i)})+|N^{(i)}\Delta N^{(i+1)}|$.

In summary, $\zeta^{(i)}(\cdot)$ decreases in every
$O(\sqrt{n}\log(n/\gamma))$ iteration. When reaching the end of the $i$-th
segment, we switch to the potential $\zeta^{(i+1)}(\cdot)$. This may be
larger, but only by $|N^{(i)}\Delta N^{(i+1)}|$. This would yield the bound in
Theorem 7.1.

This argument unfortunately breaks due to the $(4n^{2}/\gamma^{2})$ factor in
Lemma 6.5. The singular values may in fact increase on the short term. This
would not be a problem on sufficiently ‘long’ segments. However, on ‘short’
segments, this could lead to an increase in singular values, while there may
not be sufficiently many—$\Omega(\sqrt{n}\log(n/\gamma))$—iterations to
compensate. Such increments could even aggregate over a sequence of short
segments.

The proof below—in a sense—works with a more robust version of (77). We track
singular values above a threshold $\Gamma^{q_{i}}\tau/n^{1.5}$ for a parameter
$\Gamma$ and a value ${q_{i}}$ at the $i$-th segment. The additional factor
represents possible increases accumulated on previous short segments. However,
the contributions $|N^{(j)}\Delta N^{(j-1)}|$ of these short segments will
‘pay’ for bringing down large singular values later.

We need a technical lemma that controls the change in the singular values and
of $\zeta^{(i)}(\cdot)$ along a polarized segment. In the next lemma, $k=0$
corresponds to a ‘short’ distance between points $y$ and $y^{\prime}$; in part
(i), the singular values may increase on a short distance, but must decrease
for $k\geq 2$.

######  Lemma 7.6.

There exists values $\Gamma=O(n^{9}\gamma^{-5})$ and
$D=O(\sqrt{n}\log(n/\gamma))$ such that for any $i\in[T]$, and
$y,y^{\prime}\in\overline{\mathcal{N}}^{2}(\beta)$ with
$\mu^{(i)}\leq\overline{\mu}(y^{\prime})<\overline{\mu}(y)\leq\mu^{(i-1)}$,
the following hold. Assume that Algorithm 1 has $M$ iterates $z^{(t)}$ such
that
$\overline{\mu}(y^{\prime})\leq\overline{\mu}(z^{(t)})\leq\overline{\mu}(y)$.
Let $k\coloneqq\lfloor M/D\rfloor$. Then,

  1. (i)

$\sigma(\ell_{y^{\prime},N^{(i)}})\leq\sigma(\ell_{y,N^{(i)}})/\Gamma^{k-1}$.

  2. (ii)

$k\leq\zeta^{(i)}(y)$, and if $k\geq 1$ then
$\zeta^{(i)}(y^{\prime})\leq\zeta^{(i)}(y)-k$.

###### Proof.

Let us select $\Gamma_{0}=O(n^{6.5}\gamma^{-3})$ as the bound in Theorem
6.10(i), and let $\Gamma\coloneqq 4n^{2}\gamma^{-2}\Gamma_{0}/\tau$. Let
$D=2\log(\Gamma)/\log(1-\beta/\sqrt{n})=O(\sqrt{n}\log(n/\gamma))$ be twice
the number of iterations such that $\overline{\mu}(z)$ is guaranteed decrease
by a factor $\Gamma$. By Theorem 6.10 and Lemma 6.5, starting from any
iteration on the polarized segment $(B^{(i)},N^{(i)})$, within $D/2$
iterations we either reach the end of the segment, or $\zeta^{(i)}(z)$
decreases by 1.

##### Proof of Part (i)

In case $k=0$, that is, there are fewer than $D$ iterations between $y$ and
$y^{\prime}$, then we use the trivial bound
$\sigma(\ell_{y^{\prime},N^{(i)}})\leq
4n^{2}\gamma^{-2}\sigma(\ell_{y,N^{(i)}})\leq\Gamma\sigma(\ell_{y,N^{(i)}})$
from Lemma 6.5. If $k\geq 1$, then let $z^{(t)}$ be the first iterate with
$\overline{\mu}(z^{(t)})\leq(4n^{2}\gamma^{-2})^{-1}\overline{\mu}(y)$ and let
$z^{(t^{\prime})}$ be the last iterate with
$\overline{\mu}(z^{(t^{\prime})})\geq
4n^{2}\gamma^{-2}\overline{\mu}(y^{\prime})$. By the choice of $D$, there are
at most $D/4$ iterates between $y$ and $t$, and at most $D/4$ iterates between
$t^{\prime}$ and $y^{\prime}$. By Lemma 6.5, we have
$\sigma(\ell_{z^{(t)},N^{(i)}})\leq\sigma(\ell_{y,N^{(i)}})$ and
$\sigma(\ell_{z^{(t^{\prime})},N^{(i)}})\geq\sigma(\ell_{y^{\prime},N^{(i)}})$.
As noted above, every $D/2$ iterations between $t$ and $t^{\prime}$ decreases
$\overline{\mu}(z)$ by at least a factor $\Gamma$. This implies the bound.

##### Proof of Part (ii)

Assuming $k\geq 1$, we pick $z^{(t)}$ and $z^{(t^{\prime})}$ as above. We have
$\zeta^{(i)}(z^{(t)})\leq\zeta^{(i)}(y)$ and
$\zeta^{(i)}(z^{(t^{\prime})})\geq\zeta^{(i)}(y^{\prime})$. Every $D/2$
iterations between $t$ and $t^{\prime}$ decrease $\zeta^{(i)}(z)$ by at least
one. We also have $\zeta^{(i)}(y)\geq k$: once $\zeta^{(i)}(z)=0$, we must
reach the end of the segment within $D/2$ iterations. ∎

###### Proof of Theorem 7.1.

By induction on $i=1,\ldots,T$, we prove the following statement; the theorem
follows for $i=T$. Recall $N^{(0)}=\emptyset$ and $t_{0}=0$. We let $\Gamma$
and $D$ as in Lemma 7.6. Recall that $t_{0}=0$ and for $i>0$, $t_{i}$ is the
largest index of an iterate with $\mu(z^{(t_{i})})>\mu^{(i)}$.

$\displaystyle\exists p_{i},q_{i}\in\mathbb{N}\quad\textrm{s.t.}$
$\displaystyle\quad t_{i}+D(p_{i}+q_{i})\leq
4D\sum_{j=1}^{i}\left|N^{(j)}\Delta N^{(j-1)}\right|$ (78)
$\displaystyle\textrm{and}\quad\sigma_{p_{i}}(\ell_{y^{(i)},N^{(i)}})\leq\frac{\tau}{n^{1.5}}\Gamma^{q_{i}}\,.$

We say that $p_{i}$ and $q_{i}$ are _suitable_ if the requirement above is
satisfied. For the base case $i=1$, we set $p_{1}=|N^{(1)}|+1$, $q_{1}=0$.
Note that $\ell_{z,N^{(1)}}$ can have at most $|N^{(1)}|$ nonzero singular
values, hence $p_{1}$ and $q_{1}$ are trivially suitable. Lemma 7.6(ii) for
$y=z^{(0)}$ and $y^{\prime}=z^{(t_{1})}$ gives that
$\lfloor(t_{1}-t_{0})/D\rfloor\leq\zeta^{(1)}(z^{(0)})\leq|N^{(1)}|$. Hence,

$t_{1}+D(p_{1}+q_{1})\leq D(2|N^{(1)}|+2)\leq 4D|N^{(1)}\Delta N^{(0)}|\,.$

Assume the statement holds for $i$; we now prove it for $i+1$. Let
$m_{i+1}\coloneqq|N^{(i+1)}\Delta N^{(i)}|$; recall the assumption
$m_{i+1}>0$. Further, let $k\coloneqq\lfloor(t_{i+1}-t_{i})/D\rfloor$; in
particular $t_{i+1}-t_{i}\leq D(k+1)$. Then, it suffices to show that

$k+1+p_{i+1}+q_{i+1}\leq p_{i}+q_{i}+4m_{i+1}\,.$ (79)

First, note that by Lemma 7.3 we get

$\sigma_{p_{i}+m_{i+1}}(\ell_{y^{(i)},N^{(i+1)}})\leq\sigma_{p_{i}}(\ell_{y^{(i)},N^{(i)}})$
(80)

  1. Case I.

If $k\leq q_{i}+1$, then let us define $p_{i+1}\coloneqq p_{i}+m_{i+1}$,
$q_{i+1}\coloneqq q_{i}-k+1$. Then, $p_{i+1}$ and $q_{i+1}$ are suitable due
to (80) and Lemma 7.6(i). Now (79) holds, since

$k+1+p_{i+1}+q_{i+1}=p_{i}+q_{i}+m_{i+1}+2\leq p_{i}+q_{i}+4m_{i+1}\,,$

using that $m_{i+1}\geq 1$.

  2. Case II.

If $k\geq q_{i}+2$, then let us define

$p_{i+1}\coloneqq p_{i}+q_{i}+m_{i+1}-k+1\quad\textrm{and}\quad
q_{i+1}\coloneqq 0\,.$

We see that (79) holds; it is left to argue that $p_{i+1}$ and $q_{i+1}$ are
suitable. To see this, let us first set $t^{\prime}\coloneqq
t_{i}+D(q_{i}+1)$. Thus,
$\overline{\mu}(z^{(t^{\prime})})>\overline{\mu}(z^{(t_{i+1})})\geq\mu^{(i+1)}$.
Using (80) and Lemma 7.6(i) for $y^{\prime}=z^{(t^{\prime})}$ and $y=y^{(i)}$,
we get

$\sigma_{p_{i}+m_{i+1}}(\ell_{z^{(t^{\prime})},N^{(i+1)}})\leq\frac{\tau}{n^{1.5}}\,,$

that is, $\zeta^{(i+1)}(z^{(t^{\prime})})\leq p_{i}+m_{i+1}-1$. Now,
$\lfloor(t_{i+1}-t^{\prime})/D\rfloor=k-q_{i}-1\geq 1$. Using Lemma 7.6(ii)
for $y=z^{(t^{\prime})}$ and $y^{\prime}=y^{(i+1)}$, we get

$\zeta^{(i+1)}(y^{({i+1})})\leq\zeta^{(i+1)}(z^{(t^{\prime})})-(k-q_{i}-1)\leq
p_{i}+q_{i}+m_{i+1}-k\,.$

This implies that

$\sigma_{p_{i+1}}(\ell_{y^{(i+1)},N^{(i+1)}})\leq\frac{\tau}{n^{1.5}}\,,$

in other words, our chosen $p_{i+1}$ and $q_{i+1}$ are suitable.

∎

###  7.2 Decomposition of primal segments into primal-dual segments

######  Lemma 7.7.

Let $g\geq 0$ and $\alpha\geq 1$. Then for all $i\in[n]$ we have
$x^{\mathfrak{m}}_{i}(\alpha g)\leq\alpha x^{\mathfrak{m}}_{i}(g)$ and
$x^{\mathfrak{m}}_{i}(\frac{1}{\alpha}g)\geq\frac{1}{\alpha}x^{\mathfrak{m}}_{i}(g)$.

###### Proof.

We use the concavity of $g\mapsto x^{\mathfrak{m}}_{i}(g)$ (Lemma 1.5) and
deduce that
$(1-\frac{1}{\alpha})x^{\mathfrak{m}}_{i}(0)+\frac{1}{\alpha}x^{\mathfrak{m}}_{i}(\alpha
g)\leq x^{\mathfrak{m}}_{i}(g)$. The first inequality of the lemma follows
from $x^{\mathfrak{m}}_{i}(0)\geq 0$. The second inequality follows from the
first applied to $\tilde{g}=\frac{g}{\alpha}$. ∎

A simple consequence of the concavity of $x^{\mathfrak{m}}_{i}(g)$, our next
lemma shows that the definition of the primal straight-line complexity
(Definition 1.3) can be restricted to breakpoints
$(g_{k},z_{k})=(g_{k},x^{\mathfrak{m}}_{i}(g_{k}))$. The analogous statement
holds for the dual straight-line complexity.

######  Lemma 7.8.

Let $0\leq\underline{g}<\overline{g}$. We have

$\operatorname{SLC}^{\mathrm{p}}_{\theta,i}(\underline{g},\overline{g})=\min\begin{multlined}\big{\\{}p\geq
1\colon\exists(g_{k})_{k\in[p+1]}\in\mathbb{R}\,,\enspace\overline{g}=g_{1}>g_{2}>\dots>g_{p+1}=\underline{g}\,,\\\
\forall
k\in[p]\,,\;\forall\lambda\in[0,1]\,,(1-\lambda)x^{\mathfrak{m}}_{i}(g_{k})+\lambda
x^{\mathfrak{m}}_{i}(g_{k+1})\\\
\geq(1-\theta)x^{\mathfrak{m}}_{i}((1-\lambda)g_{k}+\lambda
g_{k+1})\big{\\}}\end{multlined}\big{\\{}p\geq
1\colon\exists(g_{k})_{k\in[p+1]}\in\mathbb{R}\,,\enspace\overline{g}=g_{1}>g_{2}>\dots>g_{p+1}=\underline{g}\,,\\\
\forall
k\in[p]\,,\;\forall\lambda\in[0,1]\,,(1-\lambda)x^{\mathfrak{m}}_{i}(g_{k})+\lambda
x^{\mathfrak{m}}_{i}(g_{k+1})\\\
\geq(1-\theta)x^{\mathfrak{m}}_{i}((1-\lambda)g_{k}+\lambda g_{k+1})\big{\\}}$
(84)

###### Proof.

Let $\overline{g}=g_{1}>g_{2}>\dots>g_{p+1}=\underline{g}$. By the concavity
of $g\mapsto x^{\mathfrak{m}}_{i}(g)$, the condition
$(1-\lambda)x^{\mathfrak{m}}_{i}(g_{k})+\lambda
x^{\mathfrak{m}}_{i}(g_{k+1})\leq
x^{\mathfrak{m}}_{i}((1-\lambda)g_{k}+\lambda g_{k+1})$ is satisfied for every
$k\in[p]$ and $\lambda\in[0,1]$. We deduce that
$\operatorname{SLC}_{\theta,i}(\underline{g},\overline{g})$ is less than or
equal to the right-hand side of (84).

We now prove the converse inequality. Let
$(g_{1},z_{1}),\dots,(g_{p+1},z_{p+1})$ as in the right-hand side of (5). Up
to removing or shortening segments in the sequence
$\big{(}[(g_{k},z_{k}),(g_{k+1},z_{k+1})]\big{)}_{k\in[p]}$, we can assume
that $\overline{g}=g_{1}\geq g_{k}>g_{p+1}=\underline{g}$ for every $k\in[p]$.
As $z_{k}\leq x^{\mathfrak{m}}_{i}(g_{k})$ for all $k\in[p+1]$, we have
$(1-\lambda)x^{\mathfrak{m}}_{i}(g_{k})+\lambda
x^{\mathfrak{m}}_{i}(g_{k+1})\geq(1-\lambda)z_{k}+\lambda
z_{k+1}\geq(1-\theta)x^{\mathfrak{m}}_{i}((1-\lambda)g_{k}+\lambda g_{k+1})$
for all $k\in[p]$. It remains us to show that, up to removing some $g_{k}$, we
can ensure $g_{1}>g_{2}>\dots>g_{p+1}$. Suppose that there is $k\in[p]$ such
that $g_{1}>\dots>g_{k}$ and $g_{k+1}\geq g_{k}$. We introduce the smallest
integer $l\geq k$ such that $g_{l+1}<g_{k}$ ($l$ is well-defined as
$g_{p+1}=\underline{g}<g_{k}$). By concavity of $x^{\mathfrak{m}}_{i}$, we
have
$x^{\mathfrak{m}}_{i}(g_{k})\geq(1-\bar{\lambda})x^{\mathfrak{m}}_{i}(g_{l})+\bar{\lambda}x^{\mathfrak{m}}_{i}(g_{l+1})$
for $\bar{\lambda}=\frac{g_{k}-g_{l}}{g_{l+1}-g_{l}}\in[0,1]$. Then, for all
$\lambda\in[0,1]$,

$\displaystyle(1-\lambda)x^{\mathfrak{m}}_{i}(g_{k})+\lambda
x^{\mathfrak{m}}_{i}(g_{l+1})$
$\displaystyle\geq(1-\lambda^{\prime})x^{\mathfrak{m}}_{i}(g_{l})+\lambda^{\prime}x^{\mathfrak{m}}_{i}(g_{l+1})$
$\displaystyle\geq(1-\theta)x^{\mathfrak{m}}_{i}((1-\lambda^{\prime})g_{l}+\lambda^{\prime}g_{l+1})$
$\displaystyle=(1-\theta)x^{\mathfrak{m}}_{i}((1-\lambda)g_{k}+\lambda
g_{l+1})$

where $\lambda^{\prime}=\bar{\lambda}+\lambda(1-\bar{\lambda})\in[0,1]$. By
removing the $g_{k+1},\dots,g_{l}$ and recursively applying the same argument
$l+1$, we end up with a sequence
$\overline{g}=g_{1}>\dots>g_{q+1}=\underline{g}$ as in the right-hand side of
(84), with $q\leq p$. This shows that
$\operatorname{SLC}^{\mathrm{p}}_{\theta,i}(\underline{g},\overline{g})$ is
greater than or equal to the right-hand side of (84). ∎

###### Proof of Theorem 7.2.

We only prove the statement for the primal straight-line complexity bound; the
proof for the dual bound follows analogously.

Let $\underline{g}\coloneqq n\mu_{1}$ and $\overline{g}\coloneqq n\mu_{0}$
denote the gaps at $\mu_{1}$ and $\mu_{0}$. Let $i\in[n]$, and let
$g_{1}>\dots>g_{p+1}$ reaching the minimum in (84), where
$p=\operatorname{SLC}^{\mathrm{p}}_{\theta,i}(\underline{g},\overline{g})$. We
introduce the continuous piecewise linear curve
$\phi_{i}\colon[\underline{g},\overline{g}]\to\mathbb{R}$, defined by

$\phi_{i}(g)\coloneqq\max\left\\{\frac{g}{g_{k}}x^{\mathfrak{m}}_{i}(g_{k}),x^{\mathfrak{m}}_{i}(g_{k+1})\right\\}$

for all $g_{k+1}\leq g\leq g_{k}$ and $k\in[p]$. This function is well-defined
since $\frac{g_{k+1}}{g_{k}}x^{\mathfrak{m}}_{i}(g_{k})\leq
x^{\mathfrak{m}}_{i}(g_{k+1})$ and
$\frac{g_{k+1}}{g_{k+1}}x^{\mathfrak{m}}_{i}(g_{k+1})\geq
x^{\mathfrak{m}}_{i}(g_{k+2})$. So the values on the intervals
$[g_{k+2},g_{k+1}]$ and $[g_{k+1},g_{k}]$ that define $\phi_{i}(g_{k+1})$ do
agree and we have $\phi_{i}(g_{k+1})=g_{k+1}$. We claim that, for all
$\underline{g}\leq g\leq\overline{g}$,

$\frac{1-\theta}{4}x^{\mathfrak{m}}_{i}(g)\leq\phi_{i}(g)\leq
4x^{\mathfrak{m}}_{i}(g)\,.$ (85)

Indeed, let $k\in[p]$ and $g_{k+1}\leq g\leq g_{k}$. We set
$\lambda\coloneqq\frac{g}{g_{k}}$. We observe that
$g^{\prime}\coloneqq\frac{\lambda}{1+\lambda}g_{k}+\frac{1}{1+\lambda}g_{k+1}$
satisfies $\frac{1}{2}g^{\prime}\leq g\leq 2g^{\prime}$. Then,

$\displaystyle\phi_{i}(g)$ $\displaystyle\leq
2\Big{(}\frac{\lambda}{1+\lambda}x^{\mathfrak{m}}_{i}(g_{k})+\frac{1}{1+\lambda}x^{\mathfrak{m}}_{i}(g_{k+1})\Big{)}$
as $\lambda\leq 1$ $\displaystyle\leq 2x^{\mathfrak{m}}_{i}(g^{\prime})$ by
concavity $\displaystyle\leq 4x^{\mathfrak{m}}_{i}(g)$ by monotonicity and
Lemma 7.7.

Similarly, we have

$\displaystyle\phi_{i}(g)$
$\displaystyle\geq\frac{1}{2}\Big{(}\frac{\lambda}{1+\lambda}x^{\mathfrak{m}}_{i}(g_{k})+\frac{1}{1+\lambda}x^{\mathfrak{m}}_{i}(g_{k+1})\Big{)}$
$\displaystyle\geq\frac{1-\theta}{2}x^{\mathfrak{m}}_{i}(g^{\prime})$ by (84)
$\displaystyle\geq\frac{1-\theta}{4}x^{\mathfrak{m}}_{i}(g)$ by monotonicity
and Lemma 7.7.

We denote by $G_{i}$ the set of nondifferentiable points of the function
$\phi_{i}$ in $(\underline{g},\overline{g})$. We remark that $|G_{i}|\leq
2\operatorname{SLC}^{\mathrm{p}}_{\theta,i}(\underline{g},\overline{g})-1$.

We now introduce the piecewise linear curve
$\phi\colon[\underline{g},\overline{g}]\to\mathbb{R}^{n}$ defined by
$\phi(g)=(\phi_{i}(g))_{i\in[n]}$. The set of nondifferentiable points of
$\phi$ in $(\underline{g},\overline{g})$ is $\bigcup_{i\in[n]}G_{i}$. We
denote them by $h_{2}>\dots>h_{T}$, and we set $h_{1}\coloneqq\overline{g}$
and $h_{T+1}\coloneqq\underline{g}$. For all $k\in[T]$, there exists a
partition $(B^{(k)},N^{(k)})$ of $[n]$ such that for all $h_{k+1}\leq g\leq
h_{k}$,

$\displaystyle\phi_{B^{(k)}}(g)$ $\displaystyle=\phi_{B^{(k)}}(h_{k})\,,$
$\displaystyle\phi_{N^{(k)}}(g)$
$\displaystyle=\frac{g}{h_{k}}\phi_{N^{(k)}}(h_{k})\,.$

Using (85), we deduce that for all $h_{k+1}\leq g\leq h_{k}$,

$\displaystyle\frac{1-\theta}{16}x^{\mathfrak{m}}_{B^{(k)}}(h_{k})$
$\displaystyle\leq x^{\mathfrak{m}}_{B^{(k)}}(g)\,,$ (86) $\displaystyle
x^{\mathfrak{m}}_{N^{(k)}}(g)$
$\displaystyle\leq\frac{16}{1-\theta}\frac{g}{h_{k}}x^{\mathfrak{m}}_{N^{(k)}}(h_{k})\,.$

We set $\mu_{k}\coloneqq\frac{h_{k}}{n}$. Combining (86) with Lemma 1.2 then
shows that for all $\mu_{k+1}\leq\mu\leq\mu_{k}$,

$\displaystyle\gamma x^{\mathrm{cp}}_{B^{(k)}}(\mu_{k})$ $\displaystyle\leq
x^{\mathrm{cp}}_{B^{(k)}}(\mu)\,,$ $\displaystyle
x^{\mathrm{cp}}_{N^{(k)}}(\mu)$
$\displaystyle\leq\frac{1}{\gamma}\frac{\mu}{\mu_{k+1}}x^{\mathrm{cp}}_{N^{(k)}}(\mu_{k})\,,$

where $\gamma=\frac{1-\theta}{32n}$. Moreover, we have

$N^{(k)}\Delta N^{(k+1)}=\\{i\in[n]\colon h_{k+1}\in G_{i}\\}\,.$

We deduce that

$\sum_{k=1}^{T}|N^{(k-1)}\Delta N^{(k)}|=\sum_{i=1}^{n}|G_{i}|\leq
2\sum_{i=1}^{n}\operatorname{SLC}^{\mathrm{p}}_{\theta,i}(\underline{g},\overline{g})\,.$

∎

##  8 Polynomial approximation of singular values

To compute the subspace LLS direction, we need to identify the linear spaces
$U$ and $V$ that are obtained from an exact SVD decomposition of the matrix
$M$ representing the lifting map $\widetilde{\ell}_{z}$. It is important to
note that our arithmetic model does not allow for computing an exact
decomposition. As the analysis of the main algorithm (Algorithm 1) is robust,
it suffices to identify a subspace $V\subseteq\pi_{\tilde{N}}(\hat{x}^{-1}W)$
such that the lifting map from $V$ has singular values at most $\tau$ and
$\dim(V)\geq\dim(V^{*}_{z,N}(\tau/n^{c}))$ for some constant $c>0$;
analogously for $U$. In Section 8.1, we provide a simple deterministic
approximation for $c=1.5$. In Section 8.2, we show that these guarantees
follow from the strongly polynomial approximate SVD decomposition result in
[13]. This algorithm provides much stronger guarantees, but is randomized.
Moreover, in Section 8.1 we only show a strongly polynomial bound on the
number of arithmetic operations, but do not give bounds on the bit-complexity
of the numbers throughout the algorithm. It would require a nontrivial
modification to get such a guarantee, as the naïve implementation could lead
to doubling the bit-complexity in each iteration. The algorithm of [13] also
provides bit-complexity guarantees. We leave it as an interesting open problem
to design a deterministic strongly polynomial approximate SVD.

###  8.1 A deterministic approximate SVD algorithm

The algorithm Approx-SVD is presented in Algorithm 2. For the proof of Lemma
5.4, recall the min-max principle of singular values stated as (32).

1

Input : A matrix $\mathbf{M}\in\mathbb{R}^{m\times n}$.

Output : A matrix $\mathbf{V}\in\mathbb{R}^{n\times n}$ satisfying the
conditions of Lemma 5.4.

2

3$\mathbf{V}\leftarrow\mathbf{I}_{n}$;

4 for  _$i=1,\ldots,n$_ do

5
$\mathbf{V}\leftarrow\hyperref@@ii[proc:orthogonalize]{\textsc{orthogonalize}}(\mathbf{I}_{n},\mathbf{V})$;

6 $\mathbf{V}_{\geq
i}\leftarrow\hyperref@@ii[proc:orthogonalize]{\textsc{orthogonalize}}(\mathbf{M},\mathbf{V}_{\geq
i})$;

7 $c\leftarrow\operatorname*{arg\,min}_{i\leq j\leq
n}\frac{\|\mathbf{M}\mathbf{V}_{j}\|}{\|\mathbf{V}_{j}\|}$ ;

8 $\mathbf{V}\leftarrow\mathbf{V}\text{ with column $i$ swapped with column
$c$}$;

9 $\mathbf{V}^{(i)}\leftarrow\mathbf{V}$ ;

10 // Only needed for the analysis

11

12return _$\mathbf{V}$_ ;

13 procedure  _Orthogonalize( $\mathbf{N},\mathbf{V}$)_:

Input : Matrices $\mathbf{N}\in\mathbb{R}^{m\times n}$ and
$\mathbf{V}\in\mathbb{R}^{n\times k}$

Output : A matrix $\widehat{\mathbf{V}}\in\mathbb{R}^{n\times k}$ with
$\operatorname{im}(\mathbf{V}_{\leq
i})=\operatorname{im}(\widehat{\mathbf{V}}_{\leq i})$ for all $i\in[k]$ and
$\mathbf{N}$-orthogonal columns, i.e.,
$\widehat{\mathbf{V}}^{\top}\mathbf{N}^{\top}\mathbf{N}\widehat{\mathbf{V}}$
is diagonal.

// If $m=0$ return $\mathbf{V}$.

14

15

16

Algorithm 2 Approx-SVD

###### Proof of Lemma 5.4.

To bound the number of arithmetic operations, we first note that the each call
to Orthogonalize can be executed via the standard Gram-Schmidt
orthogonalization (GSO) process using either the inner product induced by
$\mathbf{M}^{\top}\mathbf{M}$ or $\mathbf{I}_{n}$. Applying the GSO on $n$
vectors in $\mathbb{R}^{n}$ requires $O(n^{2})$ inner product computations as
well as elementary vector operations, each of which require at most $O(n^{2})$
arithmetic operations. In particular, computing inner products with respect to
$\mathbf{M}^{\top}\mathbf{M}$ requires $O(n^{2})$ arithmetic operations. Since
the algorithm executes $2n$ GSO’s on at most $n$ vectors in $\mathbb{R}^{n}$,
the total number of arithmetic operations is $O(n(n^{2})n^{2})=O(n^{5})$.

We now show that the output of the algorithm satisfies the conditions of Lemma
5.4. Note that the first and last inequality follow from (32). We prove the
second and the third inequality. Note that by choice of $j$ in line 2 we have
for all $j$ with $i\leq j\leq n$ that

$\frac{\|\mathbf{M}\mathbf{V}_{i}^{(i)}\|}{\|\mathbf{V}_{i}^{(i)}\|}\leq\frac{\|\mathbf{M}\mathbf{V}_{j}^{(i)}\|}{\|\mathbf{V}_{j}^{(i)}\|}\,.$
(87)

Therefore, by $\mathbf{M}$-orthogonality of $\mathbf{V}_{\geq i}^{(i)}$ we
have for an arbitrary $u\in\mathbb{R}^{n-i+1}\setminus\\{\mathbf{0}\\}$

$\displaystyle\frac{\|\mathbf{M}\mathbf{V}_{\geq
i}^{(i)}u\|}{\|\mathbf{V}_{\geq i}^{(i)}u\|}$
$\displaystyle=\frac{\sqrt{\sum_{j\geq
i}u_{j}^{2}\|\mathbf{M}\mathbf{V}^{(i)}_{j}\|^{2}}}{\|\mathbf{V}_{\geq
i}^{(i)}u\|}\stackrel{{\scriptstyle\eqref{eq:ell_i_bound}}}{{\geq}}\frac{\|\mathbf{M}\mathbf{V}_{i}^{(i)}\|}{\|\mathbf{V}_{i}^{(i)}\|}\frac{\sqrt{\sum_{j\geq
i}u_{j}^{2}\|\mathbf{V}_{j}^{(i)}\|^{2}}}{\|\mathbf{V}_{\geq i}^{(i)}u\|}$
(88)
$\displaystyle\stackrel{{\scriptstyle\mathmakebox[width("=")]{\triangle\text{-ineq.}}}}{{\geq}}\quad\frac{\|\mathbf{M}\mathbf{V}_{i}^{(i)}\|}{\|\mathbf{V}_{i}^{(i)}\|}\frac{\sqrt{\sum_{j\geq
i}u_{j}^{2}\|\mathbf{V}_{j}^{(i)}\|^{2}}}{\left(\sum_{j\geq
i}|u_{j}|\|\mathbf{V}^{(i)}_{j}\|\right)}$
$\displaystyle\stackrel{{\scriptstyle\mathmakebox[width("=")]{\text{AM-
QM}}}}{{\geq}}\quad\frac{1}{\sqrt{n}}\frac{\|\mathbf{M}\mathbf{V}_{i}^{(i)}\|}{\|\mathbf{V}_{i}^{(i)}\|}\,.$

Note that $\operatorname{im}(\mathbf{V}_{\geq
i}^{(i)})=\operatorname{im}(\mathbf{V}_{\geq i})$ and
$\mathbf{V}_{i}^{(i)}=\mathbf{V}_{i}$ for all $i\in[n]$.

Therefore,

$\min_{v\in\operatorname{im}(\mathbf{V}_{\geq
i})\setminus\\{\mathbf{0}\\}}\frac{\|\mathbf{M}v\|}{\|v\|}=\min_{v\in\operatorname{im}(\mathbf{V}_{\geq
i}^{(i)})}\frac{\|\mathbf{M}v\|}{\|v\|}\stackrel{{\scriptstyle\eqref{eq:sing_val_approx_bound}}}{{\geq}}\frac{1}{\sqrt{n}}\frac{\|\mathbf{M}\mathbf{V}_{i}^{(i)}\|}{\|\mathbf{V}_{i}^{(i)}\|}=\frac{1}{\sqrt{n}}\frac{\|\mathbf{M}\mathbf{V}_{i}\|}{\|\mathbf{V}_{i}\|}\,,$
(89)

which proves the third inequality of the lemma.

It remains to prove the second inequality of the lemma. Note that by the
$\mathbf{I}_{n}$-orthogonality of the columns of $\mathbf{V}$ we have for all
$i\in[n]$ that

$\displaystyle\max_{v\in\operatorname{im}(\mathbf{V}_{\leq
i})\setminus\\{\mathbf{0}\\}}\frac{\|\mathbf{M}v\|}{\|v\|}$
$\displaystyle=\max_{u\in\mathbb{R}^{i}\setminus\\{\mathbf{0}\\}}\frac{\|\mathbf{M}\mathbf{V}_{\leq
i}u\|}{\|\mathbf{V}_{\leq
i}u\|}\stackrel{{\scriptstyle\text{orthogonality}}}{{=}}\max_{u\in\mathbb{R}^{i}\setminus\\{\mathbf{0}\\}}\frac{\|\mathbf{M}\mathbf{V}_{\leq
i}u\|}{\sqrt{\sum_{j\leq i}\|\mathbf{V}_{j}\|^{2}u_{j}^{2}}}$ (90)
$\displaystyle\stackrel{{\scriptstyle\mathmakebox[width("=")]{\triangle\text{-ineq.}}}}{{\leq}}\max_{u\in\mathbb{R}^{i}\setminus\\{\mathbf{0}\\}}\frac{\sum_{j\leq
i}\|\mathbf{M}\mathbf{V}_{j}\||u_{j}|}{\sqrt{\sum_{j\leq
i}\|\mathbf{V}_{j}\|^{2}u_{j}^{2}}}$
$\displaystyle\stackrel{{\scriptstyle\mathmakebox[width("=")]{\text{AM-
QM}}}}{{\leq}}\max_{u\in\mathbb{R}^{i}\setminus\\{\mathbf{0}\\}}\sqrt{n}\frac{\sum_{j\leq
i}\|\mathbf{M}\mathbf{V}_{j}\||u_{j}|}{\sum_{j\leq
i}\|\mathbf{V}_{j}\||u_{j}|}$
$\displaystyle\stackrel{{\scriptstyle\mathmakebox[width("=")]{\text{mediant}}}}{{\leq}}\sqrt{n}\max_{j\leq
i}\frac{\|\mathbf{M}\mathbf{V}_{j}\|}{\|\mathbf{V}_{j}\|}\,.$

Furthermore, the specification of Orthogonalize implies that, for all $j\leq
i$, we have $\mathbf{V}_{i}\in\operatorname{im}(\mathbf{V}_{\geq
j}^{(j)})=\operatorname{im}(\mathbf{V}_{\geq j})$. Hence, for all $j\leq i$,
we get

$\frac{\|\mathbf{M}\mathbf{V}_{i}\|}{\|\mathbf{V}_{i}\|}\geq\min_{v\in\operatorname{im}(\mathbf{V}_{\geq
j})}\frac{\|\mathbf{M}v\|}{\|v\|}\stackrel{{\scriptstyle\eqref{eq:sing-val-
approx-bound-
upper}}}{{\geq}}\frac{1}{\sqrt{n}}\frac{\|\mathbf{M}\mathbf{V}_{j}\|}{\|\mathbf{V}_{j}\|}\,.$
(91)

In particular, (91) holds for $\max_{j\leq
i}\frac{\|\mathbf{M}\mathbf{V}_{j}\|}{\|\mathbf{V}_{j}\|}$. Combining this
with (90) yields the second inequality of the lemma. ∎

###  8.2 Implementation using a Randomized SVD

We now provide the statement of the approximate SVD algorithm of Diakonikolas,
Kane and Tzamos [13, Proposition 4.1]. We further explain how to apply it to
derive stronger guarantees than provided by Algorithm 2 at the expense of
randomization.

######  Lemma 8.1 ([13, Proposition 4.1]).

Given a $n\times n$ positive semidefinite matrix
$\mathbf{G}\in\mathbb{Q}^{n\times n}$, a tolerance $\varepsilon\in(0,1/2)$ and
an error probability $\delta\in(0,1/2)$, there is a randomized algorithm which
with probability at least $1-\delta$ outputs orthogonal vectors
$v_{1},\dots,v_{n}\in\mathbb{Q}^{n}\setminus\\{0\\}$ and non-negative scalars
$s_{1},\dots,s_{n}\in\mathbb{Q}$ satisfying

$(1-\varepsilon)\mathbf{G}\preceq\tilde{\mathbf{G}}\preceq(1+\varepsilon)\mathbf{G},\quad\text{
where }\tilde{\mathbf{G}}\coloneqq\sum_{i=1}^{n}s_{i}v_{i}v_{i}^{\top}.$

Furthermore, the algorithm performs
$\operatorname{poly}(n/\varepsilon,\log(1/\delta))$ arithmetic operations on
$\operatorname{poly}(n/\varepsilon,\log(1/\delta),\langle\mathbf{G}\rangle)$
bit numbers, where $\langle\mathbf{G}\rangle$ is the bit complexity of
$\mathbf{G}$.

Since the condition
$(1-\varepsilon)\mathbf{G}\preceq\tilde{\mathbf{G}}\preceq(1+\varepsilon)\mathbf{G}$
can be verified in strongly polynomial time (checking whether a matrix is
positive semidefinite can achieved via symmetric Gaussian elimination), one
can in fact remove the probability of error above at the expense of an
expected running time. Namely, one can simply repeat the algorithm using
$\delta=1/2$ until it succeeds.

Using the above lemma, one can obtain a stronger version of the guarantees in
Lemma 5.4 as follows. We apply Lemma 8.1 on the matrix
$\mathbf{G}=\mathbf{M}^{\top}\mathbf{M}$ with $\varepsilon=1/3$ and desired
error probability $\delta>0$. We then return $\mathbf{V}=(v_{1},\dots,v_{n})$,
where we order the vectors in non-decreasing order of $\lambda_{i}\coloneqq
s_{i}\|v_{i}\|^{2}$, $i\in[n]$.

We now verify the desired guarantees under the assumption that the randomized
SVD returns correctly. Firstly, by our choice of $\varepsilon=1/3$, for all
$z\in\mathbb{R}^{n}$,

$\frac{2}{3}\|\mathbf{M}z\|^{2}=\frac{2}{3}z^{\top}\mathbf{G}z\leq
z^{\top}\tilde{\mathbf{G}}z\leq\frac{4}{3}z^{\top}\mathbf{G}z=\frac{4}{3}\|\mathbf{M}z\|^{2}.$
(92)

By orthogonality of $v_{1},\dots,v_{n}$, the eigenvalues of
$\tilde{\mathbf{G}}=\sum_{i=1}^{n}s_{i}v_{i}v_{i}^{\top}$ are
$\lambda_{1}\leq\cdots\leq\lambda_{n}$ as defined above. Furthermore, applying
(92) to $v_{i}$, $i\in[n]$, we see that

$\frac{2}{3}\frac{\|\mathbf{M}v_{i}\|^{2}}{\|v_{i}\|^{2}}\leq\frac{v_{i}^{\top}\tilde{\mathbf{G}}v_{i}}{\|v_{i}\|^{2}}=s_{i}\|v_{i}\|^{2}=\lambda_{i}\leq\frac{4}{3}\frac{\|\mathbf{M}v_{i}\|^{2}}{\|v_{i}\|^{2}}.$
(93)

We now verify the second inequality in Lemma 5.4:

$\max_{\begin{subarray}{c}z\in\operatorname{im}(\mathbf{V}_{\leq i})\\\
z\neq\mathbf{0}\end{subarray}}\frac{\|\mathbf{M}z\|^{2}}{\|z\|^{2}}\leq\frac{3}{2}\max_{\begin{subarray}{c}z\in\operatorname{im}(\mathbf{V}_{\leq
i})\\\
z\neq\mathbf{0}\end{subarray}}\frac{z^{\top}\tilde{\mathbf{G}}z}{\|z\|^{2}}=\frac{3}{2}\lambda_{i}\leq
2\frac{\|\mathbf{M}v_{i}\|^{2}}{\|v_{i}\|^{2}}.$

Lastly, we verify the third inequality:

$\min_{\begin{subarray}{c}z\in\operatorname{im}(\mathbf{V}_{\geq i})\\\
z\neq\mathbf{0}\end{subarray}}\frac{\|\mathbf{M}z\|^{2}}{\|z\|^{2}}\geq\frac{3}{4}\min_{\begin{subarray}{c}z\in\operatorname{im}(\mathbf{V}_{\geq
i})\\\
z\neq\mathbf{0}\end{subarray}}\frac{z^{\top}\tilde{\mathbf{G}}z}{\|z\|^{2}}=\frac{3}{4}\lambda_{i}\geq\frac{1}{2}\frac{\|\mathbf{M}v_{i}\|^{2}}{\|v_{i}\|^{2}}.$

With the randomized SVD, we note that the desired inequalities now hold up to
a constant factor instead of a factor depending on $n$.

##  9 Self-concordant barrier central paths

The theory of self-concordant barriers, introduced by Nesterov and Nemirovski
[35], is used to describe interior point methods in a general setting. In this
section, we show that the central paths obtained from self-concordant barriers
relate to the max-central path, as in the case of the log-barrier. From this,
we deduce a proof of Theorem 1.7.

We follow the presentation of self-concordant barriers made by Renegar [37].
We consider a $\mathcal{C}^{2}$ function $f\colon D\to\mathbb{R}$ with open
convex domain $D\subset E$ where $E=x^{0}+L$ is an affine subspace of
$\mathbb{R}^{n}$, and such that the Hessian $\nabla^{2}f(x)$ of $f$ at $x$ is
positive definite for all $x\in D$. In particular, $f$ is a strictly convex
function. Given $x\in D$, we introduce $\|\cdot\|_{x}$, the norm over $L$
associated with the Hessian $\nabla^{2}f(x)$, i.e.,
$\|z\|_{x}\coloneqq\big{(}\left\langle
z,\nabla^{2}f(x)z\right\rangle\big{)}^{1/2}$ for all $z\in L$. We define
$\mathcal{B}_{x}(y;r)\coloneqq\\{z\in D:\|y-z\|_{x}<r\\}$, the open ball with
center $y\in D$ and radius $r\geq 0$ with respect to the norm $\|\cdot\|_{x}$.

The function $f$ is _(strongly nondegenerate) self-concordant_ if, for all
$x\in D$, we have $\mathcal{B}_{x}(x;1)\subset D$, and for all
$y\in\mathcal{B}_{x}(x;1)$ and nonzero vector $v\in L$,

$1-\|y-x\|_{x}\leq\frac{\|v\|_{x}}{\|v\|_{y}}\leq\frac{1}{1-\|y-x\|_{x}}\,.$

We denote by $\nabla f(x)\in L$ the gradient of $f$ at $x$. We define the
_complexity value_ as

$\vartheta_{f}\coloneqq\sup_{x\in D}\left\langle\nabla
f(x),(\nabla^{2}f(x))^{-1}\nabla f(x)\right\rangle\,.$

If $\vartheta_{f}<\infty$, then $f$ is called a _self-concordant barrier_.

Let $f$ be self-concordant barrier over the (relative) interior of the
polyhedron $\mathcal{P}$. The _central path_ associated with $f$ is the
function that maps $\mu>0$ to the unique minimizer of the function
$x\mapsto\left\langle c,x\right\rangle+\mu f(x)$. When $f$ is (the restriction
to $E$ of) the log-barrier $x\mapsto-\sum_{i=1}^{n}\log(x_{i})$, the scalar
$\mu$ is used as the parameter of the central path. In the case of general
barriers, it is more convenient to parametrize the central path by the
optimality gap $g$. This is made possible by the fact that, if any two points
of the central path have the same optimality gap $g$, they both minimize the
(strictly convex) function $f$ over $\\{x\in\mathcal{P}\colon\left\langle
c,x\right\rangle=g\\}$, thus they are equal. Following this, we denote by
$x^{\mathrm{cp}(f)}(g)$ the unique point of the central path induced by the
barrier $f$ with optimality gap $g>0$.

In the next statement, we generalize Lemma 1.2 to the case of the central path
associated with the self-concordant barrier $f$.

######  Proposition 9.1.

For all $g>0$, we have
$\frac{1}{2(2\vartheta_{f}+1)}x^{\mathfrak{m}}(g)<x^{\mathrm{cp}(f)}(g)\leq
x^{\mathfrak{m}}(g)$.

###### Proof.

The right hand side inequality follows from
$x^{\mathrm{cp}(f)}(g)\in\mathcal{P}_{g}$. Using [37, Theorem 2.3.4] and the
fact that $\mu\nabla f(x^{\mathrm{cp}(f)}(g))+c\in L^{\perp}$ for some
$\mu>0$, we know that
$\mathcal{P}_{g}\subset\mathcal{B}_{x^{\mathrm{cp}(f)}(g)}(x^{\mathrm{cp}(f)}(g);4\vartheta_{f}+1)$.
Since $\mathcal{P}_{g}\subset\mathbb{R}^{n}_{\geq 0}$, [3, Lemma 4] shows that
$y<2(2\vartheta_{f}+1)$ for all
$y\in\mathcal{B}_{x^{\mathrm{cp}(f)}(g)}(x^{\mathrm{cp}(f)}(g);4\vartheta_{f}+1)$.
We deduce that $x^{\mathfrak{m}}(g)<2(2\vartheta_{f}+1)x^{\mathrm{cp}(f)}(g)$.
∎

As in the case of the log-barrier, interior point methods based on general
self-concordant barriers draw a piecewise linear trajectory in the
neighborhood of the central path. In [3, Section 4.1], it has been shown that
the neighborhoods of the self-concordant central path used in the literature
(including that of the log-barrier central path like the projections of
$\mathcal{N}^{2}(\theta)$ and $\mathcal{N}^{-\infty}(\theta)$ to primal
variables) are actually contained in _multiplicative neighborhoods_ , i.e.,
sets of form

$\mathcal{M}^{\mathrm{cp}(f)}(\underline{m},\overline{m})=\big{\\{}x\in\mathcal{P}:\exists
g\,\enspace\underline{m}x^{\mathrm{cp}(f)}(g)\leq
x\leq\overline{m}x^{\mathrm{cp}(f)}(g)\big{\\}}\qquad(0<\underline{m}\leq
1\leq\overline{m})\,.$

The latter turn out to be equivalent to the neighborhoods
$\mathcal{N}^{\mathrm{cp}(f)}(\theta)$ for $\theta\in(0,1)$ introduced in (6),
as shown by the following lemma:

######  Lemma 9.2.

We have
$\mathcal{N}^{\mathrm{cp}(f)}(\theta)\subset\mathcal{M}^{\mathrm{cp}(f)}\big{(}1-\theta,2(2\vartheta_{f}+1)\big{)}$
for all $\theta\in(0,1)$, and
$\mathcal{M}^{\mathrm{cp}(f)}(\underline{m},\overline{m})\subset\mathcal{N}^{\mathrm{cp}(f)}\big{(}\frac{\underline{m}}{2(2\vartheta_{f}+1)\overline{m}}\big{)}$
for all $0<\underline{m}\leq 1\leq\overline{m}$.

###### Proof.

For the first statement, let $\theta\in(0,1)$, and
$x\in\mathcal{N}^{\mathrm{cp}(f)}(\theta)$, and let $g=\left\langle
c,x\right\rangle-v^{*}$ denote the optimality gap of $x$. The inequality
$x\geq(1-\theta)x^{\mathrm{cp}(f)}(g)$ follows by the definition of
$\mathcal{N}^{\mathrm{cp}(f)}(\theta)$. We have $x\leq x^{\mathfrak{m}}(g)$
since $x\in\mathcal{P}$, and so $x\leq
2(2\vartheta_{f}+1)x^{\mathrm{cp}(f)}(g)$ by Proposition 9.1.

For the second statement, let $0<\underline{m}\leq 1\leq\overline{m}$, and let
$(\tilde{g},x)$ such that $\underline{m}x^{\mathrm{cp}(f)}(\tilde{g})\leq
x\leq\overline{m}x^{\mathrm{cp}(f)}(\tilde{g})$. Let $s^{\star}\geq 0$ denote
a dual optimal solution to (LP). The optimality gap $g=\left\langle
c,x\right\rangle-v^{*}=\left\langle s^{\star},x\right\rangle$ of $x$ satisfies
$g\leq\overline{m}\left\langle
s^{\star},x^{\mathrm{cp}(f)}(\tilde{g})\right\rangle=\overline{m}\tilde{g}$
(since $s^{\star}\geq 0$). Then, we have

$\displaystyle x$
$\displaystyle\geq\frac{\underline{m}}{2(2\vartheta_{f}+1)}x^{\mathfrak{m}}(\tilde{g})$
by Proposition 9.1
$\displaystyle\geq\frac{\underline{m}}{2(2\vartheta_{f}+1)\overline{m}}x^{\mathfrak{m}}(\overline{m}\tilde{g})$
by Lemma 7.7
$\displaystyle\geq\frac{\underline{m}}{2(2\vartheta_{f}+1)\overline{m}}x^{\mathfrak{m}}(g)$
as $g\leq\overline{m}\tilde{g}$
$\displaystyle\geq\frac{\underline{m}}{2(2\vartheta_{f}+1)\overline{m}}x^{\mathrm{cp}(f)}(g)$
by Proposition 9.1.

∎

As a consequence, the neighborhoods $\mathcal{N}^{\mathrm{cp}(f)}(\theta)$ are
flexible enough to capture the known neighborhoods of central paths. We are
now ready to prove Theorem 1.7.

###### Proof (Theorem 1.7).

Let $x^{(0)},\dots,x^{(T)}$ be the successive iterates of the IPM. We denote
by $g^{(0)},\dots,g^{(T)}$ their respective optimality gap, where $g^{(0)}\geq
g_{0}$ and $g^{(T)}\leq g_{1}$.

Let $i\in[n]$. We claim that, for all $k\in[T]$, the segment
$[(g^{(k-1)},x^{(k-1)}_{i}),(g^{(k)},x^{(k)}_{i})]$ is included in the
neighborhood ${\mathcal{N}}^{\mathfrak{mp}}_{i}(\theta^{\prime})$ for
$\theta^{\prime}=1-\frac{1-\theta}{2(2\vartheta_{f}+1)}$. Indeed, for all
$\lambda\in[0,1]$, the point $x=(1-\lambda)x^{(k-1)}+\lambda x^{(k)}$ has
optimality gap $g=(1-\lambda)g^{(k-1)}+\lambda g^{(k)}$. As $x\in\mathcal{P}$,
we have $x_{i}\leq x^{\mathfrak{m}}_{i}(g)$. Moreover, since
$x\geq(1-\theta)x^{\mathrm{cp}(f)}(g)$, Proposition 9.1 ensures that
$x_{i}>\frac{1-\theta}{2(2\vartheta_{f}+1)}x^{\mathfrak{m}}_{i}(g)$. Hence,
$(g,x)\in{\mathcal{N}}^{\mathfrak{mp}}_{i}(\theta^{\prime})$. We deduce by
Lemma 7.8 that
$T\geq\operatorname{SLC}^{\mathrm{p}}_{\theta^{\prime},i}(g_{1},g_{0})$.

Consequently, we have
$\sum_{i=1}^{n}\operatorname{SLC}^{\mathrm{p}}_{\theta^{\prime},i}(g_{1},g_{0})\leq
nT$. By Theorem 1.4, the number $T^{\prime}$ of iterations performed by the
algorithm IPM with subspace LLS is in

$O\left(\sqrt{n}\log\left(\frac{n}{1-\theta}\right)\min\left\\{\sum_{i=1}^{n}\operatorname{SLC}^{\mathrm{p}}_{\theta,i}(g_{1},g_{0}),\sum_{i=1}^{n}\operatorname{SLC}^{\mathrm{d}}_{\theta,i}(g_{1},g_{0})\right\\}\right)\,.$
(94)

This implies that

$T^{\prime}=O\left(n^{1.5}\log\left(\frac{n\vartheta_{f}}{1-\theta}\right)T\right)\,.$

∎

## References

  * [1] X. Allamigeon, P. Benchimol, S. Gaubert, and M. Joswig.  Log-barrier interior point methods are not strongly polynomial.  SIAM Journal on Applied Algebra and Geometry, 2(1):140–178, 2018\.
  * [2] X. Allamigeon, P. Benchimol, S. Gaubert, and M. Joswig.  What tropical geometry tells us about the complexity of linear programming.  SIAM Review, 63(1):123–164, Jan. 2021.
  * [3] X. Allamigeon, S. Gaubert, and N. Vandame.  No self-concordant barrier interior point method is strongly polynomial.  In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC), pages 515–528, 2022.
  * [4] K. Axiotis, A. Madry, and A. Vladu.  Faster sparse minimum cost flow by electrical flow localization.  In Proceedings of the 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 528–539, 2022.
  * [5] K. H. Borgwardt.  The Simplex Method: a probabilistic analysis, volume 1.  Springer Science & Business Media, 2012.
  * [6] S. Bubeck and R. Eldan.  The entropic barrier: a simple and optimal universal self-concordant barrier.  arXiv preprint arXiv:1412.1587, 2014.
  * [7] L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. P. Gutenberg, and S. Sachdeva.  Maximum flow and minimum-cost flow in almost-linear time.  In Proceedings of the 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612–623. IEEE, 2022.
  * [8] M. B. Cohen, Y. T. Lee, and Z. Song.  Solving linear programs in the current matrix multiplication time.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 938–942, 2019.
  * [9] D. Dadush and S. Huiberts.  Smoothed analysis of the simplex method.  In T. Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, Cambridge, 2020.
  * [10] D. Dadush, S. Huiberts, B. Natura, and L. A. Végh.  A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix.  In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC), pages 761–774, 2020.
  * [11] S. I. Daitch and D. A. Spielman.  Faster approximate lossy generalized flow via interior point algorithms.  In Proceedings of the 40th annual ACM symposium on Theory of Computing (STOC), pages 451–460, 2008.
  * [12] A. Deza, E. Nematollahi, and T. Terlaky.  How good are interior point methods? Klee–Minty cubes tighten iteration-complexity bounds.  Math. Program., 113(1):1–14, Oct. 2008.
  * [13] I. Diakonikolas, C. Tzamos, and D. M. Kane.  A strongly polynomial algorithm for approximate forster transforms and its application to halfspace learning.  arXiv preprint arXiv:2212.03008, 2022.
  * [14] Y. Gao, Y. P. Liu, and R. Peng.  Fully dynamic electrical flows: Sparse maxflow faster than Goldberg–Rao.  In Proceedings of the 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 516–527. IEEE, 2022.
  * [15] S. Gass and T. Saaty.  The computational algorithm for the parametric objective function.  Naval Res. Logist. Quart., 2:39–45, 1955.
  * [16] C. C. Gonzaga.  Path-following methods for linear programming.  SIAM review, 34(2):167–224, 1992.
  * [17] R. C. Grinold.  The payment scheduling problem.  Naval Research Logistics Quarterly, 19:123–136, 1972.
  * [18] S. Kakihara, A. O. Ohara, and T. Tsuchiya.  Information geometry and interior-point algorithms in semidefinite programs and symmetric cone programs.  Journal of Optimization Theory and Applications, 157:749–780, 2013\.
  * [19] S. Kakihara, A. O. Ohara, and T. Tsuchiya.  Curvature integrals and iteration complexities in SDP and symmetric cone programs.  Computational Optimization and Applications, 57:623–665, 2014.
  * [20] N. Karmarkar.  A new polynomial-time algorithm for linear programming.  In Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC), pages 302–311, 1984.
  * [21] J. A. Kelner and D. A. Spielman.  A randomized polynomial-time simplex algorithm for linear programming.  In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 51–60, 2006.
  * [22] L. G. Khachiyan.  A polynomial algorithm in linear programming.  In Doklady Academii Nauk SSSR, volume 244, pages 1093–1096, 1979\.
  * [23] V. Klee and G. J. Minty.  How good is the simplex algorithm?  In Inequalities, III (Proc. Third Sympos., Univ. California, Los Angeles, Calif., 1969; dedicated to the memory of Theodore S. Motzkin), pages 159–175. Academic Press, New York, 1972.
  * [24] G. Lan, R. D. Monteiro, and T. Tsuchiya.  A polynomial predictor-corrector trust-region algorithm for linear programming.  SIAM Journal on Optimization, 19(4):1918–1946, 2009.
  * [25] Y. T. Lee and A. Sidford.  Path finding methods for linear programming: Solving linear programs in $\tilde{O}(\sqrt{\mbox{rank}})$ iterations and faster algorithms for maximum flow.  In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 424–433, 2014.
  * [26] Y. T. Lee and A. Sidford.  Solving linear programs with $\tilde{O}(\sqrt{{\rm rank}})$ linear system solves.  arXiv preprint arXiv:1910.08033, 2019.
  * [27] Y. T. Lee and M.-C. Yue.  Universal barrier is $n$-self-concordant.  Mathematics of Operations Research, 46(3):1129–1148, 2021.
  * [28] A. Madry.  Navigating central path with electrical flows: From flows to matchings, and back.  In Proceedings of the 54th Annual Symposium on Foundations of Computer Science, pages 253–262. IEEE, 2013.
  * [29] N. Megiddo.  Is binary encoding appropriate for the problem-language relationship?  Theoretical Computer Science, 19(3):337–341, 1982.
  * [30] N. Megiddo, S. Mizuno, and T. Tsuchiya.  A modified layered-step interior-point algorithm for linear programming.  Mathematical Programming, 82(3):339–355, 1998.
  * [31] S. Mizuno, M. Todd, and Y. Ye.  On adaptive-step primal-dual interior-point algorithms for linear programming.  Mathematics of Operations Research, 18:964–981, 11 1993.
  * [32] R. D. Monteiro and T. Tsuchiya.  A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms.  Mathematical Programming, 115(1):105–149, 2008.
  * [33] R. D. C. Monteiro and T. Tsuchiya.  A variant of the Vavasis-Ye layered-step interior-point algorithm for linear programming.  SIAM Journal on Optimization, 13(4):1054–1079, 2003.
  * [34] R. D. C. Monteiro and T. Tsuchiya.  A new iteration-complexity bound for the MTY predictor-corrector algorithm.  SIAM Journal on Optimization, 15(2):319–347, 2005.
  * [35] Y. Nesterov and A. Nemirovskii.  Interior-point polynomial algorithms in convex programming.  SIAM, 1994.
  * [36] J. Renegar.  A polynomial-time algorithm, based on Newton’s method, for linear programming.  Mathematical Programming, 40(1-3):59–93, 1988.
  * [37] J. Renegar.  A Mathematical View of interior point Methods in Convex Optimization.  Society for Industrial and Applied Mathematics, 2001.
  * [38] S. Smale.  Mathematical problems for the next century.  The Mathematical Intelligencer, 20:7–15, 1998.
  * [39] G. Sonnevend, J. Stoer, and G. Zhao.  On the complexity of following the central path of linear programs by linear extrapolation II.  Mathematical Programming, 52(1-3):527–553, 1991.
  * [40] D. A. Spielman and S.-H. Teng.  Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems.  In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), 2004.
  * [41] D. A. Spielman and S.-H. Teng.  Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time.  Journal of the ACM (JACM), 51(3):385–463, 2004.
  * [42] P. M. Vaidya.  Speeding-up linear programming using fast matrix multiplication.  In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 332–337, 1989.
  * [43] J. van den Brand.  A deterministic linear program solver in current matrix multiplication time.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 259–278. SIAM, 2020.
  * [44] J. van den Brand, Y. T. Lee, Y. P. Liu, T. Saranurak, A. Sidford, Z. Song, and D. Wang.  Minimum cost flows, MDPs, and L1-regression in nearly linear time for dense instances.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 859–869, 2021.
  * [45] J. van den Brand, Y.-T. Lee, D. Nanongkai, R. Peng, T. Saranurak, A. Sidford, Z. Song, and D. Wang.  Bipartite matching in nearly-linear time on moderately dense graphs.  In 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 919–930, 2020.
  * [46] J. van den Brand, Y. Tat Lee, A. Sidford, and Z. Song.  Solving tall dense linear programs in nearly linear time.  In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC), pages 775–788, 2020.
  * [47] S. A. Vavasis and Y. Ye.  Condition numbers for polyhedra with real number data.  Operations Research Letters, 17:209–214, 06 1995.
  * [48] S. A. Vavasis and Y. Ye.  A primal-dual interior point method whose running time depends only on the constraint matrix.  Mathematical Programming, 74(1):79–120, 1996.
  * [49] Y. Ye.  Interior-Point Algorithms: Theory and Analysis.  John Wiley and Sons, New York, 1997.

##  Appendix A Missing Proofs in Section 2

###### Proof of Proposition 2.1.

Since $x-x^{\prime}\in W$ and $s-s^{\prime}\in W^{\perp}$, we have that

$0=\left\langle
x-x^{\prime},s-s^{\prime}\right\rangle\Leftrightarrow\left\langle
x,s\right\rangle+\left\langle x^{\prime},s^{\prime}\right\rangle=\left\langle
x,s^{\prime}\right\rangle+\left\langle x^{\prime},s\right\rangle.$

∎

###### Proof of Proposition 2.2.

Using that $\sum_{i=1}^{k}\lambda_{i}=1$ and the orthogonality of
$x^{(i)}-d\in W$ and $s^{(i)}-d\in W^{\perp}$ for all $i\in[k]$ we first get

$\displaystyle\left\langle\sum_{i=1}^{k}\lambda_{i}x^{(i)},\sum_{j=1}^{k}\lambda_{i}s^{(i)}\right\rangle$
$\displaystyle=\left\langle\sum_{i=1}^{k}\lambda_{i}(x^{(i)}-d)+d,\sum_{j=1}^{k}\lambda_{i}(s^{(i)}-c)+c\right\rangle$
$\displaystyle=\left\langle
d,c\right\rangle+\sum_{i=1}^{k}\lambda_{i}(\left\langle
x^{(i)}-d,c\right\rangle+\left\langle d,s^{(i)}-c\right\rangle)$
$\displaystyle=\sum_{i=1}^{k}\lambda_{i}(\left\langle
d,c\right\rangle+\left\langle x^{(i)}-d,c\right\rangle+\left\langle
d,s^{(i)}-c\right\rangle)$
$\displaystyle=\sum_{i=1}^{k}\lambda_{i}\left\langle
x^{(i)},s^{(i)}\right\rangle.$

Division by $n$ yields the respective normalized duality gap. ∎

###### Proof of Proposition 2.5.

By definition of $\mathcal{N}(\beta)$ we have for all $i\in[n]$ that
$|\frac{x_{i}s_{i}}{\mu}-1|\leq\|\frac{xs}{\mu}-\mathbf{1}\|\leq\beta$ and so
$(1-\beta)\mu\leq x_{i}s_{i}\leq(1+\beta)\mu$. ∎

###### Proof of Lemma 2.17.

Note first that by construction, the solution set of $L_{I}^{W}(x)$ is non-
empty. Furthermore, the minimal norm solution exists and is unique by strict
convexity of the square Euclidean norm. Thus, $w=L_{I}^{W}(x)$ is well-
defined.

We now show that $w=L_{I}^{W}(x)$ is a solution to the linear system. Clearly,
$w\in W$ and
$w_{I}=\Pi_{\pi_{I}(W)}(x)=x-\Pi_{\pi_{I}(W)^{\perp}}(x)\in\pi_{I}(W)^{\perp}+x$.
It remains to show that
$w_{J}\in\pi_{J}(W^{\perp})=\pi_{J}((W\cap\mathbb{R}^{n}_{J})^{\perp})$. Take
any $z\in\mathbb{R}^{n}_{J}\cap W$ with $\|z\|^{2}=1$. It suffices to show
that $\left\langle w,z\right\rangle=\left\langle w_{J},z_{J}\right\rangle=0$.
Noting that $w+\beta z\in W$ and $(w+\beta z)_{I}=w_{I}=\Pi_{\pi_{I}(W)}(x)$,
by the definition of $w=L_{I}^{W}(x)$, we must have that
$\|w\|^{2}\leq\min_{\beta\in\mathbb{R}}\|w+\beta
z\|^{2}=\|w\|^{2}-\left\langle z,w\right\rangle^{2}$. In particular,
$\left\langle z,w\right\rangle=0$, as needed.

Now take any $w\in W$, $w_{J}\in\pi_{J}(W^{\perp})$,
$w_{I}\in\pi_{I}(W)^{\perp}+x$. We wish to show that $w=L^{W}_{I}(x)$.
Firstly, by the above argument, this system always has a solution, namely
$L_{I}^{W}(x)$. Secondly, note that $z\in W$ implies that
$w_{I}\in(\pi_{I}(W)^{\perp}+x)\cap\pi_{I}(W)$. By the uniqueness of the
orthogonal decomposition, this implies that $z_{I}=\Pi_{\pi_{I}(W)}(x)$. Thus,
$z$ is in the solution set of the $L_{I}^{W}(x)$ program. It remains to show
that $z$ has minimum norm. Letting $w^{\prime}\in W\setminus\\{w\\}$ satisfy
$w^{\prime}_{I}=\Pi_{\pi_{I}(W)}(x)$, we must show that
$\|w^{\prime}\|^{2}>\|w\|^{2}$. Noting that
$z=w^{\prime}-w\in(W\cap\mathbb{R}^{n}_{J})\setminus\\{\mathbf{0}\\}$ and
recalling that $w\in(W\cap\mathbb{R}^{n}_{J})^{\perp}$, we have that
$\|w+z\|^{2}=\|w\|^{2}+2\left\langle
z,w\right\rangle+\|z\|^{2}=\|w\|^{2}+\|z\|^{2}>\|w\|^{2}$. Thus,
$w=L^{W}_{I}(x)$ as needed.

Given the above, we see that the solution to the linear system always exists
and is unique (since $L_{I}^{W}(x)$ is well-defined). Secondly, since
$L_{I}^{W}(x)$ is the unique solution to a linear system of equations
depending linearly on $x$, we have that $L_{I}^{W}$ is a linear map. ∎

###### Proof of Lemma 2.18.

To prove the statement, it suffices to show that for all $x\in\mathbb{R}^{I}$
that

$L_{I}^{W}(x)=\left(\Pi_{\pi_{I}(W)}(x),\ell_{I}^{W}(x)\right)=\left(\Pi_{\pi_{I}(W)}(x),-\operatorname{ad}\left[\ell_{J}^{W^{\perp}}\right](x)\right).$

Letting
$z\coloneqq\left(\Pi_{\pi_{I}(W)}(x),-\operatorname{ad}\left[\ell_{J}^{W^{\perp}}\right](x)\right)$,
by Lemma 2.17, it suffices to show that

  1. (i)

$z\in W$,

  2. (ii)

$z_{I}\in\pi_{I}(W)^{\perp}+x$,

  3. (iii)

$z_{J}\in\pi_{J}(W^{\perp})$.

Property (ii) follows directly from
$z_{I}=\Pi_{\pi_{I}(W)}(x)=x-\Pi_{(\pi_{I}(W))^{\perp}}(x)$. To show (i), it
suffices to show that $\left\langle v,z\right\rangle=0$, $\forall v\in
W^{\perp}$. For $v\in W^{\perp}$, we see that

$\displaystyle\left\langle z,v\right\rangle$
$\displaystyle=\left\langle\Pi_{\pi_{I}(W)}(x),v_{I}\right\rangle-\left\langle\operatorname{ad}\left[\ell_{J}^{W^{\perp}}\right](x),v_{J}\right\rangle=\left\langle\Pi_{\pi_{I}(W)}(x),v_{I}\right\rangle-\left\langle
x,\ell_{J}^{W^{\perp}}(v_{J})\right\rangle$
$\displaystyle=\left\langle\Pi_{\pi_{I}(W)}(x),v_{I}\right\rangle-\left\langle\Pi_{\pi_{I}(W)}(x),\ell_{J}^{W^{\perp}}(v_{J})\right\rangle\quad\left(\text{
since }\ell_{J}^{W^{\perp}}(v_{J})\in\pi_{I}(W)\right)$
$\displaystyle=\left\langle\Pi_{\pi_{I}(W)}(x),v_{I}-\ell_{J}^{W^{\perp}}(v_{J})\right\rangle=\left\langle
L_{I}^{W}(x),(v_{I}-\ell_{J}^{W^{\perp}}(v_{J}),0_{J})\right\rangle$
$\displaystyle=\left\langle
L_{I}^{W}(x),v-L_{J}^{W^{\perp}}(v_{J})\right\rangle=0\,,\quad\left(\text{
since }v_{J}\in\pi_{J}(W^{\perp})\right)$

where the last equality follows since $L_{I}^{W}(x)\in W$ and
$v-L_{J}^{W^{\perp}}(v_{j})\in W^{\perp}$.

For (iii), we must show that $\left\langle z,w\right\rangle=0$, $\forall w\in
W\cap\mathbb{R}^{n}_{J}$. For $w\in W\cap\mathbb{R}^{n}_{J}$, we first claim
that $L_{J}^{W^{\perp}}(w_{J})=\mathbf{0}_{n}$. By Lemma 2.17, this follows
since $x=\mathbf{0}$ a solution to the linear system

$x_{J}\in\pi_{J}(W^{\perp})^{\perp}=\pi_{J}(W\cap\mathbb{R}^{n}_{J})=\pi_{J}(W\cap\mathbb{R}^{n}_{J})+w_{J},\quad
x\in W^{\perp},\quad x_{I}\in W_{I}.$ (95)

From the claim, we must have
$\ell^{W^{\perp}}_{J}(w_{J})=(L_{J}^{W^{\perp}}(w_{J}))_{I}=\mathbf{0}_{I}$.
Therefore,

$\left\langle
z,w\right\rangle=-\left\langle\operatorname{ad}\left[\ell_{J}^{W^{\perp}}\right](x),w_{J}\right\rangle=-\left\langle
x,\ell_{J}^{W^{\perp}}(w_{J})\right\rangle=-\left\langle
x,\mathbf{0}_{I}\right\rangle=0.$

Thus, $\ell^{W}_{I}=-\operatorname{ad}\left[\ell^{W}_{J}\right]$ as needed.
The equality of singular values follows from the fact that adjoints operators
have the same non-zero singular values. ∎

###### Proof of Lemma 2.19.

By definition $\operatorname{im}(\ell_{I}^{W})\subseteq\pi_{J}(W)$ and by
Lemma 2.17 we have
$\operatorname{im}(\ell_{I}^{W})\subseteq\pi_{J}(W^{\perp})$. This gives the
inclusion
$\pi_{J}(W^{\perp})\cap\pi_{J}(W)\supseteq\operatorname{im}(\ell_{I}^{W})$.
For the other direction take any $y\in\pi_{J}(W^{\perp})\cap\pi_{J}(W)$. As
$y\in\pi_{J}(W)$ there exists $w\in W$ such that $w_{J}=y$. Note that $w$
fulfills the properties in Lemma 2.17 for $x=w_{I}$ and therefore
$w=L_{I}^{W}(x)$. In particular $y=w_{J}=\ell_{I}^{W}(x)$ and hence
$y\in\operatorname{im}(\ell_{I}^{W})$. ∎

##  Appendix B Missing Proof in Section 3

######  Proof of Proposition 3.1.

We restrict to the proof of the boundedness of $\mathcal{P}_{g}$, since the
proof is analogous for $\mathcal{D}_{g}$. Let $s^{\circ}\in\mathcal{D}_{++}$
be a strictly feasible point of the dual, and $x\in\mathcal{P}_{g}$. By
Proposition 2.1, we have

$\left\langle x,s^{\star}\right\rangle+\left\langle
x^{\star},s^{\circ}\right\rangle=\left\langle
x,s^{\circ}\right\rangle+\left\langle x^{\star},s^{\star}\right\rangle\,.$

Since $\left\langle x^{\star},s^{\star}\right\rangle=0$, we deduce that
$\left\langle x,s^{\circ}\right\rangle\leq g+\left\langle
x^{\star},s^{\circ}\right\rangle$. As $s^{\circ}>0$, this implies that
$x_{i}\leq(g+\left\langle x^{\star},s^{\circ}\right\rangle)/s^{\circ}_{i}$ for
all $i\in[n]$. ∎