Faster Algorithms for Structured John Ellipsoid Computation

Thanks for your thoughtful review. We appreciate your constructive feedback and the opportunity to clarify our contributions.

Regarding Theorem 1.1 clarity

We 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.

Regarding motivation and applications and NeurIPS audience fit

As 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.

Question 1: Novel contributions of Algorithm 1 vs [CCLY19]

Thanks 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.

Our 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.

The 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.

Moreover, 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.

Question 2: Concrete examples for Algorithm 2

Beyond 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.

Conclusion

We 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.

Reference

[1] Pukelsheim F. Optimal design of experiments. Society for Industrial and Applied Mathematics; 2006.

[2] Todd MJ. Minimum-volume ellipsoids: Theory and algorithms. Society for Industrial and Applied Mathematics; 2016.

[3] Allen-Zhu Z, Li Y, Singh A, Wang Y. Near-optimal design of experiments via regret minimization. ICML’17.

[4] Wang Y, Yu AW, Singh A. On computationally tractable selection of experiments in measurement-constrained regression models. JMLR’17

[5] Lu H, Freund RM, Nesterov Y. Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal on Optimization, 2018.

Thanks for your exceptionally detailed and constructive review. We deeply appreciate your recognition of our technical contributions.

Regarding reliance on appendices and Section 4 clarity

Section 1 Questions

(1) Role of $\delta$: We'll state this explicitly in the theorems rather than after.

(2) Optimal bounds remark (L194): Thanks for the suggestion. We will revise it.

Section 2 Questions:

(1) L150: Thanks for pointing it out. We will add “graph” after “tree”.

(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.

(3) L155: It is the submatrix of $A$ in column $i$ and row block $r$.

(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$.

Section 3 Questions

(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.

(2) Define Q once: Yes, we'll define Q once after equation (2) and reference it consistently.

(3) Naming clash with Q: Good catch. We'll use $\mathcal{E}$ for the ellipsoid in Lemma 3.4 to avoid confusion.

Section 4 Questions

(1) L212 "accelerated algorithm": Yes, we'll explicitly state this refers to sketching-based acceleration.

(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.

(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)$.

(4) L234 redundancy: We'll remove the redundant definitions and introduce $v$ (the normalized output) more naturally.

(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.

Algorithm 1 Issues

We'll implement all your suggestions:

• Replace lines 6-9 with $w_1 = (d/n) \cdot \mathbf{1}_n$
• Add template pseudocode for comparison with CCLY19
• Clarify that $\tilde{w}_{k+1,i}$ (line 20) approximates the ideal update $w_{k+1,i}$
• Remove line 32 and consolidate comments

Section 5 Issues

(1) Section 5.2 telescoping: We'll add intuition explaining that telescoping tracks how approximation errors accumulate across iterations.

(2) L307: Should be "informal" - we'll correct this.

(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$.

Typography and Typos

Thanks for catching these - we'll fix all of them: L114, L125, L178, L206, L218, L251, and reposition Table 1.

Limitations

Regarding 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.

Conclusion

We'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.

Thanks for your thorough review and constructive feedback. We truly appreciate your recognition of our work.

Regarding empirical comparisons

We 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.

Regarding ML applications and impact

As 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.

Regarding the epsilon parameter in Table 1

Thank 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.

Conclusion

We're encouraged by your positive assessment. We hope these clarifications will solidify your confidence in accepting our work. Thank you so much.

Reference

[1] Alman, J., & Song, Z. Fast attention requires bounded entries. NeurIPS’23.

[2] Alman J., & Song Z. The fine-grained complexity of gradient computation for training large language models. NeurIPS’24.

[3] Alman, J., & Song, Z. How to capture higher-order correlations? generalizing matrix softmax attention to kronecker computation. ICLR’24.

[4] Sarlos, T., Song, X., Woodruff, D., & Zhang, R. Hardness of low rank approximation of entrywise transformed matrix products. NeurIPS’23.

[5] Dexter, G., Drineas, P., Woodruff, D., & Yasuda, T. Sketching algorithms for sparse dictionary learning: PTAS and turnstile streaming. NeurIPS’23.

[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.

[7] Song, Z., Vakilian, A., Woodruff, D., & Zhou, S. On Socially Fair Low-Rank Approximation and Column Subset Selection. NeurIPS’24.

[8] Song, Z., Yu, Z.: Oblivious Sketching-based Central Path Method for Linear Programming. ICML’21.

[9] Brand JV, Song Z, Zhou T. Algorithm and hardness for dynamic attention maintenance in large language models. ICML’24.

[10] Song Z, Yang X, Yang Y, Zhang L. Sketching meets differential privacy: fast algorithm for dynamic kronecker projection maintenance. ICML’23.

[11] Allen-Zhu Z, Li Y, Singh A, Wang Y. Near-optimal design of experiments via regret minimization. ICML’17.

[12] Wang Y, Yu AW, Singh A. On computationally tractable selection of experiments in measurement-constrained regression models. JMLR’17

[13] Lu H, Freund RM, Nesterov Y. Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal on Optimization, 2018.

Thanks for your thorough review and constructive feedback. We truly appreciate your recognition of significance and quality.

Regarding presentation quality

We sincerely apologize for the numerous issues you encountered. We will conduct a comprehensive revision to address all presentation concerns, including fixing the repeated definitions, defining all terms clearly, and correcting all typos. We 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.

Regarding issues with [CCLY19]

We 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.

Issues about Theorem 6.2

Regarding 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.

Regarding practical applications

As 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.

Conclusion

We 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.

Reference

[1] Pukelsheim F. Optimal design of experiments. Society for Industrial and Applied Mathematics; 2006.

[2] Todd MJ. Minimum-volume ellipsoids: Theory and algorithms. Society for Industrial and Applied Mathematics; 2016.

[3] Allen-Zhu Z, Li Y, Singh A, Wang Y. Near-optimal design of experiments via regret minimization. ICML’17.

[4] Wang Y, Yu AW, Singh A. On computationally tractable selection of experiments in measurement-constrained regression models. JMLR’17

[5] Lu H, Freund RM, Nesterov Y. Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal on Optimization, 2018.