66 citations · 525 across the 94 of their papers we have counts for
10 papers · 2 filters
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…
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…