Tight Bounds for Active lp Regression and Beyond
summary
Gives tight query bounds for active lp regression with concrete algorithms: sensitivity sampling followed by Lewis-weight chaining and a label-partition that caps b by sensitivities, producing a constant-factor solution then iterating to tighten ε. Claims: d/ε for 1<p<2 (tight), d/ε^2 at p=1 (phase change at p=1), and for p>2 a tight bound d^{p/2}/ε^{p-1}. Extends to M-estimators (Huber ≈ d^{1.172}/poly(ε)) and removes nnz(b) from Kronecker-product regression; proofs include explicit lower bounds.
AI-written summary · about
chapters (13)
- 0:00Introduction to talk
- 1:23The active learning setting
- 2:31Problem setting
- 3:50Existing results
- 6:45New contributions
- 11:09Application: Kronecker product
- 13:09Sensitivity sampling
- 24:13Partitioning and large labels
- 28:47Chaining and Lewis weights
- 34:56Recursive algorithms
- 42:17Iterating for epsilon
- 51:30Lower bounds and conclusion
- 56:55Q&A session
related talks
30mComputational Barriers For Learning Some Generalized Linear Models
44mActive Regression via Linear-Sample Sparsification
53mOptimality in Locally Private Estimation and Learning
28mSketching for M-Estimators: A Unified Approach to Robust Regression
01h 17mRobust Optimization and Generalization
01h 01mRobustness, Stochastics, Uncertainty 2
01h 02mLarge-Scale Private Learning, Part I
43mRobustness in High-Dimensional Inference Tasks