Ridge regularized sparse regression involves selecting a subset of features
that explains the relationship between a design matrix and an output vector in
an interpretable manner. To select the sparsity and robustness of linear
regressors, techniques like leave-one-out cross-validation are commonly used
for hyperparameter tuning. However, cross-validation typically increases the
cost of sparse regression by several orders of magnitude. Additionally,
validation metrics are noisy estimators of the test-set error, with different
hyperparameter combinations giving models with different amounts of noise.
Therefore, optimizing over these metrics is vulnerable to out-of-sample
disappointment, especially in underdetermined settings. To address this, we
make two contributions. First, we leverage the generalization theory literature
to propose confidence-adjusted variants of leave-one-out that display less
propensity to out-of-sample disappointment. Second, we leverage ideas from the
mixed-integer literature to obtain computationally tractable relaxations of
confidence-adjusted leave-one-out, thereby minimizing it without solving as
many MIOs. Our relaxations give rise to an efficient coordinate descent scheme
which allows us to obtain significantly lower leave-one-out errors than via
other methods in the literature. We validate our theory by demonstrating we
obtain significantly sparser and comparably accurate solutions than via popular
methods like GLMNet and suffer from less out-of-sample disappointment. On
synthetic datasets, our confidence adjustment procedure generates significantly
fewer false discoveries, and improves out-of-sample performance by 2-5%
compared to cross-validating without confidence adjustment. Across a suite of
13 real datasets, a calibrated version of our procedure improves the test set
error by an average of 4% compared to cross-validating without confidence
adjustment.

提出了一种通过引入置信度修正的变化来减少交叉验证过程中的过度期望风险， 及从混合整数规划中获得可计算的放松， 从而最小化 leave-one-out 误差的方法， 能够比现有方法更快地得到更少误差的结果。