Our contributions include two general tools. The first is a scheme for boosting the performance of iterative solvers for continuous optimization problems. These boosters use recursive composition to achieve residual error that decreases exponentially in the number of iterations of the solver.
The second is a technique for designing iterative solvers that bypasses the infamous l∞ barrier for strongly convex regularization. Instead we introduce the notion of an area convex regularizer, and show that such regularizers suffice in designing good iterative solvers. Moreover, we show how to design regularizers satisfying this weaker property for the problem of approximately solving AX ≤ B over right stochastic X, which in turn implies the algorithm for maximum concurrent multi-commodity flow.