Sketching Algorithms and Lower Bounds for Ridge Regression
Authors: Praneeth Kacham, David Woodruff
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We run our algorithm on a ridge regression instance with a 6000 70000 matrix A whose entries are independent Gaussian random variables. We set λ such that σ2/λ 1. Na ıvely computing x = AT(AAT + λI) 1b takes tnaive = 71 seconds on our machine. We use OSNAP with sparsity s = 8 and vary the number r of rows and observe the running times and quality of the solution that is obtained by our algorithm.Our experiments show the general trends we expect. Increasing the number of rows in the sketching matrix results in a solution x that has lower cost and also is closer to the optimum solution x . |
| Researcher Affiliation | Academia | 1Computer Science Department, Carnegie Mellon University. Correspondence to: Praneeth Kacham <pkacham@cs.cmu.edu>, David P. Woodruff <dwoodruf@andrew.cmu.edu>. |
| Pseudocode | Yes | Algorithm 1 RIDGEREGRESSION |
| Open Source Code | No | The paper does not provide a specific link or explicit statement about the public release of the source code for the described methodology. |
| Open Datasets | No | We run our algorithm on a ridge regression instance with a 6000 70000 matrix A whose entries are independent Gaussian random variables. |
| Dataset Splits | No | The paper mentions running an experiment on a generated matrix A but does not specify any training, validation, or test dataset splits. |
| Hardware Specification | No | The paper mentions 'Na ıvely computing x = AT(AAT + λI) 1b takes tnaive = 71 seconds on our machine.' but does not provide specific hardware details for 'our machine'. |
| Software Dependencies | No | The paper does not list specific software dependencies with version numbers. |
| Experiment Setup | Yes | We run our algorithm on a ridge regression instance with a 6000 70000 matrix A whose entries are independent Gaussian random variables. We set λ such that σ2/λ 1. Na ıvely computing x = AT(AAT + λI) 1b takes tnaive = 71 seconds on our machine. We use OSNAP with sparsity s = 8 and vary the number r of rows and observe the running times and quality of the solution that is obtained by our algorithm. |