Can we globally optimize cross-validation loss? Quasiconvexity in ridge regression
This addresses a fundamental issue in hyperparameter tuning for practitioners using ridge regression, revealing limitations in optimization tractability, though it is incremental as it builds on prior research on CV loss properties.
The paper tackles the problem of whether cross-validation loss can be globally optimized in ridge regression, finding that it may fail to be quasiconvex and have multiple local optima, with quasiconvexity guaranteed only under specific conditions like a nearly flat covariate matrix spectrum and low noise.
Models like LASSO and ridge regression are extensively used in practice due to their interpretability, ease of use, and strong theoretical guarantees. Cross-validation (CV) is widely used for hyperparameter tuning in these models, but do practical optimization methods minimize the true out-of-sample loss? A recent line of research promises to show that the optimum of the CV loss matches the optimum of the out-of-sample loss (possibly after simple corrections). It remains to show how tractable it is to minimize the CV loss. In the present paper, we show that, in the case of ridge regression, the CV loss may fail to be quasiconvex and thus may have multiple local optima. We can guarantee that the CV loss is quasiconvex in at least one case: when the spectrum of the covariate matrix is nearly flat and the noise in the observed responses is not too high. More generally, we show that quasiconvexity status is independent of many properties of the observed data (response norm, covariate-matrix right singular vectors and singular-value scaling) and has a complex dependence on the few that remain. We empirically confirm our theory using simulated experiments.