## Minimax rates for memory-bounded sparse linear regression

published: Aug. 20, 2015, recorded: July 2015, views: 2269

# Slides

# Related content

# Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our**to describe your request and upload the data.**

__ticket system__*Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.*

# Description

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 bound of $b$ bits, where $\epsilon$ is the $L_2$ parameter error. When the covariance of the regressors is the identity matrix, we also provide an algorithm that uses $\tilde{O}(b+k)$ bits and requires $\tilde{O}(\frac{kd}{b\epsilon^2})$ samples to achieve error $\epsilon$. Our lower bound also holds in the more general communication-bounded setting, where instead of a memory bound, at most $b$ bits of information are allowed to be (adaptively) communicated about each sample.

# Link this page

Would you like to put a link to this lecture on your homepage?

Go ahead! Copy the HTML snippet !

## Write your own review or comment: