smooth convex optimization

A proximal-Newton method for unconstrained convex optimization in Hilbert spaces

  • M. Marques Alves
  • Benar Fux Svaiter
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    We propose and study the iteration-complexity of a proximal-Newton method for finding approximate solutions of the problem of minimizing a twice continuously differentiable convex function on a (possibly infinite dimensional) Hilbert space. We prove global convergence rates for obtaining approximate solutions in terms of function/gradient values. Our main results follow from an iteration-complexity study of … Read more

    Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods

  • François Glineur
  • Julien M. Hendrickx
  • Adrien B. Taylor
    • Categories Convex Optimization Tags , , ,

    We show that the exact worst-case performance of fixed-step first-order methods for unconstrained optimization of smooth (possibly strongly) convex functions can be obtained by solving convex programs. Finding the worst-case performance of a black-box first-order method is formulated as an optimization problem over a set of smooth (strongly) convex functions and initial conditions. We develop … Read more

    Global convergence of the Heavy-ball method for convex optimization

  • Hamid Reza Feyzmahdavian
  • Euhanna Ghadimi
  • Mikael Johansson
    • Categories Convex Optimization, Unconstrained Optimization Tags , , , , ,

    This paper establishes global convergence and provides global bounds of the convergence rate of the Heavy-ball method for convex optimization problems. When the objective function has Lipschitz-continuous gradient, we show that the Cesa ́ro average of the iterates converges to the optimum at a rate of $O(1/k)$ where k is the number of iterations. When … Read more

    Intermediate gradient methods for smooth convex problems with inexact oracle

  • Olivier Devolder
  • François Glineur
  • Yurii Nesterov
    • Categories Convex Optimization Tags , , , ,

    Between the robust but slow (primal or dual) gradient methods and the fast but sensitive to errors fast gradient methods, our goal in this paper is to develop first-order methods for smooth convex problems with intermediate speed and intermediate sensitivity to errors. We develop a general family of first-order methods, the Intermediate Gradient Method (IGM), … Read more

    First-order methods with inexact oracle: the strongly convex case

  • Olivier Devolder
  • François Glineur
  • Yurii Nesterov
    • Categories Convex Optimization Tags , , , ,

    The goal of this paper is to study the effect of inexact first-order information on the first-order methods designed for smooth strongly convex optimization problems. We introduce the notion of (delta,L,mu)-oracle, that can be seen as an extension of the inexact (delta,L)-oracle previously introduced, taking into account strong convexity. We consider different examples of (delta,L,mu)-oracle: … Read more

    Stochastic first order methods in smooth convex optimization.

  • Olivier Devolder
    • Categories Convex Optimization, Stochastic Programming Tags , , , , , ,

    In this paper, we are interested in the development of efficient first-order methods for convex optimization problems in the simultaneous presence of smoothness of the objective function and stochasticity in the first-order information. First, we consider the Stochastic Primal Gradient method, which is nothing else but the Mirror Descent SA method applied to a smooth … Read more

    First-order Methods of Smooth Convex Optimization with Inexact Oracle

  • Olivier Devolder
  • François Glineur
  • Yurii Nesterov
    • Categories Convex Optimization Tags , , , , ,

    We introduce the notion of inexact first-order oracle and analyze the behaviour of several first-order methods of smooth convex optimization used with such an oracle. This notion of inexact oracle naturally appears in the context of smoothing techniques, Moreau-Yosida regularization, Augmented Lagrangians and many other situations. We derive complexity estimates for primal, dual and fast … Read more