Lune

FOCS2022Top-tier venue

Active Linear Regression for ℓp Norms and Beyond

Cameron Musco, Christopher Musco, David P. Woodruff, Taisuke Yasuda

Abstract

We study active sampling algorithms for linear regression, which aim to query only a small number of entries of a target vector b ∈ R n and output a near minimizer to min x∈R d Axb , where A ∈ R n×d is a design matrix and • is some loss function.

For ℓ p norm regression for any 0 < p < ∞, we give an algorithm based on Lewis weight sampling which outputs a (1 + ǫ)-approximate solution using just Õ(d/ǫ 2 ) queries to b for p ∈ (0, 1), Õ(d/ǫ) queries for p ∈ (1, 2), and Õ(d p/2 /ǫ p ) queries for p ∈ (2, ∞). For p ∈ (0, 2), our bounds are optimal up to logarithmic factors, thus settling the query complexity for this range of p. For p ∈ (2, ∞), our dependence on d is optimal, while our dependence on ǫ is off by at most a single ǫ factor, up to logarithmic factors. Our result resolves an open question of Chen and Dereziński, who gave near optimal bounds for the ℓ 1 norm, but required at least d 2 /ǫ 2 samples for ℓ p regression with p ∈ (1, 2), and gave no bounds for p ∈ (2, ∞) or p ∈ (0, 1).

We also provide the first total sensitivity upper bound of O(d max1,p/2 log 2 n) for loss functions with at most degree p polynomial growth. This improves a recent result of Tukan, Maalouf, and Feldman. By combining this with our techniques for ℓ p regression, we obtain an active regression algorithm making Õ(d 1+max1,p/2 / poly(ǫ)) queries for such loss functions, including the important cases of the Tukey and Huber losses. This answers another question of Chen and Dereziński. For the Huber loss, we further improve our bound to a sample complexity of Õ(d 4-2 √ 2 / poly(ǫ)) where 4 -2 √ 2 ≈ 1.17157. Our sensitivity bounds also give improvements to a variety of previous results using sensitivity sampling, including Orlicz norm subspace embeddings, robust subspace approximation, and dimension reduction for smoothed p-norms.

Finally, our active sampling results give the first sublinear time algorithms for Kronecker product regression under every ℓ p norm. Previous results required reading the entire b vector in the kernel feature space. 1 Our work will also extend to other loss functions of the form n i=1 M ([Axb]i) that are not necessarily norms. 2 In principal, entries of b can be read adaptively -i.e., we can select indices to query based on the results of other queries. However, the benefits of adaptivity appear limited. Most methods for solving Problem 1.1 and those studied in this paper are non-adaptive.

3 All query complexity bounds in this section are stated for solving Problem 1.1 with high constant probabilitye.g., probability 99/100. In later sections we will include an explicit dependence on a failure probability δ.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

22 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Sharper Bounds for ℓp Sensitivity Sampling cites Coresets for Near-Convex Functions
  • Computing Approximate 𝓁p Sensitivities cites Sharper Bounds for ℓp Sensitivity Sampling
  • Computing Approximate 𝓁p Sensitivities cites Coresets for Classification - Simplified and Strengthened
  • Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond cites Coresets for Near-Convex Functions
  • Improved Active Learning via Dependent Leverage Score Sampling cites Fourier Sparse Leverage Scores and Approximate Kernel Learning
  • Improved Active Learning via Dependent Leverage Score Sampling cites Coresets for Classification - Simplified and Strengthened
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers22

  1. Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and BeyondKyriakos Axiotis, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome et al.ICML 2024 · 19 citations
  2. Improved Active Learning via Dependent Leverage Score SamplingAtsushi Shimizu, Xiaoou Cheng, Christopher Musco, Jonathan WeareICLR 2024 · 9 citations
  3. Sharper Bounds for ℓp Sensitivity SamplingDavid P. Woodruff, Taisuke YasudaICML 2023 · 8 citations
  4. Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph SparsificationArun Jambulapati, Yang P. Liu, Aaron SidfordSTOC 2023 · 8 citations
  5. Computing Approximate 𝓁p SensitivitiesSwati Padmanabhan, David P. Woodruff, Richard ZhangNeurIPS 2023 · 5 citations

Builds on6

  1. Coresets for Near-Convex FunctionsMurad Tukan, Alaa Maalouf, Dan FeldmanNeurIPS 2020 · 49 citations
  2. Coresets for Classification - Simplified and StrengthenedTung Mai, Cameron Musco, Anup RaoNeurIPS 2021 · 39 citations
  3. Improved Coresets and Sublinear Algorithms for Power Means in Euclidean SpacesVincent Cohen-Addad, David Saulpic, Chris SchwiegelshohnNeurIPS 2021 · 33 citations
  4. Fourier Sparse Leverage Scores and Approximate Kernel LearningTamás Erdélyi, Cameron Musco, Christopher MuscoNeurIPS 2020 · 28 citations
  5. Tight Bounds for the Subspace Sketch Problem with ApplicationsYi Li, Ruosong Wang, David P. WoodruffSODA 2020 · 5 citations

Related papers

  1. Near-optimal Active Regression of Single-Index ModelsYi Li, Wai Ming TaiICLR 2025
  2. Active Regression for Single-Index Models with Unknown Link FunctionsChansophea Wathanak In, Yi Li, Wai Ming Tai, Xuan WuICML 2026
  3. Near-Linear Sample Complexity for Lp Polynomial RegressionRaphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff et al.SODA 2023 · 3 citations
  4. Online Lewis Weight SamplingDavid P. Woodruff, Taisuke YasudaSODA 2023 · 3 citations
  5. Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentationAlexander Munteanu, Simon OmlorICML 2024 · 6 citations
Dusk over the sea between two cliffs drawn in fine vertical lines