Universal intermediate gradient method for convex problems with inexact oracle
From MaRDI portal
Publication:5865342
DOI10.1080/10556788.2019.1711079zbMATH Open1493.90132arXiv1712.06036OpenAlexW2998975330WikidataQ126332543 ScholiaQ126332543MaRDI QIDQ5865342FDOQ5865342
Authors: Dmitry Kamzolov, Pavel Dvurechensky, Alexander V. Gasnikov 
Publication date: 13 June 2022
Published in: Optimization Methods \& Software (Search for Journal in Brave)
Abstract: In this paper, we propose new first-order methods for minimization of a convex function on a simple convex set. We assume that the objective function is a composite function given as a sum of a simple convex function and a convex function with inexact H"older-continuous subgradient. We propose Universal Intermediate Gradient Method. Our method enjoys both the universality and intermediateness properties. Following the paper by Y. Nesterov (Math.Prog., 2015) on Universal Gradient Methods, our method does not require any information about the H"older parameter and constant and adjusts itself automatically to the local level of smoothness. On the other hand, in the spirit of the preprint by O. Devolder, F.Glineur, and Y. Nesterov (CORE DP 2013/17), our method is intermediate in the sense that it interpolates between Universal Gradient Method and Universal Fast Gradient Method. This allows to balance the rate of convergence of the method and rate of the oracle error accumulation. Under additional assumption of strong convexity of the objective, we show how the restart technique can be used to obtain an algorithm with faster rate of convergence.
Full work available at URL: https://arxiv.org/abs/1712.06036
Recommendations
- Stochastic intermediate gradient method for convex problems with stochastic inexact oracle
- Universal gradient methods for convex optimization problems
- Stochastic intermediate gradient method for convex optimization problems
- First-order methods of smooth convex optimization with inexact oracle
- A universal modification of the linear coupling method
Convex programming (90C25) Minimax problems in mathematical programming (90C47) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Gradient methods for minimizing composite functions
- The ordered subsets mirror descent optimization method with applications to tomography
- Title not available (Why is that?)
- Smooth Optimization with Approximate Gradient
- First-order methods of smooth convex optimization with inexact oracle
- An optimal method for stochastic composite optimization
- Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization
- Universal gradient methods for convex optimization problems
- Stochastic intermediate gradient method for convex problems with stochastic inexact oracle
- Optimal methods of smooth convex minimization
- Fast Primal-Dual Gradient Method for Strongly Convex Minimization Problems with Linear Constraints
- Stochastic intermediate gradient method for convex optimization problems
- Generalized uniformly optimal methods for nonlinear programming
- Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints
- Restarting the accelerated coordinate descent method with a rough strong convexity estimate
- Adaptive restart of accelerated gradient methods under local quadratic growth condition
- Gradient methods for problems with inexact model of the objective
- Fast gradient descent for convex minimization problems with an oracle producing a \(( \delta, L)\)-model of function at the requested point
- Accelerated primal-dual gradient descent with linesearch for convex, nonconvex, and nonsmooth optimization problems
- Universal method of searching for equilibria and stochastic equilibria in transportation networks
- A stable alternative to Sinkhorn's algorithm for regularized optimal transport
Cited In (9)
- Inexact model: a framework for optimization and variational inequalities
- Multistage transportation model and sufficient conditions for its potentiality
- Improved exploitation of higher order smoothness in derivative-free optimization
- Title not available (Why is that?)
- Generalized mirror prox algorithm for monotone variational inequalities: Universality and inexact oracle
- Accelerated gradient methods with absolute and relative noise in the gradient
- Gradient-Free Methods with Inexact Oracle for Convex-Concave Stochastic Saddle-Point Problem
- The Walrasian equilibrium and centralized distributed optimization in terms of modern convex optimization methods on the example of resource allocation problem
- An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimization
Uses Software
This page was built for publication: Universal intermediate gradient method for convex problems with inexact oracle
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5865342)
