IDEAS home Printed from https://ideas.repec.org/p/cor/louvrp/2594.html
   My bibliography  Save this paper

First-order methods of smooth convex optimization with inexact oracle

Author

Listed:
  • DEVOLDER, Olivier
  • GLINEUR, François
  • NESTEROV, Yurii

Abstract

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 accuracy 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 convex-concave saddle point problems, to the analysis of Modified Lagrangians, to the prox-method, and some others.
(This abstract was borrowed from another version of this item.)

Suggested Citation

  • DEVOLDER, Olivier & GLINEUR, François & NESTEROV, Yurii, 2014. "First-order methods of smooth convex optimization with inexact oracle," LIDAM Reprints CORE 2594, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvrp:2594
    Note: In : Mathematical Programming Series A, 146(1-2), 37-75, 2014
    as

    Download full text from publisher

    To our knowledge, this item is not available for download. To find whether it is available, there are three options:
    1. Check below whether another version of this item is available online.
    2. Check on the provider's web page whether it is in fact available.
    3. Perform a search for a similarly titled item that would be available.

    Other versions of this item:

    References listed on IDEAS

    as
    1. Belleflamme,Paul & Peitz,Martin, 2015. "Industrial Organization," Cambridge Books, Cambridge University Press, number 9781107687899, September.
    2. DEVOLDER, Olivier & GLINEUR, François & NESTEROV, Yurii, 2010. "Double smoothing technique for infinite-dimensional optimization problems with applications to optimal control," LIDAM Discussion Papers CORE 2010034, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. Pierre-Philippe Combes & Thierry Mayer & Jacques-François Thisse, 2008. "Economic Geography: The Integration of Regions and Nations," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) hal-00311000, HAL.
    4. Winfried Pohlmeier & Luc Bauwens & David Veredas, 2007. "High frequency financial econometrics. Recent developments," ULB Institutional Repository 2013/136223, ULB -- Universite Libre de Bruxelles.
    5. Florens, Jean-Pierre & Schwarz, Maik & Van Bellegem, Sébastien, 2010. "Nonparametric Frontier Estimation from Noisy Data," TSE Working Papers 10-179, Toulouse School of Economics (TSE).
    6. Huriot,Jean-Marie & Thisse,Jacques-François (ed.), 2009. "Economics of Cities," Cambridge Books, Cambridge University Press, number 9780521118279, October.
    7. GILLIS, Nicolas & GLINEUR, François, 2010. "On the geometric interpretation of the nonnegative rank," LIDAM Discussion Papers CORE 2010051, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. NESTEROV, Yu., 2005. "Excessive gap technique in nonsmooth convex minimization," LIDAM Reprints CORE 1818, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    9. Luc Bauwens & Winfried Pohlmeier & David Veredas (ed.), 2008. "High Frequency Financial Econometrics," Studies in Empirical Economics, Springer, number 978-3-7908-1992-2, March.
    10. NESTEROV, Yu., 2007. "Gradient methods for minimizing composite objective function," LIDAM Discussion Papers CORE 2007076, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    11. Schwarz, M. & Van Bellegem, S. & Florens, J.P., 2010. "Nonparametric frontier estimation from noisy data," LIDAM Discussion Papers ISBA 2010028, Université catholique de Louvain, Institute of Statistics, Biostatistics and Actuarial Sciences (ISBA).
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. AGRELL, Per & KASPERZEC, Roman, 2010. "Dynamic joint investments in supply chains under information asymmetry," LIDAM Discussion Papers CORE 2010085, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. NESTEROV, Yurii, 2011. "Random gradient-free minimization of convex functions," LIDAM Discussion Papers CORE 2011001, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. Luc Bauwens & Gary Koop & Dimitris Korobilis & Jeroen V.K. Rombouts, 2015. "The Contribution of Structural Break Models to Forecasting Macroeconomic Series," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 30(4), pages 596-620, June.
    4. Gautier, Axel & Wauthy, Xavier, 2012. "Competitively neutral universal service obligations," Information Economics and Policy, Elsevier, vol. 24(3), pages 254-261.
    5. Bouezmarni, Taoufik & Van Bellegem, Sébastien, 2009. "Nonparametric Beta Kernel Estimator for Long Memory Time Series," IDEI Working Papers 633, Institut d'Économie Industrielle (IDEI), Toulouse.
    6. Pierre Pestieau & Maria Racionero, 2015. "Tagging with leisure needs," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 45(4), pages 687-706, December.
    7. Bréchet, Thierry & Jouvet, Pierre-André & Rotillon, Gilles, 2013. "Tradable pollution permits in dynamic general equilibrium: Can optimality and acceptability be reconciled?," Ecological Economics, Elsevier, vol. 91(C), pages 89-97.
    8. Cremer, Helmuth & Gahvari, Firouz & Pestieau, Pierre, 2011. "Fertility, human capital accumulation, and the pension system," Journal of Public Economics, Elsevier, vol. 95(11), pages 1272-1279.
    9. Leroux, Marie-Louise & Ponthiere, Gregory, 2013. "Utilitarianism and unequal longevities: A remedy?," Economic Modelling, Elsevier, vol. 30(C), pages 888-899.
    10. A. Mauleon & Vincent Vannetelbosch & Cecilia Vergari, 2014. "Unions' Relative Concerns And Strikes In Wage Bargaining," Bulletin of Economic Research, Wiley Blackwell, vol. 66(4), pages 374-383, October.
    11. M.-L. Leroux & P. Pestieau, 2012. "The political economy of derived pension rights," International Tax and Public Finance, Springer;International Institute of Public Finance, vol. 19(5), pages 753-776, October.
    12. Per J. Agrell & Axel Gautier, 2017. "A Theory of Soft Capture," Scandinavian Journal of Economics, Wiley Blackwell, vol. 119(3), pages 571-596, July.
    13. Manzi, Jorge & San Martin, Ernesto & Van Bellegem, Sébastien, 2010. "School System Evaluation By Value-Added Analysis under Endogeneity," IDEI Working Papers 631, Institut d'Économie Industrielle (IDEI), Toulouse.
    14. Michel Le Breton & Juan Moreno-Ternero & Alexei Savvateev & Shlomo Weber, 2013. "Stability and fairness in models with a multiple membership," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(3), pages 673-694, August.
    15. Luc Bauwens & Christian M. Hafner & Diane Pierret, 2013. "Multivariate Volatility Modeling Of Electricity Futures," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 28(5), pages 743-761, August.
    16. Florens, Jean-Pierre & Schwarz, Maik & Van Bellegem, Sébastien, 2010. "Nonparametric Frontier Estimation from Noisy Data," IDEI Working Papers 625, Institut d'Économie Industrielle (IDEI), Toulouse.
    17. Bauwens, Luc & Dufays, Arnaud & Rombouts, Jeroen V.K., 2014. "Marginal likelihood for Markov-switching and change-point GARCH models," Journal of Econometrics, Elsevier, vol. 178(P3), pages 508-522.
    18. STEPHAN, Rüdiger, 2010. "An extension of disjunctive programming and its impact for compact tree formulations," LIDAM Discussion Papers CORE 2010045, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    19. Jacques-François Thisse, 2011. "Geographical Economics: A Historical Perspective," Recherches économiques de Louvain, De Boeck Université, vol. 77(2), pages 141-168.
    20. GILLIS, Nicolas & GLINEUR, François, 2010. "On the geometric interpretation of the nonnegative rank," LIDAM Discussion Papers CORE 2010051, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:cor:louvrp:2594. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.