Variable Selection for Feature-Based Newsvendor

Summary

The paper studies variable selection for the feature-based newsvendor: learning a sparse linear ordering policy ω⊤x+c with at most d nonzero coefficients by minimizing the ℓ0-constrained, ℓ2-regularized empirical newsvendor loss, shown NP-hard via an Exact Cover by 3-Sets reduction. Computationally, it gives a mixed-integer second-order cone 'perspective' reformulation whose continuous relaxation is provably at least as strong as — and on a constructed instance strictly stronger than — the Big-M formulation, plus a Big-M-free variant. Two scalable heuristics follow: continuous relaxation with randomized rounding, carrying a bi-criteria guarantee (support may exceed d; objective within ε), and a greedy method built on a minimax dual reformulation, for which no approximation guarantee is given. Statistically, under a sparse linear quantile model, the exact estimator attains √(d log(eD/d)/n) estimation error with matching out-of-sample risk and support-recovery guarantees. Synthetic experiments show the perspective formulation dominating Big-M as dimension grows (Big-M hits the 1800 s limit with 100% gaps or infeasibility at D=2000), and exact/greedy beating Lasso on support recovery and estimation. A Kaggle retail case (n=2239, D=1157) shows lower cost than the full model only at larger γ. Limitations: no greedy guarantee, theory covers only the exact estimator, one retailer-year of real data, and no Lasso or scalable-method baselines in the real-data comparison.