Oblivious Sketching-based Central Path Method for Solving Linear Programming Problems
Authors: Zhao Song
Zheng Yu
Venue:  (2021)
Keywords: optimization
sketching
linear programming
central path method
running time complexity

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, Lee, Song STOC 19; Lee, Song, Zhang COLT 19]. 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, Lee, Song STOC 19] enjoys feasibility while being non-oblivious, and [Lee, Song, Zhang COLT 19] is oblivious but infeasible, and relies on $\mathit{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 $\mathit{sparse}$ sketching matrix [Nelson, Nguyen FOCS 13] 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.

Under review as a conference paper at ICLR 2021
OBLIVIOUS SKETCHING-BASED CENTRAL PATH METHOD FOR SOLVING LINEAR PROGRAMMING PROBLEMS
Anonymous authors Paper under double-blind review
ABSTRACT
In this work, we propose a skotching-based central path method for solving linear programmings, whose running time matches the state of art results Cohen el 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-wist tiis embedding technique, which may be of independent interest. Compare to previous methods, the work Cohen et al. (2019b) enjoys feasibility while being non- oblivious, and Lee et al. (2019) is oblivious but infcasible, and relies on dense sketching matrices such as subsamplod randomized Hadamard/ Aataamard/Fourier /Fourier transform matrices. Our method enjoys the benefits of being both oblivious and feasible, and can use sparse sketching matrix Nelson & Nguyên (2013) 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.
INTRODUCTION
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 cconomics Tintner (1955); Dorfman et al. (1987), operations research Delson & Shahidehpour (1992), compressed sensing Donoho (2006); Candes 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 general linear program in standard form min cT x of size A E Rd without redundant constraints. For the generic case d = M(n) we considered in this paper, the state of art results take a total rumning time of O" + 2.5-a/2 + 2+16/ to obtain a solution of accuracy current matrix multiplication time Cohen et al. (2019b); Loe et al. (2019), where w is the exponent of matrix multiplication whose current value is roughly 2.373 Williams (2012); Le Gall (2014), and a 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 a, Cohen et al. (2019b) algorithm takes O 2.333) time.
For the current state-of-art results, the work Cohen et al. (2019b) involves non-oblivious sampling technique, whose sampling set and size changes along the itcrations. It avoids the possibilitics 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:
We use O" hides (1))) and (1)((8))))) factors.

---

Under review as a conference paper at ICLR 2021
Is there an oblivious and feasible algoritho for solving linear programmiing programs in fast running time (i.e. current matriz multiplication time) ?
In this work, propose both oblivious and feasible (per iteration)? method that solves linear programs in the same running time as the state of art.
The algorithm we propose is aketching-basee 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 1 1/v2n factor in each iteration and takes O" (VVn) iterations to converge. This results in O (v(vn) x n = O (nt-.9) 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 different approach. We only updating a O* "(Va))dimension
subspace in each iteration while keeping the same number of iterations vn through an Oblivious Goordinate-wist Embedding (OCE) technique. Thus, our method updates (*(n) dimensions in total, which is nearly optimal.
The coordinate-wise embedding we introduce in this work is a distribution of matrices R E Rhiteee Xn with baketch < such that, for any inner product h h between two n- dimensional vector g, h E IR", with "high" probability g RD Rh approximates g h well. In the case of solving linear programmings, multiplication Ph in each iteration by PR Rh through OCE, such that the resulting random vector is close to previous Combining with lazy update and low-rank update techniques to maintain the query structure PR Rh for any input vector h E IR", 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 fcasible, compared to other state of art results Cohen et al. (2019b); Lee et al. (2019).
approximate the calculation of matrix-vent vector
in each coordinate, i.c., (PR' Rh); (Ph); for all [n].
We state our main result as follows:
Theorem 1.1 (Main result, informal). Given a linear program An=b, eTa with no redundant construints. Let dip denotes precision. Our algorithm takes 2 log(n/ò;p)) time to solve this L.P.
1.1 RELATED WORKS
Linear programming. Linear programmings have been studied for nearly 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 algorithum 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 = Q(() considered in this work, Karmarkar's algorithm Karmarkar (1984) takes O* (n.66.) running time. Then it was improved to O" (n²3) in the work Renegar (1988); Vaidya (1987). In 1989, Vaidya further proposed an algorithm that takes running of O (122.5) This result hasn't '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
"In 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 non-oblivious one, and Lee et al. (2019) doesn't 't solve the system exactly.
2

---

Under review as a conference paper at ICLR 2021
linear regression Clarkson & Woodruff (2013); Nelson & Nguyên (2013); Andoni et al. (2018); Clarkson et al. (2019); Song et al. (2019a) and low-rank approximation Clarkson & Woodruff (2013); Nelson & Nguyen (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-defiitte matrices Clarkson & Woodruff (2017), total least regression Diao et al. (2019), quantile regression Li 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 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 funda- mental 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 mmooothess/stroon convexity of the objective in order to achieve log(1/E) dependence
the error parameter
Notations For positive integer n, we use [n|] to denote set 21, ,n]. For vectors 2 E IR" and parameter e E (0, 1), we use x Re 2 to denote (1 (1-e)z S x, < (1+e)z vi E [m]. For any scalar we use a =, t to denote (1 (1-e)t e)t S a, S (1 + e)t, Vi [n]. Given diagonal matrices X diag(x) gaxx
diag(s) _axx we use X to denote the diagonal matrix
with ) = 83 Vi E [n]]
TECHNIQUE OVERVIEW
In this section, we discuss the key ideas of our approach based on the central path method.
2.1 SHORT STEP CENTRAL PATH METHOD
Consider the following standard primal and dual problems of lincar programmings:
min cTx (primal) and A ATy-s=e, 2.820
bTy (dual)
max
Ax=b,220
where A E Rdxn is full rank with d= O(n). Then (a, y) an optimal solution if and only if it satisfies the following optimality conditions Vanderbei et al. (2015):
Ar h x x20
(primal feasibility)
A + = c, 820
(dual feasibility)
5:8; for all
(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 the tuple (I, s,, that satisfies:
Ar = b. x x>0
A 4 r;8; = for all
(1)
where t > 0 is called the complementarity gap. It has been shown obtain initialization point on the central path with t= according to Ye et. al. (1994). Then in each iteration, the classical algorithm deceases the complementarity gap uniformly from / to
3

---

Under review as a conference paper at ICLR 2021
me with 7/ < 1, and solves Eq. (1). As t approaches 0, the central path will converge to optimal solution. The short step central path method approximately solves Eq. (1) by the following linear system:
X6 St, = 8pr
Ad₂ O,
(2)
A by + 8 O,
where diag(r), S = diag(s) and we update the solution by x= x 5g, == + 8, and y y by. Denote the actual complementarity gap j R" defined under Eq. (2) as [4i T;8; for E [n]. Then Eq. (2) maintains the feasibility conditions while approximately moving the gap from le to μ 4 5p- 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 & goes to 0, which leads us to an optimal solution.
To solve the linear system (2), note when is full-rank, it has an unique solution explicitly given by:
X
1 and 6, VXS
S
8
(I - P)
6p.
(3)
VXS
VXS
VXS
where P V A AT) Av X /S is an orthogonal projection matrix.
choose 7 to be roughly 1 - v and the algorithm converges in O² (vn) iterations. Therefore, the total running time needed of solving LP by explicit solution Eq. (3) is O" (n)*t1/2).
Literature Vaidya (1989) shows
2.2 SKETCHING-BASER CENTRAL PATH METHOD
In the following subsections, we discuss approach of sketching-based central path met hod. In Subsection 2.3, we introduce the coordinate-wise embedding (CE) technique. We discuss the difference between CE and classical sketching techniques, such Johnson-Lindeesttan (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-basee based contral path method can speed up the computation. In Subsection 2.5, we explain the reason why our sxetch-based central path method is feasible and oblivious. In Subsection 2.6, we discuss the projection maintenance needed for the algorithm updates.
A Algorithm 1 Main algorithm (simplified)
1: procedure MAIN(A, b, c, 6p)
Theorem D.1 Modify the linear program and obtain an initial and s according to Ye et al. (1994) Ensure the initial complementarity gap start with O* (v/); parameters = (1), projection maintenance
2:
3:
4: Initialize: sketching size baketch
datastructure mp
5:
b Initialize the aiming gap f & Stop once the precision is good b Decrease the aiming gap by 1/vV in each iteration Actual gap Here @x(F) = Σ cosh(Ar;) is the potential function characterize the Eno closeness between actual path ğ and actual pathi T.
161
1
6: while t (32n") do
7:
new + (1 sin )
8:
11
9:
6p + mmw 1)ms know
(4x(u/t-1)
have d' in the update to help ensure ū Rio.1 L. now geww) +- STOCHASTICSIER (2 () + hew guew), ), + fuew end while
10:
8 bakesch,
b Algorithm 2
11:
12:
13: return an approximate solution of the original linear program according to Ye et al. (1994).
14:
end procedure
4

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Skotching- based central path step
1: procedure STOCHASTICSTEP((pp. 8, c)
2:
+ (mp.UPDAT((w))
Projection maintenance
3:
T
2V
/
It guarantees that _ ē and rs as
4: repeat
5:
Pa. ps
up. mpp QUERY(
Projection maintenance
6:
8. +
vx8 p
According to (4)
7:
0z 6- Pr
b. According to (4)
X
8:
until ||s 10 S 100log
and || 12 S log
9: return (Ir + 82, 6.)
10: end procedure
Statement
Reference
Emb.
Lz guarantee
Unb.
Var.
Definition 2.1
This paper
CE
for fixed one
Yes
Yes
Definition 2.2
Johnson & Lindenstrauss (1984)
JT.
for a. fixed set
No
No
Definition 2.3
Sarlós (2006)
SE
for subspace
No
No
Table 1: Summary of the guarantees of different embeddings. The three embeddings give the é--norm guarantce for different number of vectors. Coordinato-wise embedding also guarantoes the embodding is unbiasod, and the variance is bounded. Soe Scction G for more details. "Emb." denotes Embedding. "Unb." denotes Unbiased. "Var." denotes Variance.
2.3 COORDINATE-WISR. EMBEDDING
To speed up the classical central path method, introduce the coordinate-vic wise embedding (CE) as follows:
Definition 2.1 ((a,3,8) c.oordccoe wise embedding (CE)). Given parameters a, B R
and 7 E (0,1), 1), we say rundomized matria R E Rhscoto xn with distribution II satisfies (o,, c000di)-onnnn embedding property if for any fixed vector g, h E TR" we have
E R
1
R Rh) = Th.
[g] R Rh)) S h)2 +
11912111122
R
bakeich
3
Pr H-ll
T Rh T R TR Ig
1 12122100
[/1l
S 6.
Vakeetc
We remark that the (a, 3, (,, -coordiaae wise embedding proposed here is different from the conventional Joinson-Lindeestraauss Lemma Johnson & Lindenstrauss (1984) or subspace embedding Sarlós (2006) in classical literature.
The coordinate-wise embedding we proposed in Definition 2.1 only works for a fixed vector pair g, E R.. While for the Johnson-Lindenstrauu embedding stated below:
embedding (JL) Johnson & Lindenstrauss (1984)). Given < e < 1, finite point set X R" with [X| = m, we say randomized matria
Definition 2.2 (Johnson-Lindenstrren
R E Roxn salisfies Jolnson-LLndensinee properly if (1 -e) || < ||oll < (11+ e) ||
for all g E X.
The result of JL embedding works for set of points in R". However, subspace embedding holds for all the vectors from the subspace.
Definition 2.3 (Subspace embedding (SE) Sarlós (2006)). Given 0 < < 1, a malria A nxd say randomized matriz R E pbxn satisfies (1 = ly-subspace embedding for the column space of A if |Ax]| = (1 (1 c) | for all x E Rdd.
The subspace embedding property works for all vectors from the subspace Rdd
5

---

Under review as a conference paper at ICLR 2021
Several well-known sketching matrices To further concretize our sketching approach, we discuss the following commonly used sketching matricesand their corresponding properties when acting coordinate-wir embedding and solving LP.
Random Gaussian matrix All entries are sampled from N 1 /bsketch)) independently.
SRHT matrix Lu et al. (2013) Let R Vn/baaethh where S Ruseeeon X is random matrix whose rows are Dsketch uniform samples (without replacement) from the standard basis of R,, H R"*R is a normalized Walsh-Hadamar matrix, and D E R is a diagonal matrix whose diagonal elements are ii.d. Rademacher random variables
AMS sketch matrix Alon et al. (1999) Let Raj h₂()), where hi, Maaaa are Daketch random hash functions picking from a random hash family H { [m]
Valeetch
Vbakatch
Count-sketch matrix Charikar et al. (2002) Let Ba(0. = =iii for all i E [n|] and other entries to zero, where h: [n] + [baketch] and a [m]] + 1-1, are random hash
functions.
Sparse embedding matrix Nelson & Nguyên (2013) Let R1j-1)banaah ((.j))
di, for all (i, E [n] [s] and all other entries to zero, where h [n] x [bahttch/s] and a: [m] x [s] + {-1,1} are random hash functions.
Uniform sampling matrix Let R / SStebas where S Re is random matrix whose rows are baketch uniform samples (without replaceeen)) from the standard basis of IR", and D E [_= is diagonal matrix whose diagonal elements are i..dd Rademacher random variables.
Considering an oblivious regime, where the size of sketching batetch is fixed, we have Lemma 2.4 (Oblivious coordinato-wise embedding properties). For above defined sketching matrices, they are of (a, (,,5) cocordinntt wise embedding as following:
Sketching matrix
5
LP? (Left)
LP? (Right)
Random Gaussian
((1)
Olog 1-5 (n/o))
Yes
Yes
SRHT
0(1)
Ollog ((n/o))
Yes
Yes
AMS
0(1)
Ollo 1.3 (n/o))
Yes
Yes
Count-sketch
O(1)
Ol Oabatttc (18(1/8) or O(I/Vo)
No
No
Sparse embedddng
0(1)
Oly Bateeeh s log' (m//8))
No!
Yes"
Uniform sampling
((n)
O(n/ Lin/bban (bskocc))
No
No
Summary for different sketching matrices. * A sparse embedding sketching matrix be used in LP algorithm when it is added the right and = O(log (n/8)). ((())"(n/))). However when sketching on the left (in Lee et al. (2019)), additional algorithmic designs are needed to make the algorithm feasible (see Section F.1 for more discussion), and the error of the feasibility part cannot be bounded unless = M(bakotch).
Table 2:
Remark 2.5. The approach Cohen al. (2019b) behaves similarly as applying uniform sampling matria in our sketching, which doesn't work in an oblivious setting. Therefore, Cohen el al. (2019b) needs to modify the sketching size in each ileration. general, to apply the sketching in oblivious way, observe that the sketching matric 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 progremming problems.
2.4 SPEEDING UP CENTRAL PATH METHOD THROUGH OCE
To speed up the classical central path method, we randomize the calculation of Eq. (3) by
8_ X (1- ( (1-PRR R VXS
1 on and J, S. -PRR R
1
8
(4)
VXS
Vxs VXS
3In this case, we require logn n be integer.

---

Under review as a conference paper at ICLR 2021
where the random sketching matrix R Rhotatc satisfies the (a, cooordiitt wise embedding property with = 0(1) 3 O Dskatch)) and any failure probability 8 E (0,
The coordinate-wise embedding properties 2.1 ensures the randomized Eq. (4) are well concentrated around original Eq. (3), which implics the new randomized path will still be near the aiming path during the algorithm updates. Therefore, given the same decreasing rate of aiming path as before, are able to prove ÿ R & throughout the iterations. As they converge to zero, we are still able to obtain an optimal solution in (*(vi) ilerations.
In terms of rumning time, note Eq. (4) actually reduces the dimension of previous matrix- vector multiplication from n to bsketch- Assume we can maintain the sketched projection matrix PR in efficient manner, the calculation in Eq. (4) reduces to (PR") for some vector u E Rateshhh which is a multiplication between a matrix of size n x baketch and a vector of size baketch and costs (nbaketch)) rumning time. Choosing Skkttc to be O"(yn) we speed up the updates. We summarize our approach in Algorithm 1, 2. We discuss how to maintain the projection in Section 2.6.
2.5 FEASIBLE CENTRAL PATH EQUATION SKETCHING
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:
No. S5_ = 5
Ad = 0,
(5)
A T by + 8, = O,
where
8, VSSR R
VXS 6,-
(6)
Therefore, our approach can also be viewed an update of subspace of the complementarity gaps in each iteration, instead of decreasing the complementarity gaps uniformly.
Note in each iteration, our update solves the 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 lincar programs, compared the usage of dense skotching matrices in the work Lee et al. (2019).
the other hand, our method is oblivious since the choice of sketching matrix R E IR deinech x does not depend on the algorithm updates, which implies can pick the sketching matrices at the preprocessing stage. While for the state-of-art approach Cohen et al. (2019b), its sampling probability depends the algorithm updates and needs to be calculated on-the-fly.
2.6 PROJECTION MAINTENANCE
In this section, discuss approach to deal with the second computational bottleneck, ie., how to maintain the projection after sketching PR g R in an efficient way, where P E Rux is the orthogonal projection matrix defined in Eq. (3) and R E Rhantc is a random sketching matrix with appropriate (a, -ooordinte wise embedding property.
Let W diag(w) E I" denotes the diagonal matrix with w; 24/st. Then we have P:= AA)
pa Therefore, our final goal of implementing of Eq. (4) reduces back to the task of maintaining the query structure which outputs:
PR. Rh (PRT)- (R h) = (PRT)..
(7)
where B.baotchh

---

Under review as a conference paper at ICLR 2021
To achieve this, we have the similar observation 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 < logo000logg) Let wa and wiew denote the value 0:/s; in two consecutive iterations, then we have
E In (Elu " - ln; 64c²,
Σ (Var [ar w) 1000c
Above observation motivates us to take the benefit of lazy update if w; 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 we between two iterations are roughly wite x (1 ) Therefore, wy 'ss will only vary by more than a constant and possibly ruin our previous fx closeness after (v(a)) number of iterations. In this case, only need to update the matrix PR once every O (*(yn) iterations, while being "lazy" in any other time. Since the algorithm finishes in O" ('(nn) iterations, it means we only need update matrix PR (1) many times, whose total running time is O*("").
In the second case, we use the idea of low-rank update. Instead of updating PR in each iteration, we directly compute PRTu _ using the Woodbury matrix identily. Since w only changes in few coordinates, we only need to focus on computing the inverse of small matrix instead of the original computation because we only need to do matrix-vector multiplication. As a result, we can output PRTM in O" ("(naatecc)) time. Recall we choose hatetch = Or (n1/2). Therefore, the rumning time for this case is (n²),, which is also within our budget.
matrix. And computing PR u instead of PR fastens the
For general cases, we combine above techniques together and have the following theorem: Theorem 2.7 (Projection maintenance). Given a number E a0) and sketching matrices R R xm with b E [0, 1]. We approzimately maintain the projection by
1. UPDATE(w): Output a vector e such that for all i,
(1 (1- S w, S (1 E.
2. QUERY(h): Output (AATAAA") last call to UPDATE.
Bi, for the d outputted by the
The data structure takes n time to initialize, each call of QUERY(K) takes time On +b n (t), and the amortized expected time per call of UPDATE(W) is O" (n- 1/2 + n 2-a a/2).
Note our approach maintains the projection at point V = =X/3 instead of W = X/S, where C4 34 03/ fa/w: 0o.1 34 and 8; = 8; / w N0.1 8;- Equivalently speaking, instead of solving
Eq. (5), we solving
X5, 55, 8pp
Aδ_ O,
A T + 8, = O,
where 52 = VXSRR R. 15, as shown in Algorithm 2. And the final running time of our VXS
algorithm can be bounded bt O" (n").
Corollary 2.8 (Extension to FRM)). Our approach for solving LP naturally generalizes to other conver optimization problems of the following form Lee et al. (2019), including empirical risk minimization: min, L(Ar + by), where fa is connex function on R with
= E,n, ni. Our algorithm output the solution in time O (n2.377 log(n/5)), where is the precision parameler.
aa is the dual exponent of matrix multiplication, whose current value is roughly 0.31 Le Gall & Urrutia (2018).
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Dimitris Achlioptas. Satabase-friendly random projections: binary coins. Journal of computer and System Sciences, 66(4):671 687, 2003.
with Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast johnson- lindenstrauss transform. In Proceedings of the thirty-eightll anmual ACM symposium on Theory of computing (STOC), pp. 557-563. ACM, 2006.
Zeyuan Allen-Zhun Natasha 2: Faster non-convex optimization than sgd. In Advances in neural information processing systems, pp. 2675 2686, 2018.
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and system sciences, 58(1):137-147, 1999.
Alexandr Andoni, Chengyu Lin, Ying Sheng, Peilin Zhong, and Ruiqi Zhong. Subspace embedding and linear regression with orlicz norm. In ICML. https://arXiv. htt////iiv..oo//.... 1806. 06630, 2018.
Sergei Bernstein. On modification of chebyshev's incquality and of the error formula of laplace. Ann. Sci. Inst. Sav. Ukraine, Sect. Math, 1(4):38-49, 1924.
Christos Boutsidis and David P Woodruff. Optimal cur matrix dccompositions. In Proceedings of the 46th Annual ACM Symposium Theory of Compuling (STOC), pp. 353 362. ACM, https:/ /ttpps//arxiv... orgooog//.oo /ptf//f////// 1405. 7910, 2014.
Christos Boutsidis, David P Woodruff, and Peilin Zhong. Optimal principal component analysis in distributed and streaming models. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Compuling (STOC), pp. 236 249. ACM, https:// arxiv. /tciv..rrg//f//// 1504.06729, 2016.
Jan den Brand, Binghui Peng, Zhao Song, and Omri Weinstein. Training (over- parametrized) neural networks in near-linear time. In Manuscript, 2020.
Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recovery from incom- plete and inaccurate measurements. Communications on pure and opplied mathematics, 50(8):1207-122) 2006.
Moses Charikar, Kevin Chen, and Martín Farach-Colton. Finding frequent items in data streams. In Automata, Languages and Programmingg pp. 693 703. Springer, 2002.
Herman Chernoff. A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations. The Annols of Mathematical Statistics, pp. 193-507, 1952.
Kenneth L. Clarkson and David P. Woodruff. Low rank approximation and regression in input sparsity time. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pp. 81 90. https: //axiv..///iv.// org/ /dff/df//// hpdff//20/ /wwff//20....0 6365, 2013.
Kenneth L Clarkson and David P Woodruff. Input sparsity and hardness for robust subspace approximation. In IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 310-329. https: / arxiv. org/ org/pdf// 215./.10000.. 2015a.
Kenneth L Clarkson and David P Woodruff. Sketching for m-cstimators: unified approach lo robust regression. In Proceedings of the T Twerly-Sizth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 921 939. SIAM, 2015b.
Kenneth L Clarkson and David P Woodruff. Low-rank psd approximation in input-sparsity time. In Proceedings of the Twenty- Eighth Annual ACM-SIAM Symposium on Discrete STAM, 2017.
Algorithms (SODA), pp.
Kenneth L Clarkson, Ruosong Wang, and David P Woodruff. Dimensionality reduction for //ariiv.///....a/ http//awxxv...../dd..aa/ orgg/dff/900f 05376. pdf, 2019.
tukey regression. In ICML. https:

---

Under review as a conference paper at ICLR 2021
Michael B Cohen, Ben Cousins, Yin Tat Lee, and Xin Yang. A near-optimal algorithm for approximating the john ellipsoid. In COLT. attps://arae /ttp///axxvvvvv/ wttpa//.rrgppp///////e/ 11580, 2019a.
Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. In Proceedings of the 51sl Annual ACM Symposium on Theory of Computing (STOC). https:/ haaps:///rxxvv otreiiioog///ooo wttgp///g//////// 07896. pdf, 2019b.
George B Dantzig. Maximization of a linear function of variables subject to linear inequalities. Activity analysis of production and allocation, 13:339-33 -477 1947.
Jerome K Delson and SM Shahidehpour. Linear programming applications to power system economics, planning and operations. IEEE Transaclions on Power Systems, 7(3):1155 1163, 1992.
Huaian Diao, Zhao Song, Wen Sun, and David P Woodruff. Sketching for kronecker product wwtpp///gppp....///////////// 111.//119.9977 2018.
regression and p-splines. In AISTATS.
Huaian Diao, Zhao Song, David Woodruff, and Xin Yang. Total least squares regression in input sparsity time. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2478 2489, https://arrs org/pdf /ddf/199... 12441. .dff, 2019.
David L. Donoho. Compressed sensing. IEEE Trans. Information Theory, 52(4):1289 1306, 2006.
Robert Dorfman, Paul Anthony Samuclson, and Robert M Solow. Lineor programming and economic analysis. Courier Corporation, 1987.
Sergey Foss, Dmitry Korshunov, and Stan Zachary. An introduction to heavy-tailed and subeaponential distributions, volume 6. Springer, 2011.
Uffe Haagerup. The best constants in the khintchine incquality. Studia Mathematica, 70(3): 231-283, 1981. URL http:///dmmm...doo///oo//
David Lee Hanson and Farroll Tim Wright. A bound on tail probabilities for quadratic forms in independent random variables. The Annals of Mathematical Statistics, 42(3):1079 1083, 1971.
Wassily Hoeffding. Probability incqualitics for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13 30, 1963.
Piotr Indyk, Ali Vakilian, Tal Wagner, and David Woodruff. Sample-optimal low-rank approximation of distance matricos. In COLT, 2019.
Chi Jin, Lydia T Lin, Rong Ge, and Michael T Jordan. On the local minima of the empirical risk. In Advances in neural information processing systems, pp. 4896 4905, 2018.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pp- 315-323, 2013.
William Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into hilbert space. Contemporary mathematics, 26(189-206) 1984.
Daniel M. Kane and Jelani Nelson. Sparser johnson lindenstrauss transforms. In SODA, pp. 1195-1206, 2012.
Narendra Karmarkar. A new polynomial-time algorithm for linear programming. In Pro- ceedings of the sizteenth annual ACM symposium on Theory of computing(STOC), pp. 302 311. ACM, 1984.
Leonid G Khachiyan. Polynomial algorithms in linear programming. USSR Compulational Mathematics and Mathematical Physics, 20(1):53-72 72, 1980.
10

---

Under review as a conference paper at ICLR 2021
Aleksandr Khintchine. Über dyadische brüche. Mathematische Zeilschrift, 18(1):109 116, 1923.
Victor Klee and George J Minty. How good is the simplex algorithm. Inequalities, 3(3): 159-175, 1972.
Beatrice Laurent and Pascal Massart. Adaptive cstimation of a quadratic functional by model selection. Annals of Statistics, pp. 1302 1338, 2000.
François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th international symposium on symbolic and algebraic computation(ISSAC) pp. 296 303, ACM, 2014.
Francois Le Gall and Florent Urrutia. Improved rectangular matrix multiplication using powers of the soppersmith-wingeee tensor. In Proceedings of the Twenty-Nin Ninth Anmual ACM-SIAM Symposium Discrete Algoritlms(SODAA) pp. 1029 1046. SIAM, 2018.
Yin Tat Lee, Zhao Song, and Qiuyi Zhang. Solving empirical risk minimization in the current matrix multiplication time. In COLT. https: / arxiv http://aaxvvvoooa///.a/e/a 01///110000044..... 04440.44477... pdf, 2019.
Xingguo Li, Jarvis Haupt, and David Woodruff. Near optimal sketching of low-rank tensor regression. In Advances in Neural Information Processing Systems (NeurIPS), pp. 3466- 3476. https:/ /tt//axxvvcoo werxiv.org/pdee org/pdf 11009. .w0.90.700.... pdf, 2017.
Yi Li, Ruosong Wang, and David P Woodruff. Tight bounds for the subspace sketch problem with applications. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1675-1674. SIAM, https://arxtv.org/fff///// 05543 påf, 2020a.
Yi Li, Ruosong Wang, Lin Yang, and Hanrui Zhang. Nearly lincar row sampling algorithm for quantile regression. In ICML, 2020b.
Yichao Lu, Paramveer Dhillon, Dean P Foster, and Lyle Ungar. Faster ridge regression via the subsampled randomized hadamard transform. In Advances in neural information processing systems, pp. 369-377, 2013.
Olvi Mangasarian, Rudy Setiono, and William H Wolberg. Pattern recognition via linear programming: Theory and application to medical diagnosis. 1990.
Olvi Mangasarian, W Nick Street, and William H Wolberg. Breast cancer diagnosis and prognosis via linear programming. Operations Research, 43(4):570-5) 577,, 1995.
Jelani Nelson and Huy L Nguyên. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. Tn 2013 IEEE 54th Annuul Symposium on Foundations of Computer Science (FOCS), pp. 117-126. TEEE, attp::///ardv.orrr////////11110 1002, 2013.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochas- tic approximation approach to stochastic programming, SIAM Journal on optimization, 19(4):1574 1609, 2009.
Yurii Nesterov. Introductory lectures on convex programming volume notes, 3()):5, 1998.
Basic course. Lecture
Yurii Nesterov. Introductory lectures on conver optimizalion: A basic course, volume 87. Springer Science & Business Media, 2013.
Yurii Nesterov and Sebastian U Stich. Efficiency of the accelerated coordinate descent method on structured optimization problems. SIAM Journal on Optimization, 27(1): 110-123, 2017.
Yurïi E Nesterov. A method for solving the convex programming problem with convergence rate o (1/k" 2). In Dokd. akad. nauk Sasr, volume 269, pp. 543 547, 1983.
11

---

Under review as a conference paper at ICLR 2021
Mert Pilanci and Martin J Wainwright. Iterative hessian sketch; Fast and accurate solution approximation for constrained least-squares. The Journal of Machine Learning Research, 17(1):1842-1879, 2016.
Mert Pilanci and Martin J Wainwright. Newton sketch: A near linear-time optimization algorithm with lindar-quadratic convergence. SIAM Journal on Optimization, 27(1): 205-20 245, 2017.
Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and oplimization, 30(4):838 855, 1992.
Ilya Razenshteyn, Zhao Song, and David P Woodruff. Weighted low rank approximations with provable guarantees. In Proceedings of the 48th Anmual Symposium on the Theory of Computing (STOC), 2016.
James Renegar. A polynomial-time algorithm, based on newton's method, for linear pro- gramming. Mathemalical Programming, 40(1-3):59 -3,, 1988.
Mark Rudelson and Roman Vershynin. Hanson-wright inequality and sub-gaussian concen- tration. Flectronic Communications in Probability, 18, 2013.
Tamás Sarlós. Improved approximation algorithms for large matrices via random projections. In 47th Annual IEFE Symposium on. Foundations of Computer Science (FOCS) 21-24 October 2006, Berkeley, California, USA, Proceedings, pp. 143- 132,1 2006.
Gerard Sierksma and Yori Zwols. Linear and integer optimization: theory and practice. CRC Press, 2015.
Zhao Song. Matriz theory: optimization, concentration, and algorithms. PhD thesis, The University of Texas at Austin, 2019.
Zhao Song, David P. Woodruff, and Huan Zhang. Sublinear time orthogonal tensor decom- position. In Advances in Neural Information Processing Systems 29: Annual Conference on Newral Information Processing Systems (NIPS) 2016, December 5-10, 2016, Barcelona, Spain, pp. 793- 193-801, 2016.
Zhao Song, David P Woodruff, and Peilin Zhong. Low rank approximation with entrywise f1-norm error. In Proceedings of the 49th Annual Symposium on the Theory of Computing (STOC). ACM, https://aatt
org/pdf///e /1fff/11...../ 11111111111.,....111111111111111 2017.
Zhao Song, Ruosong Wang, Lin Yang, Hongyang Zhang, and Peilin Zhong. Efficient symmetric norm regression via linear sketching. Advances in Newral Information Processing Systems (NeurIPS), pp. 828 838. https: : //arxiv...vvv//////////eaa org/ //tff//////// /9900 01788. pdf, 2019a.
Zhao Song, David Woodruff, and Peilin Zhong, Average case column subset selection for entrywise -n-mr loss. In Advances in Neural Information Processing Systems (NearIPS), pp. 10111-10121. https: //axxiv//xivv/// org/ /ptpp///.0...////////// 07986. .df, 2019b.
Zhao Song, David Woodruff, and Peilin Zhong. Towards zero-one law for colunn subset selection. In Advances in Newral Information Processing Systems (NeurIPS), pp. 1120-1131. https://arxx org/pdf/ 1111/.11.111 01442,1422200 pdf, 2019c.
Zhao Song, David P Woodruff, and Peilin Zhong, Relative error tensor low rank approximation. In Proceedings of the Thirticth Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 2772 2789. SIAM,
08246.0886..... pff, 2019d.
Gerhard Tintner. Stochastic linear programming with applications to agricultural economics. In Proceedings of the Second Symposium in Linear Programming, volume 1, pp. 197-228. National Bureau of Standards Washington, DC, 1955.
Joel A Tropp. Improved analysis of the subsampled randomized hadamard transform. Advances in Adaptive Data Analysis, 110 2011.
12

---

Under review as a conference paper at ICLR 2021
Pravin M. Vaidya. An algorithm for linear programming which requires O(((m + n + (m + Jarithmetic operations. In FOCS. IEEE, 1987.
Pravin M Vaidya. Spooding-up linear programming using fast matrix multiplication. In FOCS. IEEE, 1989.
Robert J Vanderbei al. Linear programming. Springer, 2015.
Vladimir Vapnik. Principles of risk minimization for learning theory. In Advances in neural information processing systems, pp. 831-838, 1992.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
Ruosong Wang and David P Woodruff. Tight bounds for l oblivious subspace embeddings. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1825-1843. SIAM, 2019.
Yining Wang, Hsiao- Yu Tung, Alexander J Smola, and Anima Anandkumar. Fast and guaranteed tensor decomposition via sketching. In Advances in Newral Information Processing Systems (NIPS), pp. 991 999. attps://arxiv.orgg
/5006. 04448, 2015.
Tsui-Wei Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit S Dhillon, and Luca Daniel. Towards fast computation of certified robustness for relu networks. In ICML. https: https://arraie //arxivv org/pdf /804..8044.00 09699. pdf, 2018.
Virginia Vassilevska Williams. Multiplying matrices faster than poppersmit-winnggee In Proceedings of the forty-oourth annual ACM symposium on Theory of computing (STOC), pp. 887-898. ACM, 2012.
Eric Wong and J Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In TCML, 2018.
David P. Woodruff. Sketching as tool for numerical linear algebra. Foundalions and Trends in Theoretical Computer Science, 10(1-2):1-157, 2014.
Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Oplimizalion, 24(4):2057 2075, 2014.
Yinyu Ye, Michael J Todd, and Shinji Mizuno. An self-dual linear programming algorithun Mathemalics of Operalions Research, 19(1):53 67, 1994.
homogencous and
13


Reviews:
[{"review_id": "e-tz6KX24X8", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "SUMMARY: 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. \n\nREVIEW: I don't think the paper is ready for publication yet, since it needs significant polish and strengthening. My reasons are stated below. \n\n1. My biggest issue with the paper is that the motivation doesn't seem strong enough to me. If, despite being able to use exact solvers in each step of the IPM, the paper is able to merely match the run time of Lee et al and Cohen et al, then what is the advantage of doing the exact solves? I think the paper could be greatly strengthened if they are able to apply this technique to *improving* run times of some problem classes, as opposed to just matching state-of-the-art on one problem class.  \n\n2. While one could argue that using exact solvers and having feasibility in each step is theoretically interesting, I personally don't think it's interesting enough to merit publication at ICLR; of course, this is a subjective matter of taste, so one could argue otherwise as well. However, I think if this were to be of interest to the broader theoretical CS audience (beyond the handful of researchers that have worked on this problem in the recent past), then the paper's scope would need to be wider. Can the authors try to make more changes to these methods and *still* match the state-of-the-art? With the current modifications, to me, the paper doesn't seem sufficiently different from previous works to merit publication. \n\n3. The sketching techniques shown are not different enough. I have the same comment about it as 1. and 2.\n\n4. I feel the writing also needs to be significantly improved. Leaving aside error of language and grammar, what I think needs a vast improvement is the story-telling aspect of the paper. There needs to be greater effort put into telling *why* characteristic X of algorithm A is \"bad\" or \"good\", *why* some question is interesting, etc. I think, at its current state, the paper can be read and comprehended by a very small handful of people (the ones whose works are cited), and that, to me, is really not enough. \n\n5. Finally, I was disappointed that a paper marketed as so heavily theoretical, there is not even a proof sketch shown of the high level technique or any of the technical contributions. I shouldn't have to go to the appendix to see these, and the authors should put some effort into putting some math into the main body. I believe that highlighting novel proof techniques in the main body would also go a long way into convincing the reader(s) (such as myself) of novelty of the paper's contributions. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "U8onvvhzfkS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper improves robust central path based methods for linear programming. It's able to keep intermediate matrices oblivious, and solutions feasible. It builds upon a line of recent work that solves linear programs in time proportional to the cost of inverting a single matrix.\n\nIn my opinion, these improved methods are of mostly theoretical interest: if one assume n^{3} time matrix multiplication, the rank-1 update schemes from the original Karmarkar paper already obtain an n^{3} runtime. Such gains also hold for more intermediate values of matrix multiplication (e.g. Strassen fast matrix multiplication has bene implemented, so 2.8 is a reasonable assumption from practical perspectives), but I think the 2-batch update scheme of Vaidya is already sufficient as well.\n\nTherefore, I'm concerned whether this paper is suitable for this venue. There are no experimental evaluations of the algorithm, and the theoretical gains are too reliant on the matrix multiplication exponent being < 2.5.", "extra_scores": {}, "extra_text": {}}, {"review_id": "PXkP9m_SETP", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.  \n\nAlso, one way of motivating the new approach is the use of sparse sketching methods. Recently for several tasks in numerical linear algebra it has been shown that NN can learn efficient sparse sketching matrices which outperform the standard \"randomized\" sketching constructions such as CountSketch.  \n\nHowever, my only concern is whether ICLR is the right venue for this purely theoretical paper. While I am supportive of the paper I can understand the potential objections regarding lack of empirical evaluations.  \n\nMinor Comments:\n- fix quotation marks (e.g., the \"iterate and sketch\" in the abstract.)\n- page 2: We only updating -> We only update\n- page 2: our method decrease -> our method decreases\n- page 2: sketching methodology proposed by Clarkson and Woodruff'13. I would instead say Sarlos'06 and Clarkson and Woodruff'13\n- page 3:  generalizes to subspace -> subspace embedding\n- page 4: Literature Vaidya (1989) shows -> The work of ... shows that\n- page 4: ... potential function characterize -> charcterizing\n- page 5: rephrase the sentence before Def 2.2\n- page 6: matricesand -> matrices and\n- page 7: state-of-art -> state of the art (fix all instances)\n- page 7: The new update ->The new update rule\n- page 7: solve the linear system inexactly -> solve the linear system approximately?\n- page 7: the feasibility of our approach prevents us from the complicated analysis -> maybe need to rephrase it? \n- page 7: implementing of Eq. (4) reduces back -> implementing Eq. (4) reduces\n- page 8: we only need to do matrix-vector multiplications. How many such multiplications are needed? O(1)? specify it.\n- page 8: fasten -> speed up?\n\n=====POST-REBUTTAL COMMENTS========\nAs I mentioned earlier in my review, I like the result and I feel it could be interest of the TCS community. However, as correctly raised by other reviewers, ICLR may not be the right venue for this paper and also it would be beneficial if authors improve the presentation of their result and the motivation of their work further. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "NYAOdBTPbT1", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:  The authors propose a randomized linear program solver that applies sketching to the central path calculations. The resulting algorithm maintains feasibility and employs oblivious sketching matrices as opposed to other randomized solvers. The algorithm is relatively simpler to describe. However, the requirement of feasibility and oblivious sketching is not well motivated.\n\n\nMajor comments/questions\n1. The difference between oblivious and non-oblivious sketches.\nThe advantage of the oblivious sketching is not well explained and motivated. Is there an algorithmic advantage of the oblivious sketching methodology? Oblivious sketching has clear advantages in streaming data settings, however it's not clear what would be the benefit in an iterative algorithm with an obvious sketch. Given that the computational complexity is the same as leverage score sampling based non-oblivious sketching based methods, the authors need to provide a stronger motivation.\n\n2. Maintaining feasibility.\nIt's not clear why exact feasibility is important in this class of randomized algorithms. Maintaining approximate feasibility should be possible to obtain relatively easily in the state of the methods. Please correct me if I'm wrong.\n\n3. Sparsity.\nThe authors mention destroying the sparsity pattern as a shortcoming. Does the proposed method leverage input sparsity and sparsity pattern? Is it possible to quantify this, e.g., in terms of the number of nonzero entries?\n\n\nMinor comments/questions\n\n1. Left and right sketch.\nCan you clarify what is the algorithmic consequence of the left/right sketching property in Table 2.\n\n2. Coordinate-wise embedding\nIt looks like coordinate wise embedding property is a standard property that is satisfied for almost all known randomized JL embeddings, as opposed to a new construction. Is there a known JL construction that doesn't satisfy the coordinate-wise embedding property?\n\n3. In corollary 2.8, what are the dimensions of A_i ?\n \nMinor comment\n1. Some small typos\npage 1 footnote 1. Missing word or typo in 'We use O* hides;\npage 2 'linear programmings'. I believe 'linear programs' is more idiomatic.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers found it hard to understand the motivation of using both oblivious sketching and maintaining feasibility throughout the course of the algorithm, given that the ultimate running times matched those of existing work. Because there wasn't a concrete improvement over prior work, the worry is what the impact of the paper would ultimately be. There was also a concern with novelty, similarity to the work of Cohen, Lee, and Song, and a reliance on fast matrix multiplication exponents. The paper could also benefit from an improved presentation. 
Decision: Reject