inexact oracle

Randomized Similar Triangles Method: A Unifying Framework for Accelerated Randomized Optimization Methods (Coordinate Descent, Directional Search, Derivative-Free Method)

  • Pavel Dvurechensky
  • Alexander Gasnikov
  • Alexander Tiurin
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , , , , , , ,

    In this paper, we consider smooth convex optimization problems with simple constraints and inexactness in the oracle information such as value, partial or directional derivatives of the objective function. We introduce a unifying framework, which allows to construct different types of accelerated randomized methods for such problems and to prove convergence rate theorems for them. … 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

    Nonsmooth Optimization Using Uncontrolled Inexact Information

  • Welington de Oliveira
  • Jérôme Malick
  • Sofia Zaourar
    • Categories Nonsmooth Optimization Tags , , , ,

    We consider convex nonsmooth optimization problems whose objective function is known through a (fine) oracle together with some additional (cheap but poor) information – formalized as a second coarse oracle with uncontrolled inexactness. It is the case when the objective function is itself the output of an optimization solver, using a branch-and-bound procedure, or decomposing … 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