13 citations · 52 across the 24 of their papers we have counts for
26 papers
Optimal Parameter-Free Second-order Acceleration with Inexact Hessians under Generalized Smoothness
Artem Agafonov, Aslan Ashabokov, Alexander D'yakonov +3
We study second-order convex optimization under generalized Hessian smoothness, where the local Hessian Lipschitz constant may grow linearly with the gradient norm. For inexact Hes…
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…
Decentralized Inexact Cubic Newton Method with Consensus Procedure
Artem Agafonov, Anton Novitskii, Alexander Rogozin +5
Distributed optimization is widely used in large-scale and privacy-preserving machine learning, where each agent stores a local objective and communicates only with its neighbors i…
Adaptive Regularized Newton Method with Inexact Hessian
Aleksandr Shestakov, Nail Bashirov, Andrei Semenov +4
Newton's method is the most widespread high-order method, demanding the gradient and the Hessian of the objective function. However, one of the main disadvantages of Newtons method…
Cubic Regularized Newton Method with Variance Reduction for Finite-sum Non-convex Problems
Dmitry Pasechnyuk-Vilensky, Dmitry Kamzolov, Martin Takáč
We study finite-sum non-convex optimization and analyze a variance-reduced cubic Newton method based on EMA-smoo…
DAG: Projected Stochastic Approximation Iteration for DAG Structure Learning
Klea Ziu, Slavomír Hanzely, Loka Li +3
Learning the structure of Directed Acyclic Graphs (DAGs) presents a significant challenge due to the vast combinatorial search space of possible graphs, which scales exponentially…
OPTAMI: Global Superlinear Convergence of High-order Methods
Dmitry Kamzolov, Dmitry Pasechnyuk, Artem Agafonov +2
Second-order methods for convex optimization outperform first-order methods in terms of theoretical iteration convergence, achieving rates up to for highly-smooth funct…
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…
SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithms
Farshed Abdukhakimov, Chulu Xiang, Dmitry Kamzolov +2
Adaptive optimization methods are widely recognized as among the most popular approaches for training Deep Neural Networks (DNNs). Techniques such as Adam, AdaGrad, and AdaHessian…
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…
Cubic Regularization is the Key! The First Accelerated Quasi-Newton Method with a Global Convergence Rate of for Convex Functions
Dmitry Kamzolov, Klea Ziu, Artem Agafonov +1
In this paper, we propose the first Quasi-Newton method with a global convergence rate of for general convex functions. Quasi-Newton methods, such as BFGS, SR-1, are we…
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…
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…
Suppressing Poisoning Attacks on Federated Learning for Medical Imaging
Naif Alkhunaizi, Dmitry Kamzolov, Martin Takáč +1
Collaboration among multiple data-owning entities (e.g., hospitals) can accelerate the training process and yield better machine learning models due to the availability and diversi…
FLECS: A Federated Learning Second-Order Framework via Compression and Sketching
Artem Agafonov, Dmitry Kamzolov, Rachael Tappenden +2
Inspired by the recent work FedNL (Safaryan et al, FedNL: Making Newton-Type Methods Applicable to Federated Learning), we propose a new communication efficient second-order framew…
Hyperfast Second-Order Local Solvers for Efficient Statistically Preconditioned Distributed Optimization
Pavel Dvurechensky, Dmitry Kamzolov, Aleksandr Lukashevich +4
Statistical preconditioning enables fast methods for distributed large-scale empirical risk minimization problems. In this approach, multiple worker nodes compute gradients in para…
Inexact Tensor Methods and Their Application to Stochastic Convex Optimization
Artem Agafonov, Dmitry Kamzolov, Pavel Dvurechensky +2
We propose general non-accelerated and accelerated tensor methods under inexact information on the derivatives of the objective, analyze their convergence rate. Further, we provide…
Recent Theoretical Advances in Non-Convex Optimization
Marina Danilova, Pavel Dvurechensky, Alexander Gasnikov +4
Motivated by recent increased interest in optimization algorithms for non-convex optimization in application to training deep neural networks and other optimization problems in dat…
Accelerated meta-algorithm for convex optimization
Alexander Gasnikov, Darina Dvinskikh, Pavel Dvurechensky +5
We propose an accelerated meta-algorithm, which allows to obtain accelerated methods for convex unconstrained minimization in different settings. As an application of the general s…
On the Optimal Combination of Tensor Optimization Methods
Dmitry Kamzolov, Alexander Gasnikov, Pavel Dvurechensky
We consider the minimization problem of a sum of a number of functions having Lipshitz -th order derivatives with different Lipschitz constants. In this case, to accelerate opti…
Universal composite prox-method for strictly convex optimization problems
Alexander Gasnikov, Dmitry Kamzolov, Mikhail Mendel
We propose a simple way to explain Univerasal method of Yu. Nesterov. Based on this method and using the restart technique we propose Universal method for strictly convex optimizat…
Efficient Numerical Methods to Solve Sparse Linear Equations with Application to PageRank
Anton Anikin, Alexander Gasnikov, Alexander Gornov +3
In this paper, we propose three methods to solve the PageRank problem for the transition matrices with both row and column sparsity. Our methods reduce the PageRank problem to the…