101 citations · 414 across the 51 of their papers we have counts for
53 papers
Last-Iterate Convergence Rate of Normalized Gradient Descent under Hölder Smoothness
Yuki Takezawa, Eduard Gorbunov
Normalized gradient descent is a widely studied adaptive optimization method. Most existing analyses focus on the best iterate or a weighted average of the iterates, whereas practi…
Accelerated and Stable Convergence with Anchored Generalized Optimistic Method
Motahareh Sohrabi, Jianxin You, Simon Lacoste-Julien +2
We study first-order methods for solving monotone variational inequalities arising in min-max optimization. Classical approaches such as the extragradient method rely on two gradie…
Heterogeneous-Horizon Exact-Weight Local SGD
Dmitry Pasechnyuk-Vilensky, Martin Takáč
We study adaptive aggregation for heterogeneous local SGD in convex finite-sum optimization, allowing heterogeneous local horizons, minibatch sizes, gradient noise, and participati…
On the Role of Batch Size in Stochastic Conditional Gradient Methods
Rustem Islamov, Roman Machacek, Aurelien Lucchi +3
We study the role of batch size in stochastic conditional gradient methods under a -Kurdyka-Łojasiewicz (-KL) condition. Focusing on momentum-based stochastic conditional gra…
On the Interaction of Batch Noise, Adaptivity, and Compression, under -Smoothness: An SDE Approach
Enea Monzio Compagnoni, Rustem Islamov, Frank Norbert Proske +3
Distributed stochastic optimization intertwines (i) stochastic gradient noise, (ii) communication compression, and (iii) adaptive/normalized updates. While each factor has been stu…
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…
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…
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…
Clip21: Error Feedback for Gradient Clipping
Sarit Khirirat, Eduard Gorbunov, Samuel Horváth +3
Motivated by the increasing popularity and importance of large-scale training under differential privacy (DP) constraints, we study distributed gradient methods with gradient clipp…
Partially Personalized Federated Learning: Breaking the Curse of Data Heterogeneity
Konstantin Mishchenko, Rustem Islamov, Eduard Gorbunov +1
We present a partially personalized formulation of Federated Learning (FL) that strikes a balance between the flexibility of personalization and cooperativeness of global training.…
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…
Unified analysis of SGD-type methods
Eduard Gorbunov
This note focuses on a simple approach to the unified analysis of SGD-type methods from (Gorbunov et al., 2020) for strongly convex smooth optimization problems. The similarities i…
Byzantine-Robust Loopless Stochastic Variance-Reduced Gradient
Nikita Fedin, Eduard Gorbunov
Distributed optimization with open collaboration is a popular field since it provides an opportunity for small groups/companies/universities, and individuals to jointly solve huge-…
Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions
Sayantan Choudhury, Eduard Gorbunov, Nicolas Loizou
Single-call stochastic extragradient methods, like stochastic past extragradient (SPEG) and stochastic optimistic gradient (SOG), have gained a lot of interest in recent years and…
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…
Convergence of Proximal Point and Extragradient-Based Methods Beyond Monotonicity: the Case of Negative Comonotonicity
Eduard Gorbunov, Adrien Taylor, Samuel Horváth +1
Algorithms for min-max optimization and variational inequalities are often studied under monotonicity assumptions. Motivated by non-monotone machine learning applications, we follo…
Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey
Aleksandr Beznosikov, Boris Polyak, Eduard Gorbunov +2
This paper is a survey of methods for solving smooth (strongly) monotone stochastic variational inequalities. To begin with, we give the deterministic foundation from which the sto…
Federated Optimization Algorithms with Random Reshuffling and Gradient Compression
Abdurakhmon Sadiev, Grigory Malinovsky, Eduard Gorbunov +4
Gradient compression is a popular technique for improving communication complexity of stochastic first-order methods in distributed training of machine learning models. However, th…
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…
Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalities
Eduard Gorbunov, Adrien Taylor, Gauthier Gidel
The Past Extragradient (PEG) [Popov, 1980] method, also known as the Optimistic Gradient method, has known a recent gain in interest in the optimization community with the emergenc…