Open Problem: Lower bounds for Boosting with Hadamard Matrices
Jiazhong Nie, Manfred K. Warmuth, S. V. N. Vishwanathan, Xinhua Zhang · 2013
Boosting algorithms can be viewed as a zero-sum game. At each iteration a new column / hypothesis is chosen from a game matrix representing the entire hypotheses class. There are algorithms for which the gap between the value of the sub-matrix (the t columns chosen so far) and the value of the entire game matrix is O( logn t). A matching lower bound has been shown for random game matrices for t up to nα where α ∈ (0, 12). We conjecture that with Hadamard matrices we can build a certain game matrix for which the game value grows at the slowest possible rate for t up to a fraction of n. 1. Boosting as a zero-sum game Boosting algorithms follow the following protocol in each iteration (e.g. Freund and Schapire, 1997; Freund, 1995): The algorithm provides a distribution d on a given set of n examples. Then an oracle provides “weak hypothesis ” from some hypotheses class and the distribution is updated. At the end, the algorithm outputs a convex combination w of the hypotheses