A Survey of old and New Results for the Test Error Estimation of a Classifier <s> Maurer-Pontil Bound <s> Algorithms based on upper confidence bounds for balancing exploration and exploitation are gaining popularity since they are easy to implement, efficient and effective. This paper considers a variant of the basic algorithm for the stochastic, multi-armed bandit problem that takes into account the empirical variance of the different arms. In earlier experimental works, such algorithms were found to outperform the competing algorithms. We provide the first analysis of the expected regret for such algorithms. As expected, our results show that the algorithm that uses the variance estimates has a major advantage over its alternatives that do not use such estimates provided that the variances of the payoffs of the suboptimal arms are low. We also prove that the regret concentrates only at a polynomial rate. This holds for all the upper confidence bound based algorithms and for all bandit problems except those special ones where with probability one the payoff obtained by pulling the optimal arm is larger than the expected payoff for the second best arm. Hence, although upper confidence bound bandit algorithms achieve logarithmic expected regret rates, they might not be suitable for a risk-averse decision maker. We illustrate some of the results by computer simulations. <s> BIB001 </s> A Survey of old and New Results for the Test Error Estimation of a Classifier <s> Maurer-Pontil Bound <s> We give improved constants for data dependent and variance sensitive confidence bounds, called empirical Bernstein bounds, and extend these inequalities to hold uniformly over classes of functionswhose growth function is polynomial in the sample size n. The bounds lead us to consider sample variance penalization, a novel learning method which takes into account the empirical variance of the loss function. We give conditions under which sample variance penalization is effective. In particular, we present a bound on the excess risk incurred by the method. Using this, we argue that there are situations in which the excess risk of our method is of order 1/n, while the excess risk of empirical risk minimization is of order 1/sqrt/{n}. We show some experimental results, which confirm the theory. Finally, we discuss the potential application of our results to sample compression schemes. <s> BIB002
Because of the application of the upper-bound of Eq. (31) in Eq. (39), the estimation of the generalization error through the Bernstein approach requires a numerical procedure for computing the unluckiness factor ∆( f , X , δ). Recently, a new bound has been proposed, which overcomes this problem by exploiting the sample variance instead of the true one BIB001 BIB002 : This last inequality can be considered an empirical formulation of the Bernstein bound, which is still rigorous but explicit and, therefore, easy to compute. Because of the application of the upper-bound of Eq. (31) in Eq. (39), the estimation of the generalization error through the Bernstein approach requires a numerical procedure for computing the unluckiness factor ∆( f , X , δ). Recently, a new bound has been proposed, which overcomes this problem by exploiting the sample variance instead of the true one BIB001 BIB002 : This last inequality can be considered an empirical formulation of the Bernstein bound, which is still rigorous but explicit and, therefore, easy to compute.