AdaBoost, proposed by Freund and Schapire [1]}, is an algorithm where an additive model for an unnormalized version of \(\beta ^*\)  is built by iteratively adding weak classifiers to the model. To facilitate our analysis, we assume that the features \(X_i\)  are i.i.d. Gaussian and that the weak classifiers can be identified with the standard basis vectors in \(\mathbb {R}^p\) . We consider AdaBoost as described in Algorithm REF . The main difference to the original proposal by [1]} consists of the choice of the step-size \(\alpha _t\) , which is obtained by minimizing a quadratic upper bound for the loss-function at each step [3]}.
[h]
Binary data \(Y_{i}, ~i=1, \dots , n\) , features \(X_{ji}\) , \(i=1, \dots , n, j=1, \dots , p\) , run-time \(T\) , learning rate \(\epsilon \)  
Vector \(\tilde{\beta }\in \mathbb {R}^p\) 
Initialize \(\tilde{\beta }_{0,i}=0\)  and rescale features \(X=X/\Vert X\Vert _\infty \)
