Iterative Double Sketching for Faster Least-Squares Optimization
Authors: Rui Wang, Yanyan Ouyang, Wangli Xu
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We conduct experiments to verify the good performance of the IDS algorithm in practice. We carry out simulations of the IDS algorithm and compare it with the IHS algorithm and the PCG algorithm in (Lacotte & Pilanci, 2021). All algorithms are implemented by C++. No external library is used except for C++ Standard Template Library. The matrix inverse is implemented by Gaussian elimination. The program is compiled using gcc version 7.5.0 with -O2 optimization, and runs on a CPU with 3.30 GHz. We use t := A(xt x ) 2 to measure the precision of xt, t = 1, . . . , T. In our experiments, T = 6 iterations are performed for all algorithms. |
| Researcher Affiliation | Academia | Center for Applied Statistics and School of Statistics, Renmin University of China, Beijing 100872, China. |
| Pseudocode | Yes | Algorithm 1 Generic iterative double sketching, Algorithm 2 Optimal sketch sizes, Algorithm 3 IDS algorithm with iteration efficient sketching matrices |
| Open Source Code | No | The paper states: 'All algorithms are implemented by C++. No external library is used except for C++ Standard Template Library.' However, it does not provide an explicit statement about making the source code available for the described methodology (e.g., a link to a repository or a statement about supplementary material). |
| Open Datasets | No | The paper describes a 'data generation mechanism' for Model I and Model II, where data elements are i.i.d. generated from standard normal distributions or based on Model I with added zeros. It does not use or reference any publicly available datasets. |
| Dataset Splits | No | The paper describes a data generation mechanism for Models I and II but does not specify any training, validation, or test splits, as the data is generated for each experiment rather than being pre-split from a fixed dataset. |
| Hardware Specification | No | The program is compiled using gcc version 7.5.0 with -O2 optimization, and runs on a CPU with 3.30 GHz. This specifies a clock speed but not a specific CPU model (e.g., 'Intel Core i7-XXXX' or 'AMD Ryzen XXXXX'), which would provide more precise hardware information. |
| Software Dependencies | Yes | All algorithms are implemented by C++. No external library is used except for C++ Standard Template Library. The program is compiled using gcc version 7.5.0 with -O2 optimization |
| Experiment Setup | Yes | The IDS algorithm is implemented according to Algorithm 3 with T = 5, T = 1, m0 = N/25, r = 8d. Following the result of Ozaslan et al. (2019), we adopt the step size µ = (1 d/r)2 1+d/r . For the IHS algorithm, we use the update formula xt+1 = xt µ(A S 0 S0A) 1 f(xt; A, y) where S0 is an (8d) N SRHT sketching matrix and µ = (1 d/r)2 1+d/r . |