Discrepancy Minimization in Input-Sparsity Time

We sincerely thank the reviewer for the insightful comments and thorough evaluation of our paper.

W1 and W2: Technical Density and Intuition

We appreciate the reviewer's concern regarding the technical density of our presentation. Given the complex nature of discrepancy minimization and the depth of the theoretical contributions, our initial goal was to ensure rigorous correctness. However, we acknowledge that improving readability and intuition is crucial. In the final version, we will include additional intuitive explanations and clear roadmaps to guide readers through the intricate parts of our proofs, particularly emphasizing high-level insights before delving into technical details.

W3: Experiments

Thank you for pointing this out. We conduct the experiments to demonstrate the effectiveness of our algorithm. We focused our experimental evaluation on demonstrating the improvements achieved through the fast hereditary projection. This is because the lazy update scheme is primarily designed to leverage fast matrix multiplication. Although fast matrix multiplication theoretically has lower asymptotic complexity, algorithms based on FMM often suffer from significantly large constant factors, adversely affecting their practical runtime performance. Additionally, for practical considerations, the parameters used in the experiments do not strictly follow the theoretical suggestions in the paper. Our experimental setup follows the matrix configurations used in Larsen’s paper.

Uniform matrices: Each entry of $A$ is uniformly chosen from $\\{-1,1\\}$

2D Corner matrices: $A$ is constructed by choosing two sets of points in the unit square—one for rows and one for columns—and marking an entry as 1 if the row point strictly exceeds the column point in both coordinates, otherwise marking it as 0.

Our algorithm achieves substantial speedups with only minor sacrifices in approximation guarantees. The speedup will be more significant once $m$ is much largerer than $n$, as sketching is known to work well in the regime where $m \gg n$ .

W4: Constants

We agree with the reviewer that the constants in our current analysis primarily serve to highlight theoretical improvements. Optimizing these constants would indeed further enhance the practical applicability of our algorithm, although it would require additional effort. Nevertheless, our preliminary experiments indicate that the algorithm achieves significant improvements in runtime even without strictly adhering to the exact parameters suggested by the theoretical analysis.

We appreciate the positive assessment of our work. Thank you again for your thoughtful review.

We thank the reviewer for the valuable feedback.

Theoretical Claims: The proof of Theorem C.3 (page 19) claimed that a particular set of eigenvectors are orthogonal, which is not true in general.

Because any real symmetric matrix admits an orthogonal diagonalization, its eigenvectors can always be taken to be orthonormal.

W1: Originality and connection to existing methods

While our work builds upon Larsen's algorithm and Lovett–Meka random walk method, we would like to highlight the significant theoretical and algorithmic advances introduced in our work:

• We introduce an innovative implicit leverage-score sampling technique, enabling us to significantly reduce the computational complexity of hereditary projection from Larsen’s original $O(mn^2)$ (or $O(mn^\omega)$ with fast matrix multiplication) to $O(nnz(A)+n^{\omega})$. This improvement is crucial, particularly for sparse input matrices.
• We provide a robust theoretical analysis that carefully manages error accumulation introduced by randomized sketching methods. Such robustness was not previously established and represents a substantial methodological advancement over existing discrepancy minimization frameworks.
• The lazy-update mechanism we introduce to efficiently implement the iterative Edge-Walk algorithm fundamentally reduces computational complexity from Larsen’s $O(mn^2+n^3)$ to our result of $\tilde{O}(nnz(A) + n^{2.53})$. This addresses and overcomes a significant computational barrier identified in prior literature.

W2 and Q2: Interest to the ICML community and applications in ML

Thanks for pointing this out. We argue that the broad relevance of discrepancy theory to the ICML community stems from its strong connections to central themes in machine learning. Specifically, discrepancy minimization intersects significantly with computational learning theory [1,2], computer vision [3], unsupervised learning [4], attention KV caching [5], differential privacy [6], and sampling [7,8]. More specifically, [1,2] introduces the relationship of discrepancy and concepts in learning theory such as VC dimension, PAC learning. [3] introduces a method to learn hash functions via discrepancy minimization. Learning hash functions in content-based image retrieval optimize binary codes to preserve similarity in high-dimensional feature spaces, enabling faster and more efficient image search. [4] leverage discrepancy minimization for unsupervised graph matching by aligning predictions from classical solvers and neural models. [5] proposed an algorithm for compressing the KV cache recursively using a geometric correlated sampling process based on discrepancy theory [6] investigated the relationship between discrepancy minimization and differential privacy in the context of linear queries over histograms. Quasi-Monte Carlo methods [7,8] leverage concepts from discrepancy theory by employing low-discrepancy sequences to efficiently approximate high-dimensional integrals and expectations.

In the final manuscript, we will explicitly clarify and elaborate on these connections to further emphasize the relevance and significance of our work to the ICML audience.

[1] Matousek, Jiri. Geometric discrepancy: An illustrated guide. 2009

[3] Karnin, Zohar, and Edo Liberty. Discrepancy, coresets, and sketches in machine learning. COLT’19

[3] Chen, Zhixiang, et al. Deep hashing via discrepancy minimization. CVPR’18

[4] Wang, Runzhong, Junchi Yan, and Xiaokang Yang. Unsupervised learning of graph matching with mixture of modes via discrepancy minimization. TPAMI’23

[5] Han, Insu, et al. BalanceKV: KV Cache Compression through Discrepancy Theory. arXiv preprint:2502.07861

[6] Nikolov, Aleksandar, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. STOC’13

[7] Lyu, Yueming, Yuan Yuan, and Ivor Tsang. Subgroup-based rank-1 lattice quasi-monte carlo. NeurIPS’20

[8] Lyu, Yueming. Fast rank-1 lattice targeted sampling for black-box optimization. NeurIPS’23

W3: Typos

We sincerely appreciate the detailed list of typos and suggestions provided by the reviewer. We will carefully proofread the manuscript, correcting all listed typographical errors and ensuring clarity in terminology and statements. We recognize that readability and precision are crucial, particularly in technical papers, and will make substantial efforts to improve the overall presentation quality.

Q1: Competitiveness relative to Larsen’s algorithm

Thank you for pointing this out. We conduct the experiments to demonstrate the effectiveness of our algorithm. Due to space limit, please refer to the rebuttal to the reviewer ZGyW for the experiment results.

We sincerely appreciate your valuable feedback, which will significantly help us improve our paper. We hope that we have adequately addressed your concerns. Please do not hesitate to reach out if you have any further questions or comments. Thank you once again for your thoughtful review.

We thank the reviewer for the valuable feedback and for recognizing the novelty, significance, and technical contributions of our work.

W1: Connection to existing works

While our work indeed builds upon Larsen's algorithm and Lovett–Meka random walk method, we would like to highlight the significant theoretical and algorithmic advances in our work:

• We introduce an innovative implicit leverage-score sampling technique, enabling us to significantly reduce the computational complexity of hereditary projection from Larsen’s original $O(mn^2)$ (or $O(mn^\omega)$ with fast matrix multiplication) to $O(nnz(A)+n^{\omega})$. This improvement is crucial, particularly for sparse input matrices.
• We provide a robust theoretical analysis that carefully manages error accumulation introduced by randomized sketching methods. Such robustness was not previously established and represents a substantial methodological advancement over existing discrepancy minimization frameworks.
• The lazy-update mechanism we introduce to efficiently implement the iterative Edge-Walk algorithm fundamentally reduces computational complexity from Larsen’s $O(mn^2+n^3)$ to our result of $\tilde{O}(nnz(A) + n^{2.53})$. This addresses and overcomes a significant computational barrier identified in prior literature.

W2: Interest to ICML community

Thanks for pointing this out. We argue that the broad relevance of discrepancy theory to the ICML community stems from its strong connections to central themes in machine learning. Specifically, discrepancy minimization intersects significantly with computational learning theory [1,2], computer vision [3], unsupervised learning [4], attention KV caching [5], differential privacy [6], and sampling [7,8].

More specifically, [1,2] introduces the relationship of discrepancy and concepts in learning theory such as VC dimension, PAC learning. [3] introduces a method to learn hash functions via discrepancy minimization. Learning hash functions in content-based image retrieval optimize binary codes to preserve similarity in high-dimensional feature spaces, enabling faster and more efficient image search. [4] leverage discrepancy minimization for unsupervised graph matching by aligning predictions from classical solvers and neural models. [5] proposed an algorithm for compressing the KV cache recursively using a geometric correlated sampling process based on discrepancy theory [6] investigated the relationship between discrepancy minimization and differential privacy in the context of linear queries over histograms. Quasi-Monte Carlo methods [7,8] leverage concepts from discrepancy theory by employing low-discrepancy sequences to efficiently approximate high-dimensional integrals and expectations. In the final manuscript, we will explicitly clarify and elaborate on these connections to further emphasize the relevance and significance of our work to the ICML audience.

[1] Matousek, Jiri. Geometric discrepancy: An illustrated guide. 2009

[2] Karnin, Zohar, and Edo Liberty. Discrepancy, coresets, and sketches in machine learning. COLT’19

[3] Chen, Zhixiang, et al. Deep hashing via discrepancy minimization. CVPR’18

[4] Wang, Runzhong, Junchi Yan, and Xiaokang Yang. Unsupervised learning of graph matching with mixture of modes via discrepancy minimization. TPAMI’23

[5] Han, Insu, et al. BalanceKV: KV Cache Compression through Discrepancy Theory. arXiv preprint:2502.07861

[6] Nikolov, Aleksandar, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. STOC’13.

[7] Lyu, Yueming, Yuan Yuan, and Ivor Tsang. Subgroup-based rank-1 lattice quasi-monte carlo. NeurIPS’20

[8] Lyu, Yueming. Fast rank-1 lattice targeted sampling for black-box optimization. NeurIPS’23

C1: Adding the combinatorial bound to Table 1

Thank you for your nice suggestion. We will add this to Table 1.

C2: notation $V_{l,*}$ undefined

Thanks for pointing this out. This means the $l$-th row of the matrix $V$. We will define this in the final manuscript.

C3: Could you adopt a single notation to capture both \cal{T}_mat(m,n,k) and \omega(a,b,c)?

Thank you for your insightful question. We use two notations intentionally due to their different emphases and contexts: We use $\mathcal{T}_\mathrm{mat}(m,n,k)$ to explicitly highlight absolute matrix dimensions, making it convenient for describing the algorithm's complexity at a high level; meanwhile, $\omega(a,b,c)$ concisely captures relative dimension ratios and is widely adopted in algebraic complexity theory, facilitating rigorous complexity analysis. We will clarify this distinction in our revision to ensure readers fully understand why both notations are necessary and complementary.

C4: page 5 line 223 and on & 234 and on - most of the content seems repeated

Thanks for pointing this out. We will remove the repeated parts.

We greatly appreciate the positive evaluation of our paper and thank you for your constructive review.

We greatly appreciate the reviewer's recognition of our contributions, specifically, including significant runtime improvements, novel algorithmic techniques, clear comparisons to existing literature, and rigorous theoretical justifications. We believe our contributions represent a significant step forward in improving computational efficiency and advancing algorithmic techniques for discrepancy minimization. Please let us know if you have any further comments regarding our work. Thank you again for your positive feedback.