Minimax rates for memory-bounded sparse linear regression thumbnail
Pause
Mute
Subtitles not available
Playback speed
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Full screen

Minimax rates for memory-bounded sparse linear regression

Published on Aug 20, 20152297 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