66 citations · 525 across the 94 of their papers we have counts for
12 papers · 1 filter
Composite optimization for the resource allocation problem
Anastasiya Ivanova, Pavel Dvurechensky, Alexander Gasnikov +1
In this paper we consider resource allocation problem stated as a convex minimization problem with linear constraints. To solve this problem, we use gradient and accelerated gradie…
Mirror Descent and Constrained Online Optimization Problems
Alexander Titov, Fedor Stonyakin, Alexander Gasnikov +1
We consider the following class of online optimization problems with functional constraints. Assume, that a finite set of convex Lipschitz-continuous non-smooth functionals are giv…
Primal-dual accelerated gradient methods with small-dimensional relaxation oracle
Yurii Nesterov, Alexander Gasnikov, Sergey Guminov +1
In this paper, a new variant of accelerated gradient descent is proposed. The pro-posed method does not require any information about the objective function, usesexact line search…
A Dual Approach for Optimal Algorithms in Distributed Optimization over Networks
César A. Uribe, Soomin Lee, Alexander Gasnikov +1
We study dual-based algorithms for distributed convex optimization problems over networks, where the objective is to minimize a sum of functions over in a ne…
The global rate of convergence for optimal tensor methods in smooth convex optimization
Alexander Gasnikov, Pavel Dvurechensky, Eduard Gorbunov +3
We consider convex optimization problems with the objective function having Lipshitz-continuous -th order derivative, where . We propose a new tensor method, which clos…
Generalized Mirror Prox for Monotone Variational Inequalities: Universality and Inexact Oracle
Fedor Stonyakin, Alexander Gasnikov, Pavel Dvurechensky +2
We introduce an inexact oracle model for variational inequalities (VI) with monotone operator, propose a numerical method which solves such VI's and analyze its convergence rate. A…
Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters
Pavel Dvurechensky, Darina Dvinskikh, Alexander Gasnikov +2
We study the decentralized distributed computation of discrete approximations for the regularized Wasserstein barycenter of a finite set of continuous probability measures distribu…
On the upper bound for the mathematical expectation of the norm of a vector uniformly distributed on the sphere and the phenomenon of concentration of uniform measure on the sphere
Eduard Gorbunov, Evgeniya Vorontsova, Alexander Gasnikov
We considered the problem of obtaining upper bounds for the mathematical expectation of the -norm () of the vector which is uniformly distributed…
An Accelerated Directional Derivative Method for Smooth Stochastic Convex Optimization
Pavel Dvurechensky, Eduard Gorbunov, Alexander Gasnikov
We consider smooth stochastic convex optimization problems in the context of algorithms which are based on directional derivatives of the objective function. This context can be co…
Distributed Computation of Wasserstein Barycenters over Networks
César A. Uribe, Darina Dvinskikh, Pavel Dvurechensky +2
We propose a new \cu{class-optimal} algorithm for the distributed computation of Wasserstein Barycenters over networks. Assuming that each node in a graph has a probability distrib…
An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimization
Eduard Gorbunov, Pavel Dvurechensky, Alexander Gasnikov
We consider an unconstrained problem of minimizing a smooth convex function which is only available through noisy observations of its values, the noise consisting of two parts. Sim…
Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm
Pavel Dvurechensky, Alexander Gasnikov, Alexey Kroshnin
We analyze two algorithms for approximating the general optimal transport (OT) distance between two discrete distributions of size , up to accuracy . For the first…