# OptEx: Expediting First-Order Optimization with Approximately Parallelized Iterations

arXiv: https://arxiv.org/abs/2402.11427 · HTML: https://mlsanity.com/paper/2402.11427/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 53 references that are in the map.
- First posted on arXiv 18 Feb 2024.

## Builds on (most cited first, 27 of 27)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradients](https://mlsanity.com/paper/2010.07468/) (2020)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [Measuring the Effects of Data Parallelism on Neural Network Training](https://mlsanity.com/paper/1811.03600/) (2018)
- [An Improved Analysis of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/2007.07989/) (2020)
- [PipeDream: Fast and Efficient Pipeline Parallel DNN Training](https://mlsanity.com/paper/1806.03377/) (2018)
- [Hyper-Parameter Optimization: A Review of Algorithms and Applications](https://mlsanity.com/paper/2003.05689/) (2020)
- [High Probability Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2302.14843/) (2023)
- [Advances in Asynchronous Parallel and Distributed Optimization](https://mlsanity.com/paper/2006.13838/) (2020)
- [Neural Contextual Bandits without Regret](https://mlsanity.com/paper/2107.03144/) (2021)
- [The Complexity of Finding Stationary Points with Stochastic Gradient Descent](https://mlsanity.com/paper/1910.01845/) (2019)
- [Sample-Then-Optimize Batch Neural Thompson Sampling](https://mlsanity.com/paper/2210.06850/) (2022)
- [No-regret Algorithms for Multi-task Bayesian Optimization](https://mlsanity.com/paper/2008.08885/) (2020)
- [Posterior Variance Analysis of Gaussian Processes with Application to Average Learning Curves](https://mlsanity.com/paper/1906.01404/) (2019)
- [A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates](https://mlsanity.com/paper/1806.11027/) (2018)
- [Federated Zeroth-Order Optimization using Trajectory-Informed Surrogate Gradients](https://mlsanity.com/paper/2308.04077/) (2023)
- [Thermostat-assisted continuously-tempered Hamiltonian Monte Carlo for Bayesian learning](https://mlsanity.com/paper/1711.11511/) (2017)
- [Towards closing the gap between the theory and practice of SVRG](https://mlsanity.com/paper/1908.02725/) (2019)
- [Revisiting the Characteristics of Stochastic Gradient Noise and Dynamics](https://mlsanity.com/paper/2109.09833/) (2021)
- [Efficient First-Order Algorithms for Adaptive Signal Denoising](https://mlsanity.com/paper/1803.11262/) (2018)

## Abstract (arXiv)

First-order optimization (FOO) algorithms are pivotal in numerous computational domains such as machine learning and signal denoising. However, their application to complex tasks like neural network training often entails significant inefficiencies due to the need for many sequential iterations for convergence. In response, we introduce first-order optimization expedited with approximately parallelized iterations (OptEx), the first framework that enhances the efficiency of FOO by leveraging parallel computing to mitigate its iterative bottleneck. OptEx employs kernelized gradient estimation to make use of gradient history for future gradient prediction, enabling parallelization of iterations -- a strategy once considered impractical because of the inherent iterative dependency in FOO. We provide theoretical guarantees for the reliability of our kernelized gradient estimation and the iteration complexity of SGD-based OptEx, confirming that estimation errors diminish to zero as historical gradients accumulate and that SGD-based OptEx enjoys an effective acceleration rate of Omega(√N) over standard SGD given parallelism of N. We also use extensive empirical studies, including synthetic functions, reinforcement learning tasks, and neural network training across various datasets, to underscore the substantial efficiency improvements achieved by OptEx.