Research map / Optimization / Optimizers
FOSI: Hybrid First and Second Order Optimization
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 FOSI, a meta-optimizer that splits each iteration's quadratic model into two orthogonal subspaces, applying a Newton-like step on the top Hessian eigenspace (via Lanczos) and a base first-order optimizer on the complement.
Problem
First-order optimizers are cheap but converge slowly on ill-conditioned problems, while second-order methods are intractable for large DNNs and approximate Hessian inversions amplify error and noise.
Approach
Implicitly split the quadratic model into two orthogonal subspaces: a scaled Newton step on the extreme Hessian eigenspace estimated by Lanczos (inverse preconditioner obtained directly, no matrix inversion), and the base optimizer on the orthogonal complement, so FOSI wraps any first-order optimizer without extra tuning.
Key results
- FOSI reaches the best first-order baseline's target metric in 48%-77% of the wall time depending on the task.
- On average FOSI achieves the same training loss as its base optimizer in 78% of the time.
- On PD quadratic functions FOSI converges at least two orders of magnitude faster than GD, HB, and Adam.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add FOSI to Heavy-Ball | Heavy-Ball · DNN training tasks | wall time to target validation accuracy or loss: 48\%--77\% of the wall time | Helped |
| Add FOSI to the base optimizer | First-order optimizers · DNN training set | time to same loss: 78\% of the time | Helped |
| Add FOSI to the base optimizer | First-order optimizers · DNN validation set | time to same accuracy/loss: 75\% of the time | Helped |
| Use FOSI with Heavy-Ball instead of Heavy-Ball alone | Heavy-Ball · Five DNN training tasks | wall time to target metric | Helped |
| Use FOSI with Adam instead of Adam alone | Adam · Logistic Regression on MNIST | wall time to target validation accuracy | Hurt |
| Use FOSI with Heavy-Ball instead of Heavy-Ball alone | Heavy-Ball · Positive definite quadratic functions | convergence speed: at least two orders of magnitude faster | Helped |
| Use FOSI with Adam instead of Adam alone | Adam · Positive definite quadratic functions | convergence speed | Helped |
| Use FOSI instead of K-FAC or L-BFGS | K-FAC and L-BFGS · DNN training tasks | runtime and performance | Helped |
| Add FOSI to Adam | Adam · Audio Classification | training loss | No clear effect |
Surprising findings
- FOSI can accelerate convergence even when its effective condition number is larger than the original one (e.g., 100000 vs 1000 in a quadratic example).
- FOSI speeds up overfitting: it reaches the overfitting point earlier than the base Heavy-Ball optimizer.
Limitations
- Gains on Adam are smaller than on Heavy-Ball; FOSI does not help Adam on some tasks.
- Non-quadratic settings risk divergence from inexact Hessian eigenvalue estimates, mitigated by heuristics like warmup and scaled Newton steps.
- Key hyperparameters (k, l, alpha, c, T) are fixed by heuristics rather than automatically tuned.
Experimental setup
Datasets: AudioSet Tiny Shakespeare CIFAR-10 ImageNet2012 MNIST
Benchmarks: AudioSet Tiny Shakespeare CIFAR-10 MNIST synthetic PD quadratic functions
Metrics: wall time to target validation accuracy wall time to target validation loss convergence rate on quadratics
Baselines: Heavy-Ball Adam gradient descent K-FAC L-BFGS
Builds on: Lanczos algorithm Heavy-Ball Adam K-FAC L-BFGS
Closest papers by meaning
- Global curvature for second-order optimization of neural networks (ICML 2025 · similarity 0.87)
- Studying K-FAC Heuristics by Viewing Adam through a Second-Order Lens (ICML 2024 · similarity 0.86)
- Advancing the Lower Bounds: an Accelerated, Stochastic, Second-order Method with Optimal Adaptation to Inexactness (ICLR 2024 · similarity 0.86)
- On the Parameterization of Second-Order Optimization Effective towards the Infinite Width (ICLR 2024 · similarity 0.85)
- Trust the Direction, Search the Step: Zero-and-First-Order Methods for LLM Fine-Tuning (NeurIPS 2026 · similarity 0.84)
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · 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.