Open Problem: Lower bounds for Boosting with Hadamard Matrices

Jiazhong Nie, Manfred K. Warmuth, S.V.N. Vishwanathan, Xinhua Zhang
Proceedings of the 26th Annual Conference on Learning Theory, PMLR 30:1076-1079, 2013.

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 this Paper

BibTeX
@InProceedings{pmlr-v30-Nie13, 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 = {Proceedings of the 26th Annual Conference on Learning Theory}, pages = {1076--1079}, year = {2013}, editor = {Shalev-Shwartz, Shai and Steinwart, Ingo}, volume = {30}, series = {Proceedings of Machine Learning Research}, address = {Princeton, NJ, USA}, month = {12--14 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v30/Nie13.pdf}, url = {https://proceedings.mlr.press/v30/Nie13.html}, 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.} }
Endnote
%0 Conference Paper %T Open Problem: Lower bounds for Boosting with Hadamard Matrices %A Jiazhong Nie %A Manfred K. Warmuth %A S.V.N. Vishwanathan %A Xinhua Zhang %B Proceedings of the 26th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2013 %E Shai Shalev-Shwartz %E Ingo Steinwart %F pmlr-v30-Nie13 %I PMLR %P 1076--1079 %U https://proceedings.mlr.press/v30/Nie13.html %V 30 %X 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.
RIS
TY - CPAPER TI - Open Problem: Lower bounds for Boosting with Hadamard Matrices AU - Jiazhong Nie AU - Manfred K. Warmuth AU - S.V.N. Vishwanathan AU - Xinhua Zhang BT - Proceedings of the 26th Annual Conference on Learning Theory DA - 2013/06/13 ED - Shai Shalev-Shwartz ED - Ingo Steinwart ID - pmlr-v30-Nie13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 30 SP - 1076 EP - 1079 L1 - http://proceedings.mlr.press/v30/Nie13.pdf UR - https://proceedings.mlr.press/v30/Nie13.html AB - 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. ER -
APA
Nie, J., Warmuth, M.K., Vishwanathan, S. & Zhang, X.. (2013). Open Problem: Lower bounds for Boosting with Hadamard Matrices . Proceedings of the 26th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 30:1076-1079 Available from https://proceedings.mlr.press/v30/Nie13.html.

Related Material