Research map / Optimization / Optimizers
Zeroth-Order Optimization Finds Flat Minima
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.
Shows that zeroth-order optimization with the two-point estimator implicitly regularizes the trace of Hessian and proves convergence to approximate flat minima (minimizers with smallest Hessian trace) for convex, smooth functions.
Problem
Zeroth-order optimization is known to converge to stationary points, but it is unclear which minimizer among many it selects; the paper asks whether ZO methods implicitly favor flat minima defined via the smallest Hessian trace among minimizers.
Approach
The expected two-point zeroth-order estimator targets the smoothed loss, whose Taylor expansion adds (lambda^2/2) trace of Hessian, so ZO implicitly penalizes trace of Hessian; the analysis tracks the regularized loss F(x)=f(x)+(lambda^2/2)tr(Hessian) directly, with Isserlis-based moment bounds, to get rates to approximate flat minima.
Key results
- Theorem/Corollary: ZO with two-point estimator reaches (O(eps/d^2), eps)-approximate flat minima after T=O(d^4/eps^2) iterations under convexity and higher-order smoothness.
- On SVM and logistic regression experiments, ZO consistently reduces trace of Hessian while achieving comparable training loss and test accuracy to GD, though ZO is slower.
- On RoBERTa-Large few-shot fine-tuning, both GD and ZO reduce the expected-sharpness estimate of trace of Hessian during training; GD generally achieves lower loss and sharpness.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use two-point zeroth-order optimization instead of gradient descent | SVMs and logistic regression · a5a and w5a binary classification | trace of Hessian | Helped |
| Use two-point zeroth-order optimization instead of gradient descent | SVMs and logistic regression · a5a and w5a binary classification | training loss | No clear effect |
| Use two-point zeroth-order optimization instead of gradient descent | SVMs and logistic regression · a5a and w5a binary classification | test accuracy | No clear effect |
| Use two-point zeroth-order optimization instead of gradient descent | RoBERTa-Large fine-tuning · SST-2, SST-5, and TREC | trace of Hessian estimate | No clear effect |
| Use gradient descent instead of two-point zeroth-order optimization | RoBERTa-Large fine-tuning · SST-2, SST-5, and TREC | training loss | Mixed |
| Use gradient descent instead of two-point zeroth-order optimization | RoBERTa-Large fine-tuning · SST-2, SST-5, and TREC | trace of Hessian estimate | Mixed |
| Use gradient descent instead of two-point zeroth-order optimization | RoBERTa-Large fine-tuning · SST-2, SST-5, and TREC | test accuracy | Mixed |
| Increase the smoothing parameter λ | Two-point zeroth-order optimization · Example test function | trace of Hessian | Helped |
| Increase the smoothing parameter λ | Two-point zeroth-order optimization · Example test function | loss | Hurt |
| Use λ→0 (directional derivatives) instead of λ=0.1 | Two-point zeroth-order optimization · Example test function | trace of Hessian | Hurt |
Surprising findings
- Gradient descent also decreases the sharpness proxy on RoBERTa fine-tuning, which the authors attribute to large learning-rate implicit regularization.
Limitations
- Results require convexity and three-times differentiability with higher-order smoothness assumptions; nonconvex extension is left open.
- Trace of Hessian is approximated by expected sharpness in the LLM experiments rather than computed exactly.
- Complexity bound T=O(d^4/eps^2) is worse in dimension than standard zeroth-order rates for function value alone.
Experimental setup
Datasets: a5a w5a SST-2 SST-5 TREC
Benchmarks: a5a w5a SST-2 SST-5 TREC
Metrics: training loss trace of Hessian (exact for convex models; expected sharpnes test accuracy
Baselines: gradient descent sharpness-aware minimization
Builds on: Gaussian smoothing zeroth-order optimization sharpness-aware minimization MeZO
Closest papers by meaning
- Zeroth-Order Sharpness-Aware Learning with Exponential Tilting (NeurIPS 2026 · similarity 0.89)
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity (NeurIPS 2024 · similarity 0.89)
- On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization (NeurIPS 2025 · similarity 0.88)
- Refining Adaptive Zeroth-Order Optimization at Ease (ICML 2025 · similarity 0.87)
- Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations (ICLR 2025 · similarity 0.87)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.87)
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.