# Stochastic Subspace Descent Accelerated via Bi-fidelity Line Search

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 56 references that are in the map.
- First posted on arXiv 30 Apr 2025.

## Builds on (most cited first, 26 of 26)

- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023)
- [Black-Box Tuning for Language-Model-as-a-Service](https://mlsanity.com/paper/2201.03514/) (2022)
- [A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning](https://mlsanity.com/paper/2006.06224/) (2020)
- [Survey of multifidelity methods in uncertainty propagation, inference, and optimization](https://mlsanity.com/paper/1806.10761/) (2018)
- [Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark](https://mlsanity.com/paper/2402.11592/) (2024)
- [Practical Multi-fidelity Bayesian Optimization for Hyperparameter Tuning](https://mlsanity.com/paper/1903.04703/) (2019)
- [DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Training](https://mlsanity.com/paper/2310.02025/) (2023)
- [Sparse MeZO: Less Parameters for Better Performance in Zeroth-Order LLM Fine-Tuning](https://mlsanity.com/paper/2402.15751/) (2024)
- [BBTv2: Towards a Gradient-Free Future with Large Language Models](https://mlsanity.com/paper/2205.11200/) (2022)
- [Probabilistic Line Searches for Stochastic Optimization](https://mlsanity.com/paper/1502.02846/) (2015)
- [Global convergence rate analysis of unconstrained optimization methods based on probabilistic models](https://mlsanity.com/paper/1505.06070/) (2015)
- [Bi-fidelity Modeling of Uncertain and Partially Unknown Systems using DeepONets](https://mlsanity.com/paper/2204.00997/) (2022)
- [Zeroth order optimization with orthogonal random directions](https://mlsanity.com/paper/2107.03941/) (2021)
- [A stochastic subspace approach to gradient-free optimization in high dimensions](https://mlsanity.com/paper/2003.02684/) (2020)
- [Neural Network Training Using ℓ1-Regularization and Bi-fidelity Data](https://mlsanity.com/paper/2105.13011/) (2021)
- [Stochastic Subspace Descent](https://mlsanity.com/paper/1904.01145/) (2019)
- [Bi-fidelity Variational Auto-encoder for Uncertainty Quantification](https://mlsanity.com/paper/2305.16530/) (2023)
- [Bi-fidelity Stochastic Gradient Descent for Structural Optimization under Uncertainty](https://mlsanity.com/paper/1911.10420/) (2019)
- [Certified Multi-Fidelity Zeroth-Order Optimization](https://mlsanity.com/paper/2308.00978/) (2023)
- [Stochastic ISTA/FISTA Adaptive Step Search Algorithms for Convex Composite Optimization](https://mlsanity.com/paper/2402.15646/) (2024)
- [Worst case complexity bounds for linesearch-type derivative-free algorithms](https://mlsanity.com/paper/2302.05274/) (2023)

## Abstract (arXiv)

Efficient optimization remains a fundamental challenge across numerous scientific and engineering domains, especially when objective function and gradient evaluations are computationally expensive. While zeroth-order optimization methods offer effective approaches when gradients are inaccessible, their practical performance can be limited by the high cost associated with function queries. This work introduces the bi-fidelity stochastic subspace descent (BF-SSD) algorithm, a novel zeroth-order optimization method designed to reduce this computational burden. BF-SSD leverages a bi-fidelity framework, constructing a surrogate model from a combination of computationally inexpensive low-fidelity (LF) and accurate high-fidelity (HF) function evaluations. This surrogate model facilitates an efficient backtracking line search for step size selection, for which we provide theoretical convergence guarantees under standard assumptions. We perform a comprehensive empirical evaluation of BF-SSD across four distinct problems: a synthetic optimization benchmark, dual-form kernel ridge regression, black-box adversarial attacks on machine learning models, and transformer-based black-box language model fine-tuning. Numerical results demonstrate that BF-SSD consistently achieves superior optimization performance while requiring significantly fewer HF function evaluations compared to relevant baseline methods. This study highlights the efficacy of integrating bi-fidelity strategies within zeroth-order optimization, positioning BF-SSD as a promising and computationally efficient approach for tackling large-scale, high-dimensional problems encountered in various real-world applications.