2016/06/02 by Zhivotovskiy, Nikita, Hanneke, Steve
#FOS: Mathematics #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.1606.00922
In this paper we introduce an alternative localization approach for binary classification that leads to a novel complexity measure: fixed points of the local empirical entropy. We show that this complexity measure gives a tight control over complexity in the upper bounds. Our results are accompanied by a novel minimax lower bound that involves the same quantity. In particular, we practically answer the question of optimality of ERM under bounded noise for general VC classes.