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. |
Year | Venue | Field |
---|---|---|
2013 | COLT | Hadamard's maximal determinant problem,Mathematical optimization,Minimax,Hadamard matrix,Upper and lower bounds,Convex combination,Matrix (mathematics),Artificial intelligence,Hadamard's inequality,Machine learning,Block matrix,Mathematics |
DocType | Volume | Citations |
Conference | 30 | 0 |
PageRank | References | Authors |
0.34 | 4 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jiazhong Nie | 1 | 45 | 4.72 |
Manfred K. Warmuth | 2 | 6105 | 1975.48 |
S. V. N. Vishwanathan | 3 | 1991 | 131.90 |
Xinhua Zhang | 4 | 12 | 3.65 |