0.25
0.5
0.75
1.25
1.5
1.75
2
Minimax rates for memory-bounded sparse linear regression
Published on Aug 20, 20152290 Views
We establish a minimax lower bound of $\Omega\p{\frac{kd}{b\epsilon}}$ on the number of samples needed to estimate the parameters in a $k$-sparse linear regression of dimension $d$ given a memory boun
Related categories
Chapter list
Minimax Rates for Memory-Constrained Sparse Linear Regression00:00
Resource-Constrained Learning00:02
Setting01:10
Motivating question03:19
Problem Statement03:50
Proof Overview05:38
Lower Bound Construction08:42
Some Information Theory10:32
Strong Data-Processing Inequality13:26
Upper Bound15:23
Discussion16:50