The greedy heuristic for the ℓ₀-constrained feature-based newsvendor has no approximation guarantee

Abstract

Yuan and Wang (arXiv:2609.01544) select features for a linear newsvendor decision rule by minimising the empirical newsvendor (pinball) loss plus a ridge term under a hard sparsity constraint |ω|₀ ≤ d, and propose a greedy heuristic for the resulting support-selection problem min_(|S| ≤ d)G(S). They leave the approximation quality of the greedy iterate as an open question, noting that G is not submodular. We answer the question in the negative. On an explicit instance with three features, four samples, budget d=2 and unit costs, every greedy run, under every tie-breaking rule, ends at a support of value at least 1/2 while the optimal support has value at most 1/γ, for every ridge parameter γ ≥ 8; the loss ratio is therefore at least γ/2 and no constant-factor guarantee exists. The same instance breaks the guarantee in the gain form used by the weak-submodularity literature: the greedy gain is strictly below 1-1/e times the optimal gain for every γ ≥ 8, and G has increasing marginal returns. At γ=8 all seven values of G are determined exactly, each by a matching primal–dual pair, and the ratio is exactly 6. We also explain why the question was genuinely open: the standard lower bound on the submodularity ratio requires a differentiable loss with a finite restricted-smoothness constant, and the pinball loss has none. Every value certificate rests on a weak-duality inequality proved from first principles; strong duality is never assumed. All theorems are verified in Lean 4 with Mathlib.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-09-07 03:53 UTC

   File fingerprint

   e0032f9816c22a25197cfe5fe3547ae3474b8fe456b0676f8574046b693cb7fd