101 citations · 488 across the 33 of their papers we have counts for
5 papers · 1 filter
Super-Universal Regularized Newton Method
Nikita Doikov, Konstantin Mishchenko, Yurii Nesterov
We analyze the performance of a variant of Newton method with quadratic regularization for solving composite convex minimization problems. At each step of our method, we choose reg…
Adaptive Learning Rates for Faster Stochastic Gradient Methods
Samuel Horváth, Konstantin Mishchenko, Peter Richtárik
In this work, we propose new adaptive step size strategies that improve several stochastic gradient methods. Our first method (StoPS) is based on the classical Polyak step size (Po…
Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays
Konstantin Mishchenko, Francis Bach, Mathieu Even +1
The existing analysis of asynchronous stochastic gradient descent (SGD) degrades dramatically when any delay is large, giving the impression that performance depends primarily on t…
ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich +1
We introduce ProxSkip -- a surprisingly simple and provably efficient method for minimizing the sum of a smooth () and an expensive nonsmooth proximable () function. The cano…
Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimization
Grigory Malinovsky, Konstantin Mishchenko, Peter Richtárik
We present a theoretical study of server-side optimization in federated learning. Our results are the first to show that the widely popular heuristic of scaling the client updates…