Research map / Optimization / Nonconvex and smooth optimization
On the Second-order Convergence Properties of Random Search Methods
Aurelien Lucchi, Antonio Orvieto, Adamos Solomou
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace random direction sampling with DFPI negative-curvature extraction (RSPI vs two-step RS) | two-step random search · Growing-dimension function, d=100,200 | optimality gap vs run-time | Improved |
| Replace random direction sampling with DFPI (RSPI vs two-step RS) | two-step random search · Growing-dimension function, d=5 | run-time to convergence | Hurt |
| Use RSPI instead of AHDS (power iteration vs full Hessian approximation) | AHDS · Growing-dimension function, high d | run-time | Improved |
| Use RSPI instead of AHDS | AHDS · Leading eigenvector (d=350) | time per iteration (s): 9.01 -> 0.06 | Improved |
| Use AHDS instead of RSPI | RSPI · Leading eigenvector (d=350) | progress per iteration | Mixed |
| Use RSPI instead of two-step RS | two-step RS · Rastrigin function | iterations to escape saddle: 300 -> one iteration | Improved |
| Increase dimension for two-step RS | two-step RS · Rastrigin function, higher d | saddle escape | Hurt |
| Use two sampling radii (RS) instead of one (STP) | STP · Growing-dimension function | optimality gap | Improved |
| Use BDS or AHDS instead of RSPI | RSPI · Rastrigin function | optimality gap | Hurt |
| Run more DFPI iterations than 20 (ablation) | RSPI · All tasks | overall performance | No clear effect |
| Estimate Hessian-vector products with SPSA (4 calls) instead of finite differences (4d calls) | DFPI · experiments | speed | Improved |
Closest papers by meaning
- Stochastic Optimization with Random Search (NeurIPS 2026 · similarity 0.89)
- High Probability Complexity Bounds for Line Search Based on Stochastic Oracles (NeurIPS 2021 · similarity 0.89)
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity (NeurIPS 2024 · similarity 0.87)
- Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization (ICML 2025 · similarity 0.87)
- Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization (ICML 2025 · similarity 0.87)
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · 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.
