Implement ISTA and verify the lasso rate

CodingAdvanced⏱ 3 hoursHigh-Dim Statisticslassoistaimplementationrate verification

Problem

Implement proximal gradient descent (ISTA) for the lasso and use it to verify empirically that the estimation error scales like $\sqrt{s\log p/n}$ .

Generate sparse $\beta^\star$ with $s$ non-zeros and Gaussian design; solve with $\lambda = 2\sigma\sqrt{2\log p/n}$ .
Sweep $n$ at fixed $s,p$ and fit the slope of $\log\|\hat\beta-\beta^\star\|_2$ against $\log n$ .
Sweep $p$ at fixed $n,s$ and check the $\sqrt{\log p}$ dependence.
Compare with ridge regression at its best $\lambda$ , for sparse and for dense $\beta^\star$ .

Implement it, then check the implementation against something you can verify independently.

Solve it here5 tests · Python runs in your browser

⌘/Ctrl + ↵ to run · limit 45s · draft saved in this browser

5 tests will run against your code. The first run downloads the Python runtime — several megabytes, once per browser.

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
Derive the soft-thresholding operator	High-Dim Statistics	Proof	Intermediate	30 min
Implement backpropagation from scratch run	Deep Learning	Coding	Intermediate	3 hours
Implement kernel ridge regression run	Classical ML	Coding	Intermediate	1 hour
Implement multi-head attention from scratch run	Deep Learning	Coding	Intermediate	3 hours
Implement power iteration and verify the convergence rate run	Foundations	Coding	Intermediate	1 hour