66 citations · 228 across the 17 of their papers we have counts for
19 papers
Towards Easier-to-Tune Training Algorithms: New Results from AlgoPerf
Priya Kasimbeg, Ahmed Khaled, Aahlad Chandrabhatta +9
Evaluating deep learning optimizer is challenging because confounding factors such as hyperparameter tuning and optimizer-model co-design often obscure true algorithmic performance…
Muon Does Not Converge on Convex Lipschitz Functions
Tetiana Parshakova, Ahmed Khaled, Michael Crawshaw +2
Muon and its variants have shown strong empirical performance in a variety of deep learning tasks. Existing convergence analyses of Muon rely on smoothness assumptions, though argu…
MuonBP: Faster Muon via Block-Periodic Orthogonalization
Ahmed Khaled, Kaan Ozkara, Tao Yu +2
Gradient orthogonalization is a simple strategy that shows great utility in speeding up gradient descent. The Muon optimizer (Jordan, Jin, et al., 2024) combines gradient orthogona…
Understanding Outer Optimizers in Local SGD: Learning Rates, Momentum, and Acceleration
Ahmed Khaled, Satyen Kale, Arthur Douillard +3
Modern machine learning often requires training with large batch size, distributed data, and massively parallel compute hardware (like mobile and other edge devices or distributed…
A Novel Unified Parametric Assumption for Nonconvex Optimization
Artem Riabinin, Ahmed Khaled, Peter Richtárik
Nonconvex optimization is central to modern machine learning, but the general framework of nonconvex optimization yields weak convergence guarantees that are too pessimistic compar…
Tuning-Free Stochastic Optimization
Ahmed Khaled, Chi Jin
Large-scale machine learning problems make the cost of hyperparameter tuning ever more prohibitive. This creates a need for algorithms that can tune themselves on-the-fly. We forma…
Directional Smoothness and Gradient Methods: Convergence and Adaptivity
Aaron Mishkin, Ahmed Khaled, Yuanhao Wang +2
We develop new sub-optimality bounds for gradient descent (GD) that depend on the conditioning of the objective along the path of optimization rather than on global, worst-case con…
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…
Faster federated optimization under second-order similarity
Ahmed Khaled, Chi Jin
Federated learning (FL) is a subfield of machine learning where multiple clients try to collaboratively learn a model over a network under communication constraints. We consider fi…
Federated Optimization Algorithms with Random Reshuffling and Gradient Compression
Abdurakhmon Sadiev, Grigory Malinovsky, Eduard Gorbunov +4
Gradient compression is a popular technique for improving communication complexity of stochastic first-order methods in distributed training of machine learning models. However, th…
FLIX: A Simple and Communication-Efficient Alternative to Local Methods in Federated Learning
Elnur Gasanov, Ahmed Khaled, Samuel Horváth +1
Federated Learning (FL) is an increasingly popular machine learning paradigm in which multiple nodes try to collaboratively learn under privacy, communication and multiple heteroge…
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…
Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization
Ahmed Khaled, Othmane Sebbouh, Nicolas Loizou +2
We present a unified theorem for the convergence analysis of stochastic gradient algorithms for minimizing a smooth and convex loss plus a convex regularizer. We do this by extendi…
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…
Better Theory for SGD in the Nonconvex World
Ahmed Khaled, Peter Richtárik
Large-scale nonconvex optimization problems are ubiquitous in modern machine learning, and among practitioners interested in solving them, Stochastic Gradient Descent (SGD) reigns…
Distributed Fixed Point Methods with Compressed Iterates
Sélim Chraibi, Ahmed Khaled, Dmitry Kovalev +3
We propose basic and natural assumptions under which iterative optimization methods with compressed iterates can be analyzed. This problem is motivated by the practice of federated…
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…
Gradient Descent with Compressed Iterates
Ahmed Khaled, Peter Richtárik
We propose and analyze a new type of stochastic first order method: gradient descent with compressed iterates (GDCI). GDCI in each iteration first compresses the current iterate us…
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…