A Primal-Dual Convergence Analysis of Boosting, JMLR 13:561-606, 2012. (The arXiv version has internal hyperlinks.) The general convergence of boosting, for a variety of strictly convex losses, is \(\mathcal O(1/\epsilon)\); moreover if either weak learnability or (disjointly) attainability of the empirical risk infimum hold, the rate is \(\mathcal O(\ln( 1/\epsilon))\).

This version of the manuscript is quite lengthy, but dissects many issues, for instance the connection between the infinite/bounded decomposition and hard-core sets, the construction of the generalized weak learning rate, the choice of line search, and a few other things.

The Fast Convergence of Boosting, NIPS 2011. This is the short version of the above; although it lacks many of the connections, it is perhaps easier to skim.

Steepest Descent Analysis for Unregularized Linear Prediction with Strictly Convex Penalties, NIPS Optimization Workshop 2011 (video). This manuscript shows that the techniques from the boosting analysis carry over to other linear prediction problems, using any steepest descent method (gradient descent, coordinate descent, etc.).

Hartigan's method: \(k\)-means without Voronoi, with Andrea Vattani, in AISTATS, 2010. This manuscript studies basic aspects of Hartigan's method for \(k\)-means, which proceeds point-by-point, but accounts for the shift of a mean after a point is reassigned, thus allowing it to escape certain local optima of Lloyd's method.

Once upon a time, I implemented the algorithm in html canvas and javascript.

Signal decomposition using multiscale admixture models, with John Lafferty, In ICASSP, 2007.

Blackwell Approachability and Minimax Theory, 2011.

Central Binomial Tail Bounds, 2009.