LASSO (L1) 좌표하강법 [medium]

v1 Ridge 는 L2 페널티 ($\lambda \|w\|_2^2$) → 가중치를 줄이지만 0으로 만들진 않음. LASSO (Tibshirani 1996) 는 L1 페널티 ($\lambda \|w\|_1$) → 많은 $w_j$ 를 정확히 0 으로 → 자동 특성 선택.

$\mathcal{L}(w) = \tfrac{1}{2N} \|y - X w\|^2 + \lambda \|w\|_1$

닫힌 해가 없음 (절댓값 미분 불가). 표준 기법: 좌표 하강법 (coordinate descent).

좌표 하강법

1. $w \gets 0$ 초기화.
2. 수렴까지: 각 $j$ 에 대해:
   • $r_j = y - X w + X_{:,j} w_j$ (j번째 성분 빼고 나머지 잔차).
   • $\rho_j = X_{:,j}^\top r_j$.
   • $z_j = \|X_{:,j}\|^2$.
   • soft-thresholding: $w_j \gets \frac{\text{sign}(\rho_j) \cdot \max(|\rho_j| - N \lambda, 0)}{z_j}$

max(|ρ| - Nλ, 0) 이 정확히 0 을 만드는 트릭. L2 와의 핵심 차이.

수렴

• 모든 $w_j$ 변화 합이 tol 미만이면 종료.
• 또는 max_iter 도달.

과제

함수 fit_lasso(X, y, lam, max_iter=100, tol=1e-6) 를 완성하세요.

• 반환: w shape (D,).
• 수렴 조건: max |w_new - w_old| < tol.
• 특성 정규화 가정: 테스트 데이터는 표준화되어 있음 (고려 안 해도 됨).

테스트 케이스

#	이름	검증
1	shape (D,)
2	lam=0 → Ridge(λ=0) = OLS 와 근사
3	큰 lam → w = 0 (전부)
4	중간 lam → 희소 (일부 정확히 0)
5	실제 희소 데이터에서 0 위치 맞춤
6	sklearn Lasso(alpha=lam, fit_intercept=False) 와 유사
7	수렴: max_iter 충분하면 update 변화 작음