-

 

 

 




Optimization Online





 

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

Pavel Dvurechensky(pavel.dvurechensky***at***gmail.com)
Alexander Gasnikov(gasnikov***at***yandex.ru)
Alexander Tiurin(alexandertiurin***at***gmail.com)

Abstract: 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. We focus on accelerated random block-coordinate descent, accelerated random directional search, accelerated random derivative-free method and, using our framework, provide their versions for problems with inexact oracle information. Our contribution also includes accelerated random block-coordinate descent with inexact oracle and entropy proximal setup as well as derivative-free version of this method.

Keywords: convex optimization, accelerated random block-coordinate descent, accelerated random directional search, accelerated random derivative-free method, inexact oracle, complexity, accelerated gradient descent methods, first-order methods, zero-order methods

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation:

Download: [PDF]

Entry Submitted: 07/31/2017
Entry Accepted: 07/31/2017
Entry Last Modified: 07/31/2017

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society