Timezone: »

 
Poster
The power of first-order smooth optimization for black-box non-smooth problems
Alexander Gasnikov · Anton Novitskii · Vasilii Novitskii · Farshed Abdukhakimov · Dmitry Kamzolov · Aleksandr Beznosikov · Martin Takac · Pavel Dvurechenskii · Bin Gu

Wed Jul 20 03:30 PM -- 05:30 PM (PDT) @ Hall E #731
in Poster Session 2 »

Gradient-free/zeroth-order methods for black-box convex optimization have been extensively studied in the last decade with the main focus on oracle calls complexity. In this paper, besides the oracle complexity, we focus also on iteration complexity, and propose a generic approach that, based on optimal first-order methods, allows to obtain in a black-box fashion new zeroth-order algorithms for non-smooth convex optimization problems. Our approach not only leads to optimal oracle complexity, but also allows to obtain iteration complexity similar to first-order methods, which, in turn, allows to exploit parallel computations to accelerate the convergence of our algorithms. We also elaborate on extensions for stochastic optimization problems, saddle-point problems, and distributed optimization.

Keywords: OPT: Convex · OPT: Global Optimization · OPT: Stochastic · OPT: Zero-order and Black-box Optimization · T: Optimization

Author Information

Alexander Gasnikov (Moscow Institute of Physics and Technology)
Anton Novitskii (MIPT)
Vasilii Novitskii (MIPT)
Farshed Abdukhakimov (MBZUAI)
Dmitry Kamzolov (Mohamed bin Zayed University of Artificial Intelligence)
Aleksandr Beznosikov (Moscow Institute of Physics and Technology (National Research University))
Martin Takac (MBZUAI)
Pavel Dvurechenskii (Weierstrass Institute)

Graduated with honors from Moscow Institute of Physics and Technology. PhD on differential games in the same university. At the moment research associate in the area of optimization under inexact information in Berlin. Research interest include - algorithms for convex and non-convex large-scale optimization problems; - optimization under deterministic and stochastic inexact information; - randomized algorithms: random coordinate descent, random (derivative-free) directional search; - numerical aspects of Optimal Transport - Algorithms for saddle-point problems and variational inequalities

Bin Gu (Nanjing University of Information Science & Technology)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors