66 citations · 525 across the 94 of their papers we have counts for
112 papers
Lower Bounds For Gradient-Free Convex Optimization And Convex-Concave Saddle-Point Problems
Yuriy Dorn, Darina Dvinskikh, Timofei Loginov +4
We study the query complexity of optimization with exact scalar-value information. For globally -smooth convex functions on with a minimizer in a Euclidean ball of…
Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise
Alexandra Suvorikova, Egor Gladin, Darina Dvinskikh +5
Gradient clipping is widely used to stabilize training, but it need not improve the statistical accuracy of averaged SGD, even under heavy-tailed noise. We derive a finite-sample c…
The Complexity of Convex Optimization with Mismatched Geometry
Timofei Loginov, Alexander Gasnikov, Yuriy Dorn +4
Optimal first-order methods on non-Euclidean domains such as the ball pair the prox-function with the norm in which smoothness…
Certified Residual Quasi-Newton Methods for Distributed Variational Inequalities
Ewsey R. Obzherin, Roman M. Mozhaev, Alexander V. Gasnikov +3
Second-order methods for smooth monotone variational inequalities reach the optimal rate , but a distributed exact Jacobian costs times more communication than an…
Application of Optimal Inexact Second-Order Acceleration to Distributed Stochastic Optimization under Statistical Similarity
Yury A. Sokolov, Maxim K. Mashtaler, Alexander V. Gasnikov +3
We consider distributed stochastic convex optimization with a fixed budget of independent samples split among workers. Sample average approximation reduces the problem to a…
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…
Exploring Jacobian Inexactness in Second-Order Methods for Variational Inequalities: Lower Bounds, Optimal Algorithms and Quasi-Newton Approximations
Artem Agafonov, Petr Ostroukhov, Roman Mozhaev +5
Variational inequalities represent a broad class of problems, including minimization and min-max problems, commonly found in machine learning. Existing second-order and high-order…
AdaBatchGrad: Combining Adaptive Batch Size and Adaptive Step Size
Petr Ostroukhov, Aigerim Zhumabayeva, Chulu Xiang +3
This paper presents a novel adaptation of the Stochastic Gradient Descent (SGD), termed AdaBatchGrad. This modification seamlessly integrates an adaptive step size with an adjustab…
Median Clipping for Zeroth-order Non-Smooth Convex Optimization and Multi-Armed Bandit Problem with Heavy-tailed Symmetric Noise
Nikita Kornilov, Yuriy Dorn, Aleksandr Lobanov +5
In this paper, we consider non-smooth convex optimization with a zeroth-order oracle corrupted by symmetric stochastic noise. Unlike the existing high-probability results requiring…
Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems
Nikita Puchkin, Eduard Gorbunov, Nikolay Kutuzov +1
We consider stochastic optimization problems with heavy-tailed noise with structured density. For such problems, we show that it is possible to get faster rates of convergence than…
Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance
Nikita Kornilov, Ohad Shamir, Aleksandr Lobanov +5
In this paper, we consider non-smooth stochastic convex optimization with two function evaluations per round under infinite noise variance. In the classical setting when noise has…
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…
Advancing the lower bounds: An accelerated, stochastic, second-order method with optimal adaptation to inexactness
Artem Agafonov, Dmitry Kamzolov, Alexander Gasnikov +4
We present a new accelerated stochastic second-order method that is robust to both gradient and Hessian inexactness, which occurs typically in machine learning. We establish theore…
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…
Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits
Yuriy Dorn, Nikita Kornilov, Nikolay Kutuzov +3
The Implicitly Normalized Forecaster (INF) algorithm is considered to be an optimal solution for adversarial multi-armed bandit (MAB) problems. However, most of the existing comple…
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…
Online Optimization Problems with Functional Constraints under Relative Lipschitz Continuity and Relative Strong Convexity Conditions
Oleg Savchuk, Fedor Stonyakin, Mohammad Alkousa +3
Recently, there were introduced important classes of relatively smooth, relatively continuous, and relatively strongly convex optimization problems. These concepts have significant…
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…
A Damped Newton Method Achieves Global and Local Quadratic Convergence Rate
Slavomír Hanzely, Dmitry Kamzolov, Dmitry Pasechnyuk +3
In this paper, we present the first stepsize schedule for Newton method resulting in fast global and local convergence guarantees. In particular, a) we prove an $O\left( \frac 1 {k…
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…
Gradient-Type Methods For Decentralized Optimization Problems With Polyak-Łojasiewicz Condition Over Time-Varying Networks
Ilya Kuruzov, Mohammad Alkousa, Fedor Stonyakin +1
This paper focuses on the decentralized optimization (minimization and saddle point) problems with objective functions that satisfy Polyak-Łojasiewicz condition (PL-condition). The…