Discrepancy Minimization in Input-Sparsity Time
Authors: Yichuan Deng, Xiaoyu Li, Zhao Song, Omri Weinstein
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We conduct the experiments to empirically validate the efficiency 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 algorithm. Our experimental setup follows the matrix configurations used in Larsen (2023): Uniform matrices: Every entry is chosen independently and uniformly from the set { 1, +1}. 2D corner matrices: Sample two point sets P = {p1, . . . , pn} and Q = {q1, . . . , qm} independently and uniformly from the unit square [0, 1] [0, 1]. Construct a matrix with one column per pj P and one row per qi Q; set the entry (i, j) to 1 if pj is dominated by qi, i.e. qi, x > pj, x and qi, y > pj, y , and to 0 otherwise. 2D halfspace matrices: Draw P = {p1, . . . , pn} uniformly from [0, 1] [0, 1] and construct a set Q of m half-spaces as follows: pick a point a uniformly on either the left or the top boundary of the unit square, a point b uniformly on either the right or the bottom boundary, and then choose uniformly whether the half-space consists of all points above the line through a and b or all points below it. Form a matrix with one column per pj P and one row per half-space hi Q; set the entry (i, j) to 1 if pj hi and to 0 otherwise. |
| Researcher Affiliation | Academia | 1The University of Washington 2University of New South Wales 3University of California, Berkeley 4Columbia University. Correspondence to: Xiaoyu Li <EMAIL>, Zhao Song <EMAIL>. |
| Pseudocode | Yes | Algorithm 1, Algorithm 2, Algorithm 3, Algorithm 4, Algorithm 5, Algorithm 6, Algorithm 7, Algorithm 8, Algorithm 9, Algorithm 10, Algorithm 11 are provided in the appendix and main text. |
| Open Source Code | Yes | Our code is available at https://github.com/magiclinux/input_sparsity_discrepancy_icml_2025. |
| Open Datasets | No | Our experimental setup follows the matrix configurations used in Larsen (2023): Uniform matrices: Every entry is chosen independently and uniformly from the set { 1, +1}. 2D corner matrices: Sample two point sets P = {p1, . . . , pn} and Q = {q1, . . . , qm} independently and uniformly from the unit square [0, 1] [0, 1]. Construct a matrix with one column per pj P and one row per qi Q; set the entry (i, j) to 1 if pj is dominated by qi, i.e. qi, x > pj, x and qi, y > pj, y , and to 0 otherwise. 2D halfspace matrices: Draw P = {p1, . . . , pn} uniformly from [0, 1] [0, 1] and construct a set Q of m half-spaces as follows: pick a point a uniformly on either the left or the top boundary of the unit square, a point b uniformly on either the right or the bottom boundary, and then choose uniformly whether the half-space consists of all points above the line through a and b or all points below it. Form a matrix with one column per pj P and one row per half-space hi Q; set the entry (i, j) to 1 if pj hi and to 0 otherwise. The paper describes generating synthetic datasets according to specified procedures rather than providing concrete access information (link, DOI, citation) for pre-existing public datasets. |
| Dataset Splits | No | The paper describes methods for generating input matrices of various sizes and sparsities for experimental evaluation, such as 'Uniform matrices', '2D corner matrices', and '2D halfspace matrices'. However, it does not specify any training/test/validation dataset splits, which are typically relevant for machine learning models and supervised learning tasks. |
| Hardware Specification | No | The paper mentions 'The runtime is measured in second' in Tables 2, 3, and 4, but no specific hardware details (like GPU models, CPU types, or memory) are provided for the experimental setup. |
| Software Dependencies | No | The paper does not explicitly mention any specific software dependencies or their version numbers (e.g., Python 3.x, PyTorch 1.x, specific solvers with versions) that would be needed to replicate the experiments. |
| Experiment Setup | Yes | Our experimental setup follows the matrix configurations used in Larsen (2023): Uniform matrices: Every entry is chosen independently and uniformly from the set { 1, +1}. 2D corner matrices: Sample two point sets P = {p1, . . . , pn} and Q = {q1, . . . , qm} independently and uniformly from the unit square [0, 1] [0, 1]. Construct a matrix with one column per pj P and one row per qi Q; set the entry (i, j) to 1 if pj is dominated by qi, i.e. qi, x > pj, x and qi, y > pj, y , and to 0 otherwise. 2D halfspace matrices: Draw P = {p1, . . . , pn} uniformly from [0, 1] [0, 1] and construct a set Q of m half-spaces as follows: pick a point a uniformly on either the left or the top boundary of the unit square, a point b uniformly on either the right or the bottom boundary, and then choose uniformly whether the half-space consists of all points above the line through a and b or all points below it. Form a matrix with one column per pj P and one row per half-space hi Q; set the entry (i, j) to 1 if pj hi and to 0 otherwise. Tables 2, 3, and 4 also show 'Matrix Size' and 'Sparsity' as experimental parameters. |