Stochastic Subspace Descent Accelerated via Bi-fidelity Line Search
Nuojin Cheng [email protected], Alireza Doostan [email protected], Stephen Becker [email protected] · 2025
Read Stochastic Subspace Descent Accelerated via Bi-fidelity Line Search by Nuojin Cheng [email protected], Alireza Doostan [email protected], Stephen Becker [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-00162.txt.
Introduction
Nuojin Cheng and co-authors speed up optimization when each look at the problem is expensive and no gradient is available. Their 2025 paper introduces a bi-fidelity subspace descent method. It mixes many cheap, rough evaluations with a few accurate ones to build a stand-in model of the landscape.
The stand-in drives a backtracking line search that picks step sizes wisely, and the authors prove convergence under standard assumptions. Four testbeds show the pattern: a synthetic benchmark, a kernel regression problem, black-box attacks on classifiers, and fine-tuning a language model through an opaque interface. In each, the method reached better optima while spending far fewer of the costly accurate evaluations. The authors pitch bi-fidelity thinking as a general budget saver for zeroth-order optimization.
Catalog record
| CREATOR | Nuojin Cheng [email protected], Alireza Doostan [email protected], Stephen Becker [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-00162
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stochastic Subspace Descent Accelerated via Bi-fidelity Line Search Nuojin Cheng [email protected], Alireza Doostan [email protected], Stephen Becker [email protected] Abstract 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. 1 Introduction In this work, we are interested in the unconstrained optimization problem \bm{x}^{\ast}\in\argmin_{\bm{x}\in{\mathbb{R}}^{D}}f(\bm{x}), (1.1) where the objective function f:\mathbb{R}^{D}\to\mathbb{R} is assumed to be L-smooth (i.e., its gradient \nabla f is L-Lipschitz continuous). Crucially, we operate in a black-box setting where direct access to the gradient \nabla f is unavailable or computationally infeasible to obtain with low complexity (e.g., via closed-form expressions or automatic differentiation), thereby precluding the direct application of standard first-order or higher-order optimization techniques. Furthermore, we focus on high-dimensional scenarios where D is large (e.g., D\gtrsim 100 ), posing significant challenges related to computational cost and scalability for many traditional derivative-free optimization methods. The primary focus of this work is on selecting an appropriate step size (a.k.a learning rate) \alpha_{k}>0 for iterative descent schemes of the form: \bm{x}_{k+1}=\bm{x}_{k}-\alpha_{k}\bm{v}_{k}, (1.2) where \bm{v}_{k}\in{\mathbb{R}}^{D} represents an estimate of the true gradient \nabla f(\bm{x}_{k}) or another suitable descent direction at iteration k . Selecting an appropriate step size \alpha_{k} dynamically can significantly improve the convergence performance of the optimization process. This is illustrated in Figure 1 , where an example function is optimized using different methods with and without a step size tuning scheme. However, common practices in machine learning often involve either using a fixed step size throughout the optimization or employing a predefined adaptive step size scheduling, e.g., Duchi et al. 2011 . While convenient to implement, these approaches often neglect the intrinsic local geometry and characteristics of the objective function. In contrast, classical line search methods, including exact line search and backtracking algorithms, typically yield better step sizes by incorporating information from additional objective function evaluations within each iteration. However, the cost of these additional evaluations can render such methods impractical, particularly when the computational budget is limited – a common situation in black-box optimization or when evaluating f (or its gradients) is expensive. To address this limitation, we propose a novel approach to tune the step size by leveraging multi-fidelity evaluations of the objective function. Here, multi-fidelity modeling involves utilizing two or more levels of objective function representations: the high-fidelity (HF) objective f , which provides accurate but expensive evaluations, and one or more low-fidelity (LF) objectives that serve as cheaper, albeit less accurate, approximations of f . We emphasize that this multi-fidelity setup (often bi-fidelity, involving one HF and one LF model) does not necessarily need to originate from the problem’s inherent structure. Even for a problem initially defined with a single fidelity, a practitioner can potentially construct a multi-fidelity extension (e.g., by creating simplified surrogate models) to accelerate the optimization procedure, particularly through more informed step size selection. Figure 1 : Gradient descent (GD), coordinate descent (CD), and stochastic subspace descent (SSD), along with their respective backtracking line search (LS) variants for step size tuning, as well as the proposed Bi-fidelity SSD (BF-SSD), are evaluated on the “worst function in the world” example, detailed in Section 4.1 . For simplicity, we focus on the bi-fidelity case, where only two fidelity levels are considered. The HF objective, f^{\textup{HF}} , is treated as the ground-truth objective function, so we treat f^{\textup{HF}} and the f from Equation ( 1.1 ) synonymously. We construct simple bi-fidelity surrogates after obtaining the gradient estimation \bm{v}_{k} . Specifically, given the LF objective f^{\textup{LF}}:{\mathbb{R}}^{D}\to{\mathbb{R}} , the current position \bm{x}_{k} , \bm{v}_{k} , an initial step size \alpha_{\textup{max}} , and a budget n_{k} for HF evaluations at this step, the local 1D surrogate of the HF objective \varphi_{k}(\alpha)\coloneqq f^{\textup{HF}}(\bm{x}_{k}-\alpha\bm{v}_{k}):{\mathbb{R}}\to{\mathbb{R}} is constructed as \tilde{\varphi}_{k}(\alpha;n_{k})=\rho f^{\textup{LF}}(\bm{x}_{k}-\alpha\bm{v}_{k})+\tilde{\psi}_{k}(\alpha;n_{k}),\quad\alpha\in[0,\alpha_{\textup{max}}]. (1.3) Here, \rho is a scalar, and \tilde{\psi}_{k}(\cdot;n_{k}):{\mathbb{R}}\to{\mathbb{R}} is a piecewise linear function constructed using n_{k} HF evaluations. Once the surrogate \tilde{\varphi}_{k} is constructed, the step size is selected using backtracking line search by (approximately) solving \alpha_{k}=\argmin_{\alpha\in[0,\alpha_{\textup{max}}]}\tilde{\varphi}_{k}(\alpha;n_{k}). (1.4) Assuming the scalar \rho is properly chosen so that the difference d(\bm{x})\coloneqq f^{\textup{HF}}(\bm{x})-\rho f^{\textup{LF}}(\bm{x}) (1.5) is Lipschitz continuous, we show that the convergence of this descent method is guaranteed, and K_{\epsilon}=\mathcal{O}(L/\epsilon) iterations are needed to ensure that \min_{k}\lVert\nabla f^{\textup{HF}}(\bm{x}_{k})\rVert^{2} is \epsilon -small. Moreover, when the HF and LF functions are well-aligned, i.e., the Lipschitz constant W of d(\bm{x}) is small, the required number of HF function evaluations N_{\epsilon}=\mathcal{O}(WL^{2}/\epsilon+DL/\epsilon) is not large. For implementation, we focus on high-dimensional zeroth-order optimization problems, using the stochastic subspace descent (SSD) method ( Kozak et al. 2021 ) combined with the proposed step size tuning strategy, and call the resulting method bi-fidelity stochastic subspace descent (BF-SSD). BF-SSD demonstrates strong empirical performance across various tasks and holds great potential for future applications. 1.1 Related Work Line Search for Optimization Line search is a widely used method for determining step sizes in optimization algorithms. Line searches can be either exact, meaning that \alpha is chosen to exactly or almost exactly minimize f^{\textup{HF}}(\bm{x}_{k}-\alpha\bm{v}_{k}) , or inexact. Exact line searches are computationally expensive, so other than in special cases, they are rarely used in practice. Common inexact line search methods include backtracking line search ( Nocedal & Wright 1999 ) , the Polyak step size ( Polyak 1987 ) , spectral methods such as ( Barzilai & Borwein 1988 ) , and learning rate scheduling ( Duchi et al. 2011 ) . Among these, backtracking line search is particularly popular due to its simplicity and explainable design, often employing stopping criteria like the Armijo and Wolfe conditions ( Nocedal & Wright 1999 ) . However, backtracking line search increases the overall computational costs considerably due to the numerous function evaluations required at each iteration. One way to mitigate this issue is by constructing surrogate models to guide step size selection. For example, Yue & Meerbergen 2013 and Grundvig 2023 used reduced-order models to approximate the objective function during line search, while Mahsereci & Hennig 2017 and Cartis & Scheinberg 2018 employed a probabilistic Gaussian model for step size selection. Paquette & Scheinberg 2020 provided a theoretical analysis of line search in stochastic optimization. A recent work by Nguyen et al. 2025 extends the