Oblivious Sketching-based Central Path Method for Solving Linear Programming Problems
Year: 2020

Abstract:
In this work, we propose a sketching-based central path method for solving linear programmings, whose running time matches the state of art results Cohen et al. (2019b); Lee et al. (2019). Our method opens up the iterations of the central path method and deploys an ”iterate and sketch” approach towards the problem by introducing a new coordinate-wise embedding technique, which may be of independent interest. Compare to previous methods, the work Cohen et al. (2019b) enjoys feasibility while being nonoblivious, and Lee et al. (2019) is oblivious but infeasible, and relies on dense sketching matrices such as subsampled randomized Hadamard/Fourier transform matrices. Our method enjoys the benefits of being both oblivious and feasible, and can use sparse sketching matrix Nelson & Nguyên (2013) to speed up the online matrix-vector multiplication. Our framework for solving LP naturally generalizes to a broader class of convex optimization problems including empirical risk minimization.

heading: 1 Introduction
text: Linear programming is one of the fundamental models widely used in both theory and practice. It has been extensively applied in many fields such as economics Tintner (1955); Dorfman et al. (1987), operations research Delson & Shahidehpour (1992), compressed sensing Donoho (2006); Candes et al. (2006), medical studies Mangasarian et al. (1990; 1995), adversarial deep learning Wong & Kolter (2018); Weng et al. (2018), etc., due to its simple and intuitive structure. The problem of solving linear programmings has been studied since the 19-th century Sierksma & Zwols (2015).
Consider solving a general linear program in standard form minAx=b,x≥0 c>x of size A ∈ Rd×n without redundant constraints. For the generic case d = Ω(n) we considered in this paper, the state of art results take a total running time of O∗(nω + n2.5−α/2 + n2+1/6)1 to obtain a solution of δ accuracy in current matrix multiplication time Cohen et al. (2019b); Lee et al. (2019), where ω is the exponent of matrix multiplication whose current value is roughly 2.373 Williams (2012); Le Gall (2014), and α is the dual exponent of matrix multiplication whose current value is 0.31 Le Gall & Urrutia (2018). The breakthrough work due to Cohen, Lee, and Song Cohen et al. (2019b) improves the long standing running time of O∗(n2.5) since 1989 Vaidya (1989). For the current ω and α, Cohen et al. (2019b) algorithm takes O∗(n2.373) time.
For the current state-of-art results, the work Cohen et al. (2019b) involves a non-oblivious sampling technique, whose sampling set and size changes along the iterations. It avoids the possibilities of implementing expensive calculations in the preprocessing stage and also makes it harder to extend to other classical optimization problems. On the other hand, the work Lee et al. (2019) only maintains an infeasible update in each iteration and requires the usage of dense sketching matrices, which will ruin the potential sparsity structure of the original linear programs. Thus, a natural question to ask is:
1We use O∗ hides no(1) and logO(1)(1/δ) factors.
Is there an oblivious and feasible algorithm for solving linear programming programs in fast running time (i.e. current matrix multiplication time) ?
In this work, we propose a both oblivious and feasible (per iteration)2 method that solves linear programs in the same running time as the state of art.
The algorithm we propose is a sketching-based short step central path method. The classical short step method follows the central path in the interior of the feasible region. It decreases the complementarity gap uniformly by roughly a 1− 1/√n factor in each iteration and takes O∗( √ n) iterations to converge. This results in O∗( √ n)× n = O∗(n1.5) coordinate updates throughout the algorithm Vaidya (1989). Compared to Cohen et al. (2019b); Lee et al. (2019), our randomized algorithm improves this amount (in Vaidya (1989)) of updates via a different approach. We only updating a O∗( √ n)-dimensional subspace in each iteration while keeping the same number of iterations √ n through an Oblivious Coordinate-wise Embedding (OCE) technique. Thus, our method updates O∗(n) dimensions in total, which is nearly optimal.
The coordinate-wise embedding we introduce in this work is a distribution of matrices R ∈ Rbsketch×n with bsketch n such that, for any inner product g>h between two ndimensional vector g, h ∈ Rn, with ”high” probability g>R>Rh approximates g>h well. In the case of solving linear programmings, we approximate the calculation of matrix-vector multiplication Ph in each iteration by PR>Rh through OCE, such that the resulting random vector is close to previous one in each coordinate, i.e., (PR>Rh)i ≈ (Ph)i for all i ∈ [n]. Combining with lazy update and low-rank update techniques to maintain the query structure PR>Rh for any input vector h ∈ Rn, we can ensure the new random path is still close to the central path throughout the iterations. Therefore, our method decrease the average running time per iteration while keeping the same number of iterations. Furthermore, the sketching matrix R in our approach can be chosen in an oblivious way since it does not depend on the algorithm updates. Compare to previous work Lee et al. (2019), our approximation form PR>Rh also helps admit a closed form solution in each iteration for solving LP. Thus, our approach takes the advantages of being oblivious and feasible, compared to other state of art results Cohen et al. (2019b); Lee et al. (2019).
We state our main result as follows:
Theorem 1.1 (Main result, informal). Given a linear program minAx=b,x≥0 c>x with no redundant constraints. Let δlp denotes precision. Our algorithm takes O(n
2.373 log(n/δlp)) time to solve this LP.

heading: 1.1 Related works
text: Linear programming. Linear programmings have been studied for nearly a century. One of the first and most popular LP algorithm is the simplex algorithm Dantzig (1947). Despite it works well in practical small size problems, the simplex algorithm is known to be an exponential time algorithm in the worst case of Klee-Minty cube Klee & Minty (1972). The first polynomial time algorithm for solving LP is the ellipsoid method Khachiyan (1980) proposed by Khachiyan. Although this algorithm runs in polynomial time in theory, but in practice this algorithm runs much slower than the simplex algorithm. The interior point type of methods Karmarkar (1984) have both polynomial running time in theory and fast and stable performance in practice. In the case of d = Ω(n) considered in this work, Karmarkar’s algorithm Karmarkar (1984) takes O∗(n3.5) running time. Then it was improved to O∗(n3) in the work Renegar (1988); Vaidya (1987). In 1989, Vaidya further proposed an algorithm that takes a running of O∗(n2.5). This result hasn’t been improved until recent work due to Cohen, Lee and Song Cohen et al. (2019b).
Sketching. Classical sketching methodology proposed by Clarkson & Woodruff (2013) is the so-called ”sketch and solve”. The most standard and well-known applications are
2In each iteration, we approximate the central path by solving a linear system. Our approach constructs a randomized oblivious system equation which can be solved exactly. While previous work Cohen et al. (2019b) constructs a non-oblivious one, and Lee et al. (2019) doesn’t solve the system exactly.
linear regression Clarkson & Woodruff (2013); Nelson & Nguyên (2013); Andoni et al. (2018); Clarkson et al. (2019); Song et al. (2019a) and low-rank approximation Clarkson & Woodruff (2013); Nelson & Nguyên (2013); Boutsidis & Woodruff (2014); Clarkson & Woodruff (2015b;a); Razenshteyn et al. (2016); Song et al. (2017; 2019b;c). It further generalizes to subspace Wang & Woodruff (2019); Li et al. (2020a), positive semi-definite matrices Clarkson & Woodruff (2017), total least regression Diao et al. (2019), quantile regression Li et al. (2020b), tensor regression Li et al. (2017); Diao et al. (2018), tensor decomposition Song et al. (2019d).
The sketching method we deploy in this work is called ”‘iterate and sketch” Song (2019). The major difference between classical “sketch and solve“, and “iterating and sketch“ is: the first one only applied the sketch once at very beginning to reduce the dimension of problem, while does not modify the solver; the second one opens up and modifies the solver by applying sketching techniques iteratively in each iteration. The idea of “iterate and sketch” has been applied to a number of problems, e.g. computing John Ellipsoid Cohen et al. (2019a), Newton method Pilanci & Wainwright (2016; 2017), tensor decomposition Wang et al. (2015); Song et al. (2016), training deep neural network Brand et al. (2020).
Empirical risk minimization Empirical risk minimization (ERM) problem is a fundamental question in statistical machine learning. Extensive literature has been devoted to study this topic Nesterov (1983); Vapnik (1992); Nesterov (1998); Polyak & Juditsky (1992); Nemirovski et al. (2009); Nesterov (2013); Vapnik (2013). First-order methods and a series of accelerated gradient descent algorithms for ERM are well-developed and studied Jin et al. (2018); Johnson & Zhang (2013); Nesterov & Stich (2017); Xiao & Zhang (2014); Allen-Zhu (2018). These rates depend polynomially on the smoothness/strong convexity of the objective in order to achieve a log(1/ ) dependence on the error parameter .
Notations For a positive integer n, we use [n] to denote set {1, 2, · · · , n}. For vectors x, z ∈ Rn and parameter ∈ (0, 1), we use x ≈ z to denote (1− )zi ≤ xi ≤ (1+ )zi, ∀i ∈ [n]. For any scalar t, we use a ≈ t to denote (1− )t ≤ ai ≤ (1 + )t, ∀i ∈ [n]. Given diagonal matrices X = diag(x) ∈ Rn×n, S = diag(s) ∈ Rn×n, we use XS to denote the diagonal matrix with (XS )i,i = xi/si,∀i ∈ [n].

heading: 2 Technique overview
text: In this section, we discuss the key ideas of our approach based on the central path method.

heading: 2.1 Short Step Central Path Method
text: Consider the following standard primal and dual problems of linear programmings:
min Ax=b,x≥0 c>x (primal) and max A>y+s=c, x,s≥0 b>y (dual)
where A ∈ Rd×n is full rank with d = O(n). Then (x, y, s) is an optimal solution if and only if it satisfies the following optimality conditions Vanderbei et al. (2015):
Ax = b, x ≥ 0 (primal feasibility) A>y + s = c, s ≥ 0 (dual feasibility)
xisi = 0 for all i (complementary slackness)
The classical interior point method finds an optimal solution by following the central path in the interior of the feasible region, which is defined as the tuple (x, y, s, t) that satisfies:
Ax = b, x > 0
A>y + s = c, s > 0 (1)
xisi = t for all i
where t > 0 is called the complementarity gap. It has been shown we can obtain an initialization point on the central path with t = 1 according to Ye et al. (1994). Then in each iteration, the classical algorithm deceases the complementarity gap uniformly from t to
ηt with η < 1, and solves Eq. (1). As t approaches 0, the central path will converge to an optimal solution. The short step central path method approximately solves Eq. (1) by the following linear system:
Xδs + Sδx = δµ,
Aδx = 0, (2)
A>δy + δs = 0,
where X = diag(x), S = diag(s) and we update the solution by x = x + δx, s = s + δs and y = y + δy. Denote the actual complementarity gap µ ∈ Rn defined under Eq. (2) as µi = xisi for i ∈ [n]. Then Eq. (2) maintains the feasibility conditions while approximately moving the gap from µ to µ+ δµ. As long as the actual complementarity gap µ is always close to the aiming complementarity gap t during the algorithm, we can assure the actual complementarity gap µ will converge to 0 as t goes to 0, which leads us to an optimal solution.
To solve the linear system (2), note when A is full-rank, it has an unique solution explicitly given by:
δx = X√ XS (I − P ) 1√ XS δµ and δs = S√ XS P 1√ XS δµ, (3)
where P = √ X S A > (AXS A> )−1 A √ X S is an orthogonal projection matrix.
Literature Vaidya (1989) shows we can choose η to be roughly 1− 1√ n , and the algorithm
converges in O∗( √ n) iterations. Therefore, the total running time needed of solving LP by explicit solution Eq. (3) is O∗(nω+1/2).

heading: 2.2 Sketching-based Central Path Method
text: In the following subsections, we discuss our approach of sketching-based central path method. In Subsection 2.3, we introduce the coordinate-wise embedding (CE) technique. We discuss the difference between CE and classical sketching techniques, such as Johnson-Lindenstrauss (JL) Lemma and subspace embedding (SE). We also discussed the results of applying common sketching matrices in CE. In Subsection 2.4, we explain why our sketching-based central path method can speed up the computation. In Subsection 2.5, we explain the reason why our sketch-based central path method is feasible and oblivious. In Subsection 2.6, we discuss the projection maintenance needed for the algorithm updates.
Algorithm 1 Main algorithm (simplified)
1: procedure Main(A, b, c, δlp) . Theorem D.1 2: Modify the linear program and obtain an initial x and s according to Ye et al. (1994) 3: . Ensure the initial complementarity gap start with xisi = 1 4: Initialize: sketching size bsketch = O ∗( √ n), parameters = O∗(1), projection maintenance
datastructure mp 5: t← 1 . Initialize the aiming gap t 6: while t > δ2lp/(32n 3) do . Stop once the precision is good 7: tnew ← (1− 3 √ n
)t . Decrease the aiming gap by 1− 1/√n in each iteration 8: µ← xs . Actual gap 9: δµ ← ( t new
t − 1)xs− 2 · tnew · ∇Φλ(µ/t−1)‖∇Φλ(µ/t−1)‖2 . Here Φλ(r) := ∑n i=1 cosh(λri) is the
potential function characterize the `∞ closeness between actual path µ̃ and actual path t̃. We have Φλ in the update to help ensure ũ ≈0.1 t. 10: (xnew, snew)← StochasticStep(mp, x, s, δµ, bsketch, ) . Algorithm 2 11: (x, s)← (xnew, snew), t← tnew 12: end while 13: return an approximate solution of the original linear program according to Ye et al. (1994) . 14: end procedure
Algorithm 2 Sketching-based central path step
1: procedure StochasticStep(mp, x, s, δµ, b, ) 2: w ← x
s , ṽ ← mp.Update(w) . Projection maintenance
3: x← x √
ṽ w
, s← s √
w ṽ
. It guarantees that x s = ṽ and xs = xs
4: repeat 5: px, ps ← mp.Query( 1√
XS δµ) . Projection maintenance
6: δ̃s ← S√ XS ps . According to (4) 7: δ̃x ← X√ XS px . According to (4) 8: until ‖s−1δ̃s‖∞ ≤ 1100 logn and ‖x−1δ̃x‖∞ ≤ 1100 logn 9: return (x+ δ̃x, s+ δ̃s)

heading: 2.3 Coordinate-wise Embedding
text: To speed up the classical central path method, we introduce the coordinate-wise embedding (CE) as follows:
Definition 2.1 ((α, β, δ)-coordinate wise embedding (CE)). Given parameters α, β ∈ R and γ ∈ (0, 1), we say a randomized matrix R ∈ Rbsketch×n with distribution Π satisfies (α, β, δ)-coordinate-wise embedding property if for any fixed vector g, h ∈ Rn, we have
1. E R∼Π
[g>R>Rh] = g>h,
2. E R∼Π [(g>R>Rh)2] ≤ (g>h)2 + α bsketch ‖g‖22‖h‖22,
3. Pr R∼Π
[ |g>R>Rh− g>h| ≥ β√
bsketch ‖g‖2‖h‖2
] ≤ δ.
We remark that the (α, β, δ)-coordinate wise embedding we proposed here is different from the conventional Johnson-Lindenstrauss Lemma Johnson & Lindenstrauss (1984) or subspace embedding Sarlós (2006) in classical literature.
The coordinate-wise embedding we proposed in Definition 2.1 only works for a fixed vector pair g, h ∈ Rn. While for the Johnson-Lindenstrauss embedding stated below: Definition 2.2 (Johnson-Lindenstrauss embedding (JL) Johnson & Lindenstrauss (1984)). Given 0 < < 1, a finite point set X in Rn with |X| = m, we say a randomized matrix R ∈ Rb×n satisfies Johnson-Lindenstrauss property if (1− ) · ‖g‖22 ≤ ‖Rg‖22 ≤ (1 + ) · ‖g‖22 for all g ∈ X.
The result of JL embedding works for a set of points in Rn. However, subspace embedding holds for all the vectors from the subspace.
Definition 2.3 (Subspace embedding (SE) Sarlós (2006)). Given 0 < < 1, a matrix A ∈ Rn×d, we say a randomized matrix R ∈ Rb×n satisfies (1± ) `2-subspace embedding for the column space of A if ‖RAx‖22 = (1± )‖Ax‖22, for all x ∈ Rd.
The subspace embedding property works for all vectors from the subspace Rd.
Several well-known sketching matrices To further concretize our sketching approach, we discuss the following commonly used sketching matricesand their corresponding properties when acting as coordinate-wise embedding and solving LP.
Random Gaussian matrix All entries are sampled from N (0, 1/bsketch) independently. SRHT matrix Lu et al. (2013) Let R = √ n/bsketchSHD, where S ∈ Rbsketch×n is a
random matrix whose rows are bsketch uniform samples (without replacement) from the standard basis of Rn, H ∈ Rn×n is a normalized Walsh-Hadamard matrix, and D ∈ Rn×n is a diagonal matrix whose diagonal elements are i.i.d. Rademacher random variables3.
AMS sketch matrix Alon et al. (1999) Let Ri,j = hi(j), where h1, h2, · · · , hbsketch are bsketch random hash functions picking from a random hash family H = {h : [n]→ {− 1√
bsketch ,+ 1√ bsketch }}.
Count-sketch matrix Charikar et al. (2002) Let Rh(i),i = σ(i) for all i ∈ [n] and other entries to zero, where h : [n] → [bsketch] and σ : [n] → {−1,+1} are random hash functions.
Sparse embedding matrix Nelson & Nguyên (2013) Let R(j−1)bsketch/s+h(i,j),i = σ(i, j)/ √ s for all (i, j) ∈ [n]× [s] and all other entries to zero, where h : [n]× [s]→ [bsketch/s] and σ : [n]× [s]→ {−1, 1} are random hash functions. Uniform sampling matrix Let R = √ n/bsketchSD, where S ∈ Rbsketch×n is a random
matrix whose rows are bsketch uniform samples (without replacement) from the standard basis of Rn, and D ∈ Rn×n is a diagonal matrix whose diagonal elements are i.i.d. Rademacher random variables.
Considering an oblivious regime, where the size of sketching bsketch is fixed, we have
Lemma 2.4 (Oblivious coordinate-wise embedding properties). For above defined sketching matrices, they are of (α, β, δ)-coordinate wise embedding as following:
Remark 2.5. The approach in Cohen et al. (2019b) behaves similarly as applying uniform sampling matrix in our sketching, which doesn’t work in an oblivious setting. Therefore, Cohen et al. (2019b) needs to modify the sketching size in each iteration. In general, to apply the sketching in an oblivious way, we observe that the sketching matrix should be relatively dense to better concentrate around its expectation, so that we can control the extra perturbation introduced by random sketching in solving linear programming problems.

heading: 2.4 Speeding up central path method through OCE
text: To speed up the classical central path method, we randomize the calculation of Eq. (3) by
δ̃x = X√ XS (I − P )R>R 1√ XS δµ and δ̃s = S√ XS PR>R 1√ XS δµ, (4)
3In this case, we require logn to be an integer.
where the random sketching matrix R ∈ Rbsketch×n satisfies the (α, β, δ)-coordinate wise embedding property with α = O(1), β = O( √ bsketch) and any failure probability δ ∈ (0, 1).
The coordinate-wise embedding properties 2.1 ensures the randomized Eq. (4) are well concentrated around original Eq. (3), which implies the new randomized path µ̃, will still be near the aiming path t during the algorithm updates. Therefore, given the same decreasing rate of aiming path t as before, we are able to prove µ̃ ≈0.1 t throughout the iterations. As they converge to zero, we are still able to obtain an optimal solution in O∗( √ n) iterations.
In terms of running time, note Eq. (4) actually reduces the dimension of previous matrixvector multiplication from n to bsketch. Assume we can maintain the sketched projection matrix PR> in an efficient manner, the calculation in Eq. (4) reduces to (PR>) · u for some vector u ∈ Rbsketch , which is a multiplication between a matrix of size n× bsketch and a vector of size bsketch and costs O(nbsketch) running time. Choosing bsketch to be O ∗( √ n), we speed up the updates. We summarize our approach in Algorithm 1, 2. We discuss how to maintain the projection in Section 2.6.

heading: 2.5 Feasible central path equation via sketching
text: To explain the strength of our approach, we discuss the feasible and oblivious advantages of our method over past state-of-art results.
The new update Eq. (4) can be viewed as an exact solution of the following linear system:
Xδ̃s + Sδ̃x = δ̃µ,
Aδ̃x = 0, (5)
A>δ̃y + δ̃s = 0,
where
δ̃µ = √ XSR>R
1√ XS δµ. (6)
Therefore, our approach can also be viewed as an update of a subspace of the complementarity gaps in each iteration, instead of decreasing the complementarity gaps uniformly.
Note in each iteration, our update solves the new linear system (5) exactly. Compared to the state-of-art approach Lee et al. (2019) which constructs a solution that solves the linear system inexactly, the feasibility of our approach prevents us from the complicated analysis. Our approach is also able to use sparse embedding matrix to prevent ruining the potential sparsity structure of the original linear programs, compared to the usage of dense sketching matrices in the work Lee et al. (2019).
On the other hand, our method is oblivious since the choice of sketching matrix R ∈ Rbsketch×n does not depend on the algorithm updates, which implies we can pick the sketching matrices at the preprocessing stage. While for the state-of-art approach Cohen et al. (2019b), its sampling probability depends on the algorithm updates and needs to be calculated on-the-fly.

heading: 2.6 Projection maintenance
text: In this section, we discuss our approach to deal with the second computational bottleneck, i.e., how to maintain the projection after sketching PR> ∈ Rn×bsketch in an efficient way, where P ∈ Rn×n is the orthogonal projection matrix defined in Eq. (3) and R ∈ Rbsketch×n is a random sketching matrix with appropriate (α, β, δ)-coordinate-wise embedding property.
Let W := diag(w) ∈ Rn denotes the diagonal matrix with wi = xi/si. Then we have P := √ WA>(AWA>)−1A √ W ∈ Rn×n. Therefore, our final goal of implementing of Eq. (4) reduces back to the task of maintaining the query structure which outputs:
PR>Rh = (PR>) · (R · h) = (PR>) · u (7) where u ∈ Rbsketch .
To achieve this, we have the similar observation as in Cohen et al. (2019b): W doesn’t vary much between two iterations under the sketching approach, which is shown in the following lemma: Lemma 2.6 (Change of W ). Let 0 < < 1/(40000 log n). Let wi and w new i denote the value xi/si in two consecutive iterations, then we have n∑
i=1
(E[lnwnewi ]− lnwi)2 ≤ 64 2, n∑
i=1
(Var[lnwnewi ]) 2 ≤ 1000 2.
Above observation motivates us to take the benefit of lazy update if wi only has little changes since we only need to maintain the projection approximately. We discuss two extreme scenarios to illustrate the core ideas: 1) w changes uniformly across all coordinates and 2) w only changes in few coordinates.
In the first case, we use the idea of lazy update. Lemma 2.6 implies the changes of w between two iterations are roughly wnewi ≈ (1± 1√n )wi. Therefore, wi’s will only vary by more than a constant and possibly ruin our previous `∞ closeness after O∗( √ n) number of iterations.
In this case, we only need to update the matrix PR> once every O∗( √ n) iterations, while being ”lazy” in any other time. Since the algorithm finishes in O∗( √ n) iterations, it means we only need to update matrix PR> O∗(1) many times, whose total running time is O∗(nω).
In the second case, we use the idea of low-rank update. Instead of updating PR> in each iteration, we directly compute PR>u using the Woodbury matrix identity. Since w only changes in few coordinates, we only need to focus on computing the inverse of small matrix instead of the original n × n matrix. And computing PR>u instead of PR> fastens the computation because we only need to do matrix-vector multiplication. As a result, we can output PR>u in O∗(nbsketch) time. Recall we choose bsketch = O∗(n1/2). Therefore, the running time for this case is O∗(n2), which is also within our budget.
For general cases, we combine above techniques together and have the following theorem: Theorem 2.7 (Projection maintenance). Given a number a ∈ (0, α)4 and sketching matrices R ∈ Rnb×n with b ∈ [0, 1]. We can approximately maintain the projection by
1. Update(w): Output a vector ṽ such that for all i,
(1− mp)ṽi ≤ wi ≤ (1 + mp)ṽi.
2. Query(h): Output √ Ṽ A>(AṼ A>)−1A √ Ṽ (R>)∗,lRl,∗h for the ṽ outputted by the
last call to Update.
The data structure takes n2dω−2 time to initialize, each call of Query(h) takes time O∗(n1+b+ n1+a), and the amortized expected time per call of Update(w) is O∗(nω−1/2 + n2−a/2).
Note our approach maintains the projection at point Ṽ = X/S instead of W = X/S, where xi = xi √ ṽi/wi ≈0.1 xi and si = si √ wi/ṽi ≈0.1 si. Equivalently speaking, instead of solving Eq. (5), we are solving
Xδs + Sδ̃x = δ̃µ,
Aδ̃x = 0, (8)
A>δ̃y + δ̃s = 0,
where δ̃µ = √ XSR>R 1√
XS δµ as shown in Algorithm 2. And the final running time of our
algorithm can be bounded bt O∗(nω). Corollary 2.8 (Extension to ERM). Our approach for solving LP naturally generalizes to other convex optimization problems of the following form Lee et al. (2019), including empirical risk minimization: minx ∑ i fi(Aix+ bi), where fi is convex function on Rni with
n = ∑ i ni. Our algorithm output the solution in time O
∗(n2.373 log(n/δ)), where δ is the precision parameter.
4α is the dual exponent of matrix multiplication, whose current value is roughly 0.31 Le Gall & Urrutia (2018).

Review summaries:
The paper studies the problem of solving LP and more generally convex programming via sketching based approaches. In particular, the running time of proposed algorithm in this paper matches the running time of the best known algorithms [Cohen et al(19b) and Lee et al(19)]. However, this paper provides some further useful properties: 1) oblivious sketching, 2) sparse sketching which can be of interest in many applications. The paper has provided theoretical guarantees of their proposed algorithm. The problem that is studied in this paper is very important and the sketching based approach is also very practical. The paper would benefit from an empirical comparison of the proposed algorithm with the existing methods for solving LPs.  

The paper is based on the works of Lee et al and Cohen et al. Building upon these works, the paper comes up with an interior point method that matches the state-of-the-art in LPs. The paper's contribution is in a new type of sketching used inside the interior point method, that demonstrates some advantages over those of Lee et al and Cohen et al. Notable among these advantages are (1) the ability to preserve sparsity of an LP, and (2) exact solutions to the system of linear equations obtained from optimality conditions.