101 citations · 488 across the 33 of their papers we have counts for
12 papers · 1 filter
Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates
Dmitry Kovalev, Konstantin Mishchenko, Peter Richtárik
We present two new remarkably simple stochastic second-order methods for minimizing the average of a very large number of sufficiently smooth and strongly convex functions. The fir…
Adaptive Gradient Descent without Descent
Yura Malitsky, Konstantin Mishchenko
We present a strikingly simple proof that two rules are sufficient to automate gradient descent: 1) don't increase the stepsize too fast and 2) don't overstep the local curvature.…
Sinkhorn Algorithm as a Special Case of Stochastic Mirror Descent
Konstantin Mishchenko
We present a new perspective on the celebrated Sinkhorn algorithm by showing that is a special case of incremental/stochastic mirror descent. In order to see this, one should simpl…
Tighter Theory for Local SGD on Identical and Heterogeneous Data
Ahmed Khaled, Konstantin Mishchenko, Peter Richtárik
We provide a new analysis of local SGD, removing unnecessary assumptions and elaborating on the difference between two data regimes: identical and heterogeneous. In both cases, we…
First Analysis of Local GD on Heterogeneous Data
Ahmed Khaled, Konstantin Mishchenko, Peter Richtárik
We provide the first convergence analysis of local gradient descent for minimizing the average of smooth and convex but otherwise arbitrary functions. Problems of this form and loc…
A Self-supervised Approach to Hierarchical Forecasting with Applications to Groupwise Synthetic Controls
Konstantin Mishchenko, Mallory Montgomery, Federico Vaggi
When forecasting time series with a hierarchical structure, the existing state of the art is to forecast each time series independently, and, in a post-treatment step, to reconcile…
MISO is Making a Comeback With Better Proofs and Rates
Xun Qian, Alibek Sailanbayev, Konstantin Mishchenko +1
MISO, also known as Finito, was one of the first stochastic variance reduced methods discovered, yet its popularity is fairly low. Its initial analysis was significantly limited by…
A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions
Konstantin Mishchenko, Peter Richtárik
We consider the problem of minimizing the sum of three convex functions: i) a smooth function in the form of an expectation or a finite average, ii) a non-smooth function i…
Revisiting Stochastic Extragradient
Konstantin Mishchenko, Dmitry Kovalev, Egor Shulgin +2
We fix a fundamental issue in the stochastic extragradient method by providing a new sampling strategy that is motivated by approximating implicit updates. Since the existing stoch…
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko +2
We consider distributed optimization where the objective function is spread among different devices, each sending incremental model updates to a central server. To alleviate the co…
99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it
Konstantin Mishchenko, Filip Hanzely, Peter Richtárik
Many popular distributed optimization methods for training machine learning models fit the following template: a local gradient estimate is computed independently by each worker, t…
Distributed Learning with Compressed Gradient Differences
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč +1
Training large machine learning models requires a distributed computing approach, with communication of the model updates being the bottleneck. For this reason, several methods bas…