Optimal gradient sliding and its application to optimal distributed optimization under similarity

D Kovalev, A Beznosikov, E Borodich… - Advances in …, 2022 - proceedings.neurips.cc
We study structured convex optimization problems, with additive objective $ r:= p+ q $,
where $ r $ is ($\mu $-strongly) convex, $ q $ is $ L_q $-smooth and convex, and $ p $ is …

Stochastic distributed optimization under average second-order similarity: Algorithms and analysis

D Lin, Y Han, H Ye, Z Zhang - Advances in Neural …, 2023 - proceedings.neurips.cc
We study finite-sum distributed optimization problems involving a master node and $ n-1$
local nodes under the popular $\delta $-similarity and $\mu $-strong convexity conditions …

Decentralized local stochastic extra-gradient for variational inequalities

A Beznosikov, P Dvurechenskii… - Advances in …, 2022 - proceedings.neurips.cc
We consider distributed stochastic variational inequalities (VIs) on unbounded domains with
the problem data that is heterogeneous (non-IID) and distributed across many devices. We …

An accelerated method for decentralized distributed stochastic optimization over time-varying graphs

A Rogozin, M Bochko, P Dvurechensky… - 2021 60th IEEE …, 2021 - ieeexplore.ieee.org
We consider a distributed stochastic optimization problem that is solved by a decentralized
network of agents with only local communication between neighboring agents. The goal of …

Newton method over networks is fast up to the statistical precision

A Daneshmand, G Scutari… - International …, 2021 - proceedings.mlr.press
We propose a distributed cubic regularization of the Newton method for solving
(constrained) empirical risk minimization problems over a network of agents, modeled as …

Flecs: A federated learning second-order framework via compression and sketching

A Agafonov, D Kamzolov, R Tappenden… - arxiv preprint arxiv …, 2022 - arxiv.org
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 …

Advancing the lower bounds: An accelerated, stochastic, second-order method with optimal adaptation to inexactness

A Agafonov, D Kamzolov, A Gasnikov, A Kavis… - arxiv preprint arxiv …, 2023 - arxiv.org
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 …

[PDF][PDF] Accelerated adaptive cubic regularized quasi-newton methods

D Kamzolov, K Ziu, A Agafonov… - arxiv preprint arxiv …, 2023 - researchgate.net
In this paper, we propose Cubic Regularized Quasi-Newton Methods for (strongly)
starconvex and Accelerated Cubic Regularized Quasi-Newton for convex optimization. The …

Exploiting Higher Order Derivatives in Convex Optimization Methods

D Kamzolov, A Gasnikov, P Dvurechensky… - Encyclopedia of …, 2023 - Springer
It is well known since the works of Newton [64] and Kantorovich [45] that the second-order
derivative of the objective function can be used in numerical algorithms for solving …

Compression and data similarity: Combination of two techniques for communication-efficient solving of distributed variational inequalities

A Beznosikov, A Gasnikov - International Conference on Optimization and …, 2022 - Springer
Variational inequalities are an important tool, which includes minimization, saddles, games,
fixed-point problems. Modern large-scale and computationally expensive practical …