66 citations · 525 across the 94 of their papers we have counts for
18 papers · 1 filter
Inexact Tensor Methods and Their Application to Stochastic Convex Optimization
Artem Agafonov, Dmitry Kamzolov, Pavel Dvurechensky +2
We propose general non-accelerated and accelerated tensor methods under inexact information on the derivatives of the objective, analyze their convergence rate. Further, we provide…
Tensor methods for strongly convex strongly concave saddle point problems and strongly monotone variational inequalities
Petr Ostroukhov, Rinat Kamalov, Pavel Dvurechensky +1
In this paper we propose three -th order tensor methods for -strongly-convex-strongly-concave saddle point problems (SPP). The first method is based on the assumption of -…
Recent Theoretical Advances in Non-Convex Optimization
Marina Danilova, Pavel Dvurechensky, Alexander Gasnikov +4
Motivated by recent increased interest in optimization algorithms for non-convex optimization in application to training deep neural networks and other optimization problems in dat…
Recent theoretical advances in decentralized distributed convex optimization
Eduard Gorbunov, Alexander Rogozin, Aleksandr Beznosikov +2
In the last few years, the theory of decentralized distributed convex optimization has made significant progress. The lower bounds on communications rounds and oracle calls have ap…
Distributed Optimization with Quantization for Computing Wasserstein Barycenters
Roman Krawtschenko, César A. Uribe, Alexander Gasnikov +1
We study the problem of the decentralized computation of entropy-regularized semi-discrete Wasserstein barycenters over a network. Building upon recent primal-dual approaches, we p…
Parallel and Distributed algorithms for ML problems
Darina Dvinskikh, Alexander Gasnikov, Alexander Rogozin +1
In this paper we make a survey of modern parallel and distributed approaches to solve sum-type convex minimization problems come from ML applications.
Solving strongly convex-concave composite saddle point problems with a small dimension of one of the variables
Egor Gladin, Ilya Kuruzov, Fedor Stonyakin +3
The article is devoted to the development of algorithmic methods ensuring efficient complexity bounds for strongly convex-concave saddle point problems in the case when one of the…
Zeroth-order methods for noisy Hölder-gradient functions
Innokentiy Shibaev, Pavel Dvurechensky, Alexander Gasnikov
In this paper, we prove new complexity bounds for zeroth-order methods in non-convex optimization with inexact observations of the objective function values. We use the Gaussian sm…
Stochastic Saddle-Point Optimization for Wasserstein Barycenters
Daniil Tiapkin, Alexander Gasnikov, Pavel Dvurechensky
We consider the population Wasserstein barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. This leads…
Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping
Eduard Gorbunov, Marina Danilova, Alexander Gasnikov
In this paper, we propose a new accelerated stochastic first-order method called clipped-SSTM for smooth convex stochastic optimization with heavy-tailed distributed noise in stoch…
Accelerated and nonaccelerated stochastic gradient descent with inexact model
Darina Dvinskikh, Alexander Tyurin, Alexander Gasnikov +1
In this paper, we propose a new way to obtain optimal convergence rates for smooth stochastic (strong) convex optimization tasks. Our approach is based on results for optimization…
Accelerated meta-algorithm for convex optimization
Alexander Gasnikov, Darina Dvinskikh, Pavel Dvurechensky +5
We propose an accelerated meta-algorithm, which allows to obtain accelerated methods for convex unconstrained minimization in different settings. As an application of the general s…
Multimarginal Optimal Transport by Accelerated Alternating Minimization
Nazarii Tupitsa, Pavel Dvurechensky, Alexander Gasnikov +1
We consider a multimarginal optimal transport, which includes as a particular case the Wasserstein barycenter problem. In this problem one has to find an optimal coupling between $…
Analogues of Switching Subgradient Schemes for Relatively Lipschitz-Continuous Convex Programming Problems
Alexander Titov, Fedor Stonyakin, Mohammad Alkousa +2
Recently some specific classes of non-smooth and non-Lipschitz convex optimization problems were selected by Yu.~Nesterov along with H.~Lu. We consider convex programming problems…
On the Optimal Combination of Tensor Optimization Methods
Dmitry Kamzolov, Alexander Gasnikov, Pavel Dvurechensky
We consider the minimization problem of a sum of a number of functions having Lipshitz -th order derivatives with different Lipschitz constants. In this case, to accelerate opti…
Near-Optimal Hyperfast Second-Order Method for convex optimization and its Sliding
Dmitry Kamzolov, Alexander Gasnikov
In this paper, we present a new Hyperfast Second-Order Method with convergence rate up to a logarithmic factor for the convex function with Lipshitz the third derivativ…
Oracle Complexity Separation in Convex Optimization
Anastasiya Ivanova, Evgeniya Vorontsova, Dmitry Pasechnyuk +4
Many convex optimization problems have structured objective function written as a sum of functions with different types of oracles (full gradient, coordinate derivative, stochastic…
Inexact Relative Smoothness and Strong Convexity for Optimization and Variational Inequalities by Inexact Model
Fedor Stonyakin, Alexander Tyurin, Alexander Gasnikov +7
In this paper, we propose a general algorithmic framework for first-order methods in optimization in a broad sense, including minimization problems, saddle-point problems, and vari…