ReLIZO: Sample Reusable Linear Interpolation-based Zeroth-order Optimization

Thank you for your careful and valuable comments. We hope to address your concerns by answering your questions below.

Q1: As noted by the authors, the method imposes few constraints on sample size, similar to smoothing techniques, but requires gradient estimation through solving a linear program, which could be a potential limitation.

A1: Our approach indeed leverages the strengths of both linear interpolation-based and smoothing-based zeroth-order (ZO) methods, as highlighted in Remark (line 142). By solving a QCLP to estimate gradients, our method achieves higher accuracy compared to smoothing-based methods while maintaining lower computational costs than linear interpolation-based methods. Sec 3.3 also shows that part of the intermediate variables contributing to the gradient estimation can be directly indexed, significantly reducing the computation complexity of ReLIZO. Further analysis of the total computational complexity is provided in Section B and Table 4 in the appendix. Additionally, since optimization problems are often high-dimensional with a typically small sample size at each iteration (i.e. $n \ll d$), ReLIZO remains competitive in terms of speed.

Q2: As a zeroth-order algorithm, is ReLIZO suitable for large-scale applications, such as network training?

A2: Compared to gradient-based methods, ZO methods are well-suited for black-box optimization problems where gradients with respect to the variables are unavailable. Additionally, ZO methods are more memory-efficient than gradient-based methods since they do not require backward propagation, making them applicable to network training, as demonstrated by recent works [1,2]. Specifically, [1] introduces DeepZero, a principled ZO framework for deep learning that is computational-graph-free and can scale to deep neural network training with performance comparable to first-order methods. [2] also applies ZO methods to large language model (LLM) fine-tuning, highlighting their memory efficiency and introducing a ZO-LLM benchmark.

To illustrate the applicability of ReLIZO in network training, we adopt it for fine-tuning an OPT-1.3b model (with 1.3 billion parameters) on the Stanford Sentiment Treebank v2 (SST2) task, following the methodology of [2]. The results, shown in the table below, indicate that ReLIZO outperforms other ZO methods across various fine-tuning schemes, including full parameter fine-tuning (FT), LoRA, Prefix-tuning, and Prompt-tuning. Notably, ReLIZO even surpasses SGD in the FT scheme while requiring significantly less memory, demonstrating its promising potential.

[1] Chen A, Zhang Y, Jia J, et al. DeepZero: Scaling Up Zeroth-Order Optimization for Deep Model Training[C], ICLR 2024.

[2] Zhang Y, Li P, Hong J, et al. Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark[C], ICML 2024.

Q3: I wonder if the proposed method could really facilitate the community of NAS? As zero-order optimization is not common in NAS.

A3: Recent studies [4,5,6] have explored zeroth-order optimization methods for solving bi-level optimization problems, including NAS task, where gradients of the parameters in the upper-level objective function are typically unavailable. These works highlight the limitations of gradient-based methods for NAS and demonstrate that ZO methods can outperform gradient-based approaches by providing more accurate gradient estimations of architecture parameters in the upper-level objective function. Nevertheless, this work aims to introduce a brand-new zero-order optimization algorithm and we apply it to NAS tasks to evaluate its performance on bi-level optimization problem.

[4] Wang X, Guo W, Su J, et al. Zarts: On zero-order optimization for neural architecture search[J]. NeurIPS, 2022.

[5] Xie L, Huang K, Xu F, et al. ZO-DARTS: Differentiable architecture search with zeroth-order approximation[C]. ICASSP, 2023.

[6] Aghasi A, Ghadimi S. Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing[J]. arXiv preprint arXiv:2404.00158, 2024.

Thank you for your careful and valuable comments. We hope to address your concerns by answering your questions below.

Q1: The effectiveness of reusing queries depends on the choice of the reusable distance bound, which might require fine-tuning for different applications, adding complexity to its implementation.

A1: In our method, the reusable distance bound $b$ restricts the distances between reusable samples and the current point and should be of the same order of magnitude as the step size. Following previous ZO research (Table 1 in [1]), we set the step size $\eta$ to $O(\frac{1}{d})$ to ensure convergence.Thus, we choose $b \sim O(\frac{1}{d})$. Ablation studies presented in Fig. 2 (in the main paper) and Fig. 4 (in the appendix) demonstrate that setting $b = 2\eta$ performs well across different optimization tasks and sample sizes $N$.

As you noted, the reusable distance bound $b$ plays a critical role in balancing speed and accuracy. A larger $b$ can increase the reuse rate, reduce the number of queries, and accelerate the process. However, it also introduces a larger residual term $o(y-x)$ in the first-order Taylor expansion, leading to an increase in relative error. Therefore, the value of $b$ must be adjusted according to the specific application. From this perspective, an adaptively adjustable reusable distance bound $b$ during the optimization process would be ideal, and we plan to explore this in future work.

[1] Ji, Kaiyi, et al. "Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization." ICML 2019.

Q2: While the method reduces the number of function queries, solving the quadratically constrained linear program (QCLP) may introduce additional computational overhead for large values of $n$.

A2: As the sample size $n$ increases, the cost of solving the QCLP also tends to increase. However:

• On one hand, in zeroth-order optimization, the sample size $n$ is typically small compared to the dimension $d$ and satisfies $n\ll d$ in high-dimension optimization problems to ensure efficiency (e.g. in black-box adversarial attacks, the variable dimension $d=3072$ while the sample size $n=10$). The performance of ZO methods in such extreme cases where $n\ll d$ is crucial for assessing their scalability and robustness. Our experiments, detailed in Appendix C.1, demonstrate the effectiveness of our method even under these conditions.
• On the other hand, Sec. 3.3 introduces a strategy for indexing some intermediate variables that contribute to gradient estimation, significantly reducing the computational complexity of solving the QCLP. We also provide a detailed analysis and comparison of the computation complexity of various ZO methods in Appendix B and Table 4, showing that our ReLIZO method is more computationally efficient than other linear interpolation-based methods. Furthermore, as the sample size $n$ increases, the number of reusable queries also increases with the same step size and reusable distance bound, leading to additional time savings compared to other ZO methods that do not support query reuse.

Q3: In Figure 5, the results for the ARGTRIGLS problem indicate a performance drop with any reusable distance bound. What is the specific structure of this problem? Does this suggest that the reuse strategy might be ineffective in certain special cases?

A3: ARGTRIGLS is a specialized academic problem designed to evaluate optimization algorithms. It is a variable dimension trigonometric problem in least-squares form, expressed as a sum of $n$ least-squares groups, each containing $n+1$ nonlinear elements. This problem is a variant of Problem 26 in [1], which can be written as follows:

Given $f_i:\mathbb{R}^n\rightarrow\mathbb{R}$ $f_i(x) = n-\sum_{j=1}^n cos(x_j) +i (1-cos(x_i)) - sin(x_i)$ and initial point $x^0= (\frac{1}{n},\cdots,\frac{1}{n})$, solve $\min\\\{ \sum_{i=1}^n f_i^2(x):x \in \mathbb{R}^n\\\}$

In Figure 5, we observe a relative performance drop (slightly slower convergence) when the reusable distance bound $b\geq \eta$, However, this does not imply that the reuse strategy is ineffective in this case. The ARGTRIGLS problem is characterized by a rugged landscape with numerous local minima. In this case, as shown in Figure 4(b), even with $b=\eta$ and a sample size $n=8$, the reuse rate of ARGTRIGLS exceeds 90%, whereas reuse rates for other problems are generally below 50% (e.g. MANCINO with d=100 in Figure 4(a), SROSENBR with d=500 in Figure 2(b)). This high reuse rate indicates that the number of new queries during optimization is relatively small, contributing to the observed decrease in convergence speed.

To address this issue, we can employ simple strategies such as reducing the reusable distance bound $b$. The table below illustrates that performance improves as $b$ decreases:

Moreover, setting an upper bound for the reuse rate in each iteration can also help. The following table reports the performance when the maximum reuse rate in each iteration is restricted to 50%. We observe that with $b\leq0.05\eta$ and 2000 iterations, there is minimal performance degradation, even with a reuse rate of approximately 30%:

As discussed in A1, an adaptively adjustable reusable distance bound $b$ aligned with the optimization process would be advantageous in this context. We plan to explore this approach in future work.

Thank you for your careful and valuable comments. We hope to address your concerns by answering your questions below.

Q1: Zeroth-order gradient estimation has a relatively limited impact. This limitation is exemplified in the NAS evaluation, where ReLIZO does not consistently achieve optimal performance.

A1: Thank you for highlighting the inherent limitations of zeroth-order (ZO) methods. Though it is true that ZO methods generally face these constraints, they offer significant advantages over gradient-based methods in black-box optimization scenarios where gradients with respect to variables are not available. Additionally, ZO methods tend to be more memory-efficient, since they do not require backward propagation. This makes them suitable for large-scale tasks such as fine-tuning large language models (LLMs), as demonstrated in recent work [1]. We applied our method to fine-tune an OPT-1.3b model (with 1.3 billion parameters) on the Stanford Sentiment Treebank v2 (SST2) task, and the results are summarized in the table below:

Regarding NAS tasks, DARTS and GDAS are two classic gradient-based methods with distinct settings. DARTS trains all parameters in the supernet at each iteration, whereas GDAS samples a sub-network from the supernet at each iteration and trains only the parameters within that sub-network. Our experiments employed DARTS's settings. The results in Table 2 demonstrate that all ZO methods outperform DARTS, and ReLIZO surpasses all other ZO methods, highlighting the effectiveness of our approach.

[1] Zhang Y, Li P, Hong J, et al. Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark[C], ICML 2024.

Q2: In ReLIZO algorithm, new samples in each iteration is random and arbitrary. There might be more effective strategies to sample new vectors based on known information.

A2: Thank you for your suggestion. The ability of ReLIZO to sample new vectors from an arbitrary distribution can be considered one of its strengths compared to other ZO methods. In contrast, smoothing-based ZO methods have to rely on Gaussian or uniform distributions with a mean of zero. We appreciate your insight and introduce an effective sampling strategy inspired by SGD with momentum. Specifically, we propose a sampling momentum strategy where the sampling probability in the current iteration follows a distribution defined as $p(x_t) = \alpha N(g_{t-1}, \sigma) + (1-\alpha)N(0, \sigma)$, with $N()$ denoting a Gaussian distribution, $g_{t-1}$ is the estimated gradient in the last iteration, $\alpha$ as the momentum parameter, and $\sigma$ as the standard deviation. The results of this approach, labeled as ReLIZO-m, are presented in the table below:

These experimental results demonstrate that incorporating an effective sampling strategy can significantly enhance performance. We plan to explore this approach in greater depth in future work.