Gradient-Free Optimization for Matrix functions
Abstract
We consider the task of optimizing smooth, possibly non-convex functions of a matrix variable given access only to directional derivatives rather than full gradients. This setting arises when fine-tuning large neural networks on consumer-grade hardware: the network's weights are matrices, memory constraints rule out backward-mode automatic differentiation, but directional derivatives remain available through forward mode. We frame gradient estimation in this setting as a structured recovery problem, in the spirit of signal processing. From this perspective we provide three contributions. First, we introduce an alternative to the standard random gradient estimator; the difference corresponds to replacing the adjoint of the sampling operator with its pseudoinverse. Second, when the gradient satisfies an approximate low-rank condition, techniques from matrix sensing yield a family of highly accurate gradient estimators that drop into any first-order method. Third, we note that while the computational cost of such estimators is high, this can be amortized by combining them with a matrix-aware optimizer such as spectral descent. Specifically, the gradient estimator computes a factorization of the gradient, allowing for the projection step of spectral descent to be done at no extra cost. We demonstrate our findings with two careful numerical experiments on synthetic functions with approximately low-rank gradients. We show that by exploiting this low-rank property one obtains much faster convergence to good approximate solutions.
Related
- Minimax optimality for sequential gradient-free minimization of smooth functions and their derivatives
- Gradient-Free Methods for Stochastic Convex Optimization with Stochastic Functional Constraints
- Lower Bounds For Gradient-Free Convex Optimization And Convex-Concave Saddle-Point Problems
- Initial condition recovery in nonlinear damped viscous photoacoustic tomography using a convolutional neural network-guided gradient-free optimization framework
- Direct Sample-Average Learning for Queueing Control: Gradient-Free Top-K Coarse-to-Fine Optimization
BibTeX
@misc{allen2026gradientfree,
title = {{Gradient-Free Optimization for Matrix functions}},
author = {Sawyer Allen and Cash Cherry and Aidan Eck and Stephen Becker and Daniel McKenzie},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03170},
eprint = {2609.03170},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03170},
}
RIS
TY - UNPB
TI - Gradient-Free Optimization for Matrix functions
AU - Sawyer Allen
AU - Cash Cherry
AU - Aidan Eck
AU - Stephen Becker
AU - Daniel McKenzie
PY - 2026
DA - 2026/09/02
PB - arXiv
DO - 10.48550/arxiv.2609.03170
UR - https://arxiv.org/abs/2609.03170
AB - We consider the task of optimizing smooth, possibly non-convex functions of a matrix variable given access only to directional derivatives rather than full gradients. This setting arises when fine-tuning large neural networks on consumer-grade hardware: the network's weights are matrices, memory constraints rule out backward-mode automatic differentiation, but directional derivatives remain available through forward mode. We frame gradient estimation in this setting as a structured recovery problem, in the spirit of signal processing. From this perspective we provide three contributions. First, we introduce an alternative to the standard random gradient estimator; the difference corresponds to replacing the adjoint of the sampling operator with its pseudoinverse. Second, when the gradient satisfies an approximate low-rank condition, techniques from matrix sensing yield a family of highly accurate gradient estimators that drop into any first-order method. Third, we note that while the computational cost of such estimators is high, this can be amortized by combining them with a matrix-aware optimizer such as spectral descent. Specifically, the gradient estimator computes a factorization of the gradient, allowing for the projection step of spectral descent to be done at no extra cost. We demonstrate our findings with two careful numerical experiments on synthetic functions with approximately low-rank gradients. We show that by exploiting this low-rank property one obtains much faster convergence to good approximate solutions.
ER -