PaperlayerView exact revision on arXiv

Source-linked AI summary

Variable Selection for Feature-Based Newsvendor

Zhaoliang Yuan, Jie Wang

arXiv:2609.01544v1stat.MLcs.LG

TL;DR

High-dimensional feature-based newsvendor policies create interpretability and data-collection challenges, motivating variable selection under a hard cardinality constraint. The paper develops exact, approximate, and statistical methods for this sparse policy problem, with experiments showing trade-offs among computational effort, support recovery, and out-of-sample operating cost.

  • Problem

    High-dimensional feature sets hinder interpretability and increase data collection and implementation costs in feature-based newsvendor models.

  • Method

    The paper combines hard-cardinality policy learning with exact MISOCP optimization, randomized rounding, greedy selection, and statistical analysis.

  • Results

    The numerical results illustrate trade-offs among computational effort, support-recovery accuracy, and out-of-sample operating cost.

  • Takeaways & Limitations

    The framework provides computational and statistical guarantees for feature-based newsvendor policies using hard-cardinality-constrained selection.

  • Takeaways & Limitations

    The paper identifies extending the framework to misspecified, heavy-tailed, dependent, or distributionally robust settings as future research.

Abstract

from arXiv · show

Feature-based newsvendor models use observable covariates to tailor inventory decisions, aiming to balance holding and shortage costs under demand uncertainty. However, high-dimensional feature sets often hinder interpretability and inflate data collection and implementation costs. This paper studies variable selection for the feature-based newsvendor problem under a hard cardinality constraint on the number of selected features. We formulate the resulting $\ell_0$-constrained empirical newsvendor problem with $\ell_2$-regularization, establish its computational hardness, and develop a mixed-integer second-order cone programming reformulation that strengthens the standard Big-$M$ formulation. To enable scalability beyond exact optimization, we develop a randomized-rounding algorithm with a bi-criteria guarantee and a greedy heuristic. Statistically, we provide theoretical analysis of the resulting sparse policy estimator, including finite-sample estimation error, out-of-sample risk bounds, and support recovery guarantees. Extensive experiments on both synthetic and real data illustrate the computational and statistical trade-offs among various baselines. Our results demonstrate that the proposed variable selection framework achieves competitive out-of-sample operational costs while using substantially fewer covariates.

1. Introduction

The paper studies variable selection for feature-based newsvendor policies, motivated by interpretability and the costs of collecting and implementing many covariates. It develops exact and approximate optimization methods, statistical guarantees, and numerical comparisons for hard-cardinality-constrained policies.

  • Variable selection can improve interpretability, reduce data collection and monitoring costs, simplify implementation, and improve robustness to noisy or unstable irrelevant features.
  • The paper asks how to efficiently solve feature-based newsvendor variable selection and establish statistical guarantees for the resulting policies.
  • The framework adds ℓ2-regularization and reformulates hard-cardinality variable selection as a mixed-integer second-order cone program.
  • The MISOCP has a tighter continuous relaxation than the standard Big-M formulation, supporting more efficient algorithm design.
  • Randomized rounding and greedy methods complement exact optimization for scalable solution procedures.
  • Under sparse linear demand dependence, the paper establishes estimation, out-of-sample performance, and support recovery guarantees that depend on sparsity rather than dimension.
  • Experiments on synthetic and retail data compare exact, randomized-rounding, greedy, and Lasso-based approaches to expose computational and statistical trade-offs.

2. Problem Setup

The paper formulates feature-based newsvendor variable selection as an ℓ0-constrained, ℓ2-regularized empirical quantile-regression problem with sparse linear decision rules. It establishes computational hardness, proposes MISOCP and approximation methods, and analyzes statistical performance under sparse linear demand.

  • Sparse linear decision rules map features directly to order quantities, making the selected policy interpretable and explainable.
  • For fixed supports, the associated subproblem is convex, enabling mixed-integer convex reformulations and nonlinear extensions through basis expansion.
  • The empirical problem minimizes asymmetric newsvendor loss with ℓ2-regularization subject to selecting at most d covariates.
  • Problem (3) is NP-hard when the sparsity level d is part of the input.
  • The MISOCP reformulation can be solved exactly for medium-sized instances, while two approximation algorithms provide scalable alternatives.
  • The statistical analysis establishes consistency, sample complexity, and support recovery guarantees for the proposed approach.

3. Exact Computational Algorithms

The paper develops exact algorithms for the cardinality-constrained newsvendor problem, focusing on a perspective reformulation that strengthens the standard Big-M formulation. The reformulation preserves optimality while tightening continuous relaxations and improving computational tractability.

  • Big-M Reformulation: The ℓ0 constraint is modeled with binary support variables and Big-M inequalities linking coefficient magnitudes to selected features.The formulation imposes |ω[i]| ≤ M[i]s[i] with binary s indicating whether a coefficient may be nonzero.
  • Big-M Reformulation: Big-M formulations can be computationally expensive because their continuous relaxations may have substantial optimality gaps.Large-scale instances and conservative Big-M constants can also create numerical difficulties.
  • Perspective Reformulation: The perspective reformulation converts the sparsity-constrained problem into a mixed-integer second-order cone program.A rotated second-order cone represents the perspective constraint, yielding a MISOCP formulation.
  • Perspective Reformulation: The perspective and Big-M formulations are equivalent as mixed-integer programs, so they have the same optimal value.The perspective formulation nevertheless has a stronger continuous relaxation than Big-M.
  • Computational Implications: A tighter continuous relaxation typically lets branch-and-bound explore fewer nodes and converge faster in practice.The perspective formulation also avoids relying as heavily on valid and tight Big-M constants, whose derivation can be difficult.

4. Scalable Approximation Algorithms

The paper develops scalable approximation methods for the sparse newsvendor problem: randomized rounding from a continuous relaxation and a greedy support-selection heuristic. Randomized rounding has a bi-criteria guarantee, while the greedy objective decreases monotonically but lacks a general final-iterate approximation guarantee.

  • Continuous Relaxation with Randomized Rounding: The randomized-rounding method solves a continuous relaxation and estimates a sparse regression support from its solution.The approach is designed to obtain near-optimal solutions more efficiently than exact optimization.
  • Continuous Relaxation with Randomized Rounding: With high probability, randomized rounding selects a support only moderately larger than d while keeping the objective within an additive tolerance of optimum.The guarantee is explicitly bi-criteria because the sparsity budget may be exceeded.
  • Continuous Relaxation with Randomized Rounding: The support-size bound depends on the target sparsity d rather than the data dimension D.The concentration result also does not require the condition log(2/δ) ≤ d/3 used in the referenced result.
  • Greedy Algorithm: For a fixed support, the inner optimization is convex, enabling a greedy method that iteratively adds the index minimizing the current objective.The dual representation depends on the selected support through the corresponding design submatrix.
  • Greedy Algorithm: The greedy iterates have a monotonically decreasing objective, but no final-iterate approximation guarantee is established because the set function is not submodular.The greedy search can be restricted to variables exceeding a threshold in the continuous-relaxation solution, reducing candidate variables when that solution is sparse.

5. Statistical Performance Guarantees

The paper analyzes the sparse policy estimator under bounded features, noise regularity, and a restricted eigenvalue condition. It establishes finite-sample estimation, out-of-sample risk, and support-recovery guarantees whose behavior depends on sparsity and sample size.

  • Assumptions: The statistical analysis assumes bounded augmented covariates, regular noise behavior, and a restricted eigenvalue condition for sparse identifiability.These assumptions are presented as standard in sparse statistical analysis.
  • Estimation Error: The finite-sample estimator converges toward the ground truth at a rate driven by sparsity rather than data dimension.The estimation error decreases as sample size increases under suitable ridge-parameter scaling.
  • Out-of-Sample Performance: The out-of-sample guarantee bounds the gap between the estimator’s population newsvendor risk and the optimal risk, with the gap vanishing as sample size grows.The result is stated under the same setup as the estimation-error theorem.
  • Support Recovery: With sufficiently large sample size, the estimator recovers the true support with probability at least 1−δ.The guarantee requires nonzero estimated coefficients on the true support and zero coefficients outside it.

6. Numerical Study

The numerical study compares exact, scalable, and ℓ1-based methods on synthetic newsvendor instances, evaluating computation, support recovery, parameter estimation, and out-of-sample cost. Results show trade-offs between computational effort and statistical performance, with exact and greedy methods generally strongest but exact optimization becoming difficult in high dimensions.

  • Exact algorithms: The perspective formulation outperforms Big-M on most instances, with the advantage increasing as ambient dimension D grows.This is consistent with its stronger continuous relaxation.
  • Exact algorithms: When D ∈{1000,2000}, both exact approaches often reach the prescribed time limit, showing that global optimization can be computationally demanding.The experiments use a 1800-second time limit, and some instances have no feasible solution within that limit.
  • Support recovery: Exact algorithms achieve the best support recovery, especially in high-dimensional, small-sample settings, while greedy generally outperforms continuous-relaxation and Lasso baselines.Support recovery is evaluated using FDP and NDP, for which smaller values indicate better performance.
  • Parameter estimation: Estimation accuracy improves as sample size n increases, with exact and greedy methods consistently outperforming continuous-relaxation and Lasso-based approaches.The comparison includes relative errors for estimated parameters across different sample sizes and signal-to-noise ratios.
  • Out-of-sample performance: Exact and greedy algorithms yield lower out-of-sample operational costs than continuous-relaxation and Lasso approaches, especially when the sparsity budget is underestimated.When the budget is overestimated, out-of-sample performance tends to stabilize.
  • Overall findings: The numerical findings demonstrate satisfactory parameter estimation and out-of-sample performance while using substantially fewer covariates and yielding interpretable decisions.The results are presented as a trade-off among computational effort, support-recovery accuracy, and statistical performance.

7. Real-world case study

The real-world case study evaluates sparse newsvendor models on retail sales data with 2,239 samples and 1,157 dimensions. With suitable regularization and sparsity budgets, variable selection approaches the full model’s performance while achieving interpretable decisions and the lowest reported out-of-sample operational costs.

  • Data and evaluation: The retail dataset contains n = 2239 samples and D = 1157 dimensions after preprocessing.The study uses 70% training and 30% testing splits across 20 independent trials.
  • Operational performance: The sparse framework’s out-of-sample performance approaches that of the full model as sparsity budget d increases.Models include the full model and hard-cardinality-constrained models under multiple sparsity levels.
  • Operational performance: With an appropriate ℓ2 regularization coefficient and sparsity budget, the framework attains the lowest out-of-sample operational costs among the evaluated models.The same configuration also yields interpretable decisions.
  • Selected features: The most persistent selected features are weekly customer purchase days for hardware products and the weekly number of active SKUs.The paper relates these features to weekend shopping habits and product-assortment breadth.
  • Selected features: Historical weekly transaction volume consistently appears as a strong predictor of future customer demand.The paper identifies transaction volume as highly correlated with future demand.
  • Selected features: Store location and type, along with selected store-month interactions, are important predictors, indicating heterogeneous effects across stores and time.Examples include store indicators, city, and interactions involving stores 9 and 44 with specific months.

8. Conclusion

The paper develops and analyzes variable selection for feature-based newsvendor models under a hard cardinality constraint. Its numerical results expose trade-offs among computational effort, support recovery, and out-of-sample operating cost, while identifying extensions for future work.

  • The framework studies variable selection for feature-based newsvendor models under a hard cardinality constraint on selected covariates.
  • The paper provides computational algorithms and statistical performance guarantees for the proposed framework.
  • Numerical results illustrate trade-offs among computational effort, support-recovery accuracy, and out-of-sample operating cost.
  • Future work includes extensions to nonlinear policy classes, more efficient algorithms, hyperparameter selection, and broader statistical settings.The broader settings include misspecified, heavy-tailed, dependent, and distributionally robust settings.

EC.1. Proof of Proposition 1

The proof establishes computational hardness by reducing Exact Cover by 3-Sets to the sparse empirical newsvendor problem. The constructed instance has an optimal solution corresponding exactly to an exact cover.

  • The NP-hardness proof reduces Exact Cover by 3-Sets to the sparse empirical newsvendor problem.
  • The reduction uses an incidence matrix and an error vector r = 1 − Aω to encode exact-cover feasibility.
  • Conversely, an optimal solution attaining the relevant bound has exactly d nonzero entries whose associated subsets form an exact cover.
  • An exact cover yields a feasible weight vector with ∥ω∥0 = d and objective value bounded by d/(2γ).

EC.2. Proof of Theorem 1

The Big-M and perspective formulations are equivalent for integer solutions, but the perspective formulation provides a stronger continuous relaxation. This strengthens the optimization model without changing its integer optimum.

  • Big-M and perspective reformulations have the same optimal value and are equivalent for integer solutions.
  • The two formulations differ when binary selection variables are relaxed from {0,1} to [0,1].
  • The perspective relaxation is stronger than the Big-M relaxation.

EC.3. Proof of Theorem 2

The appendix derives randomized-rounding and statistical guarantees through support-size control, risk concentration, and sparse-function complexity bounds. These arguments yield finite-sample risk and support-recovery results under the stated assumptions.

  • The randomized-rounding analysis controls the support size of the rounded solution using moment-generating-function bounds.
  • The proof reformulates the continuous relaxation through duality and a min-max representation before bounding rounding loss.
  • The global risk lower bound converts parameter error into excess risk under the stated assumptions.
  • Uniform risk concentration is established using covering numbers, empirical Rademacher complexity, symmetrization, and McDiarmid’s inequality.
  • The out-of-sample risk bound scales with dlog(eD/d) + 1 + log(2/δ).
  • When the true support has size d, feasibility and inclusion together imply exact support recovery: S∗ = supp(bωn).
Loading 2609.01544v1…