How to allocate a restricted budget of leave-one-out assessments for effective model selection in machine learning: A comparison of state-of-art techniques

The problem of selecting the best among several alternatives in a stochastic context has been the object of researcli in several domains: stochastic optimization, discrete-event stochastic simulation, experimental design. A particular instance of this problem is of particular relevance in machine learning where the search of the model which could best represent a finite set of data asks for comparing several alternatives on the basis of a finite set of noisy data. This paper aims to bridge a gap between these different communities by comparing experimentally the effectiveness of techniques proposed in the simulation and in the stochastic dynamic programming community in performing a model selection task. In particular, we will consider here a model selection task in regression where the alternatives are represented by a finite set of K-nearest neighbors models with different values of the structural parameter K. The techniques we compare are i) a two-stage selection technique proposed in the stochastic simulation community, ii) a stochastic dynamic programming approach conceived to address the multi-armed bandit problem, iii) a racing method, iv) a greedy approach, v) a round-search technique.SCOPUS: cp.p