Variable Selection for Feature-Based Newsvendor

Sparse recovery is among the most well-studied problems in learning theory and high-dimensional statistics. In this work, we investigate the statistical and computational landscapes of sparse recovery with $\ell_\infty$ error guarantees. This variant of the problem is motivated by \emph{variable selection} tasks, where the goal is to estimate the support of a $k$-sparse signal in $\mathbb{R}^d$. Our main contribution is a provable separation between the \emph{oblivious} (for each'') and \emph{adaptive} (for all'') models of $\ell_\infty$ sparse recovery. We show that under an oblivious model, the optimal $\ell_\infty$ error is attainable in near-linear time with $\approx k\log d$ samples, whereas in an adaptive model, $\gtrsim k^2$ samples are necessary for any algorithm to achieve this bound. This establishes a surprising contrast with the standard $\ell_2$ setting, where $\approx k \log d$ samples suffice even for adaptive sparse recovery. We conclude with a preliminary examination of a \emph{partially-adaptive} model, where we show nontrivial variable selection guarantees are possible with $\approx k\log d$ measurements.

Feature rankings are widely used in supervised feature selection because they are simple, scalable and easy to interpret. Variables are first ranked by a relevance score, and a subset is then obtained by retaining the top-ranked variables. Although the first stage has been extensively studied, the second is often governed by an arbitrary cardinality, an empirical threshold or cross-validation, without a direct interpretation. This raises a basic question: given a feature ranking, when is there enough accumulated class-separation evidence to stop selecting features? This paper develops a distributional framework for transforming supervised feature rankings into class-independent subsets through an explicit risk-calibrated stopping rule. For each variable and each pair of classes, marginal separation is measured by the Bhattacharyya coefficient between the corresponding class-conditional distributions. The proposed method selects a single global subset shared by all classes by retaining the shortest prefix of a ranking whose residual product overlap falls below a prescribed threshold for every relevant class contrast. We derive binary and multiclass Bayes-risk bounds for the labelled product marginal problem, and obtain prior-dependent and prior-free calibrations of the residual-overlap threshold from a target all-pairs risk level. An empirical comparison on high-dimensional genomic datasets illustrates that the rule can reduce tens of thousands of variables to a few dozen while maintaining predictive performance statistically comparable to the all-features baseline. As the stopping rule only requires one-dimensional marginal overlap estimates and scans a precomputed ranking, it is well suited to very high-dimensional settings where exhaustive subset search is infeasible and interpretable truncation of feature rankings is essential.

We present Variance-Preserving Orthogonal Selection (VPOS), an unsupervised feature-selection method that performs sequential orthogonal deflation in the variance-weighted principal component analysis (PCA) loading space $\mathbf{V}_d\mathbfΛ_d^{1/2}$. After each feature is selected, its loading direction is projected out of all remaining candidates, so subsequent selections cover complementary directions of the rank-$d$ covariance approximation while returning original variables. We establish rank-reduction guarantees and a determinant-growth interpretation, and distinguish VPOS from greedy selection on raw data, unweighted eigenvector pivoting, Principal Feature Analysis (PFA), and Principal Variable Selection (PVS). Experiments enforce $k\leq d$, tune method-specific parameters on validation observations, and evaluate on unseen outer folds. Across seven labelled benchmarks, VPOS improves held-out normalised reconstruction error over matched PCA without deflation on every dataset, with reductions of 1--78%. It obtains the lowest mean reconstruction error on Wine, Breast Cancer, and MNIST and is within 1.7% of the lowest error on CIFAR-10 and HighDim. On CIFAR-10, VPOS is approximately 24$\times$ faster than the closely related PVS baseline while incurring a 1.7% reconstruction gap. These results establish VPOS as an efficient covariance-coverage method, particularly when correlated high-dimensional data must be represented by a small set of identifiable original variables.