In boosting one maintains a distribution d_i, i = 1,..,N, over a set of examples {x_i, y_i}, i=1,...,N. At each iteration a “weak hypothesis” is obtained from the base learning algorithm using the distribution, which is updated in a second step. There exist many algorithms differing in how they update the distribution and combine the hypotheses. For some of these algorithms, in particular for AdaBoost, convergence rates have been proven showing how fast they converge to the optimum. However, these algorithms can be very slow in practice and are very sensitive with respect to noise in the training data. Other approaches, most notably LPBoost, are noise robust, but there exist no guarantees on their convergence speed. It is the goal of this work to develop new algorithms that combine the benefits of the different approaches: good convergence rates, fast empirical convergence and state-of-the-art accuracy.