Research map / Learning theory and algorithms / Sample complexity
Nearly Linear Row Sampling Algorithm for Quantile Regression
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ℓ1 Lewis weights rather than ℓ1 leverage scores to sample rows | Quantile loss row sampling · Quantile loss row sampling | sample complexity: O(d^3/(\varepsilon^2 \tau)) -> \widetilde{O}(d/(\varepsilon^2\tau^{2})) | Helped |
| Use the sampled instance with Katyusha for optimization | Quantile regression · Quantile regression | running time: \widetilde{O}(\nnz(A) + d^{2.5}/(\varepsilon^2 \tau^2)) | Helped |
| Use Lewis weights sampling on the edge-vertex incidence matrix | Balanced directed graph sparsification · Balanced directed graphs | number of edges: O(n(\alpha/\varepsilon)^2\log (\alpha n/\varepsilon))) | Helped |
| Use LEW instead of SPC2 and SPC3 | Synthetic quantile regression data, τ = 0.5 and 0.75 · Synthetic data | relative solution error | Helped |
| Use LEW instead of SPC3 | Synthetic quantile regression data, τ = 0.95 · Synthetic data | relative solution error | Helped |
| Use LEW instead of SPC2 and SPC3 | Synthetic quantile regression data · Synthetic data | running time | Helped |
| Use LEW instead of uniform sampling and SPC1 | Census quantile regression · U.S. 2000 Census data | relative solution error | Helped |
| Use LEW instead of SPC2 and SPC3 | Census quantile regression · U.S. 2000 Census data | relative solution error | No clear effect |
| Use LEW instead of SPC2 and SPC3 | Census quantile regression · U.S. 2000 Census data | running time | Helped |
Closest papers by meaning
- Turnstile $\ell_p$ leverage score sampling with applications (ICML 2024 · similarity 0.88)
- High-Dimensional Structured Quantile Regression (ICML 2017 · similarity 0.86)
- Distributed High-Dimensional Quantile Regression: Estimation Efficiency and Support Recovery (ICML 2024 · similarity 0.86)
- Robust Sparse Regression with Non-Isotropic Designs (NeurIPS 2024 · similarity 0.82)
- Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel (ICLR 2025 · similarity 0.82)
- Causal Discovery via Transformed Low-Rank Quantile Surfaces (NeurIPS 2026 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.