John Ellipsoids via Lazy Updates
Authors: David Woodruff
Taisuke Yasuda
Venue: NeurIPS 2024 poster (2024)
Keywords: John ellipsoid
sketching
sampling
fast matrix multiplication
Primary area: optimization
TL;DR: Efficient algorithms for John ellipsoids by lazily updating the weights

Abstract: We give a faster algorithm for computing an approximate John ellipsoid around $n$ points in $d$ dimensions. The best known prior algorithms are based on repeatedly computing the leverage scores of the points and reweighting them by these scores (Cohen et al., 2019). We show that this algorithm can be substantially sped up by delaying the computation of high accuracy leverage scores by using sampling, and then later computing multiple batches of high accuracy leverage scores via fast rectangular matrix multiplication. We also give low-space streaming algorithms for John ellipsoids using similar ideas.

John Ellipsoids via Lazy Updates
David P. Woodruff Carnegie Mellon University dwoodruf@cs. cmu edu
Taisuke Yasuda
Voleon Group
yasuda. taisukee@gmailll............. com
Abstract
We give a faster algorithm for computing an approximate John ellipsoid around n points in d dimensions. The best known prior algorithms are based on repeatedly computing the leverage scores of the points and reweighting them by these scores [CCLY19]. We show that this algorithm can be substantially sped up by delaying the computation of high accuracy leverage scores by using sampling, and then later computing multiple batches of high accuracy leverage scores via fast rectangular matrix multiplication. We also give low-space streaming algorithms for John ellipsoids using similar ideas.
Introduction
The John ellipsoid problem is a classic algorithmic problem, which takes as input a set n points {ai, ....... an) in d dimensions, and asks for the minimum volume enclosing ellipsoid (MVEE) of these n points. If is the convex hull of these n points, then a famous result of Fritz John [Jo48]] states that such ellipsoid satisfies 1 P S Q, and if P is furthermore symmetric, then yd LQEPE IPCC Q. Equivalently, we may consider the input points to be constraints of polytope (x: (a., IiÚe [n]]. in which case the problem is to compute a maximal volume inscribed ellipsoid (MVIE). These problems the quadratic form defining the ellipsoid. In this work, we focus on the symmetric case, so that the polytope P' may be written P (x || 1}, where A denotes the d matrix with the input points a; in the rows, and our goal is to output an ellipsoid Q which approximately satisfies P Vd.Q. Q.
related by taking polars, which corresponds to inverting
The John ellipsoid problem has far- far-reaching applications in numerous fields of computer science. In statistics, the John ellipsoid problem equivalent to the dual of the D-optimal experiment design problem [Atw69, Si113], in which one seeks weights for selecting subset of dataset to observe an experiment. Other statistical applications of John ellipsoids include outlier detection [ST80] and pattern recognition [Ros65, Gli98]. In the optimization literature, computing John ellipsoids is a fundamental ingredient for the ellipsoid method for linear programming [Kha79], cutting plane methods [TKES8], and convex programming [Sho77, Vai96]. Other applications in theoretical computer science include sampling (Vem05, CDWY 18, GN23), bandits [BCK] 12, HK 16), differential privacy [NTZ13], coresets [TMF20, TWZ* 22], and randomized numerical linear algebra [Cla05, DDH 09, WY23, BMV23].
We refer to survey of Todd [Tod16] 6] for account algorithms and applications of John ellipsoids.
1.1 John ellipsoids via iterated leverage scores
Following long line of work on algorithms for computing John ellipsoids [Wo170, Atw73, KT93, NN94, Kha96, STT78, KY05, SF04, TY07, ASTO8, Yull, HFR20J based on convex optimization techniques, the work of [CCLY19] developed new approach towards computing approximate John
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

ellipsoids via a simple fixed point iteration approach. The approach of [CCLY19] starts with an observation on the optimality condition for the dual problem, given by
minimize
log det(A WA) d
subject to W; 2 0, E [n]
where W diag(w).' The optimality condition requires that the dual weights satisfy
w, (.(VWAA
for each E [n]. where (A) for a matrix denotes the i-th leverage score of A. Definition 1.1 (Leverage score). Ler A E Rxd Then, for each E [n], we define the i-th leverage score
[Ax]
Ti (A) a (A a,
sup Ax
A
The optimality condition of (1) can be viewed as a fixed point condition, which suggests the following iterative algorithm for computing approximate John ellipsoids
T W AA) = = (.t-!..a. a. (A (( A)=a a
(2)
where W(() diag( w(t) (.). After repeating this update for Os log(n/d) iterations starting with (0) d/n- 1, it can be shown that the ellipsoid Q defined by the quadratic form Q A (7) A, i.e. Q fx E Rd x Qx 1}, satisfies
VI= LRPCCV0.0
Note that the computation leverage scores can be done in O(nd==1) time, where w S 2.371552 the current exponent of fast matrix multiplication [DWZ23, WXXZ24]. Thus, this gives an algorithm running time (( ndd log(n//d) (fd)) for outputting an ellipsoid with the guarantee (3).
known that input matrices with additional structure admit even faster implementation of this algorithm. For instance, [CCLY 19, SYYZ22] give faster algorithms for sparse matrices A for which the number of nonzero entries nnz(A) (A) ) is much less than nd. The work of [SYYZ22] shows that this approach can also be sped up for matrices with small treewidth.
1.2
Our results
Our first main result a substantially faster algorithm for computing John ellipsoids. the typical regime where >> d. our algorithm runs in nnd log(n/d) time to output ellipsoid Q satisfying (3), and O( 'nnd log(n/d) time to output an ellipsoid Q which approximates the maximal volume up to (1 E) factor. We will discuss techniques for this result in Sections 1.2.1 and 1.2.2.
Table 1: Running time of John ellipsoid approximation for dense n d matrices, for > d poly(=- log n). There is other prior work on sparse matrices and matrices with low treewidth [CCLY19, SYYZ22].
Running time
Guarantee
[KY05, TY07]
O(E O ndd)
volume approximation
[CCLY19] [CCLY19, SYYZ22]
( nd - log(n/d)
(3)
(( nnd (log n) log(n/d)
(3)
Theorem 1.6
O nd) log(n/d)
For a weight vector w E I2", we will often write the corresponding n n diagonal matrix diag(w) as the capitalized version W.

---

1.2.1 Linear time leverage scores via fast matrix multiplication
We start by showing how approximate leverage scores up to (1 +) factors in ((dd) time, which had not been observed before to the best of our knowledge. Note that if we compute exact leverage scores using fast matrix multiplication, then this takes time O(nd~=1) Alternatively, sketching- based algorithms for approximate leverage scores are known, which gives the following running time for sparse matrices with nnz(A) nonzero entries.
Theorem 1.2 (1SS11, DMMW12, CW13)). There is an algorithm which, with probability at least 1- 6, outputs T for E [n]] such that
T = (1 c)r((A)
and runs in time O nnn(nn A) log(n/00 ())) + poly(ds- poly(d+==oog(n/O))
If the goal is to compute (1 + -aapproxita leverage scores for dense n x d matrix, then we are not aware of a previous result which does this in a nearly linear ((nd) time, which we now show: Theorem 1.3. There is an algorithm which, with probability at least 6, outpus F/ i E [n] such that
7 in time ((nd) poly log(e-1 log(n/0)) + (n) (alyye=-og((//00
Our improvement comes from improving the running time analysis of a sketching- based algorithm of [DMMW12] by using fast rectangular matrix multiplication. We will need the following result on fast matrix multiplication:
Theorem 1.4 ([Cop82, Will1, Wi124J). There is a constant a 2 0.1 and an algorithum for multiplying m X m and m X m² matrix in O(m² poly log m) time, under the assumption that field operations can be carried out in (1) time.
By applying the above result in blocks, we get the following version of this result for rectangular matrix multiplication.
Corollary 1.5. There is constant a 2 0.1 and an algorithm for multiplying n x d for n. 2 d and a d t matrix in O(nd nt!/a+1) poly log t time, under the assumption that field operations can be carried out in (1) time.
Proof. Let m = 1//0_ If d S m, then matrix multiplication takes only O(ndt) (ntt//-11) time, so assume that d 2 m. We partition the first matrix into an O(n/m) x ((d/m) block matrix with blocks of size m m and the second into an (dd/m) x block matrix with blocks of size m m By Theorem 1.4, each block matrix multiplication requires Om poly log m) time, and we have O(nd/m²) of these to do, which gives the desired running time.
That is, the above result shows that when multiplying much smaller 1, then this multiplication can be done roughly O(nd) poly log / time. The work of (DMMW12) shows that the leverage scores of A can be written as the row norms of A. for a d x t matrix with f O( log(n/6)) 6)), and thus this gives us the result of Theorem 1.3.
n x d matrix A with a d x matrix for
1.2.2 John ellipsoids via lazy updates
By using Theorem 1.3, we already obtain a John ellipsoid algorithm which runs in time log(n/ poly log(s log time, which substantially improves upon prior algorithms for dense input matrices A. We now show how to obtain further improvements by using the idea of lazy updates. At the heart of our idea is to only compute the quadratic forms for the John ellipsoids for most iterations, and defer the computation of the weights until we have computed roughly Ollog n) iterations. the end of this group of iterations, we can then compute the John ellipsoid weights via fast matrix multiplication as used in Theorem 1.3, which allows us to remove the suboptimal poly log log n terms the dominating term of the running time.
Theorem 1.6. Given A E Raxd, let P be the polytope defined by P = fx E Rd ||Ax| S 1}. For & E (0, 1), there is an algorithm, Algorithm 3, that runs in time
O (le='nn)(loo(// + poly log(e log n)) + O(n) poly(e"'
+ 0(n )a (log n)
and returns an ellipsoid Q such that VI+E Q PCC Vd- Q with probability at least 1 - 1/ poly(n).
3

---

The full proof of this result is given in Section 2.
Let Q(+) = A T (()) A, where the weights w-(+) are defined as (2). Note that with this notation, the update rule for the iterative algorithm of [CCLY19] can be written as
w (t-1) a. (Q a,.
(4)
Thus, given high-aceuracy spectral estimates to the quadraties Q(+, we can recover the weights w! to high accuracy in (d²) time per iteration by evaluating the quadratic forms a ( a, and then multiplying them together. This approach is useful for fast algorithms if we only need to to do this for a small number of indices i E [n]. This indeed the case we only need these weights for a row sample of vW( A, which is sufficient for computing a spectral approximation to the next quadratic form Q(+) Furthermore, we only need low-accuracy leverage scores (up to a factor of, say, n1 to obtain a good row sample, which can be done quickly for all rows [LMP13, CLM+ Thus, by repeatedly sampling rows of (W(") A, computing high-aceuracy weights on the sampled rows, and then building an approximate quadratic, we can iteratively compute segh-accuracy approximations (()) to the quadratics Q(t) More formally, our algorithm takes the following steps:
We first compute low-accuracy leverage scores of v (((+-)) A. which can be done in ((d) time. This gives us the weights (()) to low accuracy, say (()), for all n rows.
We use the low-accuracy weights (*) to obtain a weighted subset of rows of VUC A which spectrally approximates Q Note, however, that we do not yet have the sampled rows of ( A to high accuracy, since we do not know the weights ((()) to high accuracy.
If we only need the weights ((') for a small number of sampled rows S [ [n], then we can explicitly compute these using (4), since we inductively have access to high-aceuracy quadratics Q(t') for I' 1,, 1. These can then be used to build Q(1)
While this algorithm allows us to quickly compute high-accuracy approximate quadratics Q(), this algorithm cannot be run for too many iterations, the error in the low-accuracy leverage scores ( grows to poly(n) factors in (logn) rounds. This is problem, this error factor directly influences the number of leverage score samples needed to approximate Q(t), We will now the fast matrix multiplication trick from the previous Section 1.2.1 to fix this problem. Indeed, after Oloog n) iterations, we will now have approximate quadratics Q(1) @ Q(0 for t = O(log n).
Now we just need to compute the John ellipsoid weights which are given by
= II |o, "TTAQ" (1)
To approximate this quickly, we can approximate each term ||e, A(Q by [leT -()((=1))-/""((()) [| for a random Gaussian matrix G(t), by the Johnson lemma [JL84]]. Here, the number of columns of the Gaussian matrix can be taken to be poly(s-1 log n), so now all we need to compute is the matrix product
A (Q()))1/22 (,))))
which is the product of a d matrix and d x m matrix for poly(s- n). By Theorem 1.4, this can be computed in Ond poly log m) time. However, this resetting procedure only run the running time contribution from the O(s-!) times across the T 0(E log n) iterations,
resetting is just
( poly bog(s-1lop log n) + O(n) poly(s-1 log
Overall, the total running time of our algorithm is
( O(==Ind)(logh nnoonnnnn//////// + poly log(=-" + +(n) poly(s- logn). Remark 1.7. In general, our techniques can be be viewed as a way of exploiting the increased efficiency of matrix multiplication when performed on larger instance by delaying large matrix multiplication operations, so that the running time is O nogon// (n)(n)/d)) Oyr where Tr is the time that it takes to multiply A by d x matrix for = poly(E-) logn). While we have instantiated this general theme by obtaining faster running times via fast matrix multiplication, one can expect similar improvements by other ways of exploiting the economies of scale of matrix multiplication, such as parallelization. For instance, we recover the same running time if we can multiply vectors in parallel so that T, O(dd).

---

1.2.3 Streaming algorithms
The problem of computing John ellipsoids is also well-studied in the streaming model, where the input points a; arrive one at time in a stream [MSS10, ASI5, WY22, MMO22, MMO23J. The streaming model is often considered when the number of points is so large that we cannot fit all of the points in memory at once, and the focus is primarily on designing algorithms with low space complexity. Our second result of this work is that approaches similar to the Theorem 1.6 in fact also give a low-space implementation of the iterative John ellipsoid algorithm of [CCLY19).
take to prove
Theorem 1.8 (Streaming algorithms). Given A Ruxd, let P be the polytope defined by P {x E R | S 1]. Furthermore, suppose that is presented in a stream where the rows a, E IR arrive one by one in a stream. For (0,1). there is an algorithm, Algorithm 1, that makes passes over the stream, takes OddT) time update after each new row, and returns an ellipsoid such that VI+E QQ P Vd. Q. Furthermore, the algorithm uses most O(PT) words of space.
||Ax||
T = ll=="oog(n//f
In Section 1.2.2, we showed that by storing only the quadratics Q(t) and only computing the weights =h= a, (Q('-1)) a, needed, we could design fast algorithms for John ellipsoids. In fact, this idea is also useful in the streaming setting, since storing all of the weights w!" requires ((n) space per iteration, whereas storing the quadratics Q(9 requires only O(de) space per iteration. Furthermore, the streaming setting, we may optimize the update running time by instead storing the pseudo-inverse of the quadratics (Q(1)- and then updating them by using the low rank update formula. This gives the result of Theorem 1.8.
Algorithm 1 Streaming John ellipsoids via lazy updates
1: function STrEEAMNIKOOOONNEELLLPPOOODIIpp matrix A)
2: for f 0 T' do
3:
Let Q = 0
4: for i
do
5:
if t 0 then
6:
Let Q(1)
Q(1) + a
7:
else
8:
Let w
I a. (Q(
9:
Let Q (t)
Q(1) + a,a
10:
return
7+1 ΣT
1.3
Notation
Throughout this paper, A will denote an n x matrix whose n rows are given by vectors a, E Rd. For positive numbers a, b > 0, we write positive semidefinite matrices Q, R. we write Q = (1 R to mean that (1- - Q < R.+ where z denotes the Löwner order PSD matrices.
bb to mean that (1-s)b (1++)b. For symmetric
Fast algorithms
2.1 Approximating the quadratics
We will analyze the following algorithm, Algorithm 2, for approximating the quadratics Q( of the iterative John ellipsoid algorithm.
Fix row i. Note then that for each iteration 4, Ile, A A(Q(--))-1/3G11 is distributed as indepen- dent x2 variable with & degrees of freedom, scaled by ||e? A(Q (1-1))) [23, say X,. Note then that
We note that storing the sscudo-inverss may increase the space complexity by polynomial factors in the bit complexity model.
5

---

Algorithm 2 Approximating the quadratics
function APPROOXQUADRATIC(nnng matrix A, initial weights w()) number of rounds 7)
2: Let (0) A W(
A for W diag (w)
3:
for f = 1 T do
4:
d x & Gaussian matrix G. Let u! = u [(-1) ||. A (Q
Compute A (Q -
5:
for each i E [n]. Let S( be a (1 -aprroxiiaa leverage score sample of VU( A (Thm. 2.3).
6:
7:
For rows sampled by ((9), set v; = III, a; (Q((-1))aa a.
8: Let Q / /V
(Q))T 9: return {Q Jt=0 Tt=
after 7 iterations,
T
II
ee TeTT ((((((Q@)---a 1/2
u
t=1
which is distributed as
T
(T)
II c 1(Q 1/221
II X,
(5)
for ii.d. x² variables X2 with & degrees of freedom. We will now bound each of the terms in this product.
2.1.1 Bounds on products of x² variables
We need the following bound on products of x2 variables, which generalizes [SSK17, Proposition 1].
Lemma 2.1. Let X1, X2,..., X² be t i..dd. x² variables with k degrees of freedom. Then,
1
Pr
X <
inf C -. R
R
.((Okk/2)
1=1
and
Pr
X;
R
S inf C. R 5>-k/2
i=1
where
2T + k/2)
C.
> 0
1(k/2)
Proof. For s k//2, the moment generating function of log X; is given by
1
2/21 aa/2 dr ( C. Ce,
E log
E E
2k/2I(k/2)
T(k/2)
Then by Chernoff bounds,
1
1
Pr X
Pr
exp
Σ
s log N;
R²
E
slogg slog slog X. C
R
1=1
and
Pr
X₂ > R
Pr
exp
Σ log X;
2 12.
E log Rt

---

Using the above result, we can show that if the x2 variables have k = O(1/0) degrees of freedom and the number of rounds is log n for small enough constant e, then the product of the x2 variables Ih X will be within n factor for some small constant
O.
Lemma 2.2. Fix small constant 0 > 0 and let k = O(1/0). Let T = c log n. for sufficiently small constant e 0. Let X1, X2,........ XT be t i.i.d. x² variables with & degrees of freedom. Then,
Pr 2
II Xi
n² } 21 poly(n)
Proof. Set 8 - k/2. Then, C- and Cs.k are absolute constants. Now let to be small enough (depending on and k) such that for T = clog C -, C. S n. Furthermore, set R = n.. Then, by Lemma 2.1, we have that both Pr[ X; R) and Pr[II X; 2 R} are bounded by n R-= = n no = 1/ (nly(n), as desired.
It follows that with probability at least 1 1- are bounded by n for every row i E [xx] and for every iteration / E [7]. We will condition on this event in the following discussion.
1 1/ (olyooll.... the products of x² variables appearing in (5)
2.1.2 Bounds on the quadratic Q(+)
In the previous section, we have established that the products of x² variables in (5) are bounded by n². We will now use this fact to show that the quadratics Q (f-1) in Algorithm 2 are good approximate John ellipsoid quadratics. We will use the following leverage score sampling theorem for this.
Theorem 2.3 ([DMM06, SS11J). Let A Raxd Let T 2 (A) and let p: minf1, T for a ( log(d/8). I is diagonal matrix with S = 1/VP, with probability and 0 otherwise for i E [n], then with probability at least 1- -, 8,
for all x E Rd.
|SAx 2 = (1 + Ax
This theorem, combined with the bounds on x2 products, gives the following guarantee for the approximate quadraties Q(t).
Lemma 2.4. Fix a small constant 0 > and let = 0(100). Suppose that the leverage score sample in Line 6 oversamples by a factor of O(n20), that is, uses leverage score estimates T such that T 2 ( ((=2))==(VVU TT(VVUU A). Then, with probability at least 1 - 1/ poly(n), we have for every I E [T) that
Q -1+te)
where (1) = -1 a (Q()) a for E [n]. Furthermore, Q can be computed in (Te 2,1 log time in each ileration.
Proof. We will first condition the success of the event of Lemma 2.2, that the x² products in (5) are bounded by n² factors for every row i [n] and every iteration E [t]. We will also condition on the success of the leverage score sampling for all T' iterations.
(t) Note that by (5) and the bound the x² products, u is within O(n29) factor of vi") and thus (())
a correct leverage score sample for vV(()). A. We thus have that
(()) (S(t) V) ( V = (
For the running time, note that ((1) samples at most O 20 log rows in each iteration, and each sampled row i requires O(d"T)) compute ( This gives the running time claim. D
7

---

Algorithm 3 John ellipsoids via lazy updates
1: function JOHNELLIPSOID(iput matrix A)
2: Let B = 0(ccte-- and T O(clog(n/d)) for sufficiently small constant
3: Let w; = d/n for i E [md]
(0)
4:
for b= to do
5:
Let [Q (1()))
1t=0 be given by APPROXQUADRATIC(A, w (Algorithm 2).
6:
Let (t- for t E [2]] be a random d x m Gaussian for m O( 2 (g n)
Compute A (1)0) """ (77))
7:
Let w/(h.tt = IIp m ll -IQ .....
8:
(b,t)
for each E [n]].
9:
Let (0) = ((,T))
10:
Let W BT Es.e w-(b.))
11:
return A WA
2.2
Full algorithm
We now combine the subroutine for approximating quadratics from Section 2.1 with resetting procedure using fast matrix multiplication to obtain our full algorithm for quickly computing John ellipsoids. The full algorithm is presented in Algorithm 3.
We will need the following theorem, which summarizes results of [CCLY19] on guarantees of the fixed point iteration algorithm (2) under approximate leverage score computations.
Theorem 2.5 (Lemma 2.3 and Lemma C.4 of [CCLY19[). Ler A Raxd and let P = {x ||Ax loc S 1}. Let 0( - log(n/d)). Suppose that
w (1) (1 + ((L1)
for all t [T' and E [n]. Then, if the ellipsoid given by the quadratic form A (T) A, then VI+E CC /d.Q.
We also use the Johnson-LLindensraass lemma, which is standard tool for randomized numerical linear algebra, especially in the context of approximating leverage scores [SS11, DMMW12, LMP13, 15]+15).
Theorem 2.6 (JJL84, DG03)). Let m O log(n/5) and let be random m Gaussian
matrix. Then, for any n points a a2, ..... an I in d dimensions, we have with probability at least 1 - that
Ga 12 = (1 c)llall
simultaneously for every E [n]]
We will now give proof of Theorem 1.6.
Proof of Theorem 1.6. We first argue the correctness of this algorithm. By Theorem 2.5, it suffices verify that w! (htt) computes (1 -)approxxmmate leverage scores in order prove the claimed guarantees of Theorem 1.6. For the updates within APPROXQUADRATIC (Algorithm 2), we have by
Lemma 2.4 that
Q0)= (1) V. A
Thus,
((-1), lle, (
1/2 = - E
lle A(A T (1 -1/1/1
((--1)
=
(t) output by APPROXQUADRATE (Algorithm 2) indeed satisfy the require- and thus the weights v ments of Theorem 2.5.
For the weights computed in Line 8 of Algorithm 3, note that also compute these weights, but this time with approximation error from the application of the Gaussian matrix G()) to speed up the

---

computation. Applying Theorem 2.6 with set to e/ BT and failure probability 8 = 1/ poly(n), we have that
le. |e
= (
Note then that Line takes a product of at most BT of these approximations, so the total error in the approximation is at most
(1 = (T) BT = - (1 (E)))
The running time is given by BT iterations of the inner loop of APPROX QUADRATUA and B iterations of the fast matrix multiplication procedure in Line 7 of Algorithm 3. The inner loop of APPROXXQUARAATU AUACRATIC requires (nd) time to compute the product with the x & Gaussian as well as the time to compute the approximate quadratic, which is bounded in Lemma 2.4. Altogether, this gives the claimed running time bound.
Future directions
In this work, we developed fast algorithms and low-space streaming algorithms for the problem of computing John ellipsoids. Our fast algorithms use combination of using lazy updates together with fast matrix multiplication to substantially improve the running time of John ellipsoids, and we apply similar ideas to obtain low-space streaming implementation of the John ellipsoid algorithm.
Our results have several limitations that we discuss here, which we leave for future work to resolve. First, algorithm makes crucial use of fast matrix multiplication in order to get running time improvements. However, this makes it a less attractive option for practical implementations, and also makes the polynomial dependence on E in the (n) poly(E-1) term rather large. Thus, it is an interesting question whether the rumning time that we obtain in Theorem 1.6 is possible without fast matrix multiplication.
Question 3.1. Is there an algorithm with the guarantee of Theorem 1.6 that avoids fast matrix multiplication?
More generally, an interesting question to design algorithms for approximating John ellipsoids with optimal rumning time. This is old question which has been studied in a long line of work [Wo170, Atw73, KT93, NN94, Kha96, STT78, KY05, SFO4, TY07, ASTO8, Yull, HFR20J, and we believe that the investigation of this question will lead to further interesting developments in algorithms research.
Question 3.2. What is the optimal rumning time of approximating John ellipsoids?
For instance, one interesting question is whether it is possible to obtain nearly linear time algorithms that run in time ((nd) + (nn) po or even input sparsity time algorithms that run in time ((nz((A) + (n)) (oly(e-1). The resolution of such questions for the least squares linear regression problem has led to great progress algorithms, and studying these questions for the John ellipsoid problem may have interesting consequences well.
John ellipsoids are closely related E, Lewis weights, which give natural b generalization of John ellipsoids and leverage scores and have been a valuable tool in randomized numerical linear algebra. There has been a recent focus on fast algorithms for computing (1 + a-pprooxee Lp Lewis weights (FLPS22, AGS24], and thus it is natural to ask whether developments in algorithms for John ellipsoids would carry over to algorithms for E, Lewis weights well.
Question 3.3. What is the optimal running time of approximating É Lewis weights?
Finally, we raise questions concerning streaming algorithms for approximating John ellipsoids. In Theorem 1.8, we gave multi-pass pass streaming algorithm which obtains (1++)-optima) John ellipsoid. natural question whether a similar algorithm can be achieved in fewer passes, or there are pass lower bounds for computing (1 + E) -)-ottimal John ellipsoids.
Question 3.4. Are there small space streaming algorithms for approximating John ellipsoids up to a (1 + E) factor which make fewer than O(e log(n/d) passes, or do small space streaming algorithms necessarily require many passes?
We note that there are one-pass small space streaming algorithms we allow for approximation factors that scale as (VVlogn) rather than (1 + e) [WY22, MMO22, MMO23].

---

Acknowledgments and Disclosure of Funding
The authors were supported in part by a Simons Investigator Award and NSF CCF-2335412.
Bibliography
[AGS24] Simon Apers, Sander Gribling, and Aaron Sidford. On computing approximate Lewis weights. CoRR, 000/22444002881, 2024. 3
[AS15] Pankaj K. Agarwal and R. Sharathkumar. Streaming algorithms for extent problems in high dimensions. Algorithmica, 72(1):83-99, 2015. 1.2.3
[AST08] Selin Damla Ahipasaoglu, Peng Sun, and Michael J. Todd. Linear convergence of modified Frank- Wolfe algorithm for computing minimum-volumm enclosing ellipsoids. Optim. Methods Softw., 23(1):5-19, 2008. 1.1,3
[Atw69] Corwin L.. Atwood. Optimal and efficient designs of experiments. Ann. Math. Statist., 40:1570-1602, 1969.
[Atw73] Corwin I.. Atwood. Sequences converging to D-optimal designs of experiments. Ann. Statist., 1:342-352, 1973, 1.1,
[BCKI2] Sébastien Bubeck, Nicolò Cesa- Bianchi, and Sham M. Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, COLT 2012 -he 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, volume 23 of JMLR Proceedings, pages 41.1 JMLR.org. 2012.
[BMV23] Aditya Bhaskara, Sepideh Mahabadi, and Ali Vakilian. Tight bounds for volumetric spanners and applications. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
[CCLY19] Michael B. Cohen, Ben Cousins, Yin Tat Lee, and Xin Yang. A near-optimal algorithm for approximating the John ellipsoid. In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Reseurch, pages 849-873, PMLR, 2019. (document), 1.1, 1, 1, 1.2.2, 1.2.3, 2.5
[CDWY18] Yuansi Chen, Raaz Dwivedi, Martin J. Wainwright, and Bin Yu. Fast MCMC sampling algorithms on polytopes. J. Mach. Learn. Res., 19:55:1-55:880 2018.
[Cla05] Kenneth L. Clarkson. Subgradient and sampling algorithms for é regression. In Proceedings of the Sixteenth Anmual ACM-SIAM Symposium on Discrete Algorithms, SODA '05, pages 257-266, USA, 2005. Society for Industrial and Applied Mathemat-
ics. 1
[CLM* 15] Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform sampling for matrix approximation. In Tim Roughgarden, editor, Proceedings of the 2015 Conference Innovations Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, pages 181-190. ACM, 2015. 1.2.2, 2.2
[Cop82] Don Coppersmith. Rapid multiplication of rectangular matrices. SIAM J. Comput., 11(3):467-47) 471, 1982. 1.4
[CW13] Kenneth L. Clarkson and David P. Woodruff. Low rank approximation and regression in input sparsity time. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC' 13, Palo Alto, CA, USA, June 1-4, 2013, pages 8 81-90. ACM, 2013, 1.2
10

---

[DDH 09] Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W. Ma- honey. Sampling algorithms and coresets for Ep regression. SIAM J. Comput. 38(5):2000-2078 2009.
[DG03] Sanjoy Dasgupta and Anupam Gupta, An elementary proof of a theorem of Johnson and Lindenstrauss. Random Struct. Algorithms, 22(1):60-65, 2003, 2.6
[DMM06] Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Sampling algorithms for Eg regression and applications. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pages 1127-1136. ACM Press, 2006. 2.3
[DMMW12] Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, and David P. Woodruff. Fast approximation matrix coherence and statistical leverage. J. Mach. Learn. Res., 13:3475-3506, 2012. 1.2, 1.2.1, 1.2.1, 2.2
[DWZ23] Ran Duan, Hongxun Wu, and Renfei Zhou. Faster matrix multiplication via asymmetric hashing. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 2129-2138. IEEE, 2023.
[FLPS22] Maryam Fazel, Yin Tat Lee, Swati Padmanabhan, and Aaron Sidford. Computing Lewis weights to high precision. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 12, 2022, pages 2723-2742
SIAM, 2022. 3
[Gli98] François Glineur. Pattern separation via ellipsoids and conic programming. Mémoire de DEA, Faculté Polytechnique de Mons, Mons, Belgium, 1998.
[GN23] Adam Gustafson and Hariharan Narayanan. John's walk. Adv. in Appl. Probab., 55(2):473-499) 2023.
[HFR20] Radoslav Harman, Lenka Filová, and Peter Richtárik. A randomized exchange algo- rithm for computing optimal approximate designs of experiments. J. Amer. Statist. Assoc., 115(529):348-366 2020. 1.1,3
[НK16] Elad Hazan and Zohar S. Karnin. Volumetric spanners: An efficient exploration basis for learning. Mach. Learn. Res., 17:119:1-119:44 2016.
[JL84] William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), volume 26 of Contemp. Math., pages 189-206. Amer. Math. Soc., Providence, RI, 1984. 1.2.2,
[Joh48] Fritz John. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, Jamuary 8, 1948, pages 187-204. Interscience Publishers, Inc., New York, N. Y., 1948.
[Kha79] Leonid G. Khachiyan. A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR, 149(5))103331000) 1096, 1979.
[Kha96] Leonid G. Khachiyan. Rounding of polytopes in the real number model of computation. Math. Oper. Res., 21(2):07--20,, 1996. 1.1.
[KT93] Leonid G. Khachiyan and Michael Todd. On the complexity approximating the maximal inscribed ellipsoid for a polytope. Math. Programming, 61 Ser. 1):137-159, 1993. 1.1,
[KY05] Piyush Kumar and Alper Yildirim. Minimum-volume enclosing ellipsoids and core sets. J. Optim. Theory Appl., 126(1):1-21, 2005. 1.1, 1,3
[LMP13] Mu Li, Gary L. Miller, and Richard Peng. Iterative row sampling. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 127-136. IEEE Computer Society, 2013, 1.2.2,
11

---

[MM022] Yury Makarychev, Naren Sarayu Manoj, and Max Ovsiankin. Streaming algorithms for ellipsoidal approximation of convex polytopes. In Po-Ling Loh and Maxim Raginsky. editors, Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 3070-3093, PMLR, 2022. 1.2.3,
[MM023] Yury Makarychev, Naren Sarayu Manoj, and Max Ovsiankin. Near-optimal streaming ellipsoidal rounding for general convex polytopes. CoRR, 0bs/2211100946 2023. 1.2.3, 3
[MSS10] Asish Mukhopadhyay, Animesh Sarker, and Tom Switzer. Approximate ellipsoid in the streaming model. In Weili Wu and Ovidiu Daescu, editors, Combinatorial Optimization and Applications 4th International Conference, COCOA 2010, Kailua- Kona, HI, USA, December 18-20, 2010, Proceedings, Part II, volume 6509 of Lecture Notes in Computer Science, pages 401-413 Springer, 2010. 1.2.3
[NN94] Yurii Nesterov and Arkadii Nemirovskii. Interior-poins polynomial algorithms in convex progranming. volume 13 of SIAM Studies in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. 1.1,
[NTZ13] Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 351-360 ACM, 2013.
[Ros65] Judah Ben Rosen. Pattern separation by convex programming. Journal of Mathematical Analysis and Applications, 10(1): 1965.
[SF04] Peng Sun and Robert M. Freund. Computation of minimum-volumee covering ellipsoids. Oper. Res., 52(5):690-706 2004. 1.1,
[Sho77] Naum Z Shor. Cut-off method with space extension in convex programming problems. Cybernetics, 13(1):94 96, 1977.
[Sil13] Samuel Silvey. Optimal design: an introduction to the theory for parameter estimation, volume 1. Springer Science & Business Media, 2013.
[SS11] Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM J. Comput. 1016))111311926 2011. 1.2, 2.3, 2.2
[SSK17] Željka Stojanac, Daniel Suess, and Martin Kliesch. On products of gaussian random variables. arXiv preprint arXiv: 2017. 2.1.1
[ST80] BW Silverman and DM Titterington. Minimum covering ellipses. SIAM Journal on Scientific and Statistical Computing, 1 1(4):401-409, 1980.
[STT78] Samuel D Silvey, DH Titterington, and Ben Torsney. An algorithm for optimal designs on a design space. Communications in -heeryy and Methods, 7(14):1379- 1389, 1978. 1.1,3
[SYY722] Zhao Song, Xin Yang, Yuanyuan Yang, and Tianyi Zhou. Faster algorithm for structured John ellipsoid computation. CoRR, abs/2211.11442 144007 2022. 1, 1
[TKE88] S. P. Tarasov, L. G. Khachiyan, and I. I. Arlikh. The method of inscribed ellipsoids. Dokl. Akad. Nauk SSSR, 298(5):0081-1085 1988. 1
[TMF20] Murad Tukan, Alaa Maalouf, and Dan Feldman. Coresets for near-convex functions. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, virtual, 2020.
[Tod166 Michael J. Todd. Minimum volume ellipsoids- - theory and algorithms, volume 23 of MOS-SIAM Series Optimization. SIAM, 2016.
12

---

[TWZ*22] Murad Tukan, Xuan Wu, Samson Zhou, Vladimir Braverman, and Dan Feldman. New coresets for projective clustering and applications. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 5391-5415. PMLR, 2022. 1
[TY07] Michael J. Todd and E. Alper Yildirim. On Khachiyan's 's algorithm for the computation of conninum-volumee enclosing ellipsoids. Discrete Appl. Math., 1335133:17311744 2007. 1.1, 3.3
[Vai96] Pravin M. Vaidya. A algorithm for minimizing convex functions over convex sets. Math. Programming, 73(3, Ser. A):291-341, 1996.
[em05] Santosh Vempala. Geometric random walks: a survey. Combinatorial and computa- tional geometry, 52(573-612):2. 2005.
[Wil11] Ryan Williams. Non-uniform ACC circuit lower bounds. Proceedings of the 26th Annual IEEE Conference Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pages 115-125. IEEE Computer Society, 2011. 1.4
[Wi124] Ryan Williams. Personal communication, 2024. 1.4
[Wo170] P. Wolfe. Convergence theory in nonlinear programming. In Integer and nonlinear programming, pages 1-36. North-Holland, Amsterdam-Londonn, 1970. 1.1,3
[WXXZ24] Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha to omega. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithmss, SODA 2024, Alexandria, VA, USA, Junuary 7-10, 2024, pages 3792-3835. SIAM, 2024. 1
[WY22] David P. Woodruff and Taisuke Yasuda. High-dimensional geometric streaming in polynomial space. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO. USA, October 31 November 2022, pages 732- 743. IEEE, 2022. 1,2.3,3
[WY23] David P. Woodruff and Taisuke Yasuda. New subset selection algorithms for low rank approximation: Offline and online. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 1802-1813. ACM, 2023. 1
[Yul1] Yaming Yu. D-optimal designs via a cocktail algorithm. Stat. Comput., 21(4):475-44 481, 2011. 1.1,3
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss limitations our work in Section 3, and pose open questions towards closing these gaps.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
We provide complete proofs of all of our results, and references to prior work whenever we need prior results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/ Stapcc/guiess//odeee
wwmmiisssooooooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips. wttpccccpppccccceeececceccccccct /ttp:///ggiieeeeeeeuuuubiiiiiiii /CodeSubmic ssisnnonllll onPolicy))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
16

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that NeurIPS Code of Ethics https: / /ttp///eers///ee/ee//ee//reeeree cc httpppbliit/thicccuueeeeeeee.eel
didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
17

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
18

---

Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/coddemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
19


Reviews:
[{"review_id": "qciyY2JVAd", "reviewer": "Reviewer_hiPW", "summary": "This paper considers the computing of an approximate John ellipsoid. They improve the algorithm by lazy update and fast matrix multiplication. They also give low-space streaming algorithms using similar ideas.", "questions": "See weakness", "limitations": "NA", "rating": 3, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "This paper improves John ellipsoid algorithm via lazy update and fast matrix multiplication from O(d^{\\omega-1}) to O(d).", "weaknesses": "Major:\n- This paper is badly written.\n- The authors do not give justifications in the checklist.\n\nMinor:\n- Please check the capitalization in the references.\n- can you explicitly give the space complexity in Theorem 1.8?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The authors do not give justifications in the checklist.\n\nWe believe we have included a justification for the paper checklist whenever the list item warrants additional justifications. In particular, we give an in-depth discussion of the limitations of our work in Section 3. We are happy to give further justification on anything.\n\n> Please check the capitalization in the references.\n\nUpon a review of the citations, we have ensured that the names in the following titles are properly capitalized:\n- \"An elementary proof of a theorem of Johnson and Lindenstrauss\"\n- \"Computing Lewis Weights to High Precision\"\n- \"On computing approximate Lewis weights\"\n- \"A near-optimal algorithm for approximating the John ellipsoid\"\n- \"Linear convergence of a modified Frank-Wolfe algorithm for computing minimum-volume enclosing ellipsoid\"\n- \"Faster Algorithm for Structured John Ellipsoid Computation\"\n\n> can you explicitly give the space complexity in Theorem 1.8?\n\nThe space complexity for Theorem 1.8 is included in the paragraph following Theorem 1.8, and the total space usage is $O(d^2 T)$ words (i.e., real numbers) of space, where $T = O(\\epsilon^{-1}\\log(n/d))$ is the number of passes. This has been clarified in the theorem statement of Theorem 1.8 in the revision.", "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": "", "extra_scores": {}}, {"review_id": "G6q23s6aYW", "reviewer": "Reviewer_VRzA", "summary": "The authors give a leverage score approximation algorithm that runs in nearly linear time for dense matrices. Specifically, to find leverage scores for a matrix $A \\in \\mathbb{R}^{n \\times d}$, they give an algorithm based on fast matrix multiplication that runs in time $\\widetilde{O}(nd)$. This, combined with a \"lazy update\" trick, yield a new fast algorithm to approximate the John ellipsoid for a symmetric convex polyhedron represented as the set $\\{x \\in \\mathbb{R}^d \\colon \\| Ax \\|_{\\infty} \\le 1\\}$. The same ideas also transfer to a $\\sim \\log n$-pass streaming setting to find the John ellipsoid, yielding a new low space complexity algorithm for finding the John ellipsoid that has a stronger approximation guarantee than existing one-pass solutions.", "questions": "See all of the above.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The leverage score approximation algorithm the authors give may yield faster algorithms for a class of optimization algorithms that use leverage score computations as a primitive (one example I can think of offhand is the work [JLS21]). In particular, this should imply a $\\widetilde{O}(nd)$ time algorithm for finding weights $w$ such that $2w_i \\ge \\tau_i(W^{1/2-1/p}A)$ for $p \\ge 2$ (which is a one-sided Lewis weight approximation that suffices for a large number of applications, including $\\ell_p$ row sampling and $\\ell_p$ regression for $p \\ge 2$). The insight is pretty simple and cleanly presented, which I view as a positive. I suspect a similar result is true (along with a corresponding low-space streaming algorithm) for for $p < 2$ by applying this to the natural contraction mapping that computes the weights.\n\n[JLS21] Improved Iteration Complexities for Overconstrained p-Norm Regression (https://arxiv.org/abs/2111.01848)", "weaknesses": "I wish more applications had been discussed. Leverage scores are a pretty fundamental primitive that get used in a lot of problems in optimization and numerical linear algebra, and it would have been nice to write down concrete runtime improvements (if any) that emerge from Theorem 1.3. I alluded to some in the previous section, and I would be happy to raise my score if the authors either confirm the above or present a few more settings in which concrete runtime improvements are realized. Alternately, I'd also raise the score if the authors discussed a bit about the barriers behind extending their approach to these settings.\n\nMild issues:\n\nI think there are typos in Algorithm 1 and a suboptimal runtime guarantee. I think Line 8 should read:\n\n$w_{i}^{(t)} = \\prod_{t'=1}^{t} a_i^{\\top}(A^{\\top}W^{(t')}A)^{-1}a_i$. In particular, as written, Line 8 multiplies across the first $t$ rows for a fixed quadratic, whereas the loop counter should be running over the quadratics instead.\n\nI also think Line 9 should read:\n\n$Q^{(t)} \\gets Q^{(t)} + w_i^{(t)}a_ia_i^{\\top}$ (I think you need an outer product and not an inner product, same thing for Line 6)\n\nI think you also need an averaging step at the very end, as the [CCLY19] algorithm returns the weights $w = 1/T \\cdot \\sum_{t'=1}^{T} w_{t'}$.\n\nFinally, I think this algorithm actually can be implemented in $d^2T \\le d^{\\omega}T$ time per row. This is because of associativity:\n\n$\\prod_{t=1}^t a_i^{\\top}Q_{t}^{-1}a_i = \\prod_{t=1}^t a_i^{\\top}(Q_{t}^{-1}a_i)$\n\nNow, $(Q_{t}^{-1}a_i)$ is a vector that can be formed in time $d^2$ via naive multiplications, and then $a_i^{\\top}(Q_{t}^{-1}a_i)$ is a dot product that can be found in $d$ time. We do this $t$ times for each term in the product and then multiply them all together for a total time of $d^2t$ for step $t$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> I wish more applications had been discussed. ...\n\nWe note that $(1+\\epsilon)$-approximate John ellipsoids have many applications to statistics, machine learning, and computational geometry, as is discussed in our introduction as well as in the works of [CCLY19, SYYZ22]. Some notable applications include D-optimal experiment design, outlier detection, and pattern recognition.\n\nThere are a couple of difficulties which prevent us from stating further running time improvements as a result of our faster leverage score algorithm beyond our applications to John ellipsoids, and we believe our work highlights the importance of overcoming such difficulties. The first is that the target application should require $(1+\\epsilon)$-approximate leverage scores, since if only constant factor approximations are required (as in the case of $\\ell_p$ Lewis weight sampling), then leverage score approximation can be done in input sparsity time. If we wish to compute $(1+\\epsilon)$-approximate $\\ell_p$ Lewis weights using $(1+\\epsilon)$-approximate leverage scores, then known reductions require either exact leverage scores [FLPS22] or leverage score approximations that are $(1+\\epsilon/\\mathrm{poly}(d))$-approximate [AGS24]. In the latter case, in theory our results may no longer give improvements due to the large exponent in our polynomial dependence on $\\epsilon$. We have raised the question of whether faster algorithms can be design for $\\ell_p$ Lewis weights in the original draft, and we will include this discussion in the revision.\n\n> Mild issues: ...\n\nThank you for pointing these out! We have fixed these in the revision. The $d^\\omega$ dependence (rather than the $d^2$ that you suggest) is due to computing the matrix inverse $Q^{-1}$.", "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": "", "extra_scores": {}}, {"review_id": "v5UBN8viXS", "reviewer": "Reviewer_wsbb", "summary": "The paper proposes provably faster algorithm for computing John ellipsoids. The first idea is to approximate Leverage score with an existing faster algorithm given by Theorem 1.3. The second idea is to use fast matrix multiplication and lazy updates to reduce polylog suboptimality.", "questions": "Could you please clarify on your particular contribution?\n\nCould you please refer to the proof of Theorem 1.3?\n\nI am not an expert in John Ellipsoids. For me it seemed that the contribution was incremental, because the theoretical result combines existing techniques. By the way, the new result is obtained.\n\nI would also like you to comment on the most recent papers and preprints from 2023 and 2024 if any, to confirm your contribution.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Provably faster algorithm proposed", "weaknesses": "- despite that the main result does not rely on Theorem 1.3, there is no proof or reference for it.\n- contribution should clarified. The proof of Theorem 1.6 mainly relies on the existing results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> despite that the main result does not rely on Theorem 1.3, there is no proof or reference for it.\n\n> Could you please refer to the proof of Theorem 1.3?\n\nThe proof of Theorem 1.3 is sketched in the paragraphs immediately below it. \n\nWe first summarize the result of [DMMW12]. It is known that we can compute $Q$ such that $(1+\\epsilon)Q \\preceq A^\\top A \\preceq (1-\\epsilon) Q$ in time $\\mathrm{nnz}(A) + \\mathrm{poly}(d/\\epsilon)$ time [CW13], so the leverage scores of $A$ are the row norms of $A Q^{-1/2}$ up to a $(1\\pm\\epsilon)$ factor. We can then apply the Johnson--Lindenstrauss lemma and multiply this matrix by a random projection matrix $P$ with $t = O(\\epsilon^{-2}\\log n)$ rows, so that the row norms of $A Q^{-1/2} P$ approximate the row norms of $A Q^{-1/2}$ up to a $(1\\pm\\epsilon)$ factor. Thus, we indeed have that the leverage scores are approximated by the row norms of some matrix $AR$ for $R = Q^{-1/2}P$ up to $(1\\pm\\epsilon)$ factors.\n\nFinally, we can efficiently multiply $A$ by $Q^{-1/2}P$ quickly using Corollary 1.5. In the revision, we will include a full proof in the appendix. \n\n> contribution should clarified. The proof of Theorem 1.6 mainly relies on the existing results.\n\n> Could you please clarify on your particular contribution?\n\nOur result gives the fastest known algorithm for computing $(1+\\epsilon)$-approximate John ellipsoids when $\\epsilon$ is not too small. While we indeed build on existing techniques, and in particular the iterated leverage score algorithm of [CCLY19], we make two key improvements to this algorithm: (1) the use of lazy updates that allow us to better exploit the faster running time of leverage scores by batching the leverage score computations, and (2) the use of fast matrix multiplication to give a faster algorithm for approximating leverage scores. Finally, these ideas also give low-space streaming algorithms.\n\n> I would also like you to comment on the most recent papers and preprints from 2023 and 2024 if any, to confirm your contribution.\n\nTo the best of our knowledge, the most recent relevant work on computing $(1+\\epsilon)$-approximate John ellipsoids is the works of [CCLY22] and [SYYZ22], which are discussed thoroughly in the introduction. We are not aware of works from 2023 or 2024 on this topic.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper improves upon the computational state of the art for computing John's ellipsoids. The focus is on giving low-storage algorithms amenable to streaming data setting, and is based on a simple idea of delaying leverage scores via sampling, and then using fast matrix multiplication in batches to speed up the bottleneck with high approximation accuracy. The main weaknesses in my view are that the paper is presented in a way that feels narrow in scope, and as one reviewer points out, it can come across as a fairly incremental contribution. However, the results are correct and carefully executed, and the paper can be further improved incorporating some comments from useful reviews such as further acceleration using Woodbury approximations. I would encourage the authors to give more context on how these contributions can allow users to tackle problems that may have been out of reach due to the previous bottleneck, and just widen the scope of the paper even though the contribution is technical in nature. 

I recommend acceptance after studying the paper myself; due to the brevity and lack of substantive criticism in review hiPW, I chose to dismiss that score in the decision making process
Decision: Accept (poster)