A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-L1-Norm Interpolated Classifiers

Download:

Abstract:

This paper establishes a precise high-dimensional asymptotic theory for Boosting on separable data, taking statistical and computational perspectives. We consider the setting where the number of features (weak learners) $p$ scales with the sample size $n$, in an over-parametrized regime. On the statistical front, we provide an exact analysis of the generalization error of Boosting, when the algorithm interpolates the training data and maximizes an empirical $L_1$ margin. The angle between the Boosting solution and the ground truth is characterized explicitly. On the computational front, we provide a sharp analysis of the stopping time when Boosting approximately maximizes the empirical $L_1$ margin. Furthermore we discover that, the larger the margin, the smaller the proportion of active features (with zero initialization). At the heart of our theory lies a detailed study of the maximum $L_1$ margin, using tools from convex geometry. The maximum $L_1$ margin can be precisely described by a new system of non-linear equations, which we study using a novel uniform deviation argument. Preliminary numerical results are presented to demonstrate the accuracy of our theory.

Citation

Tengyuan Liang, and Pragya Sur. 2022. “A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-L1-Norm Interpolated Classifiers.” The Annals of Statistics 50 (3): 1669-1695.

@article{Liang_2022,
   title={A precise high-dimensional asymptotic theory for boosting and minimum-ℓ1-norm interpolated classifiers},
   volume={50},
   ISSN={0090-5364},
   url={http://dx.doi.org/10.1214/22-AOS2170},
   DOI={10.1214/22-aos2170},
   number={3},
   journal={The Annals of Statistics},
   publisher={Institute of Mathematical Statistics},
   author={Liang, Tengyuan and Sur, Pragya},
   year={2022},
   month=jun }