$\ell_{y}+B_{\delta}$, integration of the exponential distribution over
$K^{\prime}$ must be infinite, leading to contradiction. ∎

The following is the extension of Nesterov et al. (2018, Theorem 5.1.6) to
self-concordant matrix functions, which implies invertibility of Dikin-
amenable metrics in the reduced problem.

######  Lemma 4.24.

For convex $K\subset\mathbb{R}^{d}$ containing no straight line, a self-
concordant matrix function $g:\textup{{int}}(K)\to\mathbb{S}_{+}^{d}$ is non-
degenerate on $K$.

###### Proof.

Suppose ${\|h\|}_{g(x)}=0$ for some $0\neq h\in\mathbb{R}^{d}$ and
$x\in\textup{{int}}(K)$. Clearly, the line $x+th$ for $t\in\mathbb{R}$ is
contained in $\mathcal{D}_{g}^{1}(x)$. As $\mathcal{D}_{g}^{1}(x)\subset K$
due to Lemma 4.3, it implies that $K$ contains a straight line $x+th$, which
leads to contradiction. ∎

See 3

###### Proof.

First of all, $\bar{g}_{i}^{e}$ is $(\nu_{i},\bar{\nu}_{i})$-self-concordant
(Corollary 4.20), and SLTSC and SASC on $K^{\prime}$ (Lemma 4.22). For fixed
$\varepsilon>0$, $\bar{g}_{i}^{e}+\varepsilon I$ is SSC by Lemma 4.21. We can
make similar arguments for $\bar{g}_{j}^{c}$ regarding self-concordance,
symmetry, SLTSC, SASC, and SSC. Hence, $g+(I+J)\varepsilon I$ is SSC by Lemma
4.5. Since $g$ is self-concordant on $K^{\prime}$ by Lemma 4.2 and
$K^{\prime}$ contains no straight line, $g$ is PD by Lemma 4.24. Sending
$\varepsilon$ to $0$, we can obtain SSC of $g$. LTSC and ASC of $g$ follows
from Lemma 4.12 and 4.14. The symmetry parameter of $g$ follows from Lemma
4.11. ∎

###  4.4 Direct product

For $i\in[m]$ and domain $E_{i}\subset\mathbb{R}^{d_{i}}$, let
$g_{i}(x_{i}):\textup{{int}}(E_{i})\to\mathbb{S}_{++}^{d_{i}}$ be a self-
concordant matrix. For $l:=\sum_{i}d_{i}$ and $E:=\prod_{i}E_{i}$, we define a
self-concordant matrix $g$ on $E\subset\mathbb{R}^{l}$ with block diagonals
being $g_{i}$. To be precise, we can write

$\displaystyle g(x)$
$\displaystyle=g(x_{1},\dots,x_{m}):=\sum_{i}\bar{g}_{i}(x)\,,$

where $\bar{g}_{i}:\mathbb{R}^{l}\to\mathbb{S}_{+}^{l}$ is a matrix function
whose entry is all zero but the $i$-th block diagonal being $g_{i}$.

When handling the direct product of domains, it is common for each domain to
have an $\mathcal{O}(1)$-dimension. In such cases, scaling the barriers by
dimension worsens mixing time at most constant factors while making the
barriers SSC and SLTSC. We defer the proofs to §7.3.7.

######  Lemma 4.25 (SSC under direct product).

For open $E_{i}\subset\mathbb{R}^{d_{i}}$, let
$g_{i}:E_{i}\to\mathbb{S}_{++}^{d_{i}}$ be SC. Then $g:=\sum d_{i}\bar{g}_{i}$
defined on $\prod E_{i}$ is SSC.

######  Lemma 4.26 (SLTSC under direct product).

For open $E_{i}\subset\mathbb{R}^{d_{i}}$, let
$g_{i}:E_{i}\to\mathbb{S}_{++}^{d_{i}}$ be HSC. Then $g:=\sum
d_{i}\bar{g_{i}}$ defined on $\prod E_{i}$ is SLTSC.

###  4.5 Inverse images under non-linear mappings

Nesterov and Nemirovskii (1994) introduced the notion of _compatibility_ with
a convex domain while constructing a self-concordant barrier for a wider class
of structured constraints. We generalize this notion to the fourth order, by
which we can easily construct a SSC, SLTSC, and SASC barrier. For a convex
cone $K$, we use $a\leq_{K}b$ to denote $b-a\in K$.

######  Definition 4.27 (Compatibility).

Let $\beta,\gamma\geq 0$. Let $K$ be a convex cone in $\mathbb{R}^{m}$ and
$\Gamma$ be a closed convex domain in $\mathbb{R}^{d}$. A mapping
$\mathcal{A}:\textup{{int}}(\Gamma)\to\mathbb{R}^{m}$ of class $C^{4}$ is
called $(K,\beta,\gamma)$-compatible with the domain $\Gamma$ if

  * •

$\mathcal{A}$ is concave with respect to $K$. That is,
$t\mathcal{A}(x)+(1-t)\,\mathcal{A}(y)\leq_{K}\mathcal{A}(tx+(1-t)\,y)$ for
all $t\in[0,1]$ and $x,y\in\textup{{int}}(\Gamma)$. Equivalently,
$-\mathrm{D}^{2}\mathcal{A}(x)[h,h]\in K$ for any $x\in\textup{{int}}(\Gamma)$
and $h\in\mathbb{R}^{m}$.

  * •

For any $x\in\textup{{int}}(\Gamma)$, $y\in\Gamma\cap(2x-\Gamma)$, and
$h=y-x$, it holds that

$\displaystyle\beta\mathrm{D}^{2}\mathcal{A}(x)[h,h]$
$\displaystyle\leq_{K}\mathrm{D}^{3}\mathcal{A}(x)[h,h,h]\leq_{K}-\beta\mathrm{D}^{2}\mathcal{A}(x)[h,h]\,,$
$\displaystyle\gamma\mathrm{D}^{2}\mathcal{A}(x)[h,h]$
$\displaystyle\leq_{K}\mathrm{D}^{4}\mathcal{A}(x)[h,h,h,h]\leq_{K}-\gamma\mathrm{D}^{2}\mathcal{A}(x)[h,h]\,.$

######  Example 4.28.

An affine mapping is $(\\{0\\},0,0)$-compatible with any closed convex domain.
We note that a function that is $(\mathbb{R}_{+},\beta,\gamma)$-compatible
with $\mathbb{R}_{+}$ is a $C^{4}$-smooth concave real-valued function
$f:(0,\infty)\to\mathbb{R}$ such that for any $t>0$,

$\displaystyle|f^{\prime\prime\prime}(t)|$
$\displaystyle\leq-\frac{\beta}{t}\,f^{\prime\prime}(t)\quad\text{and}\quad|f^{(4)}(t)|\leq-\frac{\gamma}{t^{2}}\,f^{\prime\prime}(t)\,.$

  * •

Let $0<p\leq 1$. Then the function of $f(t)=t^{p}$ is
$(\mathbb{R}_{+},2-p,(2-p)\,(3-p))$-compatible with $\mathbb{R}_{+}$.

  * •

$f(t)=\log t$ is $(\mathbb{R}_{+},2,6)$-compatible with $\mathbb{R}_{+}$.

The following lemma is an extension of Nesterov and Nemirovskii (1994, Lemma
5.1.3) to our fourth-order compatibility.

######  Lemma 4.29.

Let $K,K_{1},K_{2}$ be convex cones in
$\mathbb{R}^{m},\mathbb{R}^{m_{1}},\mathbb{R}^{m_{2}}$ respectively.

  * •

If $\mathcal{A}:\textup{{int}}(\Gamma)\to\mathbb{R}^{m}$ is
$(K,\beta,\gamma)$-compatible with $\Gamma$ and $K\subset K^{\prime}$ is a
closed convex cone in $\mathbb{R}^{m}$, then $\mathcal{A}$ is
$(K^{\prime},\beta,\gamma)$-compatible with $\Gamma$.

  * •

If $\mathcal{A}_{i}:\textup{{int}}(\Gamma_{i})\to\mathbb{R}^{m_{i}}$ is
$(K_{i},\beta_{i},\gamma_{i})$-compatible with $\Gamma_{i}$ for $i=1,2$, then
$\mathcal{A}:\textup{{int}}(\Gamma_{1}\times\Gamma_{2})\to\mathbb{R}^{m_{1}}\times\mathbb{R}^{m_{2}}$
mapping $(x,y)\to(\mathcal{A}_{1}(x),\mathcal{A}_{2}(y))$ is $(K_{1}\times
K_{2},\max(\beta_{1},\beta_{2}),\max(\gamma_{1},\gamma_{2}))$-compatible with
$\Gamma_{1}\times\Gamma_{2}$.

We now introduce a main result in this section (see §7.3.8). To begin with, we
recall that for a closed convex domain $G\subset\mathbb{R}^{d}$ the _recessive
cone_ $R(G)$ of $G$ is $\\{h\in\mathbb{R}^{d}:x+th\in G\ \text{for all }x\in
G\text{ and }t>0\\}$.

######  Lemma 4.30.

Let $G$ be a closed convex domain in $\mathbb{R}^{m}$, $F$ be a highly
$\theta$-self-concordant barrier for $G$, $\Gamma$ be a closed convex domain
in $\mathbb{R}^{d}$, and $\Pi$ be a highly $\nu$-self-concordant barrier for
$\Gamma$. Let $\mathcal{A}$ be a $(K,\beta,\gamma)$-compatible with $\Gamma$,
where $K$ is a ray contained in the recessive cone $R(G)$. Assume that
$\mathcal{A}(\textup{{int}}(\Gamma))\cap G\neq\emptyset$.

  * •

The set
$G^{+}=\overline{\textup{{int}}(\Gamma)\cap\mathcal{A}^{-1}{\bigl{(}\textup{{int}}(G)\bigr{)}}}$
is a closed convex domain in $\mathbb{R}^{d}$.

  * •

For $\delta=\max\left(\beta,\gamma,2\right)$, the function
$\Psi(x)=F(\mathcal{A}(x))+\delta^{2}\,\Pi(x)$ is a
$(\theta+\delta^{2}\nu)$-self-concordant barrier for $G^{+}$.

  * •

$\Psi$ is highly self-concordant.

Using this result, we can obtain a useful tool in establishing lower trace
self-concordance of a barrier for the direct product of structured sets.

######  Lemma 4.31.

Let $f$ be a $C^{4}$ concave function on $\\{t>0\\}$ such that
$|f^{\prime\prime\prime}(t)|\leq\frac{\beta}{t}\,|f^{\prime\prime}(t)|$ and
$|f^{(4)}(t)|\leq\frac{\gamma}{t^{2}}\,|f^{\prime\prime}(t)|$ for $t>0$. Then
the function

$F(t,x)=-\log{\bigl{(}f(t)-x\bigr{)}}-\max(4,\beta^{2},\gamma^{2})\,\log t$

is a highly $(1+\max(4,\beta^{2},\gamma^{2}))$-self-concordant barrier for the
two dimensional convex domain

$G_{f}=\overline{\\{(t,x)\in\mathbb{R}^{2}:t>0,\,x\leq f(t)\\}}\,.$

###### Proof.

From the discussion in Example 4.28, the map $f(t):(0,\infty)\to\mathbb{R}$ is
$(\mathbb{R}_{+},\beta,\gamma)$-compatible with $\mathbb{R}_{+}$. Clearly, the
identity map from $\mathbb{R}$ to $\mathbb{R}$ is $(\\{0\\},0,0)$-compatible
with $\mathbb{R}$. Hence by Lemma 4.29-(2) implies that the map
$\mathcal{A}:\mathbb{R}_{+}\times\mathbb{R}\to\mathbb{R}^{2}$ defined by
$\mathcal{A}(t,x)=(f(t),x)$ is
$(\\{0\\}\times\mathbb{R}_{+},\beta,\gamma)$-compatible with
$\mathbb{R}_{+}\times\mathbb{R}$.

Now observe that $G_{f}$ can be written as
$\mathcal{A}^{-1}{\bigl{(}\\{(t,x):x\leq t\\}\bigr{)}}$ and that
$K=\\{0\\}\times\mathbb{R}_{+}$ is a ray contained in the recessive cone
$R(G)$ for $G:=\\{(t,x):x\leq t\\}$. By applying Lemma 4.30 to the highly
$1$-self-concordant barriers $F(t,x)=-\log(t-x)$ for $G$ and $\Phi(t,x)=-\log
t$ for $\mathbb{R}_{+}\times\mathbb{R}$, it follows that $F$ is is a highly
$(1+\max(4,\beta^{2},\gamma^{2}))$-self-concordant barrier for $G_{f}$. ∎

We can prove a similar result for a convex $f$ as follows:

######  Lemma 4.32.

Let $f$ be a $C^{4}$ convex function on $\\{x>0\\}$ such that
$|f^{\prime\prime\prime}(x)|\leq\frac{\beta}{x}\,f^{\prime\prime}(x)$ and
$|f^{(4)}(x)|\leq\frac{\gamma}{x^{2}}\,f^{\prime\prime}(x)$ for $x>0$. Then
the function

$F(t,x)=-\log{\bigl{(}t-f(x)\bigr{)}}-\max(4,\beta^{2},\gamma^{2})\,\log x$

is a highly $(1+\max(4,\beta^{2},\gamma^{2}))$-self-concordant barrier for the
two dimensional convex domain

$G_{f}=\overline{\\{(t,x)\in\mathbb{R}^{2}:x>0,\,t\geq f(x)\\}}\,.$

Its proof follows from applying Lemma 4.31 to the image of $G_{f}$ under the
map $(t,x)\to(-x,t)$.

##  5 Structured densities and constraint families

In order to obtain a mixing-time bound of the $\mathsf{Dikin\ walk}$ for the
reduced problem, a concrete understanding of properties and parameters of
barriers for $K_{i}$ and $K_{j}$ is essential. To this end, we revisit self-
concordant barriers for structured convex constraints and level sets,
examining the required scaling factors which ensure those properties.

###  5.1 Linear constraints

Consider a set of linear constraints: $K=\\{x\in\mathbb{R}^{d}:Ax\geq b\\}$
for $A\in\mathbb{R}^{m\times d}$ and $b\in\mathbb{R}^{m}$, where $A$ has no
all-zero rows. We use $s_{x}:=Ax-b$ to denote the slack at $x$, and
$A_{x}:=S_{x}^{-1}A$ to denote the constraints normalized by the slack, where
$S_{x}:=\textup{{Diag}}(s_{x})$ is the diagonalization of the slack.

We now introduce three barriers (and metrics) for handling the linear
constraints.

##### Logarithmic barrier.

The logarithmic barrier
$\phi_{\log}(x):=-\sum_{i=1}^{m}\log(a_{i}^{\mathsf{T}}x-b_{i})$ is the
simplest self-concordant barrier for linear constraints. We refer readers to
§B.1 for gentle introduction to the log-barriers. As seen below, we
demonstrate that the metric induced by the logarithmic barrier has
$\nu,\bar{\nu}=m$ and requires no scaling to achieve SSC, SLTSC, and SASC.

######  Lemma 5.1 (Logarithmic barrier).

For a closed convex $K=\\{x\in\mathbb{R}^{d}:Ax\geq b\\}$ with
$A\in\mathbb{R}^{m\times d}$ and $b\in\mathbb{R}^{m}$, let
$\phi_{\log}(x)=-\sum_{i=1}^{m}\log(a_{i}^{\mathsf{T}}x-b_{i})$ and define
$g(x):=\nabla^{2}\phi_{\log}(x)=A_{x}^{\mathsf{T}}A_{x}$.

  * •

$\nu=m$ (Nesterov and Nemirovskii (1994)).

  * •

SSC along $\textup{{row}}(A)$ and $\bar{\nu}=m$ (Lemma 5.5).

  * •

$\mathrm{D}^{2}g(x)[h,h]\succeq 0$ for any $h\in\mathbb{R}^{d}$ (so SLTSC)
(Claim B.1).

  * •

SASC (Lemma 5.10).

##### Vaidya metric.

In sampling over a polytope $K$, the number $m$ of constraints is assumed to
be greater than the ambient dimension $d$. Given that the mixing time of the
$\mathsf{Dikin\ walk}$ for uniform sampling is
$\widetilde{\mathcal{O}}(d\bar{\nu})=\widetilde{\mathcal{O}}(dm)$, a larger
$m$ leads to a worse mixing time. Is there a self-concordant barrier that has
a better dependence on $m$ for its self-concordance and symmetry parameters,
without compromising SSC, SLTSC, and SASC?

Let us recall the _leverage score_ first and move onto such improved self-
concordant barriers. For a full-rank matrix $A\in\mathbb{R}^{m\times d}$ with
$m\geq d$, we recall that $P(A)=A(A^{\mathsf{T}}A)^{-1}A^{\mathsf{T}}$ is the
orthogonal projection matrix onto the column space of $A$, and the leverage
scores of $A$ is $\sigma(A)=\textsf{{diag}}(P(A))\in\mathbb{R}^{m}$. We let
$\Sigma(A):=\textup{{Diag}}(\sigma(A))=\textup{{Diag}}(P(A))$ and
$P^{(2)}(A)=P(A)\circ P(A)$, where $P(A)\circ P(A)$ is the Hadamard product of
size $d\times d$ defined by $(P(A)\circ P(A))_{ij}=[P(A)]_{ij}^{2}$.

Vaidya (1996) introduced the _volumetric barrier_ for $K$ defined by

$\phi_{\textrm{vol}}=\frac{1}{2}\,\log\det(\nabla^{2}\phi_{\log})=\frac{1}{2}\,\log\det(A_{x}^{\mathsf{T}}A_{x})\,.$

Then the Hessian of $\phi_{\textrm{vol}}$ can be written as

$\nabla^{2}\phi_{\textrm{vol}}=A_{x}^{\mathsf{T}}(3\Sigma_{x}-2P_{x}^{(2)})A_{x}\,,$

where $\Sigma_{x}=\textup{{Diag}}(\sigma(A_{x}))$ is the diagonalized leverage
scores, and this Hessian satisfies

$A_{x}^{\mathsf{T}}\Sigma_{x}A_{x}\preceq\nabla^{2}\phi_{\textrm{vol}}(x)\preceq
3A_{x}^{\mathsf{T}}\Sigma_{x}A_{x}\,.$

We refer readers to §B.2 for details. In other words, the _approximate_
volumetric metric $A_{x}^{\mathsf{T}}\Sigma_{x}A_{x}$ serves as an
$\mathcal{O}(1)$-approximation of the local metric
$\nabla^{2}\phi_{\textrm{vol}}$ (i.e.,
$A_{x}^{\mathsf{T}}\Sigma_{x}A_{x}\asymp\nabla^{2}\phi_{\textrm{vol}}(x)$). We
find in Lemma 5.5 that the local metric
$40\sqrt{m}A_{x}^{\mathsf{T}}\Sigma_{x}A_{x}$ is SSC with
$\nu,\,\bar{\nu}=\mathcal{O}(\sqrt{m}d)$, but in some regime of $d$ this
parameter leads to worse mixing of the $\mathsf{Dikin\ walk}$. In the same
paper, Vaidya (1996) introduced a _regularized_ volumetric metric by adding
$\mathcal{O}{\bigl{(}\nabla^{2}\phi_{\log}\bigr{)}}$, which we call the
_Vaidya metric_ :

$g(x):=\sqrt{\frac{m}{d}}\,A_{x}^{\mathsf{T}}{\bigl{(}\Sigma_{x}+\frac{d}{m}I_{m}\bigr{)}}A_{x}\,.$

Note that
$g(x)\asymp\nabla^{2}{\bigl{(}\sqrt{\frac{m}{d}}{\bigl{(}\phi_{\textrm{vol}}+\frac{d}{m}\text{$\phi_{\log}$}\bigr{)}}\bigr{)}}$.
We show that the Vaidya metric is also SSC, SLTSC, and SASC without additional
scaling, while it has a better $\nu$ and $\bar{\nu}$ than the logarithmic
barrier.

######  Lemma 5.2 (Vaidya metric).

For a closed convex $K=\\{x\in\mathbb{R}^{d}:Ax\geq b\\}$ with
$A\in\mathbb{R}^{m\times d}$ and $b\in\mathbb{R}^{m}$, let
$g(x)=\sqrt{\frac{m}{d}}A_{x}^{\mathsf{T}}{\bigl{(}\Sigma_{x}+\frac{d}{m}I_{m}\bigr{)}}A_{x}$.

  * •

$\nu=\mathcal{O}(\sqrt{md})$ Anstreicher (1997, Theorem 5.2).

  * •

SSC and $\bar{\nu}=\mathcal{O}(\sqrt{md})$ (Lemma 5.5).

  * •

SLTSC (Lemma 5.6) and SASC (Lemma 5.11).

##### Lewis weights metric.

Self-concordance and symmetry parameters of $\mathcal{O}(\sqrt{md})$ is
certainly better than $\mathcal{O}(m)$, but can we even achieve an
$\mathcal{O}(d\log^{\mathcal{O}(1)}m)$ bound on those parameters?

Let us recall the $\ell_{p}$-_Lewis weights_. The $\ell_{p}$-Lewis weight of
$A$ is denoted by $w(A)$, the solution $w$ to the equation
$w(A)=\textsf{{diag}}{\bigl{(}W^{\nicefrac{{1}}{{2}}-\nicefrac{{1}}{{p}}}A(A^{\mathsf{T}}W^{1-\nicefrac{{2}}{{p}}}A)^{-1}A^{\mathsf{T}}W^{\nicefrac{{1}}{{2}}-\nicefrac{{1}}{{p}}}\bigr{)}}\in\mathbb{R}^{m}$
for $W:=\textup{{Diag}}(w)$. For $W_{x}=\textup{{Diag}}(w(A_{x}))$ and $p\geq
2$, the Lewis weight barrier function is defined by

$\phi_{\textup{{Lw}}}(x):=\log\det(A_{x}^{\mathsf{T}}W_{x}^{1-\nicefrac{{2}}{{p}}}A_{x})\,.$

Note that the leverage score and volumetric barrier can be recovered as a
special case of the Lewis weight and barrier by setting $p=2$. As done for the
Vaidya metric, it is natural to consider the Lewis weight metric with
$p=\Theta(\log^{\mathcal{O}(1)}m)$, defined as

$g(x):=\mathcal{O}(\log^{\mathcal{O}(1)}m)\,A_{x}^{\mathsf{T}}W_{x}A_{x}\,.$

In fact, this metric serves as an
$\mathcal{O}(\log^{\mathcal{O}(1)}m)$-approximation of
$\nabla^{2}\phi_{\textup{{Lw}}}$, as demonstrated in the following relation
proven in Lee and Sidford (2019, Lemma 31):

$A_{x}^{\mathsf{T}}\Sigma_{x}A_{x}\preceq\nabla^{2}\phi_{\textup{{Lw}}}\preceq(1+p)\,A_{x}^{\mathsf{T}}\Sigma_{x}A_{x}\,.$

Ignoring the logarithmic factors we have $\nabla^{2}\phi_{\textup{{Lw}}}\asymp
g$. Notably, the Lewis-weight metric needs an additional $\sqrt{d}$-scaling
for SLTSC and SASC, unlike the logarithmic barrier and Vaidya metric. Hence,
when combining this with other metrics, one should use $\sqrt{d}g$, which
leads to $\nu,\,\bar{\nu}=\mathcal{O}(d^{3/2}\,\log^{\mathcal{O}(1)}m)$.

######  Lemma 5.3 (Lewis weight metric).

For a closed convex $K=\\{x\in\mathbb{R}^{d}:Ax\geq b\\}$ with
$A\in\mathbb{R}^{m\times d}$ and $b\in\mathbb{R}^{m}$, let
$g(x)=\mathcal{O}(\log^{\mathcal{O}(1)}m)\,A_{x}^{\mathsf{T}}W_{x}A_{x}$.

  * •

$\nu=\mathcal{O}(d\log^{5}m)$ Lee and Sidford (2019, Theorem 30).

  * •

SSC and $\bar{\nu}=\mathcal{O}(d\log^{\mathcal{O}(1)}m)$ (Lemma 5.5).

  * •

$\sqrt{d}g$ is SLTSC (Lemma 5.7) and SASC (Lemma 5.12).

####  5.1.1 Analysis of self-concordant metrics for linear constraints

##### Strong self-concordance and symmetry.

We defer the proofs of two lemmas below to §7.4.1. We study SSC and symmetry
of the metrics of the form $A_{x}^{\mathsf{T}}D_{x}A_{x}$ in Lemma 5.4, where
$D_{x}\in\mathbb{R}^{m\times m}$ is a diagonal matrix used to address the
constraints of the form $Ax\geq b$ for $A\in\mathbb{R}^{m\times d}$ and
$b\in\mathbb{R}^{m}$. Specifically, we relate the notions of SSC and symmetry
to well-studied terms in the field of optimization, namely
$\max_{i}\,[\sigma(\sqrt{D_{x}}A_{x})]_{i}/[D_{x}]_{ii}$ and
${\|\mathrm{D}D_{x}[h]\|}_{D_{x}^{-1}}^{2}$.

######  Lemma 5.4.

For $x\in\textup{{int}}(K)$, let
$g(x)=A_{x}^{\mathsf{T}}D_{x}A_{x}\in\mathbb{R}^{d\times d}$ for a diagonal
matrix $0\prec D_{x}\in\mathbb{R}^{m\times m}$.

  * •

For any PSD matrix function $g^{\prime}$ such that $g^{\prime}+g$ is
invertible on the domain,

$\displaystyle{\|(g^{\prime}(x)+g(x))^{-1/2}\mathrm{D}g(x)[h]\,(g^{\prime}(x)+g(x))^{-1/2}\|}_{F}^{2}$
$\displaystyle\qquad\qquad\leq
4\max_{i}\frac{[\sigma(\sqrt{D_{x}}A_{x})]_{i}}{[D_{x}]_{ii}}\cdot{\bigl{(}{\|h\|}_{g(x)}^{2}+\sum_{i=1}^{m}\frac{(\mathrm{D}D_{x}[h])_{ii}^{2}}{[D_{x}]_{ii}}\bigr{)}}\,.$

  * •

$\max_{h:{\|h\|}_{g(x)}=1}{\|A_{x}h\|}_{\infty}={\bigl{(}\max_{i\in[m]}\frac{[\sigma(\sqrt{D_{x}}A_{x})]_{i}}{[D_{x}]_{ii}}\bigr{)}}^{1/2}$.

  * •

$K\cap(2x-K)\subset\mathcal{D}_{g}^{\sqrt{\textup{{Tr}}(D_{x})}}(x)$.

Then for each metric we refer to existing bounds on these terms, estimating
the smallest possible scaling required for SSC and symmetry.

######  Lemma 5.5 (Strong self-concordance and symmetry).

Let $A\in\mathbb{R}^{m\times d}$,
$\Sigma_{x}=\textup{{Diag}}(\sigma(A_{x}))\in\mathbb{R}^{m\times m}$, and
$W_{x}=\textup{{Diag}}(w_{x})\in\mathbb{R}^{m\times m}$ for the
$\ell_{p}$-Lewis weight $w_{x}$ with $p=\mathcal{O}(\log m)$.

  * •

Logarithmic metric: $g(x)=A_{x}^{\mathsf{T}}A_{x}$ with $D_{x}=I_{m}$ is SSC
along $\textup{{row}}(A)$ with $\bar{\nu}=m$.

  * •

Approximate volumetric metric:
$g(x)=40\sqrt{m}A_{x}^{\mathsf{T}}\Sigma_{x}A_{x}$ with
$D_{x}=40\sqrt{m}\Sigma_{x}$ is SSC with $\bar{\nu}=\mathcal{O}(\sqrt{m}d)$.

  * •

Vaidya metric:
$g(x)=22\sqrt{\frac{m}{d}}A_{x}^{\mathsf{T}}{\bigl{(}\Sigma_{x}+\frac{d}{m}I_{m}\bigr{)}}A_{x}$
with $D_{x}=22\sqrt{\frac{m}{d}}{\bigl{(}\Sigma_{x}+\frac{d}{m}I_{m}\bigr{)}}$
is SSC with $\bar{\nu}=\mathcal{O}(\sqrt{md})$.

  * •

Lewis-weight metric: $\exists$ positive constants $c_{1}$ and $c_{2}$ such
that $g(x)=c_{1}(\log m)^{c_{2}}A_{x}^{\mathsf{T}}W_{x}A_{x}$ is SSC and
$\bar{\nu}$-symmetric with $\bar{\nu}=\mathcal{O}^{*}(d)$.

##### Strongly lower trace self-concordance

We show SLTSC of the Vaidya and Lewis-weight metric. Let $g_{2}$ be either
Vaidya or Lewis-weight metric, and $g_{1}$ be an arbitrary PSD matrix function
on $K$ such that $g=g_{1}+g_{2}$ is PD on $\textup{{int}}(K)$. Ensuring
(S)LTSC of the Vaidya or Lewis-weight metrics is challenging, as
$\mathrm{D}^{2}g_{2}[h,h]\succeq 0$ is difficult to verify due to complicated
expressions for $\mathrm{D}^{2}\Sigma_{x}[h,h]$ and
$\mathrm{D}^{2}W_{x}[h,h]$. As for the Vaidya metric, we compute higher-order
derivatives of leverage scores and other pertinent matrices in Lemma B.4,
finding succinct formulas by using algebraic properties of the Hadamard
product. We then show SLTSC of $g_{2}$ using these results (see §7.4.2 for the
proof):

######  Lemma 5.6 (SLTSC of Vaidya).

$\textup{{Tr}}{\bigl{(}g^{-1}\mathrm{D}^{2}g_{2}(x)[h,h]\bigr{)}}\geq-{\|h\|}_{g_{2}(x)}^{2}/2$
for the Vaidya metric $g_{2}$.

For the Lewis-weights metric, analysis is more involved due to numerous terms
appearing in $\mathrm{D}^{2}W_{x}[h,h]$. In order to avoid dealing with each
of the terms, we employ existing bounds on derivatives of $W_{x}$ and other
relevant matrices in §B.3. This approach significantly simplifies the
computation but comes at the cost of an additional scaling of $\sqrt{d}$,
which as far as we can tell might be unavoidable. We refer readers to §7.4.3
for the proof.

######  Lemma 5.7 (SLTSC of Lewis-weight).

$\textup{{Tr}}{\bigl{(}g(x)^{-1}\mathrm{D}^{2}g_{2}(x)[h,h]\bigr{)}}\geq-{\|h\|}_{g_{2}(x)}^{2}$,
where $g_{2}(x)=cA_{x}^{\mathsf{T}}W_{x}A_{x}$ with $c=c_{1}(\log
m)^{c_{2}}\sqrt{d}$ for some constants $c_{1},c_{2}>0$.

##### Strongly average self-concordance.

Typically, (S)ASC is the most challenging property to verify, often requiring
involved analysis in order to establish it _without_ additional scalings.
Since the three metrics are HSC (e.g., see Lemma B.10 for Lewis-weight
metrics), scaling by $d$ leads to SASC by Lemma 4.15. However, for linear
constraints one can still achieve SASC without scaling (or with a smaller
scaling) through more sophisticated concentration techniques.

To sketch this idea, we recall that SASC requires showing that for small
enough $r$

${\|z-x\|}_{g(z)}^{2}-{\|z-x\|}_{g(x)}^{2}\leq 2\varepsilon\frac{r^{2}}{d}\,.$

Taylor’s expansion of ${\|z-x\|}_{g(z)}^{2}$ at $z=x$ up to second-order
necessitates bounds on

$\mathrm{D}g(x)[(z-x)^{\otimes
3}]=\frac{r^{3}}{d^{3/2}}\mathrm{D}g(x)[h^{\otimes
3}]\qquad\text{and}\qquad\mathrm{D}g(x^{\prime})[(z-x)^{\otimes
4}]=\frac{r^{4}}{d^{2}}\mathrm{D}^{2}g(x^{\prime})[h^{\otimes 4}]\,,$

for some $x^{\prime}\in[x,z]$ and $h\sim\mathcal{N}(0,I_{d})$. Observe that
the first-order term $P(h):=\frac{r^{3}}{d^{3/2}}\mathrm{D}g(x)[h^{\otimes
3}]$ is a Gaussian polynomial in $h$, and this is where we can invoke the
following concentration phenomenon:

######  Lemma 5.8 (Concentration of Gaussian polynomials).

For $d\geq 1$, let $P:\mathbb{R}^{d}\to\mathbb{R}$ be a polynomial of degree
$n$. For any $t\geq(2e)^{n/2}$,

$\mathbb{P}_{h\sim\mathcal{N}(0,I_{d})}{\Bigl{[}|P(h)|\geq
t\sqrt{\mathbb{E}[P(h)^{2}]}\Bigr{]}}\leq\exp{\bigl{(}-\frac{n}{2e}\,t^{2/n}\bigr{)}}\,.$

This concentration inequality necessitates bounding $\mathbb{E}[P(h)^{2}]$,
and this is where Stein’s lemma comes into play:

######  Lemma 5.9.

For $h=(h_{1},\dots,h_{d})\sim\mathcal{N}(0,I_{d})$, it holds that
$\mathbb{E}[h_{i}f(h)]=\mathbb{E}[\partial_{i}f(h)]$.

Unlike the first-order term, the second-order term is _not_ a Gaussian
polynomial due to $x^{\prime}$ depending on $z$. To address this issue, we
derive an upper bound (in absolute value) of the quadratic form. Using
coordinate-wise closeness of slacks, leverage scores, and Lewis weights at two
nearby points, we replace every value estimated at $z$ by those at $x$,
removing dependence on $z$ in the quadratic bound. The resulting quadratic
bound is now a Gaussian polynomial, so we follow the same proof approach as
with the first-order term.

This approach was used by Sachdeva and Vishnoi (2016) for ASC of log-barriers
and by Chen et al. (2018) for that of Vaidya and Lewis-weight metrics. We
further extend this approach to achieve SASC of those metrics, going beyond
ASC.

######  Lemma 5.10 (SASC of logarithmic barrier).

$g(x)=\nabla^{2}\phi_{\log}(x)=A_{x}^{\mathsf{T}}A_{x}$ is SASC.

See §7.4.4 for the proof.

######  Lemma 5.11 (SASC of Vaidya metric).

$g(x)=\mathcal{O}{\bigl{(}\sqrt{\frac{m}{d}}\bigr{)}}\,A_{x}^{\mathsf{T}}(\Sigma_{x}+\frac{d}{m}I_{m})A_{x}$
is SASC.

See §7.4.4 for the proof.

######  Lemma 5.12 (SASC of Lewis-weight metric).

There exists constants $c_{1}$ and $c_{2}$ such that
$g(x)=c_{1}\sqrt{d}\log^{c_{2}}m\,A_{x}^{\mathsf{T}}W_{x}A_{x}=\mathcal{O}^{*}(\sqrt{d})\,A_{x}^{\mathsf{T}}W_{x}A_{x}$
is SASC.

See §7.4.4 for the proof.

###  5.2 Quadratic potentials and constraints

Suppose that in ($\mathsf{redLC}$) we have either
$f_{i}(x),\,h_{j}(x)={\|x-\mu\|}_{\Sigma}^{2}$ or
$\frac{1}{2}x^{\mathsf{T}}Qx+p^{\mathsf{T}}x+l$ for $\mu,p\in\mathbb{R}^{d}$,
$\Sigma\in\mathbb{S}_{++}^{d}$, and $0\neq Q\in\mathbb{S}_{+}^{d}$.

##### Quadratic constraint.

Consider a second-order region given by
$K=\\{x\in\mathbb{R}^{d}:\frac{1}{2}x^{\mathsf{T}}Qx+p^{\mathsf{T}}x+l\leq
0\\}$. Nesterov and Nemirovskii (1994) shows that $\phi:=-\log f$ is an
$1$-self-concordant barrier for $K$, when
$f(x)=-\frac{1}{2}{\|x-\mu\|}_{\Sigma}^{2}$ or
$-(\frac{1}{2}x^{\mathsf{T}}Qx+p^{\mathsf{T}}x+l)$. Since
$\bar{\nu}=\mathcal{O}(\nu^{2})$ for a self-concordant barrier due to Lemma
4.8, $\phi$ is $\mathcal{O}(1)$-symmetric. In case we consider
${\|x-\mu\|}_{\Sigma}^{2}$, the trivial scaling by dimension $d$ implies that
$d\phi$ is SSC and $\mathcal{O}(d)$-symmetric.

Moreover, $d\phi$ is SASC by Lemma 4.15 by HSC of $\phi$. For HSC of $\phi$,
we develop a handy tool for checking HSC. See §7.4.5 for the proof.

######  Lemma 5.13.

For a real-valued function $f$ on $K\subset\mathbb{R}^{d}$, let $\psi=-\log f$
be a $\nu$-self-concordant barrier for $K$. Then,

$|\mathrm{D}^{4}\psi(x)[h^{\otimes
4}]|\lesssim\nu^{2}{\|h\|}_{\nabla^{2}\psi(x)}^{2}+\big{|}\frac{\mathrm{D}^{4}f(x)[h^{\otimes
4}]}{f(x)}\big{|}\,.$

Using this tool, we can study properties of the barrier for the quadratic
constraints. We provide the proof in §7.4.5.

######  Lemma 5.14 (Quadratic constraint).

For a closed convex
$K=\\{x\in\mathbb{R}^{d}:\frac{1}{2}x^{\mathsf{T}}Qx+p^{\mathsf{T}}x+l\leq
0\\}$ with $p\in\mathbb{R}^{d}$ and $0\neq Q\in\mathbb{S}_{+}^{d}$, let
$\phi(x)=-\log(-l-p^{\mathsf{T}}x-\frac{1}{2}x^{\mathsf{T}}Qx)$ and
$g=d\,\nabla^{2}\phi$.

  * •

$\nu,\,\bar{\nu}=\mathcal{O}(d)$.

  * •

SSC when $Q\succ 0$, and SASC.

  * •

$\mathrm{D}^{2}g(x)[h,h]\succeq 0$ for any $x\in\textup{{int}}(K)$ and
$h\in\mathbb{R}^{d}$ (so SLTSC).

##### Gaussian distribution ($f(x)=\frac{1}{2}{\|x-\mu\|}_{\Sigma}^{2}$).

Suppose the quadratic term $f(x)=\frac{1}{2}{\|x-\mu\|}_{\Sigma}^{2}$ appears
in a potential of a target distribution. Then its epigraph is

$\\{(x,t)\in\mathbb{R}^{d+1}:\frac{1}{2}{\|x-\mu\|}_{\Sigma}^{2}-t\leq
0\\}\,,$

and clearly $q(x,t)=\frac{1}{2}{\|x-\mu\|}_{\Sigma}^{2}-t$ is a quadratic
function in $(x,t)$. Hence, this level set admits an $1$-self-concordant
barrier

$\phi(x,t)=-\log(t-\frac{1}{2}{\|x-\mu\|}_{\Sigma}^{2})\,.$

Our earlier discussion immediately leads to the following result:

######  Lemma 5.15 (Quadratic potential).

Consider a closed convex $K=\\{(x,t):\frac{1}{2}{\|x-\mu\|}_{\Sigma}^{2}\leq
t\\}$ with $\mu\in\mathbb{R}^{d}$ and $\Sigma\in\mathbb{S}_{++}^{d}$, and let
$\phi(x)=-\log(t-\frac{1}{2}{\|x-\mu\|}_{\Sigma}^{2})$ and
$g=d\,\nabla^{2}\phi$.

  * •

$\nu_{g},\,\bar{\nu}_{g}=\mathcal{O}(d)$.

  * •

SSC and SASC.

  * •

$\mathrm{D}^{2}g(x,t)[h,h]\succeq 0$ for any $(x,t)\in\textup{{int}}(K)$ and
$h\in\mathbb{R}^{d+1}$.

##### Second-order cone ($f(x)=\frac{1}{2}{\|x-\mu\|}_{\Sigma}$).

It is common that a potential includes a non-smooth term like ${\|Ax-b\|}_{2}$
in many applications, and we can handle such potentials via our framework.
Nesterov and Nemirovskii (1994, Lemma 4.3.3) shows that

$\phi(x,t)=-\log(t^{2}-{\|x\|}^{2})$

is a $2$-self-concordant for a level set
$K=\\{(x,t)\in\mathbb{R}^{d}\times\mathbb{R}:{\|x\|}_{2}\leq t\\}$ (here we
may assume that $\mu=0$ and $\Sigma=I$ due to Lemma 4.18). This level set is
called a _second-order cone_ or Lorentz cone.

Applying Lemma 5.13 to $f(x,t)=t^{2}-{\|x\|}^{2}$ with $\nu=2$, we immediately
show HSC of $\phi$. Thus, $d\phi$ satisfies SLTSC and SASC by Lemma 4.13 and
Lemma 4.15, respectively.

######  Lemma 5.16 (Second-order cone).

Consider a closed convex $K=\\{(x,t):{\|x-\mu\|}_{\Sigma}\leq t\\}$ with
$\mu\in\mathbb{R}^{d}$ and $\Sigma\in\mathbb{S}_{++}^{d}$, and let
$\phi(x,t)=-\log(t^{2}-{\|x-\mu\|}_{\Sigma}^{2})$ and $g=d\,\nabla^{2}\phi$.

  * •

$\nu_{g},\,\bar{\nu}_{g}=\mathcal{O}(d)$.

  * •

SSC, SASC, and SLTSC.

###  5.3 PSD cone

The function $\phi(X)=-\log\det X$ serves as an $d$-self-concordant barrier
for the PSD cone $\mathbb{S}_{+}^{d}$. While achieving self-concordance does
not require additional scaling, it turns out that SSC requires a scaling of
$\Theta(d)$. Notably, this scaling is less than the trivial dimension-based
scaling of $d_{s}:=d(d+1)/2$. Also, direct computation leads to
$\mathrm{D}^{4}\phi(X)[H,H]\succeq 0$ (so SLTSC).

As $\phi$ is HSC, scaling by $d_{s}$ ensures SASC. However, we can achieve ASC
with a smaller scaling by $\mathcal{O}(d)$ via the random matrix theory.

######  Lemma 5.17 (PSD cone).

On a closed convex $K=\mathbb{S}_{+}^{d}$, let $\phi(X)=-\log\det X$ and
define $g=d\,\nabla^{2}\phi$.

  * •

$\nu=d^{2}$ (Nesterov and Nemirovskii (1994)) and $\bar{\nu}=d^{2}$ (Lemma
5.21).

  * •

SSC (Corollary 5.24).

  * •

$\mathrm{D}^{2}g(X)[H,H]\succeq 0$ for any $X\in\textup{{int}}(K)$ and
$H\in\mathbb{S}^{d}$ (Lemma 5.25).

  * •

ASC (Lemma 5.27), and $d_{s}\,\nabla^{2}\phi$ is SASC.

####  5.3.1 Formalism via matrix-vector transformations

In analyzing $\phi$, we work in $\mathbb{R}^{d_{s}}=\mathbb{R}^{d(d+1)/2}$ and
$\mathbb{S}^{d}$ simultaneously in the sequel, moving back and forth between
them implicitly. We justify this identification as follows.

##### Measure on $\mathbb{S}^{d}$.

We can define and work with the Lebesgue measure on $\mathbb{S}^{d}$ by
identifying it with the Lebesgue measure on $\mathbb{R}^{d_{s}}$, where each
component in the Lebesgue measure on $\mathbb{S}^{d}$ corresponds to each
entry in the upper triangular part. Hence, with the Lebesgue measure
$\mathrm{d}X$ on $\mathbb{S}^{d}$ it is straightforward to define a
probability distribution on $\mathbb{S}^{d}$ whose probability density
function with respect to $\mathrm{d}X$ is proportional to $\exp(-f)$ for a
function $f:\mathbb{S}^{d}\to\mathbb{R}$. For instance, the uniform
distribution over a region corresponds to $f$ being constant in the region and
infinity outside of the region, and an exponential distribution to
$f(X)=\langle C,X\rangle=\textup{{Tr}}(C^{\mathsf{T}}X)$ for
$C\in\mathbb{S}^{d}$.

##### Directional derivatives.

A function $\phi:\mathbb{S}^{d}\to\mathbb{R}$ induces its counterpart
$\psi:\mathbb{R}^{d_{s}}\to\mathbb{R}$ defined by $\psi(x)=\phi(X)$ for
$x:=\textup{{svec}}(X)$. For symmetric matrices $\\{H_{i}\\}_{i\leq k}$, the
$k$-th directional derivative of $\phi$ in directions $H_{1},\dots,H_{k}$ is

$\mathrm{D}^{k}\phi(X)[H_{1},\cdots,H_{k}]\stackrel{{\scriptstyle\mathrm{{\scriptscriptstyle
def}}}}{{=}}\frac{\mathrm{d}^{k}}{\mathrm{d}t_{k}\cdots\mathrm{d}t_{1}}\phi{\Bigl{(}X+\sum_{i=1}^{k}t_{i}H_{i}\Bigr{)}}\bigg{|}_{t_{1},\dots,t_{k}=0}\,.$

For $h_{i}:=\textup{{svec}}(H_{i})$, it follows that
$\phi(X+\sum_{i=1}^{k}t_{i}H_{i})=\psi(x+\sum_{i=1}^{k}t_{i}h_{i})$ and thus

$\mathrm{D}^{k}\phi(X)[H_{1},\cdots,H_{k}]=\mathrm{D}^{k}\psi(x)[h_{1},\cdots,h_{k}]\,.$

With this identification in hand, since the notion of (symmetric or strong)
self-concordance is formulated in terms of directional derivatives, we can
deal with both representations without having to specify one of them.

##### Important operators.

We introduce three linear operators that enable us to make smooth transitions
between $\mathbb{S}^{d}$ and $\mathbb{R}^{d_{s}}$.

######  Definition 5.18 (Magnus and Neudecker (1980)).

Let $E_{ij}=e_{i}e_{j}^{\mathsf{T}}\in\mathbb{R}^{d\times d}$ be the matrix
with a single $1$ in the $(i,j)$ position and zeros elsewhere.

  * •

$M:\mathbb{R}^{d_{s}}\to\mathbb{R}^{d^{2}}$ is the linear operator that maps
$\textup{{svec}}(\cdot)$ to $\textup{{vec}}(\cdot)$ (i.e.,
$M\circ\textup{{svec}}=\textup{{vec}}$). It can be written as $M=\sum_{i\geq
j}\textup{{vec}}(T_{ij})u_{ij}^{\mathsf{T}}$, where
$T_{ij}\in\mathbb{R}^{d\times d}$ has all zero entries except for $1$ at
$(i,j)$ and $(j,i)$ positions (i.e., $T_{ij}=E_{ij}+E_{ji}$ if $i\neq j$ and
$E_{ij}$ if $i=j$), and $u_{ij}=\textup{{svec}}(E_{ij})$.

  * •

$N:\mathbb{R}^{d^{2}}\to\mathbb{R}^{d^{2}}$ is the linear operator that maps
$\textup{{vec}}(A)$ to
$\textup{{vec}}{\bigl{(}\frac{1}{2}(A+A^{\mathsf{T}})\bigr{)}}$ for a matrix
$A\in\mathbb{R}^{d\times d}$.

  * •

$L:\mathbb{R}^{d_{s}}\to\mathbb{R}^{d^{2}}$ is the linear operator that maps
$\textup{{vec}}(A)$ to $\textup{{svec}}(A)$ for a matrix
$A\in\mathbb{R}^{d\times d}$. It can be written as $L=\sum_{i\geq
j}u_{ij}\textup{{vec}}(E_{ij})^{\mathsf{T}}$.

######  Lemma 5.19 (Magnus and Neudecker (1980)).

Let $M,N,L$ be matrices in Definition 5.18.

  * •

(Lemma 2.1) $N=N^{\mathsf{T}}=N^{2}$ and $N(A\otimes A)=(A\otimes A)N$ for any
$d\times d$ matrix $A$.

  * •

(Lemma 3.5) $MLN=N$.

####  5.3.2 Analysis of a self-concordant metric for the PSD cone

We first examine properties of the metric defined by the Hessian of self-
concordant barrier $\phi(X)=-\log\det X$ (see Nesterov (2003, Theorem 4.3.3)
for self-concordance). In this case, its Hessian and inverse have clean
formulas.

######  Proposition 5.20.

Let
$\nabla_{X}^{2}\phi(X)=-\nabla_{x}^{2}\log\det(\textup{{svec}}^{-1}(x))\in\mathbb{R}^{d_{s}\times
d_{s}}$ for $X\in\mathbb{S}_{+}^{d}$. Then,

$\displaystyle\nabla^{2}\phi(X)$ $\displaystyle=M^{\mathsf{T}}(X^{-1}\otimes
X^{-1})M=M^{\mathsf{T}}(X\otimes X)^{-1}M\,,$
$\displaystyle{\bigl{(}\nabla^{2}\phi(X)\bigr{)}}^{-1}$
$\displaystyle=M^{\dagger}(X\otimes
X){\bigl{(}M^{\dagger}\bigr{)}}^{\mathsf{T}}=LN(X\otimes X)NL^{\mathsf{T}}\,,$

where
$M^{\dagger}=(M^{\mathsf{T}}M)^{-1}M^{\mathsf{T}}\in\mathbb{R}^{d_{s}\times
d^{2}}$ is the Moore-Penrose inverse of $M\in\mathbb{R}^{d^{2}\times d_{s}}$.

We defer the proof to Appendix A.2. We remark that as an immediate corollary
to this, the local norm of $h\in\mathbb{R}^{d_{s}}$ with metric
$\nabla^{2}\phi(X)$ is

${\|h\|}_{X}^{2}=\textup{{svec}}(H)^{\mathsf{T}}M^{\mathsf{T}}(X^{-1}\otimes
X^{-1})M\textup{{svec}}(H)\underset{\text{(i)}}{=}\textup{{Tr}}(HX^{-1}HX^{-1})\eqqcolon{\|H\|}_{X}^{2}\,,$

where (i) follows from $\textup{{vec}}=M\circ\textup{{svec}}$ (Definition
5.18) and
$\textup{{Tr}}(DB^{\mathsf{T}}A^{\mathsf{T}}C)=\textup{{vec}}(A)^{\mathsf{T}}(B\otimes
C)\textup{{vec}}(D)$ (Lemma A.1).

##### Symmetry.

######  Lemma 5.21 ($\bar{\nu}$-symmetry).

For $X\in K=\mathbb{S}_{+}^{d}$, the barrier $\phi(X)=-\log\det X$ is
$d$-symmetric.

###### Proof.

For $X\in K$, pick any $Y\in K\cap(2X-K)$, and define a symmetric matrix
$H:=Y-X$. Since $Y\in K$ and $2X-Y\in K$, we have $X+H\in K$ and $X-H\in K$.
Thus,

$-I\preceq X^{-1/2}HX^{-1/2}\preceq I\,,$

and the magnitude of each eigenvalue $\\{\lambda_{i}\\}_{i=1}^{d}$ of
$X^{-1/2}HX^{-1/2}$ is bounded by $1$. Hence,

${\|H\|}_{X}^{2}=\textup{{Tr}}(X^{-1}HX^{-1}H)={\|X^{-1/2}HX^{-1/2}\|}_{F}^{2}\leq\sum_{i=1}^{d}\lambda_{i}^{2}\leq
d\,.\qed$

##### Convexity of log-determinant of Hessian and SSC.

Next, the convexity of the log-determinant of $\nabla^{2}\phi$ can be checked
via properties of Kronecker products. See §7.4.6 for the proof.

######  Proposition 5.22 (Convexity of log-determinant of Hessian).

$\log\det(\nabla^{2}\phi(\cdot))$ is convex.

We move onto SSC of $d\phi(X)$.

######  Lemma 5.23.

For
$\psi_{X}:=\sup_{H\in\mathbb{S}^{d}}{\|(\nabla^{2}\phi(X))^{-1/2}\mathrm{D}^{3}\phi(X)[H]\,(\nabla^{2}\phi(X))^{-1/2}\|}_{F}/{\|H\|}_{X}$,
we have

$\sqrt{2(d+1)}\leq\psi_{X}\leq 2\sqrt{d}\,.$

We present the proof in §7.4.6. This result informs us of the best possible
scaling of $\phi$ that ensures SSC. Recall that if $g$ satisfies
${\|g^{-1/2}\mathrm{D}g[h]g^{-1/2}\|}_{F}\leq 2\alpha{\|h\|}_{g}$ for
$\alpha>0$, then $\alpha^{2}g$ is SSC. We remark that the scaling of $d$ is
obviously better than the trivial scaling of $d_{s}=\Theta(d^{2})$.

######  Corollary 5.24 (Strong self-concordance).

A function $d\phi$ is a strongly self-concordant barrier for
$\mathbb{S}_{+}^{d}$. Moreover, the scaling factor of $d$ cannot be further
improved.

##### Strongly lower trace self-concordance.

SLTSC of $\phi$ can be easily checked by noting
$g(X)[H,H]=\textup{{Tr}}(X^{-1}HX^{-1}H)$ and using the chain rule. See the
details in §7.4.7.

######  Lemma 5.25 (SLTSC).

$\mathrm{D}^{2}g(X)[H,H]\succeq 0$ for any $X\in\textup{{int}}(K)$ and
$H\in\mathbb{S}^{d}$.

##### Average self-concordance.

In establishing ASC, we find an interesting connection to a _Gaussian
orthogonal ensemble_ (GOE), one of the main objects studied in the random
matrix theory. We prove the following lemmas and explain challenges when
extending our arguments to SASC in §7.4.8.

######  Lemma 5.26.

For $d_{s}=\frac{d(d+1)}{2}$ and
$\textup{{svec}}(H)\sim\mathcal{N}{\bigl{(}0,\frac{r^{2}}{d_{s}}g(X)^{-1}\bigr{)}}$,
$\frac{\sqrt{d_{s}d}}{r}X^{-1/2}HX^{-1/2}$ is a GOE.

######  Lemma 5.27 (ASC).

$-d\,\log\det X$ is ASC.

###  5.4 Logarithm, exponential, entropy, and $\ell_{p}$-norm (power function)

##### Logarithm in potentials.

Consider $Q_{1}=\\{(x,t)\in\mathbb{R}^{2}:-\log x\leq t,x>0\\}$. As
$f(\cdot)=-\log(\cdot)$ is convex on $\mathbb{R}_{+}$ and satisfies the
condition in Lemma 4.32 with $\beta=2$ and $\gamma=6$,

$F(x,t)=-\log(t+\log x)-36\log x$

is a highly $37$-self concordant barrier for $Q_{1}$. Therefore, $2F$ is SSC
and SLTSC with $\bar{\nu}=\mathcal{O}(1)$.

######  Lemma 5.28 (Logarithm).

Consider the direct product of level sets

$K=\prod_{i=1}^{d}\\{(x_{i},t_{i})\in\mathbb{R}^{2}:-\log x_{i}\leq
t_{i},\,x_{i}>0\\}\,,$

and let $\phi(x,t)=-\sum_{i=1}^{d}{\bigl{(}\log(t_{i}+\log x_{i})+36\log
x_{i}\bigr{)}}$ and $g=2\nabla^{2}\phi$.

  * •

$\nu,\,\bar{\nu}=\mathcal{O}(d)$.

  * •

SSC and SLTSC.

  * •

$d\,\nabla^{2}\phi$ is SASC.

###### Proof.

For $i\in[d]$, let $Q_{i}=\\{(x_{i},t_{i})\in\mathbb{R}^{2}:-\log x_{i}\leq
t_{i},\,y_{i}>0\\}$ and $F_{i}(x_{i},t_{i})$ be the self-concordant barrier
above. Note that $2F_{i}$ is SSC and SLTSC. By Lemma 4.25 and 4.26, the
Hessian of $F(x,t):=2\sum_{i=1}^{d}F_{i}(x_{i},t_{i})$ is SSC and SLTSC. The
last item on SASC follows from Lemma 4.15. ∎

##### Exponent in potentials.

Consider $Q_{2}=\\{(x,t)\in\mathbb{R}^{2}:e^{x}\leq
t\\}=\\{(x,t)\in\mathbb{R}^{2}:t>0,\,x\leq\log t\\}$. As $f(t)=\log t$ is
concave and satisfies the condition in Lemma 4.31 with $\beta=2$ and
$\gamma=6$,

$F(x,t)=-\log(\log t-x)-36\log t$

is a highly $37$-self concordant barrier for $Q_{2}$. Therefore, $2F$ is SSC
and SLTSC with $\bar{\nu}=\mathcal{O}(1)$.

######  Lemma 5.29 (Exponential).

Consider the direct product of level sets

$K=\prod_{i=1}^{d}\\{x_{i},t_{i})\in\mathbb{R}^{2}:\exp(x_{i})\leq
t_{i}\\}\,,$

and let $\phi(x,t)=-\sum_{i=1}^{d}(\log(\log t_{i}-x_{i})+36\log t_{i})$ and
$g=2\nabla^{2}\phi$.

  * •

$\nu,\,\bar{\nu}=\mathcal{O}(d)$.

  * •

SSC and SLTSC.

  * •

$d\,\nabla^{2}\phi$ is SASC.

###### Proof.

For $i\in[d]$, let $Q_{i}=\\{(x_{i},t_{i})\in\mathbb{R}^{2}:e^{x_{i}}\leq
t_{i}\\}$ and $F_{i}(x_{i},t_{i})$ be the self-concordant barrier above. Note
that $2F_{i}$ is SSC and SLTSC. By Lemma 4.25 and 4.26, the Hessian of
$F(x,t):=2\sum_{i=1}^{d}F_{i}(x_{i},t_{i})$ is SSC and SLTSC. The last item on
SASC follows from Lemma 4.15. ∎

##### Entropy in potentials.

Consider $Q_{3}=\\{(x,t)\in\mathbb{R}^{2}:x\geq 0,\,t\geq x\log x\\}$. Note
that $f(x)=x\log x$ is convex on $\\{x>0\\}$ and satisfies the condition in
Lemma 4.32 with $\beta=1$ and $\gamma=2$. Hence,

$F(x,t)=-\log(t-x\log x)-36\log x$

is a highly $5$-self concordant barrier for $Q_{3}$. Therefore, $2F$ is SSC
and SLTSC with $\bar{\nu}=\mathcal{O}(1)$.

######  Lemma 5.30 (Entropy).

Consider the direct product of level sets

$K=\prod_{i=1}^{d}\\{(x_{i},t_{i})\in\mathbb{R}^{2}:x_{i}\geq 0,\,t_{i}\geq
x_{i}\log x_{i}\\}\,,$

and let $\phi(x,t)=-\sum_{i=1}^{d}{\bigl{(}\log(t_{i}-x_{i}\log x_{i})+36\log
x_{i}\bigr{)}}$ and $g=2\nabla^{2}\phi$.

  * •

$\nu,\,\bar{\nu}=\mathcal{O}(d)$.

  * •

SSC and SLTSC.

  * •

$d\,\nabla^{2}\phi$ is SASC.

###### Proof.

For $i\in[d]$, let $Q_{i}=\\{(x_{i},t_{i})\in\mathbb{R}^{2}:x_{i}\geq
0,\,t_{i}\geq x_{i}\log x_{i}\\}$ and $F_{i}(x_{i},t_{i})$ be the self-
concordant barrier above. Note that $2F_{i}$ is SSC and SLTSC. By Lemma 4.25
and 4.26, the Hessian of $F(x,t):=2\sum_{i=1}^{d}F_{i}(x_{i},t_{i})$ is SSC
and SLTSC. The last item on SASC follows from Lemma 4.15. ∎

#####  $\ell_{p}$-norm (power function).

We start with the power functions. For $p\geq 1$, consider
$Q_{4}=\\{(x,t)\in\mathbb{R}^{2}:t\geq\max(0,x)^{p}\\}=\\{(x,t)\in\mathbb{R}^{2}:t\geq
0,\,x\leq t^{1/p}\\}$. Note that $f(t)=t^{1/p}$ is concave on $t>0$ and
satisfies the condition in Lemma 4.31 with $\beta=2$ and $\gamma=6$. Hence,

$F_{4}(x,t)=-\log(t^{1/p}-x)-36\log t$

is a highly $37$-self-concordant barrier for $Q_{4}$. Similarly,
$F_{5}(t,x)=-\log(t^{1/p}+x)-36\log t$ is a highly $37$-self concordant
barrier for the convex set
$Q_{5}=\\{(x,t)\in\mathbb{R}^{2}:t\geq\max(0,-x)^{p}\\}$. Since the convex set
$Q_{6}=\\{(x,t)\in\mathbb{R}^{2}:t\geq|x|^{p}\\}$ is equal to $Q_{4}\cap
Q_{5}$, the sum of $F_{4}+F_{5}$, which is

$F_{6}(x,t)=-\log(t^{2/p}-x^{2})-72\log t$

is a highly $72$-self-concordant barrier for $Q_{6}$. Hence, $2F$ is SSC and
SLTSC with $\bar{\nu}=\mathcal{O}(1)$.

######  Lemma 5.31 ($\ell_{p}$-norm).

Consider the direct product of level sets
$K=\prod_{i=1}^{d}\\{(x_{i},t_{i})\in\mathbb{R}^{2}:\left\lvert
x_{i}\right\rvert^{p}\leq t_{i}\\}$, and let
$\phi(x,t)=-\sum_{i=1}^{d}{\bigl{(}\log(t_{i}^{2/p}-x_{i}^{2})+72\log
t_{i}\bigr{)}}$ and $g=2\nabla^{2}\phi$.

  * •

$\nu,\,\bar{\nu}=\mathcal{O}(d)$.

  * •

SSC and SLTSC.

  * •

$d\,\nabla^{2}\phi$ is SASC.

###### Proof.

Consider a highly $72$-self-concordant barrier $F_{i}$ above for
$\\{(x_{i},t_{i}):|x_{i}|^{p}\leq t_{i}\\}$ for $i\in[d]$. Note that $2F_{i}$
is SSC and SLTSC. By Lemma 4.25 and 4.26, the Hessian of
$F(x,t):=2\sum_{i=1}^{d}F_{i}(x_{i},t_{i})$ is SSC and SLTSC. The last item on
SASC follows from Lemma 4.15. ∎

##  6 Examples

For given constraints and epigraphs, combining metrics for them (according to
the self-concordance theory for sampling developed in §4) and employing
$\mathsf{GCDW}$ with the combined metric lead to a poly-time mixing sampling
algorithm. Compared to the state-of-the-art poly-time mixing algorithm, the
$\mathsf{Ball\ walk}$, $\mathsf{GCDW}$ offers several advantages. First, it
does not require any preprocessing (e.g., rounding) due to affine invariance.
Also, it achieves faster mixing by leveraging inherent geometric information
in sampling problems.

The per-step complexity of $\mathsf{Dikin\ walks}$, however, is in general
higher than that of the $\mathsf{Ball\ walk}$. The primary computational
bottleneck lies in computing the inverse of a local metric. Nevertheless,
efficient implementation of inverse maintenance can significantly reduce the
per-step complexity, improving the total complexity ($\\#\,$iterations needed
for mixing times the per-step complexity).

In this section, we illustrate how our framework recovers theoretical
guarantees of previous work on $\mathsf{Dikin\ walks}$ for uniform sampling
and extends beyond uniform sampling. In particular, we show that
$\mathsf{GCDW}$ is a poly-time mixing algorithm capable of sampling uniform,
exponential, or Gaussian distributions on second-order cones or truncated PSD
cones. Additionally, we illustrate an efficient per-step implementation that
yields a faster total complexity when compared to general-purpose samplers
such as the $\mathsf{Ball\ walk}$.

###  6.1 Polytope sampling

Consider a set of linear constraints given by $K=\\{x\in\mathbb{R}^{d}:Ax\geq
b\\}$ with $A\in\mathbb{R}^{m\times d}$ and $b\in\mathbb{R}^{m}$.

##### Uniform sampling.

Kannan and Narayanan (2012) first studied the $\mathsf{Dikin\ walk}$ for
uniformly sampling a polytope, where a local metric is set to be the Hessian
of the logarithmic barrier,
$g=\nabla^{2}\phi_{\textsf{log}}=A_{(\cdot)}^{\mathsf{T}}A_{(\cdot)}$. They
showed that the $\mathsf{Dikin\ walk}$ with the log-barrier mixes in
$\mathcal{O}{\bigl{(}md\log\frac{M}{\varepsilon}\bigr{)}}$ iterations with a
warmness parameter $M$. An immediate consequence of our work is that
$\mathsf{GCDW}$ achieves the mixing time of $\widetilde{\mathcal{O}}(md)$
_without a warmness assumption_ , as $\bar{\nu},\nu=m$ and $g$ is SSC, LTSC,
and ASC by Lemma 5.1.

Chen et al. (2018) introduced the Vaidya walk and the Approximate John walk,
which are essentially $\mathsf{Dikin\ walks}$ with the Vaidya metric
$\nabla^{2}\phi_{\textsf{Vaidya}}$ and a version of the Lewis-weight metric
$\sqrt{d}\,\nabla^{2}\phi_{\textsf{Lw}}$. Their work showed that both walks
achieves mixing times of
$\mathcal{O}{\bigl{(}\sqrt{m}d^{3/2}\log\frac{M}{\varepsilon}\bigr{)}}$ and
$\mathcal{O}{\bigl{(}d^{5/2}\log^{\mathcal{O}(1)}m\,\log\frac{M}{\varepsilon}\bigr{)}}$,
respectively. Building upon our analysis of the Vaidya metric and Lewis-weight
metric in Lemma 5.2 and 5.3, we find that $\mathsf{GCDW}$ with these metrics
achieves the same mixing but without any warmness assumption.

We note that for the same task the $\mathsf{Ball\ walk}$ without a warm start
requires $\widetilde{\mathcal{O}}(d^{3})$ membership queries due to Kannan et
al. (1997); Jia et al. (2021). Given that a membership query involves
$\mathcal{O}(md)$ arithmetic operations, the total complexity of the
$\mathsf{Ball\ walk}$ is $\widetilde{\mathcal{O}}(md^{4})$. In contrast, the
per-step of the $\mathsf{Dikin\ walk}$ with the log-barrier can be run in
$\mathcal{O}(md^{\omega-1})$ operations through the fast matrix
multiplication, so the total number of arithmetic operations is
$\widetilde{\mathcal{O}}(m^{2}d^{\omega})$. Thus, for $m$ close to $d$
$\mathsf{GCDW}$ is provably faster than the $\mathsf{Ball\ walk}$. When an
efficient inverse maintenance proposed in Laddha et al. (2020) is employed,
the per-step complexity can be improved to
$\mathcal{O}(d^{2}+\textup{{nnz}}(A))=\mathcal{O}(md)$. In such cases
$\mathsf{GCDW}$ is faster in a broader range of $m$. In particular, if $A$ is
as sparse as $\textup{{nnz}}(A)=\mathcal{O}(d^{2})$, then $\mathsf{GCDW}$ is
always faster than the $\mathsf{Ball\ walk}$. Moreover, $\mathsf{GCDW}$ with
the Lewis-weight metric mixes in $\widetilde{\mathcal{O}}(d^{2.5})$ steps with
the per-step complexity of $\widetilde{\mathcal{O}}(md^{\omega-1})$, so it is
always faster than the $\mathsf{Ball\ walk}$ for any $m$.

##### Exponential and Gaussian sampling.

The current mixing bound of the $\mathsf{Ball\ walk}$ for general log-concave
sampling is $\widetilde{\mathcal{O}}(d^{4})$ due to Lovász and Vempala (2007).
On the other hand, the $\mathsf{Dikin\ walk}$ employed with any metric above
for exponential sampling converges in the same iterations as the
$\mathsf{Dikin\ walk}$ for uniform sampling. Since only difference between two
sapling is the additional term of $\exp{\bigl{(}-(f(z)-f(x))\bigr{)}}$ in the
Metropolis filter, the fast implementation techniques mentioned earlier can be
applied to the context of exponential sampling. As a result, for the
exponential sampling each of the $\mathsf{Dikin\ walks}$ described above
surpasses the $\mathsf{Ball\ walk}$ by a larger margin.

For Gaussian sampling over a polytope, we first reduce it to the exponential
sampling as in ($\mathsf{redLC}$): for $y=(x,t)\in\mathbb{R}^{d+1}$

sample $\displaystyle y\sim\tilde{\pi}\propto\exp(-t)$ s.t. $\displaystyle
Ax\geq b,\ \frac{1}{2}{\|x-\mu\|}_{\Sigma}^{2}\leq t\,.$

According to our theory, it is natural to use the metric given by

$g(x,t)=2\left[\begin{array}[]{cc}\nabla^{2}_{x}\phi_{\text{log}}(x)\\\
&0\end{array}\right]+2(d+1)\,\nabla^{2}_{(x,t)}\phi_{\text{Gauss}}(x,t)\,,$

which is ${\bigl{(}\mathcal{O}(m+d),\mathcal{O}(m+d)\bigr{)}}$-Dikin-amenable
due to Lemma 5.15. Thus, $\mathsf{GCDW}$ needs
$\widetilde{\mathcal{O}}(d(m+d))$ iterations of the $\mathsf{Dikin\ walk}$. We
note that the log-barrier can be replaced by the Vaidya or Lewis-weight
metrics, and in such cases one can obtain provable guarantees on the mixing
time by computing $\nu$ and $\bar{\nu}$, referring to §5 or Table 1.

###  6.2 Second-order cone sampling

We consider a region given by ${\|x-\mu\|}_{\Sigma}\leq t$ and
$A\left[\begin{array}[]{cc}x&t\end{array}\right]^{\mathsf{T}}\leq b$ for
$A\in\mathbb{R}^{m\times(d+1)},b\in\mathbb{R}^{m},$ $\mu\in\mathbb{R}^{d}$,
and $\Sigma\in\mathbb{S}_{++}^{d}$.

##### Uniform and exponential sampling.

In this case, our self-concordance theory suggests using

$\nabla^{2}(2\sqrt{d+1}\phi_{\text{Lw}}+2(d+1)\phi_{\text{SOC}})\quad\text{or}\quad\nabla^{2}(2\phi_{*}+2(d+1)\,\phi_{\text{SOC}})\
\text{for }*=\text{log, Vaidya}\,,$

to deal with the truncated SOC constraint. For the log-barrier case, this
yields an ${\bigl{(}\mathcal{O}(m+d),\mathcal{O}(m+d)\bigr{)}}$-Dikin-amenable
metric due to Lemma 5.16, with which $\mathsf{GCDW}$ requires
$\widetilde{\mathcal{O}}(d(m+d))$ iterations of the $\mathsf{Dikin\ walk}$.

##### Gaussian sampling.

Following the reduction as in the polytope sampling, we should use

$g(x,t,t^{\prime})=3\left[\begin{array}[]{cc}\nabla^{2}_{(x,t)}\phi_{\textup{log}}(x,t)+(d+1)\,\nabla^{2}_{(x,t)}\phi_{\textup{SOC}}(x,t)\\\
&0\end{array}\right]+3(d+2)\,\nabla^{2}_{(x,t,t^{\prime})}\phi_{\textup{Gauss}}(x,t,t^{\prime}),$

which is ${\bigl{(}\mathcal{O}(m+d),\mathcal{O}(m+d)\bigr{)}}$-Dikin-amenable,
and thus $\mathsf{GCDW}$ needs $\widetilde{\mathcal{O}}(d(m+d))$ iterations of
the $\mathsf{Dikin\ walk}$.

###  6.3 PSD cone sampling

For a matrix $X\in\mathbb{R}^{d\times d}$, recall that
$\textup{{vec}}(X)\in\mathbb{R}^{d^{2}}$ denotes the vector obtained by
stacking columns of $X$ vertically. Additionally, we define
$A\in\mathbb{R}^{m\times d^{2}}$, $S_{X}\in\mathbb{R}^{m\times m}$, and
$A_{X}\in\mathbb{R}^{m\times d^{2}}$ by

$A:=\left[\begin{array}[]{ccc}\textup{{vec}}(A_{1})&\cdots&\textup{{vec}}(A_{m})\end{array}\right]^{\mathsf{T}},\quad
S_{X}:=\textup{{Diag}}(\langle A_{i},X\rangle-b_{i}),\quad
A_{X}:=S_{X}^{-1}A\,,$

where we assume $A$ has no all-zero rows and $(S_{X})_{ii}>0$ for $i\in[m]$.

##### Uniform and exponential sampling.

The metric below comes from the Hessian of

$-2d^{2}\,\log\det X-2\sum_{i=1}^{m}\log(\langle A_{i},X\rangle-b_{i})\,.$

Here the first term, the log-determinant, serves as a barrier for the PSD cone
while the second term is the standard logarithmic barrier for linear
constraints. We note that the $-\log\det X$ is strictly convex on
$x\in\textup{{int}}(K)$ for $K$ the truncated PSD cone, so all metrics $g$
introduced in our main results are positive definite. Thus, the
$\mathsf{Dikin\ walk}$ with those $g$ is well-defined.

######  Proposition 6.1.

Let $K$ be the truncated PSD cone and $g$ be the local metric such that at
each $X\in\textup{{int}}(K)$, for symmetric matrices $H_{1},H_{2}$,

$g_{X}(H_{1},H_{2})=2d^{2}\textup{{Tr}}(X^{-1}H_{1}X^{-1}H_{2})+2\,\textup{{vec}}(H_{1})^{\mathsf{T}}A_{X}^{\mathsf{T}}A_{X}\textup{{vec}}(H_{2})\,.$

Then $\mathsf{GCDW}$ needs $\widetilde{\mathcal{O}}((d^{3}+m)d^{2})$ steps of
the $\mathsf{Dikin\ walk}$ with the local metric $g$, where each step runs in
$\mathcal{O}{\bigl{(}(md^{\omega}+m^{2}d^{2})\wedge(d^{2\omega}+md^{2(\omega-1)})\bigr{)}}$
time444Here $\omega<2.373$ is the current matrix multiplication complexity
exponent (Le Gall (2014))..

Since $g_{X}$ is
${\bigl{(}\mathcal{O}(m+d^{3}),\mathcal{O}(m+d^{3})\bigr{)}}$-Dikin-amenable
by Lemma 5.17, $\mathsf{GCDW}$ requires
${\widetilde{\mathcal{O}}(d^{2}\,(d^{3}+m))}$ iterations of the
$\mathsf{Dikin\ walk}$. As mentioned earlier, efficient maintenance of the
inverse of a metric function could lead to a faster per-step complexity. As an
example, we provide such an implementation of Proposition 6.1 in §6.3.1.
Putting these together, for an interesting regime of $m=\mathcal{O}(1)$,
$\mathsf{GCDW}$ is faster than the $\mathsf{Ball\ walk}$ by a factor of $d$ in
terms of the total complexity.

If we replace the log-barrier by the Vaidya metric, then the dependence on $m$
is improved to $\sqrt{m}$ as in the polytope sampling. See §7.5.1 for the
proofs of the two claims below.

######  Proposition 6.2.

Let $K$ be the truncated PSD cone and $g$ be the local metric such that at
each $X\in\textup{{int}}(K)$, for symmetric matrices $H_{1},H_{2}$,

$g_{X}(H_{1},H_{2})=2d^{2}\textup{{Tr}}(X^{-1}H_{1}X^{-1}H_{2})+44\sqrt{\frac{m}{d}}\,\textup{{vec}}(H_{1})^{\mathsf{T}}A_{X}^{\mathsf{T}}{\bigl{(}\Sigma_{X}+\frac{d}{m}I_{m}\bigr{)}}A_{X}\textup{{vec}}(H_{2})\,.$

Then $\mathsf{GCDW}$ needs $\widetilde{\mathcal{O}}((d^{2}+\sqrt{m})d^{3})$
steps of the $\mathsf{Dikin\ walk}$ with the local metric $g$, with each step
running in $\widetilde{\mathcal{O}}(md^{2(\omega-1)})$ amortized time.

Lastly, the dependence on $m$ can be made poly-logarithmic by working with the
Lewis-weight metric. We remark that for uniform sampling the total complexity
of $\mathsf{GCDW}$ is less than that of the $\mathsf{Ball\ walk}$ by the order
of $d^{5-2\omega}$.

######  Proposition 6.3.

Let $K$ be the truncated PSD cone and $g$ be the local metric such that at
each $X\in\textup{{int}}(K)$, for symmetric matrices $H_{1},H_{2}$,

$g_{X}(H_{1},H_{2})=2d^{2}\textup{{Tr}}(X^{-1}H_{1}X^{-1}H_{2})+dc_{1}(\log
m)^{c_{2}}\,\textup{{vec}}(H_{1})^{\mathsf{T}}A_{X}^{\mathsf{T}}W_{X}A_{X}\textup{{vec}}(H_{2})\,,$

where $W_{X}$ is the diagonalized $\ell_{p}$-Lewis weight of $A_{X}$ with
$p=\mathcal{O}(\log m)$, and $c_{1},c_{2}>0$ are universal constants. Then
$\mathsf{GCDW}$ requires $\widetilde{\mathcal{O}}(d^{5})$ steps of the
$\mathsf{Dikin\ walk}$, with each step running in
$\widetilde{\mathcal{O}}(md^{2(\omega-1)})$ amortized time.

##### Gaussian sampling.

Just as in polytope or second-order cone sampling, we introduce a new variable
$t$ by replacing a quadratic term in the potential. This reduces the Gaussian
sampling problem to an exponential sampling problem. We then work with a local
metric

$g(X,t)=3\left(d\left[\begin{array}[]{cc}\nabla^{2}_{X}\phi_{\textup{Lw}}(X)\\\
&0\end{array}\right]+d^{2}\left[\begin{array}[]{cc}\nabla^{2}_{X}\phi_{\textup{PSD}}(X)\\\
&0\end{array}\right]+d^{2}\nabla^{2}_{(X,t)}\phi_{\textup{Gauss}}(X,t)\right)\,,$

which is
${\bigl{(}\mathcal{O}^{*}(d^{3}),\mathcal{O}^{*}(d^{3})\bigr{)}}$-Dikin-
amenable. Thus, $\mathsf{GCDW}$ needs $\widetilde{\mathcal{O}}(d^{5})$
iterations of the $\mathsf{Dikin\ walk}$ with the local metric $g$, and the
per-step complexity remains $\widetilde{\mathcal{O}}(md^{2(\omega-1)})$ in
amortized time.

####  6.3.1 Per-step implementation

Now we design an oracle that implements each iteration of the $\mathsf{Dikin\
walk}$ (Algorithm 1). This can be implemented as follows: when the current
point is $x$,

  * •

Sample $z\sim\mathcal{N}{\bigl{(}0,\frac{r^{2}}{d}g(x)^{-1}\bigr{)}}$.

  * •

Compute $y=x+g(x)^{-1/2}z$ and propose it.

  * •

Accept $y$ with probability $1\wedge{\bigl{(}\sqrt{\frac{\det g(y)}{\det
g(x)}}\,\frac{\exp f(x)}{\exp f(y)}\bigr{)}}$.

We provide two algorithms with the complexity of
$\mathcal{O}(md^{\omega}+m^{2}d^{2})$ and
$\mathcal{O}(d^{2\omega}+md^{2(\omega-1)})$. We can implement each iteration
in
$\mathcal{O}{\bigl{(}(md^{\omega}+m^{2}d^{2})\wedge(d^{2\omega}+md^{2(\omega-1)})\bigr{)}}$
time by using the former for small $m$ and the latter for large $m$. This
completes the second half of Theorem 6.1.

##### Algorithm for small $m$.

For simplicity here, we ignore the constant factors of $g=g_{1}+g_{2}$, where

$g_{1}(X)=M^{\mathsf{T}}(X\otimes
X)^{-1}M=:BB^{\mathsf{T}}\qquad\text{and}\qquad
g_{2}(X)=M^{\mathsf{T}}A^{\mathsf{T}}S_{X}^{-2}AM=:UU^{\mathsf{T}}\,.$

where $B:=M^{\mathsf{T}}(X\otimes X)^{-1/2}\in\mathbb{R}^{d_{s}\times d^{2}}$
and $U:=M^{\mathsf{T}}A^{\mathsf{T}}S_{X}^{-1}\in\mathbb{R}^{d_{s}\times m}$.
Letting $u_{i}$ be the $i$-th column of $U$ for $i\in[m]$, we note that
$g_{2}=\sum_{i=1}^{m}u_{i}u_{i}^{\mathsf{T}}$.

We start with a subroutine for computing $g(X)^{-1}v$ for given
$v\in\mathbb{R}^{d_{s}}$ in $\mathcal{O}(md^{\omega}+m^{2}d^{2})$ time.

1

2

3

4Input: $X\in\mathbb{S}_{+}^{d}$, vector $v\in\mathbb{R}^{d_{s}}$, local
metric $g$.

5Output: $g(X)^{-1}v$

6Prepare the column vectors $u_{i}$ of
$U=M^{\mathsf{T}}A^{\mathsf{T}}S_{X}^{-1}$.

7For $\bar{g}_{0}:=g_{1}(X)$, compute $\bar{g}_{0}^{-1}v$ and
$\bar{g}_{0}^{-1}u_{i}$ for $i\in[m]$.

8for  _$i=1,\cdots,m$_ do

9

10 Compute $\bar{g}_{i}^{-1}v$ and $\bar{g}_{i}^{-1}u_{j}$ for $j\in[m]$,
according to

11 $\bar{g}_{i}^{-1}w=\bar{g}_{i-1}^{-1}w-\frac{\bar{g}_{i-1}^{-1}u_{i}\cdot
u_{i}^{\mathsf{T}}\bar{g}_{i-1}^{-1}w}{1+u_{i}^{\mathsf{T}}\bar{g}_{i-1}^{-1}u_{i}}\,.$

12 end for

13

14Output $\bar{g}_{m}^{-1}v$.

Algorithm 4 Computation of $g(X)^{-1}v$

######  Proposition 6.4.

Algorithm 4 computes $g(X)^{-1}v$ in $\mathcal{O}(md^{\omega}+m^{2}d^{2})$
time for a query $v\in\mathbb{R}^{d_{s}}$.

See §7.5.2 for the proof. With this subroutine in hand, we proceed to an
efficient implementation of two tasks – computation of (1)
$g(x)^{-\frac{1}{2}}z$ for a given vector $z\in\mathbb{R}^{d_{s}}$ and (2)
$\sqrt{\frac{\det g(y)}{\det g(x)}}\,\frac{\exp f(x)}{\exp f(y)}$.

1

2

3

4Input: current point $X\in\mathbb{S}_{+}^{d}$, local metric $g$

// Step 1: Sampling from
$\mathcal{N}{\bigl{(}0,\frac{r^{2}}{d}g(X)^{-1}\bigr{)}}$

5

6Draw $w\sim\mathcal{N}(0,I_{d^{2}+m})$ and $v\leftarrow
g(X)^{-1}\left[\begin{array}[]{cc}B&U\end{array}\right]w$ by Algorithm 4.

7Propose $y\leftarrow\textup{{svec}}(X)+\frac{r}{\sqrt{d}}v$.

8

// Step 2: Computation of acceptance probability

9

10Use Algorithm 4 to prepare
$\\{\bar{g}_{i}^{-1}u_{1},\dots,\bar{g}_{i}^{-1}u_{m}\\}_{i=0}^{m}$ at $X$ and
$Y:=\textup{{svec}}^{-1}(y)$.

11$\det\bar{g}_{0}(\cdot)\leftarrow 2^{d(d-1)/2}(\det(\cdot))^{-(d+1)}$
($\because$ Lemma A.1-7)

12for  _$i=1,\cdots,m$_ do

13

14
$\det(\bar{g}_{i+1})\leftarrow\det\bar{g}_{i}\cdot(1+u_{i+1}^{\mathsf{T}}\bar{g}_{i}^{-1}u_{i+1})$.

15 end for

16

17Accept $Y$ with probability
$1\wedge{\bigl{(}\sqrt{\frac{\det\bar{g}_{m}(Y)}{\det\bar{g}_{m}(X)}}\,\frac{\exp
f(X)}{\exp f(Y)}\bigr{)}}$.

Algorithm 5 Implementation of the $\mathsf{Dikin\ walk}$

######  Lemma 6.5.

Algorithm 5 implements the $\mathsf{Dikin\ walk}$ with per-step complexity of
$\mathcal{O}(md^{\omega}+m^{2}d^{2})$.

##### Algorithm for large $m$.

The algorithm right above has quadratic dependence on the number $m$ of
constraints, which could become expensive for large $m$. In this regime, we
just fully compute the whole matrix function of size $\mathbb{R}^{d_{s}\times
d_{s}}$, which takes $\mathcal{O}(d^{2\omega}+md^{2(\omega-1)})$ time, and
computing its inverse, square-root, and determinant takes
$\mathcal{O}(d^{2\omega})$ time.

####  6.3.2 Handling approximate Lewis weights

When implementing the $\mathsf{Dikin\ walk}$ with the Lewis-weights metric, we
use an approximation algorithm presented in Lee and Sidford (2019) for
computing and updating the Lewis weight, which ensures

$(1-\delta)\widetilde{W}_{X}\preceq W_{X}\preceq(1+\delta)\widetilde{W}_{X}$

for the approximate Lewis weights $\widetilde{W}_{X}$ and a target accuracy
parameter $\delta$ (note that the initialization and update times of the Lewis
weight above hide poly-logarithmic dependence on $\log(1/\delta)$). Strictly
speaking, we should check that these approximate Lewis weights do not affect
the theoretical guarantees above.

To see this, let us define $\widetilde{g}=2(dg_{1}+\widetilde{g}_{2})$, where
for some constants $c_{1},c_{2}>0$

$g_{1}(X)=d^{2}M^{\mathsf{T}}(X\otimes
X)^{-1}M\qquad\text{and}\qquad\widetilde{g}_{2}=dc_{1}\left(\log
m\right)^{c_{2}}M^{\mathsf{T}}A_{X}^{\mathsf{T}}\widetilde{W}_{X}A_{X}M\,.$

First of all, the $\mathsf{Dikin\ walk}$ with $\widetilde{g}$ still converges
to a target distribution, since the approximation algorithm in Lee and Sidford
(2019) is deterministic and thus the condition of detailed balance still holds
under the acceptance probability of
$1\wedge{\bigl{(}\sqrt{\frac{\det\tilde{g}(Y)}{\det\tilde{g}(X)}}\,\frac{\exp
f(X)}{\exp f(Y)}\bigr{)}}$. For $\widetilde{P}_{X}$ the one-step distribution
of the $\mathsf{Dikin\ walk}$ started at $X$ with $\widetilde{g}$, we can show
one-step coupling similar to Lemma 2.3, following the overall proof therein
and taking $\delta=1/\text{poly}(d)$ small enough. See §7.5.3 for the proof.

######  Lemma 6.6 (One-step coupling).

For convex $K\subset\mathbb{R}^{d}$, let
$g:\textup{{int}}(K)\to\mathbb{S}_{++}^{d}$ be SSC, ASC, LTSC, and
$\phi:\textup{{int}}(K)\to\mathbb{R}$ be its function counterpart. Suppose
that the potential $f$ of the target distribution $\pi$ is $\beta$-relatively
smooth in $\phi$. Then there exist constants $s_{1},s_{2}>0$ such that if
${\|x-y\|}_{g(x)}\leq s_{1}r/\sqrt{d}$ with $r=s_{2}\,(1\wedge
1/\sqrt{\beta})$ for $x,y\in\textup{{int}}(K)$, then
$d_{\textrm{{TV}}}(\widetilde{P}_{x},\widetilde{P}_{y})\leq\frac{3}{4}+0.01$.

##  7 Proofs

We collect deferred proofs in this section.

###  7.1 Mixing of $\mathsf{Dikin\ walk}$ ($\S$2)

####  7.1.1 One-step coupling

We start with the one-step coupling of the $\mathsf{Dikin\ walk}$ under the
setting $\alpha\nabla^{2}\phi\preceq\nabla^{2}f\preceq\beta\nabla^{2}\phi$ on
$\textup{{int}}(K)$. Roughly speaking, if ${\|x-y\|}_{x}\leq r/\sqrt{d}$ with
$r\lesssim 1\wedge\nicefrac{{1}}{{\sqrt{\beta}}}$, then
$d_{\textrm{{TV}}}(P_{x},P_{y})\leq 0.99$.

###### Proof of Lemma 2.3.

For $\pi\propto\exp(-f)\cdot\mathbf{1}_{K}$ and
$z\sim\mathcal{N}(x,\frac{r^{2}}{d}g(x)^{-1})$, let us denote

$p_{x}=\mathcal{N}{\Bigl{(}x,\frac{r^{2}}{d}g(x)^{-1}\Bigr{)}},\qquad
R(x,z)=\frac{p_{z}(x)}{p_{x}(z)}\frac{\pi(z)}{\pi(x)},\qquad
A(x,z)=\min{\bigl{(}1,R(x,z)\,\mathbf{1}_{K}(z)\bigr{)}}\,.$

The transition kernel $P(x,\cdot)$ of the $\mathsf{Dikin\ walk}$ started at
$x$ can be written as

$P(x,dz)=\underbrace{{\bigl{(}1-\mathbb{E}_{p_{x}}[A(x,\cdot)]\bigr{)}}}_{\eqqcolon
r_{x}}\,\delta_{x}(\mathrm{d}z)+A(x,z)\,p_{x}(\mathrm{d}z)\,.$

Thus, for $x,y\in\textup{{int}}(K)$,

$\displaystyle d_{\textrm{{TV}}}(P_{x},P_{y})$
$\displaystyle=\underbrace{\frac{1}{2}(r_{x}+r_{y})}_{\mathsf{I}}+\underbrace{\frac{1}{2}\int|A(x,z)\,p_{x}(z)-A(y,z)\,p_{y}(z)|\,\mathrm{d}z}_{\mathsf{II}}\,.$
($\mathsf{TV\text{-}decomposition}$)

Let $h\sim\mathcal{N}(0,I_{d})$ and denote a bad event
$B_{0}=\\{z\in\mathbb{R}^{d}:{\|z-x\|}_{x}\geq cr\\}$ with $c$ determined
later. Due to ${\|z-x\|}_{x}=\frac{r}{\sqrt{d}}{\|h\|}$ (in law) and
concentration of the standard Gaussian in a thin shell of radius $\sqrt{d}$
with annulus $\mathcal{O}(1)$555A standard Gaussian
$h\sim\mathcal{N}(0,I_{d})$ is concentrated around a thin sell of radius
$\sqrt{d}$ with annulus $\mathcal{O}(1)$: For $t>0$,
$\mathbb{P}_{h}({\|h\|}_{2}\geq\sqrt{d}+t)\leq\exp(-t^{2}/2)\,.$ , we have
$\mathbb{P}_{z}(B_{0})=\mathbb{P}_{h}({\|h\|}\geq
c\sqrt{d})\leq\exp{\bigl{(}-(c-1)\sqrt{d}/2\bigr{)}}$. Hence,
$\mathbb{P}(B_{0})\leq\varepsilon$ for $c\geq
1+\sqrt{\frac{2}{d}\,\log\frac{1}{\varepsilon}}$.

##### Rejection probability $r_{x}$ and $r_{y}$ (Term $\mathsf{I}$).

Note that

$r_{x}=1-\mathbb{E}_{p_{x}}[A(x,z)]=1-\int\min{\Bigl{(}1,\,\underbrace{\mathbf{1}_{K}(z)\frac{\exp
f(x)}{\exp
f(z)}}_{\eqqcolon\textsf{A}}\underbrace{\frac{p_{z}(x)}{p_{x}(z)}}_{\eqqcolon\textsf{B}}\Bigr{)}}p_{x}(\mathrm{d}z)\,.$

As for A, we let $\nabla^{2}\phi\preceq c_{\phi}g$ for some $c_{\phi}>0$ and
use Taylor’s expansion at $x\in K\cap B_{0}^{c}$ to show that for some
$x^{*}\in[x,z]$,

$\displaystyle f(x)-f(z)$ $\displaystyle+\nabla
f(x)^{\mathsf{T}}(z-x)=-{\|z-x\|}_{\nabla^{2}f(x^{*})}^{2}\geq-
c_{\phi}\beta\,{\|z-x\|}_{g(x^{*})}^{2}$
$\displaystyle\underset{\text{(i)}}{\geq}-c_{\phi}\beta\,{\|z-x\|}_{x}^{2}\cdot(1+2{\|x-z\|}_{x})^{2}\geq-
c_{\phi}\beta
c^{2}r^{2}(1+2cr)^{2}\underset{\text{(ii)}}{\geq}-\varepsilon\,,$

where we used Lemma 4.4 in (i) and took $r\leq r_{1}(\varepsilon)$ in (ii),
which is defined so that $\beta c_{\phi}c^{2}r^{2}(1+cr)^{2}\leq\varepsilon$
for any $r\leq r_{1}(\varepsilon)$. It follows from
$\mathcal{D}_{g}^{1}(x)\subset K$ and symmetry of $\mathcal{N}_{g}^{r}(x)$
that there exists a half-ellipsoid $G\subset\mathcal{D}_{g}^{1}(x)$ in which
$\langle\nabla f(x),z-x\rangle\leq 0$. Thus, $f(x)-f(z)\geq-\varepsilon$ holds
on $z\in G$.

For a bad event $B_{1}:=G^{c}$, it holds that

$\mathbb{P}_{z}(B_{1})\leq\frac{1}{2}+\mathbb{P}_{z}{\bigl{(}\mathcal{D}_{g}^{1}(x)^{c}\bigr{)}}=\frac{1}{2}+\mathbb{P}_{z}({\|z-x\|}_{x}\geq
1)=\frac{1}{2}+\mathbb{P}_{h}{\Bigl{(}{\|h\|}\geq\frac{\sqrt{d}}{r}\Bigr{)}}\leq\frac{1}{2}+\varepsilon\,,$

where the last inequality follows from concentration of $h$ for any $r\leq
r_{2}(\varepsilon):={\bigl{(}1+\frac{2}{\sqrt{d}}\,\log\frac{1}{\varepsilon}\bigr{)}}^{-1}$.

As for B, for $\varphi(x):=\frac{1}{2}\log\det g(x)$ we have

$\log\text{{B}}=-\frac{d}{2r^{2}}{\bigl{(}{\|z-x\|}_{z}^{2}-{\|z-x\|}_{x}^{2}\bigr{)}}+{\bigl{(}\varphi(z)-\varphi(x)\bigr{)}}\,.$

Invoking ASC of $\phi$, we can take $r_{3}(\varepsilon)$ so that
$\mathbb{P}_{z}{\bigl{(}{\|z-x\|}_{z}^{2}-{\|z-x\|}_{x}^{2}\leq 2\varepsilon
r^{2}/d\bigr{)}}\geq 1-\varepsilon$ for any $r\leq r_{3}(\varepsilon)$ and
control the first term. Let the complement of this event be our second bad
event $B_{2}$.

For $\varphi(z)-\varphi(x)$, Taylor’s expansion of $\varphi$ at $x$ leads to

$\varphi(z)-\varphi(x)=\underbrace{\langle\nabla\varphi(x),z-x\rangle}_{\eqqcolon\textsf{A'}}+\underbrace{\frac{1}{2}\langle\nabla^{2}\varphi(x^{*})(z-x),z-x)\rangle}_{\eqqcolon\textsf{B'}}\text{
for some }x^{*}\in[x,z]\,.$

As for $\textsf{A}^{\prime}$, we have
$\langle\nabla\varphi(x),z-x\rangle=\frac{r}{\sqrt{d}}\langle
g(x)^{-1/2}\nabla\varphi(x),h\rangle$, and a standard tail bound for $h$ leads
to

$\mathbb{P}_{z}{\Bigl{(}\langle\nabla\varphi(x),z-x\rangle\leq-\frac{r}{\sqrt{d}}\,{\|g(x)^{-1/2}\nabla\varphi(x)\|}_{2}\cdot
2\log\frac{1}{\varepsilon}\Bigr{)}}\leq\varepsilon\,.$

We call this event $B_{3}$ and bound ${\|g(x)^{-1/2}\nabla\varphi(x)\|}_{2}$
via SSC of $g$ as follows: omitting $x$ for simplicity,

$\displaystyle{\|g^{-\frac{1}{2}}\nabla\varphi\|}_{2}$
$\displaystyle=\sup_{v:{\|v\|}_{2}=1}\langle\nabla\varphi,g^{-\frac{1}{2}}v\rangle\underset{\text{(i)}}{=}\sup_{v}\textup{{Tr}}(g^{-1}\mathrm{D}g[g^{-\frac{1}{2}}v])=\sup_{v}\textup{{Tr}}(g^{-\frac{1}{2}}\mathrm{D}g[g^{-\frac{1}{2}}v]\,g^{-\frac{1}{2}})$
$\displaystyle\underset{\text{(ii)}}{\leq}\sup_{v}\sqrt{d}\,{\|g^{-\frac{1}{2}}\mathrm{D}g[g^{-\frac{1}{2}}v]\,g^{-\frac{1}{2}}\|}_{F}\underset{\text{(iii)}}{\leq}\sup_{v}2\sqrt{d}{\|g^{-\frac{1}{2}}v\|}_{x}=2\sqrt{d}\,,$

where (i) follows from (A.1), (ii) is due to
$\textup{{Tr}}(A)\leq\sqrt{d}{\|A\|}_{F}$ for $A\in\mathbb{R}^{d\times d}$,
and (iii) is due to SSC. Conditioned on $B_{3}^{c}$, taking $r\leq
r_{4}(\varepsilon):=\varepsilon(4\log\frac{1}{\varepsilon})^{-1}$, we have

$\mathsf{A^{\prime}}=\langle\nabla\varphi(x),z-x\rangle\geq-4r\,\log\frac{1}{\varepsilon}\geq-\varepsilon\,.$

As for $\textsf{B}^{\prime}$, denoting $u=z-x$ for $z\in B_{0}^{c}$

$\displaystyle\mathrm{D}^{2}\varphi(x^{*})[u,u]$
$\displaystyle\underset{\eqref{eq:hessLogDet}}{=}\textup{{Tr}}{\bigl{(}g(x^{*})^{-1}\mathrm{D}^{2}g(x^{*})[u,u]\bigr{)}}-{\|g(x^{*})^{-\frac{1}{2}}\mathrm{D}g(x^{*})[u]\,g(x^{*})^{-\frac{1}{2}}\|}_{F}^{2}$
$\displaystyle\underset{\text{(i)}}{\geq}-{\|u\|}_{x^{*}}^{2}-{\|g(x^{*})^{-\frac{1}{2}}\mathrm{D}g(x^{*})[u]\,g(x^{*})^{-\frac{1}{2}}\|}_{F}^{2}\geq-{\|u\|}_{x^{*}}^{2}-4{\|u\|}_{x^{*}}^{2}$
$\displaystyle\underset{\text{(ii)}}{\geq}-5(1-{\|x-x^{*}\|}_{x})^{-2}{\|u\|}_{x}^{2}$
(7.1) $\displaystyle\geq-5(1+2cr)^{2}c^{2}r^{2}\,,$

where (i) follows from LTSC and (ii) follows from Lemma 4.4. Hence,
$\mathsf{B^{\prime}}\geq-\varepsilon/2$ by taking $r\leq r_{5}(\varepsilon)$
so that $5(1+2cr_{5})^{2}c^{2}r_{5}^{2}=\varepsilon$.

In summary, conditioned on $G:=\bigcap_{i=0}^{3}B_{i}^{c}$ with
$\mathbb{P}_{z}(G)\geq\frac{1}{2}-4\varepsilon$ due to the union bound, we
have

$\displaystyle\textsf{A}:$ $\displaystyle\,\frac{\exp f(x)}{\exp
f(z)}\geq\exp(-\varepsilon)\,,$ (7.2) $\displaystyle\textsf{B}:$
$\displaystyle\,\frac{p_{z}(x)}{p_{x}(z)}\geq\exp(-3\varepsilon)\,,$ (7.3)
$\displaystyle\,\varphi(z)-\varphi(x)\geq-2\varepsilon\,.$ (7.4)

Combining these together,

$\displaystyle r_{x}$
$\displaystyle=1-\int\min{\Bigl{(}1,\mathbf{1}_{K}(z)\frac{\exp f(x)}{\exp
f(z)}\,\frac{p_{z}(x)}{p_{x}(z)}\Bigr{)}}p_{x}(\mathrm{d}z)\leq
1-\int_{G}(1\wedge
e^{-\varepsilon}e^{-3\varepsilon})\,\mathbb{P}_{z}(G)\leq\frac{1}{2}+5\varepsilon\,.$

Bounding $r_{y}$ in the same way, we conclude that
$\textsf{I}\leq\frac{1}{2}+5\varepsilon$ in
($\mathsf{TV\text{-}decomposition}$).

##### Overlapping part (Term $\mathsf{II}$).

WLOG, assume $f(y)\geq f(x)$. We denote good events by
$G_{x}=\cap_{i=0,2,3}B_{x,i}^{c}$ and $G_{y}=\cap_{i=0,2,3}B_{y,i}^{c}$ such
that $\mathbb{P}_{p_{x}}(G_{x}^{c})\leq 3\varepsilon$ and
$\mathbb{P}_{p_{y}}(G_{y}^{c})\leq 3\varepsilon$, where

$\displaystyle B_{x,0}$ $\displaystyle=\\{{\|z-x\|}_{x}\geq cr\\}\ \text{with
}c\geq 1+\frac{2}{\sqrt{d}}\,\log\frac{1}{\varepsilon},\ \text{and}\
B_{x,2}=\Bigl{\\{}{\|z-x\|}_{z}^{2}-{\|z-x\|}_{x}^{2}>\frac{2\varepsilon
r^{2}}{d}\Bigr{\\}}$ $\displaystyle B_{x,3}$
$\displaystyle=\Bigl{\\{}\nabla\varphi(x)^{\mathsf{T}}(z-x)\leq-\frac{2r\log\frac{1}{\varepsilon}}{\sqrt{d}}\,{\|g(x)^{-\frac{1}{2}}\nabla\varphi(x)\|}_{2}\Bigr{\\}}\,.$

Let $G:=G_{x}\cup G_{y}$, and define a partition of $G$ by

$G_{x\backslash y}:=G_{x}\backslash G_{y},\qquad G_{x,y}:=G_{x}\cap
G_{y},\qquad G_{y\backslash x}:=G_{y}\backslash G_{x}\,.$

Now we decompose the term II as follows: for
$Q:=|A(x,z)p_{x}(z)-A(y,z)p_{y}(z)|$,

II $\displaystyle=\frac{1}{2}\int_{K\backslash
G}Q\,\mathrm{d}z+\underbrace{\frac{1}{2}\int_{G_{x\backslash
y}}Q\,\mathrm{d}z}_{\eqqcolon\mathcal{A}}+\underbrace{\frac{1}{2}\int_{G_{y\backslash
x}}Q\,\mathrm{d}z}_{\eqqcolon\mathcal{B}}+\underbrace{\frac{1}{2}\int_{G_{x,y}}Q\,\mathrm{d}z}_{\eqqcolon\mathcal{C}}$
$\displaystyle\leq\frac{1}{2}{\bigl{(}\mathbb{P}_{p_{x}}(K\backslash
G)+\mathbb{P}_{p_{y}}(K\backslash
G)\bigr{)}}+\mathcal{A}+\mathcal{B}+\mathcal{C}\leq\frac{1}{2}{\bigl{(}\mathbb{P}_{p_{x}}(G_{x}^{c})+\mathbb{P}_{p_{y}}(G_{y}^{c})\bigr{)}}+\mathcal{A}+\mathcal{B}+\mathcal{C}$
$\displaystyle\leq 3\varepsilon+\mathcal{A}+\mathcal{B}+\mathcal{C}\,.$

The term $\mathcal{A}$ can be further decomposed by

$\displaystyle 2\mathcal{A}$ $\displaystyle\leq\int_{G_{x\backslash
y}}A(x,z)\,|p_{x}(z)-p_{y}(z)|\,\mathrm{d}z+\int_{G_{x\backslash
y}}|A(x,z)-A(y,z)|\,p_{y}(\mathrm{d}z)$ $\displaystyle\leq\int_{G_{x\backslash
y}}|p_{x}(z)-p_{y}(z)|\,\mathrm{d}z+\mathbb{P}_{p_{y}}(G_{x\backslash
y})\leq\int_{G_{x\backslash
y}}|p_{x}(z)-p_{y}(z)|\,\mathrm{d}z+\underbrace{\mathbb{P}_{p_{y}}(G_{y}^{c})}_{\leq
3\varepsilon}\,,$

and in a similar way $\mathcal{B}\leq\frac{1}{2}\int_{G_{y\backslash
x}}|p_{x}(z)-p_{y}(z)|\,\mathrm{d}z+3\varepsilon/2$. Combining these together,

$\displaystyle\mathcal{A}+\mathcal{B}$ $\displaystyle\leq
3\varepsilon+\frac{1}{2}\int_{G_{x\backslash y}\cup G_{y\backslash
x}}|p_{x}(z)-p_{y}(z)|\,\mathrm{d}z\leq
3\varepsilon+d_{\textrm{{TV}}}(p_{x},p_{y})\leq 4\varepsilon\,,$

where we used $d_{\textrm{{TV}}}(p_{x},p_{y})\leq\varepsilon$; to see this,
recall Pinsker’s inequality and a formula for the $\mathsf{KL}$ divergences
between two Gaussians:

$2[d_{\textrm{{TV}}}(p_{x},p_{y})]^{2}\leq\mathsf{KL}(p_{y}\mathbin{\|}p_{x})=\frac{1}{2}\,{\Bigl{(}\textup{{Tr}}{\bigl{(}g(y)^{-1}g(x)\bigr{)}}-d+\log\det{\bigl{(}g(y)g(x)^{-1}\bigr{)}}+\frac{d}{r^{2}}\,{\|y-x\|}_{x}^{2}\Bigr{)}}\,.$

Let $\\{\lambda_{i}\\}_{i\in[d]}$ be the eigenvalues of
$g(x)^{-\frac{1}{2}}g(y)g(x)^{-\frac{1}{2}}$ and
${\|x-y\|}_{x}\leq\frac{sr}{\sqrt{d}}$ with $s>0$ to be determined. Then,
$\frac{1}{2}\leq\lambda_{i}\leq 1+8{\|x-y\|}_{x}$ by Lemma 4.4. Using this and
$\log x\leq x-1$ for $x>0$,

$\displaystyle 2\,\mathsf{KL}(p_{y}\mathbin{\|}p_{x})$
$\displaystyle=\sum_{i=1}^{d}{\Bigl{(}\lambda_{i}-1+\log\frac{1}{\lambda_{i}}\Bigr{)}}+\frac{d}{r^{2}}\,{\|y-x\|}_{x}^{2}\leq\sum_{i=1}^{d}\frac{(\lambda_{i}-1)^{2}}{\lambda_{i}}+s^{2}\leq
s^{2}\,(128r^{2}+1)\,,$

Taking $s\leq s_{1}(\varepsilon):=\varepsilon$ and $r\leq r_{6}(\varepsilon)$
so that $\sqrt{128r_{6}^{2}+1}\leq 2$, we obtain

$\displaystyle
d_{\textrm{{TV}}}(p_{x},p_{y})\leq\sqrt{\frac{1}{2}\,\mathsf{KL}(p_{y}\mathbin{\|}p_{x})}$
$\displaystyle\leq\frac{s}{2}\sqrt{128r^{2}+1}\leq\varepsilon\,,$ (7.5)

We now bound $\mathcal{C}$. Recall $B_{x,1}=\\{\langle\nabla
f(x),z-x\rangle\geq 0\\}$ and
$\mathbb{P}_{p_{x}}(B_{x,1})\leq\frac{1}{2}+\mathcal{O}(\varepsilon)$. Then,

$\displaystyle 2\mathcal{C}$ $\displaystyle=\int_{(G_{x}\cap G_{y})\backslash
B_{x,1}^{c}}Q\,\mathrm{d}z+\int_{G_{x}\cap G_{y}\cap
B_{x,1}^{c}}Q\,\mathrm{d}z\leq\int_{B_{x,1}}\underbrace{Q}_{\text{The traingle
inequality}}\,\mathrm{d}z+\int_{G_{x}\cap G_{y}\cap
B_{x,1}^{c}}Q\,\mathrm{d}z$
$\displaystyle\leq\int_{B_{x,1}}|A(x,z)-A(y,z)|\,p_{x}(\mathrm{d}z)+\int_{B_{x,1}}A(y,z)\>|p_{x}(z)-p_{y}(z)|\,\mathrm{d}z+\int_{G_{x}\cap
G_{y}\cap B_{x,1}^{c}}Q\,\mathrm{d}z$
$\displaystyle\leq\underbrace{\mathbb{P}_{p_{z}}(B_{x,1})}_{\leq\frac{1}{2}+\varepsilon}+2\underbrace{d_{\textrm{{TV}}}(p_{x},p_{y})}_{\leq\varepsilon\
(\ref{eq:TV-by-KL})}+\int_{G_{x}\cap G_{y}\cap
B_{x,1}^{c}}|A(x,z)\,p_{x}(z)-A(y,z)\,p_{y}(z)|\,\mathrm{d}z$
$\displaystyle\leq\frac{1}{2}+2\varepsilon+\int_{G_{x}\cap G_{y}\cap
B_{x,1}^{c}}|A(x,z)\,p_{x}(z)-A(y,z)\,p_{y}(z)|\,\mathrm{d}z\,.$

One can check that

$|A(x,z)\,p_{x}(z)-A(y,z)\,p_{y}(z)|\,\mathrm{d}z=\Big{|}\min{\Bigl{(}1,\underbrace{\frac{\exp
f(x)}{\exp
f(z)}\,\frac{p_{z}(x)}{p_{x}(z)}}_{\eqqcolon\mathsf{U}}\Bigr{)}}-\min{\Bigl{(}\underbrace{\frac{p_{y}(z)}{p_{x}(z)}}_{\eqqcolon\mathsf{V}},\underbrace{\frac{\exp
f(y)}{\exp
f(z)}\,\frac{p_{z}(y)}{p_{x}(z)}}_{\eqqcolon\mathsf{W}}\Bigr{)}}\Big{|}\,p_{x}(\mathrm{d}z)\,.$

Here we note that $\mathsf{U}\geq e^{-4\varepsilon}$ due to $\frac{\exp
f(x)}{\exp f(z)}\geq e^{-\varepsilon}$ and $\frac{p_{z}(x)}{p_{x}(z)}\geq
e^{-3\varepsilon}$ from (7.2) and (7.3).

We now show that under additional conditioning,
$|\log\textsf{V}|\lesssim\varepsilon$ and $\log\textsf{W}\gtrsim-\varepsilon$
on $z\in G_{x}\cap G_{y}\cap B_{x,1}^{c}$. For
$\varphi(\cdot)=\frac{1}{2}\log\det g(\cdot)$ and
$\mathsf{L}:=-\frac{d}{2r^{2}}({\|z-y\|}_{y}^{2}-{\|z-x\|}_{x}^{2})$,

$\displaystyle\log\mathsf{V}$
$\displaystyle=-\frac{d}{2r^{2}}({\|z-y\|}_{y}^{2}-{\|z-x\|}_{x}^{2})+\varphi(y)-\varphi(x)$
$\displaystyle=\textsf{L}+\langle\nabla\varphi(x),y-x\rangle+\underbrace{\frac{1}{2}\langle\nabla^{2}\varphi(x^{*})(y-x),y-x\rangle}_{\text{Use
}\eqref{eq:so-taylor-logdet}}\quad\text{for some }x^{*}\in[x,y]$ (7.6)
$\displaystyle\geq\textsf{L}-{\|g(x)^{-1/2}\nabla\varphi(x)\|}_{2}{\|y-x\|}_{x}-5\underbrace{(1+2{\|x-y\|}_{x})^{2}}_{\leq
2}{\|y-x\|}_{x}^{2}$ $\displaystyle\geq\textsf{L}-2\sqrt{d}\cdot
s\frac{r}{\sqrt{d}}-10s^{2}\frac{r^{2}}{d}\geq\textsf{L}-\varepsilon\,,$ (7.7)

where the inequality follows from $s\leq\frac{\varepsilon}{10}$ and $r\leq
r_{7}(\varepsilon):=1$.

As for W, due to $f(y)\geq f(x)$ and $\exp(f(x)-f(z))\geq\exp(-\varepsilon)$,

$\displaystyle\log\mathsf{W}$ $\displaystyle\geq\log{\Bigl{(}\frac{\exp
f(x)}{\exp
f(z)}\frac{p_{z}(y)}{p_{x}(z)}\Bigr{)}}\geq-\varepsilon-\frac{d}{2r^{2}}({\|z-y\|}_{z}^{2}-{\|z-x\|}_{x}^{2})+\varphi(z)-\varphi(x)$
$\displaystyle\underset{\text{(i)}}{\geq}-\varepsilon-\frac{d}{2r^{2}}{\Bigl{(}{\|z-y\|}_{y}^{2}+2\varepsilon\frac{r^{2}}{d}-{\|z-x\|}_{x}^{2}\Bigr{)}}-2\varepsilon=\textsf{L}-4\varepsilon\,,$
(7.8)

where (i) follows from ${\|z-y\|}_{z}^{2}-{\|z-y\|}_{y}^{2}\leq 2\varepsilon
r^{2}/d$ on $z\in B_{y,2}^{c}$, and $\varphi(z)-\varphi(x)\geq-2\varepsilon$
on $z\in B_{x,3}^{c}$ from (7.4).

Lastly, we show that $|\textsf{L}|$ is bounded by $\mathcal{O}(\varepsilon)$
with high probability (w.r.t. $p_{x}$). Due to affine invariance of the
algorithm, we may assume that $x=0$ and $g(x)=I_{d}$ (so
$p_{x}=\mathcal{N}(0,I_{d})$). Therefore,

$\displaystyle{\|z-y\|}_{y}^{2}-{\|z-x\|}_{x}^{2}$
$\displaystyle={\|z-y\|}_{y}^{2}-{\|z\|}^{2}={\|z\|}_{g(y)-I_{d}}^{2}-2\langle
z,y\rangle_{y}+{\|y\|}_{y}^{2}\,.$

The last term is bounded by $2{\|y\|}^{2}$ due to SC of $g$. Using a tail
bound for Gaussians, we have $\mathbb{P}_{p_{x}}{\bigl{(}|\langle
z,y\rangle_{y}|\geq\frac{r}{\sqrt{d}}\,{\|g(y)y\|}_{2}\cdot
2\log\frac{1}{\varepsilon}\bigr{)}}\leq\varepsilon$ and call this event
$C_{1}$. In addition, SC of $g$ leads to $g(y)\preceq 2I_{d}$, so
${\|g(y)y\|}\leq 2{\|y\|}$.

To bound ${\|z\|}_{g(y)-I_{d}}^{2}$, we note that ${\|y\|}={\|y-x\|}_{x}\leq
1/\sqrt{2}$ and so

$\displaystyle{\|g(y)-I_{d}\|}_{F}$
$\displaystyle\leq(1+2{\|y\|})^{2}{\|y\|}\leq
2s\frac{r}{\sqrt{d}}\,,\quad\text{(Lemma \ref{lem:strongSC-closeness})}$
$\displaystyle\mathbb{E}[{\|z\|}_{g(y)-I_{d}}^{2}]$
$\displaystyle=\frac{r^{2}}{d}\textup{{Tr}}(g(y)-I_{d})\leq\frac{r^{2}}{d}\sqrt{d}\,{\|g(y)-I_{d}\|}_{F}\leq\frac{r^{2}}{d}\cdot
2rs\,.$

By the Hanson-Wright inequality666

######  Lemma (Hanson-Wright; Adapted to Gaussian).

Let $h\sim\mathcal{N}(0,\sigma^{2}I_{d})$ and $M\in\mathbb{R}^{d\times d}$.
Then there exists universal constants $c,K>0$ such that for $t\geq 0$
$\mathbb{P}{\bigl{(}|{\|h\|}_{A}^{2}-\mathbb{E}[{\|h\|}_{A}^{2}]|>t\bigr{)}}\leq
2\exp{\Bigl{(}-c\min{\Bigl{(}\frac{t^{2}}{K^{4}\sigma^{4}{\|M\|}_{F}^{2}},\frac{t}{K^{2}\sigma^{2}{\|M\|}_{2}}\Bigr{)}}\Bigr{)}}\,.$
, for universal constants $K_{1},K_{2}>0$ and $t\geq 0$ it holds that

$\mathbb{P}_{z\sim\mathcal{N}(0,I_{d})}{\bigl{(}|{\|z\|}_{g(y)-I_{d}}^{2}-\mathbb{E}[{\|z\|}_{g(y)-I_{d}}^{2}]|\geq
t\bigr{)}}\leq
2\exp{\Bigl{(}-K_{1}{\Bigl{(}\frac{t^{2}}{K_{2}^{4}\frac{r^{4}}{d^{2}}{\|g(y)-I_{d}\|}_{F}^{2}}\wedge\frac{t}{K_{2}^{2}\frac{r^{2}}{d}{\|g(y)\|}_{2}}\Bigr{)}}\Bigr{)}}\,.$

By taking $r\leq r_{8}(\varepsilon):=\frac{\sqrt{K_{1}}}{2K_{2}^{2}}$ and
$s\leq
s_{2}(\varepsilon):=\varepsilon(1+\sqrt{\log\frac{2}{\varepsilon}})^{-1}$, it
follows that ${\|z\|}_{g(y)-I_{d}}^{2}\leq\frac{2\varepsilon r^{2}}{d}$ with
probability at least $1-\varepsilon$. Denote the complement of this event by
$C_{2}$.

Conditioned on $z\in C_{1}^{c}\cap C_{2}^{c}$, we conclude that

$\displaystyle|{\|z-y\|}_{y}^{2}-{\|z-x\|}_{x}^{2}|$
$\displaystyle\leq{\|z\|}_{g(y)-I_{d}}^{2}+2|\langle
z,y\rangle_{y}|+2{\|y\|}^{2}\leq\frac{2r^{2}\varepsilon}{d}+\frac{8r{\|y\|}}{\sqrt{d}}\,\log\frac{1}{\varepsilon}+2{\|y\|}^{2}\leq\frac{2r^{2}}{d}\cdot
3\varepsilon\,,$

where the last inequality follows from ${\|y\|}\leq\frac{sr}{\sqrt{d}}$ when
$s\leq s_{3}(\varepsilon):=\varepsilon\,(4\log\frac{1}{\varepsilon})^{-1}$.
Hence, $|\textsf{L}|\leq 3\varepsilon$ on $C_{1}^{c}\cap C_{2}^{c}$. Putting
this into (7.7) and (7.8),

$\log\mathsf{V}\geq\exp(-4\varepsilon)\qquad\text{and}\qquad\log\mathsf{W}\geq\exp(-7\varepsilon)\,.$

We can also show $\log\textsf{V}\leq 5\varepsilon$. Conditioned on $z\in
C_{1}^{c}\cap C_{2}^{c}$,

$-\log\mathsf{V}=-\textsf{L}+\varphi(x)-\varphi(y)\geq-3\varepsilon+\varphi(x)-\varphi(y)\geq-5\varepsilon\,,$

since $\varphi(x)-\varphi(y)$ can be lowered bounded by $-2\varepsilon$ as in
(7.6). Hence, $\log\textsf{V}\leq 5\varepsilon$.

For $F:=G_{x}\cap G_{y}\cap B_{x,1}^{c}$ and $C:=(C_{1}\cup C_{2})^{c}$, since
$e^{-4\varepsilon}\leq\mathsf{V}\leq e^{5\varepsilon}$,
$e^{-7\varepsilon}\leq\mathsf{W}$, and $\mathsf{U}\geq e^{-4\varepsilon}$,

$\displaystyle\int_{F}|A(x,z)\,p_{x}(z)-A(y,z)\,p_{y}(z)|\,\mathrm{d}z\leq\int_{C^{c}}(\cdot)\,\mathrm{d}z+\int_{F\cap
C}(\cdot)\,\mathrm{d}z$ $\displaystyle\leq$
$\displaystyle\underbrace{\mathbb{P}_{p_{x}}(C^{c})}_{\leq
2\varepsilon}+2\underbrace{d_{\textrm{{TV}}}(p_{x},p_{y})}_{\leq\varepsilon}+\int_{F\cap
C}(\cdot)\,\mathrm{d}z\leq 4\varepsilon+\int_{F\cap
C}|1\wedge\mathsf{U}-\mathsf{V}\wedge\mathsf{W}|\,p_{x}(\mathrm{d}z)\leq
4\varepsilon+(e^{5\varepsilon}-e^{-4\varepsilon})$ $\displaystyle\leq$
$\displaystyle 18\varepsilon\,.$

Using this, we can bound $\mathcal{C}$ by

$\displaystyle\mathcal{C}$
$\displaystyle\leq\frac{1}{4}+\varepsilon+\frac{1}{2}\int_{F}|A(x,z)\,p_{x}(z)-A(y,z)\,p_{y}(z)|\,\mathrm{d}z\leq\frac{1}{4}+10\varepsilon\,.$

Therefore, $\textsf{II}\leq
3\varepsilon+\mathcal{A}+\mathcal{B}+\mathcal{C}\leq
3\varepsilon+4\varepsilon+\frac{1}{4}+10\varepsilon\leq\frac{1}{4}+17\varepsilon.$
Along with $\textsf{I}\leq\frac{1}{2}+5\varepsilon$, we can conclude that if
$r\leq\min_{i}r_{i}(\varepsilon)$ and $s\leq\min_{i}s_{i}(\varepsilon)$, then
$d_{\textrm{{TV}}}(P_{x},P_{y})\leq\frac{3}{4}+23\varepsilon$. ∎

####  7.1.2 Isoperimetric inequality

We now prove an isoperimetric inequality arising from the a SC barrier. Recall
the _cross-ratio_ _distance_ $d_{K}$ defined on a convex body $K$: for
$x,y\in\textup{{int}}(K)$, suppose that the chord passing through $x,y$ has
endpoints $p$ and $q$ in the boundary $\partial K$ (so the order of points is
$p,x,y,q$), then the cross-ratio distance between $x$ and $y$ is defined by

$d_{K}(x,y)\stackrel{{\scriptstyle\mathrm{{\scriptscriptstyle
def}}}}{{=}}\frac{{\|x-y\|}_{2}{\|p-q\|}_{2}}{{\|p-x\|}_{2}{\|y-q\|}_{2}}\,.$

The first type of isoperimetric inequalities says $\psi_{\pi}\gtrsim
1/\sqrt{\bar{\nu}}$.

###### Proof of Lemma 2.6.

For a ball $B_{r}(0)$ of radius $r>0$ centered at the origin, we define a
convex body $K_{r}:=K\cap B_{r}(0)$ and use $\pi_{r}$ to denote the truncated
distribution of $\pi$ over $K_{r}$. Let $\\{S_{1},S_{2},S_{3}\\}$ be a
partition of $K$ and define $S_{i}^{r}:=S_{i}\cap K_{r}$ for $i\in[3]$. By
Lovász and Vempala (2007, Theorem 2.5), we have

$\pi_{r}(S_{3}^{r})\geq
d_{K_{r}}(S_{1}^{r},S_{2}^{r})\,\pi_{r}(S_{1}^{r})\,\pi_{r}(S_{2}^{r})\,,$

where $d_{K_{r}}(S_{1}^{r},S_{2}^{r})=\inf_{x\in S_{1}^{r},y\in
S_{2}^{r}}d_{K_{r}}(x,y)$. Due to
$d_{K_{r}}(x,y)\geq{\|x-y\|}_{x}/\sqrt{\bar{\nu}}$ for any $x,y\in K_{r}$ (see
Laddha et al. (2020, Lemma 2.3)),

$\pi_{r}(S_{3}^{r})\geq\inf_{x\in S_{1}^{r},\,y\in
S_{2}^{r}}\frac{{\|x-y\|}_{x}}{\sqrt{\bar{\nu}}}\,\pi_{r}(S_{1}^{r})\,\pi_{r}(S_{2}^{r})\geq\frac{1}{\sqrt{\bar{\nu}}}\inf_{x\in
S_{1},\,y\in S_{2}}{\|x-y\|}_{x}\,\pi_{r}(S_{1}^{r})\,\pi_{r}(S_{2}^{r})\,.$

As $r\to\infty$, the bounded convergence theorem implies
$\pi_{r}(S_{i}^{r})\to\pi(S_{i})$ for $i\in[3]$, completing the proof. ∎

We provide the deferred proof for another isoperimetric inequality,
$\psi_{\pi}\gtrsim\sqrt{\alpha}$, originating from $\alpha$-relatively strong-
convexity of the potential with respect to $\nabla^{2}\phi$.

###### Proof of Lemma 2.7.

The proof essentially follows Gopi et al. (2023). Their first proof ingredient
is a modified localization lemma Gopi et al. (2023, Lemma 8); let
$f_{1},f_{2},f_{3},f_{4}$ be non-negative functions on $\mathbb{R}^{d}$ such
that $f_{1}$ and $f_{2}$ are upper semicontinuous, and $f_{3}$ and $f_{4}$ are
lower semicontinuous, and $\phi:\mathbb{R}^{d}\to\mathbb{R}$ be convex. Then
the following are equivalent:

  * •

For any density $\pi:\mathbb{R}^{d}\to\mathbb{R}$ which is $1$-relatively
strongly logconcave in $\phi$,

$\int f_{1}\,\mathrm{d}\pi\cdot\int f_{2}\,\mathrm{d}\pi\leq\int
f_{3}\,\mathrm{d}\pi\cdot\int f_{4}\,\mathrm{d}\pi\,.$

  * •

Let $\int_{E}h:=\int_{0}^{1}h((1-t)\,a+tb)e^{-\gamma t}\,\mathrm{d}t$. Then
$\int_{E}f_{1}e^{-\phi}\cdot\int_{E}f_{2}e^{-\phi}\leq\int_{E}f_{3}e^{-\phi}\cdot\int_{E}f_{4}e^{-\phi}$
for any $a,b\in\mathbb{R}^{d}$ and $\gamma\in\mathbb{R}$.

First of all, this can be generalized to an extended convex function $f$ and
$\phi$, whose values outside of $\textup{{int}}(K)$ are set to $\infty$. Since
the density $\pi$ and a needle $\exp\left(\gamma t-\phi((1-t)a+tb)\right)$ for
$\gamma\in\mathbb{R}$ and $a,b\in\mathbb{R}^{d}$ (induced by the extended $f$
and $\phi$) vanish outside of $\textup{{int}}(K)$, integrands above become
zero on $\textup{{int}}(K)^{c}$, and thus the integrals above remain the same.

As in Gopi et al. (2023, Lemma 9), the proof boils down to the case of
$\alpha=1$, and it suffices to show that there exists a constant $C>0$ such
that

$C\cdot d_{\phi}(S_{1},S_{2})\int_{S_{1}}e^{-f}\cdot\int_{S_{2}}e^{-f}\leq\int
e^{-f}\int_{S_{3}}e^{-f}\,.$

We can replace $S_{i}\leftarrow$ its closure $\bar{S_{i}}$ for $i\in[2]$,
which only increases the LHS. Also, we can replace $S_{3}\leftarrow$ an open
set $\textup{{int}}(K)\backslash\bar{S_{1}}\backslash\bar{S_{2}}$, which does
not change the RHS since the boundary of a convex set is a null set Lang
(1986, Theorem 1). By taking $f_{i}=\mathbf{1}_{S_{i}}$ for $i\in[3]$ and
$f_{4}=(C\,d_{\phi}(S_{1},S_{2}))^{-1}$, we only need to show that for some
$0\leq c<d\leq 1$,

$\displaystyle C\cdot d_{\phi}(S_{1},S_{2})\int_{c}^{d}e^{\gamma
t-\phi((1-t)\,a+tb)}\mathbf{1}_{S_{1}}((1-t)\,a+tb)\,\mathrm{d}t\cdot\int_{c}^{d}e^{\gamma
t-\phi((1-t)\,a+tb)}\mathbf{1}_{S_{2}}((1-t)\,a+tb)\,\mathrm{d}t$
$\displaystyle\leq$ $\displaystyle\int_{c}^{d}e^{\gamma
t-\phi((1-t)\,a+tb)}\,\mathrm{d}t\cdot\int_{c}^{d}e^{\gamma
t-\phi((1-t)\,a+tb)}\mathbf{1}_{S_{3}}((1-t)\,a+tb)\,\mathrm{d}t\,,$

where $\phi((1-t)\,a+b)<\infty$ for $t\in(c,d)$. The rest of the proof is
similar to Gopi et al. (2023, Lemma 9). ∎

###  7.2 Sampling IPM ($\S$3)

####  7.2.1 Well-definedness of sampling IPM

######  Proposition 7.1.

Let $p:\mathbb{R}^{d}\to\mathbb{R}$ be a log-concave density with finite
second moment. Then $p$ is bounded on $\mathbb{R}^{d}$.

###### Proof.

Let $X\sim p$ and denote the mean and covariance of the distribution $p$ by
$\mu:=\mathbb{E}[X]$ and $\Sigma:=\mathbb{E}[(X-\mu)(X-\mu)^{\mathsf{T}}]$.
Then the pushforward $T_{\\#}p$ of $p$ via the map $T:x\mapsto
y:=\Sigma^{-1/2}(x-\mu)$ is an isotropic log-concave, and satisfy
$(T_{\\#}p)(y)=\frac{p(x)}{|\det T|}$. Since $T_{\\#}p$ is bounded on
$\mathbb{R}^{d}$ Lovász and Vempala (2007, Theorem 5.14 (e)), $p$ is bounded
as well. ∎

Next, we show that every measure appearing within the sampling IPM is
integrable.

###### Proof of Proposition 3.1.

Recall that we may assume $\phi\geq 0$. Hence, all $\mu_{i}$’s in Phase 3 and
4 are well-defined

$\int_{K}\exp{\Bigl{(}-{\bigl{(}f(x)+\frac{\phi(x)}{\sigma_{i}^{2}}\bigr{)}}\Bigr{)}}\,\mathrm{d}x\leq\int_{K}\exp(-f(x))\,\mathrm{d}x<\infty\,.$

In particular, $\exp{\bigl{(}-(f+\frac{\phi}{\nu/d})\bigr{)}}$ is integrable
with finite second moment. By Proposition 7.1, $f(x)+\frac{\phi(x)}{\nu/d}$
achieves a global minimum $m$ in $K$. As
$\sigma_{i}^{2}\leq\sigma_{i_{0}}^{2}=\nu/d$ in Phase 2, we have

$\displaystyle\int_{K}\exp{\Bigl{(}-\frac{\sigma_{i_{0}}^{2}f+\phi}{\sigma_{i_{0}}^{2}}\Bigr{)}}=\int_{K}\exp{\Bigl{(}-\frac{\sigma_{i_{0}}^{2}f+\phi-\min(\sigma_{i_{0}}^{2}f+\phi)}{\sigma_{i_{0}}^{2}}-\frac{\min(\sigma_{i_{0}}^{2}f+\phi)}{\sigma_{i_{0}}^{2}}\Bigr{)}}$
$\displaystyle\geq\int_{K}\exp{\Bigl{(}-\frac{\bar{f}+\phi-\sigma_{i_{0}}^{2}m}{\sigma_{i}^{2}}-m\Bigr{)}}=\exp{\Bigl{(}m{\bigl{(}\frac{\sigma_{i_{0}}^{2}}{\sigma_{i}^{2}}-1\bigr{)}}\Bigr{)}}\int_{K}\exp{\Bigl{(}-\frac{\bar{f}+\phi}{\sigma_{i}^{2}}\Bigr{)}}\,,$

where the inequality holds due to
$\min(\sigma_{i_{0}}^{2}f+\phi)=\sigma_{i_{0}}^{2}m$ and
$\bar{f}=\sigma_{i_{0}}^{2}f$. Therefore, $\mu_{i}$’s in Phase 2 are also
well-defined. ∎

####  7.2.2 Closeness of distributions in sampling IPM

We begin with closeness between
$\mathcal{N}{\bigl{(}x^{*},\frac{\sigma_{0}^{2}}{1+\nu\beta
d^{-1}}g(x^{*})^{-1}\bigr{)}}\cdot\mathbf{1}_{\mathcal{D}_{g}^{3\sigma_{0}\sqrt{d}}(x^{*})}$
and $\exp{\bigl{(}-\frac{\bar{f}+\phi}{\sigma_{0}^{2}}\bigr{)}}$ in Phase 1.

###### Proof of Lemma 3.5.

Let $\gamma=9$, $r=(\gamma\sigma_{0}^{2}d)^{1/2}<0.01$, $\psi:=\bar{f}+\phi$,
and $S=\\{x\in K:\psi(x)\leq\psi(x^{*})+r^{2}/4\\}$. For
$\widetilde{\mu}_{0}=\exp(-\psi/\sigma_{0}^{2})\cdot\mathbf{1}_{K}\propto\mu_{0}$
and $x\in S$, we have $\mu_{0}(x)\geq e^{-\gamma d}\mu_{0}(x^{*}).$ Due to
$\mu_{0}(S^{c})\leq\exp(-\gamma d/3)$ (Lemma 3.3), it follows that
$1=\mu_{0}(S)+\mu_{0}(S^{c})\leq\mu_{0}(S)+\exp(-\gamma d/3)$ and

$1\leq{\bigl{(}1+2\exp(-\gamma
d/3)\bigr{)}}\,\mu_{0}(S)={\bigl{(}1+2\exp(-\gamma
d/3)\bigr{)}}\,\widetilde{\mu}_{0}(S)/\widetilde{\mu}_{0}(\mathbb{R}^{d})\,.$
(7.9)

We show $S\subset D=\mathcal{D}_{g}^{3\sigma_{0}\sqrt{d}}(x^{*})$. For $x\in
S$, use Taylor’s expansion of $\psi$ at $x^{*}$: for some
$\bar{x}\in[x^{*},x]$

$\displaystyle\psi(x)-\psi(x^{*})$
$\displaystyle=\frac{1}{2}(x-x^{*})^{\mathsf{T}}\nabla^{2}\psi(\bar{x})(x-x^{*})\geq\frac{1}{2}(x-x^{*})^{\mathsf{T}}\nabla^{2}\phi(\bar{x})(x-x^{*})\,.$
(7.10)

As $\psi(x)-\psi(x^{*})\leq r^{2}/4$ on $x\in S$, we have
${\|\bar{x}-x^{*}\|}_{\bar{x}}^{2}\leq{\|x-x^{*}\|}_{\bar{x}}^{2}\leq
2(\psi(x)-\psi(x^{*}))\leq r^{2}/2$. Thus, by self-concordance of $\phi$

$\exp(-3r)\,{\|x-x^{*}\|}_{x^{*}}^{2}\leq{\|x-x^{*}\|}_{\bar{x}}^{2}\leq\exp(3r)\,{\|x-x^{*}\|}_{x^{*}}^{2}\,,$
(7.11)

and it follows that ${\|x-x^{*}\|}_{x^{*}}^{2}\leq r^{2}$, showing $S\subset
D$.

Combining (7.10), (7.11), and $(1+\nu\alpha
d^{-1})\,\nabla^{2}\phi\preceq\nabla^{2}\psi\preceq(1+\nu\beta
d^{-1})\,\nabla^{2}\phi$, we have

$\frac{\exp(-3r)}{2}{\Bigl{(}1+\frac{\nu\alpha}{d}\Bigr{)}}\,{\|x-x^{*}\|}_{x^{*}}^{2}\underset{(*)}{\leq}\psi(x)-\psi(x^{*})\underset{(\\#)}{\leq}\frac{\exp(3r)}{2}{\Bigl{(}1+\frac{\nu\beta}{d}\Bigr{)}}\,{\|x-x^{*}\|}_{x^{*}}^{2}\,,$
(7.12)

and thus for a constant $c:=1+\nu\beta d^{-1}$ and function
$h(x):=-(2\sigma_{0}^{2})^{-1}{\|x-x^{*}\|}_{x^{*}}^{2}$,

$\displaystyle{\|\mu/\mu_{0}\|}=\mathbb{E}_{\mu}{\bigl{[}\frac{\mathrm{d}\mu}{\mathrm{d}\mu_{0}}\bigr{]}}=\frac{\int_{D}\exp{\Bigl{(}-\frac{c}{\sigma_{0}^{2}}{\|x-x^{*}\|}_{x^{*}}^{2}+\frac{\psi}{\sigma_{0}^{2}}\Bigr{)}}\cdot\widetilde{\mu}_{0}(\mathbb{R}^{d})}{{\Bigl{[}\int_{D}\exp{\Bigl{(}-\frac{c}{2\sigma_{0}^{2}}\,{\|x-x^{*}\|}_{x^{*}}^{2}\Bigr{)}}\Bigr{]}}^{2}}$
$\displaystyle\underset{\text{(\ref{eq:intp-
intSp})}}{\leq}\frac{1}{{\Bigl{[}\int_{D}\exp(c\cdot
h)\Bigr{]}}^{2}}\int_{D}\exp{\Bigl{(}-\frac{c}{\sigma_{0}^{2}}{\|x-x^{*}\|}_{x^{*}}^{2}+\underbrace{\frac{\psi}{\sigma_{0}^{2}}}_{\text{Use
}(\\#)\text{ in (\ref{eq:approx-psigap})}}\Bigr{)}}{\bigl{(}1+2\exp(-\gamma
n/3)\bigr{)}}\underbrace{\widetilde{\mu}_{0}(S)}_{\text{Use }(*)}$
$\displaystyle\lesssim\frac{\int_{D}\exp{\Bigl{(}-\frac{1}{2\sigma_{0}^{2}}{\bigl{(}2c-e^{3r}(1+\nu\beta
d^{-1})\bigr{)}}\,{\|x-x^{*}\|}_{x^{*}}^{2}\Bigr{)}}\int_{D}\exp{\bigl{(}-\frac{1}{2\sigma_{0}^{2}}e^{-3r}(1+\nu\alpha
d^{-1})\,{\|x-x^{*}\|}_{x^{*}}^{2}\bigr{)}}}{{\Bigl{[}\int_{D}\exp(c\cdot
h)\Bigr{]}}^{2}}$
$\displaystyle=\underbrace{\frac{\int_{D}\exp{\Bigl{(}{\bigl{(}2c-c\,e^{3r}\bigr{)}}\,h(x)\Bigr{)}}\cdot\int_{D}\exp{\bigl{(}c\,e^{3r}h(x)\bigr{)}}}{{\Bigl{[}\int_{D}\exp(c\cdot
h)\Bigr{]}}^{2}}}_{=:\text{{A}}}\,\underbrace{\frac{\int_{D}\exp{\bigl{(}e^{-3r}(1+\nu\alpha
d^{-1})\,h(x)\bigr{)}}}{\int_{D}\exp{\bigl{(}c\,e^{3r}h(x)\bigr{)}}}}_{=:\text{{B}}}\,.$

As for A, Lemma 3.2 leads to

A
$\displaystyle\leq{\Bigl{(}\frac{c^{2}}{(2c-c\,e^{3r})\,ce^{3r}}\Bigr{)}}^{d}={\Bigl{(}\frac{1}{(2-e^{3r})e^{3r}}\Bigr{)}}^{d}=(1+\mathcal{O}(r^{2}))^{d}=\mathcal{O}(1)\,.$

As for B, let $c_{1}=e^{-3r}\,(1+\nu\alpha d^{-1})$ and
$c_{2}=e^{3r}\,(1+\nu\beta d^{-1})$. With the change of variable
$y=\sigma_{0}^{-1}\sqrt{c_{i}}g(x^{*})^{1/2}(x-x^{*})$ for $i\in[2]$, it
follows that for $r_{i}:=r\sigma_{0}^{-1}\sqrt{c_{i}}(\geq 3\sqrt{d})$

B
$\displaystyle={\Bigl{(}\frac{c_{2}}{c_{1}}\Bigr{)}}^{d/2}\frac{\int_{B_{r_{1}}}\exp{\bigl{(}-\frac{1}{2}{\|y\|}^{2}\bigr{)}}\,\mathrm{d}y}{\int_{B_{r_{2}}}\exp{\bigl{(}-\frac{1}{2}{\|y\|}^{2}\bigr{)}}\,\mathrm{d}y}\leq{\Bigl{(}\frac{c_{2}}{c_{1}}\Bigr{)}}^{d/2}\lesssim{\Bigl{(}\frac{\nu\beta+d}{\nu\alpha+d}\Bigr{)}}^{d}\,e^{3rd}\lesssim{\Bigl{(}\frac{\nu\beta+d}{\nu\alpha+d}\Bigr{)}}^{d}\,.\qed$

Now we show closeness of two consecutive distributions in Phase 2, i.e.,
$\sigma_{i+1}^{2}=\sigma_{i}^{2}{\bigl{(}1+\frac{1}{\sqrt{d}}\bigr{)}}$.

###### Proof of Lemma 3.6.

Observe that for $\psi=\bar{f}+\phi=\frac{\nu}{d}f+\phi$ on $K$ and
$F(\sigma^{2})=\int_{K}\exp(-\psi/\sigma^{2})$,

$\displaystyle{\|\mu_{i}/\mu_{i+1}\|}$
$\displaystyle=\mathbb{E}_{\mu_{i}}{\bigl{[}\frac{\mathrm{d}\mu_{i}}{\mathrm{d}\mu_{i+1}}\bigr{]}}=\frac{\int_{K}\exp{\bigl{(}-2\frac{\psi}{\sigma_{i}^{2}}+\frac{\psi}{\sigma_{i+1}^{2}}\bigr{)}}\cdot\int_{K}\exp{\bigl{(}-\frac{\psi}{\sigma_{i+1}^{2}}\bigr{)}}}{\left(\int_{K}\exp{\bigl{(}-\frac{\psi}{\sigma_{i}^{2}}\bigr{)}}\right)^{2}}=\frac{F{\bigl{(}{\bigl{(}\frac{2}{\sigma_{i}^{2}}-\frac{1}{\sigma_{i+1}^{2}}\bigr{)}}^{-1}\bigr{)}}\,F(\sigma_{i+1}^{2})}{F(\sigma_{i}^{2})^{2}}\,.$

By Lemma 3.2, the function $a^{d}F{\bigl{(}\frac{\sigma^{2}}{a}\bigr{)}}$ is
log-concave in $a$. Using the definition with endpoints
$\frac{2}{\sigma_{i}^{2}}-\frac{1}{\sigma_{i+1}^{2}}$ and
$\frac{1}{\sigma_{i+1}^{2}}$, and the middle point $\frac{1}{\sigma_{i}^{2}}$,
we obtain

$\frac{F{\bigl{(}{\bigl{(}\frac{2}{\sigma_{i}^{2}}-\frac{1}{\sigma_{i+1}^{2}}\bigr{)}}^{-1}\bigr{)}}\,F(\sigma_{i+1}^{2})}{F(\sigma_{i}^{2})^{2}}\leq\Biggl{(}\frac{{\bigl{(}\frac{1}{\sigma_{i}^{2}}\bigr{)}}^{2}}{{\bigl{(}\frac{2}{\sigma_{i}^{2}}-\frac{1}{\sigma_{i+1}^{2}}\bigr{)}}\,\frac{1}{\sigma_{i+1}^{2}}}\Biggr{)}^{d}=\Biggl{(}\frac{{\bigl{(}1+\frac{1}{\sqrt{d}}\bigr{)}}^{2}}{1+\frac{2}{\sqrt{d}}}\Biggr{)}^{d}\leq{\Bigl{(}1+\frac{1}{d}\Bigr{)}}^{d}\leq
e\,.\qed$

We now establish closeness in Phase 3, during which we use the update of
$\sigma_{i+1}^{2}=\sigma_{i}^{2}{\bigl{(}1+\frac{\sigma_{i}}{\sqrt{\nu}}\bigr{)}}$.

###### Proof of Lemma 3.7.

The update is $\sigma_{i+1}^{2}=\sigma_{i}^{2}\left(1+r\right)$ for
$r=\frac{\sigma_{i}}{\sqrt{\nu}}$. For $s:=\frac{r}{1+r}$,
$\sigma:=\sigma_{i}$, and $F(\sigma^{2})=\int\exp(-f-\phi/\sigma^{2})$, we
have

$\displaystyle{\|\mu_{i}/\mu_{i+1}\|}$
$\displaystyle=\frac{F{\bigl{(}{\bigl{(}\frac{2}{\sigma_{i}^{2}}-\frac{1}{\sigma_{i+1}^{2}}\bigr{)}}^{-1}\bigr{)}}\,F(\sigma_{i+1}^{2})}{F(\sigma_{i}^{2})^{2}}=\frac{F{\bigl{(}\frac{\sigma^{2}}{1+s}\bigr{)}}\,F{\bigl{(}\frac{\sigma^{2}}{1-s}\bigr{)}}}{F(\sigma^{2})^{2}}\,.$

Let $g(t):=\log F{\bigl{(}\frac{\sigma^{2}}{t}\bigr{)}}$ for $t>0$. Then,

$\displaystyle\log{\|\mu_{i}/\mu_{i+1}\|}$
$\displaystyle=g(1+s)+g(1-s)-2g(1)=\int_{0}^{s}{\bigl{(}g^{\prime}(1+t)-g^{\prime}(1-t)\bigr{)}}\,\mathrm{d}t=\int_{0}^{s}\int_{1-t}^{1+t}g^{\prime\prime}(q)\,\mathrm{d}q\,\mathrm{d}t$
(7.13)

and for a probability measure
$\nu_{q}\propto\exp{\bigl{(}-f-\frac{q\phi}{\sigma^{2}}\bigr{)}}$,

$\displaystyle g^{\prime\prime}(q)$
$\displaystyle=\frac{\mathrm{d}^{2}}{\mathrm{d}q^{2}}{\Bigl{[}\log\int_{K}\exp{\Bigl{(}-f-\frac{q\phi}{\sigma^{2}}\Bigr{)}}\Bigr{]}}=-\frac{1}{\sigma^{2}}\,\frac{\mathrm{d}}{\mathrm{d}q}\Bigg{[}\frac{\int_{K}\phi\cdot\exp{\Bigl{(}-f-\frac{q\phi}{\sigma^{2}}\Bigr{)}}}{\int_{K}\exp{\Bigl{(}-f-\frac{q\phi}{\sigma^{2}}\Bigr{)}}}\Biggr{]}$
$\displaystyle=-\frac{1}{\sigma^{2}}\,\Bigg{(}-\frac{1}{\sigma^{2}}\,\frac{\int_{K}\phi^{2}\cdot\exp{\Bigl{(}-f-\frac{q\phi}{\sigma^{2}}\Bigr{)}}}{\int_{K}\exp{\Bigl{(}-f-\frac{q\phi}{\sigma^{2}}\Bigr{)}}}+\frac{1}{\sigma^{2}}\,\frac{{\Bigl{[}\int_{K}\phi\cdot\exp{\Bigl{(}-f-\frac{q\phi}{\sigma^{2}}\Bigr{)}}\Bigr{]}}^{2}}{{\Bigl{[}\int_{K}\exp{\Bigl{(}-f-\frac{q\phi}{\sigma^{2}}\Bigr{)}}\Bigr{]}}^{2}}\Biggr{)}$
$\displaystyle=\frac{1}{\sigma^{4}}\,{\Bigl{(}\mathbb{E}_{\nu_{q}}[\phi^{2}]-(\mathbb{E}_{\nu_{q}}\phi)^{2}\Bigr{)}}=\frac{1}{\sigma^{4}}\,\mathrm{Var}_{\nu_{q}}\phi\,.$

By the Brascamp-Lieb inequality with
$V(\cdot):=f(\cdot)+\frac{q\phi(\cdot)}{\sigma^{2}}$,

$\displaystyle\mathrm{Var}_{\nu_{q}}\phi$
$\displaystyle\leq\mathbb{E}_{\nu_{q}}{\bigl{[}(\nabla\phi)^{\mathsf{T}}{\bigl{(}\nabla^{2}V\bigr{)}}^{-1}\nabla\phi\bigr{]}}\leq\frac{\sigma^{2}}{q}\,\mathbb{E}_{\nu_{q}}{\|\nabla\phi\|}_{(\nabla^{2}\phi)^{-1}}^{2}\leq\frac{\sigma^{2}\nu}{q}\,,$

and thus $g^{\prime\prime}(q)\leq\frac{\nu}{q\sigma^{2}}.$ Putting this back
to (7.13), we acquire

$\displaystyle\log{\|\mu_{i}/\mu_{i+1}\|}$
$\displaystyle\leq\frac{\nu}{\sigma^{2}}\int_{0}^{s}\int_{1-t}^{1+t}\frac{1}{q}\,\mathrm{d}q\,\mathrm{d}t=\frac{\nu}{\sigma^{2}}\int_{0}^{s}{\bigl{(}\log(1+t)-\log(1-t)\bigr{)}}\,\mathrm{d}t$
$\displaystyle=\frac{\nu}{\sigma^{2}}{\bigl{(}(1+s)\,\log(1+s)+(1-s)\,\log(1-s)\bigr{)}}\lesssim\frac{\nu
s^{2}}{\sigma^{2}}\,.$ (7.14)

It follows from $s=\frac{r}{1+r}$ and $r=\frac{\sigma}{\sqrt{\nu}}$ that
$\mu_{i}$ is an $\mathcal{O}(1)$-warm start for $\mu_{i+1}$.

For Phase 4, observe that for $\mu\propto\exp(-f-\phi/\sigma^{2})$ with
$\sigma^{2}=\nu$,

$\displaystyle{\|\mu/\pi\|}$
$\displaystyle=\frac{\int_{K}\exp{\bigl{(}-f-\frac{\phi}{\sigma^{2}/2}\bigr{)}}\cdot\int_{K}\exp(-f)}{{\Bigl{[}\int_{K}\exp{\Bigl{(}-f-\frac{\phi}{\sigma^{2}}\Bigr{)}}\Bigr{]}}^{2}}\underset{\text{(i)}}{=}\lim_{r\to
1}\frac{F{\bigl{(}\frac{\sigma^{2}}{1+r}\bigr{)}}\cdot
F{\bigl{(}\frac{\sigma^{2}}{1-r}\bigr{)}}}{F(\sigma^{2})}$
$\displaystyle\underset{\text{(ii)}}{\leq}\lim_{r\to
1}\exp{\Bigl{(}\mathcal{O}(1)\frac{\nu}{\sigma^{2}}\,{\bigl{(}(1+r)\,\log(1+r)+(1-r)\,\log(1-r)\bigr{)}}\Bigr{)}}=\exp{\Bigl{(}\mathcal{O}(1)\frac{\nu}{\sigma^{2}}\Bigr{)}}=\exp(\mathcal{O}(1))\,.$

where (i) holds due to the monotone convergence theorem, and (ii) follows from
(7.14). Therefore, $\mu$ serves as an $\mathcal{O}(1)$-warm start for $\pi$. ∎

######  Remark 7.2 (Coupling argument).

The total number of measures involved in Algorithm 3 is
$m:=\mathcal{O}(\sqrt{d})$. Let $(X_{1},\dots,X_{m})$ be a sequence of samples
provided by Algorithm 3, and $(\bar{X}_{1},\dots,\bar{X}_{m})$ be a sequence
of samples where each sample is drawn from the _actual_ target distributions
$\\{\mu_{\sigma^{2}}\\}$. Conditioned on events $X_{i}=\bar{X}_{i}$, Algorithm
3 ensures that there is a coupling such that
$\mathbb{P}(X_{i+1}=\bar{X}_{i+1}\mid X_{i}=\bar{X}_{i})\geq
1-\frac{\varepsilon}{\sqrt{d}}$ due to $\varepsilon/\sqrt{d}$ TV-distance
guarantee. Combining these couplings,

$\mathbb{P}\left(X_{i}=\bar{X_{i}}\ \forall
i\in[m]\right)=\mathbb{P}(X_{1}=\bar{X}_{1})\cdot\prod_{i=2}^{m}\mathbb{P}(X_{i}=\bar{X}_{i}\mid
X_{i-1}=\bar{X}_{i-1})\geq 1-\varepsilon\,.$

Thus, it leads to a coupling between $X_{m}$ and $\bar{X}_{m}$ such that
$\mathbb{P}(X_{m}=\bar{X}_{m})\geq 1-\varepsilon$, so $\textup{{law}}(X_{m})$
is within $\varepsilon$-TV distance to $\pi=\textup{{law}}(\bar{X}_{m})$.

###  7.3 Self-concordance theory ($\S$4)

####  7.3.1 Basic properties: strong self-concordance

We show that $2(g_{1}+g_{2})$ is SSC if $g_{1}$ and $g_{2}$ are SSC.

###### Proof of Lemma 4.5.

For fixed $x\in K_{1}\cap K_{2}$ and $h\in\mathbb{R}^{d}$, let
$\mathrm{D}g_{i}:=\mathrm{D}g_{i}(x)[h]$ for $i=1,2$. Note that

$\displaystyle{\|(g_{1}+g_{2})^{-\frac{1}{2}}\mathrm{D}(g_{1}+g_{2})\,(g_{1}+g_{2})^{-\frac{1}{2}}\|}_{F}$
$\displaystyle\leq\sum_{i=1}^{2}{\|(g_{1}+g_{2})^{-\frac{1}{2}}\mathrm{D}g_{i}\,(g_{1}+g_{2})^{-\frac{1}{2}}\|}_{F}=\sum_{i=1}^{2}\sqrt{\textup{{Tr}}{\bigl{(}(g_{1}+g_{2})^{-1}\mathrm{D}g_{i}\,(g_{1}+g_{2})^{-1}\mathrm{D}g_{i}\bigr{)}}}$
$\displaystyle={\Bigl{[}\textup{{Tr}}{\Bigl{(}{\bigl{(}\underbrace{I+g_{1}^{-\frac{1}{2}}g_{2}g_{1}^{-\frac{1}{2}}}_{=:E_{1}}\bigr{)}}^{-1}\underbrace{g_{1}^{-\frac{1}{2}}\mathrm{D}g_{1}\,g_{1}^{-\frac{1}{2}}}_{=:T_{1}}{\bigl{(}I+g_{1}^{-\frac{1}{2}}g_{2}g_{1}^{-\frac{1}{2}}\bigr{)}}^{-1}g_{1}^{-\frac{1}{2}}\mathrm{D}g_{1}\,g_{1}^{-\frac{1}{2}}\Bigr{)}}\Bigr{]}}^{1/2}$
$\displaystyle\qquad+{\Bigl{[}\textup{{Tr}}{\Bigl{(}{\bigl{(}\underbrace{I+g_{2}^{-\frac{1}{2}}g_{1}g_{2}^{-\frac{1}{2}}}_{=:E_{2}}\bigr{)}}^{-1}\underbrace{g_{2}^{-\frac{1}{2}}\mathrm{D}g_{2}\,g_{2}^{-\frac{1}{2}}}_{=:T_{2}}{\bigl{(}I+g_{2}^{-\frac{1}{2}}g_{1}g_{2}^{-\frac{1}{2}}\bigr{)}}^{-1}g_{2}^{-\frac{1}{2}}\mathrm{D}g_{2}\,g_{2}^{-\frac{1}{2}}\bigg{)}\Bigr{)}}\Bigr{]}}^{1/2}$
$\displaystyle=\sum_{i=1}^{2}\sqrt{\textup{{Tr}}(E_{i}^{-1}T_{i}E_{i}^{-1}T_{i})}\leq\sum_{i=1}^{2}\sqrt{\textup{{Tr}}(T_{i}E_{i}^{-2}T_{i})}\,,$

where we used the Cauchy-Schwarz inequality
$\textup{{Tr}}(A^{2})\leq\textup{{Tr}}(A^{\mathsf{T}}A)$ in the last line. It
follows from $I\preceq E_{i}$ that $I\preceq E_{i}^{2}$ and $I\succeq
E_{i}^{-2}\succ 0$. Therefore,

$\displaystyle\sum_{i=1}^{2}\sqrt{\textup{{Tr}}(T_{i}E_{i}^{-2}T_{i})}$
$\displaystyle\leq\sum_{i=1}^{2}{\|T_{i}\|}_{F}\leq
2\sum_{i=1}^{2}{\|h\|}_{g_{i}(x)}^{2}\leq
2\sqrt{2}{\|h\|}_{(g_{1}+g_{2})(x)}\,.$

Putting these together completes the proof. ∎

####  7.3.2 Basic properties: lower trace self-concordance

We now show that if $g$ is HSC, then $dg$ is SLTSC.

###### Proof of Lemma 4.13.

We first consider when $\bar{g}$ is positive definite on $K$. By HSC of
$\bar{g}$, it holds that
$-{\|h\|}_{\bar{g}}^{2}\,\bar{g}\lesssim\mathrm{D}^{2}\bar{g}[h,h]$, and thus

$-\frac{1}{d}\,{\|h\|}_{g}^{2}\,(g^{\prime}+g)^{-\frac{1}{2}}g\,(g^{\prime}+g)^{-\frac{1}{2}}\lesssim(g^{\prime}+g)^{-\frac{1}{2}}\mathrm{D}^{2}g[h,h]\,(g^{\prime}+g)^{-\frac{1}{2}}\,.$

Hence,

$\displaystyle\textup{{Tr}}{\bigl{(}(g^{\prime}+g)^{-1}\mathrm{D}^{2}g[h,h]\bigr{)}}$
$\displaystyle\gtrsim-\frac{1}{d}\,{\|h\|}_{g}^{2}\,\textup{{Tr}}{\Bigl{(}(g^{\prime}+g)^{-\frac{1}{2}}g\,(g^{\prime}+g)^{-\frac{1}{2}}\Bigr{)}}=-\frac{1}{d}\,{\|h\|}_{g}^{2}\,\textup{{Tr}}{\bigl{(}g^{\frac{1}{2}}(g^{\prime}+g)^{-1}g^{\frac{1}{2}}\bigr{)}}$
$\displaystyle\geq-\frac{1}{d}\,{\|h\|}_{g}^{2}\,\textup{{Tr}}(g^{\frac{1}{2}}g^{-1}g^{\frac{1}{2}})=-{\|h\|}_{g}^{2}\,.$

When $g$ is singular, we consider
$\bar{g}_{\varepsilon}=\bar{g}+\frac{\varepsilon}{d}I\in\mathbb{S}_{++}^{d}$
for $\varepsilon>0$. Then $\bar{g}_{\varepsilon}$ is HSC, so for
$g_{\varepsilon}=d\bar{g}_{\varepsilon}$

$\textup{{Tr}}{\bigl{(}(g^{\prime}+g_{\varepsilon})^{-1}\mathrm{D}^{2}g[h,h]\bigr{)}}\gtrsim-{\|h\|}_{g_{\varepsilon}}^{2}\,.$

From
$(g^{\prime}+g_{\varepsilon})^{-1}=\frac{1}{\det(g^{\prime}+g_{\varepsilon})}\,\text{adj}(g^{\prime}+g_{\varepsilon})$,
the LHS is continuous in $\varepsilon$, and the RHS is too clearly. Sending
$\varepsilon\to 0$ completes the proof. ∎

####  7.3.3 Basic properties: strongly average self-concordance

To prove Lemma 4.15, we first recall a concentration bound.

######  Lemma 7.3 (Narayanan (2016), Lemma 4).

Let $h$ be drawn from $\mathbb{S}^{d-1}$ uniformly at random. For any odd $k$,
$C^{k}$-smooth $F:\mathbb{R}^{d}\to\mathbb{R}$, and $\varepsilon>0$,

$\mathbb{P}_{h}{\Bigl{(}|\mathrm{D}^{k}F(x)[h^{\otimes
k}]|>k\varepsilon\cdot\sup_{{\|v\|}\leq 1}\mathrm{D}^{k}F(x)[v^{\otimes
k}]\Bigr{)}}\leq\exp{\Bigl{(}-\frac{d\varepsilon^{2}}{2}\Bigr{)}}\,.$

We show that if $g$ is HSC, then $dg$ is SASC, using this lemma and following
Narayanan (2016).

###### Proof of Lemma 4.15.

Let $g=d\,\nabla^{2}\phi$ and consider
$g^{\prime}:\textup{{int}}(K)\to\mathbb{S}_{+}^{d}$ such that
$\bar{g}=g+g^{\prime}$ is PD. For fixed $w\in\mathbb{R}^{d}$, apply Taylor’s
expansion to $\varphi(z):={\|w\|}_{g(z)}^{2}$ at $z=x$, so there exists
$p_{w}\in[x,z]$ such that
$w^{\mathsf{T}}g(z)w=w^{\mathsf{T}}g(x)w+\mathrm{D}g(x)[z,w,w]+\frac{1}{2}\,\mathrm{D}^{2}g(p_{w})[z,z,w,w].$
Putting $z=w$ here,

$|{\|z\|}_{g(z)}^{2}-{\|z\|}_{g(x)}^{2}|\leq|\mathrm{D}^{3}g(x)[z^{\otimes
3}]|+\frac{1}{2}|\mathrm{D}^{2}g(p_{z})[z^{\otimes 4}]|\,.$

Going forward, we can assume that $x=0$ and $\bar{g}(x)=I$ due to affine
invariance, and then $z$ equals $rh/\sqrt{d}$ for $h\sim\mathcal{N}(0,I_{d})$
in law. Using a standard tail bound on the standard Gaussian, we have
$\mathbb{P}_{h}({\|h\|}\geq-\sqrt{d}\cdot 2\log\varepsilon)\leq\varepsilon.$
Call this event $B_{1}$. In addition, Lemma 7.3 implies that

$\mathbb{P}{\Bigl{(}\Big{|}\mathrm{D}^{3}\phi(x){\Bigl{[}\frac{h^{\otimes
3}}{{\|h\|}^{3}}\Bigr{]}}\Big{|}\geq
3\frac{\varepsilon}{\sqrt{d}}\cdot\sup_{{\|v\|}\leq
1}\mathrm{D}^{3}\phi(x)[v^{\otimes 3}]\Bigr{)}}\leq\varepsilon\,,$

and call this event $B_{2}$. Conditioned on $B_{2}^{c}$,

$\displaystyle\Big{|}\mathrm{D}^{3}\phi(x){\Bigl{[}\frac{h^{\otimes
3}}{{\|h\|}^{3}}\Bigr{]}}\Big{|}$
$\displaystyle\leq\frac{3\varepsilon}{\sqrt{d}}\,\sup_{{\|v\|}\leq
1}\mathrm{D}^{3}\phi(x)[v^{\otimes
3}]\leq\frac{6\varepsilon}{\sqrt{d}}\,\sup_{{\|v\|}\leq
1}{\|v\|}_{g(x)/d}^{3}\leq\frac{6\varepsilon}{d^{2}}\,\sup_{{\|v\|}\leq
1}{\|v\|}_{g(x)}^{3}\underbrace{\leq}_{g(x)\preceq
I_{d}}\frac{6\varepsilon}{d^{2}}\,.$

Hence, conditioned on $z\in B_{1}^{c}\cap B_{2}^{c}$

$\displaystyle|\mathrm{D}^{3}g(x)[z^{\otimes 3}]|$
$\displaystyle=\frac{r^{3}}{\sqrt{d}}\,\mathrm{D}^{3}\phi(x)[h^{\otimes
3}]\leq\frac{r^{3}}{\sqrt{d}}\,\frac{6\varepsilon}{d^{2}}\,{\|h\|}^{3}\leq\frac{r^{2}}{d}\cdot
48r\varepsilon{\Bigl{(}\log\frac{1}{\varepsilon}\Bigr{)}}^{3}\,.$

By taking $r_{1}(\varepsilon)$ so that
$-48r_{1}\varepsilon\,(\log\varepsilon)^{3}\leq\varepsilon$, we can ensure
$|\mathrm{D}^{3}g(x)[z^{\otimes 3}]|\leq\varepsilon r^{2}/d$ for any $r\leq
r_{1}(\varepsilon)$.

As for $|\mathrm{D}^{2}g(p_{z})[z^{\otimes 4}]|$, HSC of $\phi$ and Lemma 4.4
lead to

$\displaystyle\frac{1}{2}\,|\mathrm{D}^{2}g(p_{z})[z^{\otimes 4}]|$
$\displaystyle\leq
3d\,{\|z\|}_{\nabla^{2}\phi(p_{z})}^{4}\leq\frac{3}{d}{\|z\|}_{\nabla^{2}\phi(x)}^{4}\,(1+2\,{\|z\|}_{\nabla^{2}\phi(x)}^{2})^{2}=\frac{3}{d}\,{\|z\|}_{g(x)}^{4}\,{\bigl{(}1+\frac{2}{d}\,{\|z\|}_{g(x)}^{2}\bigr{)}}^{2}$
$\displaystyle\underset{g\preceq
I_{d}}{\leq}\frac{3}{d}{\|z\|}^{4}{\bigl{(}1+\frac{2}{d}\,{\|z\|}^{2}\bigr{)}}^{2}=\frac{3}{d}\,\frac{r^{4}}{d^{2}}\,{\|h\|}^{4}{\Bigl{(}1+\frac{2r^{2}}{d^{2}}{\|h\|}^{2}\Bigr{)}}^{2}$
$\displaystyle\leq\frac{r^{2}}{d}\cdot
3r^{2}\,{\bigl{(}2\log\frac{1}{\varepsilon}\bigr{)}}^{4}{\Bigl{(}1+2r^{2}{\bigl{(}2\log\frac{1}{\varepsilon}\bigr{)}}^{4}\Bigr{)}}^{2}\,.$

By taking $r_{2}(\varepsilon)$ and $r_{3}(\varepsilon)$ so that
${\Bigl{(}1+2r_{2}^{2}{\bigl{(}2\log\frac{1}{\varepsilon}\bigr{)}}^{4}\Bigr{)}}^{2}\leq
2$ and $2^{2}\cdot
3r_{3}^{2}{\bigl{(}2\log\frac{1}{\varepsilon}\bigr{)}}^{4}\leq\varepsilon$
respectively, it holds that on $B_{1}^{c}\cap B_{2}^{c}$

$\frac{1}{2}\,|\mathrm{D}^{2}g(p_{z})[z^{\otimes
4}]|\leq\varepsilon\frac{r^{2}}{d}\ \text{for any }r\leq\min
r_{i}(\varepsilon).$

Putting all these together, it follows that
$|{\|z\|}_{g(z)}^{2}-{\|z\|}_{g(x)}^{2}|\leq 2\varepsilon r^{2}/d$ with
probability at least $1-2\varepsilon$. By replacing
$2\varepsilon\leftarrow\varepsilon$, the claim follows. ∎

####  7.3.4 Collapse and embedding: well-definedness

We start with well-definedness of the notions of collapse and embedding
(Definition 4.16).

###### Proof of Proposition 4.17.

Let $k:=\dim(W)$, and $U$ and $V$ be matrices in $\mathbb{R}^{d\times k}$,
where the columns of each matrix form an orthonormal basis of $W$. Let us
denote by $g_{1}:=U^{\mathsf{T}}gU$ and $g_{2}:=V^{\mathsf{T}}gV$ matrices
represented with respect to $U$ and $V$, and define the invertible matrix
$M=V^{-1}U\in\mathbb{R}^{k\times k}$. Since $U$ and $V$ are full-column rank,
if $g_{1}$ is PD, so is $g_{2}$.

Suppose $g$ is SSC along $W$. Then,

$\displaystyle 4{\|h\|}_{g}^{2}$
$\displaystyle\geq\textup{{Tr}}(g_{1}^{-1}\mathrm{D}g_{1}[h]\,g_{1}^{-1}\mathrm{D}g_{1})=\textup{{Tr}}{\bigl{(}(U^{\mathsf{T}}gU)^{-1}\cdot
U^{\mathsf{T}}\mathrm{D}g[h]\,U\cdot(U^{\mathsf{T}}gU)^{-1}\cdot
U^{\mathsf{T}}\mathrm{D}g[h]\,U\bigr{)}}$
$\displaystyle=\textup{{Tr}}{\Bigl{(}(M^{\mathsf{T}}V^{\mathsf{T}}gVM)^{-1}\cdot
M^{\mathsf{T}}V^{\mathsf{T}}\mathrm{D}g[h]\,VM\cdot(M^{\mathsf{T}}V^{\mathsf{T}}gVM)^{-1}\cdot
M^{\mathsf{T}}V^{\mathsf{T}}\mathrm{D}g[h]\,VM\Bigr{)}}$
$\displaystyle=\textup{{Tr}}{\Bigl{(}(V^{\mathsf{T}}gV)^{-1}V^{\mathsf{T}}\mathrm{D}g[h]\,V\,(V^{\mathsf{T}}gV)^{-1}V^{\mathsf{T}}\mathrm{D}g[h]\,V\Bigr{)}}={\|g_{2}^{-\frac{1}{2}}\mathrm{D}g_{2}[h]\,g_{2}^{-\frac{1}{2}}\|}_{F}^{2}\,,$

and thus $g_{2}$ also satisfies the definition. ∎

####  7.3.5 Collapse and embedding: affine transformation

We begin with a barrier version.

###### Proof of Lemma 4.18.

For the first part, $\psi$ is a $\nu$-self-concordant barrier for $\bar{K}$ by
Nesterov (2003, Theorem 4.2.3), so
$\mathcal{D}_{\bar{g}}^{1}(x)\subset\bar{K}\cap(2x-\bar{K})$ for
$\bar{g}(\cdot):=\nabla^{2}\psi(\cdot)$ by Lemma 4.7. Now let
$z\in\bar{K}\cap(2x-\bar{K})$. Then $Tz\in K$ and $T(2x-z)\in K$, and the
latter implies $2y-Tz\in K$. Thus $Tz\in K\cap(2y-K)$ and
$Tz\in\mathcal{D}_{g}^{\sqrt{\bar{\nu}}}(y)$. Due to

$\displaystyle\mathrm{D}^{2}\psi(x)[(z-x)^{\otimes 2}]$
$\displaystyle=\mathrm{D}^{2}\phi(y)[{\bigl{(}A(z-x)\bigr{)}}^{\otimes
2}]=\mathrm{D}^{2}\phi(y)[(Tz-y)^{\otimes 2}]\leq\bar{\nu}\,,$

it follows that $\psi$ is also $\bar{\nu}$-symmetric.

For the second part, observe that
$\mathrm{D}^{4}\psi(x)[v,v,h,h]=\mathrm{D}^{4}\phi(y)[Av,Av,Ah,Ah]\geq 0$ for
any $v,h\in\mathbb{R}^{d}$. The third part can be proven similarly. ∎

Next is a matrix version.

###### Proof of Lemma 4.19.

Let $\phi$ be a $\nu$-self-concordant function counterpart of $g$. Then
$\psi(x):=\phi(Tx)$ defined on $\textup{{int}}(\bar{K})$ is $\nu$-self-
concordant by Lemma 4.18. For any $h\in\mathbb{R}^{d}$ and $y:=Tx$, we have

$\mathrm{D}\bar{g}(x)[h]=A^{\mathsf{T}}\mathrm{D}g(y)[Ah]\,A\preceq
2{\|Ah\|}_{g(y)}\,A^{\mathsf{T}}g(y)A=2{\|h\|}_{\bar{g}(x)}\,\bar{g}(x)\,.$

Consider a sequence $\\{x_{n}\\}\subset\bar{K}$ converging to a boundary point
$x\in\partial\bar{K}$. If $Tx\notin\partial K$, then $Tx\in\textup{{int}}(K)$,
and the continuity of $T$ implies $x$ is also in $\textup{{int}}(\bar{K})$.
Thus, $Tx\in\partial K$ and $\psi(x_{n})=\phi(Tx_{n})\to\phi(Tx)=\infty$.
Lastly, $\nabla^{2}\phi\asymp g$ leads to
$\nabla^{2}\psi=A^{\mathsf{T}}\nabla^{2}\phi\,A\asymp
A^{\mathsf{T}}gA=\bar{g}$, and $\bar{g}$ is $\nu$-self-concordant for
$\bar{K}$.

As for symmetry, since $\bar{g}$ is self-concordant,
$\mathcal{D}_{\bar{g}}^{1}(x)\subset\bar{K}\cap(2x-\bar{K})$ for
$x\in\textup{{int}}(\bar{K})$ by Lemma 4.3. For $z\in\bar{K}\cap(2x-\bar{K})$,
as $Tz\in K\cap(2Tx-K)$ holds, it follows that

$\bar{\nu}\geq{\|Tz-
Tx\|}_{g(y)}^{2}={\|z-y\|}_{A^{\mathsf{T}}g(y)A}^{2}={\|z-y\|}_{\bar{g}(x)}^{2}\,,$

and thus $\bar{g}$ is $\bar{\nu}$-symmetric.

As for the second item, we first show that $\bar{g}$ is collapsed onto
$W=\textup{{row}}(A)$ (i.e., $\bar{g}=P_{W}\bar{g}P_{W}$ for the orthogonal
projection $P_{W}$ onto $W$). To see this, observe that

$\displaystyle P_{W}\bar{g}P_{W}$
$\displaystyle=P_{W}A^{\mathsf{T}}gAP_{W}=A^{\mathsf{T}}(AA^{\mathsf{T}})^{\dagger}A\cdot
A^{\mathsf{T}}gA\cdot A^{\mathsf{T}}(AA^{\mathsf{T}})^{\dagger}A\,,$

and due to
$AA^{\mathsf{T}}(AA^{\mathsf{T}})^{\dagger}A=AA^{\mathsf{T}}(A^{\mathsf{T}})^{\dagger}A^{\dagger}A=AA^{\dagger}A=A$,
we have $P_{W}\bar{g}P_{W}=A^{\mathsf{T}}gA=\bar{g}$.

We now show that $\bar{g}$ is SSC along $W$. For $k:=\dim(W)$, take
$U\in\mathbb{R}^{d\times k}$ whose columns form an orthonormal basis of $W$.
It suffices to show that
$g_{W}:=U^{\mathsf{T}}\bar{g}U=U^{\mathsf{T}}A^{\mathsf{T}}gAU=M^{\mathsf{T}}gM$
for $M:=AU\in\mathbb{R}^{m\times k}$ is SSC. First of all, we can check PDness
of $g_{W}$ as follows: Suppose $g_{W}v=0$ for some $v\in\mathbb{R}^{k}$. Then
$0={\|v\|}_{g_{W}}={\|g^{1/2}Mv\|}_{2}$ and $AUv=Mv=0$. Since
$Uv\in\textup{{row}}(A)\cap\textsf{ker}(A)$ and $U$ is full-rank, we have
$v=0$. Next, for $h\in\mathbb{R}^{k}$ and $x\in\textup{{int}}(\bar{K})$

$\displaystyle\textup{{Tr}}{\bigl{(}g_{W}(x)^{-1}\mathrm{D}g_{W}(x)[h]\,g_{W}(x)^{-1}\mathrm{D}g_{W}(x)[h]\bigr{)}}=\textup{{Tr}}{\Bigl{(}{\bigl{(}g^{\frac{1}{2}}M(M^{\mathsf{T}}gM)^{-1}M^{\mathsf{T}}g^{\frac{1}{2}}\cdot
g^{-\frac{1}{2}}\mathrm{D}g(Tx)[Ah]\,g^{-\frac{1}{2}}\bigr{)}}^{2}\Bigr{)}}$
$\displaystyle\underset{\text{(i)}}{\leq}$
$\displaystyle\textup{{Tr}}{\Bigl{(}{\bigl{(}g^{-\frac{1}{2}}\mathrm{D}g(Tx)[Ah]\,g^{-\frac{1}{2}}\bigr{)}}^{2}\Bigr{)}}\leq{\|g^{-\frac{1}{2}}\mathrm{D}g(Tx)[Ah]\,g^{-\frac{1}{2}}\|}_{F}^{2}\leq
4{\|Ah\|}_{g(Tx)}^{2}=4{\|h\|}_{\bar{g}(x)}^{2}\,,$

where in (i) we used
$P(g^{\frac{1}{2}}M)=g^{\frac{1}{2}}M(M^{\mathsf{T}}gM)^{-1}M^{\mathsf{T}}g^{\frac{1}{2}}\preceq
I$. Thus, $\bar{g}$ is SSC along $W=\textup{{row}}(A)$.

The third item immediately follows from
$\mathrm{D}^{2}\bar{g}(x)[h,h]=A^{\mathsf{T}}\mathrm{D}^{2}g(y)[Ah,Ah]\,A\succeq
0$ for any $h\in\mathbb{R}^{d}$.

As for the fourth item, for any PSD matrix function $g^{\prime}$ on $\bar{K}$
we have

$\displaystyle\textup{{Tr}}{\bigl{(}(g^{\prime}+\bar{g})^{-1}\mathrm{D}^{2}\bar{g}[h,h]\bigr{)}}=\textup{{Tr}}{\Bigl{(}(g^{\prime}+A^{\mathsf{T}}gA)^{-1}A^{\mathsf{T}}\mathrm{D}^{2}g[Ah,Ah]\,A\Bigr{)}}$
$\displaystyle=$
$\displaystyle\textup{{Tr}}{\Bigl{(}(A^{-\mathsf{T}}g^{\prime}A^{-1}+g)^{-1}\mathrm{D}^{2}g[Ah,Ah]\Bigr{)}}\geq-{\|Ah\|}_{g}^{2}=-{\|h\|}_{\bar{g}}^{2}\,.$

The last item is straightforward to check by the change of variable. ∎

####  7.3.6 Collapse and embedding: lifting up SSC, SLTSC, and SASC

In passing SSC to an augmented space, the Woodbury matrix identity is a main
technical tool used: for matrices with compatible sizes

$(I+UV)^{-1}=I-U\,(I+VU)^{-1}V\,.$

Using this, we show that if $g\in\mathbb{S}_{++}^{d}$ is SSC, then
$\bar{g}+\varepsilon I_{m}$ is SSC.

###### Proof of Lemma 4.21.

Fix $\varepsilon>0,y\in\textup{{int}}(K^{\prime})$, and $h\in\mathbb{R}^{m}$.
Take a projection matrix $P\in\\{0,1\\}^{d\times m}$ such that
$PP^{\mathsf{T}}=I_{d}$ and $\bar{g}(y)=P^{\mathsf{T}}g(Py)P$ for
$x=Py\in\textup{{int}}(K)$. Also for $k:=\dim(W)$, take a matrix
$U\in\mathbb{R}^{d\times k}$ whose columns form an orthonormal basis of $W$.
Then $\bar{g}(y)=P^{\mathsf{T}}g(Py)P$ and $g(x)=Ug_{W}(x)U$, so for
$M:=U^{\mathsf{T}}P\in\mathbb{R}^{k\times m}$,

$\bar{g}(y)=P^{\mathsf{T}}Ug_{W}(Py)U^{\mathsf{T}}P=M^{\mathsf{T}}g_{W}(Py)M\,.$

Note that $MM^{\mathsf{T}}=I_{k}$. Thus,

$\displaystyle{\|(\bar{g}(y)+\varepsilon
I)^{-\frac{1}{2}}\mathrm{D}(\bar{g}+\varepsilon
I)(y)[h]\,(\bar{g}(y)+\varepsilon
I)^{-\frac{1}{2}}\|}_{F}^{2}=\textup{{Tr}}{\Bigl{(}{\bigl{(}(\bar{g}(y)+\varepsilon
I)^{-1}\mathrm{D}\bar{g}(y)[h]\bigr{)}}^{2}\Bigr{)}}$ $\displaystyle=$
$\displaystyle\textup{{Tr}}{\Bigl{(}{\bigl{(}M(M^{\mathsf{T}}g_{W}(x)\,M+\varepsilon
I)^{-1}M^{\mathsf{T}}\cdot\mathrm{D}g_{W}(x)[Ph]\bigr{)}}^{2}\Bigr{)}}\underset{\text{(i)}}{=}\textup{{Tr}}{\Bigl{(}{\bigl{(}(g_{W}(x)+\varepsilon
I_{k})^{-1}\mathrm{D}g_{W}(x)[Ph]\bigr{)}}^{2}\Bigr{)}}$ $\displaystyle\leq$
$\displaystyle{\|g_{W}(x)^{-\frac{1}{2}}\mathrm{D}g_{W}(x)[Ph]\,g_{W}(x)^{-\frac{1}{2}}\|}_{F}^{2}\leq
4{\|Ph\|}_{g(x)}^{2}=4{\|h\|}_{\bar{g}(y)}^{2}\,,$

where in (i) we used the identity
$M{\bigl{(}M^{\mathsf{T}}g_{W}(x)\,M+\varepsilon
I\bigr{)}}^{-1}M^{\mathsf{T}}=(g_{W}(x)+\varepsilon I_{k})^{-1}$. To see this,
we use the Woodbury matrix identity to get

$(\varepsilon
I_{m}+M^{\mathsf{T}}g_{W}M)^{-1}=\frac{1}{\varepsilon}I_{m}-\frac{1}{\varepsilon^{2}}M^{\mathsf{T}}g_{W}^{\frac{1}{2}}{\bigl{(}I_{k}+\frac{1}{\varepsilon}g_{W}\bigr{)}}^{-1}g_{W}^{\frac{1}{2}}M\,,$

and thus conjugating both sides by $M$ results in

$\displaystyle M{\bigl{(}M^{\mathsf{T}}g_{W}M+\varepsilon
I_{m}\bigr{)}}^{-1}M^{\mathsf{T}}$
$\displaystyle=\frac{1}{\varepsilon}I_{k}-\frac{1}{\varepsilon}g_{W}^{\frac{1}{2}}(g_{W}+\varepsilon
I_{k})^{-1}g_{W}^{\frac{1}{2}}=\frac{1}{\varepsilon}I_{k}-\frac{1}{\varepsilon}(g_{W}+\varepsilon
I_{k})^{-1}g_{W}\,.$

Then, the identity follows from

$\displaystyle(g_{W}+\varepsilon
I_{k})\cdot{\bigl{(}\frac{1}{\varepsilon}I_{k}-\frac{1}{\varepsilon}\,(g_{W}+\varepsilon
I_{k})^{-1}g_{W}\bigr{)}}$
$\displaystyle=\frac{1}{\varepsilon}(g_{W}+\varepsilon
I_{k})-\frac{1}{\varepsilon}g_{W}=I_{k}\,.\qed$

In extending SLTSC and SASC, we need two technical lemmas: the inverse of a
block matrix and connection between P(S)Dness and Schur complements.

######  Lemma 7.4.

If $D$ and its Schur complement $A-BD^{-1}C$ are invertible, then

$\left[\begin{array}[]{cc}A&B\\\
C&D\end{array}\right]^{-1}=\left[\begin{array}[]{cc}(A-BD^{-1}C)^{-1}&*\\\
&*\end{array}\right]\,.$

######  Lemma 7.5 (Schur complement).

Let $A\in\mathbb{R}^{d\times d},B\in\mathbb{R}^{d\times
m},C\in\mathbb{R}^{m\times m}$ and define a matrix
$M\in\mathbb{R}^{(m+d)\times(m+d)}$ by

$M=\left[\begin{array}[]{cc}A&B\\\ B^{\mathsf{T}}&D\end{array}\right]\,.$

Then $M\succ 0$ if and only if $A\succ 0$ and $C-BA^{-1}B^{\mathsf{T}}\succ 0$
if and only $C\succ 0$ and $A-B^{\mathsf{T}}C^{-1}B\succ 0$.

Using these, we show that if $g$ is SLTSC and SASC, then $\bar{g}$ is SLTSC
and SASC.

###### Proof of Lemma 4.22.

Take a full row-rank projection matrix $P\in\\{0,1\\}^{d\times m}$ such that
$\bar{g}(y)=P^{\mathsf{T}}g(Py)P$, where the rows of $P$ forms a subset of the
canonical basis $\\{e_{1},\dots,e_{m}\\}$. We can augment the rows of $P$ with
the rest of the canonical basis so that the augmented matrix
$\bar{P}\in\mathbb{R}^{m\times m}$ is an orthonormal matrix. Then we can
represent $\bar{g}$ by

$\bar{g}(y)=\bar{P}^{\mathsf{T}}\left[\begin{array}[]{cc}g(Py)&0\\\
0&0\end{array}\right]\bar{P}\,.$

Consider a PSD matrix function
$g^{\prime}:\textup{{int}}(K^{\prime})\to\mathbb{S}_{+}^{m}$ such that
$g^{\prime}+\bar{g}$ is PD on $K^{\prime}$. Representing them in the block
form with $g_{A}\in\mathbb{R}^{d\times d},g_{B}\in\mathbb{R}^{d\times(m-d)},$
and $g_{C}\in\mathbb{R}^{(m-d)\times(m-d)}$

$\bar{g}+g^{\prime}=\bar{P}^{\mathsf{T}}\left(\left[\begin{array}[]{cc}g&0\\\
0&0\end{array}\right]+\left[\begin{array}[]{cc}g_{A}&g_{B}\\\
g_{B}^{\mathsf{T}}&g_{C}\end{array}\right]\right)\bar{P}=\bar{P}^{\mathsf{T}}\underbrace{\left[\begin{array}[]{cc}g+g_{A}&g_{B}\\\
g_{B}^{\mathsf{T}}&g_{C}\end{array}\right]}_{\eqqcolon g^{*}}\bar{P}\,.$

Since $g^{*}$ is PD, $g_{C}$ and its Schur complement
$(g+g_{A})-g_{B}g_{C}^{-1}g_{B}^{\mathsf{T}}$ are PD. Thus by Lemma 7.4,

$\left[\begin{array}[]{cc}g+g_{A}&g_{B}\\\
g_{B}^{\mathsf{T}}&g_{C}\end{array}\right]^{-1}=\left[\begin{array}[]{cc}(g+g_{A}-g_{B}g_{C}^{-1}g_{B}^{\mathsf{T}})^{-1}&*\\\
&*\end{array}\right]\,.$

Hence,

$\displaystyle\textup{{Tr}}{\bigl{(}(\bar{g}+g^{\prime})^{-1}\mathrm{D}^{2}\bar{g}(y)[h,h]\bigr{)}}=\textup{{Tr}}\Biggl{(}\bar{P}^{\mathsf{T}}\left[\begin{array}[]{cc}g+g_{A}&g_{B}\\\
g_{B}^{\mathsf{T}}&g_{C}\end{array}\right]^{-1}\bar{P}\bar{P}^{\mathsf{T}}\left[\begin{array}[]{cc}\mathrm{D}^{2}g(Py)[Ph,Ph]&0\\\
0&0\end{array}\right]\bar{P}\Biggr{)}$ $\displaystyle=$
$\displaystyle\textup{{Tr}}\Biggl{(}\left[\begin{array}[]{cc}g+g_{A}&g_{B}\\\
g_{B}^{\mathsf{T}}&g_{C}\end{array}\right]^{-1}\left[\begin{array}[]{cc}\mathrm{D}^{2}g(Py)[Ph,Ph]&0\\\
0&0\end{array}\right]\Biggr{)}=\textup{{Tr}}{\bigl{(}(g+\underbrace{g_{A}-g_{B}g_{C}^{-1}g_{B}^{\mathsf{T}}}_{\succeq
0})^{-1}\,\mathrm{D}^{2}g(Py)[Ph,Ph]\bigr{)}}$ $\displaystyle\geq$
$\displaystyle-{\|Ph\|}_{g(Py)}^{2}=-{\|h\|}_{\bar{g}(y)}^{2}\,,$

where in the last inequality we used STLSC of $g$, since $g^{\prime}\succeq 0$
ensures that its Schur complement satisfies
$g_{A}-g_{B}g_{C}^{-1}g_{B}^{\mathsf{T}}\succeq 0$ by Lemma 7.5.

For SASC, consider any PSD matrix function
$g^{\prime}:\textup{{int}}(K^{\prime})\to\mathbb{S}_{+}^{m}$. For $x=Py$ and
$z_{x}=Pz_{y}\in\mathbb{R}^{d}$ with
$z_{y}\sim\mathcal{N}{\bigl{(}y,\frac{r^{2}}{m}\,(\bar{g}+g)(y)^{-1}\bigr{)}}$,
we have

${\|z_{y}-y\|}_{\bar{g}(z_{y})}^{2}-{\|z_{y}-y\|}_{\bar{g}(y)}^{2}={\|z_{x}-x\|}_{g(z_{x})}^{2}-{\|z_{x}-x\|}_{g(x)}^{2}\,.$

Also, $z_{x}-x=P\,(z_{y}-y)$ is a Gaussian with zero mean and covariance

$\displaystyle\frac{r^{2}}{m}\,P\,(\bar{g}+g^{\prime})(y)^{-1}P^{\mathsf{T}}=\frac{r^{2}}{m}\,P\bar{P}^{\mathsf{T}}\left(\left[\begin{array}[]{cc}g&0\\\
0&0\end{array}\right]+\left[\begin{array}[]{cc}g_{A}&g_{B}\\\
g_{B}^{\mathsf{T}}&g_{C}\end{array}\right]\right)^{-1}\bar{P}\bar{P}^{\mathsf{T}}$
$\displaystyle=$
$\displaystyle\frac{r^{2}}{m}\,\left[\begin{array}[]{cc}I_{d}&0_{d\times(m-d)}\end{array}\right]\left(\left[\begin{array}[]{cc}g&0\\\
0&0\end{array}\right]+\left[\begin{array}[]{cc}g_{A}&g_{B}\\\
g_{B}^{\mathsf{T}}&g_{C}\end{array}\right]\right)^{-1}\left[\begin{array}[]{c}I_{d}\\\
0_{d\times(m-d)}\end{array}\right]=\frac{r^{2}}{m}\,(g+g_{A}-g_{B}g_{C}^{-1}g_{B}^{\mathsf{T}})^{-1}\,.$

Since $g_{A}-g_{B}g_{C}^{-1}g_{B}^{\mathsf{T}}\succeq 0$ due to
$g^{\prime}\succeq 0$, it holds that
$g_{0}:=\frac{m-d}{d}g+\frac{m}{d}(g_{A}-g_{B}g_{C}^{-1}g_{B}^{\mathsf{T}})$
on $\textup{{int}}(K)$ is PSD. Now, it suffices to check that the covariance
matrix above is equal to $\frac{r^{2}}{d}(g+g_{0})^{-1}$:

$\frac{d}{r^{2}}\,(g+g_{0})=\frac{d}{r^{2}}{\Bigl{(}g+\frac{m-d}{d}\,g+\frac{m}{d}\,(g_{A}-g_{B}g_{C}^{-1}g_{B}^{\mathsf{T}})\Bigr{)}}\frac{m}{r^{2}}\,(g+g_{A}-g_{B}g_{C}^{-1}g_{B}^{\mathsf{T}})\,.\qed$

####  7.3.7 Direct product: SSC and SLTSC

We show that if $g_{i}\in\mathbb{S}_{++}^{d_{i}}$ is SC, then $g=\sum
d_{i}\bar{g}_{i}$ is SSC.

###### Proof of Lemma 4.25.

Note that $d_{i}g_{i}$ is SSC for $i=1,\dots,m$. For $x\in\prod E_{i}$ and
$h=(h_{1},\dots,h_{m})\in\mathbb{R}^{l}$ with $h_{i}\in\mathbb{R}^{d_{i}}$, we
have

$\displaystyle{\|g(x)^{-\frac{1}{2}}\mathrm{D}g(x)[h]\,g(x)^{-\frac{1}{2}}\|}_{F}^{2}$
$\displaystyle=\left\|\left[\begin{array}[]{ccc}g_{1}(x_{1})^{-\frac{1}{2}}\mathrm{D}g_{1}(x_{1})[h_{1}]\,g_{1}(x_{1})^{-\frac{1}{2}}\\\
&\ddots\\\
&&g_{m}(x_{m})^{-\frac{1}{2}}\mathrm{D}g_{m}(x_{m})[h_{m}]\,g_{m}(x_{m})^{-\frac{1}{2}}\end{array}\right]\right\|_{F}^{2}$
$\displaystyle=\sum_{i}{\|g_{i}(x_{i})^{-\frac{1}{2}}\mathrm{D}g_{i}(x_{i})[h_{i}]\,g_{i}(x_{i})^{-\frac{1}{2}}\|}_{F}^{2}\leq
4\sum_{i}{\|h_{i}\|}_{d_{i}g_{i}(x_{i})}^{2}=4{\|h\|}_{g(x)}^{2}\,.\qed$

Next, we show that if $g_{i}\in\mathbb{S}_{++}^{d_{i}}$ is HSC, then $g=\sum
d_{i}\bar{g}_{i}$ is SLTSC.

###### Proof of Lemma 4.26.

For $h=(h_{1},\dots,h_{m})$ and any PSD matrix function $g^{\prime}$, we have

$\displaystyle\textup{{Tr}}{\bigl{(}(g^{\prime}+g)^{-1}\mathrm{D}^{2}g[h^{\otimes
2}]\bigr{)}}$
$\displaystyle=\sum_{i}\textup{{Tr}}{\bigl{(}(g^{\prime}+(g-d_{i}\bar{g}_{i})+d_{i}\bar{g}_{i})^{-1}\mathrm{D}^{2}(d_{i}\bar{g}_{i})[h^{\otimes
2}]\bigr{)}}\gtrsim-\sum_{i}{\|h\|}_{d_{i}\bar{g}_{i}}^{2}=-{\|h\|}_{g}^{2}\,,$

where we used Lemma 4.13 in the inequality. ∎

####  7.3.8 Inverse images under non-linear mappings

###### Proof of Lemma 4.30.

Since $\mathcal{A}$ is $(R(G),\beta),\gamma)$-compatible with $\Gamma$, the
first two claims immediately follow from Nesterov and Nemirovskii (1994,
Proposition 5.1.7). Let $x\in G^{+}$ and $h\in\mathbb{R}^{d}$. Define the
following notations:

$\displaystyle u=\mathrm{D}\mathcal{A}(x)[h],$ $\displaystyle\quad
v=\mathrm{D}^{2}\mathcal{A}(x)[h^{\otimes 2}],\quad
w=\mathrm{D}^{3}\mathcal{A}(x)[h^{\otimes 3}],\quad
z=\mathrm{D}^{4}\mathcal{A}(x)[h^{\otimes 4}],$ $\displaystyle
s=\sqrt{\mathrm{D}F(y)[v]},$
$\displaystyle\quad\rho=\sqrt{\mathrm{D}^{2}\Pi(x)[h^{\otimes 2}]},\quad
r=\sqrt{\mathrm{D}^{2}F(y)[u^{\otimes 2}]}\,.$

From direct computations, we have

$\displaystyle\mathrm{D}^{2}\Psi(x)[h^{\otimes 2}]$
$\displaystyle=\mathrm{D}F(y)[v]+\mathrm{D}^{2}F(y)[u^{\otimes
2}]+\delta^{2}\mathrm{D}^{2}\Pi(x)[h^{\otimes
2}]=s^{2}+r^{2}+\delta^{2}\rho^{2}\,,$
$\displaystyle\mathrm{D}^{3}\Psi(x)[h^{\otimes 3}]$
$\displaystyle=\mathrm{D}F(y)[w]+3\mathrm{D}^{2}F(y)[u,v]+\mathrm{D}^{3}F(y)[u^{\otimes
3}]+\delta^{2}\mathrm{D}^{3}\Pi(x)[h^{\otimes 3}]\,,$
$\displaystyle\mathrm{D}^{4}\Psi(x)[h^{\otimes 4}]$
$\displaystyle=\mathrm{D}^{2}F(y)[w,u]+\mathrm{D}F(y)[z]+3\mathrm{D}^{3}F(y)[u,u,v]+3\mathrm{D}^{2}F(y)[v^{\otimes
2}]$
$\displaystyle\qquad+3\mathrm{D}^{2}F(y)[u,w]+\mathrm{D}^{4}F(y)[u^{\otimes
4}]+3\mathrm{D}^{3}F(y)[u,u,v]+\delta^{2}\mathrm{D}^{4}\Pi(x)[h^{\otimes 4}]$
$\displaystyle=\mathrm{D}F(y)[z]+3\mathrm{D}^{2}F(y)[v^{\otimes
2}]+4\mathrm{D}^{2}F(y)[u,w]$
$\displaystyle\qquad+6\mathrm{D}^{3}F(y)[u,u,v]+\mathrm{D}^{4}F(y)[u^{\otimes
4}]+\delta^{2}\mathrm{D}^{4}\Pi(x)[h^{\otimes 4}]\,.$

HSC of $F$ and $\Pi$ implies that

$|\mathrm{D}^{4}\Pi(x)[h^{\otimes 4}]|\leq
6\rho^{4}\,,\qquad\text{and}\qquad|\mathrm{D}^{4}F(y)[u^{\otimes 4}]|\leq
6r^{4}\,.$

Since $\mathcal{A}$ is $(K,\beta,\gamma)$-compatible and $K\subset R(G)$,
Lemma 4.29-1 implies concavity of $\mathcal{A}$ with respect to $R(G)$, which
means $-v\geq_{R(G)}0$. Then, Nesterov and Nemirovskii (1994, Corollary 2.3.1)
ensures

$\sqrt{\mathrm{D}^{2}F(y)[v^{\otimes 2}]}\leq\mathrm{D}F(y)[v]=s^{2}\,.$

Hence, $|3\mathrm{D}^{2}F(y)[v,v]|\leq 3(\mathrm{D}F(y)[v])^{2}=3s^{4}$, and
self-concordance of $F$ results in

$|6\mathrm{D}^{3}F(y)[u,u,v]|\leq 12r^{2}\sqrt{\mathrm{D}^{2}F(y)[v,v]}\leq
12r^{2}s^{2}\,.$

Since $\\{h:h^{\mathsf{T}}\Pi(x)h\leq 1\\}$ is contained in
$\Gamma\cap(2x-\Gamma)$, compatibility of $\mathcal{A}$ leads to

$\beta\mathrm{D}^{2}\mathcal{A}(x){\Bigl{[}{\Bigl{(}\frac{h}{{\|h\|}_{\Pi(x)}}\Bigr{)}}^{\otimes
2}\Bigr{]}}\leq_{K}\mathrm{D}^{3}\mathcal{A}(x){\Bigl{[}{\Bigl{(}\frac{h}{{\|h\|}_{\Pi(x)}}\Bigr{)}}^{\otimes
3}\Bigr{]}}\leq_{K}-\beta\mathrm{D}^{2}\mathcal{A}(x){\Bigl{[}{\Bigl{(}\frac{h}{{\|h\|}_{\Pi(x)}}\Bigr{)}}^{\otimes
2}\Bigr{]}}\,,$

and thus $\beta\rho v\leq_{K}w\leq_{K}-\beta\rho v$. As $K$ is a ray,
$\mathrm{D}^{2}F(y)[w,w]\leq\beta^{2}\rho^{2}\mathrm{D}^{2}F(y)[v,v]\leq\beta^{2}\rho^{2}s^{4}$.
Thus,

$|4\mathrm{D}^{2}F(y)[u,w]|\leq
4\sqrt{\mathrm{D}^{2}F(y)[u,u]}\sqrt{\mathrm{D}^{2}F(y)[w,w]}\leq 4r\beta\rho
s^{2}\,.$

Lastly, since $\gamma v\rho^{2}\leq_{K}z\leq_{K}-\gamma v\rho^{2}$ and $K$ is
a ray, we have

$|\mathrm{D}F(y)[z]|\leq
3\gamma\rho^{2}|\mathrm{D}F(y)[v]|=3\gamma\rho^{2}s^{2}\,.$

Putting these together,

$\displaystyle\left\lvert\mathrm{D}^{4}\Psi(x)[h^{\otimes 4}]\right\rvert\leq
3\gamma\rho^{2}s^{2}+4r\beta\rho
s^{2}+12r^{2}s^{2}+3s^{4}+6\delta^{2}\rho^{4}+6r^{4}$ $\displaystyle\leq$
$\displaystyle
6(\delta^{2}\rho^{4}+r^{4}+s^{4}+r^{2}s^{2}+\delta\rho^{2}s^{2}+\delta r\rho
s^{2})\leq
6{\bigl{(}(\delta\rho)^{4}+r^{4}+s^{4}+r^{2}s^{2}+(\delta\rho)^{2}s^{2}+r^{2}s^{2}+(\delta\rho)^{2}s^{2}\bigr{)}}$
$\displaystyle\leq$ $\displaystyle
6{\bigl{(}(\delta\rho)^{2}+r^{2}+s^{2}\bigr{)}}^{2}=6{\bigl{(}\mathrm{D}^{2}\Psi(x)[h,h]\bigr{)}}^{2}\,.\qed$

###  7.4 Main constraints and epigraphs ($\S$5)

####  7.4.1 Linear constraints: strong self-concordance and symmetry

We relate SSC and symmetry to well-studied terms in the field of optimization,
such as $\max_{i}\frac{[\sigma(\sqrt{D_{x}}A_{x})]_{i}}{[D_{x}]_{ii}}$ and
${\|D_{x,h}^{\prime}\|}_{D_{x}^{-1}}^{2}$.

###### Proof of Lemma 5.4.

Let us write $g(x)=A_{x}^{\mathsf{T}}D_{x}A_{x}=A^{\mathsf{T}}V_{x}A$ for
$V_{x}:=S_{x}^{-1}D_{x}S_{x}^{-1}$. By Claim B.1,

$\displaystyle\mathrm{D}g(x)[h]$
$\displaystyle=A^{\mathsf{T}}(-2S_{x}^{-1}S_{x,h}S_{x}^{-1}D_{x}+S_{x}^{-1}\mathrm{D}D_{x}[h]\,S_{x}^{-1})A=A^{\mathsf{T}}V_{x}^{1/2}\overline{D}_{x}V_{x}^{1/2}A\,,$
(7.15)

where $\overline{D}_{x}:=-2S_{x,h}+D_{x}^{-1}\mathrm{D}D_{x}[h]$. Using this,

$\displaystyle{\|(g^{\prime}+g)^{-\frac{1}{2}}\mathrm{D}g[h]\,(g^{\prime}+g)^{-\frac{1}{2}}\|}_{F}^{2}$
$\displaystyle=\textup{{Tr}}{\bigl{(}(g^{\prime}+g)^{-1}A^{\mathsf{T}}V_{x}^{1/2}\overline{D}_{x}\underbrace{V_{x}^{1/2}A(g^{\prime}+g)^{-1}A^{\mathsf{T}}V_{x}^{1/2}}_{=:P_{x}^{\prime}}\overline{D}_{x}V_{x}^{1/2}A\bigr{)}}$
$\displaystyle=\textup{{Tr}}(P_{x}^{\prime}\overline{D}_{x}P_{x}^{\prime}\overline{D}_{x})\,.$

By Lemma C.1, we have $P_{x}^{\prime}\preceq
P_{x}=P(V_{x}^{1/2}A)=P(D_{x}^{1/2}A_{x})$, and thus

$\displaystyle\textup{{Tr}}(P_{x}^{\prime}\overline{D}_{x}P_{x}^{\prime}\overline{D}_{x})$
$\displaystyle\leq\textup{{Tr}}(P_{x}\overline{D}_{x}P_{x}\overline{D}_{x})\underset{\text{(i)}}{=}\textsf{{diag}}(\overline{D}_{x})^{\mathsf{T}}P_{x}^{(2)}\,\textsf{{diag}}(\overline{D}_{x})\underset{\text{(ii)}}{\leq}\textsf{{diag}}(\overline{D}_{x})^{\mathsf{T}}\Sigma_{x}\,\textsf{{diag}}(\overline{D}_{x})$
$\displaystyle\underset{\text{(iii)}}{\leq}4\sum_{i=1}^{m}[\sigma(D_{x}^{1/2}A_{x})]_{i}\,{\bigl{(}(A_{x}h)_{i}^{2}+(D_{x}^{-1}\mathrm{D}D_{x}[h])_{i}^{2}\bigr{)}}$
$\displaystyle\leq
4\max_{i}\frac{[\sigma(D_{x}^{1/2}A_{x})]_{i}}{[D_{x}]_{ii}}\cdot\sum_{i=1}^{m}[D_{x}]_{ii}\,{\bigl{(}(A_{x}h)_{i}^{2}+(D_{x}^{-1}\mathrm{D}D_{x}[h])_{i}^{2}\bigr{)}}$