Fully-Corrective Gradient Boosting with Squared Hinge: Fast Learning Rates and Early Stopping
This provides a theoretical foundation for boosting methods in classification, addressing a gap in the literature with potential applications in robust machine learning, though it is incremental in combining existing techniques.
The paper tackles the lack of theoretical generalization guarantees for boosting in binary classification by proposing an efficient method with fully-corrective greedy updates, squared hinge loss, and ADMM optimization, achieving fast learning rates of O((m/log m)^{-1/4}) to O((m/log m)^{-1/2}) and demonstrating effectiveness in simulations and experiments.
Boosting is a well-known method for improving the accuracy of weak learners in machine learning. However, its theoretical generalization guarantee is missing in literature. In this paper, we propose an efficient boosting method with theoretical generalization guarantees for binary classification. Three key ingredients of the proposed boosting method are: a) the \textit{fully-corrective greedy} (FCG) update in the boosting procedure, b) a differentiable \textit{squared hinge} (also called \textit{truncated quadratic}) function as the loss function, and c) an efficient alternating direction method of multipliers (ADMM) algorithm for the associated FCG optimization. The used squared hinge loss not only inherits the robustness of the well-known hinge loss for classification with outliers, but also brings some benefits for computational implementation and theoretical justification. Under some sparseness assumption, we derive a fast learning rate of the order ${\cal O}((m/\log m)^{-1/4})$ for the proposed boosting method, which can be further improved to ${\cal O}((m/\log m)^{-1/2})$ if certain additional noise assumption is imposed, where $m$ is the size of sample set. Both derived learning rates are the best ones among the existing generalization results of boosting-type methods for classification. Moreover, an efficient early stopping scheme is provided for the proposed method. A series of toy simulations and real data experiments are conducted to verify the developed theories and demonstrate the effectiveness of the proposed method.