66 citations · 450 across the 76 of their papers we have counts for
91 papers
Stochastic variance reduced extragradient methods for solving hierarchical variational inequalities
Pavel Dvurechensky, Andrea Ebner, Johannes Carl Schnebel +2
We are concerned with optimization in a broad sense through the lens of solving variational inequalities (VIs) -- a class of problems that are so general that they cover as particu…
Extragradient methods with complexity guarantees for hierarchical variational inequalities
Pavel Dvurechensky, Meggie Marschner, Shimrit Shtern +1
In the framework of a real Hilbert space we consider the problem of approaching solutions to a class of hierarchical variational inequality problems, subsuming several other proble…
On Solving Minimization and Min-Max Problems by First-Order Methods with Relative Error in Gradients
Artem Vasin, Valery Krivchenko, Dmitry Kovalev +6
First-order methods for minimization and saddle point (min-max) problems are widely used for solving large-scale problems, in particular arising in machine learning. The majority o…
Decentralised convex optimisation with probability-proportional-to-size quantization
Dmitrii Pasechniuk, Pavel Dvurechensky, César A. Uribe +1
Communication is one of the bottlenecks of distributed optimisation and learning. To overcome this bottleneck, we propose a novel quantization method that transforms a vector into…
Improved global performance guarantees of second-order methods in convex minimization
Pavel Dvurechensky, Yurii Nesterov
In this paper, we attempt to compare two distinct branches of research on second-order optimization methods. The first one studies self-concordant functions and barriers, the main…
Barrier Algorithms for Constrained Non-Convex Optimization
Pavel Dvurechensky, Mathias Staudigl
In this paper we theoretically show that interior-point methods based on self-concordant barriers possess favorable global complexity beyond their standard application area of conv…
Analysis of Kernel Mirror Prox for Measure Optimization
Pavel Dvurechensky, Jia-Jie Zhu
By choosing a suitable function space as the dual to the non-negative measure cone, we study in a unified framework a class of functional saddle-point optimization problems, which…
High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise
Eduard Gorbunov, Abdurakhmon Sadiev, Marina Danilova +5
High-probability analysis of stochastic first-order optimization methods under mild assumptions on the noise has been gaining a lot of attention in recent years. Typically, gradien…
Accuracy Certificates for Convex Minimization with Inexact Oracle
Egor Gladin, Alexander Gasnikov, Pavel Dvurechensky
Accuracy certificates for convex minimization problems allow for online verification of the accuracy of approximate solutions and provide a theoretically valid online stopping crit…
Intermediate Gradient Methods with Relative Inexactness
Nikita Kornilov, Eduard Gorbunov, Mohammad Alkousa +3
This paper is devoted to first-order algorithms for smooth convex optimization with inexact gradients. Unlike the majority of the literature on this topic, we consider the setting…
Algorithms for Euclidean-regularised Optimal Transport
Dmitry A. Pasechnyuk, Michael Persiianov, Pavel Dvurechensky +1
This paper addresses the Optimal Transport problem, which is regularized by the square of Euclidean -norm. It offers theoretical guarantees regarding the iteration complexi…
Gradient-Free Methods for Non-Smooth Convex Stochastic Optimization with Heavy-Tailed Noise on Convex Compact
Nikita Kornilov, Alexander Gasnikov, Pavel Dvurechensky +1
We present two easy-to-implement gradient-free/zeroth-order methods to optimize a stochastic non-smooth function accessible only via a black-box. The methods are built upon efficie…
High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance
Abdurakhmon Sadiev, Marina Danilova, Eduard Gorbunov +5
During recent years the interest of optimization and machine learning communities in high-probability convergence of stochastic optimization methods has been growing. One of the ma…
Randomized gradient-free methods in convex optimization
Alexander Gasnikov, Darina Dvinskikh, Pavel Dvurechensky +3
This review presents modern gradient-free methods to solve convex optimization problems. By gradient-free methods, we mean those that use only (noisy) realizations of the objective…
Numerical Methods for Large-Scale Optimal Transport
Nazarii Tupitsa, Pavel Dvurechensky, Darina Dvinskikh +1
The optimal transport (OT) problem is a classical optimization problem having the form of linear programming. Machine learning applications put forward new computational challenges…
Exploiting higher-order derivatives in convex optimization methods
Dmitry Kamzolov, Alexander Gasnikov, Pavel Dvurechensky +2
Exploiting higher-order derivatives in convex optimization is known at least since 1970's. In each iteration higher-order (also called tensor) methods minimize a regularized Taylor…
A conditional gradient homotopy method with applications to Semidefinite Programming
Pavel Dvurechensky, Gabriele Iommazzo, Shimrit Shtern +1
We propose a new homotopy-based conditional gradient method for solving convex optimization problems with a large number of simple conic constraints. Instances of this template nat…
Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise
Eduard Gorbunov, Marina Danilova, David Dobre +3
Stochastic first-order methods such as Stochastic Extragradient (SEG) or Stochastic Gradient Descent-Ascent (SGDA) for solving smooth minimax problems and, more generally, variatio…
Decentralized Convex Optimization on Time-Varying Networks with Application to Wasserstein Barycenters
Olga Yufereva, Michael Persiianov, Pavel Dvurechensky +2
Inspired by recent advances in distributed algorithms for approximating Wasserstein barycenters, we propose a novel distributed algorithm for this problem. The main novelty is that…
Decentralized convex optimization under affine constraints for power systems control
Demyan Yarmoshik, Alexander Rogozin, Oleg. O. Khamisov +2
Modern power systems are now in continuous process of massive changes. Increased penetration of distributed generation, usage of energy storage and controllable demand require intr…
A General Framework for Distributed Partitioned Optimization
Savelii Chezhegov, Anton Novitskii, Alexander Rogozin +3
Decentralized optimization is widely used in large scale and privacy preserving machine learning and various distributed control and sensing systems. It is assumed that every agent…
An Approach for Non-Convex Uniformly Concave Structured Saddle Point Problem
Mohammad Alkousa, Alexander Gasnikov, Pavel Dvurechensky +2
Recently, saddle point problems have received much attention due to their powerful modeling capability for a lot of problems from diverse domains. Applications of these problems oc…
The Power of First-Order Smooth Optimization for Black-Box Non-Smooth Problems
Alexander Gasnikov, Anton Novitskii, Vasilii Novitskii +6
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,…
Hessian barrier algorithms for non-convex conic optimization
Pavel Dvurechensky, Mathias Staudigl
We consider the minimization of a continuous function over the intersection of a regular cone with an affine set via a new class of adaptive first- and second-order optimization me…