John Ellipsoids via Lazy Updates

despite that the main result does not rely on Theorem 1.3, there is no proof or reference for it.

Could you please refer to the proof of Theorem 1.3?

The proof of Theorem 1.3 is sketched in the paragraphs immediately below it.

We first summarize the result of [DMMW12]. It is known that we can compute $Q$ such that $(1+\epsilon)Q \preceq A^\top A \preceq (1-\epsilon) Q$ in time $\mathrm{nnz}(A) + \mathrm{poly}(d/\epsilon)$ time [CW13], so the leverage scores of $A$ are the row norms of $A Q^{-1/2}$ up to a $(1\pm\epsilon)$ factor. We can then apply the Johnson--Lindenstrauss lemma and multiply this matrix by a random projection matrix $P$ with $t = O(\epsilon^{-2}\log n)$ rows, so that the row norms of $A Q^{-1/2} P$ approximate the row norms of $A Q^{-1/2}$ up to a $(1\pm\epsilon)$ factor. Thus, we indeed have that the leverage scores are approximated by the row norms of some matrix $AR$ for $R = Q^{-1/2}P$ up to $(1\pm\epsilon)$ factors.

Finally, we can efficiently multiply $A$ by $Q^{-1/2}P$ quickly using Corollary 1.5. In the revision, we will include a full proof in the appendix.

contribution should clarified. The proof of Theorem 1.6 mainly relies on the existing results.

Could you please clarify on your particular contribution?

Our result gives the fastest known algorithm for computing $(1+\epsilon)$-approximate John ellipsoids when $\epsilon$ is not too small. While we indeed build on existing techniques, and in particular the iterated leverage score algorithm of [CCLY19], we make two key improvements to this algorithm: (1) the use of lazy updates that allow us to better exploit the faster running time of leverage scores by batching the leverage score computations, and (2) the use of fast matrix multiplication to give a faster algorithm for approximating leverage scores. Finally, these ideas also give low-space streaming algorithms.

I would also like you to comment on the most recent papers and preprints from 2023 and 2024 if any, to confirm your contribution.

To the best of our knowledge, the most recent relevant work on computing $(1+\epsilon)$-approximate John ellipsoids is the works of [CCLY22] and [SYYZ22], which are discussed thoroughly in the introduction. We are not aware of works from 2023 or 2024 on this topic.

I wish more applications had been discussed. ...

We note that $(1+\epsilon)$-approximate John ellipsoids have many applications to statistics, machine learning, and computational geometry, as is discussed in our introduction as well as in the works of [CCLY19, SYYZ22]. Some notable applications include D-optimal experiment design, outlier detection, and pattern recognition.

There are a couple of difficulties which prevent us from stating further running time improvements as a result of our faster leverage score algorithm beyond our applications to John ellipsoids, and we believe our work highlights the importance of overcoming such difficulties. The first is that the target application should require $(1+\epsilon)$-approximate leverage scores, since if only constant factor approximations are required (as in the case of $\ell_p$ Lewis weight sampling), then leverage score approximation can be done in input sparsity time. If we wish to compute $(1+\epsilon)$-approximate $\ell_p$ Lewis weights using $(1+\epsilon)$-approximate leverage scores, then known reductions require either exact leverage scores [FLPS22] or leverage score approximations that are $(1+\epsilon/\mathrm{poly}(d))$-approximate [AGS24]. In the latter case, in theory our results may no longer give improvements due to the large exponent in our polynomial dependence on $\epsilon$. We have raised the question of whether faster algorithms can be design for $\ell_p$ Lewis weights in the original draft, and we will include this discussion in the revision.

Mild issues: ...

Thank you for pointing these out! We have fixed these in the revision. The $d^\omega$ dependence (rather than the $d^2$ that you suggest) is due to computing the matrix inverse $Q^{-1}$.

Indeed, constant factor leverage score approximation takes time $\tilde O(\mathrm{nnz}(A) + d^\omega)$ time, as we cite in Theorem 1.2. We have informally referred to this as input sparsity time, as we assume a regime where $\mathrm{nnz}(A) \geq n \gg \mathrm{poly}(d)$. For dense matrices, our $\tilde O(nd)$ dominating running time would upper bound $\mathrm{nnz}(A)$. To re-iterate, our running time improvement is focused on $(1+\epsilon)$ approximation of leverage scores, where we improve from $\epsilon^{-2}\mathrm{nnz}(A) + \mathrm{poly}(d/\epsilon)$ to $\tilde O(nd) + \mathrm{poly}(d/\epsilon)$. However, this does not give substantial improvements when $\epsilon$ is constant.

Yes, we can use the Sherman--Morrison formula to improve the update time of maintaining the inverse of the quadratic in our streaming algorithm, thank you for pointing that out! It is unclear if the Sherman--Morrison would improve the running time of the offline fast algorithm.

The authors do not give justifications in the checklist.

We believe we have included a justification for the paper checklist whenever the list item warrants additional justifications. In particular, we give an in-depth discussion of the limitations of our work in Section 3. We are happy to give further justification on anything.

Please check the capitalization in the references.

Upon a review of the citations, we have ensured that the names in the following titles are properly capitalized:

• "An elementary proof of a theorem of Johnson and Lindenstrauss"
• "Computing Lewis Weights to High Precision"
• "On computing approximate Lewis weights"
• "A near-optimal algorithm for approximating the John ellipsoid"
• "Linear convergence of a modified Frank-Wolfe algorithm for computing minimum-volume enclosing ellipsoid"
• "Faster Algorithm for Structured John Ellipsoid Computation"

can you explicitly give the space complexity in Theorem 1.8?

The space complexity for Theorem 1.8 is included in the paragraph following Theorem 1.8, and the total space usage is $O(d^2 T)$ words (i.e., real numbers) of space, where $T = O(\epsilon^{-1}\log(n/d))$ is the number of passes. This has been clarified in the theorem statement of Theorem 1.8 in the revision.