期刊名称：CORE Discussion Papers / Center for Operations Research and Econometrics (UCL), Louvain
出版年度：2011
卷号：2011
期号：1
出版社：Center for Operations Research and Econometrics (UCL), Louvain
摘要：In this paper, we analyze different first-order methods of smooth convex
optimization employing inexact first-order information. We introduce the notion of
an approximate first-order oracle. The list of examples of such an oracle includes
smoothing technique, Moreau-Yosida regularization, Modified Lagrangians, and
many others. For different methods, we derive complexity estimates and study the
dependence of the desired ac- curacy in the objective function and the accuracy of
the oracle. It appears that in inexact case, the superiority of the fast gradient
methods over the classical ones is not anymore absolute. Contrary to the simple
gradient schemes, fast gradient methods necessarily suffer from accumulation of
errors. Thus, the choice of the method depends both on desired accuracy and
accuracy of the oracle. We present applications of our results to smooth convexconcave
saddle point problems, to the analysis of Modified Lagrangians, to the
prox-method, and some others.
