66 citations · 525 across the 94 of their papers we have counts for
18 papers · 1 filter
Adaptive Mirror Descent for the Network Utility Maximization Problem
Anastasiya Ivanova, Fedor Stonyakin, Dmitry Pasechnyuk +2
Network utility maximization is the most important problem in network traffic management. Given the growth of modern communication networks, we consider the utility maximization pr…
Accelerated gradient sliding and variance reduction
Darina Dvinskikh, Sergey Omelchenko, Alexander Tyurin +1
We consider sum-type strongly convex optimization problem (first term) with smooth convex not proximal friendly composite (second term). We show that the complexity of this problem…
Near-optimal tensor methods for minimizing the gradient norm of convex functions and accelerated primal-dual tensor methods
Pavel Dvurechensky, Petr Ostroukhov, Alexander Gasnikov +2
Motivated, in particular, by the entropy-regularized optimal transport problem, we consider convex optimization problems with linear equality constraints, where the dual objective…
Adaptive Catalyst for Smooth Convex Optimization
Anastasiya Ivanova, Dmitry Pasechnyuk, Dmitry Grishchenko +3
In this paper, we present a generic framework that allows accelerating almost arbitrary non-accelerated deterministic and randomized algorithms for smooth convex optimization probl…
Alternating Minimization Methods for Strongly Convex Optimization
Nazarii Tupitsa, Pavel Dvurechensky, Alexander Gasnikov +1
{We consider alternating minimization procedures for convex optimization problems with variable divided in many block, each block being amenable for minimization with respect to it…
Adaptive Gradient Descent for Convex and Non-Convex Stochastic Optimization
Darina Dvinskikh, Aleksandr Ogaltsov, Alexander Gasnikov +3
In this paper we propose several adaptive gradient methods for stochastic optimization. Unlike AdaGrad-type of methods, our algorithms are based on Armijo-type line search and they…
Optimal Decentralized Distributed Algorithms for Stochastic Convex Optimization
Eduard Gorbunov, Darina Dvinskikh, Alexander Gasnikov
We consider stochastic convex optimization problems with affine constraints and develop several methods using either primal or dual approach to solve it. In the primal case, we use…
Numerical methods for the resource allocation problem in networks
Anastasiya Ivanova, Dmitry Pasechnyuk, Pavel Dvurechensky +2
In this paper, we consider the resource allocation problem in a network with a large number of connections which are used by a huge number of users. The resource allocation problem…
Mirror Descent for Constrained Optimization Problems with Large Subgradient Values
Fedor Stonyakin, Alexey Stepanov, Alexander Gasnikov +1
Based on the ideas of arXiv:1710.06612, we consider the problem of minimization of the Holder-continuous non-smooth functional with non-positive convex (generally, non-smooth)…
Lecture Notes on Stochastic Processes
Alexander Gasnikov, Eduard Gorbunov, Sergey Guz +3
This is lecture notes on the course "Stochastic Processes". In this format, the course was taught in the spring semesters 2017 and 2018 for third-year bachelor students of the Depa…
On a Combination of Alternating Minimization and Nesterov's Momentum
Sergey Guminov, Pavel Dvurechensky, Nazarii Tupitsa +1
Alternating minimization (AM) procedures are practically efficient in many applications for solving convex and non-convex optimization problems. On the other hand, Nesterov's accel…
Accelerated methods for composite non-bilinear saddle point problem
Mohammad Alkousa, Darina Dvinskikh, Fedor Stonyakin +2
Based on G. Lan's accelerated gradient sliding and general relation between the smoothness and strong convexity parameters of function under Legendre transformation we show that un…
Decentralized and Parallel Primal and Dual Accelerated Methods for Stochastic Convex Programming Problems
Darina Dvinskikh, Alexander Gasnikov
We introduce primal and dual stochastic gradient oracle methods for decentralized convex optimization problems. Both for primal and dual oracles, the proposed methods are optimal i…
Gradient Methods for Problems with Inexact Model of the Objective
Fedor Stonyakin, Darina Dvinskikh, Pavel Dvurechensky +8
We consider optimization methods for convex minimization problems under inexact information on the objective function. We introduce inexact model of the objective, which as a parti…
On Primal-Dual Approach for Distributed Stochastic Convex Optimization over Networks
Darina Dvinskikh, Eduard Gorbunov, Alexander Gasnikov +2
We introduce a primal-dual stochastic gradient oracle method for distributed convex optimization problems over networks. We show that the proposed method is optimal in terms of com…
Advances in Low-Memory Subgradient Optimization
Pavel Dvurechensky, Alexander Gasnikov, Evgeni Nurminsky +1
This chapter is devoted to the black-box subgradient algorithms with the minimal requirements for the storage of auxiliary results, which are necessary to execute these algorithms.…
Inexact Model: A Framework for Optimization and Variational Inequalities
Fedor Stonyakin, Alexander Gasnikov, Alexander Tyurin +6
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 variat…
On the Complexity of Approximating Wasserstein Barycenter
Alexey Kroshnin, Darina Dvinskikh, Pavel Dvurechensky +3
We study the complexity of approximating Wassertein barycenter of discrete measures, or histograms of size by contrasting two alternative approaches, both using entropic re…