# Curvature-Aware Derivative-Free Optimization

arXiv: https://arxiv.org/abs/2109.13391 · HTML: https://mlsanity.com/paper/2109.13391/

## 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 (most cited first, 30 of 32)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Square Attack: a query-efficient black-box adversarial attack via random search](https://mlsanity.com/paper/1912.00049/) (2019)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [Black-box Adversarial Attacks with Limited Queries and Information](https://mlsanity.com/paper/1804.08598/) (2018)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning](https://mlsanity.com/paper/2006.06224/) (2020)
- [Sign-OPT: A Query-Efficient Hard-label Adversarial Attack](https://mlsanity.com/paper/1909.10773/) (2019)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization](https://mlsanity.com/paper/1905.01332/) (2019)
- [Stochastic Zeroth-order Optimization in High Dimensions](https://mlsanity.com/paper/1710.10551/) (2017)
- [Structured Evolution with Compact Architectures for Scalable Policy Optimization](https://mlsanity.com/paper/1804.02395/) (2018)
- [Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling](https://mlsanity.com/paper/2003.13001/) (2020)
- [A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization](https://mlsanity.com/paper/2102.10707/) (2021)
- [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019)
- [Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients](https://mlsanity.com/paper/1806.00413/) (2018)
- [Stochastic Three Points Method for Unconstrained Smooth Minimization](https://mlsanity.com/paper/1902.03591/) (2019)
- [Safeguarded Learned Convex Optimization](https://mlsanity.com/paper/2003.01880/) (2020)
- [Stochastic Subspace Cubic Newton Method](https://mlsanity.com/paper/2002.09526/) (2020)
- [A stochastic subspace approach to gradient-free optimization in high dimensions](https://mlsanity.com/paper/2003.02684/) (2020)
- [A One-bit, Comparison-Based Gradient Estimator](https://mlsanity.com/paper/2010.02479/) (2020)
- [Global Convergence Rate Analysis of a Generic Line Search Algorithm with Noise](https://mlsanity.com/paper/1910.04055/) (2019)
- [Scalable Subspace Methods for Derivative-Free Nonlinear Least-Squares Optimization](https://mlsanity.com/paper/2102.12016/) (2021)
- [A Stochastic Derivative-Free Optimization Method with Importance Sampling: Theory and Learning to Control](https://mlsanity.com/paper/1902.01272/) (2019)
- [A Stochastic Derivative Free Optimization Method with Momentum](https://mlsanity.com/paper/1905.13278/) (2019)
- [A dimensionality reduction technique for unconstrained global optimization of functions with low effective dimensionality](https://mlsanity.com/paper/2003.09673/) (2020)
- [Global optimization using random embeddings](https://mlsanity.com/paper/2107.12102/) (2021)
- [Efficient Implementation of Second-Order Stochastic Approximation Algorithms in High-Dimensional Problems](https://mlsanity.com/paper/1906.09533/) (2019)
- [AdaDGS: An adaptive black-box optimization method with a nonlocal directional Gaussian smoothing gradient](https://mlsanity.com/paper/2011.02009/) (2020)

## Built on by (most cited first, 7 of 7)

- [Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark](https://mlsanity.com/paper/2402.11592/) (2024)
- [ZeroFlow: Overcoming Catastrophic Forgetting is Easier than You Think](https://mlsanity.com/paper/2501.01045/) (2025)
- [Leveraging Coordinate Momentum in SignSGD and Muon: Memory-Optimized Zero-Order](https://mlsanity.com/paper/2506.04430/) (2025)
- [Converge Faster, Talk Less: Hessian-Informed Federated Zeroth-Order Optimization](https://mlsanity.com/paper/2506.02370/) (2025)
- [Memory Efficient Full-gradient Attacks (MEFA) Framework for Adversarial Defense Evaluations](https://mlsanity.com/paper/2605.06357/) (2026)
- [Trust the Direction, Search the Step: Zero-and-First-Order Methods for LLM Fine-Tuning](https://mlsanity.com/paper/2610.02190/) (2026)
- [TACO: Ternary Absolute-max Column-wise One-sparse Optimizer for LLM Fine-Tuning](https://mlsanity.com/paper/2610.02199/) (2026)

## 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.