It is well-known that bundle-level methods (or their certain variants) exhibit an optimal rate of convergence, i.e., ${\cal O}(1/\sqrt{t})$, and also excellent practical performance for solving general non-smooth convex programming (CP) problems. However, this rate of convergence is significantly worse than the optimal one for solving smooth CP, i.e., ${\cal O}(1/t^2)$. In this paper, we present new bundle-type methods which are optimal, not only for non-smooth, but also for smooth convex programming problems. Interestingly, the optimal rates of convergence can be obtained without even knowing whether a CP problem is smooth or not.
Moreover, given that the problem is smooth, the methods do not require any smoothness information, such as, the Lipschitz constant. We demonstrate the superior practical performance of these methods over existing optimal first-order methods for convex programming, when the Lipschitz constant is big and/or the desired accuracy is high.
Copyright. All Rights Reserved.