Open Problem: Lower Bounds for Boosting with Hadamard Matrices
Abstract
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(\sqrt\frac\log nt). A matching lower bound has been shown for random game matrices for t up to n^αwhere α∈(0,\frac12). 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.
Cite
Text
Nie et al. "Open Problem: Lower Bounds for Boosting with Hadamard Matrices." Annual Conference on Computational Learning Theory, 2013.Markdown
[Nie et al. "Open Problem: Lower Bounds for Boosting with Hadamard Matrices." Annual Conference on Computational Learning Theory, 2013.](https://mlanthology.org/colt/2013/nie2013colt-open/)BibTeX
@inproceedings{nie2013colt-open,
title = {{Open Problem: Lower Bounds for Boosting with Hadamard Matrices}},
author = {Nie, Jiazhong and Warmuth, Manfred K. and Vishwanathan, S. V. N. and Zhang, Xinhua},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2013},
pages = {1076-1079},
url = {https://mlanthology.org/colt/2013/nie2013colt-open/}
}