mlsanityData to 14 Oct 2026

Curvature-Aware Derivative-Free Optimization

arXiv 2109.13391 ↗First posted 27 Sep 2021math.OC cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

The paper discusses derivative-free optimization (DFO), which involves minimizing a function without access to gradients or directional derivatives, only function evaluations. Classical DFO methods, which mimic gradient-based methods, such as Nelder-Mead and direct search have limited scalability for high-dimensional problems. Zeroth-order methods have been gaining popularity due to the demands of large-scale machine learning applications, and the paper focuses on the selection of the step size αk in these methods. The proposed approach, called Curvature-Aware Random Search (CARS), uses first- and second-order finite difference approximations to compute a candidate α+. We prove that for strongly convex objective functions, CARS converges linearly provided that the search direction is drawn from a distribution satisfying very mild conditions. We also present a Cubic Regularized variant of CARS, named CARS-CR, which converges in a rate of O(k-1) without the assumption of strong convexity. Numerical experiments show that CARS and CARS-CR match or exceed the state-of-the-arts on benchmark problem sets.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 32 of its 72 references that are in the map. First posted on arXiv 27 Sep 2021.

Builds on

32 of 72 references.

References · 32

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  2. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  3. 2019Square Attack: a query-efficient black-box adversarial attack via random searchcited by 685
  4. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 666
  5. 2017Evolution Strategies as a Scalable Alternative to Reinforcement Learningcited by 574
  6. 2018Black-box Adversarial Attacks with Limited Queries and Informationcited by 501
  7. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 250
  8. 2020A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learningcited by 162
  9. 2019Sign-OPT: A Query-Efficient Hard-label Adversarial Attackcited by 120
  10. 2018Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimizationcited by 111
  11. 2019A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimizationcited by 68
  12. 2017Stochastic Zeroth-order Optimization in High Dimensionscited by 63
20 more
  1. 2018Structured Evolution with Compact Architectures for Scalable Policy Optimizationcited by 48
  2. 2020Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Samplingcited by 46
  3. 2021A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimizationcited by 46
  4. 2019RSN: Randomized Subspace Newtoncited by 34
  5. 2018Global linear convergence of Newton's method without strong-convexity or Lipschitz gradientscited by 24
  6. 2019Stochastic Three Points Method for Unconstrained Smooth Minimizationcited by 24
  7. 2020Safeguarded Learned Convex Optimizationcited by 24
  8. 2020Stochastic Subspace Cubic Newton Methodcited by 21
  9. 2020A stochastic subspace approach to gradient-free optimization in high dimensionscited by 16
  10. 2020A One-bit, Comparison-Based Gradient Estimatorcited by 16
  11. 2019Global Convergence Rate Analysis of a Generic Line Search Algorithm with Noisecited by 13
  12. 2021Scalable Subspace Methods for Derivative-Free Nonlinear Least-Squares Optimizationcited by 10
  13. 2019A Stochastic Derivative-Free Optimization Method with Importance Sampling: Theory and Learning to Controlcited by 9
  14. 2019A Stochastic Derivative Free Optimization Method with Momentumcited by 9
  15. 2020A dimensionality reduction technique for unconstrained global optimization of functions with low effective dimensionalitycited by 7
  16. 2021Global optimization using random embeddingscited by 6
  17. 2019Efficient Implementation of Second-Order Stochastic Approximation Algorithms in High-Dimensional Problemscited by 3
  18. 2020AdaDGS: An adaptive black-box optimization method with a nonlocal directional Gaussian smoothing gradientcited by 3
  19. 2020The Hessian Estimation Evolution Strategycited by 2
  20. 2020Hessian Inverse Approximation as Covariance for Random Perturbation in Black-Box Problemscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 3.

7 papers.

  1. 2024Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmarkcited by 114
  2. 2025ZeroFlow: Overcoming Catastrophic Forgetting is Easier than You Thinkcited by 9
  3. 2025Leveraging Coordinate Momentum in SignSGD and Muon: Memory-Optimized Zero-Ordercited by 9
  4. 2025Converge Faster, Talk Less: Hessian-Informed Federated Zeroth-Order Optimizationcited by 3
  5. 2026Memory Efficient Full-gradient Attacks (MEFA) Framework for Adversarial Defense Evaluationscited by 0
  6. 2026Trust the Direction, Search the Step: Zero-and-First-Order Methods for LLM Fine-Tuningcited by 0
  7. 2026TACO: Ternary Absolute-max Column-wise One-sparse Optimizer for LLM Fine-Tuningcited by 0