Faster Algorithms for Structured John Ellipsoid Computation
Authors: Yang Cao
Xiaoyu Li
Zhao Song
Xin Yang
Tianyi Zhou
Venue: NeurIPS 2025 poster ()
Keywords: John Ellipsoid
Primary area: optimization

Abstract: The famous theorem of Fritz John states that any convex body has a unique maximal volume inscribed ellipsoid, known as the John Ellipsoid. Computing the John Ellipsoid is a fundamental problem in convex optimization. In this paper, we focus on approximating the John Ellipsoid inscribed in a convex and centrally symmetric polytope defined by $P := \{ x \in \mathbb{R}^d : -\mathbf{1}_n \leq A x \leq \mathbf{1}_n \},$ where $ A \in \mathbb{R}^{n \times d}$ is a rank-$d$ matrix and $ \mathbf{1}_n \in \mathbb{R}^n $ is the all-ones vector. We develop two efficient algorithms for approximating the John Ellipsoid. The first is a sketching-based algorithm that runs in nearly input-sparsity time $ \widetilde{O}(\mathrm{nnz}(A) + d^\omega) $, where $ \mathrm{nnz}(A) $ denotes the number of nonzero entries in the matrix $A$ and $ \omega \approx 2.37$ is the current matrix multiplication exponent. The second is a treewidth-based algorithm that runs in time $ \widetilde{O}(n \tau^2)$, where $\tau$ is the treewidth of the dual graph of the matrix $A$. Our algorithms significantly improve upon the state-of-the-art running time of $ \widetilde{O}(n d^2) $ achieved by [Cohen, Cousins, Lee, and Yang, COLT 2019].

Faster Algorithms for Structured John Ellipsoid Computation
Yang Cao Wyoming Seminary ycao48@yymiingsmminary org
Xiaoyu Li
University of New South Wales 7. Alaoyu.li@@maal com
Zhao Song
Xin Yang
University of California, Berkeley magic. linuzkde@gmail.commm com
The University of Washington yangxin1999277@mail..cm com
Tianyi Zhou
University of Southern California tzhou029@usc.eet
Abstract
The famous theorem of Fritz John states that any convex body has a unique maximal volume inscribed ellipsoid, known as the John Ellipsoid. Computing the John Ellipsoid is a fundamental problem in convex optimization. In this paper, we focus on approximating the John Ellipsoid inscribed in a convex and centrally symmetric polytope defined by P {a E Rd -1, I Ar S 1,), where A Raxdd is rank-d matrix and 1,, R is the all-ones vector. We develop efficient algorithms for approximating the John Ellipsoid. The first is sketching- based algorithm that runs in nearly input-sparsit time Ó(nzz( A) + d²), where nnz(A) denotes the number of nonzero entries in the matrix A and w 2.37 is the current matrix multiplication exponent. The second is a treewidth- based algorithm that runs in time Ö(nr²), where is the treewidth of the dual graph of the matrix A. Our algorithms significantly improve upon the state-of- sate-offthe--ee running time ((dd)) achieved by [Cohen, Cousins, Lee, and Yang, COLT 2019].
1 Introduction
The concept of the John Ellipsoid, introduced in the seminal work of [Joh48], plays fundamental role in convex optimization and convex geometry [Ba191, Bal01, LYZ05, Tod16]. John's 's theorem states that every compact convex with nonempty interior has a unique maximum-volume in- scribed ellipsoid, known as the John Ellipsoid [Joh48]. The John Ellipsoid has numerous significant applications, including high-dimensional sampling [Vem05, CDWY18, GN23), linear program- ming [1.S14), online learning [BCBK12, HK16), differential privacy [NTZ133, and uncertainty quantification [TLY24]. Moreover, is known that computing the John Ellipsoid equivalent to the D-optimal design problem in statisties [Puk06, Tod16], which has lot of applications in machine learning [AZLSW17, WYS17, LFNI8].
In this paper, we study the problem of computing the John ellipsoid Q of convex and centrally symmetric polytope P := {i Rd 1, < Ar 1,), where A Bn rank-d matrix and 1, is the all-ones vector. The John Ellipsoid E is the unique solution to the optimization problem maxgce" vol(Q) s.t. Q C P, where 8d is the set of ellipsoids in Rd and vol(Q) denotes the volume of Q. Since this geometric optimization problem can be formulated as constrained
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

convex optimization problem, the John Ellipsoid can be computed in polynomial time using convex optimization solvers, such as first-order methods [Kha96, KY05] and second-order interior-pon point methods INN94, SFO4]. The most efficient algorithm using convex optimization solvers takes (nd)) time, as demonstrated by (KY05, TY07].
Recently [CCLY19] proposed simple and fast fixed-point iteration (Algorithm 1) to compute the John Ellipsoid in (nd?) time by reducing the problem to the computation of &oc Lewis weights of the matrix A. The &o Lewis weights of A is a vector E RR" which can be seen as a weighted version of the leverage scores of A.
Algorithm I Approximating John Ellipsoid inside symmetric polytopes, Algorithm [CCLY19]
1: procedure APPROXJE(A E R
2: W1 < (d/n) 1,
3: for k 1,... ,T do
4: for i = + n do
5: end for
Wk++11 Wkit" a. (A diag(us ( AA) 'a;
6:
7:
end for
8:
for = + n2 do
9:
Ui T Ek= Wket
10: end for
11: U- diag(u)
12: return A UA
13:
end procedure
This iterative approach plays crucial role in simplifying the computation of the John Ellipsoid for convex symmetric polytopes defined by set of inequalities. Delving deeper into the algorithmic intricacies of [CCLY19], it becomes evident that primary computational hurdle lies in calculating the quadratic forms, denoted as a B B='a, a, where B is a weighted version of A A and a is a row vector in A. The algorithm in [CCLY19] employs the standard linear algebraic approach, which involves computing the Cholesky decomposition and subsequently solving linear systems. However, significant drawback of this method is its time complexity Ó(nd)). In many computational scenarios, this can be excessively cone-cons...n.
To address this challenge, we develop a new sketching baase based algorithm that offers an improved running time compared to [CCLY19]. Furthermore, we also provide an algorithm that exploit certain special structures to achieve speedups.
1.1 Algorithm in Nearly Input-Sparsity Time
Our first contribution an algorithm that computes the John Ellipsoid in nearly input-sparsity time. Theorem 1.1 (Main result I, input-sparsity time). Given matrix A E Band let symmetric convex polytope be defined as P = {a E R2 -1,, I Ax S 1n For any e, (0, 0.1), where ó denotes the failure probability, there exists randomized algorithm (Algorithm 2) that with probability at least - 5 outputs an ellipsoid Q satisfying vi+e CQ S vd. Q. Moreover, it runs within
Ol---o iterations and each iteration takes Õ nnz(A) 220 time, where nnz( A) is the number of non-zero entries of A and w R. 2.37 denotes the current matrix multiplication exponent [ADW*24) 24], and the Ô hides the log(d/8) factor.
Compared [CCLY19], we have significantly improved the per-iteration cost, reducing it from (ndd) to Ō(e-1 A) + - Here, the O-notation hides the log(d/5) factor. When the matrix A is sparse, our algorithm significantly outperforms [CCLY19]. Note that when the matrix A is dense, ie., nnz(A) A) (nd), our per-iteration cost becomes Õ
-eed'dd nd 2d2d). In the regime where n > dd and > e our algorithm is also better than [CCLY19] even when the matrix A is dense.
The technical improvements stem from two key factors: First, to achieve an input-sparsity running time, we introduce an additional subsampling procedure alongside the sketching approach used by [C]LY19]. This sampling step utilizes approximation of leverage scores, significantly accelerating

---

1: the oxpooenn of cotal time complestty
13
OUTS
12
11
2.173
2
10
of number constroluts
Figure 2: The geometric interpretation of the output ellipsoid. Let P be a given input polytope. We can find an ellipsoid Q so that VIFc Q S
Figure I: Time complexity comparison between CCLY19 (denotes (CCLY19) and ours, assum- ing n d²; = (1), and ignoring the log factors. The r-axis is corresponding to and y-axis is corresponding to b. The n² is the total running time.
PC Vd.Q.
the computation of matrix inverses, which is the main bottleneck in the per-iteration complexity of [CCLY19]. Second, approach requires more detailed analysis manage the accumulation of errors from both sampling and sketching within each iteration, thereby reducing the explicit dimension dependency in running time from log(n).
1.2 Algorithm for Small Treewidth
Our second algorithm is treewidth-based algorithm to compute the John Ellipsoid, which is extremely faster when the matrix A has small treewidth. Informally speaking, treewidth is property that measures how "tree-like" a graph is, and it originates from the structural graph theory [BGHK95, Dav06, LMS13J. For matrix A, the concept of treewidth is associated with the dual graph G that constructed from the matrix A. We defer the formal definitions to Section 2.3. We state our second main result as follows.
Theorem 1.2 (Main result II, small treewidth). Given a matrix A E Rxd whose dual graph G has treewidth т, let a symmetric convex polytope be defined as P = {a Rd -1, S Ar < 1n)- For any c, E (0, 0.1), where denotes the failure probability, there exists a deterministic algorithm (Algorithm 3) that outputs an ellipsoid Q satisfying
VT+c QCPCCIL
Moreover, it runs within O O(--11og(n//n log(n/d)) iterations and each iteration takes ((n time.
Our grewwdth-bassee algorithm is extremely useful when the input matrix A has small treewidth. In many real world datasets, the input matrix A typically can have large dimension n and d, but often exhibits small treewidth. For example, in the Netlib dataset, most LP instances have sublinear treewidth, typically in the range id//2 d3/4] [BDGR95]. In MATPOWER dataset used for power system analysis, the maximum problem size is 20467, 12659 while the maximum treewidth т = 35 IZMST10, Z.. For a detailed experimental analysis of treewidth in real-world datasets, refer the reader [MSJ19].
is also worth noting that having a small treewidth is a stricter condition compared to input sparsity since it places additional restrictions on the connectivity pattern of the matrix, which may not be captured solely by input sparsity.
Roadmap. The rest of the paper is organized follows. In Section 2, we provide some preliminaries for treewidth and John Ellipsoid. Section we give the formal definition for the John Ellipsoid. In Section 4, we present the technique overview for this paper. In Section 5, we present our main algorithm (Algorithm 2) for approximating John Ellipsoid inside symmetric polytopes and show the running time for the algorithm. In addition, prove the correctness of our implementation. In Section 6, we present our algorithm (Algorithm 3) for small treewidth setting. Section we provide the conclusion for our paper.
3

---

Table 1: Comparison of our algorithms with the previous ttte-of-thhe-at art presented in [CCLY19]. Given the input matrix A E Raxd and the approximation error e (0, 0.1), our algorithms achieve less ier-iteration cost while maintaining the same number of iterations. We ignore the O-notation in the table.
References
#Iters.
Cost per iter.
[CC
log(n/d)
nd'
Theorem 1.1
c =log(n/d)
6
nnz ()) +
Theorem 1.2 <-
#log(n/dd
nt²
2 Preliminaries
We first define some notations in Section 2.1. Then we introduce the definition of leverage score and its useful properties in Section 2.2. Next, we provides the necessary backgrounds of treewidth in Section 2.3. Then, in Section 2.4, we give the definition for Cholesky factorization. Finally, we state a matrix concentration bound in Section 2.5.
2.1 Notations
We use N(u, o²) to denote the normal distribution with mean and variance o². Given two vectors and y Rd, use (x, y) to denote the inner product between and y, i... (z, y) i= 24y4- We use 1, denote an all-1 vector with dimension n. For any matrix A E gaxd, we say A - 0 (positive semi-definite) if for all x E Rdd we have x: T Ax O. For function f. we use O(f) to denote f- (log f). For matrix A, use A" to denote the transpose of matrix A. We use w ~ 2.371 to denote the current matrix mulitpilcation exponent [ADW* 24]. For a matrix A, we use nnz(A) to denote the number of non-zero entries in A. For square and full rank matrix A, we use A-1 to denote the inverse of matrix A. For a positive integer, we use [n] to denote the set {1, ... n). For a vector æ, we use ||zl|| to denote the entry-wise & norm z, i... || == (Σin x x²/1/22 We say vector is 7-sparse if it has at most non-zero entries. For random variable X, use E[X] to denote its expectation. We use Pr[.] to denote the probability.
2.2 Leverage Score
We assume A E Raad has rank d. The leverage scores can be defined in several equivalent ways as follows.
Definition 2.1 (Leverage score). Given a matrix A Raad let U Rund be an orthonormal basis for the column space of A. For any i E [n]. the leverage score of the i-th row of A can be defined equivalently as: Part I. o;(A) = |/1/122 Part 2. (A(A) = a, (AT () A aç Part 3. a, (A) maxxerd (a.
The last definition offers an intuitive understanding of leverage scores. A row ag has higher leverage score when it is more influential, meaning there exists vector x for which the inner product with a; significantly larger than its average inner product (i.c.. || (1²) with the other rows of the matrix. This concept forms the basis of leverage score sampling, widely used technique in which rows with higher leverage scores are sampled with greater probability.
Next, we state a well-known folklore property of leverage scores (see [SS11, CCLY19) for example).
Lemma 2.2 (Folklore), Given a matrix A E Rexd, for any i E [n], it holds that S (A) S 1. Moreover, we have Ei (A) d.
We state useful tool for leverage score from [DSW22], which proved a stronger version that computes the leverage score for the matrix in the form of A(T - -VTV.. We only compute the leverage score for matrix A here.
computation, Lemma 4.3 in (DSW221). Given matrix A Boxd can compute vector ã E R in Ō (nnz(A) + d))) time, so that, ō is an approximation of the leverage score of matrix A, iee. ā E (1 + <z) a (A), with probability at least 5 The hides the log(d/ 8,) factor.
Lemma 2.3 (Leverage

---

2.3 Treewidth
We first define the tree decomposition and treewidth of a given graph, see figure for a concrete example.
Definition 2.4 (Tree decomposition and width graph [BGHK95, Dav06, LMS13)). tree decomposition is mapping of graphs into trees. For graph G. the tree decomposition is defined as (G) tree, and M (T)) (V))) is a family of subsets of V (G) called bags
pair (M, T), where labelling the vertices Tf satisfies that:
The vertices maintained by all bags is the same as those of graph G: ULeV(r) V(G).
For every vertex E EVGG), the nodes t (T) satisfying u E M(t) induce connected subgraph of
For every edge (u. u) E E(G), there exist node t V(T) that u, M()).
where V() denotes the vertex set of graph.
T}. The treewidth T of the The width of a tree decomposition (M,T) is max (M)) -1: minimum width over all tree decompositions of G.
Given a matrix A, we generalize the definition of treewidth as the treewidth of its associated dual graph. Though the treewidth of a graph is NP-hard to compute [FLS 18, ACP87J, is possible to find a width-O(7 log" n) tree decomposition within (m poly log n), where m denotes the number of edges, n denotes the number of vertices and T denotes the treewidth of graph G' [BGS21].
Definition 2.5 (Dual graph). Given matrix A E Raxd,
optionally partition its rows into m blocks of sizes Ti, Tem where n = -i=1 n2, When no explicit block structure given, we simply treat each row its own block (i.e,
for all i). The dual graph G of the matrix the columns of A). We say edge (i,j) E E if and only if there exists some block r E [m] such that both Ar, # O and And + 0, where Ar denotes the submatrix of A containing column and all rows in block r.
and is the graph G = (V, E) with veriex set = (1, .d} (corresponding
The treewidth of the matrix A is defined as the treewidth of its dual graph G
2.4 Cholesky Factorization
Next, we give the definition for Cholesky factorization.
Definition 2.6 (Cholesky factorization). Given a positive-defiiite matrix P, there exists a unique Cholesky factorization P = LL E Raxd, where L &Rax is lower-triangular matrix with real and positive diagonal entries.
We then introduce a result based on the Cholesky factorization of a given matrix with treewidth T:
Lemma 2.7 (Fast Cholesky factorization [BGHK95, Dav06)). For any positive diagonal matrix H Rxn for any matrix A E Æ with treewidth T, we can compute the Cholesky factorization A A HA = LL Rdxd d in O(T²²) time, where L E I is lower-triangular matrix with real and positive entries. satisfies the property that every row is T-sparse.
Remark 2.8. When only an O(log" -approximmation F to the treewidth T is known (which can be computed in (m p log n) time [BGS21]), the runtime becomes O(n O log' n), which remains efficient for small т.
2.5 Matrix Concentration
We need the following matrix concentration bound as tool to analyze the performance of our algorithm.
Lemma 2.9 (Matrix Chernoff Bound [Troll]. Let Xi...., X, be i.i.d. symmetric random matrices
with E[X,] 0, || almost surely and ||| Xilll S o², Let C E X,. For any
e E (0, 1), holds that Pr[[[C|| 2 e] S 2d - exp (- - 7
sr?
5

---

Problem Formulation
In this section, we give the formal definition for the John Ellipsoid of a symmetric polytope. We first give characterization of any symmetric polytope.
Definition 3.1 (Symmetric convex polytope). We define a symmetric convex polytope as
P : fxr E Rd Kaa, $ Vi [n)).
We define matrix A Rxxd associated with the above polytope P C R as collection of column vectors, i... A = (a1, 02. an)) and we assume A is full rank. Note that since symmetric, the John Ellipsoid of must be centered the origin. Since any origin-centered ellipsoid is of the form {a x G-2x I } for a positive definite matrix G, we can search over the optimal ellipsoid by searching proportional to (ee((G-l)i det(G)-1/2 so maximizing the volume is equivalent to maximizing log(det(G))) log(det(G)):
the possible matrix G. Note that for such ellipsoid, the volume is
Maximize log())t(G))), subject to: G = 0 |Ga,:I2 S 1, E [n]
(1)
In [CCLY19], it is shown that the optimal G must satisfy G-2 A diag(w) for the matrix A and vector w E R22- Thus, optimizing over we have the following optimization program:
Minimize Σ
log det waana? - d, subject to: w; 2 0, Vi E [n]]
For any weight vector E 20. we define the associated matrix
Q w.aaa Rdxd
(3)
Additionally, the optimality condition for this w has been studied in [Tod16]:
Lemma 3.2 (Optimality criteria, Proposition 2.5 in [Todd6]). weight w E R is optimal for
program (Eq. (2)) if and only if
Σ w. =d d, a 1, if 40 a < wf, = 0.
Ew
where Q is defined as in Eq. (3).
Besides finding the exact John Ellipsoid, can also find + ()++)-appronn) appproxxieete John Ellipsoid:
Definition 3.3 ((1 -)aaproxxmaate John Ellipsoid). For > 0, we say E B is (1 c)- approximation of program (Eq. (2)) if w satisfies E wy d, a 11+6, Vj Ejel [n] where Q defined as in Eq. (3).
Lemma 3.4 gives a geometric interpretation of the approximation factor in Definition 3.3. Note that for the exact John Ellipsoid Q" of the same polytope, Q' C Vd.Q"
Lemma 3.4 ((1 + a)approximnttion is good rounding, Lemma 2.3 in [CCLY19]). Let P be defined Definition 1. Let E R be (1 + approxxmmaaio of Eq. (2), and let be the associated matrix defined in Eq. (3). We define the ellipsoid E := {x Rd x Qx < 1}. Then the following property holds; A++ E C P.C. C Vd.& E. Moreover, vol( o0(()1=E) 2 (ep(-de/2) vol(E") where E the exact John Ellipsoid of P.
4 Technical Overview
In Section 4.1, we provide comprehensive overview of the framework from [CCLY19] upon which our work builds. In Section 4.2, we present our techniques for achieving nearly input-sparsity runtime. In Section 4.3, we describe our algorithm tailored for small treewidth.

---

4.1 Overview of Previous Work
The algorithm from [CCLY19] solves the John Ellipsoid problem via fixed- ixxed-point iteration scheme. Given the optimization program in Eq. (2), the optimal weight vector w" satisfies the fixed-point condition: for all i [n]. Wk+1,5 Wk, o, (wx), where dy(w) a, (A diag(w)A) aq. Starting from initial weight w1 (d/n) n, the algorithm iteratively updates the weights for T= O log(n log(n/d)) iterations until convergence to an (1 + appproxxiaat solution.
The main computational bottleneck the naive fixed-point iteration is computing a,(w²) for all i [n]] at each iteration, which requires (ndd) time using standard matrix inversion. To accelerate this, [CCLY19] applies random Gaussian sketching matrix S Rsxd (with O)c to approximate the quadratic form:
|IS(AT diag(w;) -1/2 diag(w)))))1122 / (uk..aill o, = II(AT diag(wx)A))" 1/2 a
Despite using sketching, [CCLY19] still computes the matrix inverse (AT diag(wx) (A) exactly, resulting in an (ndd) per-iteration cost.
4.2 Algorithm in Nearly Input-Sparsity Time
Fixed Point Iteration. Following [CCLY19), by the observation that the optimal solution wt to the program (2) satisfies w (1 (u(")) for all i [n], where ar(-) denote the leverage score based on the constraint matrix A, i.e., (,()) := a. (A" diag(w) A)- where a, denote the i-th row vector of matrix A, we use the fixed point iteration method to find the John Ellipsoid. Ideally, the algorithm updates the vector w by the fixed point iteration defined as:
Wk+1,i = a. v / (AT diag( (on((w))))) (wx) - / /
a, W (AT diag wK ()) 1/2 (A (iag(wa)) AA) - 1/2 V /k = [[(A* T diag(w:) (1) 1/2 11111/////uu /wk,,
If want to calculate this quantity exactly, then [CCLY19] already stated that the per iteration rumning time must have a dependence on quadratic dependency on d. Instead, we only require an approximate version, which comes at the cost of approximation guarantees and failure probability. The sketching-based algorithm in [CCLY19] use a random Gaussian matrix' 5 E R alone for speedup, and the resulting update becomes 1 == (A diag(w;) ())//) //w,,/
This update mitigate the running time dependency on but still suffers naf running time as they calculate the inverse term exactly.
Leverage Score Sampling. Note that if we denote B₁ := /diag(ux) A, and b7, is the i-th
row of matrix Bg, then for e [T 1]. we can write Wk+1.1 ((Bx) B&) -1b... In this light, 1,+1, & is precisely the leverage score of the i-th row of matrix Bg.
To compute these leverage scores efficiently, we use leverage score sampling with oversam- pling [CLM+15, 15, DLS233.. Specifically, if we sample rows of B& with probabilities proportional to an overestimate of their leverage scores (by a factor of k),, then with high probability, the sampled matrix provides (1 co) approximation to B B₁ A diag(w;)A.
Formally, the sampling process defined as follows.
Definition 4.1 (Sampling process). For any RT let H(w) = A W A, where W diag(w). Let p, 2 B a,(VW /) suppose we sample with replacement independently for s rows of matrix VW A, with probability pa of sampling row for some 3 > 1. Let i(j) denote the index of the row sampled in the j-th trial. Define the generated sampling matrix as
(w)) 1 Σ 1 - P(()
The following lemma provides the guarantee of the above sampling process.
each entry draws i.dd from standard normal distribution (O, 1)
7

---

Lemma 4.2 (Sampling using Matrix Chernoff, informal version of Lemma F.4), Let co, óo E (0,1)
be the precision and failure probability parameters, respectively. Suppose H (w) is generated in Definition I, then with probabilit al least 1 So, we have (1 (eoo)H((u)) 3 H(w) 3 (1+co) ((). Moreover, the number of rows sampled s = ( c (g dd
Sketching. In order to further speed up the algorithm, we apply sketching techniques at line 12 in Algorithm 2. For each iteration, we random Gaussian matrix of dimension X d to speed up the calculation while maintaining enough accuracy.
Following all the tools above, the algorithm first computes the veration-average vector u and then normalizes it to obtain the final output
able to prove the following conclusion. As shown in Algorithm 2,
Lemma 4.3 (Approximation error, informal version of Lemma E.4), Let u E R denote the iteration- averaged vector computed in Algorithm 2, where
1 - Wk,i Fix the number of iterations executed in the algorithm as T = O 11 log(n/d) d)) and 1000/e. Let (b) == log (z(u). Then for E [n]: (b(u)) S T log(5) + e/250 + 6g holds with probability
ó0-
This conclusion says that, by adding the steps (line 7 to line 15 in Alg. 2) to approximate the leverage score B we only introduce some extra manageable failure probability and additive error terms.
4.3 Algorithm for Small Treewidth
Now let's move to the technical overview for the treewidth setting. The treewidth setting is an interesting research problem, and has been studied in many works such as [BGS21, LSZ 20, SZ23]. When the constraint matrix is an incidence matrix for a graph, it is natural to parameterize the graph in terms of its Ireewidth T.
In our second algorithm (Algorithm 3), we leverage the fact that for matrix with small treewidth there exist a permutation P of A such that the Cholesky factorization PA W WAP = L.. is T-sparse during the iterative algorithm, i.c., L E R= has column sparsity т. Thus, instead first decompose B by LuLE in O(nr²) time. By using
of computing B, directly, the sparsity of LR, we then complete the follow-up computation of (ww) with O(nr²) time. In conclusion, we provide an implementation that takes O(nr²) T) to find the (1 + e)-approximmtion of John Ellipsoid.
5 Analysis of Input-Sparsity Algorithm
In Section 5.1, we present the running time needed for our algorithm (Algorithm 2). In Section 5.2, we provide a novel telescoping lemma. In Section 5.3, we show the correctness of our implementation.
For discussions, especially in the context of proofs, we've also introduced some new notation as- sist in comprehension and clarity. We define Qs == Ss Hg E RRa and WA +1, := 11Q [|
5.1 Running Time of Input-Sparsity Algorithm
Next, we show the running time of Theorem 1.1.
Lemma 5.1 (Running time of Algorithm 2, informal version of Lemma D.I). Given a symmetric convex polytope, for all (0, 1), Algorithm 2 can find (1 + c)² apprroiiinntio of John Ellipsoid inside this polytope with eo ((e) and T O(E log(n/d)) in time Ö((E") "nz((A (A) + YT)
5.2 Telescoping Lemma
We introduce an innovative telescoping lemma. This stands in contrast to Lemma C.4 as mentioned in [CCLY19]. The distinction between the two is crucial: the prior telescoping lemma restricted to sketching processes. contrast, the lemma we are about to discuss encompasses both sketching and sampling.
At each iteration of Algorithm 2, we compute approximate weights Wh,i using sketching or sampling, introducing errors relative to exact weights wx,i Our telescoping analysis bounds how
8

---

Algorithm 2 Faster Algorithm for approximating John Ellipsoid inside symmetric polytopes
procedure FASTAPPROXGENERALLA E Raxd)
Theorem 1.1 eD t Occ), + O (llodldggnd))) w1 + (d/n) 1n
2:
S 8 5 -
3:
for k L,..,,,,, 1
4:
W - diag(w:)
5:
B₃ t- VW b We want to compute Wk+1,i = (
by Eq. (4).
6:
Let Sk Rexd be random matrix where each entry is chosen i.i.d from (0 1)
7:
Computing the o(1)-xpproiinttionn the leverage score of B&
( d())
8:
Generate diagonal sampling matrix D2 E RR. RR"x according to the leverage score
9:
Via matrix Chernoff, (1 - <o) B Bg 3 Bg D3 B (1 + 60) Bg Bg
10:
Compute HA - (B₁ Dx)
Lemma 4.2, D N, O -2 dd log (1
11:
b For proof purpose, H3 (B k B₁) -1/2
12:
Compute Q2 5- F1
Qu E R Roxd O d2
13:
for i + m do
D 1 nnz A))
14:
1R+1.1 11 / end for
b 08+1. approximates the ideal update W
15:
16:
end Wk++1 wk+1
17:
for i for
18:
1 + do
19:
Ui T >k== Whet
b Lemma 4.3
20:
end for
21:
for = - do U; Σj u4
Lemma 5.3
23:
end for
V - (ddag(v)
V a diagonal matrix with the entries of
25:
return V and A VAA
26:
end procedure
these errors accumulate over T iterations by decomposing the final approximation quality dr(u) into We two terms: an initial condition term + log ă/2 and an average per-iteration error + E k= log wa, This directly motivates our choice T O log(n/d)) to ensure both terms O(e). yielding (1 (L+ e)-approximation.
Lemma 5.2 (Telescoping, Algorithm 2, informal version of Lemma E.3). Let u E R" denote
T the iteration-avent eeverion-averaged vector computed in Algorithm 2, where u, 1 E k= Whit. Fix T as the number of main loops executed in Algorithm 2. Let (:(u) log (u). Then for E [n]]
(u) < log z + Σk=1 log Wh.1 Eg holds with probability 1 80-
5.3 Correctness of Input-Sparsity Algorithm
In terms of Definition 3.3, to show Algorithm provides a reasonable approximation of the John Ellipsoid, it is necessary to prove that for the output R= of Algorithm 2, o,(v) < O(e).
Vi E [n]. Our main result is shown below.
Theorem 5.3 (Correctness, informal version of Theorem E.1). Lei en 1000' Let RD be the output of Algorithm For all C 10, when O(c-1 log(n/d)), we have Pr [a,(u) < c)+ e [n]] 2 1 - 5 8g Moreover, E 82 = d. Therefore, Algorithm 2 provides (1 (1+ c)2 approximation program Eq. (2).
Next, we show our final result.
Theorem 5.4 (Correctness part of Theorem 1.1). Given a matrix A Raxd we define centrally
symmetric polytope P as follows: {æ E Rd 1, < Ax $ 1,). h. Then, given e E (0, 1), Algorithum
that outputs an ellipsoid Q satisfies: V1+c Q PCC Qd
Proof. By combining Theorem 5.3 and Lemma 3.4, we can complete the proof.

---

Analysis of Small Treewidth Algorithm
In this section, we analyze the algorithm (Algorithm. 3) for constraint matrix with small treewidth (Definition 2.5). Further details are provided in Appendix G.
Algorithm 3 Faster Algorithm for approximating John Ellipsoid (under tree width setting)
1: procedure FASTAPPROXTW(A E Raxd)
Theorem 1.2
2:
- (e O(E log(n/d)), wi + (d/n)- 1n
3: for 1.... - do
4:
W₁ diag(wk).
5:
B& V
6:
La <- Cholesky decomposition matrix for Bg Bg i.e., In BB By
b O(r7?)
7:
for i = 1 do
8:
WK+ - b -
D 0(77)
9:
end for
10:
end for for
= + do
12:
U1 T 2k=1 Wkit
13:
end for
14:
U= diag(u).
U is diagonal matrix with the entries of > Approximate John Ellipsoid inside the polytope
15:
return U and AUA
end procedure
Theorem 6.1 (Running time of Algorithm 3, informal version of Theorem G.4). For all E (0, 1), we can find (1 + e)approxximation of John Ellipsoid defined by matrix A with treewidth T inside a symmetric convex polytope in time ( -T) where T - log(n/d).
Proof sketch. For matrices like A with a small treewidth т, there exists a permutation P allowing the Cholesky factorization, PA W APT -LL". to be T-sparse throughout the iterative algorithm. In essence, the matrix has a column sparsity of т. Instead of directly calculating B₃ B we first break down Bg BT into L which takes O(nr?) time. Utilizing the sparsity of L,, the computation of a (w) is also achieved O(nr?) time.
Next, we propose the theorem that shows the correctness of our algorithm.
Theorem 6.2 (Correctness of Algorithm 3, informal version of Theorem G.2). Let be the output of Algorithm For all (0, when T O(c log(n/d)) we have au S (1 +c) and n
2. 21 =
Proof sketch. We set T := log By using Corollary G.1 and the fact that for small e/50 < log(1 + <). we have for E [n]. log (u) < log(1 + +c) conclusion, dz(u) S 1 e. Additionally, since for & e [T') each row of Wki is leverage score of i-th row of matrix B =
WW.AA according Lemma 2.2, we have: Dmm ui - # + Wk,i + > d
Thus, we complete the proof.
7 Conclusion
Our paper studies the problem of approximating John Ellipsoid inside a symmetric polytope, where the state-of-the-art approach [CCLY19] had running time of O(nd²) per iteration. We proposed two fast algorithms based on different sparsity notions (i.c., number of nonzeros and treewidth) of the constraint matrix. Our first algorithm combines leverage-score- based sampling with sketching.
This has allowed us to optimize per iteration running time to Ō(E mnz(A) + e -2,²) with high probability, achieving logarithmic dependency on Furthermore, our second algorithm targets scenarios where the constraint matrix has low treewidth r. By Cholesky factorization, this algorithm achieves a time complexity of O(n7²) per iteration.
10

---

Acknowledgment
We thank anonymous NeurIPS reviewers for their constructive comments.
References
[ACP87] Stefan Arnborg, Derek G Corniil, and Andrzej Proskurowski. Complexity of finding embeddings in ak-tree. SIAM Journal on Algebraic Discrete Methods, 8(2):277-284, 1987.
24] Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. arXiv preprint arXiv:2404. 16349, 2024.
[Ans02] Kurt M Anstreicher.
Improved complexity for maximum volume inscribed ellipsoids. SIAM Journal on Optimization, 13(2):309-33) 2002.
[AW21] Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522-539, SIAM, 2021.
(AZLSW17] Zeyuan Allen-Zhu, Yuanzhi Li, Aarti Singh, and Yining Wang. Near-optimal design of experiments via regret minimization. In International Conference on Machine Learning pages 126-135. PMLR, 2017.
[Ba191] Keith Ball. Volume ratios and reverse isoperimetric inequality. Journal of the London Mathematical Society, 2(2):351-359) 1991.
[Ba10]] Keith Ball. Convex geometry and functional analysis. In Handbook of the geometry of Banach spaces, volume 1, pages 161-194. Elsevier, 2001.
[BCBK12] Sébastien Bubeck, Nicolo Cesa-Bianchi, and Sham M Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Conference on Learning Theory, pages 41-1. JMLR Workshop and Conference Proceedings, 2012.
[BDGR95] Shirley Browne, Jack Dongarra, Eric Grosse, and Tom Rowan. The netlib mathematical software repository. Technical report, 1995.
[BGdMT23] Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, and Stéphan Thomassé. Twin-width Linear minors, modular counting, and matrix multiplication. In 40th International Symposium on Theoretical Aspects of Computer Science, 2023.
[BGHK95] Hans L Bodlaender, John R Gilbert, Hjálmtyr Hafsteinsson, and Ton Kloks. Ap- proximating treewidth, pathwidth, frontsize, and shortest elimination tree. Journal of Algorithms, 18(2):238-255, 1995.
[BGS21] Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deter- ministic decremental sssp and approximate min-cost flow in almost-linear time. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1000-1008. IEEE, 2021.
[BLSS20] Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song. Solving tall dense linear programs in nearly linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, pages 775-788, 2020.
[BPSW21] Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein. Training (over- parametrized) neural networks near-linear time. In ITCS, 2021.
[BSS12] Joshua Batson, Daniel A Spielman, and Nikhil Srivastava. Twice-ramanujan sparsifiers.
SIAM Journal Computing, 1706):17041171,, 2012.
[BWZ16] Christos Boutsidis, David P Woodruff, and Peilin Zhong. Optimal principal component analysis distributed and streaming models. Proceedings of the forty-eighth annual ACM symposium Theory of Computing, pages 236-249 2016.
11

---

[CCLY19] Michael B Cohen, Ben Cousins, Yin Tat Lee, and Xin Yang. A near- near-optingg mpar-optimal algorithm for approximating the john ellipsoid. In Conference on Learning Theory, pages 849- 873. PMLR, 2019.
[CDWY18] Yuansi Chen, Raaz Dwivedi, Martin J Wainwright, and Bin Yu. Fast meme sampling algorithms on polytopes. Journal of Machine Learning Research, 19(55):1-88 2018.
[CLM+15] Michael B Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform sampling for matrix approximation. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 181-190 2015.
[CLS19] Michael Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs the current matrix multiplication time. In STOC, 2019.
[CW13] Kenneth L. Clarkson and David P. Woodruff. Low rank approximation and regression in input sparsity time. In Symposium on Theory of Computing Conference (STOC), pages 81-90, 2013.
[Dav06] Timothy A Davis. Direct methods for sparse linear systems. SIAM, 2006.
[DLS23] Yichuan Deng, Zhihang Li, and Zhao Song. Attention scheme inspired softmax regression. arXiv preprint arX1vv2304.10411, 2023.
[DSW22] Yichuan Deng, Zhao Song, and Omri Weinstein. Discrepancy minimization in input- sparsity time. arXiv preprint arXiv:2210.12444 2022.
[DWZ22] Ran Duan, Hongxun Wu, and Renfei Zhou. Faster matrix multiplication via asymmetric hashing. arXiv preprint arXiv:2210. 10173, 2022.
[FLS+18] Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, Michat Pilipczuk, and Marcin Wrochna. Fully polynomial-tine parameterized computations for graphs and matrices of low treewidth. ACM Transactions on Algorithms (TALG), 14(3):1-45, 2018.
[GN23] Adam Gustafson and Hariharan Narayanan. John's 's walk. Advances in Applied Proba- bility, 55(2):473 491, 2023.
[GS22] Yuzhou Gu and Zhao Song. A faster small treewidth sdp solver. arXiv preprint arXiv:2211.0603. 2022.
[GSY23] Yeqi Gao, Zhao Song, and Junze Yin. An iterative algorithm for rescaled hyperbolic functions regression. arXiv preprint arXiv:2305. 00660, 2023.
[GSZ23] Yuzhou Gu, Zhao Song, and Lichen Zhang. A nearly- time algorithm for struc- tured support vector machines. arXiv preprini urXiv:2307.07733. 2023.
[HJS+22] 22] Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, and Ruizhe Zhang. Solving sdp faster: A robust ipm framework and efficient implementation. In 2022 IEEE 63rd Anmual Symposium on Foundations of Computer Science (FOCS), pages 233-244. IEEE, 2022.
[[K6 Elad Hazan and Zohar Karnin. Volumetric spanners: an efficient exploration basis for learning. Journal of Machine Learning Research, 2016.
[HSWZ22] Hang Hu, Zhao Song, Omri Weinstein, and Danyang Zhuo Training overparametrized neural networks in sublinear time. In arXiv preprint arXiv: 2208.04508 2022.
[JK++ Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. A faster interior point method for semidefinite programming. In 2020 IEEE 61st annual symposium on foundations of computer science (FOCS), pages 910-918. IEEE, 2020.
[Joh48] Fritz John. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented R. Courant on his 60th Birthday, January 8, 1948, pages 187-204. Interscience Publishers, Inc., New York, N. Y., 1948.
12

---

[JSWZ21] Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang. A faster algorithm for solving general Ips. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 823-832, New York, NY, USA, 2021. Association for Computing Machinery.
[Kha96] I Leonid G Khachiyan. Rounding of polytopes in the real number model of computation. Mathematics of Operations Research, 21(2):30--320, 1996.
[KKMR22] Jonathan A Kelner, Frederic Koehler, Raghu Meka, and Dhruv Rohatgi. On the power of preconditioning in sparse linear regression. 202/ IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 550-561. IEFF, 2022.
[KT93] IG Khachiyan and MJ Todd. On the complexity of approximating the maximal inscribed ellipsoid for polytope. Mathematical Programming, 61(1-3):137-15, 1993.
[KY05] Piyush Kumar and E Alper Yildirim. Minimum-volume enclosing ellipsoids and core sets. Journal of Optimization Theory and Applications, 126(1):1-21, 2005.
[LFN18] Haihao Lu, Robert M Freund, and Yurii Nesterov. Relatively smooth convex opti- mization by first-order methods, and applications. SIAM Journal on Optimization, 28( 28(1):333-335 354, 2018.
[LG114] François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th international symposium symbolic and algebraic computation, pages 296-303, 2014.
[LMS13] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis. Bulletin of EATCS, 3(105), 2013.
[LS14] Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in O O(yrank) iterations and faster algorithms for maximum flow. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 424-433. IEEE, 2014.
[LSZ19] Yin Tat Lee, Zhao Song, and Qiuyi Zhang. Solving empirical risk minimization in the current matrix multiplication time. In Conference on Learning Theory, pages 2150-2157. PMLR, 2019.
[LSZ+20] S Cliff Liu, Zhao Song, Hengjie Zhang, Lichen Zhang, and Tianyi Zhou. Space-efficient interior point method, with applications linear programming and maximum weight bipartite matching. arXiv e-prints, pages arXiv-2009, 2020.
[LS723] Zhihang Li, Zhao Song, and Tianyi Zhou. Solving regularized exp, cosh and sinh regression problems. arXiv preprint arXiv:2303. 15725, 2023.
[LYZ05] Erwin Lutwak, Deane Yang, and Gaoyong Zhang. John ellipsoids. Proceedings of the London Mathematical Society, 90(2):4975520, 2005.
[MM022] Yury Makarychev, Naren Sarayu Manoj, and Max Ovsiankin. Streaming algorithms for ellipsoidal approximation of convex polytopes. In Conference on Learning Theory, pages 3070-3093. PMLR, 2022.
[MSJ19] Silviu Maniu, Pierre Senellart, and Suraj Jog. An experimental study of the treewidth of real-world graph data. In ICDT 2019-22nd International Conference on Databuse Theory, page 18, 2019.
[Nem99] Arkadi Nemirovski. On self-concordant convex-coneave functions. Optimization Methods and Software, 11(1-4)3303-884 1999.
[NN94] Yurii Nesterov and Arkadii Nemirovskii. Interior-point polynomial algorithms in convex programming, volume 13. Siam, 1994.
13

---

[NN13] Jelani Nelson and Huy L Nguyên. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2013.
[NTZ13] Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 351-360. ACM, 2013.
[Puk06] Friedrich Pukelsheim. Optimal design of experiments. SIAM. 2006.
[QSZZ23] Lianke Qin, Zhao Song, Lichen Zhang, and Danyang Zhuo An online and unified algorithm for projection matrix vector multiplication with application to empirical risk minimization. In International Conference on Artificial Intelligence and Statistics, pages 101-156. PMLR, 2023.
[RSW16] Ilya Razenshteyn, Zhao Song, and David P. Woodruff. Weighted low rank approxi- mations with provable guarantees. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC 16, page 250-263, 2016.
[SF04] Peng Sun and Robert M Freund. Computation of minimum-volume covering ellipsoids. Operations Research, 52(5):690-706, 2004.
[SS11] Daniel A Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6): 2011.
[SWYZ21] Zhao Song, David P. Woodruff, Zheng Yu, and Lichen Zhang, Fast sketching of polynomial kernels of polynomial degree. In International Conference on Machine Learning (ICML), pages 9812 9823. PMLR, 2021.
[SWZ17] Zhao Song. David P Woodruff, and Peilin Zhong. Low rank approximation with entrywise & norm error. In Proceedings of the 49th Annual Symposium on the Theory of Computing (STOC), 2017.
[SWZ19] Zhao Song, David P Woodruff, and Peilin Zhong. Relative error tensor low rank approximation. In SODA. arXiv preprint arXiv:1704.000 1704.0824,, 2019.
[SXYZ22] Zhao Song, Zhaozhuo Xu, Yuanyuan Yang, and Lichen Zhang. Accelerating frank- wolfe algorithm using diw-dimesiional and adaptive data structures. arXiv preprint 3Xxi:2200.00000. 2022.
[SXZ22] Zhao Song, Zhaozhuo Xu, and Lichen Zhang. Speeding up sparsification with inner product search data structures. 2022.
[SY21] Zhao Song and Zheng Yu. Oblivious sketching based central path method for linear programming. In International Conference on Machine Learning, pages 9835-9847. PMLR, 2021.
[SYYZ23] Zhao Song, Xin Yang, Yuanyuan Yang, and Lichen Zhang. Sketching meets differential privacy: Fast algorithm for dynamic kronecker projection maintenance. In ICMI,, 2023.
[SZ23] Zhao Song and Tianyi Zhou. Faster sinkhorn's 's algorithm with small treewidth. arXiv preprint arXiv:2301.06744 2023.
[LY224] Yukai Tang, Jean-Bernan Lasserre, and Heng Yang. Uncertainty quantification of set- membership estimation in control and perception: Revisiting the minimum enclosing ellipsoid. In 6th Annual Learning for Dynamics & Control Conference, pages 286-298. PMLR, 2024.
[Tod16] Michael J Todd. Minimum-volume ellipsoids: Theory and algorithms. SIAM, 2016.
[Trol1] Joel Tropp. Improved analysis of the subsampled randomized hadamard transform. Advances in Adaptive Data Analysis, 3:115-126, 2011.
14

---

[TY07] Michael J Todd and E Alper Yikdirim. On khachiyan's 's algorithm for the computation of minimum-volume enclosing ellipsoids. Discrete Applied Mathematics, 155(13):1731- 1744, 2007.
[Vem05] Santosh Vempala. Geometric random walks: survey. In Combinatorial and compula- tional geometry, volume 52 of Math. Sci. Res. Inst. Publ., pages 577-616. Cambridge Univ. Press, Cambridge, 2005.
[Wil12] Virginia Vassilevska Williams. Multiplying matrices faster than goppersmith-winggee In Proceedings of the forty-fourth annual ACM symposium on Theory of computing (STOC), pages 887-898. ACM, 2012.
[WYS17] Yining Wang, Adams Wei Yu, and Aarti Singh. On computationally tractable selection of experiments in meeaureeeent-constrainee regression models. Journal of Machine Learning Research, 18(143):1 41, 2017.
[XZZ18] Chang Xiao, Peilin Zhong, and Changxi Zheng. Bourgan: generative networks with metric embeddings. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (NeurIPS), pages 2275-2286, 2018.
[Zha22] Lichen Zhang. Speeding up optimizations via data structures: Faster search, sample and maintenance. Master's thesis, Carnegie Mellon University, 2022.
[Zha23] Richard Y Zhang. Parameterized complexity of chordal conversion for sparse semidefi- nite programs with small treewidth. arXiv preprint arXiv:2306. 15288, 2023.
[ZL21] Richard Y Zhang and Javad Lavaei. Sparse semidefinite programs with guaranteed near- linear time complexity via dualized clique tree conversion. Mathematical programming. 188:351-393, 2021.
[ZMST10] Ray Daniel Zimmerman, Carlos Edmundo Murillo-Sánchez, and Robert John Thomas. Matpower: Steady-state operations, planning, and analysis tools for power systems research and education. JEEE Transactions power systems, 26(1):12-19, 2010.
15

---

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: The abstract and introduction clearly state the claims made, including the contributions made in the paper and important assumptions and limitations.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We include the limitation discussion in Section H.
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 on 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]
16

---

Justification: All assumptions of this work are made within the statement of theorems or lemmas. For each theoretical result:
The formal version of Lemma 4.2 is Lemma F.4, where the proof is in Section F.
The formal version of Lemma 4.3 is Lemma E.4, where the proof is in Section E.
The formal version of Lemma 5.1 is Lemma D.1, where the proof is in Section D.
The formal version of Lemma 5.2 is Lemma E.3, where the proof is in Section E.
The formal version of Theorem 5.3 is Theorem E. where the proof is in Section E.
The proof of Theorem 5.4 is in Section 5.
The formal version of Theorem 6.1 is Theorem G.4, where the proof is in Section G.
The formal version of Theorem 6.2 Theorem G.2 where the proof in Section G. 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 referenced in the statement of any theorems. The proofs 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 short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main 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 not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 a specific model and empirical evaluation, it may be necessary to either make it 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 to accomplish this, but reproducibility 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, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS 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 the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution 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).
17

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe 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., to 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?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips.co
public/guides, /owiidde///odeuumissssiii wwtpamiissssooloiiiiiiooo mmPolcy) iyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nniss. wttpccccppcccc/ecc.ccc.ccccccttt /gguides////eeeeeer
for more details.
The authors should provide instructions on data access and preparation, including how to 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. 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 much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is 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 understand the results?
Answer: [NA]
Justification:
The paper does not include experiments.
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, 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: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
18

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to 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.
It is OK to report 1-sigma error bars, but 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 errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures 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 reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //tp:://///////////ee http://uurrrsscccppuboeeee cccpublic//eieeceeeeeecceeeeeeee Ceeeiii//iiieeeee csQuidel ines?
Answer: [Yes]
Justification: All authors have reviewed and confirmed that the research conducted in the paper conforms, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We include the broader impacts discussion in Section I.
19

---

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 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 partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to 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.
If there are negative societal 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 system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments and poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual- 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question:
Are the creators or 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?
Answer: [NA]
Justification:
The paper does not use existing assets.
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 or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
20

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms 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 it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is 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 participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS 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 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
21

---

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 we expect authors to adhere to 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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: / //neruurpp.... wcc//onfeeeecce/222//11111 for what should or should not be described.
22

---

Appendix
Roadmap. In Section A, in list some related work. In Section B, we provide some simple algebra fact. In Section C, we introduce some tools from previous work. In Section D, we give the remaining detailed proof of running time in Theorem 5.1. In Section E, we give a lemma that helps the correctness proof. In Section G, we present faster algorithm to solve the John Ellipsoid problem with small treewidth setting. In Section F, we provide the sparsification tool used in analysis of Algorithm
A Related Works
Fast John Ellipsoid Computation There is a rich body of research on efficient algorithms for computing the John Ellipsoid. The interior point algorithm by [NN94] computes the John Ellipsoid in O((n3. + dd2 log(n/e)) time. [KT93] improved this to On log(n/e) ( log(d/c)). Subse- quently, [Nem99, Ans02] developed algorithms with a time complexity of O(n (o)((/))).... The best algorithm based on convex optimization solvers, developed by Y05 TY07J, runs in O(E I time. More recently, the fixed-point iteration method by [CCLY19] achieves a time complexity of ndf)) For a comprehensive survey of John Ellipsoid computation, we refer readers to [TTdd16].
Leverage score sampling Applying a sampling matrix for efficiency a quite standard way in the field of numerical linear algebra (see (CW13, BWZ16, RSWIG 16, SWZ17, SWZ19, CLS19, BLSS20, DSW22, DLS23, LSZ23, GSY23)). In our paper, we use leverage score sampling as a non-oblivious dimension reduction technique, similarly in [SS11, BSS12, SXZ22, Zha22).
Sketching Sketching a powerful technique used in many other fundamental problems such as linear programming [JSWZ21, SY21], empirical risk minimization [LSZZ99, QSZZ23], semi-definite programming 2J0 HJS+ SYYZ23J. Moreover, it a popular technique in randomized linear algebra and has been widely applied in a lot of linear algebra tasks [CW13, NNI3, BWZ16, RSW 16, SWZ17, X SWZ19, LSZ19, JSW211, SY21, BPSW21, HSWZ22, SXYZ22, GS22, SWYZ21]. Sketching is widely applied in oblivious way dimension reduetion technique [CW13 13, NN13]. For approximate John-Ellin Ellipsoid methods, prior work (CCLY 19] 19] uses the sketching method alone, providing the potential for further optimization. [MMO22] also studied ellipsoidal approximation given a convex polytope characterized in the form of a data stream. Their problem more challenging, and their solution is not optimal in our setting.
Treewidth Setting Since the introduction treewidth as concept, extensive work has optimized various problems based on it. More recently, [KKMR22, GS22, GSZ23, Zha23, BGdMT23] associate treewidth with linear program solvers and enhance the efficiency of the optimization beyond matrix sparsity.
B Basic Tools
provide basic algebra claim that used in our paper.
Fact B.1. Given vector w, it holds that A diag(w)A = Ei_ wra,a, where a; is the i-th column of A.
Proof. We have,
AT diag(w) = [lian W202, ... -.,,, Wnan]
Then the æ, element for A diag(w) is Σ u. Hence, AT diag(w) Ei_ ua
We introduce some facts that are useful to our proof.
Fact B.2. For any real numbers 2 and 2 2, we have
log(ab) 2a log b
23

---

Proof. We have
log(ab)
v log + log
S a + log b
S a log b log b
1 a log + a log
S 2a logb.
where the third step follows from log b 2 1, the forth step follows from a 1.
Thus, we complete the proof.
Fact B.3. For any a 2 and b 2, we have
+ log(ab) S 3a log b
Proof. Using Fact B.2, we have
log(ab) S 2u log
Then we have
log(ab) S + 2a log b s 3a log where the last step follows from a S log b.
Fact B.4. For any n, d such that 2 S d S S poly(d). For any d (0,0.1), have
log(d (gg/d/ogg//d)//)) = O(log(((o)))))))
Proof. Let c
denote some constant value such that - dc.
Then write
dlog(n/d) s dlog(d" = (c- l)d d
S ed d
S ed2
where the first step follows from S ds, and the last step follows from log d S d.
Thus
s log(ed c/d /6)
< 2c log(do (d2//)
< 2c log( /22)2)
4c log(d/5)
(llogdd/)).
where the second step follows from Fact B.2, the third step follows from 5 E (0, 1).
C Tools From Previous Works
We provide bounding expectation in Section C. and show the convexity in Section C.2.
C.1 Bounding expectation
Lemma C.1 (Implicitly Lemma C.5 and Lemma C.6 arXiv² version of [CCLY19]). If s even,
define );(wx) = log We.s then we have
2 E[A(ww))]
[((())((<((x))))) S( 11 (1+
2a
)r
sT - 2a
where the randomness is taken the sketching matrices Pnttps://arxte http:///aawwwwoo///////////e//// 11580. .pff
{5(()) T-1
lk=1.

---

C.2 Convexity
Here, we show the convexity of Φ;.
Lemma C.2 (Convexity, Lemma 3,4 in arXiv [CCLY19]), For -. ,.,,,,,, let Øz : RR" - R be the function defined as
(b(1) log (g) log(a,
uyaga))
Then dh convex.
D Proofs of Running Time of Input-Sparsity Algorithm
Lemma D.1 (Performance of Algorithm 2, formal version of Lemma 5.1). Given symmetric convex
polytope, for all (0, 1). Algorithm 2 can find (e)+ee))pppppp aaproxximation of John Ellipsoid inside this polytope with = (e)) and T O(e llognn/))
/d) ) in time
O((c~)oog log(d/8) -mn((A) + log(n/8) d=) (T))),
where 2.37 denote the current matrix multiplication exponent (Wil12, LG14, AW21, DWZ22, ADW+ 24].
Proof. At first, initializing the vector w R" takes O(n) time. In the main loop, the per iteration running time can be decomposed as follows:
Calculating matrix B& E Rxxd takes ((nnz(A)) time. Due to the structure of matrix Wi. we only need multiply the non-zero entries of i-th row by wk, get matrix Bg. The total non-zero entries here is nnz(A).
Initializing matrix S₁ Rexd, where O takes Onn-'n) time.
Generating diagonal matrix DR E RR takes ( + )))) time by using Lemma 2.3.
Computing matrix H. (B Da contains three steps.
We first compute B3 DB E 1ddd where Dy a diagonal matrix with N non-zero entries and N ( 'd llloo(d/)))) takes O dd= log(nd/8)) time by using fast matrix multiplication. As n = poly(d), dd), we can simplify it as
O 2d log(n/5))
Second, we compute the inverse of the result in the first step, which takes (dd)) time Third, we take the square root of the result in second step. To take square root of matrix T E Raxd we can first decompose T as UEV using SVD, which takes Odd)). Then we take the square root of the diagonal matrix Σ, which takes O(d). Then, we multiply them back together to get T1/2, which takes O(d"). Hence, the time needed for the final step is
Old)) + O + O(d") = O(d")
As (ad)) is less than O d log(n/5)), the total running time for computing Hg is O dd log(n/8)).
Computing matrix Q takes O time.
Updating vector w1+1 takes O umz(A)) time. We need O( nnz(a;)) time for each iteration to compute & /wk /w Hence to update vector wk++1 we need
Σ O nnz(a;)) O mnz((A)
time.
25

---

In summary, the overall per iteration running time for the main loop is
O(E log(d/o) nnz(A) + e llo(n/00) d²)
where
6 dc 6 = (1) and 60 T log(n/d)
Hence, with 6, (1) and 6g &
de log(n/d)
the overall per iteration running time for the main
loop is
O(unz(A)) + +0 Ō(E (nnz A) + d + (og())))) +0 O(E "nnz(A))
O(e-'nnz(A))
= = + )²)) + 0 dt log(m/ 0(
mnz(A))
log + -0s (A) d²) log (/ + 0 ( (n)( O((E² log(d/ (d),))))))))))))) ) nnz A) (5 - log / + log( n1 ( + +(-)
O(log(d)) b6) + + nnz (A) (log(d d/ c (og(n/0)) / dd
where the first step comes from (mz(A) n and nnz(A) > d, the second step follows from the definition of O, the third step follows from reorganization, the fourth step follows from 6, (
Note that without loss of generality, we can assume 2 < d S S poly(d). For convenient of the simplifying complexity related to logs, we can assume n 2 2d and 6 (0,0.1) and E (0, 0.1).
We try to further simplify log(d/6>) + E- using the definition of 8, / have
log(n/aj then
be
dlog(n//)
log(d/6.) + = logg
+ +
de
10 d dlog(n/d)
O(c log(d/)
where the first step follows from definition of 8g the second step follows from Fact B.3 and the last step follows from Fact B.4.
Hence yields the total running time for the main loop as
(og(d/) nnz(A) + (log(d/(6c)) + + lo2lon(n/))) d= +c-..d0
Then, computing the average of vector w from time 1 to T' and computing the vector vj takes O(nl)
time. Finally, note that don't have to output A V.A. Instead, we can just output A and vector v, which takes (nn) time.
Therefore, by calculation, the running time of Algorithm 2 is:
O((E - (og((/)) mnz(A) + (log(d/(6e)) + c log(n/0)) d -t.1..8m
= O((c Log(d/}) mnz(A) + (log(d/(6e)) + (n))))/)) - d))
-(((e (o/()))) muz( A) + e -2 log(nn////// dT)
where the first step comes from co (c) and 2 2, and the last step follows from d and
E (0, 1). Note that w denotes the exponent matrix multiplication [Wil12, LG14, AW21]. O
E Proofs Of Correctness of Input-Sparsity Algorithm
In Section E. we show that Algorithm 2 gives reasonable approximation of the John Ellipsoid. In Section F.2, we provide the bound of X; In Section E.3, we provide the formal version of telescoping. In Section E.4, we give the upper bound of o;.
26

---

E.1 Main Result
Theorem E.1 (Correctness, restatement of Theorem 5.3). Let cu 1000 Let R be the outpu of Algorithm 2. For all E (0, 1), when T O( log(n/d)), we have
Pr [o( S (1 + +e) v [m]] 2 1 8 - 60
Moreover,
Σ 22 d.
Therefore, Algorithm 2 provides (1 + approxiiiinnnnn to program Eq. (2)
Proof. We set
1000 log(n/d) and 6n = e/1000,
By Lemma E.4, know the succeed probability is 8 du. Then, have for i [m],
log (u) du(u)
log(n/d) + e/250
50
log +)
where the first step uses the definition of d; the second step uses Lemma 4.3, the third step comes from calculation, and the last step comes from the fact that when < c < 1, 50 I log(1 + c).
In conclusion, (u) S c
Because, we choose 1; = Σ u5 U4 then D U; d.
Next, we have
02(0) = = (A(A (TTV) -ta,
d
= a Σ us
A AUA))-
Ei= "i oo((u)
d
< <1+c)
$ (1 + (1+c)
where the first step uses the definition of oz (v), the second step uses the definition of V, the third step uses the definition of a; (u), the fourth step comes from u; is at most (1 + e) true leverage score, and the summation of true leverage scores is (by Lemma 2.2), the last step comes from a,(n) S (1 +
Thus, we complete the proof.
E.2 High Probability Bound A;
We provide high probability bound of X; as follows.
Lemma E.2 (High probability Argument on \s(w)). Let (u(w) log
Tr. wa,s
Then we have
(r(e 2 21 (1 c)
Moreover, with our choice of 8, T, with large enough n and d, we have:
Pr(oxp(>((w)) 2 21+d n
27

---

Proof. In the proof, we pick 2 log 5'
By the choice of a, we have that:
log(n/5)
2 log I++/4
(5)
1+c
sT 2 4a
(6)
Then, E [r], by Markov Inequality on the a moment of exp(A:(w))) we have that:
Pr(exp(A((w)) 2 1 + Pr(e)p(><(1o)) 2 (1 c)a
(lexp();(w))()
(1 c)a
(2) (1+ + -T-2a yT
61+
20 7 (g)* (1+
xT/2
(1+c)a
r f
(1 + c)a
where the first step comes from calculation, the second step comes from Markov Inequality, the third step comes from applying Lemma C.I, the fourth step comes from the choice of a that sT 2 4a, and the final step comes from
e".
Moreover, for large enough and d, we have that:
2 = 7 log(na
S $1+
(7)
Also, we have:
e = 2 $ 11+0/10
(8)
Hence,
(1 + c/10)2
Pr(exp(A((w)) 2 21+ <
)
1
+ e/4
)a
1+e
where the first step comes from applying Eq (7) and Eq. (8), the second step comes from calculation, and the last step comes from Eq. (5).
E.3 Proof of Lemma 5.2
Lemma E.3 (Telescoping, Algorithm 2, restatement of Lemma 5.2). Fix T the number of main loops executed in Algorithm 2. Let E IR" denote the iteration-averaged vector computed in Algorithm 2, where T Etm Wk.i. Then for i E [n], with probability 80.
dc(u) S T
1
n1 log
1
log
Wk.i + 60 Wk
d
T
Proof. We define
= (u1. U2
un) E R..
For k 1,... T define
== (Wk,1,'" W...) E R
28

---

and
0x+1 = (wk.1 -I(ww),, " Wh on (wx))
By the convexity of de (Lemma C.2)
(.(1) 0. 1
Σ wk)
T
(uw)
log (wwx))
T
01++11
log
T
Wkii
T
1K+1,
Wk.s Wh.
log
T
Tk,d Thi Wk,
T
#x+1.1
Whii
Whii
log
log
log
T
Wket
Wkii
Wkk
k=1
k=1
#T+11
1
log ikk
log
log(
+
T
11,
T
Wk.
Wk.
1
nWT+1
1
Wkes
Wk.
log
log(
+
log
T
T
Wk.s
T
Wk.
1=1
k=1
1 T
1
n
Wk.i
Wk.i
log
+
log(
log
T
d
T k=1
Wk.i
T
Wk.i
T
< T
log a
+ log(1 + co) +
log
Wk.i
d
Wk.i
T
< 7 log 7 7 + +
log
where the first step uses the definition of u. the second step uses the convexity of é;, the third step uses the definition o; the fourth step uses the definition of a, the fifth step comes from reorganization. the sixth step comes from reorganization, the seventh step comes from reorganization, the eighth step uses our initialization on W1, the ninth step comes from Lemma 2.2, the tenth step uses Corollary F.5, and the final step comes from the fact log(1 1 cu) S Cu-
Note that, the tenth step only holds with probability on. which gives us the high probability argument in the lemma statement.
E.4
Upper Bound of Φ;
Then, show the upper bound of di.
Lemma E,4 (0s, formal version of Lemma 4.3). Let u be the vector generated during the Algorithmn 2, fix the number of iterations executed in the algorithm as T and s 1000/e, with 1 5g we have
1
dr(u) $ log( + c/250 + co Vi [n].
)
29

---

Proof. To begin with, by Lemma 5.2, we have that, with probability - 80.
1
n
Wke
0:(1) S
log
log
+060
T
d
T
Wk.i
T
1
n
1
log
+
(2 ED
T
d
T
km1
We have with probability 8 -0. for all [n]:
Φu(u) -
log 1000 + 60
T
log
+
T
250
where the first step follows from Lemma E.2.
Sampling
In this section, provide the sparsification tool used in Line 7 of Algorithm 2. Especially, we show how to approximate the matrix that has pattern A W A, where W some non-negative diagonal matrix, by using sample matrix D.
Lemma F.1 (Matrix Chernoff Bound [Trol Let X,...., & be i.i.d. symmetric random matrices with E[X,] O. || almost surely and [[]] xill I 0². Let CerC= = : -Ee(()) X,. For any
e E (0, 1), holds that
sc
Pr[[[C|| 2 c) 2d exp
(- 02 7e/3)
To better monitor the whole process, is useful to write H(w) as A W A, where A E Raxd the constraint matrix and W is diagonal matrix with W diag( w)) The sparsification process is then sample the rows from the matrix A.A
We define the leverage score as follows: Definition F.2. Let B E RRxd be full rank matrix. We define the leverage score of the i-th of B as
o, (B = b. (B B) B)-
where b, is the i-th row B.
Next we define our sampling process as follows:
Definition F.3 (Sampling process). For any w E K, les (w) A.W. Letp, 2 B--..oolll o.(VWWW)
suppose we sample with replacement independently for rows of matrix vW A, with probability pi of sampling row for some 3 2 Let i(j) denote the index of the row sampled in the j-th trial. Define the generated sampling matrix as
1 (3)))
(ww)= =
P((
For our sampling process defined Definition F.3, we can have the following guarantees: Lemma F.4 (Sampling using Matrix Chernoff, formal version of Lemma 4.2), Let ca, do (0,1) be the precision and failure probability parameters, respectively. Suppose H(w) is generated as in Definition E3, then with probability at least 8g. we have
(1 (1-6)) t0) H(w) 3 Hw) 3 (1+ H(w).
Moreover, the number of rows sampled is
@ Eg 2d loog(d) (o)))
30

---

Proof. The proof follows from the high level idea of Lemma 5.2 in [DSW22] by designing the family of random matrices X. Let
= (A WA)
1/2 1/2 1,4 a2
be the i-th sampled row and set Y; = - y.y
Using (ww) A W A, we can write
y1
04-
Let X; Yi La Note that
T Vc
Σ
(ww) a;a, (ww)-1/
i=1
((w) - 1/2
Wi, [ [H(w)
1=1
(12 W (W)
Ig-
(9)
where the first step uses the definition of yt. the second step comes from reorganization, the third step comes from Fact B. and the last step uses the definition of Hww).
Also, the norm of y, connects directly to the leverage score:
11 vW, W (A W 1;;;;
= (v(W
(10)
We use i(j) to denote the index of row that has been sampled during j-th trial.
We first show that [ 0. Note that
E[X]
E[y]
Is
1
Σ
pt
u.y!
La
1=1 p.
0.
where the first step uses the definition of the second step uses the definition of Y and the definition of expectation, and the last step uses Eq. (9).
Now, bound |||||, we provide bound for any || |X,]| ||
follows
||
|| Iall
$ 1 + ||
|a II
Pi
d- 11::113
3 0 (vVVA
d
3'
where the first step uses the definition of X,, the second step uses triangle inequality and the definition of Ta. the third step uses the definition of Yú, the fourth step comes from pt 2 3- (.-ov(WWWW A)/d and the definition of & norm and the last step comes from Eq. (10).
31

---

Then we bound|
E[ X]| as follows.
E|X x]
Elaal + EE Y| - 1E[
n
yi y.y.y!
n
la +
pi
ps
ps
i=1
0i WWWY A)
Is +
V:Vl )
2I
Pi
(ml 3 Dili
la
3 1)la.
where the first step uses definition of X, the second step uses the definition of Y and the definition of expectation, the third step follows from Eq. (9), Eq. (10) and the definition of expectation, the third step comes from p; 2 8 (v(vW A)/d. and the last step comes from Eq. (9) and distributive property.
The spectral norm is then
d X]|
E[X
1.
13
Putting everything together, we choose
d 3
0²
and then we apply Matrix Chernoff Bound in Lemma F.l:
Pr[[[C] 2 eol
Se
< 2d . exp
1133114 1+ (1 + d/ d/
2d exp( exp(-se) (((/d))
50
where we choose 0(3 c 2 dl log (og((//j)) d/66)).
Finally, we can show that
C Vio))aay La)
j=1 Pi())
1
H(w) 112
( (Ww) la
Pi()
H(w) 11/ (w) H H(w) (ww) Ia-
where the first step uses the definition C, the second step uses the definition of Bı(s)- and the last step uses the definition of H (w).
Therefore, we can conclude the desired result via ||C 2 Eg.
Corollary F.5. Let to denote the parameter defined as Algorithm 2. Then we have with probubility 1-80
(1 (-6)) W. < w. < (1 + co)
for all i E [n].
32

---

h
c.f.c
e,h
a.b,c
c.d.f
f.i.g
(b)
Figure 3: (a) A graph G(V, E) (b) The tree decomposition for graph G. We can see that the union of the vertices in all bags are nodes o.... i, which the same as V(G). For every edge u, VG)). we can find at least one bag containing u and v. For example, for edge (c. b) in graph G. bag 1 contains both e and b. Furthermore, the bags containing any one node in (a) subgraph of tree (b). For example, the bags containing node are bags 1, 1,2,3 3, which is subgraph of the tree. Similarly, we can see that the bags containing node bags 3, 5, which also a subgraph of the tree. For edge (c, f), bag? 2 and 3 both contain vertices e and f. For edge (i, g), bag 5 contains vertices i and
Proof. Since if
BL
then for all æ, we know
(0) Az < x Bæ S + co) x² Ar.
Thus, using lemma (Lemma F.4) implies the weights guarantees.
G Small Treewidth Setting
In this section, we provide an algorithm (Algorithm 3) that approximate the John Ellipsoid in O (nr²²) log(n/d) time with small treewidth setting. In Section G.I, we prove the correctness of our implementation. In Section G.2, we show the running time of it.
G.1 Correctness
Note that for Algorithm 3, compute the exact leverage score of each row, the randomness of sketching matrix and diagonal sampling D doesn't play a role our analysis. It immediately follows that the following corollary holds:
Corollary G.1 (Telescoping, Algorithm 3). Fix T as the number of main loops executed in Al- gorithm 3. Let u gn denote the iteration-average vector computed in Algorithm 3, where W4 + Σk= Wk.5. Then for E [n],
(u( T log
Next, we prove the correctness of our implementation with small treewidth setting,
Theorem G.2 (Correctness of Algorithm 3, formal version of Theorem 6.2), Let be the output of Algorithm 3. For all E (0, 1), when O(e log(n/d)) /dd), we have:
(;(u) < cc)
Σ M4
Proof. We set
1000 log(n//)
We also have for E [n],
log (u) (2)
33

---

(a)
(b)
Figure 4: (a) A 10 10 positive definite matrix P AAT, where the blue dot represent the non-zero elements in P. (b) The Cholesky factor L of AAT. (c) The corresponding elimination tree for matrix P. where each node represent one column in the Cholesky factor. We can see that, the row index of the first subdiagonal nonzero entry of the 6-th column is 8, the parent of node 6 is 8. Furthermore, the non-zero pattern of this coloumn (6, 8, 10), which is subset of vertices on the path from node 6 to the root in the elimination tree.
T log(n/d)
50
log(1 +)
where the first step uses the definition of (u)), , the second step follows from Corollary G.1, the third step follows from calculation, and the last step follows from the fact that for small e, e e/50 S log(1 +c).
In conclusion, (u) < 1 + 6.
Additionally, since for [2]. each row of wkei a leverage score of some matrix, according to Lemma 2.2, we have:
T
Wke
1=1
i=1
k=
Wk.t
T
1
Σ
T k=
1
T Td
where the first line the definition of u, the second step follows from reorganization, the third step follows from Lemma 2.2, the fourth and the final step comes from calculation.
Thus, complete the proof.
G.2 Running Time
The rest of this section is prove the running time of Algorithm 3. We first show the time needed to compute the leverage score with small treewidth setting.
Lemma G.3. Given the Cholesky factorization LL Let a. denote the i-th row of f. each i [n]]
Let B VHA guxd where H nonnegative diagonal matrix. Let o, 6, (BT -)- We can compute I in O(nr2) time.
Proof. Let LL = BTB B be Cholesky factorization decomposition. Then, we have
6. (B B) B1 b. -L-T--1 b.
34

---

= (L
(L (L))
Using the property of elimination tree, we have each row B has sparsity r and they lie on a path of elimination tree T. In this light, able to output b, in O(72) time, and then compute solution of sparsity ((T).
Therefore, can compute the score for a single column in 0(72). In total, it takes O(nr²).
Next, we show our main result.
Theorem G.4 (Performance of Algorithm formal version of Theorem 6.1). For all E (0, 1), we can find (1 + appproxiimttoon of John Ellipsoid defined by matrix A with treewidth T inside symmetric convex polytope in time ((n+2) T) where cl lol(g///
Proof. At first, initializing the vector w takes (n) time. In the main loop, the per iteration running time can be decomposed as follows:
Using Lemma 2.7, calculating the Cholesky decomposition for B Bg takes O time.
Using Lemma G.3, computing Wk+1 takes O(nr²) time.
Hence, the overall per iteration running time for the main loop is O time, hence yields the total running time for the main loop as ((nr))TT)
Then, computing the average of vector w from time 1 to T,, and computing the vector v; takes O(n)) time. Finally. note that we don't 't have to output A VVA. VA. Instead, we can just output A and vector which takes ((n) time.
Therefore, by calculation, the running time of Algorithm 3 is: (((r2)7)) Thus, we complete the proof.
H Limitations
While our findings primarily revolve around algorithmic advancements, we also see potential in exploring matching lower bound for this problem in future research.
I
Impact Statement
Our paper introduces research aimed at advancing the area of Machine Learning and Optimization. While there are numerous societal implications associated with our research, we believe none require particular emphasis in this context. We propose two algorithms that solve the John Ellipsoid problem more efficiently. We hope our work can inspire effective algorithm design and promote a better understanding of John Ellipsoid problem and the D-optimal design problem. Since this is theoretical paper, we do not foresee any potential negative societal impact.
35


Reviews:
[{"review_id": "In6vQQM6Ec", "reviewer": "Reviewer_mXV8", "summary": "Computing the John ellipsoid of a convex set is a classical and computationally challenging problem in computer science. In certain cases where the convex bodies exhibit additional structure, more efficient algorithms are known. This paper focuses on the setting where the convex body is a convex and centrally symmetric polytope, and proposes efficient algorithms that refine the approach of CCLY’19. The key idea is to extend the simple fixed-point iteration scheme of CCLY’19 under either of two structural assumptions: (i) when the matrix defining the convex and centrally symmetric polytope is sparse, and (ii) when its dual graph has small treewidth.", "questions": "Could the authors provide concrete examples of practical problems in which the computation of the John ellipsoid is relevant and the defining matrix of the convex and centrally symmetric polytope is naturally sparse?", "limitations": "Limitations appropriately addressed. NA for societal impacts", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths and Weaknesses:\n\nOverall, I find the presented results interesting and relevant within the literature on John ellipsoid computation. The required techniques are sufficiently novel, and, if I understand correctly, the assumption that the convex set is a centrally symmetric polytope is not overly restrictive and can have meaningful practical applications.\n\n\nThe quality of the results themselves appears adequate. The paper provides appropriate approximation guarantees and runtime analyses. I briefly reviewed some of the proofs, and they appear reasonable.\n\n\nMy primary concerns, however, relate to the quality of the presentation. The manuscript contains numerous confusing or unnatural passages, repeated definitions (for example, the paragraph beginning at line 234), as well as undefined terms (such as $n_i$​ in the definition of the dual graph). Additionally, there are many punctuation errors and typographical mistakes throughout the text, which may be artifacts of extensive rewriting or abbreviation. Furthermore, the main body of the text is not fully self-contained: for instance, the proof of Theorem 6.2 relies on Lemma G.2 from the appendix without sufficient explanation. Despite the technical contributions being of interest, these presentation issues create an overall impression of a manuscript that is unpolished and not yet ready for publication.\n\n\nAnother point I found confusing is that, while the authors frequently reference and build on CCLY’19, they do not provide a concise and coherent overview of the general structure of the CCLY approach itself. Personally, I found it difficult to keep track of how the new contributions relate to the existing framework, which made it challenging to separate what is directly adopted, what is modified, and what is entirely new. In my opinion, providing a clear and structured overview of the CCLY method early in the paper would greatly improve readability and help orient the reader more effectively.\n\n\nAt present, I am on the fence about recommending acceptance. Given the unclear and insufficiently polished presentation, I am inclined to suggest rejection, although I could be persuaded otherwise if the authors are able to significantly improve the clarity and self-contained nature of the paper.", "was_revised": true, "final_justification": "Improved score based on presentation improvements that the authors suggested", "rebuttal": "Thanks for your thorough review and constructive feedback. We truly appreciate your recognition of significance and quality. \n\n## Regarding presentation quality\nWe sincerely apologize for the numerous issues you encountered.\nWe will conduct a comprehensive revision to address all presentation concerns, including fixing the repeated definitions, defining all terms clearly, and correcting all typos.\nWe recognize that clear presentation is crucial for delivering our technical contributions effectively, and we're committed to revise the manuscript to publication-ready standards for the camera ready version.\n\n## Regarding issues with [CCLY19]\nWe agree with your suggestion about providing a clearer overview of the [CCLY19] framework. We will introduce [CCLY19] in a dedicated section in our revised version that comprehensively explains its structure, adopted components, modified components and our new contribution.\n\n## Issues about Theorem 6.2\nRegarding the self-containedness issue with Theorem 6.2, we will ensure that all key lemmas referenced from the appendix are either briefly stated in the main text or their intuition is sufficiently explained. \n\n## Regarding practical applications\n\nAs mentioned in the introduction. John Ellipsoid is equivalent to the D-optimal design problem in statistics [1,2]. Moreover, John Ellipsoid has numerous applications in machine learning, including [3,4,5]. The faster solving algorithm of John Ellipsoid could also possibly accelerate these algorithms, thus improving the efficiency of real-world problems.\n\n## Conclusion\nWe truly appreciate your elaborate and detailed feedback. Given that you find our technical contributions of interest with appropriate guarantees and novel techniques, we hope you'll reconsider your rating after we address all presentation issues! Thank you so much.\n\n## Reference\n\n[1] Pukelsheim F. Optimal design of experiments. Society for Industrial and Applied Mathematics; 2006.\n\n[2] Todd MJ. Minimum-volume ellipsoids: Theory and algorithms. Society for Industrial and Applied Mathematics; 2016.\n\n[3] Allen-Zhu Z, Li Y, Singh A, Wang Y. Near-optimal design of experiments via regret minimization. ICML’17.\n\n[4] Wang Y, Yu AW, Singh A. On computationally tractable selection of experiments in measurement-constrained regression models. JMLR’17\n\n[5] Lu H, Freund RM, Nesterov Y. Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal on Optimization, 2018."}, {"review_id": "YaKEl86l6b", "reviewer": "Reviewer_MGG9", "summary": "This paper considers the solution of the John Ellipsoid problem, which is to find the epplisoid of the largest volume that is contained inside a convex body. In particular it  assumes that the convex body is defined by a linear systems |A x| <= 1. It proposed two methods, one based on sketching that runs in near linear time to the input size, another tree-width based algorithm.", "questions": "- In Section 1.2, Table 1, if epsilon is small (<1/sqrt(n)), doesn’t it make the proposed algorithm slower than CCLY19 in cost per iter?", "limitations": "yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n- The paper is well organized, presenting the main results first, then hierarchically diving into the details\n- The proof that leads to Theorem 1.1 is impressive and uses quite a bit of machinery\n- The results do seem to be an improvement of previous results under certain conditions (e.g., how small is epsilon)\n\nWeakness:\n- For readers who are not familiar with this problem, it would be very helpful to explain the impact of the proposed algorithm in terms of implications to the applications in machine learning, e.g., would it be able solution of some ML problems that would otherwise be too slow?\n- I don’t see a comparison with benchmarks in actual implementations. I believe Figure 2 shows theoretical results. How do the algorithms compare in practice?", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your thorough review and constructive feedback. We truly appreciate your recognition of our work. \n\n## Regarding empirical comparisons\n\nWe focused on rigorous analysis of our algorithms' theoretical guarantees. We would like to clarify that our work is mostly a theoretical study, which does have a large place in the top machine learning conferences, like NeurIPS, ICLR, and ICML. For instance, NeurIPS accepts papers [1,2,4,5,6,7], all of which are entirely theoretical and do not contain any experiments. Moreover, ICLR and ICML also accepted papers [8,9], which are purely theoretical. Our work is similar to theoretical studies like [5,6,8,10], concentrating on the theoretical aspects of optimization algorithms.\n\n## Regarding ML applications and impact\n\nAs mentioned in Section 1, John Ellipsoid has numerous applications in machine learning, including [11,12,13]. The faster solving algorithm of John Ellipsoid could also possibly accelerate these algorithms, thus improving the efficiency of real-world problems.\n\n## Regarding the epsilon parameter in Table 1\n\nThank you for the question. You are correct. As we stated in Line 56 - 60,  when the matrix $A$ is dense, i.e.,$ \\mathrm{nnz}(A) = \\Theta(nd)$, our per-iteration cost becomes $O(\\epsilon^{-1}nd +\\epsilon^{−2}d^\\omega)$. In the regime where $n > d^\\omega$ and $\\epsilon \\in (1/d, 1)$, our algorithm is always better than [CCLY19] even when the matrix A is dense. \n\n## Conclusion\n\nWe're encouraged by your positive assessment. We hope these clarifications will solidify your confidence in accepting our work. Thank you so much.\n\n## Reference\n[1] Alman, J., & Song, Z. Fast attention requires bounded entries. NeurIPS’23. \n\n[2] Alman J., & Song Z. The fine-grained complexity of gradient computation for training large language models. NeurIPS’24.\n\n[3] Alman, J., & Song, Z. How to capture higher-order correlations? generalizing matrix softmax attention to kronecker computation. ICLR’24.\n\n[4] Sarlos, T., Song, X., Woodruff, D., & Zhang, R. Hardness of low rank approximation of entrywise transformed matrix products. NeurIPS’23.\n\n[5] Dexter, G., Drineas, P., Woodruff, D., & Yasuda, T. Sketching algorithms for sparse dictionary learning: PTAS and turnstile streaming. NeurIPS’23.\n\n[6] Xu, Z., Song, Z. and Shrivastava, A., 2021. Breaking the linear iteration cost barrier for some well-known conditional gradient methods using maxip data-structures. NeurIPS’21.\n\n[7] Song, Z., Vakilian, A., Woodruff, D., & Zhou, S. On Socially Fair Low-Rank Approximation and Column Subset Selection. NeurIPS’24.\n\n[8] Song, Z., Yu, Z.: Oblivious Sketching-based Central Path Method for Linear Programming. ICML’21.\n\n[9] Brand JV, Song Z, Zhou T. Algorithm and hardness for dynamic attention maintenance in large language models. ICML’24.\n\n[10] Song Z, Yang X, Yang Y, Zhang L. Sketching meets differential privacy: fast algorithm for dynamic kronecker projection maintenance. ICML’23.\n\n[11] Allen-Zhu Z, Li Y, Singh A, Wang Y. Near-optimal design of experiments via regret minimization. ICML’17.\n\n[12] Wang Y, Yu AW, Singh A. On computationally tractable selection of experiments in measurement-constrained regression models. JMLR’17\n\n[13] Lu H, Freund RM, Nesterov Y. Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal on Optimization, 2018."}, {"review_id": "cvZXgx6tB2", "reviewer": "Reviewer_uqeL", "summary": "The paper proposes faster algorithms for approximating the John ellipsoid, building upon and improving the best known result, by Cohen et al. (2019a). Namely, within the framework of Cohen et al., the authors propose two algorithms to improve the per-iteration cost: the first is based on improved sketching/sampling, and the second is based on treewidth.", "questions": "Presentation:\n- Section 1\n  - In both main theorems, please clarify the role of $\\delta$ within the formal statement rather than after it for Theorem 1, and skipping it altogether for Theorem 2.\n  - it would be nice to highlight the remark on L194 on the optimal upper/lower bounds somewhere in the introduction.\n- Section 2\n  - L150: treewidth of a ~tree~ graph is NP-hard\n  - Definition 2.5\n    - How's the block structure chosen?\n    - Not sure I follow L155: submatrix of $A$ in column $i$\n  - Lemma 2.7\n    - It would help to clarify the case where $\\tau$ is only known approximately\n- Section 3\n  - Eq(1): would you like to hint at how $\\log(\\det(G))^2$ captures the volume to be maximized?\n  - Would it help to define $Q$ once, instead of twice on L188 and L192?\n  - Is it possible to avoid the naming clash with the approximating polytope $Q$ in Lemma 3.4?\n- Section 4\n  - L212: would you like to highlight that the \"accelerated algorithm\" is based on **sketching**?\n  - L216: this paragraph needs significant clarification\n    - It starts off by digressing into a remark on rewriting $w$ as a leverage score.  While necessary, it delays the discussion of sampling, how sampling works, and why any of that benefits the fixed-point iteration.\n   - Upon reaching \"to be specific\" on L220, the overview given is difficult to follow, and starts talking about a \"sampling matrix\"\n   - The symbols $D$ and $K$, as well as $W$, are not defined.\n   - Later on, it's seen that $D$ is the sampling matrix, but also $H$ and its approximate versions.\n   - The aspect of overapproximating the leverage scores, the required rescaling, and the connection to the two references [CLM+15, DLS23] are not explained.\n  - L234: this paragraph seems redundant, redefining notation.\n    - Crucially though, it's where the vector $v$ appears, which ends up being the primary output of Algorithm 1.\n  - L239: to further speed up the algorithm\n    - What's the running time so far, before the additional speeding up?\n  - L239: starts discussing Algorithm 1, out of no where, even pointing to specific lines.\n  - Algorithm 1\n    - Lines 6-9 can simply be replaced by $w_1 = d \\cdot 1_n$\n    - It would have helped to present a template pseudocode for the fixed-point iteration, leaving the iteration to a subprocedure, to allow easy comparison with the original algorithm of [CCLY19], and duplication in Algorithm 2.\n    - On line#20, note that $\\tilde{w}$ was not defined, and calling it original is pretty confusing.  Perhaps a reference to an equation or definition is better.\n    - Note that line#32 is not useful.\n    - Some line numbers are taken up just to accommodate comments.\n- Section 5\n  - As mentioned in the top-level comment, those informal statements end up taking space, defining and redefining various hyperparameters, while not contributing much towards comprehension and clarity cf. L265.\n  - Section 5.2 is very difficult to appreciate, as the telescoping aspect was not highlighted in the algorithm to motivate this particular angle to the analysis.\n  - L307: formal -> informal\n  - L312: each row of $w_{k,i}$ is a leverage score of some matrix\n    - The phrasing seems wrong.  Referring to line#13 in Algorithm 2, it should be easy to explicitly specify the matrix, instead of calling it some matrix.\n\nNitpicking:\n- consider moving the placement of Table 1, e.g., at the top of the page\n- L145: might as well define $E(G)$ explicitly.\n- L256: during the iterative algorithm -> the fixed-point iteration in Eq(3)\n\nTypos:\n- L114: equivalently -> equivalent\n- L125: propertie -> property\n- L178: associate -> associated\n- L206: for $a_i$ denote\n- L218: we leverage the utilize\n- L251: has some studied", "limitations": "Please mention the ease or feasibility of implementing those algorithms, to complement the theoretical progress and further substantiate the practical relevance of the approximate John ellipsoid.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Improved algorithms for the approximation of the John ellipsoid for an important class of polytopes.  Besides being fundamental objects in math and algorithm theory, see also L18-23 for relevance to ML.\n- The technical tools developed can find further applications, i.e., the approximation of leverage scores and matrix inverses; see L61-67.\n- The connection to treewidth is an interesting perspective, and its practical manifestations can be appreciated more broadly; see L81-85.\n\nWeaknesses:\n- Although the earlier sections of the paper are well-written with good flow, the actual technical sections have serious issues.  Notably, the execution relies heavily on the appendices, resulting in a number of gaps in the overview Section 4, and reducing the informal statements for the analysis in Section 5 as hollow pointers to the appendices that otherwise don't contribute much.\n- While I did not carefully review the appendix, it seems in much better shape, so the authors need to figure out how to summarize the main ideas in the paper.  To allow for this possibility, if the authors can convincingly recover in the rebuttal phase, I'm leaning to a borderline-accept score.\n- If more space is needed, perhaps the second algorithm can be confined to the summary in the introduction, deferring the actual development to the appendix.", "was_revised": true, "final_justification": "The authors engaged in the rebuttal to convincingly address the presentation issues highlighted.  The technical content, motivation, and relevance were already satisfactory to me, so with the promise to revise the presentation I'm recommending acceptance.", "rebuttal": "Thanks for your exceptionally detailed and constructive review. We deeply appreciate your recognition of our technical contributions.\n\n## Regarding reliance on appendices and Section 4 clarity\n\n## Section 1 Questions\n(1) Role of $\\delta$: We'll state this explicitly in the theorems rather than after.\n\n(2) Optimal bounds remark (L194): Thanks for the suggestion. We will revise it.\n\n## Section 2 Questions:\n(1) L150: Thanks for pointing it out. We will add “graph” after “tree”.\n\n(2) Definition 2.5: The block structure partitions the $n$ rows into $m$ blocks. We'll clarify that this is given as part of the input when considering block-structured matrices.\n\n(3) L155: It is the submatrix of $A$ in column $i$ and row block $r$.\n\n(4) Lemma 2.7: We'll add that when only an $O(\\tau \\log^3 n)$-approximation is known (from the [BGS21] algorithm), our runtime becomes $O(n\\tau^2 \\log^6 n)$, which is still efficient for small $\\tau$.\n\n## Section 3 Questions\n(1) $\\log(\\det(G))^2$ and volume: We'll add that for an ellipsoid $\\{x: x^TG^{-2}x \\leq 1\\}$, the volume is proportional to $\\det(G^{-1})^{1/2} = \\det(G)^{-1/2}$, so maximizing $\\log(\\det(G))^2 = 2\\log(\\det(G))$ maximizes volume.\n\n(2) Define Q once: Yes, we'll define Q once after equation (2) and reference it consistently.\n\n(3) Naming clash with Q: Good catch. We'll use $\\mathcal{E}$ for the ellipsoid in Lemma 3.4 to avoid confusion.\n\n## Section 4 Questions\n(1) L212 \"accelerated algorithm\": Yes, we'll explicitly state this refers to sketching-based acceleration.\n\n(2) L216 paragraph clarification: We'll completely rewrite this paragraph with clear flow: (i) explain that $w_{k+1,i}$ equals leverage scores of $B_k = \\sqrt{W_k}A$, (ii) introduce leverage score sampling to approximate these scores efficiently, (iii) explain how oversampling by factor $\\kappa$ ensures $(1\\pm\\epsilon_0)$ approximation.\n\n(3) Undefined symbols: We'll define all notation upfront: $D$ is the sampling matrix, $K$ is likely a typo (should be either $\\mathcal{K}$ the constraint set or removed), $W = \\text{diag}(w)$.\n\n(4) L234 redundancy: We'll remove the redundant definitions and introduce $v$ (the normalized output) more naturally.\n\n(5) L239 running time: We'll clarify that before sketching, the per-iteration cost is $O(\\text{nnz}(A) + d^\\omega)$ from leverage score computation.\n\n## Algorithm 1 Issues\nWe'll implement all your suggestions:\n- Replace lines 6-9 with $w_1 = (d/n) \\cdot \\mathbf{1}_n$\n- Add template pseudocode for comparison with CCLY19\n- Clarify that $\\tilde{w}_{k+1,i}$ (line 20) approximates the ideal update $w_{k+1,i}$\n- Remove line 32 and consolidate comments\n\n## Section 5 Issues\n(1) Section 5.2 telescoping: We'll add intuition explaining that telescoping tracks how approximation errors accumulate across iterations.\n\n(2) L307: Should be \"informal\" - we'll correct this.\n\n(3) L312 clarification: We'll specify explicitly that $w_{k,i}$ is the leverage score of the $i$-th row of matrix $B_k = \\sqrt{W_k}A$.\n\n## Typography and Typos\nThanks for catching these - we'll fix all of them: L114, L125, L178, L206, L218, L251, and reposition Table 1.\n\n## Limitations\nRegarding implementation feasibility: Our algorithms are practical to implement. The first algorithm uses standard randomized linear algebra primitives (Gaussian sketching, leverage score sampling) available in libraries like LAPACK/Scikit-learn. The treewidth algorithm leverages sparse Cholesky factorization, implemented efficiently in packages like CHOLMOD. We'll add this discussion to emphasize practical relevance.\n\n## Conclusion\nWe're grateful for your thorough review and your appreciation. Given that you found our technical contributions solid and indicated willingness to reconsider, we hope these planned improvements will earn your support for acceptance! Thank you so much."}, {"review_id": "A5W7hY85go", "reviewer": "Reviewer_Aseo", "summary": "This work proposes two new algorithms that accelerate the approximation of the John Ellipsoid within a symmetric polytope, claiming an improvement over the state-of-the-art CCLY19 method.\n* The first algorithm utilizes the sparsity of the constraint matrix to lower the per-iteration complexity to $\\tilde{\\mathcal{O}}(\\epsilon^{-1}\\text{nnz}(A) + \\epsilon^{-2}d^\\omega)$, where $\\omega$ is the matrix multiplication exponent.\n* The second algorithm considers from the structural graph point of view, reduces this complexity further to $\\mathcal{O}(n\\tau^2)$ per iteration, with $\\tau$ signifying the treewidth.", "questions": "- The improvement offered by Algorithm 1 over CCLY19 appears incremental, particularly since CCLY19 also discussed using sketching methods for acceleration. Could the authors elaborate on the primary novel contributions of Algorithm 1 compared to CCLY19?\n\n- Could the authors provide concrete examples to illustrate the motivations for, and benefits of, using Algorithm 2?", "limitations": "NaN", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- This work proposes two interesting extensions based on previous work [CCLY19], and the theoretical discussion appears solid.\n- The combination of John Ellipsoid estimation with the treewidth of a matrix-dual-graph seems new.\n\n---\nWeaknesses:\n- Theorem 1.1 is somewhat confusing: the variable $\\delta$ is introduced in the preceding text but is not explicitly part of the theorem's statement. Furthermore, it's unclear whether the theorem makes a probabilistic or deterministic claim.\n- The motivation for incorporating treewidth could be further clarified. Real-world examples would help readers better understand its practical relevance.\n- The primary audience for this work might align more with the TCS community than the NeurIPS audience, though this is a minor concern.", "was_revised": true, "final_justification": "The authors' response has effectively alleviated my concerns about the technical novelty of this work relative to [CCLY19]. While I am now confident in the paper's core contribution, the quality of the presentation still has room to improve. My recommendation is borderline accept.", "rebuttal": "Thanks for your thoughtful review. We appreciate your constructive feedback and the opportunity to clarify our contributions.\n\n## Regarding Theorem 1.1 clarity\nWe agree that we can further clarify this statement. The algorithm makes a probabilistic claim - it succeeds with probability at least $1-\\delta-\\delta_0$ where $\\delta$ is the failure probability for leverage score approximation and $\\delta_0$ is for the sampling process. We'll revise the theorem statement to explicitly include $\\delta$ as a parameter and clearly state the probabilistic nature of the guarantee upfront. This will make it immediately clear that we're providing a randomized algorithm with high-probability bounds.\n\n## Regarding motivation and applications and NeurIPS audience fit\n\nAs mentioned in the introduction. John Ellipsoid is equivalent to the D-optimal design problem in statistics [1,2]. Moreover, John Ellipsoid has numerous applications in machine learning, including [3,4,5]. The faster solving algorithm of John Ellipsoid could also possibly accelerate these algorithms, thus improving the efficiency of real-world problems.\n\n## Question 1: Novel contributions of Algorithm 1 vs [CCLY19]\n\nThanks for asking us to clarify this important distinction. While CCLY19 does use sketching in their Algorithm 2, our contributions go significantly beyond their approach. CCLY19's sketching applies a Gaussian sketch $S \\in \\mathbb{R}^{s \\times m}$ to reduce the per-iteration dependence on $m$ (number of constraints), but they still compute the full $d \\times d$ matrix inverse $(B^T B)^{-1}$ exactly, resulting in $O(mn^2)$ per-iteration cost.\n\nOur key innovation is introducing leverage score sampling as an additional preprocessing step before sketching. This two-stage approach is novel: first, we compute approximate leverage scores and use them to subsample $O(\\epsilon^{-2}d \\log d)$ important rows from the $n \\times d$ matrix, dramatically reducing the effective problem size; second, we apply sketching to this subsampled matrix, further accelerating computations. \n\nThe combination enables us to work with much smaller matrices throughout, achieving $O(\\epsilon^{-1}\\text{nnz}(A) + \\epsilon^{-2}d^{\\omega})$ per iteration instead of CCLY19's $O(mn^2)$. For sparse matrices where $\\text{nnz}(A) \\ll mn$, this is a substantial improvement.\n\nMoreover, our novel telescoping analysis (Lemma 5.2) handles the interaction between sampling and sketching errors, which wasn't needed in CCLY19's simpler sketching-only approach. In essence, CCLY19 showed that sketching helps; we show that intelligent sampling before sketching helps much more, achieving the first input-sparsity time algorithm for this problem.\n\n## Question 2: Concrete examples for Algorithm 2\n\nBeyond the real-world applications mentioned above, here's a concrete example: Consider solving a John ellipsoid problem for a transportation network with 10,000 nodes and tree-like structure (common in distribution networks). The constraint matrix would be $10,000 \\times 10,000$ but with treewidth $\\tau \\approx 10$. Algorithm 2 would run in $O(10,000 \\times 100) = 10^6$ operations per iteration, while CCLY19 needs $O(10,000^3) = 10^{12}$ operations - a million-fold improvement! We'll include such concrete examples to illustrate the practical impact.\n\n## Conclusion\nWe appreciate your engagement with our work and hope these clarifications address your concerns. We would like to kindly request if you could reconsider the rating for our paper, after our clarification. Thank you so much.\n\n## Reference\n[1] Pukelsheim F. Optimal design of experiments. Society for Industrial and Applied Mathematics; 2006.\n\n[2] Todd MJ. Minimum-volume ellipsoids: Theory and algorithms. Society for Industrial and Applied Mathematics; 2016.\n\n[3] Allen-Zhu Z, Li Y, Singh A, Wang Y. Near-optimal design of experiments via regret minimization. ICML’17.\n\n[4] Wang Y, Yu AW, Singh A. On computationally tractable selection of experiments in measurement-constrained regression models. JMLR’17\n\n[5] Lu H, Freund RM, Nesterov Y. Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal on Optimization, 2018."}]

Author rebuttal:

Meta-review: The authors present a well-motivated problem, provide a novel method to address it, and provide a nontrivial proof to guarantee their method’s performance. The tools they introduce have the potential to be used more broadly. The authors must clean up their writing and polish their presentation. They also need to provide a clearer overview of [CCLY19].
Decision: Accept (poster)