A Nearly-Optimal Bound for Fast Regression with $\ell_∞$ Guarantee
Authors: Zhao Song, Mingquan Ye, Junze Yin, Lichen Zhang
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | On the algorithmic side, we prove that there exists a distribution of dense sketching matrices with m = ϵ 2d log3(n/δ) such that solving the sketched regression problem gives the ℓ guarantee, with probability at least 1 δ. Moreover, we develop a novel analytical framework for ℓ guarantee regression that utilizes the Oblivious Coordinate-wise Embedding (OCE) property introduced in (Song & Yu, 2021). Our analysis is much simpler and more general than that of (Price et al., 2017). |
| Researcher Affiliation | Collaboration | 1Adobe Research 2University of Illinois at Chicago 3Boston University 4MIT. |
| Pseudocode | No | The paper does not contain any pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not discuss the use of any specific datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not discuss dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or training configurations. |