The main goal of this paper is to develop uniformly optimal first-order methods for large-scale convex programming (CP). By uniform optimality we mean that the first-order methods themselves do not require the input of any problem parameters, but can still achieve the best possible iteration complexity bounds. To this end, we provide a substantial generalization of the accelerated level method by Lan \cite{Lan10-2} and demonstrate that it can uniformly achieve the optimal iteration complexity for solving a class of generalized composite CP problems, which covers a wide range of CP problems, including the nonsmooth, weakly smooth, smooth, minmax, composite and regularized problems etc. Then, we present two variants of this level method for solving a class of structured CP problems with a bilinear saddle point structure due to Nesterov~\cite{Nest05-1}. We show that one of these variants can achieve the ${\cal O} (1/\epsilon)$ iteration complexity without requiring the input of any problem parameters. We illustrate the significant advantages of these level methods over some existing first-order methods for solving certain important classes of semidefinite programming (SDP) and two-stage stochastic programming (SP) problems.
Citation
Technical Report, Department of Industrial and Systems Engineering, University of Florida, April 2011.
Article
View Level methods uniformly optimal for composite and structured nonsmooth convex optimization