Quantile Regression: Check Loss, KKT Conditions, and Scalable Optimization

Fix a quantile level $\tau \in (0, 1)$. The quantile regression estimator $\hat{\beta}$ minimizes the check-loss objective: $\hat{\beta} = \arg\min_{\beta} \sum_{i=1}^{n} \rho_\tau(y_i - x_i^\top \beta), \quad \rho_\tau(u) = u(\tau - \mathbf{1}\{u < 0\})$ **(i)** Show that $\hat{\beta}$ defined above is indeed the sample $\tau$-quantile regression estimator. Derive the first-order (subgradient) optimality conditions. **(ii)** Reformulate the minimization as a linear program (LP). Define the auxiliary variables and write the LP explicitly. **(iii)** For large-scale problems where the LP is too slow, describe coordinate descent with a Huberized approximation of the check loss. Explain why the Huberized approximation is needed and how to choose the smoothing parameter.