101 citations · 488 across the 33 of their papers we have counts for
33 papers
Adaptive Proximal Gradient Method for Convex Optimization
Yura Malitsky, Konstantin Mishchenko
In this paper, we explore two fundamental first-order algorithms in convex optimization, namely, gradient descent (GD) and proximal gradient method (ProxGD). Our focus is on making…
Prodigy: An Expeditiously Adaptive Parameter-Free Learner
Konstantin Mishchenko, Aaron Defazio
We consider the problem of estimating the learning rate in adaptive methods, such as AdaGrad and Adam. We propose Prodigy, an algorithm that provably estimates the distance to the…
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.…
DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method
Ahmed Khaled, Konstantin Mishchenko, Chi Jin
This paper proposes a new easy-to-implement parameter-free gradient-based optimizer: DoWG (Distance over Weighted Gradients). We prove that DoWG is efficient -- matching the conver…
Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxy
Blake Woodworth, Konstantin Mishchenko, Francis Bach
We present an algorithm for minimizing an objective with hard-to-compute gradients by using a related, easier-to-access function as a proxy. Our algorithm is based on approximate p…
Convergence of First-Order Algorithms for Meta-Learning with Moreau Envelopes
Konstantin Mishchenko, Slavomír Hanzely, Peter Richtárik
In this work, we consider the problem of minimizing the sum of Moreau envelopes of given functions, which has previously appeared in the context of meta-learning and personalized f…
Learning-Rate-Free Learning by D-Adaptation
Aaron Defazio, Konstantin Mishchenko
D-Adaptation is an approach to automatically setting the learning rate which asymptotically achieves the optimal rate of convergence for minimizing convex Lipschitz functions, with…
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…
Regularized Newton Method with Global Convergence
Konstantin Mishchenko
We present a Newton-type method that converges fast from any initialization and for arbitrary convex objectives with Lipschitz Hessians. We achieve this by merging the ideas of cub…
On Seven Fundamental Optimization Challenges in Machine Learning
Konstantin Mishchenko
Many recent successes of machine learning went hand in hand with advances in optimization. The exchange of ideas between these fields has worked both ways, with machine learning bu…
Proximal and Federated Random Reshuffling
Konstantin Mishchenko, Ahmed Khaled, Peter Richtárik
Random Reshuffling (RR), also known as Stochastic Gradient Descent (SGD) without replacement, is a popular and theoretically grounded method for finite-sum minimization. We propose…
IntSGD: Adaptive Floatless Compression of Stochastic Gradients
Konstantin Mishchenko, Bokun Wang, Dmitry Kovalev +1
We propose a family of adaptive integer compression operators for distributed Stochastic Gradient Descent (SGD) that do not communicate a single float. This is achieved by multiply…
Random Reshuffling: Simple Analysis with Vast Improvements
Konstantin Mishchenko, Ahmed Khaled, Peter Richtárik
Random Reshuffling (RR) is an algorithm for minimizing finite-sum functions that utilizes iterative gradient descent steps in conjunction with data reshuffling. Often contrasted wi…
Dualize, Split, Randomize: Toward Fast Nonsmooth Optimization Algorithms
Adil Salim, Laurent Condat, Konstantin Mishchenko +1
We consider minimizing the sum of three convex functions, where the first one F is smooth, the second one is nonsmooth and proximable and the third one is the composition of a nons…
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…