Research map / Optimization / Optimizers
OptEx: Expediting First-Order Optimization with Approximately Parallelized Iterations
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes OptEx, which uses a kernelized (GP-posterior) gradient estimate from gradient history to run proxy updates that let N sequential FOO iterations be partially parallelized, and proves a Θ(√N) sequential-iteration acceleration for SGD-based OptEx.
Problem
First-order optimization requires many sequential iterations to converge, and the inherent iterative dependency makes it hard to parallelize iterations, which is costly for expensive tasks like deep RL and neural network training.
Approach
Use a separable kernelized gradient estimate (GP posterior mean built from a localized history of evaluated gradients) to run N-1 cheap proxy FOO steps ahead, then evaluate true gradients at those N proxy inputs in parallel, so that the sequential iteration count drops with parallelism N.
Key results
- SGD-based OptEx achieves at least 2x fewer sequential iterations than vanilla FOO with parallelism N=5 on synthetic functions (deterministic case).
- Theory: effective acceleration rate of Θ(√N) over standard SGD with parallelism N, with gradient estimation error bounded by O(sqrt(γ_T0/T0)) for worst case and tending to zero as history grows.
- On CIFAR-10 and Shakespeare training with N=4, OptEx consistently outperforms vanilla optimizers by a large margin in iterations and wallclock time, approaching the ideal Target baseline.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use OptEx instead of Vanilla | first-order optimization on synthetic functions · Synthetic functions | sequential iterations: at least 2× more efficient | Helped |
| use OptEx instead of Target | first-order optimization on synthetic functions · Synthetic functions | sequential iterations | Hurt |
| use OptEx instead of Vanilla | DQN optimization · OpenAI Gym DQN tasks | sequential iterations | Helped |
| use OptEx instead of Target | DQN optimization · OpenAI Gym DQN tasks | sequential iterations | Helped |
| use OptEx instead of Vanilla | 10-layer MLP training · CIFAR-10 | training error | Helped |
| use OptEx instead of Vanilla | 10-layer MLP training · CIFAR-10 | test error | Helped |
| use OptEx instead of Vanilla | autoregressive transformer training · Shakespeare Corpus | training loss | Helped |
| use OptEx instead of Vanilla | autoregressive transformer training · Shakespeare Corpus | test error | Helped |
Surprising findings
- OptEx sometimes outperforms the ideal Target baseline (ground-truth-gradient parallelization) in RL, attributed to gradient variance shrinking as gradient history grows.
Limitations
- Additional storage and computational cost from kernelized gradient estimation.
- Error bounds rely on Gaussian process assumptions; with large N relative to the optimal learning rate, performance degrades due to estimation error.
Experimental setup
Datasets: CIFAR-10 Shakespeare Corpus OpenAI Gym
Benchmarks: CIFAR-10 Shakespeare Corpus OpenAI Gym RL tasks synthetic functions
Metrics: optimality gap cumulative average reward test error training loss number of sequential iterations wallclock time
Baselines: Vanilla FOO (standard sequential optimizer) Target (ideal parallelized iterations with ground-truth gradients)
Builds on: SGD Adam Gaussian process regression kernelized bandits
Closest papers by meaning
- A Universal Transfer Theorem for Convex Optimization Algorithms Using Inexact First-order Oracles (ICML 2024 · similarity 0.85)
- DesignX: Human-Competitive Algorithm Designer for Black-Box Optimization (NeurIPS 2025 · similarity 0.84)
- Fundamental Benefit of Alternating Updates in Minimax Optimization (ICML 2024 · similarity 0.84)
- MetaBox-v2: A Unified Benchmark Platform for Meta-Black-Box Optimization (NeurIPS 2025 · similarity 0.84)
- Revisiting Scalable Hessian Diagonal Approximations for Applications in Reinforcement Learning (ICML 2024 · similarity 0.84)
- Learning Provably Improves the Convergence of Gradient Descent (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.