A Faster Small Treewidth SDP Solver

Introduction

Semidefine programming is one fundamental problem in optimization and theoretical computer science. It has many applications in computer science, such as verifying the robustness of neural network [RSL18], solving the discrepancy problems [Ban10], sparse matrix factorization [CSTZ22], sparsest cut [ARV09], $3$-colorable graph [KMS94], terminal embeddings [CN21], quantum complexity theory [JJUW11], obtaining tight approximation ratio for MAXCUT [GW95], solving sum of squares programs [BS16, FKP19], and so on.

Mathematically, a semidefinite program can be defined as follows.

Over the last century, many efforts have been put into optimizing the running time of semidefinite programming [Sho77, YN76, Kha80, KTE88, NN89, Vai89, KM03, BV02, LSW15, JLSW20, JLSW20, JKL+20, HJS+22]. Based on how many iterations you need to solve semi-definite programming, the previous work of solving semi-definite programming can be splitted into three lines: cutting plane method [LSW15, JLSW20], log barrier function [JKL+20, HJS+22], volumetric/hybrid barrier function [HJS+22].

Many graph problems can be written as semidefinite programs with certain structure. For example, the famous Goemans-Williamson algorithm [GW95] relaxes $\mathsf{MaxCut}$ problem to a semidefinite program. When the underlying graph has low treewidth, the corresponding SDP also has small treewidth. While the $\mathsf{MaxCut}$ problem takes exponential time in treewidth [LMS11] (under plausible hyposthesis like Exponetial Time Hypothesis [IP01]), when treewidth is constant, it can be easily solved in linear time; on the other hand, before our work, it was not known whether $\mathsf{MaxCut}$ SDP can be solved in nearly linear time even when treewidth is constant. Another graph problem is Lovász theta function [Lov79], it is an important quantity in noisy communication and is naturally defined as a semidefinite program.

In practice, data sets on graphs often have small treewidth, see e.g. [ZL18, Table 1], and [DLY21, Appendix B]. Therefore SDP with small treewidth is a problem of practical interest.

In this work, we consider SDP for which the treewidth is small. Formally,

Given an SDP (Definition 1.1), we define its SDP graph as a graph $G=(V,E)$ where $V=[n]$ and

Treewidth of an SDP is defined as treewidth of the SDP graph.

Let $\tau$ denote the treewidth of the SDP graph. The best previous work on small treewidth semidefinite programming is due to [ZL18], which runs in $n^{1.5}\tau^{6.5}$ time. A natural question to consider is,

Can we solve SDP much faster under treewidth assumption, i.e., in particular can we solve SDP in nearly linear time in $n$?

In this work, we answer the above question in affirmative.

We make the following linear independence assumption on our SDP. This assumption is standard in IPM literature, and is also present previous works [ZL18].

Under Assumption 1.3, the total number of constraints $m$ is bounded by $m\leq\tau n$.

For the standard semidefinite programming (without low-treewidth assumptions), the best previous algorithms are due to [JKL+20, HJS+22]. Those algorithms are based on dual-only central path algorithms. Due to technical reasons, even with small treewidth assumption, those techniques lead to algorithm with running time at least $\Omega(m^{\omega})$,Here $\omega$ denotes the exponent of matrix multiplication, i.e., multiplying an $n\times n$ matrix with another $n\times n$ matrix takes $n^{\omega}$ time. Currently, $\omega\approx 2.373$ [Wil12, AW21]. and cannot solve semidefinite programming with time only linear in $n$.

There is an algorithm that solves semidefinite programming (1) with accuracy $\epsilon>0$ in

1.2 Low-Treewidth LP

Furthermore, we also improve the best previous low-treewidth LP result due to [DLY21] (which runs in $n\tau^{2}$ time). Before stating our result for LP, let us define treewidth of an LP.

Given an LP, we construct the LP dual graph where vertices are constraints, and there is an edge between two vertices if they share a common variable (with non-zero coefficients). Then treewidth of the LP is defined as the treewidth of its LP dual graph.

There is an algorithm that solves linear programming (3) with accuracy $\epsilon>0$ in

1.3 Decomposable SDP

There are cases where Theorem 1.4 does not apply but we can still obtain an efficient SDP solving algorithm. One such case is summarized in the following theorem. To state the result, let us define the sparsity graph, a graph with potentially lower treewidth than the SDP graph (Definition 1.2).

Given an SDP (Definition 1.1), we define its sparsity graph as a graph $G=(V,E)$ where $V=[n]$ and

Let $\gamma_{\max}$ be the maximum number of constraints a bag correspond to. Let $\tau$ be the maximum size of a bag. Then the SDP can be solved in time $\widetilde{O}(n\tau^{0.5}(\tau^{2}+\gamma_{\max})^{\omega})$.

A special case for which the condition in Theorem 1.9 is satisfied is the “Network Flow Semidefinite Program” studied in [ZL18].

A network flow SDP is an SDP (Definition 1.1) where for every constraint matrix $A_{i}$, there exists a vertex $k_{i}\in[n]$ such that $A_{i,u,v}\neq 0\Rightarrow k_{i}\in\{u,v\}$.

[ZL18] gave an algorithm to solve network flow semidefinite programs in $\widetilde{O}(n^{1.5}\tau^{3.5}(\tau+d_{\max}m_{\max})^{3.5})$ time, where $d_{\max}$ is the maximum degree of the tree $\mathcal{T}$ and $m_{\max}$ is the maximum number of network flow constraints at any vertex (i.e., $m_{\max}:=\max_{k\in V}\#\{i\in[m]:k_{i}=k\}$).

Using Theorem 1.9, we can achieve almost linear running time for network flow semidefinite programs.

The network flow semidefinite program can be solved in time $\widetilde{O}(n\tau^{0.5}(\tau^{2}+\gamma_{\max})^{\omega})$.

Note that for network flow SDPs, a trivial bound for $\gamma_{\max}$ is $\gamma_{\max}\leq\tau m_{\max}$.

2 Applications

In this section, we discuss three applications: MaxCut SDP, Lovasz Theta function, and low rank matrix completion.

For a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph’s vertices into two complementary sets $S$ and $T$, such that the number of edges between the set $S$ and the set $T$ is as large as possible. The problem of finding a maximum cut in a graph is known as the $\mathsf{MaxCut}$ Problem. This problem is NP-complete [Kar72], and also APX-hard [PY91]. The $\mathsf{MaxkCut}$ problem is a natural generalization of $\mathsf{MaxCut}$, where we would like to partition the set of vertices into $k$ disjoint parts, and maximize the number of edges between different parts. A $\mathsf{Max2Cut}$ problem is the same as a $\mathsf{MaxCut}$ problem.

$\mathsf{MaxCut}$ and $\mathsf{MaxkCut}$ admit natural SDP relaxations.

Let $L_{G}$ be the weighted Laplacian matrix for a graph $G$ with $n$ vertices. There is a randomized algorithm to solve $\mathsf{MaxkCut}$ with an approximation ratio of $1-1/k$ based on solving

The classic Goemans-Williamson 0.878-approximation algorithm [GW95] for $\mathsf{MaxCut}$ is recovered by setting $k=2$ and removing the redundant constraint $X_{i,j}\geq-1$. This is the best possible approximation ratio under the Unique Games Conjecture [KKMO07].

2.2 Lovász Theta Function

We discuss another famous application of SDP which is the Lovász theta function,

The SDP graph (Definition 1.2) is obtained by adding a new vertex $o$ to the complement graph $\overline{G}$ of input graph $G$, with an edge $(i,o)$ for all $i\in V$. Given a tree decomposition of $\overline{G}$ with bag size $\tau$, a tree decomposition of the SDP graph with bag size $\tau+1$ can be obtained by adding the new vertex $o$ into every bag. So SDP treewidth is small when $\overline{G}$ has small treewidth.

2.3 Low Rank Matrix Completion

In the low rank matrix completion problem, we are given a partially filled matrix $B$, where entries $(i,j)\in\Omega$ are filled. The goal is to find a matrix $X$ of smallest rank that agrees with $B$ on $\Omega$.

This problem is non-convex and in general difficult to solve. A popular relaxation [CR09] of the problem is to minimize the nuclear norm $\|\cdot\|_{*}$ instead.

Furthermore, [CR09] rewrote the above formulation in the following equivalent form:

Let $G=([n],\Omega)$ be the adjacency graph. The SDP graph (Definition 1.2) is as follows: for every edge $(i,j)\in\Omega$, the SDP graph contains the clique $\{i,j,i+n,j+n\}$.

3 Related Work

In the previous SDP literature, there are two lines of SDP solvers: second order methods and first order methods. Second order methods usually have running time with logarithmic dependence on $\epsilon$, while first order methods usually have polynomial dependence on $\epsilon$.

Second order methods can be further splitted into several lines: first line is cutting plane methods, for example [LSW15, JLSW20]. The algorithm in [LSW15, JLSW20] can solve semidefinite programming in $O(m(mn^{2}+m^{2}+n^{\omega}))$ time. The second line is interior point methods (associated with certain self-concordant barrier functions), for example, [NN92, JKL+20, HJS+22] use log-barrier function, and [Ans00, HJS+22] use hybrid barrier function. The algorithm in [JKL+20] can solve SDP in $O(\sqrt{n}(mn^{2}+n^{\omega}+n^{\omega}))$ time. Furthermore, [HJS+22] shows that as long as $m=\Omega(n^{2})$, we can solve semidefinite programming in $O(m^{\omega}+m^{2+1/4})$ time.

The interior point method is a second-order algorithm. Second-order algorithms usually have logarithmic dependence on the error parameter $1/\epsilon$. First-order algorithms do not need to use second-order information, but they usually have polynomial dependence on $1/\epsilon$. There is a long list of work focusing on first-order algorithms [AK07, GH16, AZL17, CDST19, LP20, YTF+19, JY11, ALO16].

For a semidefinite program with bounded treewidth, the work [ZL18] shows how to solve it in $\widetilde{O}(n^{1.5}\tau^{6.5})$ time.

Technique Overview

In this section, we explain the previous technique and summarize our new techniques.

In Section 2.1, we briefly summarize the techniques in [ZL18] and explain the barrier of that algorithm.

In Section 2.3, we briefly analyze running time of the algorithm in previous section and explain the bottlenecks.

In Section 2.4, we discuss how we improve the running time for bottlenecks, thus achieving an improved algorithm for low-treewidth SDP.

In Section 2.5, we discuss how we achieve improved algorithm for low-treewidth linear program.

In this section, we briefly summarize the technique in [ZL18].

Suppose we have an SDP of form (1) with a tree decomposition of maximum bag size $\tau$.

[ZL18] creates another SDP of smaller number of variables, where every bag in the tree decomposition becomes one $\tau\times\tau$ PSD matrix, which corresponds to an $\tau\times\tau$ principal minor in the original PSD matrix.

See Appendix 5 for a more detailed explanation of the program.

The new SDP has three types of contraints:

$A_{i}\bullet X_{j_{i}}=b_{i}$, which corresponds to linear constraints in the original SDP;

$\mathcal{N}_{i,j}(X_{i})=\mathcal{N}_{j,i}(X_{j})$, which says that when two minors overlap in the original PSD matrix, they should have the same value in overlapping positions;

$X_{j}\geq 0$, meaning that each minor should be PSD.

After this reduction, we run IPM iteration directly.In fact, [ZL18] ran IPM on the dual SDP, because the maximum degree of a bag in the tree decomposition could be large. However, we can easily make the maximum degree $O(1)$ by adding $O(n)$ bags. This does not change the asymptotic running time but results in a simpler algorithm.

[ZL18] uses interior point method to solve (5). For every step, we need to perform computation of the following kind

$H_{x}$ is the Hessian matrix, a block-diagonal matrix.

Because of the low-treewidth assumption, these updates can be implemeneted efficiently, as discussed below.

Number of iterations we need to run is controlled by the number of variables and geometry of the primal space. (More precisely, number of iterations is square root of sum of self-concordance value of all blocks.) Because we can have $O(n)$ $\tau\times\tau$ matrix variables, each of them is in the PSD cone, which is is $\tau$-self-concordant, the total number of iterations is

Each of the matrix factors in the above equation can be computed in $\widetilde{O}(n\tau^{6})$ time, and contains $O(n\tau^{4})$ non-zero entries, so cost per iteration is $\widetilde{O}(n\tau^{6})$.

So the overall running time of [ZL18]’s algorithm is $\widetilde{O}(n^{1.5}\tau^{6.5})$.

More specifically, [DLY21] gave an $O(n\tau^{2})$ algorithm for low-treewidth LP. Their central path equation is

where $x$ is the primal variable, $y$ is the dual variable, $s$ is the slack variable, and $\mu$ denotes the error. The central path is defined as the path of $(x,s)$ as $t$ goes from initial value to .

where $H_{x}=\nabla^{2}\phi(x)$ is the Hessian.

We only need to follow the central path approximately, meaning that when computing the steps, we could use $\overline{x}$ instead of $x$, where $\overline{x}$ is a vector close enough to $x$. The IPM algorithm works roughly in the following sense.

$x\leftarrow x+\delta_{x}$, $s\leftarrow s+\delta_{s}$

The general LP and SDP central path algorithm (without treewidth assumption) maintains $(AH_{\overline{x}}^{-1}A^{\top})^{-1}$ directly, since we don’t have the benefit of Cholesky decomposition (coming from treewidth assumption). This would lead to algorithms with cost-per-iteration super-linear in $n$.

The key idea of [DLY21] is that, instead of maintaining the pair $(x,s)$ on the central path explicitly, we maintain them implicitly (“multiscale coefficients”)

Similar ideas can be applied to our treewidth SDP case. We maintain primal-dual pairs $(x_{i},s_{i})$, and let them follow the central path. In each step, we need to run approximate Newton step

To maintain the central path, we need to have a data structure which can support (1) central path steps (8), and (2) report coordinates on which $x$ and $\overline{x}$ differ too much.

However, because we maintain $(x,s)$ implicitly, maintaining $\Phi x$ under central path steps and under change of multiscale representation and answering range queries is not a trivial task. We resolve this issue by using BlockBalancedSketch (Section 4.4.5), a block version of balanced sampling tree sketch in [DLY21]. Using BlockBalancedSketch and BlockVectorSketch (Section 4.4.4, an easy application of segment trees), we are able to implement BatchSketch (Section 4.4.3), a data structure for maintaining sketches of $(x,s)$.

Finally, by combining ExactDS and ApproxDS, we are able to maintain $(x,s)$ implicitly, and to maintain an approximation $(\overline{x},\overline{s})$ explicitly. This gives our central path maintenance algorithm CentralPathMaintenance (Section 4.2).

3 Bottlenecks for Running Time

In this section we give a brief analysis of running time. The actual analysis is much more complicated, but the highlight the bottlenecks here.

Therefore, the final running time is a result of balancing the total restart time and update time.

In the following, we plug in the exact exponents of $\tau$ and compute the running time.

Restart can be splitted into two steps, one is initialization and the other is output. The most time-consuming step is computing Choleky factorization in initialization.

As described in Algorithm 1, update can be splitted into mainly four substeps: Central path (ExactDS) move, ApproxDS query (using sketching data structure BatchSketch), ExactDS update, and sketching data structure BatchSketch update.

The central path move step takes $O(1)$ time per iteration because it only updates constant coefficients in the multiscale representation.

4 Improve Running Time Bottleneck

In this section we discuss how to improve the running time bottleneck. As described in the last section, the most time consuming step is computing Cholesky factorization $AH_{\overline{x}}^{-1}A^{\top}=L_{\overline{x}}L_{\overline{x}}^{\top}$ (which affects restart time), and updating Cholesky factorization under change of one variable block (which affects update time).

5 Improve Running Time of Low-Treewidth LP

In this section, we discuss the technique we use to achieve a more efficient algorithm for LP with bounded treewidth.

Recall that the key idea of [DLY21] is, instead of maintaining the primal and slack variables on the (approximate) central path explicitly, we maintain a sparsely-changing representation (multiscale representation) of them. The central path maintenance algorithm has two main parts (1) restart (which contains initialize and output), and (2) update. In every iteration, if certain conditions are satisfied, we restart the data structure. Afterwards, we perform a central path move and maintain the relevant data structures ExactDS and ApproxDS. The final running time is achieved by balancing restart time and update time.

We improve restart time by devising improved algorithms for computations related to Cholesky factorization. One main step in initialization part is to compute the Cholesky factorization of the matrix $AH_{\overline{x}}^{-1}A^{\top}=L_{\overline{x}}L_{\overline{x}}^{\top}$. Because of the treewidth assumption, the Cholesky factor $L_{\overline{x}}$ is $\widetilde{O}(\tau)$-column sparse, i.e., every column has at most $\widetilde{O}(\tau)$ non-zero entries. Using this property, [DLY21] is able to compute the Choleksy factorization in $\widetilde{O}(n\tau^{2})$ time.

We can do better by utilization more properties of the matrix. The key observation is that we can divide the indices of $AH_{\overline{x}}^{-1}A^{\top}$ into blocks of size $O(\tau)$, such that in the Cholesky factor is $\widetilde{O}(1)$-block sparse, i.e., every block column has at most $\widetilde{O}(1)$ non-zero block entries.

In this way, we can perform the Choleksy factorization algorithm on block level, achieving an algorithm (c.f. Lemma 6.4, 8.4) running in time

Using similar ideas, we are able to improve other Cholesky-related computations, including Cholesky factor inverse (c.f. Lemma 8.7), product of Cholesky factor and a batch of vectors (c.f. Lemma 8.8), and so on. These are all bottleneck steps in the original [DLY21] algorithm. By combining all these improvements, we achieve improved running time for restart.

The overall running time is sum of restart time and update time. In the LP case, the number of iterations $N$ is $\sqrt{n}$. Let $q$ be the data structure restart threshold. Then overall restart time is given by

where the last step is by taking $q=n^{0.5}\tau^{(\omega-3)/2}$.

Acknowledgements

The authors would like to thank Guanghao Ye and Lichen Zhang for useful discussions.

Here, we provide an organization for the rest of the paper.

In Section 3, we present a few basic definitions and results used in the paper.

In Section 4, we present a general framework which covers both semidefinite programming and linear programming.

In Section 6: we show how to further improve the running time of semidefinite programming solver to achieve an $\widetilde{O}(n\tau^{2\omega+0.5})$ time algorithm.

In Section 7, we show how to solve a more general kind of low-treewidth SDP (which we call decomposable SDP) using our general framework.

In Section 8, we show how to improve running time of low-treewidth linear programming to $\widetilde{O}(n\tau^{(\omega+1)/2})$.

Preliminaries

In Section 3.1, we define some basic notations. In Section 3.2, we define self concordant barrier. In Section 3.3, we define treewidth. In Section 3.4, we introduce some backgrounds for sketching matrices.

For two functions $f,g$, we use the shorthand $f\lesssim g$ (resp. $\gtrsim$) to indicate that $f\leq C\cdot g$ (resp. $\geq$) for an absolute constant $C$. We use $f\eqsim g$ to mean $cf\leq g\leq Cf$ for constants $c,C$.

We use $\omega$ to denote the exponent of matrix multiplication, i.e., multiplying an $n\times n$ matrix with another $n\times n$ matrix takes $n^{\omega}$ time. Currently, $\omega\approx 2.373$ [Wil12, AW21].

We will deal with block matrices and vectors a lot. Therefore we use a block-friendly notation.

In particular $\|x\|_{0,1}=\|x\|_{0}$, $\|x\|_{2,2}=\|x\|_{2}$.

2 Self-Concordant Barrier

We start with defining self concordant barrier,

A function $\phi$ is a self-concordant barrier if the first condition holds.

Log-barrier for the $n\times n$ PSD cone is $n$-self-concordant.

3 Treewidth

Let $G=(V,E)$ be a graph, a tree decomposition of $G$ is a tree $T$ with $b$ vertices, and $b$ sets $J_{1},\ldots,J_{b}\subseteq V$ (called bags), satisfying the following properties:

For every edge $(u,v)\in E$, there exists $j\in[b]$ such that $u,v\in J_{j}$;

For every vertex $v\in V$, $\{j\in[b]:v\in J_{j}\}$ is a non-empty subtree of $T$.

The treewidth of $G$ is defined as the minimum value of $\max\{|J_{j}|:j\in[b]\}-1$ over all tree decompositions.

4 Sketching Matrices

5 Sparse Cholesky Decomposition

In this section we state a few basic results on sparse Cholesky decomposition. The following definition essentially come from [Sch82].

Let $G$ be an undirected graph on $n$ vertices. An elimination tree $\mathcal{T}$ is a rooted tree on $V(G)$ together with an ordering $\pi$ of $V(G)$ such that for any vertex $v$, its parent is the smallest (under $\pi$) element $u$ such that there exists a path $P$ from $v$ to $u$, such that $\pi(w)\leq\pi(v)$ for all $w\in P-u$.

The following lemma is useful in proving elimination trees.

Let $G$ be an undirected graph on $n$ vertices. Let $\mathcal{T}$ be a rooted tree with $n$ vertices, satisfying the property that: for any path $u=v_{1},\cdots,v_{k}=v$ with $(v_{i},v_{i+1})\in E(G)$ for all $i\in[k-1]$, then there exists $i\in[k]$ such that $v_{i}$ is an ancestor of both $u$ and $v$. Then $\mathcal{T}$ together with any post-order traversal of $\mathcal{T}$ is an elimination tree.

We prove that $\mathcal{T}$ satisfies Definition 3.7. Let $v\in V(G)$ and $P$ be any path from $v$ to a vertex outside the subtree rooted at $v$. By assumption, there exists a vertex $u\in P$ which is an ancestor of $v$. Let $w$ be the parent of $v$. Then $\pi(u)\geq\pi(w)>\pi(v)$. Therefore $w$ is the smallest element reachable from $v$ using only elements before $v$. ∎

When any post-order traversal of $\mathcal{T}$ works, we omit the choice of $\pi$ and say $\mathcal{T}$ is an elimination tree.

Under the setting of Lemma 3.8, if depth of $\mathcal{T}$ is at most $\tau$, then the Cholesky decomposition $L$ can be computed in $O(n\tau^{2})$ time.

General Treewidth Program Solver Framework

In this section we establish a general framework for solving treewidth LP/SDP and related problems. Our framework takes block size into consideration and do not assume various block size-related parameters are constant. Our framework takes in certain subroutine running time as parameters. This allows us to see which subroutines are running time bottlenecks. Our SDP and LP results follow from the general framework with minimal problem-specific results in addition.

We briefly describe the outline of this section.

In Section 4.1, we present the definitions and backgrounds for this Section 4.

In Section 4.2, we present the main data structure which is central path maintenance data structure.

In Section 4.3, we present several computation-related lemmas which will be heavily used in our tasks.

In Section 4.4, we present several data structures that are being used in central path maintenance, including ExactDS (Section 4.4.1), ApproxDS (Section 4.4.2), BatchSketch (Section 4.4.3) and BlockVectorSketch(Section 4.4.4).

In Section 4.5, we prove correctness and running time of the central path maintenance data structure.

In Section 4.6, we prove the main result (Theorem 4.3).

We consider programs of the following form.

We make the following assumptions on Program (9) and define relevant parameters. These parameters will have an impact to the final running time (Theorem 4.3).

Assume that for each $\mathcal{K}_{i}$, we have a $\nu_{i}$-self-concordant barrier function $\phi_{i}$. Let $\nu_{\max}:=\max_{i\in[n]}\nu_{i}$.

Assume that $\phi_{i}$, $\nabla\phi_{i}$ and $\nabla^{2}\phi_{i}$ can be computed in $T_{H,i}$ time. Define $T_{H,\max}:=\max_{i\in[n]}T_{H,i}$ and $T_{H}:=\sum_{i\in[n]}T_{H,i}$.

Assume that it takes $T_{L}$ time to compute Cholesky decomposition $AHA^{\top}=LL^{\top}$.

Assume that it takes $T_{\Delta_{L},\max}$ time to update Cholesky decomposition, i.e., given $AHA^{\top}=LL^{\top}$ and $\Delta_{H}$ supported on a single diagonal block, computing $\Delta_{L}$ such that $A(H+\Delta_{H})A^{\top}=(L+\Delta_{L})(L+\Delta_{L})^{\top}$.

Assume that it takes $T_{Z}$ time to compute $L^{-1}v_{i}$ for all $i\in[m]$, where $v_{i}$ is supported on $\bigcup_{j\in\mathcal{P}(i)}B_{j}$, where $\mathcal{P}(i)$ is the set of ancestors of vertex $i$. This is used in Lemma 4.24.

Assume that $R$ is the diameter of $\mathcal{K}_{i}$. Assume that we are given an initial point $x$ such that $B(x,r)\subseteq\mathcal{K}$. Assume that there exists $x$ such that $Az=b$ and $B(x,r)\subseteq\mathcal{K}$.

Under assumptions in Definition 4.2, given any $0<\epsilon\leq\frac{1}{2}$, we can find $x\in\mathcal{K}$ with $Ax=b$ such that

2 Algorithm structure and CentralPathMaintenance

Our algorithm is a robust Interior Point Method (robust IPM). Details of the robust IPM will be given in Section A.

and explicitly maintain $(\overline{x},\overline{s})$ such that they remain close to $(x,s)$.

This task is handled by the CentralPathMaintenance data structure, which is the main data structure. The robust IPM algorithm (Algorithm 19,20) directly calls it in every iteration. This data structure is a generalization of CentralPathMaintenance data structure in [DLY21].

The CentralPathMaintenance data structure (Algorithm 2) has two main sub data structures, ExactDS (Algorithm 4 and Algorithm 5) and ApproxDS. ExactDS is used to to maintain $(x,s)$, and ApproxDS is used to monitor changes in $(x,s)$, and update $(\overline{x},\overline{s})$ when necessary.

MultiplyAndMove$(t)$: (See Lemma 4.38) It implicitly maintains

Assuming the function is called at most $N$ times and $t$ is monotonically decreasing from $t_{\max}$ to $t_{\min}$, the total running time is

Correctness and running time analysis of CentralPathMaintenance is deferred to Section 4.5 and Section 4.6, after we establish properties of the sub data structures.

3 Block Elimination Tree and Computation-Related Lemmas

Our algorithm is based on efficient computations involving Cholesky factorization and the block elimination tree. In this section we introduce the block elimination tree and prove a few useful lemmas on running time of relevant computations. They will be used repeatedly in the running time analysis of our algorithm.

Under the setting of Program 9, we always take $G$ to be the LP dual graph, and $M$ to be $AH_{\overline{x}}^{-1}A^{\top}$.

The following lemma is the block verion of Lemma 3.9.

We define another tree $\mathcal{T}^{\prime}$ with block pattern $(1,\ldots,1)$. For every vertex $v$ in $\mathcal{T}$, we replace it with a path (of an arbitrary ordering of elements in $v$). For all edges in $\mathcal{T}$, we connect top element of the child and the bottom element of the parent.

In this way, $\mathcal{T}^{\prime}$ satisfies the property that for any path $u=v_{1},\cdots,v_{k}=v$ with $(v_{i},v_{i+1})\in E(G)$ for all $i\in[m_{k}-1]$, then there exists $i\in[k]$ such that $v_{i}$ is an ancestor of both $u$ and $v$. By Lemma 3.9, $\mathcal{T}^{\prime}$ is a valid elimination tree. This implies that $\mathcal{T}$ is a valid block elimination tree. ∎

As in Definition 4.2, we assume that we are given a block elimination tree with (block) depth $\eta$. We can without loss of generality assume that the blocks are labeled in postorder, i.e., for any $i$ and $j\in\mathcal{P}(i)$, we have $i<j$.

Given a block elimination tree, we can efficiently perform many computations related to the Cholesky decomposition, as shown in the following lemma.

Assume that we are given a block elimination tree with block structure $(m_{1},\ldots,m_{m})$ and block depth $\eta$. Assume that we are given the Cholesky factorization $AHA^{\top}=LL^{\top}$ together with inverses of the diagonal blocks of $L$, i.e., $L_{i,i}^{-1}$ for all $i\in[m]$.

Then we have the following running time for matrix-vector multiplications.

Statements about $L^{\top}v$ and $L^{-\top}v$ follow from the Transposition principle [Bor57].

If $v$ is supported on a single block $i\in[m]$, then computing $Lv$ takes $\sum_{j\in\mathcal{P}(i)}m_{j}^{2}=O(\eta m_{\max}^{2})$ time by block column sparsity of $L$. So computing $Lv$ for general $v$ takes $O(\|v\|_{2,0}\eta m_{\max}^{2})$ time.

Consider Algorithm 3. By block column sparsity pattern of $L$, for every block $j\in[m]$ with $x_{j}\neq 0$, it takes $O(\eta m_{\max}^{2})$ time to compute $x_{j}$ and update $v\leftarrow v-L_{*,j}x_{j}$. So overall running time is $O(\|L^{-1}v\|_{2,0}\eta m_{\max}^{2})$.

$\mathcal{W}^{\top}v=H^{-1/2}A^{\top}L^{-\top}v$. So the result follows from combining (i)(vii)(v).

Assume that we are given a block elimination tree with block structure $(m_{1},\ldots,m_{m})$ and block depth $\eta$. Assume that we are given the Cholesky factorization $AHA^{\top}=LL^{\top}$ together with inverses of the diagonal blocks of $L$, i.e., $L_{i,i}^{-1}$ for all $i\in[m]$.

Then we have the following running time for matrix-vector multiplications, when we only need result for a subset of coordinates.

We have $(L^{-\top}v)_{S}=e_{S}^{\top}L^{-\top}v=(v^{\top}L^{-1}e_{S})^{\top}$. By column sparsity pattern of $L$, $L^{-1}e_{S}$ is supported on $S$. So $(L^{-\top}v)_{S}$ depends only on $v_{S}$. So we only need to compute $L_{S,S}^{-\top}v_{S}$, which takes $O(\eta^{2}m_{\max}^{2})$ time By Lemma 4.7(i).

We state a generic bound on $T_{Z}$ (recall Definition 7.1).

Computing each $L^{-1}v_{i}$ takes $O(\eta^{2}m_{\max}^{2})$ time by Lemma 4.7(iv). So computing $m$ of them takes $O(\eta^{2}mm_{\max}^{2})$ time. ∎

4 Data structures being used in CentralPathMaintenance

In Section 4.4, we present several data structures that are being used in central path maintenance, including:

ExactDS (Section 4.4.1). This data structure implicitly maintains the primal-dual solution pair $(x,s)$. This data structure is directly used by CentralPathMaintenance.

ApproxDS (Section 4.4.2). This data structure explicitly maintains the approximate primal-dual solution pair $(\overline{x},\overline{s})$. This data structure is directly used by CentralPathMaintenance.

BatchSketch (Section 4.4.3). This data structure maintains a sketch of $x$ and $s$, using BlockVectorSketch and BlockBalancedSketch. This data structure is used by ApproxDS.

BlockVectorSketch(Section 4.4.4). This data structure maintains a sketch of a vector (with block pattern) under single-point updates. This data structured is used by BatchSketch.

BlockBalancedSketch(Section 4.4.5). This data structure maintains a sketch of a vector of form $\mathcal{W}^{\top}v$, under updates of $(\overline{x},\overline{s})$. This data structure is used by BatchSketch.

In this section, we present our ExactDS (Algorithm 4 and Algorithm 5). In Theorem 4.11, we provide our theoretical statement for Algorithm 4 and Algorithm 5. This is a block-based generalization of MultiscaleRepresentation data structure of [DLY21].

We can write the central path update using multiscale representation

The data structure supports the following functions:

time, with initial value of the primal-dual pair $(x,s)$, its initial approximation $(\overline{x},\overline{s})$, and initial approximate timestamp $\overline{t}$.

time, and output the changes in variables $\delta_{h},\delta_{\epsilon_{x}},\delta_{\epsilon_{s}},\delta_{H_{\overline{x}}^{1/2}\widehat{x}},\delta_{H_{\overline{x}}^{-1/2}\widehat{s}},\delta_{\overline{H}_{\overline{x}}^{-1/2}c_{x}}$.

Furthermore, $\delta_{h},\delta_{\epsilon_{x}},\delta_{\epsilon_{s}}$ changes in $O(\eta(\|\delta_{\overline{x}}\|_{2,0}+\|\delta_{\overline{s}}\|_{2,0}))$ blocks, and $\delta_{H_{\overline{x}}^{1/2}\widehat{x}},\delta_{H_{\overline{x}}^{-1/2}\widehat{s}},\delta_{\overline{H}_{\overline{x}}^{-1/2}c_{x}}$ changes in $O(\|\delta_{\overline{x}}\|_{2,0}+\|\delta_{\overline{s}}\|_{2,0})$ blocks.

Query$x(i\in[n])$: Output $x_{i}$ in $\widetilde{O}(n_{\max}^{2}+\eta^{2}m_{\max}^{2})$ time. This function is used by ApproxDS.

Query$s(i\in[n])$: Output $s_{i}$ in $\widetilde{O}(n_{\max}^{2}+\eta^{2}m_{\max}^{2})$ time. This function is used by ApproxDS.

By combining Lemma 4.12, 4.13, 4.15, 4.16. ∎

ExactDS correctly maintains an implicit representation of $(x,s)$, i.e., invariant

Initialize: Initialization satisfies the invariant because $\widehat{x}=x$, $\widehat{s}=s$, $\epsilon_{x}=\epsilon_{s}=0$, $\beta_{x}=\beta_{s}=0$. Furthermore, we correctly initialize $H_{\overline{x}}$, $L_{\overline{x}}$, $\overline{\alpha}$, $\overline{\delta}_{\mu}$, $c_{x}=H_{\overline{x}}^{-1/2}\overline{\delta}_{\mu}$, $h=L_{\overline{x}}^{-1}AH_{\overline{x}}^{-1}\overline{\delta}_{\mu}$.

Move: By inspecting terms with coefficient $\beta_{x},\beta_{s}$, we see that we move in the correct direction and step size.

Update: We would like to prove that Update does not change the value of $(x,s)$. First note that $H_{\overline{x}}$ and $L_{\overline{x}}$, $\overline{\alpha}$, $\overline{\delta}_{\mu}$ are update correctly. The remaining updates are separated into two steps: Update$H$ and Update$\mathcal{W}$.

So $c_{x}$ and $h$ are updated correctly. Furthermore, immediately after Algorithm 5, Line 24, we have

So $x$ is updated correctly, i.e., after Update$H$ finishes, we have

Immediately after Algorithm 5, Line 24, we have

So $s$ is updated correctly, i.e., after Update$H$ finishes, we have

So $x$ is updated correctly, i.e., after Update$\mathcal{W}$ finishes, we have

Immediately after Algorithm 5, Line 33, we have

So $s$ is updated correctly, i.e., after Update$\mathcal{W}$ finishes, we have

Computing $H_{\overline{x}}$ takes $T_{H}$ time. Computing $L_{\overline{x}}$ takes $T_{L}$ time.

ExactDS.Move (Algorithm 4) runs in $O(1)$ time.

All steps in this procedure can be done in $O(1)$ time. ∎

Each call of ExactDS.Update (Algorithm 5) runs in

time. Furthermore, $\delta_{h},\delta_{\epsilon_{x}},\delta_{\epsilon_{s}}$ changes in $O(\eta(\|\delta_{\overline{x}}\|_{2,0}+\|\delta_{\overline{s}}\|_{2,0}))$ blocks, and $\delta_{H_{\overline{x}}^{1/2}\widehat{x}},\delta_{H_{\overline{x}}^{-1/2}\widehat{s}},\delta_{\overline{H}_{\overline{x}}^{-1/2}c_{x}}$ changes in $O(\|\delta_{\overline{x}}\|_{2,0}+\|\delta_{\overline{s}}\|_{2,0})$ blocks.

It remains to analyze two parts Update$H$ and Update$\mathcal{W}$. We will analyze these two parts separately in the next a few paragraphs.

time by Lemma 4.8(i). Also, $\delta_{h}$ is supported on $O(\|\delta_{x}\|_{2,0})$ paths in the block elimination tree, thus $O(\eta\|\delta_{x}\|_{2,0})$ blocks, or $O(\eta n_{\max}\|\delta_{x}\|_{2,0})$ dimension.

We compute $\delta_{\widehat{x}}$ and $\delta_{\widehat{s}}$ from left to right. This takes

Computing $\delta_{\widehat{x}}$ and $\delta_{\widehat{s}}$ takes

To compute $\delta_{\epsilon_{x}}$ and $\delta_{\epsilon_{s}}$, we first compute $(L^{-\top}(\beta_{x}h+\epsilon_{x}))_{S}$, where $S\in[m]$ is the row support of $\Delta_{L}$, which can be decomposed into at most $\|\delta_{\overline{x}}\|_{2,0}$ paths. This takes

time by Lemma 4.8(i). So computing $\delta_{\epsilon_{x}}$ and $\delta_{\epsilon_{s}}$ takes

Combining everything finishes the proof of running time.

For the claim on output sparsity, note that $\delta_{h},\delta_{\epsilon_{x}},\delta_{\epsilon_{s}}$ change in $O(\|\delta_{\overline{x}}\|_{2,0}+\|\delta_{\overline{s}}\|_{2,0})$ paths, and that $\delta_{H_{\overline{x}}^{1/2}\widehat{x}},\delta_{H_{\overline{x}}^{-1/2}\widehat{s}},\delta_{\overline{H}_{\overline{x}}^{-1/2}c_{x}}$ change only in the support of $\delta_{\overline{x}}$ and support of $\delta_{\overline{s}}$. ∎

Correctness is by Lemma 4.12. By Lemma 4.7(viii). ∎

ExactDS.Query$x$ (Algorithm 4) and ExactDS.Query$s$ (Algorithm 4) runs in $O(n_{\max}^{2}+\eta^{2}m_{\max}^{2})$ time and returns the correct answer.

Correctness is obvious. Running time follows from Lemma 4.8(ii). ∎

4.2 ApproxDS

In this section we introduce ApproxDS, data structure for maintaining a sparsely-changing approximation of $(x,s)$.

Furthermore, total time cost over all queries is at most

The proof for $s$ is similar and omitted.

Initialize: By Initialize part of Theorem 4.21.

Then the running time bound for Query$x$ follows from Query part of Theorem 4.11 and Query$x$ part of Theorem 4.21.

The proof for $s$ is similar and omitted. ∎

4.3 BatchSketch

In this section we introduce BatchSketch, our data structure for maintaining a sketch of $H_{\overline{x}}^{1/2}x$ and $H_{\overline{x}}^{-1/2}s$.

For this task, we need another tree structure on the set of variable blocks.

If $v$ is a leaf node of $\mathcal{S}$, then $|\chi(v)|=1$

For any node $v$ of $\mathcal{S}$, the set \{\chi(c):\text{c$is a child of$v}\} forms a partition of $\chi(v)$.

The partition tree does not need to (but can) have any relationship with the block elimination tree. The partition tree will need to satisfy $O(1)$ maximum degree and $\widetilde{O}(1)$ depth. We will choose the partition tree in Section 4.4.5 so that the BlockBalancedSketch data structure can be efficiently maintained.

Data structure BatchSketch (Algorithm 8, 9) supports the following operations:

For every query, with probability at least $1-\delta$, the return values are correct, and costs at most

For every query, with probability at least $1-\delta$, the return values are correct, and costs at most

Correctness: Correctness of Update follows from combining Lemma 4.23 and Lemma 4.29. In the following we focus on correctness of queries.

Proof of correctness of Query$s$ is similar and omitted.

Initialize: Follows from Lemma 4.23 and Lemma 4.30.

Update: Follows from Lemma 4.23 and Lemma 4.31.

Then the result follows from Lemma 4.23 and Lemma 4.35.

Query$s$: Proof is similar to Query$x$ and is omitted. ∎

4.4 BlockVectorSketch

In this section we present BlockVectorSketch (Algorithm 10), data structure for maintaining a vector with block structure under sparse changes. This is generalization of VectorSketch in [DLY21].

Query$(v\in V(\mathcal{S}))$: Outputs $\Phi_{\chi(v)}x_{\chi(v)}$ in $O(r\log n)$ time.

Note that in Theorem 4.23, the running time does not depend on depth of the partition tree.

Correctness follows from from guarantees of segment trees.

Update: For every modified coordinate, it takes $O(r\log n)$ time to update $\mathcal{T}$. So total time cost is $O(r\|\delta_{x}\|_{0}\log n)$.

Query: Takes $O(r\log n)$ time because of segment tree query time.

4.5 BlockBalancedSketch

Initialize$(\mathcal{S},\chi,\Phi,\overline{x},h)$: Initializes the data structure in

Query$(v)$: Outputs $\Phi_{\chi(v)}(\mathcal{W}^{\top}h)_{\chi(v)}$ in $\widetilde{O}(r\eta^{2}m_{\max}^{2})$ time.

The algorithm is a block version of [DLY21, Section 6.6.1]. We nevertheless present a full proof for completeness.

Let us first describe the main idea of the algorithm. Note that in BlockBalancedSketch, we have the freedom of choosing the partition tree $(\mathcal{S},\chi)$. Then this tree is used by BatchSketch and BlockVectorSketch. Therefore we can choose a partition tree which works well for our purpose.

Let us consider the operations BlockBalancedSketch needs to support. It needs to support updating $\overline{x}$ and $h$, and answering queries on a subtree $\chi(v)$. Change of one block in $\overline{x}$ leads to change of one path in the block elimination tree $\mathcal{T}$, and change of one block in $h$ leads to change of one subtree in $\mathcal{T}$. Therefore we essentially would like a data structure which supports subtree and path updates and subtree queries. With this in mind, it is natural to use heavy-light decomposition [ST81].

Given a rooted tree $\mathcal{T}$ with $m$ vertices, we can construct in $O(m)$ time an ordering $\pi$ of the vertices such that (1) every path in $\mathcal{T}$ can be decomposed into $O(\log m)$ contiguous subseqeuences under $\pi$, and (2) every subtree in $\mathcal{T}$ is a single contiguous subsequence under $\pi$.

We fix an ordering $\pi$ of $[m]$ using the heavy-light decomposition (Lemma 4.25). We construct complete binary tree $\mathcal{B}$ with leaves $[m]$ and ordering $\pi$.

To get a partition tree, we need to add leaves $[n]$ to $\mathcal{B}$. For every coordinate $i\in[n]$, let $\mathsf{low}^{\mathcal{T}}(i)$ be any vertex $v$ in $\mathcal{T}$ such that the support of $A_{*,i}$ is contained in $\mathcal{P}^{\mathcal{T}}(v)$. (Recall that for a block elimination tree, support of $A_{*,i}$ is contained in a path for any $i\in[n]$.) For any $j\in[m]$, we construct a complete binary tree with leaves $\{i\in[n]:\mathsf{low}^{\mathcal{T}}(i)=j\}$ and hang this tree under leaf $j$ in $\mathcal{B}$. This finishes the construction of a partition tree $(\mathcal{S},\chi)$.

The following definitions come from [DLY21].

We make the following definitions. For $v\in\mathcal{B}$, define

where $\overline{\chi}(v)$ is the set of leaves in $\mathcal{B}$ which are descendants of $v$.

For $u\in\mathcal{T}$, define $\Lambda^{\circ}(u)$ be the lowest vertex $v\in\mathcal{B}$ such that $u\in\overline{\Lambda}(v)$. In other words, $\Lambda^{\circ}(u)$ is the lowest vertex $v\in\mathcal{B}$ such that $\overline{\chi}(v)$ contains $\mathcal{D}^{\mathcal{T}}(u)$ (set of descendants of $u$ in $\mathcal{T}$). Therefore $\Lambda^{\circ}(u)$ is well-defined.

For any $v$, $\Lambda(v)$ is contained in the union of two paths in $\mathcal{T}$. In particular, $|\Lambda(v)|=O(\eta)$.

The order $\pi$ in Lemma 4.25 is a pre-order traversal of $\mathcal{T}$. Let $u$ be the last vertex before $\overline{\chi}(v)$ under $\pi$, and $w$ be the first vertex after $\overline{\chi}(v)$ under $\pi$. Then $\Lambda(v)$ is contained in $\mathcal{P}^{\mathcal{T}}(u)\cup\mathcal{P}^{\mathcal{T}}(w)$. ∎

BlockBalancedSketch correctly maintains a sketch of $\mathcal{W}^{\top}h$, and all query results are returned correctly.

We prove that the following invariant always holds after every call to BlockBalancedSketch.

Initialize: The invariants are clearly satisfied after initialization.

Query: If $v\in\mathcal{S}\backslash\mathcal{B}$ then we compute $J_{v}L_{\overline{x}}[t]^{-\top}h$ directly and the result is correct.

Now assume $v\in\mathcal{B}$. We update $t_{v}\leftarrow t$, and update $Z_{v}$ and $y_{v}^{\triangledown}$ accordingly. We have Note that

because Invariant (13) and column sparsity of $Z_{v}$. So

So Invariant (11) is satisfied. Updating $y_{v}^{\triangledown}$ ensures that Invariant (12) is satisfied. Finally, the return value is correct because of definition of $y_{v}^{\triangledown}$ and $y_{v}^{\vartriangle}$.

Update: We divide the proof into several steps. Correctness of Update$x$ follows from correctness of Update$L$ and Update$H$ (which we will prove below).

Correctness of Update$H$: We update $t_{v}$, $Z_{v}$ and $y_{v}^{\triangledown}$ for $v\in S=\mathcal{P}^{\mathcal{B}}(\Lambda^{\circ}(\mathsf{low}^{\mathcal{T}}(i)))$. In other words, $S$ is the set of all vertices $v$ with $\mathsf{low}^{\mathcal{T}}(i)\in\overline{\Lambda}(v)$. For any $v\not\in S$, $L[t]\cdot I_{\overline{\Lambda}(v)}$ is not changed. So Invariant (13) is preserved for $v\not\in S$.

Fix $v\in S$. In Algorithm 13, Line 5, we update $t_{v}$ to $t-1$. In Algorithm 13, Line 6, we update $t_{v}$ to $t$. By a similar computation as the one we did for Query, $Z_{v}$ is updated correctly (i.e., Invariant (11) is preserved). This implies $y_{v}^{\triangledown}$ is updated correctly (i.e., Invariant (12) is preserved).

Correctness of Update$L$: We update $J_{v}$, $Z_{v}$, $y_{v}^{\triangledown}$ for all $v\in\mathcal{P}^{\mathcal{S}}(u)$ (where $\chi(u)=\{i\}$). Invariant (13) is preserved because $t_{v}$ does not change. Invariant (10), (11), (12) are preserved by our choice of $\delta_{J_{v}}$, $\delta_{Z_{v}}$, $\delta_{y_{v}^{\triangledown}}$.

Correctness of Algorithm 12, Line 6 to Line 11: This part is “Update$h$”. For $i\in[m]$ with $\delta_{h,i}\neq 0$, we update $y_{u}^{\triangledown}$ for $u\in\mathcal{B}$ such that $i\in\overline{\Lambda}(u)$. Recall that $\mathcal{P}^{\mathcal{B}}(\Lambda^{\circ}(i))$ contains all vertices $u$ such that $i\in\overline{\Lambda}(u)$. So Invariant (12) is satisfied. ∎

BlockBalancedSketch.Initialize (Algorithm 11) costs

Computing $H_{\overline{x}}$ takes $T_{H}$ time. Computing $H_{\overline{x}}^{-1}$, $H_{\overline{x}}^{-1/2}$ takes $O(T_{n})$ time. Computing $L_{\overline{x}}[t]$ takes $T_{L}$ time.

Computation of $Z_{v}$: To compute $Z_{v}$, we first compute $Z_{v}$ for all leaves $v\in\mathcal{B}$. This takes $rT_{Z}$ time by assumption (Definition 4.2). Then we sum from bottom to up to compute $Z_{v}$ for all $v\in\mathcal{B}$. Because height of the partition tree is $\widetilde{O}(1)$, every non-zero entry in the leaves gets propagated $\widetilde{O}(1)$ times. So computing $Z_{v}$ takes $\widetilde{O}(rT_{Z})$ time in total.

Summing everything up we get the desired running time. ∎

BlockBalancedSketch.Update (Algorithm 12) costs

For each $i\in[m]$ with $\delta_{h,i}\neq 0$ and each $v$, it takes $O(rm_{\max})$ time to update $y_{u}^{\triangledown}$. So the total time needed to update $y_{u}^{\triangledown}$ is $O(rm_{\max}\|\delta_{h}\|_{2,0})$. ∎

BlockBalancedSketch.Update$\overline{x}$ (Algorithm 12) costs

BlockBalancedSketch.Update$L$ (Algorithm 13) costs $O(r\eta^{2}m_{\max}^{2})$ time.

By Lemma 4.28, we have $|\Lambda(v)|=O(\eta)$. So we can compute $(L_{\overline{x}}[t-1]-L_{\overline{x}}[t_{v}])\cdot I_{\Lambda(v)}$ in $O(\eta^{2}m_{\max}^{2})$ time by Lemma 4.7(ii). Then computing $(L_{\overline{x}}[t-1]-L_{\overline{x}}[t_{v}])\cdot I_{\Lambda(v)}\cdot Z_{v}^{\top}$ takes $O(r\eta^{2}m_{\max}^{2})$ time. Finally, computing $\delta_{Z_{v}}=L_{\overline{x}}[t-1]^{-1}\cdot(L_{\overline{x}}[t-1]-L_{\overline{x}}[t_{v}])\cdot Z_{v}^{\top}$ takes $O(r\eta^{2}m_{\max}^{2})$ time by Lemma 4.7(iv). Analysis for $\delta_{Z_{v}}^{\prime}$ is the same.

Computing $\delta_{y_{v}}^{\triangledown}$ takes $O(r\eta m_{\max})$ time by sparsity pattern of $\delta_{Z_{v}}+\delta_{Z_{v}}^{\prime}$.

Summing everything up we get the desired running time. ∎

BlockBalancedSketch.Query (Algorithm 11) takes $O(r\eta^{2}m_{\max}^{2})$ time.

If $v\in\mathcal{S}\backslash{\mathcal{B}}$, then (each row of) $J_{v}$ is supported on a path. So computing $J_{v}L_{\overline{x}}[t]^{-\top}h$ takes $O(r\eta^{2}m_{\max}^{2})$ time by Lemma 4.7(iv).

Now suppose $v\in\mathcal{B}$. By Lemma 4.28, we have $|\Lambda(v)|=O(\eta)$. So we can compute $(L_{\overline{x}}[t]-L_{\overline{x}}[t_{v}])\cdot I_{\Lambda(v)}$ in $O(\eta^{2}m_{\max}^{2})$ time by Lemma 4.7(ii). Then computing $\Delta_{L_{\overline{x}}}\cdot Z_{v}^{\top}$ takes $O(r\eta^{2}m_{\max}^{2})$ time. Furthermore, $\Delta_{L_{\overline{x}}}$ has columns supported on two paths. Therefore, computing $L_{\overline{x}}[t]^{-1}\cdot\Delta_{L_{\overline{x}}}\cdot Z_{v}^{\top}$ takes $O(r\eta^{2}m_{\max}^{2})$ time by Lemma 4.7(iv). So the total time needed to compute $\delta_{Z_{v}}$ is $O(r\eta^{2}m_{\max}^{2})$.

Computing $y_{v}^{\triangledown}$ takes $O(r\eta m_{\max})$ time by sparsity pattern of $Z_{v}$. Computing $y_{v}^{\vartriangle}$ takes $O(r\eta m_{\max})$ time because $|\Lambda(v)|=O(\eta)$.

Summing everything up we get the desired running time. ∎

Combining everything we finish the proof of Lemma 4.24.

Combining Lemma 4.29, Lemma 4.30, Lemma 4.31, Lemma 4.35. ∎

5 Analysis of CentralPathMaintenance

The goal of this section is to prove Theorem 4.4.

We first prove correctness of CentralPathMaintenance.

We correctly maintain a multiscale representation of $(x,s)$ because of correctness of $\mathsf{exact}.\textsc{Update}$ (Lemma 4.12).